1 Einleitung

Seit dem 13. März 1997 existiert die Idee für ein Verfahren zur Erzeugung von Pseudo-Zufallszahlen, das ohne Zuhilfenahme arithmetischer Operationen auskommt. Aus diesem ursprünglichen Konzept ist eine ganze Familie nicht-arithmetischer Generatoren (naPRNGs) hervorgegangen. Alle Algorithmen sind unter die 3-Klausel-BSD-Lizenz [↑] gestellt. Im Folgenden wird der Begriff "Zufall" synonym für Pseudo-Zufall genutzt.

Für Zufallszahlen gibt es viele Einsatzgebiete (u.a. Simulation, Statistik, Kryptographie), die ebenso unterschiedliche wie vielfältige Anforderungen an die verwendeten Zahlen und deren Erzeugung stellen. Ziel dieser Webseite ist es, bisher gewonnene Erkenntnisse zusammenzutragen und für eine weitergehende Begutachtung zur Verfügung zu stellen. Es wird ausdrücklich darauf hingewiesen, dass zum jetzigen Zeitpunkt keine ausreichenden Kriterien, insbesondere theoretischer Art, vorliegen, die eine Eignung für eines der Einsatzgebiete nahelegen. Andererseits sprechen die Ergebnisse bisher durchgeführter empirischer Tests und die hohe Flexibilität des Algorithmus dafür, dass eine Veröffentlichung an dieser Stelle lohnenswert erscheint. Allerdings fallen die Periodenlängen zum Teil sehr gering aus (siehe 4.1 Perioden).

nach oben

2 Dokumentation

Alle in diesem Abschnitt getroffenen Aussagen beziehen sich auf die jeweils neueste Version. Abweichende oder ergänzende Informationen finden sich unter 3.2 Sourcecode an entsprechender Stelle.

nach oben

2.1 Algorithmus

In der Literatur zu einem Seminar über Zufallszahlen an der Technischen Universität Clausthal im Jahr 1997 wurde u.a. Algorithmus P [1] vorgestellt. Dabei finden auch Transpositionen Anwendung, die die Elemente einer Permutation schrittweise in eine aufsteigende Reihenfolge überführen. Diesen Prozess umzukehren und dabei iterativ vorzugehen, war die Kernidee, die zur Realisierung von naRND führte.

Folglich bilden Permutationen die Grundelemente von naPRNGs. Um den Zahlenraum eines Bytes abdecken zu können und somit eine fundamentale Basiseinheit von Computern zu bedienen, sieht ein erster Standardgenerator (Version V1) Permutationen der Länge 256 vor, die genau die Zahlen 0 bis 255 enthalten. In ihrer Umsetzung als Array sind diese mit sogenannten dynamischen S-Boxen [↑] vergleichbar, wie sie u.a. beim Algorithmus RC4 [↑] zur Anwendung kommen. Es werden 4 solcher S-Boxen beim Standardgenerator V1 eingesetzt. Hintergrund hierfür ist, dass in einer frühen Form der Implementierung bei jedem Schritt unter Ersparnis einiger weniger Zwischenoperationen gleich alle vier Zufallszahlen (eine pro S-Box) erzeugt wurden, die sodann zu einer 32-Bit-Zahl zusammengefasst werden konnten. Auf diese Ersparnis wurde nachfolgend zugunsten einer elementareren und damit flexibleren Handhabung verzichtet.

Ordnet man den vier S-Boxen einen eindeutigen Index von 0 bis 3 zu und jedem Element einer S-Box einen eindeutigen Index von 0 bis 255, dann sei s der aktuelle Index einer S-Box und r der aktuelle Index eines Elements in der entsprechenden S-Box. Weiterhin sei l ein zwischengespeicherter Wert. Bei jedem Schritt werden die zwei Elemente innerhalb der S-Box mit Index s vertauscht, deren Indizes r bzw. l entsprechen. Danach findet eine Neuzuweisung statt in der Form, dass l dem Element r in S-Box s entspricht und s um 1 modulo 4 erhöht wird. Ist s danach gleich 0, wird r um 1 modulo 256 erhöht. Es lässt sich ein Gesamtindex i (für Iterator) errechnen: i := r * 4 + s. Die Bezeichnung Iterator weist darauf hin, dass i bei jedem Durchlauf um 1 erhöht wird (modulo 4 * 256). Als Ausgabe dient der Wert an der neuen Position von i. Eine später entwickelte Variante, der Standardgenerator V2, unterscheidet sich von der ersten Version hinsichtlich der Neuzuweisung des Wertes von l. Beide Standardgeneratoren sind als Pseudocode dokumentiert. Der Pseudocode berücksichtigt an dieser Stelle nur eine Initialisierung per Identität, d.h. der identischen Abbildung. Mit Hilfe der Anwendung <naPRNGs - Tools> können die Zustände eines Generators visualisiert und deren Veränderung nachvollzogen werden.

