RSA
Inhaltsverzeichnis |
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?
RSA mit dem Android-Handy ansehen und versuchen, umzusetzen.
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
Janis
Öffentlicher Schlüssel: 2^16+1
Serena
Pauline
Martin
Fabian
Ruben
Stefan
Robine
N= 2974166196448522949 e= 2^16+1
Theresa
Ludwig
Kevin
Milena
Oliver
Öffentlicher schlüssel: N:233555458668544594979400202582823969778199979323 e:2^16+1
Josephine
Felix
Deborah
N=3454354140502097533 e=2^16+1
Nico
Josua
Saskia
N= 1837625933157484369 e= 2^16+1
Johanna
Tobias
Ella
N=2240339100055897937 e=2^16+1