Wie schwierig ist es, 1024-Bit-Primzahlen zu erzeugen?

• Ein Experiment, bei dem die zwei für einen 2048-Bit-RSA-Schlüssel benötigten Primzahlen von jeweils etwa 1024 Bit direkt in Rust erzeugt wurden und dafür alles von der Zufallszahlenerzeugung bis zur Arithmetik großer Ganzzahlen ohne externe Abhängigkeiten implementiert wurde
• Eine einfache trial division reichte bei 16 Bit mit rund 40 ms aus, brauchte aber selbst bei 64 Bit nach Optimierungen noch 6,4 Sekunden und ließ sich daher kaum auf 1024 Bit skalieren
• Der Fermat-Test ist schnell, kann aber Pseudoprimzahlen nicht zuverlässig aussortieren, daher wurde für die endgültige Entscheidung ein Miller-Rabin-Test mit k=10 verwendet
• Um die Grenzen der eingebauten Ganzzahltypen zu überwinden, wurde ein eigenes BigInt gebaut; durch den Wechsel von bool-Arrays zu Byte-Arrays und schließlich zu u64-Chunk-Strukturen sank die Zeit zur Erzeugung einer 1024-Bit-Primzahl von 32 Minuten auf 60–90 Sekunden
• Die finale Implementierung kombiniert ein BigInt mit u64-Chunks, schnelle Division, trial division mit kleinen Primzahlen, das Erhöhen des Kandidatenwerts um +2 und parallele Ausführung mit 16 Threads und fand so im Mittel in etwa 40 ms eine 1024-Bit-Primzahl, ist aber keine validierte Kryptobibliothek

---

1024-Bit-Primzahlen für RSA selbst erzeugen

• Ziel war es, Primzahlen zu erzeugen, die sich für die RSA-Schlüsselerzeugung verwenden lassen
  • Ein 2048-Bit-RSA-Schlüssel entsteht als Produkt zweier Primzahlen, daher werden zwei Primzahlen mit jeweils ungefähr 1024 Bit benötigt
  • Damit verengte sich die Herausforderung ganz natürlich auf die Erzeugung von 1024-Bit-Primzahlen
• Für das Experiment wurden drei Einschränkungen gesetzt
  • Der Code wird von Grund auf selbst geschrieben und verwendet keine externen Abhängigkeiten
  • Es wird ein Laptop mit AMD-Ryzen-7-CPU und 16 GB RAM verwendet, ohne externe Hardware oder Cloud
  • Die Primzahl muss in „vernünftiger Zeit“ erzeugt werden
• Als Sprache wurde Rust gewählt, das der Autor gerade lernte
  • Es erschien nah genug an Low-Level-Konzepten und zugleich hoch genug, um Codefragmente gut verstehen zu können

Die Grenzen von trial division bei 16 und 64 Bit

• Der grundlegende Ablauf bestand darin, wiederholt eine N-Bit-Zufallszahl zu erzeugen und zu stoppen, sobald sie einen Primzahltest besteht
• Die Zufallszahlen wurden nicht mit Rusts rand-Crate erzeugt, sondern durch direktes Lesen aus Linux-/dev/urandom
  • /dev/urandom ist eine Pseudogerätedatei für den Zugriff auf den CSPRNG des Linux-Kernels
  • Der Kernel sammelt Entropie aus der Benutzerumgebung und setzt einen auf ChaCha20 basierenden deterministischen Stromchiffre-Generator periodisch neu
• Bei 16-Bit-Zufallszahlen wurden das erste und das letzte Bit auf 1 gesetzt
  • Das letzte Bit 1 garantiert eine ungerade Zahl
  • Das erste Bit 1 stellt sicher, dass der gesamte benötigte Bitbereich genutzt wird
• Bei 16 Bit wurde schon mit bloßer trial division durch alle Zahlen von 3 bis sqrt(num) in etwa 40 ms eine Primzahl gefunden
  • Ein Beispiel ergab Prime found: 44809, die Gesamtzeit lag bei etwa 0,038 Sekunden
• Bei der Erweiterung auf 64 Bit dauerte einfache trial division rund 30 Sekunden
  • Danach wurde verbessert, indem nur noch Kandidaten der Form 6k±1 geprüft und zunächst durch eine Liste kleiner Primzahlen geteilt wurden
  • Nach diesen Verbesserungen dauerte die Erzeugung einer 64-Bit-Primzahl 6,414 Sekunden