Die allgemeine Notation eines naPRNG lautet <naRND [OperationMode, SubstitutionMode] [NumberOfSubstitutionBoxes, NumberOfReferences]>, wobei der Operationsmodus (OperationMode) die Werte V1 oder V2 annehmen kann und der Substitutionsmodus (SubstitutionMode) einem der Werte Strict oder Loose entspricht. NumberOfSubstitutionBoxes steht für die Anzahl der verwendeten S-Boxen (S) und NumberOfReferences für die Anzahl der Elemente bzw. Referenzen pro S-Box (R). Der Substitutionsmodus Strict zeigt an, dass jede S-Box eine Permutation der Zahlen 0 bis R-1 repräsentiert (Genotyp) und diese Zahlen auch unverändert für die Ausgabe als Zufallszahlen genutzt werden (Phänotyp). Bei der Implementierung mit verketteten Listen ist der Substitutionsmodus genau dann Strict, wenn das auszugebende Element eines Knotens dem Index r des Knotens entspricht. Beide Interpretationen sind äquivalent zueinander.

nach oben

2.2 Bibliothek

Die entsprechenden Quelldateien befinden sich im Ordner "\Libraries\naPRNGs\" und haben die Endung ".cs". Als elementar sind naRND und naTools zu betrachten, von denen alle anderen Bibliotheksklassen abhängig sind. Die Funktionalität der einzelnen Klassen ist so ausgerichtet, dass sie für die hier vorgestellten Anwendungen ausreichend ist. Selbstverständlich kann der Funktionsumfang den jeweiligen Bedürfnissen angepasst werden.

Eine weitere Klasse, die nicht zu den naPRNGs gehört, ist ARC4Test, die im Ordner "\Libraries\Other\" zu finden ist. Sie implementiert eine spezielle Version des ARC4 (alleged RC4) Algorithmus, um Vergleiche zu naRND ziehen zu können. Im Funktionsumfang ist diese Klasse naTest sehr ähnlich. die Anwendungen <naPRNGs - Period> und <naPRNGs - Tools> bieten die Möglichkeit, Periodenlängen auch für ARC4 zu berechnen bzw. einen Einblick in den Zustand der Generatoren zu erhalten.

nach oben

2.2.1 naRND

Die Klasse naRND ist generisch und stellt die grundlegenden Funktionen für die Nutzung von naPRNGs bereit. Generisch bedeutet hier, dass der Objekttyp der Ausgabe frei gewählt werden kann. Diese Klasse kann zwar nativ genutzt werden, für die meisten Anwendungen dürfte es jedoch einfacher sein, auf z.B. naPool oder naStrict zurückzugreifen. Intern ist naRND mittels einer verketteten Liste implementiert. Die Verweise auf die einzelnen Knoten werden als Referenz bezeichnet, die von den Knoten repräsentierten Werte bzw. Objekte als Elemente. Im Folgenden sind alle Parameter für die Instanziierung, d.h. die Erzeugung eines neuen Objekts der Klasse naRND, und deren Bedeutung aufgelistet:

Weitere öffentliche Funktionen sind NextState und PreviousState, die den Generator in den nächstfolgenden bzw. den vorangehenden Zustand versetzen. PreviousState ist für Generatoren vom Typ V1 nicht verfügbar, wenn dieser ausschließlich 1 S-Box umfasst. Das jeweils aktuelle Zufallsobjekt z wird durch IteratorItem repräsentiert. Mit der ebenfalls öffentlichen Funktion GatherEntropy ist es möglich, den Generator in Abhängigkeit eines übergebenen Parameters in einen neuen Zustand zu versetzen. Dies wird unter anderem bei <naPRNGs - Crypt> genutzt, um den Generator mittels Benutzereingaben (Mausbewegungen) oder anderer Entropiequellen zu initialisieren.

nach oben

2.2.2 naStrict

Wie der Name sagt, bechränkt sich naSrict auf naPRNGs im Substitutionsmodus Strict. Weiterhin ist der Ausgabetyp auf Byte festgelegt. Der Operationsmodus wird einmalig bei Erzeugung einer Instanz festgelegt. Diese Instanz entspricht zunächst immer einem der Standardgeneratoren und wird zufällig, d.h. in Abhängigkeit von naPool initialisiert. Eine so erzeugte Instanz kann bei Bedarf immer wieder neu initialisiert werden. Eine erste ausführliche Möglichkeit der Initialisierung entspricht jener bei naRND, die Parameter OperationMode und ReferencedItems entfallen. Intern wird für ReferencedItems die Identität verwendet. Eine weitere, einfachere Möglichkeit fordert die Parameter NumberOfSubstitutionBoxes für die Anzahl der zu verwendenden S-Boxen, NumberOfReferences für die Anzahl der Referenzen bzw. Elemente und InitializeByIdentity. Letzterer kann die Werte "true" annehmen, wenn der Generator mit der Identität initialisiert werden soll oder den Wert "false", wenn eine zufällige Initialisierung erfolgen soll.

Zustände des Generators können gespeichert (Save) oder wieder geladen werden (Load). Die entsprechenden Dateien haben die Endung ".nastrict". CurrentRandomValue gibt die aktuelle Zufallszahl zurück, wobei der interne Zustand des Generators nicht verändert wird. PreviousRandomValue und NextRandomValue liefern die vorangehende bzw. nachfolgende Zufallszahl. Andere Funktionen erlauben die Darstellung des internen Zustands (ToString) oder geben eine Beschreibung des Generators, d.h. dessen Notation (Description), zurück.

