Kryptographie Theorie und Praxis von RSA

Internet Internet Sicherheit
#1

Es ist kein Problem im Netz Infos zur mathematischen Grundlage von RSA (Primzahlen usw.) zu finden. Auch Anleitungen zu Krptoprogrammen sind sind tausenfach Vorhanden.

Keine Infos finde ich zu Verknüpfung von der Theorie zur Praxis.

Aus Spass und zum Verständnis der Kryptographie habe ich mir ein Modul zur Erzeugung von Primzahlen und Erstellung der Werte für RSA entwickelt.

Leider kann ich meine eigenen Werte nicht mit einem Krypto-Programm testen, da diese in einem mir nicht verständlichen Format vorliegen.

Wer kann mir mit Infos oder Links auf deuschsprachige Seiten weiterhelfen?

Ich möchte kein Verschlüsselungsprogramm schreiben und dann sagen meines ist Sicher. Ich möchte nur RSA, PGP usw. verstehen, am besten duch eigenes herumspielen und herumprogrammieren.

Danke

#2

Hi hpr,

Aus Spass und zum Verständnis der Kryptographie habe ich mir
ein Modul zur Erzeugung von Primzahlen und Erstellung der
Werte für RSA entwickelt.

Leider kann ich meine eigenen Werte nicht mit einem
Krypto-Programm testen

Was du hier versucht ist eine Zufallsvorhersage, wenn diese klappen würde, würde kein Mensch RSA verwenden.

Zur Erklärung: n = p * q, wobei hier p und q „Zufallszahlen“ sind, welche auch gleichzeitig Primzahlen sind und normalerweise in einem Bereich von 2^500 - 2^4000 liegen. n ist zwar öffentlich bekannt, genauso wie der PK, aber in dem Bereich nahezu unwahrscheinlich dieses mittels ggt, Faktorisierung und modulo zurückzurechenen, wenn du wissen möchtest ob dein Algorithmus funktioniert. Musst du p und q so wählen das es knackbar ist, also p=13 und q=17 z.B. dann ist n=221 -> PHI(n) = 192 mit dem zufälligen PK ergibt sich SK*PK mod 192 = 1 (geheimer Signaturschlüssel), da n und PK bekannt sind, kann man diesen jetzt zurück berechnen.

Wer kann mir mit Infos oder Links auf deuschsprachige Seiten
weiterhelfen?

Ich kann dir nur mit Stichwörtern dienen:

  • Fermatsche Satz
  • Euklid-Algorithmus
  • Modulare Inversion
  • Berlekamp

Das Kryptoverfahren gilt als gebrochen wenn man SK = PK^-1 mod PHI(n) berechnen kann, das ist, momentan zumindest bei p,q von 2^4000, unmöglich. Von daher kann dein Vergleich mit einem Kryptoprogramm ja auch nicht funktionieren.

Gruß XXD

#3

Hi XXD,

wahrscheinlich hast Du meine Frage falsch interprtiert.

Ich kann meinen privaten und meinen öffentlichen Schlüssel berechnen. Diese beiden Schlüssel liegen aber in Form von Zahlen vor. Bei einem Schlüsselaustausch der öffentlichen Schlüssel werden aber normalerweise keine Zahlen übermittelt sondern ein für mich unverständlicher Kauderwelsch.

Wie übersetzte ich meinen Schlüssel in diesen Kauderwelsch, damit ich den Rest der Verschlüsselungstechnik auch noch verstehe.

Gruß hpr

#4

owt

#5

Du hast nicht verstanden, worum es dem Fragesteller geht.

Gruß,
Steve

#6

Hallo,

das einzige was mir dazu einfällt ist ein Teil aus folgendem Talk:
https://www.youtube.com/watch?v=IuSnY_O8DqQ#t=2857

Dort wird der Aufbau von RSA Private Key Dateien erklärt. Wenn du diese bauen kannst, kannst du auch damit auch die Public Key Datei erstellen. Vielleicht bringt dich das ja einen Schritt weiter. Falls nicht, ist es wenigstens ein spannender Talk :smiley:

Gruß,
Steve

#7

Wenn du deine Theorie mal wirklich auf den Schichten erklären würdest ,
zwei schlüssel zu haben ist keine kommunikations erklärung , sondern quasi nur die passwörter

hier ist z.b. der erste handshake
http://de.wikipedia.org/wiki/Diffie-Hellman-Schl%C3%…