• Schon bei 64 Bit mit 6 Sekunden wurde klar, dass sich dieser Ansatz nicht sinnvoll bis zur Erzeugung von 1024-Bit-Primzahlen skalieren lässt

Wechsel zu probabilistischen Primzahltests

• Es wurden zwar deterministische Algorithmen wie APR-CL und ECPP betrachtet, sie erwiesen sich aber als mathematisch komplex und schwer zugänglich für eine eigene Implementierung
• Nach dem Blick in den OpenSSL-Quellcode und die NIST-Empfehlungen zeigte sich, dass in realen Anwendungen einschließlich RSA probabilistische Primzahltests weit verbreitet sind
• Der Algorithmus wechselte damit von „beweist, dass die Zahl prim ist“ zu „stuft sie mit gegebener Genauigkeit als probable prime ein“

• Fermat-Test

  • Das kleine Theorem von Fermat nutzt die Beziehung, dass für eine Primzahl p und ein a, das nicht durch p teilbar ist, a^(p-1) = 1 mod p gilt
  • Da einfache Potenzierung bei u128 überläuft, wurde modulare Exponentiation implementiert
  • pow() erwartet einen Exponenten vom Typ u32, und das Potenzieren von u128 mit größeren Exponenten kann zu Überläufen führen
  • Auch die Multiplikation selbst kann den u128-Bereich überschreiten, weshalb vorübergehend nur 64-Bit-Zahlen innerhalb von u128 gespeichert wurden
  • Der Fermat-Test ist schnell, kann aber wegen Fermat-Pseudoprimzahlen zusammengesetzte Zahlen fälschlich als prim einstufen
  • Solche zusammengesetzten Zahlen sind selten, aber häufig genug, dass der Fermat-Test allein als nicht zuverlässig genug angesehen wurde

• Miller-Rabin-Test

  • Miller-Rabin basiert auf derselben Grundidee wie der Fermat-Test, ist aber ein stärkerer probabilistischer Primzahltest
  • Die Implementierung zerlegt n-1 in die Form 2^s × d und prüft dann mehrere Bedingungen
  • a^d = 1 mod n
  • oder für ein 0 <= r < s gilt a^(2^r × d) = n - 1 mod n
  • In 128-Bit-Experimenten wurde ähnlich wie beim Fermat-Test in etwa 0,042 Sekunden eine Primzahl gefunden
  • Die Fehlerschranke im schlimmsten Fall liegt bei Miller-Rabin bei 4^-k, für große n im Mittel eher bei 8^-k
  • Bei k=10 ergab sich eine mittlere Fehlerwahrscheinlichkeit von 0.000000000931323%
  • Verglichen wurde das mit der Wahrscheinlichkeit 2^-30, also 30-mal hintereinander eine Münze zu werfen und jedes Mal Kopf zu erhalten
  • Für echte Kryptografie muss man bei der Wahl zufälliger Basen und unter adversariellen Bedingungen vorsichtiger sein

Ein BigInt selbst bauen

• Mit Rusts eingebauten Ganzzahltypen ließen sich Zahlen jenseits von 64 Bit nicht ausreichend gut handhaben, daher wurde eine Implementierung für Ganzzahlen mit beliebiger Präzision (BigInt) nötig
• Wegen der Einschränkung, keine externe bigint-Crate zu verwenden, wurde auch BigInt selbst implementiert

• Versuch 1: Array aus Dezimalziffern

  • Zunächst wurde versucht, große Zahlen als Array aus Dezimalziffern zu speichern
  • Addition und Multiplikation ließen sich wie bei schriftlichen Rechenverfahren umsetzen, an der Division scheiterte der Ansatz jedoch

• Versuch 2: Binärarray auf Basis von bool

  • Der zweite Ansatz speicherte die Zahl als Array aus 0 und 1
  • BigInt verwendete ein Array [bool; 2048]
  • Beim Multiplizieren zweier 1024-Bit-Zahlen wird Platz für bis zu 2048 Bit benötigt, daher wurden 2048 Bit vorgesehen
  • Addition und Subtraktion wurden mit einem Full-Adder-Verfahren implementiert
  • Die Multiplikation nutzte die Eigenschaften binärer Zahlen und arbeitete als shift-and-add
  • Die Division wurde als binäre schriftliche Division umgesetzt
  • Mit dieser Implementierung gelang zwar die erste 1024-Bit-Primzahl, aber die Laufzeit lag bei etwa 32 Minuten und 44,90 Sekunden
  • Technisch war das Ziel erreicht, doch die Bedingung einer „vernünftigen Zeit“ wurde klar verfehlt

