RFC 3526 Diffie-Hellman P und G generieren

lima-city → Forum → Programmiersprachen → Programmieren mit .NET & Mono

Autor dieses Themas
computerkurs2011

computerkurs2011 hat kostenlosen Webspace.

20:48, 10.5.2016
Hallo liebes Lima-Forum,

ich möchte bzw. muss für ein C# Programm einen Diffie-Hellman Schlüsselaustausch realisieren. Dafür ist es zwingend notwendig, dass ich elementare Bestandteile wie die Primzahl P und den Generator G jederzeit abrufen kann, da der C#-Client mit einem PHP Script kommuniziert und dies ebenfalls die öffentlichen Parameter P und G benötigt.

Nun habe ich folgendes Problem. C# stellt kein Framework, zumindest nicht nach meiner Recherche, zur Verfügung um einen Diffie-Hellman Schlüsselaustausch "einfach" zu realisieren. Ich müsste die Primzahl P und den Generator G selber generieren. Allerdings weiß ich a.) nicht wie ich G generieren soll in einem Programm mit riesigen Primzahlen (min. 300 Dezimalstellen) und b.) bin ich auf ein RFC gestoßen.

Und dazu habe ich jetzt ein paar Fragen:
1. Das RFC 3526 (http://www.rfc-base.org/txt/rfc-3526.txt) gibt DH Gruppen an. Wozu genau kann ich diese verwenden? - Sind das dort fertige, sichere Primzahlen mit dem dazu gehörigen Generator?
1.1. Wenn dem so ist. Beeinträchtigt dies nicht die Sicherheit, wenn ich immer dieselbe Primzahl und denselben Generator verwende?
1.2. Wie kann ich diese Primzahl, wenn es eine ist, aus dem Hex nutzbar für Modulo Rechnungen in C# machen?
2. Wenn das RFC etwas ganz anderes angibt, was gibt es an?
3. Wenn das RFC etwas ganz anderes angibt, wie könnte ich dann ein Generator G zu einer Zufälligen Primzahl P erzeugen bzw. finden und das in einer für den Nutzer ertragbaren Zeit?

Im groben habe ich das Diffie-Hellman Verfahren verstand, abgesehen davon, wie ich den Generator G bekomme.

Hauptsächlich habe ich mich zuvor immer mit RSA beschäftigt. Es ist nun allerdings wichtig, dass ich wie oben erwähnt an das G und P immer herankomme, also wenn ein fertiges Framework mir keinen Zugriff auf P oder G gewähren würde, dann könnte ich es für meine Zwecke nicht gebrauchen.

Für alle die jetzt sagen, dass ich auch einfach HTTPS zur Kommunikation mit PHP verwenden kann... Richtig, aber ich muss darüber eine Präsentation halten und da wäre HTTPS kontra Produktiv, da mir dort alle Vorgänge abgenommen werden und ich somit keine eigene Leistung, bzw. Verständnis vorweisen könnte.

MfG
cpk2011
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage
kamakura

kamakura hat kostenlosen Webspace.

8:05, 12.5.2016

computerkurs2011 schrieb:
Hallo liebes Lima-Forum,

ich möchte bzw. muss für ein C# Programm einen Diffie-Hellman Schlüsselaustausch realisieren. Dafür ist es zwingend notwendig, dass ich elementare Bestandteile wie die Primzahl P und den Generator G jederzeit abrufen kann, da der C#-Client mit einem PHP Script kommuniziert und dies ebenfalls die öffentlichen Parameter P und G benötigt.
Entschuldige die Frage, aber machst du das bloß zur Übung oder willst du deinen Code ernsthaft benutzen?
Nun habe ich folgendes Problem. C# stellt kein Framework, zumindest nicht nach meiner Recherche, zur Verfügung um einen Diffie-Hellman Schlüsselaustausch "einfach" zu realisieren. Ich müsste die Primzahl P und den Generator G selber generieren. Allerdings weiß ich a.) nicht wie ich G generieren soll in einem Programm mit riesigen Primzahlen (min. 300 Dezimalstellen)
Also du suchst eine Primitivwurzel zu P?

Wie effizient soll das sein?

Die simpelste Art, die du sicher leicht selber programmieren kannst, wäre:
1. Wähle eine zufällige Zahl z zwischen 2 und P-1
2. Berechne die Primfaktorzerlegung von P-1
3. Angenommen die Primfaktorzerlegung von P-1 ist

$Formel: P-1 = p_1^{e_1} \cdots p_n^{e_n}$

dann berechnet für alle $Formel: p_1, \ldots, p_n$ :

$Formel: z^{\frac{P-1}{p_i}} \bmod P$

Falls dies niemals 1 ist, dann ist z eine Primitivwurzel (und damit ein Generator).

Allerdings dauert diese Vorgehensweise bei einer 3000+ Bit Primzahl zu lang. Das Problem ist die Faktorisierung von P-1.
und b.) bin ich auf ein RFC gestoßen.