Wenn "sichere" Zufallszahlen zur Verfügung stehen, liefert ProvidesSecureRandom den Wert "true" und die aktuelle sichere Zufallszahl kann mit CurrentSecureValue, die darauf folgende mit NextSecureValue abgerufen werden. Sichere Zufallszahlen sind nur dann verfügbar, wenn die Anzahl der Referenzen einer Potenz von 2 entspricht. Eine solche, sichere Zufallszahl wird erzeugt, indem die aktuelle Zahl mit dem von l referenzierten Element mittels des logischen Operators XOR (Exklusiv-Oder) verknüpft wird. Damit solle sichergestellt werden, dass durch die ausgegebenen Werte keine Rückschlüsse auf den internen Zustand des Generators geschlossen werden können.

nach oben

2.2.3 napRND

Diese Klasse simuliert eine parallele Version von naPRNGs, die sich zunächst wie naStrict auf den Ausgabetyp Byte und den Substitutionsmodus Strict beschränkt. Ebenso bestehen die einzelnen, parallel geschalteten Generatoren aus jeweils nur einer S-Box. Alle Generatoren haben die gleiche Anzahl an Elementen. Der Wert für den Iterator ist bei der Initialisierung für alle Generatoren gleich, der erste Generator wird vor der ersten Benutzung in seinen Folgezustand versetzt. Erst dadurch ergibt sich – ähnlich wie zwischen der ersten Substitutionsbox innerhalb eines Generators zu allen anderen – die notwendige Abweichung, die zu einem kontrollierten Einfluss der parallelen Generatoren untereinander führt.

Über die Funktion SetLastReference (implementiert in naRND) wird der Zustand der Variable LastReference von einem Generator auf den anderen übertragen. Konsistent ist dieses Vorgehen nur für Generatoren im Operationsmodus V2, da nur hier das Element LastReference frei wählbar ist. Prinzipiell ist keine Einschränkung hinsichtlich des Substitutionsmodus, des Ausgabetyps oder auch der Anzahl der S-Boxen der parallel geschalteten Generatoren gegeben.

nach oben

2.2.4 naPool

Bei naPool handelt es sich um eine statische Klasse, d.h. vor Benutzung muss nicht erst eine Instanz erzeugt werden. Intern nutzt diese Klasse den Standardgenerator V2 und arbeitet mit Elementen vom Typ Byte. Es bestehen verschiedene Möglichkeiten der Ausgabe von Zufallszahlen. So können die unveränderten Bytes über die Funktion NextRandomByte (ohne Parameter) und mehrere Bytes gleichzeitig über NextRandomBytes unter Angabe der Anzahl der gewünschten Bytes als Parameter abgerufen werden. Auch NextRandomByte kann mit einem Parameter aufgerufen werden, dieser stellt dann die exklusive Obergrenze (UpperBound) für die gewünschten Zahlen dar. NextRandomInt32 liefert eine positive 32-Bit-Zahl mit oder ohne einer Obergrenze als Parameter.

Implementiert ist auch die Funktion GatherEntropy, die es erlaubt, den Generator über Daten von außerhalb (z.B. Mausbewegungen des Nutzers) nicht nachvollziehbar zu beeinflussen. Mit der Funktion Flush wird der bestehende Zustand von naPool in einer vordefinierten Datei (FileEntropyPool) gespeichert.

nach oben

2.2.5 naCrypt

Als Proof of Concept gedacht, sind hier ein paar Ideen zu einem kryptographischen Verfahren basierend auf naPRNGs realisiert. Es sei erneut darauf hingewiesen, dass es bisher keinen Beweis für die Tragfähigkeit und Sicherheit dieses Konzepts gibt. Neben der Vorstellung der grundlegenden Verfahrensweise von naCrypt werden im letzten Absatz weitere Überlegungen vorgestellt. Intern arbeitet naCrypt mit einem naPRNG im Operationsmodus V2 und Substitutionsmodus Strict. Der Phänotyp ist auf Byte festgelegt und umfasst alle Werte von 0 bis 255, d.h. die Anzahl der Referenzen beträgt 256. Um den Ablauf besser beschreiben zu können, werden an dieser Stelle die wichtigsten Funktionen und Variablen mitsamt einer kurzen Erklärung aufgelistet:

Mit der Funktion Encrypt werden die in Form eines Byte-Arrays übergebenen Daten (DataBlock) verschlüsselt und sodann als Byte-Array zurückgegeben. Ein zweiter Parameter namens LastDataBlock zeigt mit "true" an, ob es sich um den letzten zu verschlüsselnden Datenblock handelt, andernfalls ist dieser auf "false" zu setzen. Bis auf den letzten Datenblock müssen alle Datenblöcke die durch PlainBigDataBlock festgelegte Länge haben. Das Entschlüsseln mit Decrypt erwartet die gleichen Parameter. Die Standardlänge der Datenblöcke schreibt hierbei die Variable CryptBigDataBlock vor. Intern werden die Datenblöcke in 256 kleinere Datenblöcke zerlegt. Diese kleinen Datenblöcke werden in zufälliger Reihenfolge abgearbeitet. Die jeweils 256 Elemente (Bytes) eines kleinen Datenblocks werden wiederum in zufälliger Reihenfolge durch XOR mit einer sicheren Zufallszahl verschlüsselt.