• Versuch 3: Byte-Chunks

  • Dann fiel auf, dass jedes bool im bool-Array nicht 1 Bit, sondern 1 Byte belegt
  • [bool; 2048] belegt also nicht 2048 Bit, sondern 2048 Byte
  • Danach wurde auf ein Schema umgestellt, bei dem 2048 Bit in einem Array von 256 Byte gespeichert werden
  • Addition, Subtraktion und Multiplikation funktionierten ohne große Änderungen weiter; die Division wurde so angepasst, dass Byte-Chunks wie eine Bitliste behandelt werden
  • Damit sank die Zeit zur Erzeugung einer 1024-Bit-Primzahl auf 4 Minuten 43 Sekunden

• Versuch 4: u64-Chunks

  • Der Byte-Chunk-Ansatz war letztlich ein ziffernbasiertes BigInt mit höherer Basis
  • Im nächsten Schritt wurden 2048 Bit als 32 u64-Chunks gespeichert
  • Jeder Chunk funktionierte wie eine einzelne „Ziffer“
  • Für das Produkt zweier u64-Chunks wurde u128 genutzt
  • In dieser Struktur lässt sich eine 1024-Bit-Zahl nicht als 309 Dezimalstellen, sondern als 16 u64-Chunks darstellen
  • Die Zeit zur Erzeugung einer 1024-Bit-Primzahl verbesserte sich auf 60–90 Sekunden

Optimierung der Engpässe

• In einfachen Benchmarks war der Unterschied zwischen der binären Implementierung und der u64-Chunk-Implementierung deutlich
  • a + b und a - b: 5537.35ns → 123.57ns
  • a * b: 1292283.14ns → 842.32ns
  • a / b und a % b: 733446.76ns → 44440.12ns
  • a < b und a > b: 2506.02ns → 58.91ns
• Die anschließenden Optimierungen konzentrierten sich vor allem auf Division, Multiplikation, interne Operationen in Miller-Rabin und die Logik zur Erzeugung von Kandidaten

• Division

  • Der größte Engpass war die Division
  • Selbst mit u64-Chunks arbeitete die vorhandene Division intern noch als schriftliche Division Bit für Bit
  • Unter Bezug auf den Algorithmus auf Seite 598 des Handbook of Applied Cryptography wurde eine radixbasierte schriftliche Division implementiert
  • Dabei wird die aktuelle Quotienten-„Ziffer“ aus den ersten 3 „Ziffern“ des Dividend und den ersten 2 „Ziffern“ des Divisor geschätzt
  • Diese Implementierung sparte pro Division etwa 40.000 ns
  • Falls der Divisor aus nur einem einzigen u64-Chunk bestand, wurde ein Spezialfall mit direkterer schriftlicher Division über u128 verwendet
  • Gerade in Miller-Rabin tritt dieser Fall häufig auf

• Multiplikation

  • Die Multiplikation wurde etwa doppelt so schnell, indem die Schleifen so umgestellt wurden, dass kein BigInt mehr für Zwischenergebnisse nötig war
  • Außerdem wurde gezählt, wie viele Chunks tatsächlich belegt sind, damit Schleifen nur über nicht nullwertige Chunks laufen
  • Da BigInt meist Zahlen bis 1024 Bit enthält, bleibt oft etwa die Hälfte des 2048-Bit-Speicherraums ungenutzt
  • Karatsuba- oder FFT-basierte Multiplikation wurden ebenfalls betrachtet, erschienen aber für eine Eigenimplementierung zu komplex, und die aktuelle Multiplikation war bereits schnell genug