Und dazu habe ich jetzt ein paar Fragen:
1. Das RFC 3526 (http://www.rfc-base.org/txt/rfc-3526.txt) gibt DH Gruppen an. Wozu genau kann ich diese verwenden? - Sind das dort fertige, sichere Primzahlen mit dem dazu gehörigen Generator?
Zumindest steht genau das in der Beschreibung.

1.1. Wenn dem so ist. Beeinträchtigt dies nicht die Sicherheit, wenn ich immer dieselbe Primzahl und denselben Generator verwende?
https://de.wikipedia.org/wiki/Diffie-Hellman-Schlüsselaustausch#Verwendung_fester_Gruppen_und_Primzahlen
1.2. Wie kann ich diese Primzahl, wenn es eine ist, aus dem Hex nutzbar für Modulo Rechnungen in C# machen?
Verstehe die Frage nicht. Du kannst doch einfach die Zahl vom Hexadezimal- ins Dezimalsystem konvertieren, oder nicht?

Natürlich brauchst du auch noch eine BigInteger-Klasse.
2. Wenn das RFC etwas ganz anderes angibt, was gibt es an?
3. Wenn das RFC etwas ganz anderes angibt, wie könnte ich dann ein Generator G zu einer Zufälligen Primzahl P erzeugen bzw. finden und das in einer für den Nutzer ertragbaren Zeit?^
Komplizierte Fragen...

Du siehst, ich habe von dem Thema auch kaum Ahnung, aber wollte dir das wenige, was ich weiß, wenigstens mitteilen.

Autor dieses Themas

computerkurs2011

computerkurs2011 hat kostenlosen Webspace.

19:23, 12.5.2016

Hallo kamakura,

ich habe mich jetzt für die feste Primzahl aus dem RFC entschieden. Ich habe einfach die 4096-bit Primzahl genommen, denn wenn 1024-bit schon eher für die NSA machbar sind, dann wird eine 4096-bit Primzahl wohl eher für einfache Hacker und nicht staatliche Institutionen nicht knack bar sein in einer realistischen Zeit.

kamakura schrieb:
Verstehe die Frage nicht. Du kannst doch einfach die Zahl vom Hexadezimal- ins Dezimalsystem konvertieren, oder nicht?

Natürlich brauchst du auch noch eine BigInteger-Klasse.

Visual Studio bietet sogar die Möglichkeit mit einem byte array das mit Hex gefüllt ist zu rechnen

Für alle die so ein byte Array vllt. auch mal für DH brauchen:

byte[] m_MODP4096 = new byte[]
            {
               0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC, 0x90, 0xFD, 0xAA, 0x22, 0x16, 0x8C, 0x23, 0x4C, 0x4C, 0x66, 0x28, 0xB8, 0x0D, 0xC1, 0xCD, 0x12, 0x90, 0x24, 0xE0, 0x88, 0xA6, 0x7C, 0xC7, 0x40, 0x20, 0xBB, 0xEA, 0x63, 0xB1, 0x39, 0xB2, 0x25, 0x14, 0xA0, 0x87, 0x98, 0xE3, 0x40, 0x4D, 0xDE, 0xF9, 0x51, 0x9B, 0x3C, 0xD3, 0xA4, 0x31, 0xB3, 0x02, 0xB0, 0xA6, 0xDF, 0x25, 0xF1, 0x43, 0x74, 0xFE, 0x13, 0x56, 0xD6, 0xD5, 0x1C, 0x24, 0x5E, 0x48, 0x5B, 0x57, 0x66, 0x25, 0xE7, 0xEC, 0x6F, 0x44, 0xC4, 0x2E, 0x9A, 0x63, 0x7E, 0xD6, 0xB0, 0xBF, 0xF5, 0xCB, 0x6F, 0x40, 0x6B, 0x7E, 0xDE, 0xE3, 0x86, 0xBF, 0xB5, 0xA8, 0x99, 0xFA, 0x5A, 0xE9, 0xF2, 0x41, 0x17, 0xC4, 0xB1, 0xFE, 0x64, 0x92, 0x86, 0x65, 0x1E, 0xCE, 0x45, 0xB3, 0xDC, 0x20, 0x07, 0xCB, 0x8A, 0x16, 0x3B, 0xF0, 0x59, 0x8D, 0xA4, 0x83, 0x61, 0xC5, 0x5D, 0x39, 0xA6, 0x91, 0x63, 0xFA, 0x8F, 0xD2, 0x4C, 0xF5, 0xF8, 0x36, 0x55, 0xD2, 0x3D, 0xCA, 0x3A, 0xD9, 0x61, 0xC6, 0x2F, 0x35, 0x62, 0x08, 0x55, 0x2B, 0xB9, 0xED, 0x52, 0x90, 0x77, 0x09, 0x69, 0x66, 0xD6, 0x70, 0xC3, 0x54, 0xE4, 0xAB, 0xC9, 0x80, 0x4F, 0x17, 0x46, 0xC0, 0x8C, 0xA1, 0x82, 0x17, 0xC3, 0x29, 0x05, 0xE4, 0x62, 0xE3, 0x6C, 0xE3, 0xBE, 0x39, 0xE7, 0x72, 0xC1, 0x80, 0xE8, 0x60, 0x39, 0xB2, 0x78, 0x3A, 0x2E, 0xC0, 0x7A, 0x28, 0xFB, 0x5C, 0x55, 0xDF, 0x06, 0xF4, 0xC5, 0x2C, 0x9D, 0xE2, 0xBC, 0xBF, 0x69, 0x55, 0x81, 0x71, 0x83, 0x99, 0x54, 0x97, 0xCE, 0xA9, 0x56, 0xAE, 0x51, 0x5D, 0x22, 0x61, 0x89, 0x8F, 0xA0, 0x51, 0x01, 0x57, 0x28, 0xE5, 0xA8, 0xAA, 0xAC, 0x42, 0xDA, 0xD3, 0x31, 0x70, 0xD0, 0x45, 0x07, 0xA3, 0x3A, 0x85, 0x52, 0x1A, 0xBD, 0xF1, 0xCB, 0xA6, 0x4E, 0xCF, 0xB8, 0x50, 0x45, 0x8D, 0xBE, 0xF0, 0xA8, 0xAE, 0xA7, 0x15, 0x75, 0xD0, 0x60, 0xC7, 0xDB, 0x39, 0x70, 0xF8, 0x5A, 0x6E, 0x1E, 0x4C, 0x7A, 0xBF, 0x5A, 0xE8, 0xCD, 0xB0, 0x93, 0x3D, 0x71, 0xE8, 0xC9, 0x4E, 0x04, 0xA2, 0x56, 0x19, 0xDC, 0xEE, 0x3D, 0x22, 0x61, 0xAD, 0x2E, 0xE6, 0xBF, 0x12, 0xFF, 0xA0, 0x6D, 0x98, 0xA0, 0x86, 0x4D, 0x87, 0x60, 0x27, 0x33, 0xEC, 0x86, 0xA6, 0x45, 0x21, 0xF2, 0xB1, 0x81, 0x77, 0xB2, 0x00, 0xCB, 0xBE, 0x11, 0x75, 0x77, 0xA6, 0x15, 0xD6, 0xC7, 0x70, 0x98, 0x8C, 0x0B, 0xAD, 0x94, 0x6E, 0x20, 0x8E, 0x24, 0xFA, 0x07, 0x4E, 0x5A, 0xB3, 0x14, 0x3D, 0xB5, 0xBF, 0xCE, 0x0F, 0xD1, 0x08, 0xE4, 0xB8, 0x2D, 0x12, 0x0A, 0x92, 0x10, 0x80, 0x11, 0xA7, 0x23, 0xC1, 0x2A, 0x78, 0x7E, 0x6D, 0x78, 0x87, 0x19, 0xA1, 0x0B, 0xDB, 0xA5, 0xB2, 0x69, 0x9C, 0x32, 0x71, 0x86, 0xAF, 0x4E, 0x23, 0xC1, 0xA9, 0x46, 0x83, 0x4B, 0x61, 0x50, 0xBD, 0xA2, 0x58, 0x3E, 0x9C, 0xA2, 0xAD, 0x44, 0xCE, 0x8D, 0xBB, 0xBC, 0x2D, 0xB0, 0x4D, 0xE8, 0xEF, 0x92, 0xE8, 0xEF, 0xC1, 0x41, 0xFB, 0xEC, 0xAA, 0x62, 0x87, 0xC5, 0x94, 0x74, 0xE6, 0xBC, 0x05, 0xD9, 0x9B, 0x29, 0x64, 0xFA, 0x09, 0x0C, 0x3A, 0x22, 0x33, 0xBA, 0x18, 0x65, 0x15, 0xBE, 0x7E, 0xD1, 0xF6, 0x12, 0x97, 0x0C, 0xEE, 0x2D, 0x7A, 0xFB, 0x81, 0xBD, 0xD7, 0x62, 0x17, 0x04, 0x81, 0xCD, 0x00, 0x69, 0x12, 0x7D, 0x5B, 0x05, 0xAA, 0x99, 0x3B, 0x4E, 0xA9, 0x88, 0xD8, 0xFD, 0xDC, 0x18, 0x6F, 0xFB, 0x7D, 0xC9, 0x0A, 0x6C, 0x08, 0xF4, 0xDF, 0x43, 0x5C, 0x93, 0x40, 0x63, 0x19, 0x9F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF

            };

Allerdings geben manche Primzahlen Tests aus, dass dies keine Primzahl wäre, vermutlich, weil es eine mit negativen Vorzeichen ist. Allerdings gibt der Miller-Rabin Primzahltest ein positives Ergebnis aus, weshalb ich hier mal von einer richtigen Implementierung ausgehe.

Mit PHP Funktioniert die mit dem phpseclib BigInteger auch sehr gut.

Allerdings dauert das Finden einer Zufallszahl, also keine Primzahl, sondern die Zahl a zwischen 2 und P-1, immer um die 40-50 Sekunden, hat jemand ein Tipp wie man dies verkürzen könnte?

Ansonsten klappt alles wunderbar. Hoffentlich hilft der Beitrag auch noch ein paar anderen Leuten.

kamakura schrieb:
Entschuldige die Frage, aber machst du das bloß zur Übung oder willst du deinen Code ernsthaft benutzen?

Das Programm Dient als Präsentationsleistung für mein Abitur.
Trotzdem sollte es einigermaßen brauchbar implementiert sein und auch funktionieren.

MfG
cpk2011

kamakura

kamakura hat kostenlosen Webspace.

9:30, 13.5.2016

computerkurs2011 schrieb:
Hallo kamakura,

ich habe mich jetzt für die feste Primzahl aus dem RFC entschieden. Ich habe einfach die 4096-bit Primzahl genommen, denn wenn 1024-bit schon eher für die NSA machbar sind, dann wird eine 4096-bit Primzahl wohl eher für einfache Hacker und nicht staatliche Institutionen nicht knack bar sein in einer realistischen Zeit.

Willst du mir sagen: "Umso mehr Bit umso sicherer" ?

kamakura schrieb:
Verstehe die Frage nicht. Du kannst doch einfach die Zahl vom Hexadezimal- ins Dezimalsystem konvertieren, oder nicht?

Natürlich brauchst du auch noch eine BigInteger-Klasse.

Visual Studio bietet sogar die Möglichkeit mit einem byte array das mit Hex gefüllt ist zu rechnen

Für alle die so ein byte Array vllt. auch mal für DH brauchen:

byte[] m_MODP4096 = new byte[]
            {
               0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC, 0x90, 0xFD, 0xAA, 0x22, 0x16, 0x8C, 0x23, 0x4C, 0x4C, 0x66, 0x28, 0xB8, 0x0D, 0xC1, 0xCD, 0x12, 0x90, 0x24, 0xE0, 0x88, 0xA6, 0x7C, 0xC7, 0x40, 0x20, 0xBB, 0xEA, 0x63, 0xB1, 0x39, 0xB2, 0x25, 0x14, 0xA0, 0x87, 0x98, 0xE3, 0x40, 0x4D, 0xDE, 0xF9, 0x51, 0x9B, 0x3C, 0xD3, 0xA4, 0x31, 0xB3, 0x02, 0xB0, 0xA6, 0xDF, 0x25, 0xF1, 0x43, 0x74, 0xFE, 0x13, 0x56, 0xD6, 0xD5, 0x1C, 0x24, 0x5E, 0x48, 0x5B, 0x57, 0x66, 0x25, 0xE7, 0xEC, 0x6F, 0x44, 0xC4, 0x2E, 0x9A, 0x63, 0x7E, 0xD6, 0xB0, 0xBF, 0xF5, 0xCB, 0x6F, 0x40, 0x6B, 0x7E, 0xDE, 0xE3, 0x86, 0xBF, 0xB5, 0xA8, 0x99, 0xFA, 0x5A, 0xE9, 0xF2, 0x41, 0x17, 0xC4, 0xB1, 0xFE, 0x64, 0x92, 0x86, 0x65, 0x1E, 0xCE, 0x45, 0xB3, 0xDC, 0x20, 0x07, 0xCB, 0x8A, 0x16, 0x3B, 0xF0, 0x59, 0x8D, 0xA4, 0x83, 0x61, 0xC5, 0x5D, 0x39, 0xA6, 0x91, 0x63, 0xFA, 0x8F, 0xD2, 0x4C, 0xF5, 0xF8, 0x36, 0x55, 0xD2, 0x3D, 0xCA, 0x3A, 0xD9, 0x61, 0xC6, 0x2F, 0x35, 0x62, 0x08, 0x55, 0x2B, 0xB9, 0xED, 0x52, 0x90, 0x77, 0x09, 0x69, 0x66, 0xD6, 0x70, 0xC3, 0x54, 0xE4, 0xAB, 0xC9, 0x80, 0x4F, 0x17, 0x46, 0xC0, 0x8C, 0xA1, 0x82, 0x17, 0xC3, 0x29, 0x05, 0xE4, 0x62, 0xE3, 0x6C, 0xE3, 0xBE, 0x39, 0xE7, 0x72, 0xC1, 0x80, 0xE8, 0x60, 0x39, 0xB2, 0x78, 0x3A, 0x2E, 0xC0, 0x7A, 0x28, 0xFB, 0x5C, 0x55, 0xDF, 0x06, 0xF4, 0xC5, 0x2C, 0x9D, 0xE2, 0xBC, 0xBF, 0x69, 0x55, 0x81, 0x71, 0x83, 0x99, 0x54, 0x97, 0xCE, 0xA9, 0x56, 0xAE, 0x51, 0x5D, 0x22, 0x61, 0x89, 0x8F, 0xA0, 0x51, 0x01, 0x57, 0x28, 0xE5, 0xA8, 0xAA, 0xAC, 0x42, 0xDA, 0xD3, 0x31, 0x70, 0xD0, 0x45, 0x07, 0xA3, 0x3A, 0x85, 0x52, 0x1A, 0xBD, 0xF1, 0xCB, 0xA6, 0x4E, 0xCF, 0xB8, 0x50, 0x45, 0x8D, 0xBE, 0xF0, 0xA8, 0xAE, 0xA7, 0x15, 0x75, 0xD0, 0x60, 0xC7, 0xDB, 0x39, 0x70, 0xF8, 0x5A, 0x6E, 0x1E, 0x4C, 0x7A, 0xBF, 0x5A, 0xE8, 0xCD, 0xB0, 0x93, 0x3D, 0x71, 0xE8, 0xC9, 0x4E, 0x04, 0xA2, 0x56, 0x19, 0xDC, 0xEE, 0x3D, 0x22, 0x61, 0xAD, 0x2E, 0xE6, 0xBF, 0x12, 0xFF, 0xA0, 0x6D, 0x98, 0xA0, 0x86, 0x4D, 0x87, 0x60, 0x27, 0x33, 0xEC, 0x86, 0xA6, 0x45, 0x21, 0xF2, 0xB1, 0x81, 0x77, 0xB2, 0x00, 0xCB, 0xBE, 0x11, 0x75, 0x77, 0xA6, 0x15, 0xD6, 0xC7, 0x70, 0x98, 0x8C, 0x0B, 0xAD, 0x94, 0x6E, 0x20, 0x8E, 0x24, 0xFA, 0x07, 0x4E, 0x5A, 0xB3, 0x14, 0x3D, 0xB5, 0xBF, 0xCE, 0x0F, 0xD1, 0x08, 0xE4, 0xB8, 0x2D, 0x12, 0x0A, 0x92, 0x10, 0x80, 0x11, 0xA7, 0x23, 0xC1, 0x2A, 0x78, 0x7E, 0x6D, 0x78, 0x87, 0x19, 0xA1, 0x0B, 0xDB, 0xA5, 0xB2, 0x69, 0x9C, 0x32, 0x71, 0x86, 0xAF, 0x4E, 0x23, 0xC1, 0xA9, 0x46, 0x83, 0x4B, 0x61, 0x50, 0xBD, 0xA2, 0x58, 0x3E, 0x9C, 0xA2, 0xAD, 0x44, 0xCE, 0x8D, 0xBB, 0xBC, 0x2D, 0xB0, 0x4D, 0xE8, 0xEF, 0x92, 0xE8, 0xEF, 0xC1, 0x41, 0xFB, 0xEC, 0xAA, 0x62, 0x87, 0xC5, 0x94, 0x74, 0xE6, 0xBC, 0x05, 0xD9, 0x9B, 0x29, 0x64, 0xFA, 0x09, 0x0C, 0x3A, 0x22, 0x33, 0xBA, 0x18, 0x65, 0x15, 0xBE, 0x7E, 0xD1, 0xF6, 0x12, 0x97, 0x0C, 0xEE, 0x2D, 0x7A, 0xFB, 0x81, 0xBD, 0xD7, 0x62, 0x17, 0x04, 0x81, 0xCD, 0x00, 0x69, 0x12, 0x7D, 0x5B, 0x05, 0xAA, 0x99, 0x3B, 0x4E, 0xA9, 0x88, 0xD8, 0xFD, 0xDC, 0x18, 0x6F, 0xFB, 0x7D, 0xC9, 0x0A, 0x6C, 0x08, 0xF4, 0xDF, 0x43, 0x5C, 0x93, 0x40, 0x63, 0x19, 0x9F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF

            };

Dann machst du was falsch. Warum ist die Zahl denn bei dir negativ? Das darf nicht sein! Irgendwas ist da schief gelaufen und du hast eine andere Zahl gekriegt, die keine Primzahl ist.
Dass der Miller-Rabin-Primzahltest sagt, deine Zahl wäre eine Primzahl, liegt möglicherweise daran, dass er ein probabilistischer Primzahltest ist. Wenn du den mit wenigen Iterationen durchführst, dann kann er eine Zahl, die keine Primzahl ist, schon mal fälschlicherweise als Primzahl ansehen.

Die 4096-Bit-Primzahl ist in Dezimal ausgedrückt:

104438888141315250667960271984652954583126906099213500902258875644433817\
202232269071044404666980978393011158573789036269186012707927049545451721\
867301692842745914600186688577976298222932119236830334623520436805101030\
915567415569746034717694639407653515728499489528482163370092181171673897\
245183497945589701030633346859075135836513878225037226911796898519432244\
453568741552200715163863814145617842062127782267499502799027867345862954\
439173691976629900551150544617766815444623488266596168079657690319911608\
934763494718777890652800800475669257166692296412256617458277670733245237\
100127216377684122931832490312574071357414100512456196591388889975346173\
534797001169325631675166067895083002751025580484610558346505544661509044\
430958305077580850929704003968005743534225392656624089819586363158888893\
636412992005930845566945403401039147823878418988859467233624276379513817\
635322284552464404009425896243361335403610464388192523848922401019419308\
891166616558422942466816544168892779046060826486420423771700205474433798\
894197466121469968970652154300626260453589099812575227594260877217437610\
731421774923304821790494440983623823577230674987439676046337648021513346\
133347839568274660824258513395388388222678611803018402813675597004538553\
47584532478

Genau das, was durch

2^4096 - 2^4032 - 1 + 2^64 * { [2^3966 pi] + 240904 }

herauskommt (es ist zwar nirgends in dem RFC erklärt, aber ich denke, dass die eckigen Klammern wie üblich Abrundung bedeuten).

Und das ist auch eine Primzahl, ich habe es mit SageMath überprüft.

Allerdings dauert das Finden einer Zufallszahl, also keine Primzahl, sondern die Zahl a zwischen 2 und P-1, immer um die 40-50 Sekunden, hat jemand ein Tipp wie man dies verkürzen könnte?

Du kannst einfach mit der 2 anfangen und testen, ob sie eine Primitivwurzel ist, dann mit der 3, 5, 6, usw.

Was du nicht testen musst, sind Potenzen von Zahlen, die du bereits getestet hast und die keine Primitivwurzeln sind (denn dann sind die Potenzen auch keine Primitivwurzeln).

Autor dieses Themas
computerkurs2011

computerkurs2011 hat kostenlosen Webspace.

13:37, 13.5.2016

kamakura schrieb:

Willst du mir sagen: "Umso mehr Bit umso sicherer" ?

Wenn man Wikipedia glauben schenkt, dann steht dort folgendes:

Wikipedia DHM-Primzahl p:
Die Sicherheit des Verfahrens basiert nicht zuletzt auf der Länge der gewählten Zahlen. So muss die Primzahl p dermassen gewählt werden, dass diskrete Logarithmen modulo p mit derzeit bekannten Methoden nicht (effizient genug) berechnet werden können. Je größer die verwendete Primzahl, desto sicherer das Verfahren, aber auch desto aufwendiger.[40] Das Bundesamt für Sicherheit in der Informationstechnik empfiehlt für p eine Schlüssellänge von mindestens 2.000 Bit (Stand 2016).

Also bedeutet es doch, dass meine 4096-bit Primzahl sicherer ist als wenn ich nur eine 1024-bit benutze. Oder habe ich da grundlegende Verständnisprobleme

kamakura schrieb:
Dann machst du was falsch. Warum ist die Zahl denn bei dir negativ? Das darf nicht sein! Irgendwas ist da schief gelaufen und du hast eine andere Zahl gekriegt, die keine Primzahl ist.
Dass der Miller-Rabin-Primzahltest sagt, deine Zahl wäre eine Primzahl, liegt möglicherweise daran, dass er ein probabilistischer Primzahltest ist. Wenn du den mit wenigen Iterationen durchführst, dann kann er eine Zahl, die keine Primzahl ist, schon mal fälschlicherweise als Primzahl ansehen.

Die 4096-Bit-Primzahl ist in Dezimal ausgedrückt:

104438888141315250667960271984652954583126906099213500902258875644433817\
202232269071044404666980978393011158573789036269186012707927049545451721\
867301692842745914600186688577976298222932119236830334623520436805101030\
915567415569746034717694639407653515728499489528482163370092181171673897\
245183497945589701030633346859075135836513878225037226911796898519432244\
453568741552200715163863814145617842062127782267499502799027867345862954\
439173691976629900551150544617766815444623488266596168079657690319911608\
934763494718777890652800800475669257166692296412256617458277670733245237\
100127216377684122931832490312574071357414100512456196591388889975346173\
534797001169325631675166067895083002751025580484610558346505544661509044\
430958305077580850929704003968005743534225392656624089819586363158888893\
636412992005930845566945403401039147823878418988859467233624276379513817\
635322284552464404009425896243361335403610464388192523848922401019419308\
891166616558422942466816544168892779046060826486420423771700205474433798\
894197466121469968970652154300626260453589099812575227594260877217437610\
731421774923304821790494440983623823577230674987439676046337648021513346\
133347839568274660824258513395388388222678611803018402813675597004538553\
47584532478

Ich habe das mal nachgerechnet allerdings komme ich a auf ein anderes Ergebnis und b zeigen mir alle Primzahltests, egal ob von C#, PHP oder Online, dass deine Primzahl keine Primzahl ist. Tippe ich etwas falsch ein? Die Zahl ist doch ohne \ zu verstehen. Warum sagen mir dann alle Tests das es keine Primzahl ist? :(

Wäre dir wirklich dankbar, wenn du mir erläutern oder zeigen könntest, dass es eine Primzahl ist oder wie die richtige 4096-bit Primzahl aussieht, da ich auch nicht mit pseudo Primzahlen in der Präsentation stehen will

kamakura schrieb:
Du kannst einfach mit der 2 anfangen und testen, ob sie eine Primitivwurzel ist, dann mit der 3, 5, 6, usw.

Was du nicht testen musst, sind Potenzen von Zahlen, die du bereits getestet hast und die keine Primitivwurzeln sind (denn dann sind die Potenzen auch keine Primitivwurzeln).

Ich wollte nicht den Generator finden, denn der ist doch schon im RFC als 2 angegeben oder irr ich mich?

Ich wollte die Zufallszahl a bzw. b generieren (der private Schlüssel von Alice oder Bob). Und dieser muss doch eine Zufallszahl (keine Primzahl oder?) zwischen 1 und p-1 sein, wobei es ja besser ist wenn die Zufallszahl recht groß ist.
So könnte man doch z.b. p*0,5 rechnen und dann die Zufallszahl zwischen p*0,5 und p-1 suchen, so wäre doch garantiert, dass die Zufallszahl groß ist und noch genug Raum für eine Zufallszahl besteht?

Vielen Dank für deine Hilfe :)