Durch die Nutzung von sicheren Zufallszahlen, wie sie auch von der Klasse naStrict zur Verfügung gestellt werden, ist es nicht möglich, durch die Ausgabe des Generators Kenntnisse über dessen internen Zustand zu erlangen. Eine weitere, nicht angewendete Möglichkeit wäre es, vom Typ Strict abzuweichen. Wird der interne Zustand dennoch bekannt, ist es eine Bedingung des BSI [2] an kryptografisch sichere Zufallsgeneratoren, dass auch dann keine Rückschlüsse auf zuvor erzeugte Zufallszahlen gezogen werden können. Dieses Kriterium wird insofern erfüllt, als dass die Funktion GatherEntropy eingesetzt wird, die es unmöglich macht, den Prozess umzukehren und somit auf vorangehende Ausgaben zu schließen.

nach oben

2.2.6 naTest

Ähnlich wie naStrict beschränkt sich naTest auf Generatoren im Modus Strict und gibt als Phänotyp eine Zahl als Byte zurück. Diese Klasse ist speziell für die Anwendung <naPRNGs - Period> konzipiert und hält hierfür besondere Funktionalitäten bereit. So kann der interne Zustand des Generators mittels der Funktion IsIsoState (implementiert in naRND) daraufhin geprüft werden, ob alle S-Boxen ein und dieselbe Permutation repräsentieren und damit identisch sind. Ist diese Bedingungen erfüllt, liefert die Funktion "true" andernfalls "false". Mit IsEqual (ebenfalls in naRND implementiert) kann der aktuelle Generator mit einem anderen Generator der gleichen Art als übergebenem Parameter verglichen werden. Der Rückgabewert ist wiederum vom Typ Bool und kann die Werte "True" und "False" annehmen.

Unter Angabe des zu verwendenden Operationsmodus wird naTest einmalig instanziiert. Für die Initialisierung werden die Anzahl der S-Boxen (NumberOfSubstitutionBoxes), die Anzahl der Referenzen bzw. Elemente (NumberOfReferences), Werte für den Referenziterator (ReferenceIterator) und die letzte interne Referenz (LastReference) benötigt. Einen besonderen Parameter stellt IndexOfPermutation dar. Dieser bestimmt die von jeder einzelnen S-Box gleicherweise repräsentierte Permutation. Eine solche Initialisierung überführt den Generator unmittelbar in einen Isostate. Eine weitere Möglichkeit der Initialisierung erfolgt über einen String, der den Generatorzustand abbildet. Ein solcher String, also ein Zustand bzw. dessen Visualisierung, kann durch die Funktion ToString abgerufen werden. Sie bildet auch die Basis für das Speichern (Save) und Laden (Load) von Zuständen. Hintergrund hierfür ist, dass ein Zustand in einer Textdatei ausgegeben werden kann und auch für den Anwender lesbar ist. So sind gespeicherte Zustände, die Ausgabe der Anwendung <naPRNGs - Period> und die Eingabe bei <naPRNGs - Tools> kompatibel zueinander.

Neben einer Beschreibung des Generators in Form seiner Notation (Description), der aktuellen (CurrentRandomValue) und der nächsten Zufallszahl (NextRandomValue) stehen viele weitere Werte zur Verfügung, die für die Berechnung der Periodenlängen notwendig sind. Dazu zählen die einzelnen Werte, die den Zustand des Generators beschreiben sowie IndexOfPermutation. Dieser Index kann für jede S-Box unter Angabe von IndexOfSubstitutionBox als Parameter einzeln abgerufen werden. Befindet sich der Generator in einem Isostate, ist IndexOfPermutation für alle S-Boxen identisch.

nach oben

2.2.7 naTools

In dieser Klasse werden verschiedene Funktionen bereitgestellt, die hilfreich für den Umgang mit naPRNGs insbesondere vom Typ naRND<byte>, d.h. Generatoren, die als Ausgabe den Typ Byte haben, sind. Solche speziellen Funktionen, die einen Generator mit Ausgabetyp Byte erwarten, sind u.a. Load und Save. Beide erwarten neben dem Generator (naPRNG) noch einen Dateinamen (FileName) und bieten optional die Möglichkeit, zusätzliche Informationen zu laden bzw. zu speichern. Beim Laden wird hierfür die Anzahl der zu ladenden Bytes (AdditionalBytes) angegeben, beim Speichern das zu speichernde Byte-Array (AdditionalData). Weitere Funktionen, die einen Generator vom Ausgabetyp Byte erwarten sind IsStrict, Description und Visualization. IsStrict gibt "true" zurück, wenn der übergebene Generator im Substitutionsmodus Strict arbeitet, "false" sonst. Description gibt eine Beschreibung des Generators in Form der Notation aus, Visualization erzeugt eine textbasierte Visualisierung des jeweils aktuellen Generatorzustands. Die Klasse naStrict nutzt diese Funktion z.B. beim Zugriff auf ToString.

Weitere, weniger spezifische Funktionen dienen der Berechnung der Fakultät (Faculty), vergleichen zwei Arrays miteinander (IsEqual) oder testen ein Array daraufhin, ob dieses eine Permutation der Zahlen von 0 bis n-1 repräsentiert (IsPermutation), wobei n die Anzahl der Elemente im Array ist. Mit RandomPermutation lassen sich zufällige Permutationen erzeugen. Als Parameter ist die Länge der Permutation (NumberOfElements, Anzahl der Elemente) erforderlich. Optional kann ein Zufallszahlengenerator (SystemRND) übergeben werden. Wird kein solcher Systemgenerator übergeben, wird naPool genutzt. IdentityIntegers gibt ein Array vom Typ Integer zurück, dessen Elemente dem jeweiligen Index des Elements im Array entsprechen. Dies dient der Initialisierung der S-Boxen mit der Identität. Die Klasse stellt auch Funktionen für die Erzeugung und Indexierung von Permutationen zur Verfügung, die speziell bei systematischen Tests der Periodenlängen Anwendung finden.