• Interne Optimierungen in Miller-Rabin

  • In der Miller-Rabin-Implementierung lag der Fokus darauf, teure Operationen zu reduzieren
  • Statt x = mod_exp(x, 2, n) wurde direkt x = (x * x) % n berechnet
  • Das erste mod_exp() wurde durch eine vereinfachte Inline-Version ersetzt, um den Overhead von Funktionsaufrufen zu reduzieren
  • Für die Prüfung auf gerade Zahlen wurde num.is_even() ergänzt, um % 2 zu vermeiden
  • d / 2 wurde in d >>= 1 geändert
  • += 1 und -= 1 wurden als Spezialfälle über increase() und decrease() behandelt
  • Gerade is_even() und d >>= 1 brachten jeweils etwa 70.000 ns Gewinn
  • Im finalen Benchmark wurde die optimierte u64-Chunk-Version deutlich schneller
  • a * b: 842.32ns → 295.04ns
  • a / b und a % b: 44440.12ns → 831.77ns
  • a / 2: 75121.58ns → 60.89ns
  • a % 2 == 0: 78400.87ns → 21.65ns
  • a - 1: 103.15ns → 67.54ns

Der finale 1024-Bit-Primzahlgenerator

• Die finale Funktion liest zunächst eine 1024-Bit-Zufallszahl aus /dev/urandom
  • Das höchstwertige Bit wird gesetzt, um 1024 Bit Länge sicherzustellen
  • Das niederwertigste Bit wird gesetzt, um eine ungerade Zahl sicherzustellen
• Anschließend wird nicht jedes Mal eine komplett neue Zufallszahl gelesen, sondern jeweils 2 zum Kandidaten addiert, um zum nächsten ungeraden Kandidaten zu gehen
  • increase_by_2() führt dabei meist nur eine Addition in einem einzigen u64-Chunk aus
• Vor Miller-Rabin wird zunächst trial division mit einer Liste kleiner Primzahlen durchgeführt
  • Im finalen Code werden die ersten 1000 kleinen Primzahlen verwendet
  • Diese kleinen Primzahlen passen in einen einzelnen u64-Chunk und profitieren daher vom schnellen Spezialfall der Ein-Chunk-Division
• Das Problem lässt sich als embarrassingly parallel behandeln, da weder gemeinsam genutzter Speicher noch Synchronisation zwischen Threads nötig sind
  • 16 CPU-Threads suchen jeweils nach einer Primzahl, und der Wert des Threads, der zuerst ein Ergebnis liefert, wird verwendet
• Ein finales Beispiel lief mit einer elapsed time von etwa 0,086 Sekunden
  • Die CPU-Auslastung wurde mit 690 % angezeigt
• Der Durchschnitt aus 100 Läufen lag bei 0.04109 ± 0.00307 Sekunden
  • Im Mittel wurde also in rund 40 ms eine 1024-Bit-Primzahl gefunden
  • Einzelne Aufrufe von prime_1024bit() können wegen der Zufälligkeit zwischen etwa 8 ms und etwa 800 ms schwanken
  • Durch die parallele Ausführung und die Wahl des schnellsten Ergebnisses wird diese Schwankung abgefedert

Code und Grenzen

• Der vollständige Code und das Repository sind auf github veröffentlicht
• Diskussionslinks gibt es auf hackernews und reddit
• Diese Implementierung ist wahrscheinlich nicht für echte kryptografische Sicherheit geeignet; sie zielte auch nicht auf eine Kryptobibliothek, sondern eher auf ein Lern- und Implementierungsexperiment ab

[GN⁺]

Hacker-News-Meinungen

