RSA

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Entwurf öffentlicher Schlüssel (e, N) 2 Entwurf privater Schlüssel (d) 3 Bob verschlüsselt die Nachricht M 4 Alice entschlüsselt die Nachricht C 5 RSA-Faktoring-Challenge 5.1 Warum ist das RSA-Verfahren mit kleinen Primzahlen immer noch unsicher? (Wozu benötigt man möglichst große Primzahlen?) 5.2 Was bedeutet 205 Bit? 5.3 Wie groß sollten zwei sichere Primzahlen sein? 6 Wir verschlüsseln uns Nachrichten gegenseitig 6.1 Ruben 6.2 Leonie 6.3 Jan-Niklas 6.4 Luis 6.5 Clemens 6.6 Maximilian 6.7 Janine 6.8 Simon 6.9 Ben 6.10 Conrad 6.11 Philip

Entwurf öffentlicher Schlüssel (e, N)

Lege zwei (große) Primzahlen und fest mit .

Bilde das Produkt .

Suche eine weitere Zahl , für die gilt:

• ist Primzahl und größer als und oder
• ist teilerfremd zu .

Die Zahlen und bilden den öffentlichen Schlüssel.

Entwurf privater Schlüssel (d)

• und
• 

Bob verschlüsselt die Nachricht M

Voraussetzung: öffentlicher Schlüssel (e, N) Ein Klartext-Zeichen mit dem Code wird mit

zu verschlüsselt.

Alice entschlüsselt die Nachricht C

Voraussetzung: privater Schlüssel d, öffentlicher Schlüssel N, Code C Der verschlüsselte Code wird mit

zum Code des Klartext-Zeichens entschlüsselt.

RSA-Faktoring-Challenge

Warum ist das RSA-Verfahren mit kleinen Primzahlen immer noch unsicher? (Wozu benötigt man möglichst große Primzahlen?)

Je kleiner D ist, desto einfacher und schneller sind die Primzahlen zu berechnen. Je größer die Primzahlen, desto schwieriger sind sie zu berechnen, was dementsprechend auch etwas länger dauert.

Was bedeutet 205 Bit?

"205 Bit" beschreibt die Länge der Zahl D. Die benötigte Zeit zur Decodierung eines 500 Bit-Schlüssels beträgt ca. 12 Jahre.

Wie groß sollten zwei sichere Primzahlen sein?

> 500 Bit

Wir verschlüsseln uns Nachrichten gegenseitig

Ruben

N=2290688290035092561 e=2^16+1

Geheimtext: C=0212462476451503813 # 0279022256428772954 # 0726293796104265093 # 2114811903790655993 # 1906335504232360310

Leonie

N=1842409465748009713 e=2^16+1

Geheimtext: 1168545598385321835 # 0036148981711874247 # 0586194511655934941 # 1542393816097386545 # 0128534568308589811 # 0747839941646094815 # 0694638595198958223 # 1379050199896526745 # 0706773945999946229

An Leonie von Philip: 0697673231366207881 # 1208374688665456941 # 1543382662282259903 # 0941826729310981749

Jan-Niklas

N= 3309019631962708007 e= 2^16+1

Geheimtext: 1914015104544774280 # 0036113690470850931 # 1825425302363606094 # 1848016099996873123 # 0051200623084067679 # 0551406544958756924 # 0241765583180759526 # 1543993545553785700 # 0278303469076891331 # 1823376381807561391 # 0977433526029579769 # 2178622118281208195 # 2165958113226190575 # 2009867642660396772 # 0478196083564867201 # 0299784635874717821 # 0298578127907452904 # 0418962187348818955 # 2541547431346270569 # 2475389964927491292 # 1567844731340249973 # 1041951082461066510 # 0856137878660897242 # 0288424509494031188 # 2293564936763893194 # 0552243076539978507 # 0599766257310047306 # 0609099107251874084 # 2619503438561745221 # 1330019863132126576 # 1057874459921951620 # 1896866491894649448 # 1192048924374843048 # 2496457168663939101 # 2521106948523856344 # 1123366733019931036 # 1487648329472786255 # 0860758396814990478 # 0801302431135626333 # 1351495023137725678 # 1403039762047628813 # 1335155860119522280 # 2494230495659964750 # 2726334050947999279 # 0927308040938273492 # 2583723444355681462 # 1623319584435442094 # 0145484810078557816 # 2290522950202233335 # 2401212265040826825 # 0558309210333318637 # 0796720229355254049 # 1202962077810465831 # 1118783701724099571 # 2090495585653198425 # 1510229106606903617 # 1776619924664447448 # 1401501130504123361 # 1563818568650875106 # 0271163217206601919 # 1985726545793521740 # 0851900714282186130 # 0862466400798624123 # 0709843161315564812 # 1398256373777854267 # 2597780099004202887 # 1211450578055534032 # 0917953628707397495 # 1912314193774309652 # 0098015191266359824 # 1554027165121681157 # 1088333704258717377 # 2698039500123505105

