Prime Root Hash

Prime Root Hash ist ein kryptographisches Hash-Verfahren. Damit können sichere Fingerabdrücke zum Speichern und Vergleichen von Passwörtern erzeugt werden, zum Kodieren von Zugängen und weitere Absicherungen.

Prime Root Hash ist Bestandteil der Design-Utils und im Intersult Maven Repository erhältlich.

Hintergrund#

Mit Java werden zwar einige Verschlüsselungsverfahren ausgeliefert, bei kryptographischen Hash-Verfahren sieht es allerdings dünn aus. Im Gegensatz zu einfachen Hash-Verfahren, wie sie oft bei der Methode hashCode verwendet werden, liegt der kryptographische Anteil in der sogenannten Trapdoor-Eigenschaft.

Trapdoor-Funktionen sind mathematisch in eine Richtung einfach zu berechnen, in die andere Richtung allerdings schwierig. Prime Roots, also Primitivwurzeln basieren auf der Schwierigkeit, einen Logarithmus aus einer großen Zahl zu ziehen.

Die komfortable Crypt-Klasse erzeugt dabei wieder eine Zeichenkette, die für URLs, Dateinamen und Passwörter verwendet werden kann. Dabei kommen die Zeichen com.intersult.util.string.StringUtils.DISTINGUISHABLE zum Einsatz. Dabei handelt es sich um eine Auswahl von Zeichen, die auch bei manueller Eingabe leicht zu unterscheiden sind.

Anwendung#

Der einfache Weg ist der Einstieg über die Klasse com.intersult.util.Crypt. Diese enthält alles, was für die Codierung von Passwörtern und Hashed benötigt wird:
Crypt crypt = new Crypt("some-key");
String hash = crypt.hash("some-password-to-encrypt");
boolean equal = hash.equals(crypt.hash(someUserEnteredPassword));

Erklärung:

  1. Die Klasse Crypt wird mit einem Schlüssel initialisiert. Die Hashes können nur mit diesem Schlüssel erzeugt werden. Jemand anderes der auch Crypt benutzt und den Schlüssel nicht kennt, kann keine gleichen Hashes erzeugen.
  2. Aus einem festgelegten Passwort wird mit crypt.hash(...) ein Hash erzeugt und gespeichert. Das Passwort selbst wird verworfen.
  3. Beim Login gibt der Benutzer das Passwort ein. Dies wird wieder durch dieselbe Methode crypt.hash(...) zu einem Hash-Wert verarbeitet. Stimmen die beiden Hash-Werte überein, stimmen die beiden Passwörter ebenfalls überein. Die Irrtumswahrscheinlichkeit liegt in der Standard-Konfiguration bei etwa 2^-64 (etwa 10^-19).

Beispiel#

Hier ein paar Strings und deren Hash-Werte dazu. Als Master-Key wurde der Schlüssel "test1" verwendet:

StringHash-Wert
HallöchenbaySkPjELI5H74rGY6myXZ
Hallöchen!bfXmVy7RkdW0CkE7QuQYVE
Hellöchen7K2tzDXmn699S9uWW7BWqj

Erklärung: Es wurden absichtlich recht ähnliche Strings benutzt um zu zeigen, dass sich die Hash-Werte stark unterscheiden.

Details#

Die dahinterstehende Klasse PrimeRootHash implementiert das Interface Hash mit dem Konstruktor PrimeRootHash(int bits) und der Methode byte hash(byte bytes).

Diese Klasse verkapselt Methoden aus der Klasse com.intersult.util.math.Num, insbesondere nextProbablePrimeRoot(int bits). Damit kann nun letzten Endes das gewünschte Object vom Typ PrimeRoot erzeugt werden, das eine Primzahl und eine zugehörige Primitivwurzel enthält. Beide Zahlen sind vom Typ java.math.BigInteger.

Das Überprüfen ob eine Zahl eine Primitivwurzel einer Primzahl ist, ist selbst mit optimierten Algorithmen relativ aufwendig zu berechnen. Daher sind derzeit Primitivwurzeln bis zu 84 Bit Länge vorab gespeichert.

Hinweis: Die Implementierung ist nur effizient für relativ kleine Byte-Arrays, nicht wesentlich größer als 1024 Bytes.

Warnung: Bei der Anfrage längerer Primitivwurzeln werden diese berechnet. Dies kann mit zunehmender Bit-Länge sehr viel Zeit in Anspruch nehmen.