nach oben

2.3 Anwendungen

Die Quelldateien befinden sich im Ordner "\Applications\Crypt\", "\Applications\Period\" bzw. "\Applications\Tools\". Der Name der Quelldateien ist entsprechend "FormCrypt.cs" und "FormPeriod.cs". <naPRNGs - Tools> gliedert sich in drei Programmteile auf: "FormDispatcher.cs", "FormBinaryOutput.cs" und "FormTextOutput.cs". Alle Anwendungen haben eine adaptive Benutzeroberfläche, die stets nur die jeweils sinnvollen Bedienungsmöglichkeiten anzeigt und dabei einzelne Elemente ein- oder ausblendet bzw. umbenennt. Die Abbildungen zeigen jeweils den Initialzustand einer Anwendung.

nach oben

2.3.1 naPRNGs - Crypt

Die Anwendung <naPRNGs - Crypt> ist zunächst nicht mehr als ein Projekt zur Verbesserung der eigenen Fähigkeiten im Umgang mit C# und der Umsetzung von Ideen vor diesem Hintergrund gewesen. Es handelt sich um eine konzeptionelle Software, die aufzeigen soll, welche Möglichkeiten sich in der Anwendung von naPRNGs in diesem Bereich ergeben. Da keine theoretischen Überlegungen zur kryptographischen Sicherheit von naRND vorliegen, müssen alle naPRNGs - und damit auch die genannte Anwendung - als kryptographisch nicht sicher angesehen werden. Weiterhin kann nicht garantiert werden, dass die Anwendung fehlerfrei funktioniert. Es ist daher besondere Vorsicht im Umgang mit den eigenen Daten geboten. Um ungewollten Datenverlust zu vermeiden, werden beim Entschlüsseln bereits vorhandene Dateien nicht überschrieben. Stattdessen werden die entschlüsselten Dateien mit der zusätzlichen Endung ".new" versehen.

Intern wird naCrypt, ein Generator des Typs V2, für die Ver- und Entschlüsselung genutzt. Die Anwendung stellt somit mehr oder weniger nur eine graphische Oberfläche zur Verfügung. Mehrere zu verschlüsselnde Dateien werden in einen Container mit der Endung ".nacrypt" geschrieben. Zusätzlich wird eine Datei gleichen Namens mit der Endung ".nakey" erzeugt. Diese speichert den Initialzustand des Generators und ist unabdingbar für die Entschlüsselung. Dieser Initialzustand wird über naPool erzeugt und kann durch den Benutzer beeinflusst werden. Durch einen Klick auf das Logo öffnet sich ein Fenster mit kurzen Informationen und der Frage: "Gather entropy?". Durch einen weiteren Klick auf "Ja" werden fortan die Mausbewegungen aufgezeichnet und für die Initialisierung des Generators genutzt. Mittels "Cancel" gelangt man zurück. Ein Passwort ist nicht unbedingt notwendig, kann aber zusätzlich angegeben werden. Es ist sinnvoll, die ".nakey"-Dateien getrennt von den verschlüsselten Daten aufzubewahren und diese evtl. gesammelt mit einem starken Passwort erneut zu verschlüsseln.

Zum Verschlüsseln von Dateien oder Ordnern, können diese per Drag & Drop auf die damit bezeichnete Fläche gezogen werden. Werden erneut Dateien per Drag & Drop abgelegt, ersetzen diese die zuvor erstellte Liste. Alternativ können über den Button "Open" Dateien zum Verschlüsseln ausgewählt werden. Die ausgewählten Dateien werden anschließend an entsprechender Stelle angezeigt. Der Button "Encrypt" wird jetzt verfügbar, ebenso die Auswahl zur Sicherheitsstufe ("Security"). Die Sicherheitsstufe wirkt sich dahingehend aus, wie viele S-Boxen intern genutzt werden. Auch ein Feld zur Eingabe eines optionalen Passworts ("Password") wird aktiviert. Die Option "High reliability" führt dazu, dass die verschlüsselten Daten etwas mehr als den zweifachen Festplattenspeicher belegen, dafür aber gegenüber bestimmten Dateifehlern weniger anfällig sind. Sind alle Einstellungen getroffen, wird der Vorgang über den Button "Encrypt" gestartet. Ein Verzeichnisauswahl-Dialog gibt hierbei die Möglichkeit, den Zielort zu bestimmen.

Zum Entschlüsseln von Dateien, können der entsprechende Container (".nacrypt"), die entsprechende Schlüsseldatei (".key") oder beide Dateien per Drag & Drop oder per "Open" ausgewählt werden. Werden mehrere oder nicht passende Dateien gewählt, wird nur das erneute Verschlüsseln angeboten. Andernfalls wird der Button "Decrypt" aktiv. Nach Eingabe des optionalen Passworts kann der Vorgang gestartet werden. Wird eine Datei (Container oder Schlüsseldatei) nicht gefunden, wird der Benutzer in einem Dateiauswahl-Dialog dazu aufgefordert, danach zu suchen.