MfG
cpk2011
kamakura

kamakura hat kostenlosen Webspace.
13:54, 13.5.2016

computerkurs2011 schrieb:
Also bedeutet es doch, dass meine 4096-bit Primzahl sicherer ist als wenn ich nur eine 1024-bit benutze. Oder habe ich da grundlegende Verständnisprobleme
Ja, das ist richtig. Ich habe nur nicht verstanden, was du mir sagen wolltest.

kamakura schrieb:
Dann machst du was falsch. Warum ist die Zahl denn bei dir negativ? Das darf nicht sein! Irgendwas ist da schief gelaufen und du hast eine andere Zahl gekriegt, die keine Primzahl ist.
Dass der Miller-Rabin-Primzahltest sagt, deine Zahl wäre eine Primzahl, liegt möglicherweise daran, dass er ein probabilistischer Primzahltest ist. Wenn du den mit wenigen Iterationen durchführst, dann kann er eine Zahl, die keine Primzahl ist, schon mal fälschlicherweise als Primzahl ansehen.

Die 4096-Bit-Primzahl ist in Dezimal ausgedrückt:

104438888141315250667960271984652954583126906099213500902258875644433817\
202232269071044404666980978393011158573789036269186012707927049545451721\
867301692842745914600186688577976298222932119236830334623520436805101030\
915567415569746034717694639407653515728499489528482163370092181171673897\
245183497945589701030633346859075135836513878225037226911796898519432244\
453568741552200715163863814145617842062127782267499502799027867345862954\
439173691976629900551150544617766815444623488266596168079657690319911608\
934763494718777890652800800475669257166692296412256617458277670733245237\
100127216377684122931832490312574071357414100512456196591388889975346173\
534797001169325631675166067895083002751025580484610558346505544661509044\
430958305077580850929704003968005743534225392656624089819586363158888893\
636412992005930845566945403401039147823878418988859467233624276379513817\
635322284552464404009425896243361335403610464388192523848922401019419308\
891166616558422942466816544168892779046060826486420423771700205474433798\
894197466121469968970652154300626260453589099812575227594260877217437610\
731421774923304821790494440983623823577230674987439676046337648021513346\
133347839568274660824258513395388388222678611803018402813675597004538553\
47584532478

