RSA

Aus ProgrammingWiki

< LKG/Inf 11 2011

Wechseln zu: Navigation, Suche

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 Wir verschlüsseln Nachrichten gegenseitig

Entwurf öffentlicher Schlüssel (e, N)

Lege zwei (große) Primzahlen $p$ und $q$ fest mit $p \neq q$ .

Bilde das Produkt $N = p \cdot q$ .

Suche eine weitere Zahl $e$ , für die gilt:

$e$ ist Primzahl und größer als $p$ und $q$ oder
$e$ ist teilerfremd zu $(p-1) \cdot (q-1)$ .

Die Zahlen $e$ und $N$ bilden den öffentlichen Schlüssel.

Entwurf privater Schlüssel (d)

$d \le (p-1) \cdot (q-1)$ und
$(d \cdot e) \bmod [(p-1) \cdot (q-1)] = 1$

Bob verschlüsselt die Nachricht M

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

$M^e \bmod N = C$

zu $C$ verschlüsselt.

Alice entschlüsselt die Nachricht C

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

$C^d \bmod N = M$

zum Code $M$ 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=2990099868748898431416127733239333299438252990718588947189627323862541320759723075359298002049945454633364655148048199507211108165727687436312872406544839729575529520270271212122028280365380192629059572326697528192650854391087074787830145645541039617319693261751740962406625982611599743519772133569772510859136968203669002607093387421841449330961737401917372593

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=07347433127281486906860280355400822537508250345757256177242517342560764165554637128539144116794110030832094986094583688632932700998987118958338928919249599364997963078522041519231369056179001463283222749566596057227903687207418161982124225449909496145850555407019365357401346326522901293338310054580376642926396802107232503603945661310889923695098781539665004

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= 0638826796452127133060851735150951071430275056123130294086692593854251533885996256027311975652580597327242054997242527919041738118652229949698800962172399502731603526218563378085587136121874198025540968920749108964742030494235298986856087470764881654124936705626178295448354161462318481557194240255986478224075382581281653576272394078618884158963166707921691394

Felix

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

verschlüsselte Nachricht= 1254544438086010397039061204298908079469205254524408687415689490059644530176722544430609264427178867395880255290343010043170390550685863497367714259899864183969585589056046525268324777327724591133401505755558766387342663931343173392696426001503783209452694269672576570768116204758581902298588500582871562821858936797178310397471364620497070913599210773880753162

Henri

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

verschlüsselte Nachricht= 0596546690750658828607070611178809956366121804004279718876202636034210127942829660022519576682411439910466288373911779018002618054809875877091124917720812070581455064361240424230263415276359358186232337822525426996042025224138279768405074675916302238335881301164741021868865349590280530865145406841665284487562865929115572380250625032511891843505584254436656882

N=1392591820228166155816688383886133939396497247225108937050742695863681846726864582644556591198341546200327317385519027717624983738017741013544440271594873087849099030320504915829915767387889361239137047141799130032511190188205166488858575753568542478783222560186344650236124822535703612524702239712828397167120792274198582504828575161412533920388062991850528297 e=2^16+1

RSA-Factoring-Challenge

RSA-Verfahren ist mit "kleinen Primzahlen" immer noch leicht zu knacken! (Primfaktorzerlegung des N-Moduls)
der Rechenaufwand ist bei großen Primzahlen (ab 500 Bit) zu groß
Schlüssel, die mit über 1000 Bit erzeugt wurden, sind bislang nicht geknackt worden
eine Primzahl mit 500 Bit liegt im Bereich 2^500

RSA