Große Primzahlen berechnen für RSA

  • VB.NET
  • .NET (FX) 4.0

Es gibt 19 Antworten in diesem Thema. Der letzte Beitrag () ist von nafets.

    Große Primzahlen berechnen für RSA

    Hallo,

    dies ist mein erster Beitrag in diesem Forum. Ich komme einfach nicht weiter. Ich möchte in Visual Basic die RSA-Verschlüsselung realisieren. Nun hänge ich aber bei der Erstellung der Primzahlen. Man benötigt ja welche in Länge von 300-500 Stellen. Mit welchem Algorithmus bekomme ich das hin? Ich habe mich mit dem Miller-Rabin-Test versucht:

    Quellcode

    1. Function isPrim(ByVal p As BigInteger, ByVal z As Integer)
    2. Dim d As BigInteger = p - 1
    3. Dim r As BigInteger = 0
    4. While d Mod 2 = 0
    5. d = d / 2
    6. r += 1
    7. End While
    8. Dim a As String = ""
    9. Dim help As String = Convert.ToString(p)
    10. For k As Integer = 0 To help.Length - 3
    11. a &= rnd.Next(1, 10)
    12. Next
    13. Dim x As BigInteger = BigInteger.ModPow(a, d, p)
    14. If x = 1 Or x = p - 1 Then
    15. Return True
    16. End If
    17. Do While z > 1
    18. x = (x * x) Mod p
    19. If x = 1 Then
    20. Return False
    21. End If
    22. If x = p - 1 Then
    23. Return True
    24. End If
    25. z -= 1
    26. Loop
    27. Return False
    28. End Function



    Damit lassen sich Primzahlen mit 17 Stellen erzeugen. Ab 18 Stellen passiert nichts mehr.. :(

    Kann mir jmd. weiterhelfen? Den Algorithmus weiter optimieren oder mir Fehler aufzeigen?

    Danke schonmal!
    Willkommen im Forum,

    lyr0x schrieb:

    Ich möchte in Visual Basic die RSA-Verschlüsselung realisieren
    Aber bitte nicht so. Nutze bitte was fertiges aus dem Framework: msdn.microsoft.com/de-de/libra…ceprovider(v=vs.110).aspx

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:
    Warum genau willst Du es selber machen? Das ist ziemlich gefährlich, wenn man da was falsch macht. Also hast Du vor, das produktiv einzusetzen?

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:
    Ich habe mich vor ner Weile schonmal mit dem Thema der Generierung von zufälligen Primzahlen und der Optimierung dieses Vorgangs befasst, allerdings nicht mit solch extrem langen Primzahlen.
    Mein Ergebnis findest du im letzten Post von der ersten Seite dieses Threads: Create Random Primes (mein Code ist zwar in C#, lässt sich aber höchstwahrscheinlich mit einem Konverter korrekt übersetzen, sollte das notwendig sein).
    Die wichtigste Frage, die du dir stellen musst, ist, ob die generierten Zahlen zu 100,0% Prim sein müssen, oder ob es reicht, mit sehr hoher Wahrscheinlichkeit eine Primzahl vorliegen zu haben. In dem Beispiel hatte ich eine Version des Miller-Rabin-Tests implementiert, welche bis zu einer bestimmten Obergrenze deterministisch ist (100%) - ich erinnere mich jetzt nicht mehr an die Größenordnung dieser, man findet dazu aber sicherlich etwas. Auf jeden Fall sollte gesagt sein, dass ein probabilistischer Primzahltest deutlich performanter als ein deterministischer ist.
    Auf jeden Fall würde ich dir empfehlen, meinen Code anzuschauen und im Speziellen die Optimierungen in den einzelnen Methoden zu übernehmen.
    Hallo,

    ich habe deinen Beitrag gelesen und meinen Code noch etwas Optimiert. Das Problem ist nur, dass bis 16 Stellen alles funktioniert. Ich kann 100 Primzahlen binnen 1 Sekunde finden,welche 16 Stellen lang sind. Aber sobald ich auf 17+ Stellen erhöhe hängt sich das Programm auf :( Wird es um soviel schwieriger bei einer Stelle mehr? Oder mache ich etwas Falsch? Hab ich einen Denkfehler im Algorithmus?

    Quellcode

    1. Function PreCheck(ByVal p As BigInteger)
    2. Dim prim() As Integer = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
    3. 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
    4. 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
    5. 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
    6. 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
    7. 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433,
    8. 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521,
    9. 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613,
    10. 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
    11. 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
    12. 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
    13. 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}
    14. For i As Integer = 0 To 10
    15. If BigInteger.ModPow(p, 1, prim(i)) = 0 Then
    16. Return False
    17. End If
    18. Next
    19. Return True
    20. End Function
    21. Function IsPrime(ByVal n As BigInteger, ByVal k As BigInteger, ByVal p As String) As Boolean
    22. If n < 2 Then
    23. Return False
    24. End If
    25. If n <> 2 AndAlso n Mod 2 = 0 Then
    26. Return False
    27. End If
    28. Dim s As BigInteger = n - 1
    29. While s Mod 2 = 0
    30. s >>= 1
    31. End While
    32. Dim r As New Random()
    33. For i As BigInteger = 0 To k - 1
    34. Dim a As String = ""
    35. For x As Integer = 0 To p.Length - 2
    36. a = a & r.Next(1, 10)
    37. Next
    38. Dim temp As BigInteger = s
    39. Dim [mod] As BigInteger = BigInteger.ModPow(a, temp, n)
    40. While temp <> n - 1 AndAlso [mod] <> 1 AndAlso [mod] <> n - 1
    41. [mod] = ([mod] * [mod]) Mod n
    42. temp = temp * 2
    43. End While
    44. If [mod] <> n - 1 AndAlso temp Mod 2 = 0 Then
    45. Return False
    46. End If
    47. Next
    48. Return True
    49. End Function
    Da spiele ich auch gerade mit herum. Folgenden Code habe ich gefunden, der funzt. Vielleicht hilfts's?
    Achtung: Im Projekt muss der Verweis auf System.Numerics gesetzt werden.

    VB.NET-Quellcode

    1. Imports System.Numerics
    2. Public Class Form1
    3. Dim p As BigInteger
    4. Dim j As Integer
    5. Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
    6. ' Große Primzahl suchen
    7. Do
    8. p = RandomBigInt(5)
    9. j = j + 1
    10. Loop Until IsFermatPrime(p.ToString(), 3)
    11. TextBox1.Text = p.ToString
    12. TextBox2.Text = j
    13. End Sub
    14. Function IsFermatPrime(number As String, n As Integer) As Boolean
    15. Dim p = BigInteger.Parse(number), len = number.Length
    16. If p = 2 Then Return True
    17. If p.IsEven Then Return False
    18. ' n Test-Durchläufe
    19. For j = 1 To n
    20. ' Geeignete zufällige Basis suchen
    21. Dim a As BigInteger
    22. Do
    23. a = RandomBigInt(len, True)
    24. Loop Until (a > 1) And (a < p)
    25. ' Können wir die Zahl überführen?
    26. Dim res = BigInteger.ModPow(2, p - 1, p)
    27. If res <> 1 Then Return False
    28. Next
    29. Return True
    30. End Function
    31. Function RandomBigInt(numDigits As Integer, Optional randomLength As Boolean = False) As BigInteger
    32. Static rnd As New Random()
    33. If randomLength Then numDigits = rnd.Next(1, numDigits + 1)
    34. Dim num = String.Join("", (From i In Enumerable.Range(1, numDigits) Select res = rnd.Next(0, 10).ToString()).ToArray())
    35. Return BigInteger.Parse(num)
    36. End Function
    37. End Class


    Code-Tags eingefügt. ~Thunderbolt

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Thunderbolt“ ()

    Nö, aber wiki kennt die C-Implementierung, kann man also mit ein bißchen Ausdauer hinkriegen.
    de.wikipedia.org/wiki/Miller-Rabin-Test#Algorithmus

    Machst Du die ganze Verschlüsselung (Sender vs. Empfänger)?

    C-Quellcode

    1. #include <stdint.h>
    2. bool mrt (const uint32_t n, const uint32_t a) { // n ungerade, 1 < a < n-1
    3. const uint32_t n1 = n - 1;
    4. uint32_t d = n1 >> 1;
    5. int j = 1;
    6. while ((d & 1) == 0) d >>= 1, ++j;
    7. uint64_t t = a, p = a;
    8. while (d >>= 1) { //square and multiply: a^d mod n
    9. p = p*p % n;
    10. if (d & 1) t = t*p % n;
    11. }
    12. if (t == 1 || t == n1) return true; // n ist wahrscheinlich prim
    13. for (int k=1 ; k<j ; ++k) {
    14. t = t*t % n;
    15. if (t == n1) return true;
    16. if (t <= 1) break;
    17. }
    18. return false; // n ist nicht prim
    19. }


    Code-Tags eingefügt. ~Thunderbolt

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Thunderbolt“ ()

    Nach einigen Tests bin ich auch zum Entschluss gekommen, dass der Miller Rabin Test dazu wirklich gut geeignet ist.
    Die von @nafets RandomPrimes-Solution.zip finde ich gut gelungen.

    Ferma kann ja genutzt werden als Vorselektionierung, ähnlich wie ich es hier gemacht habe unter ModifiedCryptoRngV02.3.0.zip
    Meine Miller Rabin habe ich übrigends von hier, ein wirklich gutes Tutorial dafür. Wer ganz sicher gehen will, kann ja noch die Germain-Zahlen einbringen, leider zu lasten der Performance.

    Hier (NSC) nutze ich einen Zufallszahlengenerator der in etwa eine 1000-stellige Zahl produziert.

    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „exc-jdbi“ ()

    Super! Falls Du den Code fertig hast, wäre ich interessiert!

    Dazu muss ich folgendes sagen: Mit RSA komme ich nicht gut zurecht, weil es deterministisch ist, ein verschlüsselter Code führt also zu immer demselben Ergebnis.

    Wiki (08.05.2017 9:51 Uhr)„In der Praxis wird das RSA-Verfahren wie oben beschrieben nicht eingesetzt, da es mehrere Schwächen hat. …Die RSA-Verschlüsselung ist deterministisch. …… Um solche Angriffe zu verhindern, werden bei RSA-Verschlüsselung und RSA-Signatur sogenannte Padding-Verfahren eingesetzt…“

    Man muss also zusätzlich ein Verstrubbelungs-HASH-Verfahren programmieren. Das wäre mir zu aufwändig. Ich spiele daher mit Diffie Hellman rum.
    de.wikipedia.org/wiki/Diffie-Hellman-Schl%C3%BCsselaustausch

    Das ist dasselbe Primzahlenprinzip, aber ohne weitere Verfahren. Nachteilig ist dabei, dass Sender und Empfänger kommunizieren müssen.
    Also, ich habe mal ein bisschen mit meiner alten Methode, welche ich in meinem verlinkten Post schon genutzt hätte (ich musste lediglich ein paar Variablen von ulongs oä zu BigIntegern ändern und kann so ausgehend von einer zufälligen 500-stelligen Zahl in zwischen 2 und 40 Sekunden mit meinem Laptop (i5-7200U mit 3GHz) die nächstgelegene Primzahl finden. Würde man das Ganze an ein paar Stellen optimieren und auch mögliche Kandidaten mit Multithreading parallel abarbeiten, könnte man sicher konstant unter 10s kommen, was ja dafür, dass man RSA-Keys eigentlich nur einmalig generiert, ausreichend schnell sein müsste.

    Und an die anderen, die sagen, dass der OP doch einen anderen Algorithmus versuchen soll: Lasst ihn doch RSA ausprobieren - die Generierung von Primzahlen für Alfons wie RSA ist ein tolles Thema, bei welchem man sehr viel über Optimierung lernen kann und auch der Rest von der Implementation von RSA sollte durchaus eine Menge Erfahrung beschaffen :)
    @nafets Das sehe ich genauso, wenn man immer nur gesagt bekommt, befass' dich lieber mit etwas fertigem was sicher ist, dann wird es nie wieder Leute geben die mal Optimierungen durchführen können. Manche Leute, so der Eindruck, meinen hier den Entwicklern vorzuschreiben was sie zu tun haben un was sie zu lassen haben.
    @nafets danke das dus erwähnst. Wie gesagt, möchte ich mich nur zum Üben damit befassen. Eine Frage: in deinem C# Code in deinem anderen Post benutzt du in Zeile 53 in Beitrag 12 steht folgendes:

    Quellcode

    1. ​ulong d = n1 >> 1;


    Kannst du oder irgendjemand mir erklären was genau hier passiert und warum?
    Dass ist ein 1-facher Bitshift nach rechts: Dabei wird jedes Bit von der Binärrepräsentation der Zahl um eine Stelle nach rechts verschoben. Letztlich teilt es die gegebene Zahl durch 2.

    Generell gilt übrigens, dass ein n-facher Bitshift nach rechts die Zahl durch 2^n teilt und ein n-facher nach links die Zahl mit 2^n multipliziert - es ist einfach schneller als die wirkliche Operation.