Ich habe das mal nachgerechnet allerdings komme ich a auf ein anderes Ergebnis und b zeigen mir alle Primzahltests, egal ob von C#, PHP oder Online, dass deine Primzahl keine Primzahl ist. Tippe ich etwas falsch ein? Die Zahl ist doch ohne \ zu verstehen. Warum sagen mir dann alle Tests das es keine Primzahl ist? :(
Ja, die
```
\
```
-Dinger müssen entfernt werden. Also so:
```
1044388881413152506679602719846529545831269060992135009022588756444338172022322690710444046669809783930111585737890362691860127079270495454517218673016928427459146001866885779762982229321192368303346235204368051010309155674155697460347176946394076535157284994895284821633700921811716738972451834979455897010306333468590751358365138782250372269117968985194322444535687415522007151638638141456178420621277822674995027990278673458629544391736919766299005511505446177668154446234882665961680796576903199116089347634947187778906528008004756692571666922964122566174582776707332452371001272163776841229318324903125740713574141005124561965913888899753461735347970011693256316751660678950830027510255804846105583465055446615090444309583050775808509297040039680057435342253926566240898195863631588888936364129920059308455669454034010391478238784189888594672336242763795138176353222845524644040094258962433613354036104643881925238489224010194193088911666165584229424668165441688927790460608264864204237717002054744337988941974661214699689706521543006262604535890998125752275942608772174376107314217749233048217904944409836238235772306749874396760463376480215133461333478395682746608242585133953883882226786118030184028136755970045385534758453247
```
Wenn ich das in den Online-Test eingebe, dann gibt der mir "Sehr wahrscheinlich eine Primzahl" raus.

