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

Cornelius

öffentlicher Schlüssel: N= 564770296095460534949

e= 65537 Text: 462205500095285750340 # 165234946189324884447

Sebastian

öffentlicher Schlüssel: N=564770296095460534949

e=2^16+1

M=534480725422052135176 # 093865893319636082765

Camilo

öffentlicher Schlüssel: N=6006895620581

e=2^16+1

429130418445698861083 # 521533381957458069104 # 611474369754604863790 # 345493507966049739474 # 056427154841869189966

David

öffentlicher Schlüssel: N= 23504900843136602761

e= 2^16+1

00965313686794480073 # 10795120661862956265 # 21489959575424599855 # 00735713607825357160

Thomas

öffentlicher Schlüssel: N=631585797098725402477

e=2^16+1

312617020153885547842 # 252609973320106634334 # 518825790258795106525

Immanuel

öffentlicher Schlüssel: N=

e=

Rouven

öffentlicher Schlüssel: N= 201833165096462546629

e= 2^16+1

Kilian

öffentlicher Schlüssel: N=46513

e=2^16+1

Elisa

öffentlicher Schlüssel: N=11037668287

e=2^16+1

Nachricht 1: 1040696772 # 1954658552 # 9226326299 # 2169845388 # 6789874577 # 8096599615 # 4057777565 # 3151654456 # 4977293038 # 7047938737 # 9617485204 # 3437434927 # 7686064856 # 6396480873

Nachricht 2: 3872097748 # 3611644946

Kai

öffentlicher Schlüssel: N=

e=