Anwendung naPRNGs - Crypt

nach oben

2.3.2 naPRNGs - Period

Mit Hilfe dieser Anwendung können die Perioden- und Quasiperiodenlängen für Generatoren vom Typ V1 und V2 im Modus Strict systematisch bestimmt werden. Zusätzlich ist die Berechnung von Periodenlängen auch für den Algorithmus ARC4 in Form der Generatoren vom Typ ARC4Test möglich. Während Perioden auf der von dem zu untersuchenden Generator erzeugten Zahlenfolge nach Mustern suchen, greifen Quasiperioden auf die Differenz zwischen aufeinanderfolgenden Gliedern zurück. Als Ergebnisse werden neben den eigentlichen Periodenlängen (PeriodLength) auch der Startzustand (StartState) und der jeweils aktuelle Zustand (CurrentState) des Generators dokumentiert. PeriodDetected und QuasiDetected weisen darauf hin, ob es sich um eine konventionelle Periode oder eine Quasiperiode handelt. Zutreffendes wird hierbei mit "true" signalisiert. Auf diese Weise wird auch festgehalten, ob der Startzustand erreicht wurde (StartReached) oder ein anderer zuvor schon einmal besuchter Zustand (CollisionDetected) erneut durchlaufen wird. Im letztgenannten Fall liegt eine Kollision vor und die aktuelle Suche wird abgebrochen.

Zunächst werden die Art des Generators ("PRNG") und seine Parameter wie Anzahl der S-Boxen ("SubstBoxes") und Anzahl der Referenzen ("References") bzw. Elemente ("Elements") pro S-Box vom Benutzer festgelegt. Alternativ kann eine zuvor gespeicherte Konfiguration (".naperiod") mit "Open" geladen werden. Intern wird die Klasse naTest verwendet, die weitere benötigte Funktionen bereitstellt und den eigenen Zustand in einer für Editoren und Benutzer lesbaren Form speichert. Unter "Possibilities" wird die Anzahl aller möglichen Zustände für die gewählte Konfiguration angezeigt. Der gesamte Zustand eines Durchlaufs wird jedesmal dann gespeichert, wenn eine Unterbrechung durch den Benutzer vorgenommen wird. Nach einer Unterbrechung kann die Berechnung über "Continue" fortgeführt oder mit "Reset" zurückgesetzt werden. "Period" und "Quasi" zeigen die Anzahl der bisher gefundenen Perioden bzw. Quasiperioden an.

Wird eine ausgewählte Konfiguration neu gestartet, so wird der Generator zunächst mit der Identität initialisiert. Fortan wird nach Perioden und Quasiperioden gesucht, bis entweder eine Kollision auftritt oder der Startzustand wieder erreicht ist. Alle Isostates, die ein Generator währenddessen durchläuft, werden intern als besucht markiert. Ein Isostate sei definiert als Zustand eines naPRNG, bei dem alle S-Boxen ein und dieselbe Permutation repräsentieren. Die Identität entspricht somit ebenfalls einem Isostate. Ist die Suche nach Perioden für einen Startzustand abgeschlossen, wird der nächste (in lexikographischer Reihenfolge) freie Isostate als neuer Zustand gewählt, solange bis keine freien Startzustände mehr zur Verfügung stehen. Zwar wird ein Großteil des Zustandsraums somit abgedeckt, um jedoch verlässliche Aussagen über die zu erwartende Mindestgröße von Perioden eines bestimmten Generators treffen zu können, ist es unerlässlich, auch die übrigen Zustände zu kontrollieren. Diese Option wird über "Verbose" geboten. Die Berechnung ist dabei wesentlich langsamer und die Obergrenzen für die Anzahl an S-Boxen und Referenzen bzw. Elemente ist stärker eingeschränkt.

Generatoren des Typs V1, die mit nur 1 S-Box konfiguriert werden, sind degeneriert und kehren nicht in jedem Fall in ihren Startzustand zurück. Eine Berechnung der Periodenlängen ist an dieser Stelle nicht sinnvoll. Darauf wird auch im Infofenster hingewiesen, welches durch einen Klick auf das Logo aufgerufen werden kann. Entsprechend fehlen diese Konfigurationen in den Ergebnissen, die unter 4.1 Perioden eingesehen werden können.

Anwendung naPRNGs - Period

nach oben

2.3.3 naPRNGs - Tools

<naPRNGs - Tools> bietet die Möglichkeit, Zufallszahlen in Form einer Binärdatei auszugeben oder den internen Zustand von naPRNGs schrittweise zu verfolgen und zu beobachten. Die Auswahl eines Generators wird über "PRNG" getroffen. Es stehen neben den Generatoren vom Typ "naStrict V1" und "naStrict V2" auch Generatoren der Klasse "naTest V1", "naTest V2" und "ARC4Test" sowie "naPool" und "System" zur Verfügung. Je nach Auswahl können weitere Parameter für den Generator bestimmt werden und es besteht gegebenenfalls die Option, einen gespeicherten Zustand über "Open" zu laden. Für naStrict kann über "SubstBoxes" und "References" die Anzahl an S-Boxen und Referenzen bestimmt werden. Weiterhin steht die Option "Secure random" bereit. Für naTest kann ein Zustand ("State") manuell eingegeben werden. naPool hat wie auch der Systemgenerator die obere Schranke ("UpperBound") als einzigen Parameter.

