EGE/RSA

Wiki-Quelltext dieser Seite.

[[Bild:schema_rsa.png]]
== Entwurf öffentlicher Schlüssel (e, N) ==
Lege zwei (große) Primzahlen <math>p</math> und <math>q</math> fest mit <math>p \neq q</math>.

Bilde das Produkt <math>N = p \cdot q</math>.

Suche eine weitere Zahl <math>e</math>, für die gilt:
* <math>e</math> ist Primzahl und größer als <math>p</math> und <math>q</math> <u>oder</u>
* <math>e</math> ist teilerfremd zu <math>(p-1) \cdot (q-1)</math>.
Die Zahlen <math>e</math> und <math>N</math> bilden den ''öffentlichen Schlüssel''.

== Entwurf privater Schlüssel (d) ==
* <math>d \le (p-1) \cdot (q-1)</math> <u>und</u>
* <math>(d \cdot e) \bmod [(p-1) \cdot (q-1)] = 1</math>

== Bob verschlüsselt die Nachricht M ==
Voraussetzung: öffentlicher Schlüssel (e, N)
Ein Klartext-Zeichen mit dem Code <math>M</math> wird mit
<blockquote><math>M^e \bmod N = C</math></blockquote>
zu <math>C</math> ''verschlüsselt''.

== Alice entschlüsselt die Nachricht C ==
Voraussetzung: privater Schlüssel d, öffentlicher Schlüssel N, Code C
Der verschlüsselte Code <math>C</math> wird mit
<blockquote><math>C^d \bmod N = M</math></blockquote>
zum Code <math>M</math> 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? ===

<!--[https://vimeo.com/114048258 RSA mit dem Android-Handy] ansehen und versuchen, umzusetzen.-->
> 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