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

e = 2^16+1

Aaron: 6109241775432 # 0445619957989 # 2011493422895 # 1753212313778 # 1560560402734 # 4668526465824

Für Tim: 0971158489226418555 # 2043547178206792772 # 0732029136643858939 # 1556005650193041109 # 0377185071036805876 # 1239559758108528165 # 2632998321014479199 # 0615496542965952553 # 1271428267648145280

Elise

Aaron

N = 8657171789267

e = 2^16+1

Tim: 2403605539189261130 # 1416580827313331326 # 2408159993458149277 # 2190278437483377366 # 1562642152801134763 # 1560000634633346060 # 2423329647570075338

Johannes

N= 2185487837714976281

Dandy

Josef

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

Theresa

N=2189329218283721051 e=2^16+1

Heidi

e: 2^16+1

N: 2923723657325689753