Luis

N=2795965616980517393

e=2^16+1

C= 1333233286463615700 # 0708527331786119064 # 2163227009381983473 # 2411244037288682174 # 1212846559725028710 # 1308111605561231331 # 0875129857703868159 # 0686044196831477305 # 2307490620937485971 # 0491184812172321734 # 1045741775702889969 # 1882831420888612690 # 2037756380541617532 # 2171578416014337757 # 1100326950715651735 # 2404432962787207845 # 1516328171955516563 # 0194425482949772980 # 2098648635157794873 # 0851314707264195693 # 2220297434633114101 # 1396605374493508458 # 0345895868714776013 # 0212674872662452393 # 1577261496737528986 # 1302862516368554164 # 0592030642502312243 # 1882203461957851486 # 0196750972909396965 # 0674166861351593621 # 2728620239068851958 # 1291888193692865571 # 1558384027931238804 # 1014357105794701016 # 2733919787642090632 # 2410635504270598780 # 2459835622552720818 # 0777281217025424678 # 2588883817717013114 # 0234847078567215625 # 0912805560890878612 # 1025824763877794156 # 0836212576150668600 # 1505736909441015864 # 0478326768009647474 # 0692006511144136312 # 1063146662938393489 # 2322282841270258932 # 2171130895046335404 # 1160483363925337022 # 0843956826059151944 # 0194718076111614810 # 0008902751985266667 # 0631317865204689562 # 2339164678082255037 # 1109799858490269083 # 1152508097274500745 # 2538343925450617470 # 0048550476277388532 # 1976277295982023844 # 1947772415970867064 # 1552684370308459041 # 2023528764694776687 # 0212674872662452393 # 2752204238113798364 # 0773573159900051333 # 2292787681850181778

Clemens

N= 75294756853 e= 2^16+1

59928078434 # 72589273530 # 16173716565 # 44713393784 # 52737605255 # 17184688515 # 46789022858 # 73855319516 # 59825312824 # 27680072701 # 49113742458 # 34690376144 # 35898905995 # 20022963209 # 51298474478 # 40307260494 # 37964653703 # 03980169672 # 02123950179 # 16710337180 # 04049797956

Maximilian

N = 3038043574127449361 e = 2^16+1

C= 1191945890916496238 # 0749104075417921294 # 2050920325587402138 # 2033322791783987871 # 2179912618785326176 # 2153547974032296128 # 0956406643232635675 # 1790666851702612133

Janine

N=2852579451223911293 e=2^16+1

Geheimtext: 1616028400802717015 # 2497530724502264956 # 0608263158308991269 # 0070416642992101753 # 1866989425014299148 # 1729590572269052699 # 1269877043949650330

Simon

N=2634640713694040663 e=2^16+1

1034836196066802899 # 2163387804459873831 # 2239945373948065010 # 1716904572690322764 # 2061974359428766560 # 2040847074043526100

Ben

N = 1795709734003242829 e = 2^16+1 Text: 0333378004246563002 # 1136093563807890709 # 0620991995616976189 # 1789808277132306342 # 1748717074485970508 # 0322120309615070086 # 0072878267165740422 # 0253255900752465152 # 1713660336361021332

Conrad

Philip

N=4125102652534801589 e=2^16+1

Geheimtext: 1815024155428420827 # 3284010809428653411 # 0367427517137291942 # 0504627377733545442 # 1745829803632146976 # 2786027334438664711 # 2352481224462571264 # 2211490466078446646 # 0542925682235426235 # 0291033818027795791 # 2770160186396651385 # 3539585172582904096 # 2716069200541142812 # 1120922036507121308 # 3242417184077934468

c¹: 2861100816995380767 # 1588060076981043803 # 1715334948567646853 # 3197898792589795440 # 2218660437173957464 # 1493760890519279434 # 0597472692900133456 # 2300766234407201140