• Es gab einige Kryptowährungen, die das Finden großer Primzahlen als Teil ihrer Proof-of-Work-Funktion nutzten, und vor etwa acht Jahren konnte man schon mit einer sehr schnellen Implementierung für Primzahltests ziemlich gut Geld verdienen.
  Ich war eine Zeit lang Autor und Maintainer der Mining-Software für riecoin; warum genau, weiß ich nicht mehr, vermutlich einfach, weil ich Primzahlen mochte.
  Dieser Beitrag lässt die wichtigste Optimierung für schnelle Primzahltests aus: Montgomery-Multiplikation: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
  Sie ist die Grundlage praktischer schneller Implementierungen modularer Exponentiation.
  Niall Emmart, der damals meines Wissens in der Wissenschaft war und heute bei Nvidia ist, hat die unglaublich schnelle GPU-Big-Integer-Bibliothek CGBN veröffentlicht: https://github.com/NVlabs/CGBN
  Sie ist immer noch die schnellste Implementierung für Batch-modulare Exponentiation, die ich kenne, und wenn ich kurz nerdig schwärmen darf: atemberaubend.
  Irgendwann sollte ich die Geschichte aufschreiben, wie ich damit die Produktion einer kleinen Kryptowährung etwa fünf Jahre lang dominiert habe. Außerdem enthält Python mit der Drei-Argumente-Form von pow(x, y, m) eine ziemlich gute modulare Exponentiation zur Berechnung von x^y % m.
  Damit lassen sich Fermat- oder Miller-Rabin-Primzahltests sehr einfach bauen, wenn man sie selbst implementieren möchte, und das macht ziemlich Spaß. Wenn man sie nicht selbst bauen will, ist auch mpz_probab_prime() aus der gmp-Bibliothek gut. gmp ist natürlich schneller, aber beim Herumspielen mit großen Primzahlen ist der Spaß an einem zweizeiligen Fermat-Test schwer zu übertreffen.

  • Niall war auch an einer der prämierten ZPrize-Einreichungen zu schneller Multi-Skalar-Multiplikation beteiligt.
    Das ist eng mit Batch-modularer Exponentiation verwandt, arbeitet aber nicht modulo einer Primzahl, sondern auf elliptischen Kurven. Ich sehe das als Fortsetzung der CGBN-Arbeit.
    Letztes Jahr hat er beim Krypto-Lunch-Seminar in Stanford einen guten Vortrag gehalten; Folien und Aufzeichnung sind online.
    https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
    https://www.youtube.com/watch?v=KAWlySN7Hm8
  • Ich frage mich, warum solche Kryptowährungen so eine maßgeschneiderte Proof-of-Work-Funktion verwendeten.
    Ich wüsste gern, ob sie nur die vage Vorstellung hatten, dass Kryptografie irgendwie Primzahlen nutzt, ohne zu wissen, wann und warum, oder ob es einen tieferen Grund gab.
  • Wegen pow(x,e,mod) bin ich von Perl zu Python gewechselt.

• Wenn es einen vorgegebenen Maximalbereich für Zahlen gibt, ist es einfach, Miller-Rabin praktisch deterministisch zu machen.
  Man wählt Basen, für die bewiesen ist, dass sie alle Pseudoprimzahlen innerhalb dieses Bereichs gemeinsam aussieben.
  Die Liste wird auch nicht lang. Miller-Rabin ist wirklich mächtig.

  • Ich frage mich, welche Basen das für den Bereich der 1024-Bit-Zahlen sind.
    Online habe ich keine Antwort gefunden.
  • Außerdem kann man, wenn man einfach nur Primzahlen sucht, Kandidaten auswählen, die wie Primzahlen aussehen, und sie dann mit einem deterministischen Test bestätigen.

• Eine Zeile Inline-Assembly macht die Schulbuchmultiplikation großer Ganzzahlen einfach: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
  Wenn ich in der Zeit zurückgehen und an C nur eine Sache ändern könnte, würde ich das Konzept der erweiterten Multiplikation einbauen. Schade, dass Rust das auch nicht hat. Hardware-Unterstützung gibt es überall. Der Cortex M0 kann nicht einmal dividieren, hat aber erweiterte Multiplikation.
  Der Code stammt aus einer sehr hässlichen Spielzeug-RSA-Implementierung, die ich vor langer Zeit geschrieben habe: https://github.com/jcalvinowens/toy-rsa
  Der Grund, warum ein Fermat-Test allein ausreichte, war, dass der Algorithmus nicht funktioniert hätte, wenn die Primzahlen nicht tatsächlich prim gewesen wären. Der Fermat-Test ist schnell, und ein einmaliges Ver- und Entschlüsseln beseitigt auch die extrem geringe Wahrscheinlichkeit, dass eine der beiden Zahlen ein Fermat-Lügner ist.
  Allerdings weiß ich nicht, ob man beweisen kann, dass es keine RSA-Schlüsselpaare gibt, die Nachrichten auch mit nicht-primen P/Q-Werten erfolgreich ver- und entschlüsseln können. In einer echten Implementierung wäre das natürlich nicht der richtige Weg, aber ich habe nie eine Antwort darauf gefunden.

  • Interessanterweise hat C inzwischen große Ganzzahlen.
    In C23 wurde der Typ _BitInt(N) hinzugefügt; zum Beispiel kann man für einen 128-Byte-Typ _BitInt(1024) verwenden.
    Die Compiler-Unterstützung ist allerdings begrenzt. In Clang kann man mit dem Flag -fexperimental-max-bitint-width=N erlauben, dass N größer als 128 ist. Wenn N größer als 128 ist und man _BitInt(N) dividiert, crasht der Compiler einfach, aber +, -, * funktionieren wie erwartet.
  • In Zig ist das vergleichsweise einfach.
    Es gibt das Built-in @mulWithOverflow, das zusammen mit dem Ergebnis das Overflow-Bit zurückgibt, und Integer gibt es bis (u|i)65535.
    Je nachdem, was man tut, kann man nach dem Erkennen eines Overflows auf einen größeren Typ anheben oder zuerst anheben und anschließend optional abschneiden.
    Außerdem unterstützt Zig mit den separaten Operatoren *| saturierende Multiplikation und mit *% Wrapping-Multiplikation. Man kann sie verwenden, wenn man genau diese Semantik braucht. Andere Overflows sind undefiniertes Verhalten, das von Safety-Checks erfasst wird; in den Build-Modi Debug und ReleaseSafe führt das zu einer Panic.
  • Wenn p und q teilerfremde Carmichael-Zahlen sind, kann RSA Nachrichten weiterhin erfolgreich ver- und entschlüsseln.
    Allerdings hat p*q dann kleinere Primfaktoren und ist leichter zu faktorisieren, was die Sicherheit senkt.
  • Meines Wissens erzeugen die meisten C-Compiler und Rust genau den gewünschten Maschinenbefehl, wenn man zuerst in einen größeren Typ castet und dann multipliziert.
  • Philip Zimmermanns ursprüngliches Pretty Good Privacy (PGP) von 1994 verwendete nur ein Sieb, das durch alle bekannten 16-Bit-Primzahlen teilte; diese Tabelle wurde mit dem Sieb des Eratosthenes erzeugt. Danach wurde ein Fermat-Test angewendet.