Ich wollte nicht den Generator finden, denn der ist doch schon im RFC als 2 angegeben oder irr ich mich?
Richtig, den kannst du nehmen. Ich dachte, das wolltest du auch selber programmieren.
Ich wollte die Zufallszahl a bzw. b generieren (der private Schlüssel von Alice oder Bob). Und dieser muss doch eine Zufallszahl (keine Primzahl oder?) zwischen 1 und p-1 sein, wobei es ja besser ist wenn die Zufallszahl recht groß ist.
So könnte man doch z.b. p*0,5 rechnen und dann die Zufallszahl zwischen p*0,5 und p-1 suchen, so wäre doch garantiert, dass die Zufallszahl groß ist und noch genug Raum für eine Zufallszahl besteht?
Ich weiß nicht, warum dein Zufallszahlengenerator so lahm ist. Mit SageMath bekomme ich in einer Sekunde mit
```
randint(0,2^4096)
```
eine zufällige 4096 Bit-Zahl generiert.

EDIT: Ich habe herausgefunden, wo der Fehler mit der Primzahl war: Aus irgendeinem Grund hat sich da am Ende eine '8' eingeschlichen. In dem Fall wäre die Zahl ja sogar gerade gewesen. Aber jetzt ist alles richtig.

Beitrag zuletzt geändert: 13.5.2016 14:01:39 von kamakura
Autor dieses Themas
computerkurs2011

