RSA

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.

Hausaufgabe

RSA-Faktoring-Chalenge (Wikipedia) lesen

• Warum ist das RSA-Verfahren mit kleinen Primzahlen immer noch unsicher? (Wozu benötigt man möglichst große Primzahlen?)
• Was bedeutet 205 Bit?
• Wie groß sollten zwei sichere Primzahlen sein?

Wir verschlüsseln uns Nachrichten gegenseitig

Tim

N = 2951496213141662331323665053128112557378911707093713492954789957537231681683032654203439442684989259303550465631213589388871323904730918478024673146050974374184029991675195149432744206146108231886549386552991581064377450979852881966895979134531826358941364454722375485044829485265639664011582319334250043031090676544576122883714970235494357318190231720540246670794151681100977732757063290446580710379323044482215917092131909505882464099680214817217724378706043017975599248131170828138859232153415378355650370118143644321361592959242030885583046225895822976010539797767795394679615254227265607237235751274593784154359271251377725420277154394575958222944682111911211201371796566162188091071630490817110562029081042512031938343752630633952255937686764881299400473306362144718149647792841490514356878964237845723962222797432389858238988839172814221863479717960538033372044532184979436259862897653773907177479210498264909262465138168256151148061508449980215896368187781716992848221547972841419916470928479327781180557556631138303960489900944303699112595506096217465711547212154899627239692182547617840348139493302730431981881993263227630518100429366221858075213461994946334604694591132001941108521807543438026992971556601021266606190130121

e = 2^16+1

1) 2392224459871828915041138653819651437883711117792746758435005777272266397058246475673863870825613037122370514985984850879580657341245535983044748962732061971626459001311509916793375588005942125612142491747166631193332625308962621091512919440369176875007257512259029772123241973196954843995515743022079706710836362583655996107071911693671690264018948558388283547128640307015898701406790573361674406417677694137770605087789495250969339181374515753572992636383697509758764128523662432717187661112758685767579196230179057950548475041049914997943500538070501135550083570549833335271348135092591604605014624443930362166649030644084001790883987250606544454665515352128931512894790097008893681235672615013777328451363321217989622627323078677190722630772137922383768352750497521330258532075112458202544679792806946363268675306442989696234826522453019031913976364163918591333051682822797405733502002730935320241431482376183306138641589791812556281769064168422916563729737834198908102704696609689563703004994786598605713733005751451481125549258944351248454691105501478044154640548687041685999060635154184586331686525908193395696379100946075013575606676736766251275120428369883210633953178163442995699774758912199228245198164130741358610943832684

Elise

N 2923723657325689753 e 2^16+1 Text 0322250827748490414 # 2472611229660409538

Aaron

N = 342956342295936292393891065641893848736794637392384905846248337168707372110193242555224205908083853003936877171398504438871986838061794089548556100318210498605169358697424178879588021755612930564718472506596932823230019829866898431511462092089434738834527839804259638587300757080878235961034877974398932419717896844890407447523692489085985424359033716736427251766485939060462261977410038006304484567526310806073451518012344047187124975235095714852025089810499097090019126147158689387795694419416576325671900858438121477483191429974749171009612676629191146199083808915894262866730712099283829536472869745453743653167884015024512206141635707412928017716264949359671943789198041161042941651281295446900810333075345070608798890527450157990047573623084580225697893846731057482172911313132340399681162714965981849334320087057013071241614799747150834558042270003477076231395504907830736251029928211875938700992659340699686674266703250431331739179054250196877807829441300900162682165577845533899425139

e = 2^16+1

Johannes

N=11760947285600722187007680388822169352914722465775663150025873219726620452322667698132003203338515849237082308349304176952629313528265414313128730488183827530712411157595645803419296408218651422365099661623318457186024029604386968344431558489090063989728309774779347231327615016603461436632461151863962301612360958863821815340312889410091326699571030352854508094555162079295364678646685290162820082795753995603758063927961372710021863900935035938896780135413270023549296782562739748213230240956398866639350995797975668163553986829881512698431661191328176839894359841733166089569856937344296203654146921847600353676479

e= 2^16+1

Dandy

N = 1688180727500347741

e = 65537

Schlüssel für Josef: 1234120474465912099 # 1230353083399707634 # 0462960430889572536 # 1668559233401989181 # 0558528854443029121 # 0061871616029764787 # 1433346339072452767 # 0197958887340782944

NEUES N: 70313059467932863650169950936591565248388630662268540577171426278710028722595972264074667753231715421602362044623199540558837571477071006385223272585194864727758823723363967365015529293171819326248730074249401342569750344511699494229111082865475344604279641227176985435756309410186029080389810872928399150596276996577278698614619434466713766369267319034270346313522879773243476720004777695933246705455221495249461522498937603515923818161571063793269519622612555578346508550406497713662914147387067822963264081898155885513293859099084743803993977664963035440168382471722577533736377750321721078751825224181296308321319

Josef

N = 70313059467932863650169950936591565248388630662268540577171426278710028722595972264074667753231715421602362044623199540558837571477071006385223272585194864727758823723363967365015529293171819326248730074249401342569750344511699494229111082865475344604279641227176985435756309410186029080389810872928399150596276996577278698614619434466713766369267319034270346313522879773243476720004777695933246705455221495249461522498937603515923818161571063793269519622612555578346508550406497713662914147387067822963264081898155885513293859099084743803993977664963035440168382471722577533736377750321721078751825224181296308321319

e = 2^16+1 bzw. (65537)

Theresa

N=2189329218283721051 e=2^16+1

1 neue Nachricht von Heidi:0960431449687320593 # 1321373400322207727 # 0782940085349524221 # 0386420003740380966 # 0537310695899918429 # 0873795174461400411 # 1767094842803462446 # 0107150302338772149 # 0332336724158767107 # 1819778149649941543 # 0684844835086246406 # 1646236126423120900 # 2118456125486013924 # 2023364804533987443 # 0975267753970930938

Heidi

e: 2^16+1

N: 2923723657325689753

verschlüsselte Nachricht:

1136011545364292294 # 1061740183986791317 # 2111626553460064403 # 2368350865761515465 # 1105560748490278701 # 0232785873229391537 # 2094094700269354771 # 0426665001269638855