• Ich frage mich, wie lange diese Arbeit gedauert hat.
  Ich habe in einem Forschungsprojekt im Bachelor Multiplikation großer Ganzzahlen gemacht, und das hat fast zwei Semester gedauert. Ich habe Karatsuba, Toom-Cook, komplexe FFT, einige NTTs und Schönhage-Strassen implementiert.
  Primzahlen sind fast schon mathematische Magie. Für alle, die sich dafür interessieren, ist Silvermans A Friendly Introduction to Number Theory ein hervorragendes Mathebuch.
  Nebenbei: Der Link auf der Seite lautet 4025051 statt 40250519.

• Guter Artikel. Ich habe vor Kurzem selbst ein wenig Big-Integer-Code für eine frühe Version von [0] geschrieben, und ich erinnere mich, wie frustrierend es ist, die abstrakten Beschreibungen in mathematischen Papers in tatsächliche Operationen zu übersetzen.
  Allerdings habe ich einen kleinen Einwand:
  Wenn man den gesamten Bereich von u64 nutzt, sind die Zahlen nicht zur Basis 2^64-1, sondern zur Basis 2^64 dargestellt. Jedes Word hat einen Bereich von 0 bis 2^64-1, genauso wie jede Dezimalziffer von 0 bis 9 geht.
  [0] https://github.com/LegionMammal978/bigfoot-sim

• Wenn man wie bei der letzten Optimierung im Fehlerfall keine neue Zufallszahl erzeugt, sondern die Zahl jeweils um 2 erhöht, schwächt das die Sicherheit ein wenig.
  Da Primzahlen nicht gleichmäßig verteilt sind, entsteht eine Verzerrung zugunsten von Primzahlen direkt nach großen Primzahllücken.

  • Das habe ich bei der Recherche gelesen.
    Es ist ein Kompromiss zwischen Ausführungsgeschwindigkeit und Zufälligkeit der Primzahl; ich habe mich für Geschwindigkeit entschieden, weil 16 Threads jeweils bei einer Zufallszahl starten und darum konkurrieren, eine Primzahl zu finden, was meiner Ansicht nach genug zusätzliche Zufälligkeit bringt.
    Wenn man Zufälligkeit stärker gewichtet als Geschwindigkeit, ist es eine einfache Änderung, +=2 durch einen rng()-Aufruf zu ersetzen.

• Guter und gut geschriebener Artikel.
  Der Autor meint vermutlich base-256, nicht base-255.