computerkurs2011 hat kostenlosen Webspace.

14:32, 13.5.2016
Hallo kamakura,

vielen Dank für deine Hilfe. Ich hatte beim Zufallsgenerator einen Denkfehler gemacht, nun klappt das finden auch deutlich schneller.

Die Primzahl ist jetzt tatsächlich eine Primzahl :p Das erklärt auch die unterschiedliche Ergebnisse.

Der Diffie-Hellman-Schlüsselaustausch funktioniert jetzt endlich schnell und richtig.

Den Generator selber zu berechnen, würde die Präsentation sprengen. Da ich noch RSA zur Authentifizierung und AES zum Verschlüsseln nehme und auch erläutern muss. Wobei ich den privaten RSA-Schlüssel mit AES noch einmal ummanteln werde, damit der lokal gespeicherte Schlüssel nur aus dem RAM beim Programmstart ausgelesen werden kann.

Ich werde noch weitere Zufallszahlen generieren während des DH Austauschs um damit dem bei Wikipedia beschriebenen Zeit-"Knacken" entgegen zu wirken.

Ich bedanke mich ganz herzlich bei dir für die wirklich konstruktive Hilfe.

Mit freundlichen Grüßen
cpk2011
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?

Über lima-city

lima-city bietet dir kostenlosen und werbefreien Speicherplatz für Deine Homepage. Sofort anmelden und direkt loslegen mit Webspace, PHP, Datenbanken, günstigen Domains und einer tollen Community!

kostenloser Webspace werbefrei: lima-city