es geht schon um das verfahren was angewendet wird .

Die Bekannten schlüssel werden eigentlich genommen um diesen schlüssel zu haben mit dem dann alles verschlüsselt wurde .

#8

Hier meine Frage mit Zahlenbeispiel

mein Programm berechnet folgendes:

Primzahl p:
314552150211643500821991640875384767327

Primzahl q:
235391493545946132683395455120169459327

Primzahl e:
192162118102686330057992387759208392339

RSA-Modul N:
74042900436407559577528600068795822565925896480978016086812839257777285008929

phi(N):    
74042900436407559577528600068795822565375952837220426453307452161781730782276

d:
51984345975281283259384594625466351948776792931228939976380440034296551333979

Nun möchte ich meinen Public-Schlüssel weitergeben, damit mir jemand eine verschlüsslte E-Mail mit OpenPGP senden kann.

Wie muß ich meinen öffentlichen Schlüssel aufbereiten, daß OpenPGP ihn verwenden kann.

Gruß und Dank
hpr

#9

Hi hpr,

d:
519843459752812832593845946254663519487767929312289399763804400
34296551333979

d ist dein SK vermute ich mal, diesen musst du in ein octet-String verwandeln, dabei sind aber bestimme Sachen zu beachten (also kein oct(d)). Für jeden Standard/Protokoll gibt es ein RFC. In deinem Fall heisst das RFC3447, dort steht alles bis ins letzte Detail genaustens beschrieben…dein Problem/Lösung kommt gleich am Anfang (K 4.1).

http://tools.ietf.org/html/rfc3447#page-10

Viel Spass und Erfolg.

Gruß XXD

#10

praktisch werden zahlen zum rechnen genommen ,
wie zahl zu zeichen steht ist was anderes .

Ich hab mal das RSAin Excel den Formeln entsprechend nachgebaut :

Deins
3,14552E+38 p
2,35391E+38 q
7,40429E+76 RAS Modul N

1,92E+38 e teilerfremd
7,40429E+76 phi N
5,19843E+76 d

Meins :
11 p
13 q
143 RAS N
3 teilerfremd
7 d (den wert hab ich ausprobiert , wie der berechnet wird ist mir gerade unklar )

KlarZahl m = 13

c = ( m hoch e ) mod 143
Verschlüsselfaktor 2197 (siehe formel auf RSA seite)

Shiffre c = 52

m = ( c hoch d ) mod 143
Entschlüsselfaktor 1,02807E+12 (siehe formel auf RSA seite)

Klarzahl m = 13

#11

Hallo TechPech,

praktisch werden zahlen zum rechnen genommen ,
wie zahl zu zeichen steht ist was anderes .

Ich hab mal das RSAin Excel den Formeln entsprechend
nachgebaut :

Deins
3,14552E+38 p
2,35391E+38 q
7,40429E+76 RAS Modul N

1,92E+38 e teilerfremd
7,40429E+76 phi N
5,19843E+76 d

Meins :
11 p
13 q
143 RAS N
3 teilerfremd
7 d (den wert hab ich ausprobiert , wie der berechnet wird
ist mir gerade unklar )

Soweit den User verstanden, möchte er (noch) nicht verschlüsseln, sondern das sein Schlüssel auf den Keyservern angenommen wird. Anhand der Zahlen ist „e“ bei ihm der offentl. Schlüssel, welchen er in ein octet-string verwandeln muss, um ihn auf einen Keyserver zu laden, ebenfalls muss „d“ = der geheime Signaturschlüssel ein octet-string sein.

Um einen privaten Schlüssel zu erzeugen gilt: SK*PK mod PHI(n) = 1 d.h SK *PK = z * PHI(n)+1 dieses kann man lösen indem man die Inverse von PK sucht (ggt(a,b) und schrittweise rückwärts einsetzt).

Bitte korrigieren, wenn ich mich irre (hatte das Thema nur am Rande)

Gruß XXD

#12

doch,er will die Verschlüsselung „knacken“ lol

#13

Nein, eben genau das nicht. m(

#14

Hi XXD,

ich glaube Du hast mich verstanden und mir die passenden Stelle in der RFC3447 gezeigt. Mit meinen Englischkenntnissen hätte ich das nicht gefunden.

Vielen Dank an Dich und auch allen anderen, die sich meinem Problem angenommen haben.

Gruß
hpr