• Ein paar 1–2-KB-Zahlen passen problemlos in den L1-Cache, und selbst wenn nicht, gibt es mehr als ein Megabyte L2-Cache mit etwa 3 ns Zugriffszeit.
  Im Artikel heißt es, man habe wegen L1-Cache-Misses vermutlich auf RAM-Lese-/Schreibzugriffe gewartet, aber darauf wird später nicht mehr zurückgekommen.
  Außerdem geht es hier nur um die Primzahlerzeugung, man vermeidet also die meisten Fallstricke von RSA, und urandom sollte sicher sein. Wenn der Code korrekt funktioniert, gibt es nicht allzu viel, was gravierend schiefgehen kann.
  Bei RSA gibt es einige Themen rund um schwache Primzahlen, die man vermeiden sollte, aber ich weiß nicht, ob sie hier häufig genug auftreten, um praktisch ein Problem zu sein.

• Das erinnert mich an ein Projekt im ersten Studienjahr vor einigen Jahrzehnten.
  Mein Projektpartner und Freund, der später Jahrgangsbester wurde, hatte die Idee und implementierte die zentrale Mathematik: eine 4096-Bit-RSA-Verschlüsselung zu bauen.
  Ich erinnere mich, wie langsam die Primzahlerzeugung in der finalen Implementierung war. Auf einer PA-RISC-Workstation dauerte die Erzeugung etwa 20 Minuten.
  Mein mathematikbegeisterter Freund optimierte den Code auch nach Projektende weiter, und ich erinnere mich, wie er Papers zu Primzahltests und Big-Integer-Mathematik las.
  Zum Beispiel brachte es eine enorme Verbesserung, bei der Multiplikation von Komponenten die Multiplikation zu überspringen und das Ergebnis als 0 zu setzen, wenn einer der Werte 0 war.

  • Auf langsamer Hardware ist es viel besser, Elliptic-Curve-Schlüssel zu erzeugen.
    Sonst wartet man entweder lange oder opfert Sicherheit, die auch in Zukunft noch Bestand haben soll.

• Das Setzen des niedrigen Bits auf 1 verstehe ich. Gerade Zahlen sind niemals prim, natürlich mit Ausnahme von 2.
  Aber ich verstehe nicht, warum auch das hohe Bit auf 1 gesetzt wird. Ich kenne mich mit Primzahlen oder Kryptografie nicht besonders aus, aber es sieht so aus, als würde man unnötig 1 Bit Entropie aufgeben. Was übersehe ich?

  • Wenn das hohe Bit immer gesetzt ist und man die Primzahl einschließlich dieses Bits kodiert, wird die Primzahl immer mit derselben Anzahl Bytes kodiert.
    Byte-Kodierungen variabler Länge können beim Datenaustausch zwischen unterschiedlicher Software Probleme verursachen, wenn die Spezifikation nicht sehr klar und gut getestet ist.
    Siehe die Probleme bei RSA-basiertem DHE, wenn der öffentliche Serverschlüssel führende Nullen enthält.
  • Es ist wie beim Erzeugen einer zweistelligen Zahl.
    Wenn die erste Ziffer 0 ist, ist es keine zweistellige Zahl.
  • Wenn man das erste Bit auf 1 setzt, verliert man zwar 1 Bit Entropie, stellt aber sicher, dass die Primzahl groß genug ist.
    Ergänzend dazu: Bei RSA multipliziert man zwei Primzahlen. Wenn eine davon 1024 Bit hat, kann die andere, wenn ich mich richtig erinnere, etwa 200 Bit haben und trotzdem die für den Schlüssel nötige Anzahl an Entropie-Bits erreichen.
    Wenn man also beide Primzahlen auf 1024 Bit setzt, hat man sogar etwas Spielraum.
  • Ja, man gibt 1 Bit Entropie auf, aber es bleiben immer noch 1022 Bit übrig.
    Das scheint sicherer zu sein, als sich zu fragen, ob eine 1020-Bit-Primzahl auch in Ordnung ist, wenn jemand eine 1024-Bit-Primzahl verlangt hat. So wie man 00042 normalerweise nicht als fünfstellige Zahl betrachtet.
    Technisch kann die optimale Wahl davon abhängen, wofür genau sie verwendet wird, aber die Vorgehensweise im Artikel wirkt wie die sicherere Standardeinstellung.
  • Es scheint auf jeden Fall ein vernünftiger Kompromiss zu sein, 1 Bit Entropie zu verlieren, um sicherzustellen, dass man keine Primzahl erzeugt, die am Ende nur 50 Bit lang ist.