Vor sechs Monaten wollte ich den besten Pseudozufallszahlengenerator (PRNG) mit einer ungewöhnlichen Architektur erstellen. Ich dachte, der Anfang wäre einfach, und während Sie arbeiten, wird die Aufgabe langsam komplexer. Und ich dachte, ich könnte alles schnell genug lernen, um mit den schwierigsten fertig zu werden.Zu meiner Überraschung nahm die Komplexität nicht linear zu. Das Testen von Chi-Quadrat-Bytes erwies sich als sehr schwierig! Später war es genauso schwierig, eingefleischte Tests zu bestehen. Ich habe die aktuellen Ergebnisse veröffentlicht, um zu verstehen, welche anderen Schwierigkeiten auf mich warten. Der PractRand-Test schlug jedoch zu diesem Zeitpunkt fehl .Dann war es sehr schwierig, den BigCrush-Test zu bestehen .Dann war es sehr schwierig, 32 Terabyte Daten zu übertragen, wenn PractRand übergeben wurde. Geschwindigkeit ist ein Problem geworden. Es reichte nicht aus, ein Design zu erstellen, das zehn Megabyte pro Sekunde generiert, da das Bestehen von PractRand einen Monat dauern würde. Aber ich muss zugeben, dass es sehr schwierig war, diesen Test mit einer Geschwindigkeit von Gigabyte pro Sekunde zu bestehen .Wenn Sie sich zu einer solchen Höhe erheben ... möchten Sie wissen, ob Sie die Grenze zu Pareto erreichen können. Sie möchten das schnellste PRNG der Welt erstellen, das die komplexesten statistischen Tests besteht.Ich hatte Erfolg.In einem früheren Artikel habe ich darüber gesprochen, was ich gelernt habe, um mein Ziel zu erreichen. Und hier werde ich Ihnen erzählen, wie die endgültige Architektur funktioniert.Zweck
Beginnen wir mit dem Offensichtlichen: Die Geschwindigkeit hängt von der Plattform ab . Ich habe mich auf die Optimierung für die moderne x86-64-Architektur (Intel- und AMD-Prozessoren) konzentriert.Um die Leistung zu vergleichen, wird die klassische cpb- Metrik verwendet : Dies ist die Anzahl der Prozessorzyklen, die zum Generieren eines Bytes aufgewendet werden. Diese Metrik wird in allen kryptografischen Werken berechnet und verglichen . Ein etwas niedrigeres cpb in der Welt der Software oder Hardware kann den Sieg im Wettbewerb oder die Verwendung auf Websites auf der ganzen Welt sicherstellen.Um cpb zu verbessern, können Sie:- Generieren Sie mehr Bytes mit dem gleichen Arbeitsaufwand.
- Oder machen Sie weniger Arbeit, um die gleiche Anzahl von Bytes zu generieren.
- Oder parallelisieren Sie die Arbeit.
Wir werden all das tun.Nach dem ersten Punkt müssen wir bei jeder Iteration mehr Bits erzeugen.Ich hatte Angst, dass sie mir sagen würden: "Wenn es keine 32-Bit-Zahlen ausgibt, dann ist dies nicht das PRSP" oder dasselbe mit 64-Bit-Zahlen. Oder: "Das PRNG sollte nur für die x86-64-Architektur gelten", als ob Anweisungen wie POPCNT oder Register wie% xmm7 verboten wären.Das PRNG ist jedoch ein Engineering: Generatoren versuchen seit mehreren Jahrzehnten, alles Mögliche aus den Prozessoren herauszuholen! Als ROL auftauchte, begannen sie sich auf ihn zu verlassen. Mit dem Aufkommen von 64-Bit-Prozessoren begannen sie, sich auf% rax zu verlassen. Natürlich können solche Algorithmen auf ARM langsamer arbeiten (obwohl dies noch abzuwarten ist), jedoch wurden 64-Bit-PRNs aktiv verwendet, noch bevor Android 2019 Unterstützung für 64-Bit benötigte!Das heißt, dieser Bereich entwickelt sich zusammen mit der Hardware. Und heute unterstützen Intel- und AMD-Prozessoren aufgrund von AVX2 bereits 256-Bit-Operationen. RC4 produzierte 1 Byte, drand48 konnte 4 Bytes gleichzeitig produzieren, pcg64 - 8 Bytes, und jetzt können wir sofort 32 Bytes erzeugen.8 Bytes können eine 64-Bit-Zahl sein, und die meisten Programmiersprachen verfügen über integrierte Typen. Nur wenige Sprachen bieten Typen für 16 Byte (eine bemerkenswerte Ausnahme ist __uint128_t in C). Noch weniger Sprachen haben einen Typ für 32 Bytes (außer intern).Wir können uns also vom üblichen Prototyp der PRNG-Funktion verabschieden (Beispiel aus dem Vigny HWD- Benchmark ):static uint64_t next(void);
Stattdessen können Sie einen Generator erstellen, der den Puffer füllt (Beispiel aus meinem Benchmark ):void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size);
Was sind die Nachteile dieser Lösung?Wenn Ihr Generator jeweils 32 Bytes erzeugt, muss der Consumer ein Array bereitstellen, das ein Vielfaches von 32 ist (idealerweise auf 32 Bytes ausgerichtet). Obwohl Sie darauf verzichten können, füllen wir nur den Puffer. Wir werden nicht verwendete Daten daraus entfernen und bei Bedarf erneut ausfüllen. Die Verzögerung wird unvorhersehbar: Einige Aufrufe lesen nur den Puffer. Aber im Durchschnitt wird alles gleich sein.Jetzt generieren wir mehr Bytes und erledigen den gleichen Arbeitsaufwand. Wie parallelisieren wir es?Parallelität
Prozessoren bieten eine unglaubliche Reihe von Parallelisierungswerkzeugen auf allen Ebenen.Erstens sind dies SIMD-Anweisungen (Einzelanweisung, mehrere Daten). Beispielsweise führt AVX2 gleichzeitig vier 64-Bit-Ergänzungen oder acht 32-Bit-Ergänzungen usw. durch.Es wird seit etwa fünfzehn Jahren in der Kryptographie verwendet. Parallelität lieferte die unglaubliche Leistung des ChaCha20 . Es wird von den wichtigsten Grundelementen verwendet, die kein AESNI verwenden. Zum Beispiel sind NORX und Gimli auf Parallelität ausgelegt.In letzter Zeit hat das Interesse an diesem Thema auch in der nicht kryptografischen PRNG-Community zugenommen. Insbesondere vorhandene Grundelemente, die nicht für SIMD entwickelt wurden, können die Grundlage für die Erstellung sehr schneller PRNs sein.Als Sebastiano Vigna seine xoshiro256 ++ - Architektur in der Julia-Standardbibliothek bewarb , stellte er fest, dass die Ergebnisse von acht wettbewerbsfähigen, unterschiedlich initialisierten PRNG-Instanzen sehr schnell verkettet werden können, wenn jede Operation gleichzeitig in allen PRNRs ausgeführt wird.SIMD ist nur eine der Parallelisierungsebenen im Prozessor. Ich empfehle, den vorherigen Artikel zu diesem Thema zu lesen , um eine bessere Vorstellung zu haben, aber ich werde einige Erklärungen geben.Prozessor-Pipelines ermöglichen die Verarbeitung mehrerer Anweisungen in verschiedenen Phasen. Wenn die Reihenfolge ihrer Ausführung gut organisiert ist, um die Abhängigkeiten zwischen den Stufen zu verringern, kann die Verarbeitung von Anweisungen beschleunigt werden.Mit der superskalaren Ausführung können Sie die Computerteile der Anweisungen gleichzeitig verarbeiten. Dafür sollten sie jedoch keine Lese- / Schreibabhängigkeiten haben. Sie können die Architektur anpassen, um das Risiko von Ausfallzeiten zu verringern, indem Sie lange vor dem Lesen aufzeichnen.Die außergewöhnliche Ausführung ermöglicht es dem Prozessor, Anweisungen nicht in der Reihenfolge ihrer Reihenfolge auszuführen, sondern sobald sie bereit sind, selbst wenn die vorherigen Anweisungen noch nicht bereit sind. Dafür sollte es jedoch keine Lese- / Schreibabhängigkeit geben.Und jetzt gehen wir zur Umsetzung über!Die Architektur
Betrachten Sie ein Schema namens Semi-SHISHUA. Woher ein solcher Name kommt, wird beim Lesen allmählich deutlich.Das Schema sieht folgendermaßen aus:Betrachten Sie seine Zeile für Zeile.typedef struct prng_state {
__m256i state[2];
__m256i output;
__m256i counter;
} prng_state;
Der Zustand ist in zwei Teile unterteilt, die im AVX2-Register abgelegt sind (256 Bit). Um die Geschwindigkeit zu erhöhen, halten wir das Ergebnis nahe am Staat selbst, aber es ist nicht Teil des Staates.Wir haben auch einen 64-Bit-Zähler. Um die Berechnung zu vereinfachen, handelt es sich auch um ein AVX2-Register. Tatsache ist, dass AVX2 eine kleine Funktion hat: Normale Register (% rax und dergleichen) können nicht direkt über MOV auf SIMD übertragen werden, sie müssen durch RAM (meistens durch den Stapel) geleitet werden, was die Verzögerung erhöht und zwei Prozessoranweisungen kostet (MOV auf dem Stapel, VMOV vom Stapel).Nun schauen wir uns die Generation an. Beginnen wir mit dem Laden, gehen wir dann durch den Puffer und füllen ihn bei jeder Iteration mit 32 Bytes.inline void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size) {
__m256i s0 = s->state[0], counter = s->counter,
s1 = s->state[1], o = s->output;
for (__uint64_t i = 0; i < size; i += 4) {
_mm256_storeu_si256((__m256i*)&buf[i], o);
// …
}
s->state[0] = s0; s->counter = counter;
s->state[1] = s1; s->output = o;
}
Da die Funktion inline ist, kann der Prozessor durch sofortiges Füllen des Puffers beim Start die Anweisungen in Abhängigkeit davon durch einen außergewöhnlichen Ausführungsmechanismus sofort ausführen.Innerhalb der Schleife führen wir schnell drei Zustandsoperationen aus:- SHI ft
- SHU ffle
- A dd
Daher der Name SHISHUA!Erste Schicht
u0 = _mm256_srli_epi64(s0, 1); u1 = _mm256_srli_epi64(s1, 3);
Leider unterstützt der AVX2 keine Drehzahl. Aber ich möchte die Bits einer Position in einer 64-Bit-Zahl mit den Bits einer anderen Position mischen! Und Verschiebung ist der beste Weg, dies zu realisieren. Wir werden um eine ungerade Zahl verschieben, so dass jedes Bit alle 64-Bit-Positionen besucht und nicht die Hälfte davon.Während der Verschiebung gehen Bits verloren, was zur Entfernung von Informationen aus unserem Zustand führt. Das ist schlecht, Sie müssen Verluste minimieren. Die kleinsten ungeraden Zahlen sind 1 und 3. Wir werden unterschiedliche Verschiebungswerte verwenden, um die Diskrepanz zwischen den beiden Teilen zu erhöhen. Dies wird dazu beitragen, die Ähnlichkeit ihrer Selbstkorrelation zu verringern.Wir werden nach rechts verschieben, da die am weitesten rechts liegenden Bits während der Addition die geringste Diffusion aufweisen: Beispielsweise ist das niedrigstwertige Bit in A + B nur das XOR der niedrigstwertigen Bits A und B.Rühren
t0 = _mm256_permutevar8x32_epi32(s0, shu0); t1 = _mm256_permutevar8x32_epi32(s1, shu1);
Wir werden 32-Bit-Mixing verwenden, da es eine andere Granularität bietet als die 64-Bit-Operationen, die wir überall verwenden (die 64-Bit-Ausrichtung wird verletzt). Es kann sich auch um eine spurübergreifende Operation handeln: Andere Mischvorgänge können Bits innerhalb der linken 128 Bits verschieben, wenn sie links beginnen, oder innerhalb der rechten 128 Bits, wenn sie rechts beginnen.Mischkonstanten:__m256i shu0 = _mm256_set_epi32(4, 3, 2, 1, 0, 7, 6, 5),
shu1 = _mm256_set_epi32(2, 1, 0, 7, 6, 5, 4, 3);
Damit das Mischen das Ergebnis wirklich verbessert, verschieben wir die schwachen 32-Bit-Teile (mit geringer Streuung) von 64-Bit-Additionen an starke Positionen, damit die nächsten Additionen sie bereichern.Der Low-End-32-Bit-Teil des 64-Bit-Blocks bewegt sich niemals zum gleichen 64-Bit-Block wie der höherwertige Teil. Somit bleiben beide Teile nicht im selben Block, was das Mischen verbessert.Am Ende durchläuft jeder 32-Bit-Teil alle Positionen in einem Kreis: von A nach B, von B nach C, ... von H nach A.Sie haben vielleicht bemerkt, dass das einfachste Mischen, das all diese Anforderungen berücksichtigt, zwei 256-Bit-Teile sind Umsatz (Umdrehungen von 96 Bit bzw. 160 Bit nach rechts).Zusatz
Fügen wir 64-Bit-Chunks aus zwei temporären Variablen hinzu - Shift und Mixing.s0 = _mm256_add_epi64(t0, u0); s1 = _mm256_add_epi64(t1, u1);
Die Addition ist die Hauptquelle der Dispersion: Bei dieser Operation werden Bits zu irreduziblen Kombinationen von XOR- und AND-Ausdrücken kombiniert, die über 64-Bit-Positionen verteilt sind.Durch Speichern des Additionsergebnisses in einem Zustand bleibt diese Dispersion dauerhaft erhalten.Ausgabefunktion
Woher bekommen wir die Ausgabe?Es ist ganz einfach: Die von uns erstellte Struktur ermöglicht es uns, zwei unabhängige Teile des Zustands s0 und s1 zu generieren, die sich in keiner Weise gegenseitig beeinflussen. Wenden Sie XOR auf sie an und erhalten Sie ein völlig zufälliges Ergebnis.Um die Unabhängigkeit zwischen den Daten zu stärken, auf die wir XOR anwenden, nehmen wir ein Teilergebnis: den verschobenen Teil eines Zustands und den gemischten Teil eines anderen.o = _mm256_xor_si256(u0, t1);
Dies ähnelt dem Reduzieren der Lese- / Schreibabhängigkeiten zwischen Befehlen in einem superskalaren Prozessor, als ob u0 und t1 bereit wären, in s0 und s1 zu lesen.Besprechen Sie nun den Zähler. Wir verarbeiten es zu Beginn des Zyklus. Ändern Sie zuerst den Status und erhöhen Sie dann den Zählerwert:s1 = _mm256_add_epi64(s1, counter);
counter = _mm256_add_epi64(counter, increment);
Warum ändern wir zuerst den Status und aktualisieren dann den Zähler? Wenn s1 früher verfügbar wird, verringert sich die Wahrscheinlichkeit, dass nachfolgende Anweisungen, die es lesen, in der Prozessor-Pipeline gestoppt werden. Diese Sequenz hilft auch, die direkte Abhängigkeit des Lese- / Schreibzählers zu vermeiden.Wir wenden den Zähler auf s1 und nicht auf s0 an, da beide ohnehin die Ausgabe beeinflussen. S1 verliert jedoch aufgrund der Verschiebung mehr Bits, so dass es ihm hilft, nach der Verschiebung „auf die Beine zu kommen“.Der Zähler zeichnet den PractRand-Test möglicherweise nicht auf. Ihr einziger Zweck besteht darin, eine Untergrenze von 2 69 festzulegenBytes = 512 Exbibytes für die PRNG-Periode: Wir beginnen den Zyklus erst nach einem Jahrtausend Arbeit mit einer Geschwindigkeit von 10 Gibytes pro Sekunde zu wiederholen. Es ist unwahrscheinlich, dass es in den kommenden Jahrhunderten für den praktischen Gebrauch zu langsam sein wird.Zuwachs:__m256i increment = _mm256_set_epi64x(1, 3, 5, 7);
Die ungeraden Zahlen werden als Inkremente gewählt, da nur die grundlegenden Coprime-Zahlen den gesamten Zyklus des endlichen Feldes GF (2 64 ) abdecken und alle ungeraden Zahlen Coprime für 2 sind. Mit anderen Worten, wenn Sie um eine gerade ganze Zahl im Bereich von 0 bis inkrementieren 4, die nach 4 auf 0 zurückkehrt, ergibt die Sequenz 0-2-0-2- ..., die niemals zu 1 oder 3 führt. Und das ungerade Inkrement durchläuft alle ganzen Zahlen.Für alle 64-Bit-Zahlen im Status werden unterschiedliche ungerade Zahlen verwendet, wodurch sie weiter voneinander getrennt werden und die Mischung leicht erhöht wird. Ich habe die kleinsten ungeraden Zahlen gewählt, damit sie nicht magisch aussehen.So funktionieren Zustandsübergang und Ausgabefunktion. Wie initialisiere ich sie?Initialisierung
Wir initialisieren den Zustand mit den hexadezimalen Ziffern Φ, der irrationalen Zahl, die durch den Bruch am wenigsten angenähert wird.static __uint64_t phi[8] = {
0x9E3779B97F4A7C15, 0xF39CC0605CEDC834, 0x1082276BF3A27251, 0xF86C6A11D0C18E95,
0x2767F0B153D27B7F, 0x0347045B5BF1827F, 0x01886F0928403002, 0xC1D64BA40F335E36,
};
Nehmen Sie einen 256-Bit-Startwert. Dies geschieht häufig in der Kryptographie und schadet der Arbeit nicht kryptografischer PRNGs nicht:prng_state prng_init(SEEDTYPE seed[4]) {
prng_state s;
// …
return s;
}
Wir wollen nicht den gesamten Teil des Staates (s0 oder s1) mit dieser Anfangszahl neu definieren, wir müssen nur die Hälfte beeinflussen. Auf diese Weise vermeiden wir die Verwendung der Dämpfung von Anfangszahlen, die versehentlich oder absichtlich zu einem bekannten schwachen Anfangszustand führen.Da wir nicht die Hälfte jedes Zustands ändern, behalten wir die Kontrolle über 128 Statusbits. Eine solche Entropie reicht aus, um eine starke Position einzunehmen und aufrechtzuerhalten.s.state[0] = _mm256_set_epi64x(phi[3], phi[2] ^ seed[1], phi[1], phi[0] ^ seed[0]);
s.state[1] = _mm256_set_epi64x(phi[7], phi[6] ^ seed[3], phi[5], phi[4] ^ seed[2]);
Dann wiederholen wir ( ROUNDS) mehrmals die folgende Sequenz:- Führen Sie die Schritte (
STEPS) der SHISHUA-Iterationen aus. - Wir weisen einen Teil des Zustands einem anderen Zustand und den anderen Teil der Ausgabe zu.
for (char i = 0; i < ROUNDS; i++) {
prng_gen(&s, buf, 4 * STEPS);
s.state[0] = s.state[1];
s.state[1] = s.output;
}
Das Zuweisen eines Ausgabeergebnisses erhöht die Zustandsstreuung. Während der Initialisierung spielt die zusätzliche Arbeit und Korrelation von Zuständen keine Rolle, da diese Reihe von Operationen einmal ausgeführt wird. Wir sind nur an der Dispersion während der Initialisierung interessiert.Nachdem ich die Auswirkung auf die Korrelation der Anfangswerte bewertet hatte, wählte ich STEPS2 für den Wert und ROUNDS10 für 10. Ich berechnete die Korrelation durch Berechnung der „ungewöhnlichen“ und „verdächtigen“ Anomalien, die sich aus dem PRNG-Qualitätskontrollwerkzeug in PractRand ergeben.Performance
Es ist aus mehreren Gründen schwierig, die Geschwindigkeit zu messen:- Die Taktmessung ist möglicherweise nicht genau genug.
- , , - , -, .
- , . .
- : , .
Ich verwende den RDTSC-Prozessorbefehl, der die Anzahl der Zyklen berechnet.Damit jeder meine Ergebnisse reproduzieren kann, verwende ich eine Cloud-basierte virtuelle Maschine. Dies ändert nichts an der Höhe der Benchmark-Ergebnisse im Vergleich zu lokalen Tests. Außerdem müssen Sie nicht denselben Computer wie meinen kaufen. Schließlich gibt es viele Situationen, in denen das PRNG in den Clouds gestartet wird.Ich habe mich für Google Cloud Platform N2 (Intel-Prozessor) und N2D (AMD-Prozessor) entschieden. Der Vorteil von GCP ist, dass sie Server mit Prozessoren beider Hersteller anbieten. In diesem Artikel konzentrieren wir uns auf Intel, aber für AMD werden die Ergebnisse in derselben Reihenfolge angezeigt.Um tiefer in das Thema einzutauchen, entfernen wir zunächst den alten kryptografischen RC4-Generator. Ich konnte die Arbeit nicht parallelisieren7,5 cpb (Zyklen pro erzeugtem Byte).Lassen Sie uns nun ein sehr beliebtes und schnelles MCG ausführen : Das einfachste Lehmer128 PRNG , das den BigCrush-Test besteht, zeigte 0,5 cpb . Wow großartig!Dann werden wir die neueste Entwicklung ausführen, die für schnelle Hash-Tabellen verwendet wird - Wyrand . 0,41 cpb , etwas besser!Einige PRSPs bestehen den 32-Terabyte-PractRand-Test nicht, arbeiten jedoch sehr schnell. Xoshiro256 + erreichte nur 512 Mebibyte, zeigte jedoch eine sehr hohe Geschwindigkeit: 0,34 cpb .Eine weitere Neuentwicklung von RomuTrio . Sie behauptet, das schnellste PRNG der Welt zu sein - 0,31 cpb.Okay, das ist genug. Was hat Semi-SHISHUA gezeigt?0,14 cpb . Zweimal so schnell wie RomuTrio.Cool. Testen Sie nun den kryptografischen Generator ChaCha8. Er erreichte ... 0,12 cpb .Oh.SIMD ist echte Magie!Für die kryptografische Gemeinschaft war dies keine besondere Überraschung . ChaCha8 ist extrem einfach zu parallelisieren. Dies ist nur ein gut gehashter Zähler in einem diffusen Zustand.Und erinnern Sie sich, wie das Julia-Sprachteam versucht hat, mehrere Instanzen der Vigny-Architektur zu kombinieren, um einen schnellen SIMD-basierten PRCH zu erstellen? Schauen wir uns das Ergebnis mit dieser Technik an ( 8 Teile Xoshiro256 + ). 0,09 cpb !Technisch könnte mein Laptop die Ergebnisse beeinflussen. Ich bin mir nicht sicher, warum die Teamentwicklung von Julia in GCP schneller als ChaCha8 ist, aber langsamer, wenn sie lokal getestet wird. Auf meiner Maschine läuft semi-SHISHUA schneller als die Julia-Teamentwicklung, aber langsamer als ChaCha8.Es ist notwendig, alle Konkurrenten zu besiegen.Sie fragen sich wahrscheinlich schon, warum wir die vorherige Version des Semi-SHISHUA-Generators aufgerufen haben? Weil es sich als einfach herausstellte, die Geschwindigkeit zu verdoppeln, wenn Sie zwei Kopien von Semi-SHISHUA ausführen.Ähnlich wie bei der Idee des Julia-Befehls initialisieren wir zwei PRNGs (vier Blöcke mit einem 256-Bit-Zustand) separat und liefern abwechselnd die Ausgabe ihrer Arbeit.Wenn wir jedoch mehr Zustände erstellen, können wir noch mehr Daten erzeugen, indem wir vier Zustände paarweise kombinieren:o0 = _mm256_xor_si256(u0, t1);
o1 = _mm256_xor_si256(u2, t3);
o2 = _mm256_xor_si256(s0, s3);
o3 = _mm256_xor_si256(s2, s1);
Also haben wir SHISHUA bekommen, das eine Geschwindigkeit von 0,06 cpb zeigte .Dies ist doppelt so schnell wie der bisher schnellste Konkurrent der Welt, der den 32-Terabyte-PractRand-Test bestanden hat. Das Ergebnis ist in der Grafik dargestellt.Ich glaube, dass sich die Entwicklung als wettbewerbsfähig herausgestellt hat. Auf meinem Laptop funktioniert es sogar noch schneller - 0,03 cpb, aber ich werde meine Grundsätze bezüglich des Benchmarks einhalten.Hoffentlich bleibt mein Generator noch ein paar Wochen auf dem Podium der schnellsten der Welt (bitte tun Sie dies).Qualität
Der Generator besteht ehrlich BigCrush und den 32-Terabyte-PractRand-Test. Und das alles dank vier Ausgangsströmen.Zu den Nachteilen der Architektur gehört ihre Irreversibilität . Dies kann durch Reduzieren auf einen 4-Bit-Zustand mit s0 = [a, b]und gesehen werden s1 = [c, d]. Mit einer Schicht bekommen wir [0, a]und [0, d]und mit Rühren [b, c]und [d, a]. Neu s0gleich [b, c] + [0, a] = [b⊕(a∧c), a⊕c], aber s1gleich [d, a] + [0, c] = [d⊕(a∧c), a⊕c]. Wenn a = ¬c, dann a⊕c = 1und a∧c = 0deshalb s0 = [b, 1]und s1 = [d, 1]. Das heißt, wir erhalten zwei Kombinationen von aund c, die uns den gleichen Endzustand geben.In unserem Fall ist dies kein Problem, da der 64-Bit-Zähler ebenfalls Teil des Status ist. Es ergibt sich der Mindestzyklus von 2 71Bytes (128 Bytes pro Zustandsübergang) mit einer Geschwindigkeit von 10 Gibytes / Sek. wird siebentausend Jahre dauern. Dies gleicht die verlorenen Zustände aus.Zusätzlich beträgt die durchschnittliche Übergangszeit zwischen Zuständen trotz Irreversibilität 2 ^ ((256 + 1) ÷ 2). Dies ergibt einen durchschnittlichen Zyklus von 2.135 Bytes (mit einer Geschwindigkeit von 10 Gibytes / Sek. Es wird mehr als eine Billion Mal länger dauern, als das Universum existiert). Obwohl ich glaube, dass mittlere Zyklen überschätzt werden, weil sie uns nichts über die Qualität des Generators sagen.Hier sind die Benchmark-Ergebnisse:- Leistung : Die Anzahl der Prozessorzyklen, die für ein generiertes Byte aufgewendet wurden. Auf den Cloud-Maschinen N2 GCP und N2D (AMD) empfangen, ist die Reihenfolge dieselbe.
- Qualität : Die Stufe, bei der der Generator den PractRand-Test nicht besteht. Wenn dies nicht fehlschlägt, gibt es ein> -Zeichen. Wenn das Ergebnis nicht bewiesen ist, gibt es ein Fragezeichen.
- Korrelation der Startnummern: PractRand-Durchquerung mit abwechselnden Bytes von acht Streams mit den Startnummern 0, 1, 2, 4, 8, 16, 32, 64. Wir verwenden PractRand mit doppelter Faltung und erweiterten Tests.
Des Weiteren
Obwohl es in unserem Fall keine Probleme mit der Irreversibilität gibt, können wir SHISHUA dennoch verbessern.Meiner Meinung nach hat das ideale PRNG die folgenden Eigenschaften:- , 21024. 10 /. 10282 , . «» ( ). , . , 128- NEON ARM? , , .
- . , SHISHUA XOR . , .
- , 2128 ( ). SHISHUA, , . , ( ) (, , . 2).
- Die Zustandsinitialisierung ist perfekt verteilt : Alle Bits der Anfangszahl wirken sich mit derselben Wahrscheinlichkeit auf alle Bits des Zustands aus. Ich möchte es in Bezug auf SHISHUA herausfinden.
Eines der Probleme, die die Entwicklung von PRNGs und der Kryptographie insgesamt behindern, ist das Fehlen besserer Allzweckwerkzeuge. Ich benötige ein Tool, mit dem ich sofort das genaue Messergebnis erhalten kann, damit ich verschiedene Architekturen im laufenden Betrieb vergleichen kann.PractRand ist jedoch großartig im Vergleich zu früher:- Es erlaubt keine Bewertung hochwertiger Generatoren, so dass es unmöglich ist, sie miteinander zu vergleichen. Wir müssen sagen: "Nun, nach 32 Terabyte haben sie keine Anomalien ..."
- Es dauert Wochen, um es auszuführen ...
Ich hoffe, dass sich die Situation bald erheblich verbessern wird.