LKG/Inf 11 2011/RSA

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
[[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''.

=== Wir verschlüsseln Nachrichten gegenseitig ===

==== Beispiel ====
öffentlicher Schlüssel: N=2212356658925775797
e=2^16+1

verschlüsselte Nachricht=0154053610309353007 # 0414178728190804750 # 1697057945399357863 # 2070423477403309778 # 1073508525444459212 # 0381990340997203895 # 1748647492571070100 # 0323355113406576190 # 0471324455178646453 # 1739775672006346255 # 0855733748764982545 # 1461509390385958697

==== Francie ====
öffentlicher Schlüssel: N=3731025641594503419741568882036125135837845056174901063114772391450747468526864965794292224829891688137917429316289568460271299239065078112443623687838629568510542255492389063296175280669776877707334497193764513489277038692096195412993414900686944115768986159035694128952775007718968586809542667566421923196571262318520819230206433623217346183718867262047639367

e=2^16+1

verschlüsselte Nachricht=0417939609475754312 # 1060955068056772435 # 1258214308725367701 # 1389478806375584696 # 0346553690748376968 # 0570059529587367499 # 0733480071254248446 # 1261445539584838999 # 0039435362133118661 # 0912735714777767741

==== Richard ====
öffentlicher Schlüssel: N=

173207312716345347388228167089849158229323171875688189180524243919601277410144791544465289459957790317002541646794123746658335851669437800686755984353141198569869096505364467877464490320461721129036994279229771120412405822986461323095040596446169452324548441940247516071235592303813319426855251114722477604741686057975838269244139298976249487806543864904484539

e=2^16+1

verschlüsselte Nachricht=020972515483720612305316420754157281061056598460332073014261675470200449751444010728474865733702829017323832415763496705189491573442308196585593245338408367280494454582082188417523860397589287508224480168803462485165428087601319704610927923692157112374434862405264993906500058558317387868483219990385762678778856083061118135907795150917072016434934537520925475

==== Philipp H. ====
öffentlicher Schlüssel: N= 40462136585917579212629197045439538492413313611857142688963241293681293736732847745235727062248825655910471095971256868158435979680882227001006548418162349279127183764367549815533485911172923931599236691394243585460443637554602198544388733295952491668293506568601135474117538851950934808117765279271810843646942849656792401735283336468090391533038839588457081 
e= 2^16+1

verschlüsselte Nachricht=

==== Philipp S. ====
öffentlicher Schlüssel: N=47365052785923405877749601542710450495290496153256556813096853784484624221642121422260794468131672417938012227781533752371191684340376706464554264808148924726247726713143549554493614456950606889979518146187810021018427728612455315511156959621246501195598384742021922323213196051166659731215569405906749044462872890103107232317961577804123434044411518082801060687400935397832368569542626605163458392115773356130127231653867
e=2^16+1

verschlüsselte Nachricht=
0757589266590435829149250651183037826820240747015960616781942643604883729370669501389907819261175669942112938960656736425157937249325510250533521173575842926207616942465102996120620442699849967551410714865558512877620616288407103340234862705221285920360374173471020375512243664913564617419717128224827219022494115785450437318736905706012015151473407414512021691

==== Tobias ====
öffentlicher Schlüssel: N=1392591820228166155816688383886133939396497247225108937050742695863681846726864582644556591198341546200327317385519027717624983738017741013544440271594873087849099030320504915829915767387889361239137047141799130032511190188205166488858575753568542478783222560186344650236124822535703612524702239712828397167120792274198582504828575161412533920388062991850528297
e=2^16+1

verschlüsselte Nachricht=
0802354138280909266280586804919451106232058148819604601058868128564436610823846119737510090503053599565160326577015653875655347187301344378876387098392789699640667692725049220949303824513249672575297187199409074997287485542471249364696260450753217942220162332240541549488105224033332419621617027707361008934446351375165578545311869164451543191305059871210742732

==== Jessie ====
öffentlicher Schlüssel: 

N= 13925918202281661558166883838861339393964972472251089370507426958636818467268645826445565911983415462003273173
85519027717624983738017741013544440271594873087849099030320504915829915767387889361239137047141799130032511190
18820516648885857575356854247878322256018634465023612482253570361252470223971282839716712079227419858250482857
5161412533920388062991850528297

e= 2^16+1

verschlüsselte Nachricht= 2833064651890972196 # 1207466354618744003

==== Felix ====
öffentlicher Schlüssel: N=2067500669502472369228111472592470862747493142585099535992808515150800589274468701699859352853365869030476044365363328820750758777023368085412623120390833844339066038217166530149962676455959868282361611790872645433423880635706042713638514225337059156062742620829740407904430750748323688708139105503819548995010150997549284551725238872657475890658436538649506271
e=2^16+1

verschlüsselte Nachricht=

==== Henri ====
öffentlicher Schlüssel: N=1573800593199814937
e=2^16+1

verschlüsselte Nachricht= 068323648144579065 # 0990084553871274927 # 1311280311930049458 # 0843323830638507610 # 1106220979580947313 # 0685672372419448786 # 1265585044974512265 # 1372958567399979422 # 0124366538256305897 # 1416334406985722316 # 0554230601006169976 # 0289824759239524350 # 1059336406429740812 # 1543618570264532185 # 0824900330332617813 # 1548264951443031537 # 0548021684665399878 # 0716876255052240635

N=1392591820228166155816688383886133939396497247225108937050742695863681846726864582644556591198341546200327317385519027717624983738017741013544440271594873087849099030320504915829915767387889361239137047141799130032511190188205166488858575753568542478783222560186344650236124822535703612524702239712828397167120792274198582504828575161412533920388062991850528297
e=2^16+1


[http://de.wikipedia.org/wiki/RSA_Factoring_Challenge RSA-Factoring-Challenge]