Über das Feld "Output" wir die Form der Ausgabe festgelegt. Prinzipiell stehen hier "Binary" für die Ausgabe in eine Binärdatei unter Angabe der Dateigröße in MByte, "Text" für die Ausgabe auf den Bildschirm und "State" für die Ausgabe auf den Bildschirm inklusive einer Visualisierung des internen Zustands zur Verfügung. Die Verfügbarkeit von "State" beschränkt sich hierbei auf naStrict und naTest. Durch einen Klick auf "Start" wird der jeweilige Generator gegebenenfalls initialisiert und die gewünschte Aktion gestartet. Im Falle der Ausgabeoption "Binary" wird eine Initialisierung mit der Identität vorgenommen, andernfalls wird der Generator in einen zufälligen Anfangszustand versetzt. Während der Bildschirmausgabe kann für Generatoren vom Typ naStrict über die Leertaste ("Space") zwischen Vorwärts- und Rückwärtsmodus gewechselt werden. Eine Ausnahme bildet naStrict V1 mit nur 1 S-Box.

Wird eine Aktion abgebrochen ("Cancel"), kann diese ohne erneute Änderung des Generatorzustands mittels "Continue" fortgesetzt werden. Dabei ist es möglich, die Form der Ausgabe neu zu wählen. Mit "Reset" werden der Generator und die Anwendung zurückgesetzt. Vor Erzeugung einer Binärdatei wird in einem Dateiauswahl-Dialog der Dateiname bestimmt. Wird dieser Dialog abgebrochen, so ist naStrict bereits mit der Identität initialisiert und kann für andere Ausgabeformen genutzt werden. Für naStrict wird zusammen mit der Binärdatei auch der Generatorzustand gespeichert. Soll nur der Zustand gespeichert werden, muss "MBytes" zuvor auf 0 gesetzt werden. Diese Anmerkungen finden sich weitestgehend auch im Infofenster wieder.

Anwendung naPRNGs - Tools

nach oben

3 Downloads

Die Suite <C# naPRNGs> wurde unter Microsoft Visual Studio Express 2010, 2013 bzw. Community 2015 für Windows Desktop und Microsoft .NET Framework 4 Client Profile erstellt. Für Fragen, Meinungen und Anregungen stehe ich selbstverständlich gerne zur Verfügung. In jedem Fall würde ich mich sehr über eine kurze Rückmeldung per E-Mail freuen.

nach oben

3.1 Release

Enthält alle drei Anwendungen als ausführbare Dateien. Hierzu ist es notwendig, das Microsoft .NET Framework 4 Client Profile [↑] zu installieren, falls nicht bereits eine Version des .NET Framework 4 installiert ist. Für andere Betriebssysteme wie Mac OS X oder Linux stellt das Open Source Projekt Mono [↑] eine entsprechende Laufzeitumgebung bereit.

Stand: 24. April 2016

nach oben

3.2 Sourcecode

Enthält die neueste Version der vollständige Suite <C# naPRNGs> als Quelltext inklusive aller drei Anwendungen. Die Implementierung mittels Arrays wurde zugunsten einer insgesamt übersichtlicheren Architektur aufgegeben. Ebenfalls wurde darauf verzichtet, eine interne Repräsentation der S-Boxen abweichend von Permutationen zuzulassen. Stattdessen wird auf verkettete Listen gesetzt. In Folge davon ergibt sich eine automatische Trennung zwischen Phänotyp und Genotyp. Im Substitutionsmodus Strict sind die neue und die alte Version in Ausgabe und Erzeugung der Zufallszahlen identisch. Damit sind auch alle Testergebnisse auf beide Versionen übertragbar.

Stand: 24. April 2016

Enthält die vollständige Suite <C# naPRNGs> als Quelltext inklusive aller drei Anwendungen. Diese Version ist zum Teil noch fehlerhaft und in Teilen (z.B. naCrypt) nicht kompatibel zu der neuesten Version. Sie wird vornehmlich zu Dokumentationszwecken zur Verfügung gestellt, da sie im Wesentlichen noch auf einer Implementierung von naRND auf der Basis von Arrays beruht. Besonders hervorgehoben sei monARCH (modular non-arithmetic random architecture), mit dessen Hilfe sich ganze Strukturen von ineinandergreifenden naPRNGs aufbauen lassen. Mit refRND ist auch hier schon eine Implementierung mittels verketteter Listen realisiert.

Anmerkung1: Für den Substitutionsmodus gibt es auch hier den Wert Strict sowie abweichend den Wert Experimental. Während der Substitutionsmodus Loose nur den Phänotyp, d.h. die Ausgabe verändert, erlaubt Experimental auch einen Eingriff in den Genotyp, indem die Konfiguration für die S-Boxen nicht auf Permutationen beschränkt ist. Zwar ist eine Umsetzung des experimentellen Modus auch mit verketteten Listen möglich, es wurde jedoch darauf verzichtet.

Anmerkung2: Die Bezeichnnung für die Anzahl der verwendeten S-Boxen ist NumberOfReferences während die Anzahl der Elemente (in der neuen Version: Referenzen) NumberOfElements lautet. Der Unterschied erklärt sich dadurch, dass bei einer Realisierung mittels Arrays Phänotyp und Genotyp identisch sind. Die "Elemente" stehen für die tatsächlichen Elemente eines Arrays, das eine S-Box repräsentiert. "Referenzen" bestimmen die aktuelle S-Box, deren Elemente als Referenz auf andere Elemente interpretiert werden. "Elemente" stellen somit einerseits den Ausgabewert und andererseits eine Referenz dar. In der neuen Realisierung mit verketteten Listen bestimmen die Elemente nur die Ausgabe, während "echte" Referenzen von einem Knoten der Liste auf einen anderen Knoten verweisen und somit den eigentlichen Generator abbilden.

Errata: Die unterschiedlichen Operationsmodi sind noch mit Irreversible und Reversible bezeichnet. Beim Erstellen dieser Website wurden die Generatoren vom Typ V1 am 10. August 2014 erneut daraufhin geprüft, ob sie tatsächlich irreversibel sind. Dem ist nicht so. Entsprechend wurden die Bezeichnungen in der neuesten Version geändert in V1 und V2 mit Bezug auf den jeweiligen Zeitpunkt ihrer Entstehung.

Stand: 30. Oktober 2013

nach oben

3.3 Binärdaten

Erzeugt eine Binärdatei mit dem Standardgenerator V2 und stellt diese anschließend zum Download zur Verfügung.

Dateigröße: MByte

nach oben

4 Tests

Hier werden Testergebnisse vorgestellt. Hierzu zählen Ergebnisse zu den Perioden- und Quasiperiodenlängen sowie Ergebnisse des Diehard Tests [3]. Die Durchführung anderer Tests wie Dieharder [4], NIST Statistical Test Suite [5] oder TestU01 [6] steht noch aus.

nach oben

4.1 Perioden

Mit der Anwendung <naPRNGs - Period> berechnete Perioden- und Quasiperiodenlängen. Während Perioden auf der erzeugten Zahlenfolge nach Mustern suchen, greifen Quasiperioden auf die Differenz zwischen aufeinanderfolgenden Gliedern zurück. Neben den eigentlichen Periodenlängen sind auch der Startzustand und der jeweils aktuelle Zustand des Generators dokumentiert. Mit <naPRNGs - Tools> können diese Zustände einer näheren Betrachtung unterzogen werden.

Anmerkung: Auffällig ist, dass sich die Periodenlängen eines Generators in ihrer Größe teilweise sehr stark unterscheiden. Dabei nehmen sie im schlechtesten Fall Werte in der Größenordnung der Anzahl der verwendeten S-Boxen an, was nicht akzeptabel ist. Auf diesen Umstand, bzw. das Erkennen und Verhindern des selben, konzentrieren sich die aktuellen Überlegungen. In einem ersten Schritt wurden die Ergebnisse zu den jeweils kleinsten Perioden systematisch aufgelistet.

Stand: 08. Juni 2016

Zum Vergleich stehen hier die Ergebnisse für ARC4, alleged RC4, zum Download bereit. Festzustellen ist, dass auch dieser Generator sehr viele kleine Perioden aufweist.

Stand: 01. März 2016

nach oben

4.2 Diehard

Die hier bereitgestellten Testergebnisse beziehen sich allesamt auf den Standardgenerator V1 bzw. V2. Initialisiert mit der Identität werden jeweils 10 Tests mit je 10 MByte an aufeinander folgenden Datenpaketen durchgeführt. Die Startzustände sind mit den Testergebnissen zusammen dokumentiert. Für die ersten 10 MByte des Standardgenerators V2 bricht das Programm Diehard mit einer Fehlermeldung ab. Generell sind die ersten KByte, die nach Initialisierung mit der Identität erzeugt werden, nicht sonderlich zufällig.

Stand: 24. Februar 2014

nach oben

4.3 Ausblick

Eine wichtige Quelle zur Sicherheit von Generatoren, die auf Arrays und modularer Addition beruhen ist: "On the (In)security of Stream Ciphers Based on Arrays and Modular Addition" [7]. naRND verzichtet zwar auf die modulare Addition und nutzt mehrere Arrays, die Parallelen sind aber offensichtlich. Neue Erkenntnisse, die sich aus der Studie dieser Quelle ergeben, werden hier veröffentlicht.

nach oben

5 Literatur

nach oben

Disclaimer

Diese Website enthält Verknüpfungen zu Websites Dritter ("externe Links"). Diese Websites unterliegen der Haftung der jeweiligen Betreiber. Der Anbieter hat bei der erstmaligen Verknüpfung der externen Links die fremden Inhalte daraufhin überprüft, ob etwaige Rechtsverstöße bestehen. Zu dem Zeitpunkt waren keine Rechtsverstöße ersichtlich. Der Anbieter hat keinerlei Einfluss auf die aktuelle und zukünftige Gestaltung und auf die Inhalte der verknüpften Seiten. Das Setzen von externen Links bedeutet nicht, dass sich der Anbieter die hinter dem Verweis oder Link liegenden Inhalte zu Eigen macht. Eine ständige Kontrolle der externen Links ist für den Anbieter ohne konkrete Hinweise auf Rechtsverstöße nicht zumutbar. Bei Kenntnis von Rechtsverstößen werden jedoch derartige externe Links unverzüglich gelöscht.

Quelle: Disclaimer von Juraforum.de

nach oben