PHP (OOP, MVC), HTML, MySQL, Javascript, AJAX und vieles mehr!

Neulich benötigte ich eine Möglichkeit, eindeutige Strings (Hashes) mit einer Länge von 8 Zeichen zu generieren. Die Anforderungen an den String waren, dass er zufällig ist (nicht fortlaufend) und eine feste Länge von 8 Zeichen hat. Meine Überlegung war, einfach die md5-Summe von einem String, der sich aus mehreren Teilen zusammensetzt, zu bilden und die ersten 8 Zeichen als Hash zu benutzen. Leider stellte sich das als ein falscher Gedanke heraus. Es gab ca. bei jedem 100. String eine Kollision (d.h. der Hash kam schonmal vor).

Der Code dazu sah übrigens so aus:

//Hash erzeugen (Kann nicht erraten werden)
      $hash = substr(
                      md5(
                          uniqid(
                                  (string)microtime(true)
                                  +sha1(
                                        (string)rand(0,10000)  //100% Zufall
                                        +$thumb_tmp_name
                                        )
                                )
                          +md5($orig_name)
                          )
                      , 0, 8);

Man sieht, dass ziemlich viel in den String eingeht, was teils zufällig und teils „konstant“ ist. Das Konzept wäre aufgegangen, wenn ich nicht 3/4 des ursprünglich 32-Zeichen-langen md5()-Hashes abgetrennt hätte. Die verbleibenden 8 Zeichen des Hashes wiederholten sich anscheinend so oft, dass es sehr viele doppelte Strings gab. Die Erklärung dazu ist ganz einfach: md5 ist von Natur aus schon nicht kollisionslos. Bei der vollen Länge von 32 Zeichen treten Kollisionen aber recht selten auf. Schneidet man den Großteils des Strings ab, ist dieser nicht mehr eindeutig. Beim Abschneiden nimmt man sozusagen drei viertel der Zufälligkeit. (An die Mathematiker unter euch: Ich weiß schon, dass man das so nicht sagen kann. Es soll das ganze nur verdeutlichen :)) Deshalb musste eine neue Methode her.

Die ganzen Funktionen, die PHP bietet (sha1, md5, uniquid, …) waren für meine Zwecke alle nicht gut genug. Ich brauchte meine eigene Klasse, um meine Hashes zu erzeugen. Und diese hat – wenn ich das mal anmerken darf – bei über 10 Millionen erzeugten Strings keine einzige Kollision aufgewiesen. Wenn das mal nicht gut ist 🙂 (Selbstlob stinkt, ich weiß :-P) Warum ich nicht mehr getestet hab? Weil es mir irgendwann zu lange gedauert hat, außerdem brauche ich für meinen Zweck nur ca. 10 000 kollisionslose Strings.

Es folgt erstmal der Code, dann wird euch die Sache bestimmt klarer:

class FW_Tool_Hash
{
  private $chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVEXYZ-_0123456789";
  private $len;

  public function __construct($length)
  {
    $this->setLength($length);
  }

  public function setLength($length)
  {
    $this->len = (int)$length;
  }

  public function getLength()
  {
    return $this->len;
  }

  public function getChars()
  {
    return $this->chars;
  }

  public function setChars($chars)
  {
    $this->chars = (string)$chars;
  }

  public function getHash()
  {
    $hash = "";
    for($i = 0; $i < $this->len; $i++)
    {
      $hash .= $this->chars{mt_rand(0, strlen($this->chars)-1)};
    }

    return $hash;
  }
}

Die Attribute $chars und $len sind ausschlaggebend dafür, wie der fertige String aussehen wird. $chars gibt an, welche Zeichen erlaubt sind und $len, wie lange der Hash sein darf. In der Defaulteinstellung
($chars = „abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVEXYZ-_0123456789“;) gibt es 64 erlaubte Zeichen. Daraus ergeben sich bei einer Länge von 8 Zeichen 64^8 = 281474976710656 Möglichkeiten. Das sind 281,47 Billionen verschiedene Kombinationen, die erdenklich sind. Zum Vergleich: md5 generiert zur Hexadezimale Zeichen als Stringelement. Bei einer Länge von 32 Zeichen sind das 16^32 = 3,4028^38 Möglichkeiten. Um einiges mehr, oder? Man muss aber auch beachten, dass md5 4x solange ist. Wäre md5 nur 8 Zeichen lang, gäbe es nur 16^8 = 4,294 Mrd verschiedene Kombinationen. Insgesamt lässt sich also sagen, dass „mein“ Verfahren das „bessere“ ist im Sinne der Kombinationsanzahl.

Noch ein kleiner Vergleich, irgendwie mag ist Statistiken. Würde ich mit meiner Klasse ebenfalls einen 32 Zeichen langen Hash erzeugen, dann gäbe es 64^32 = 6,2771^57 Möglichkeiten. Das sind 18446744073709551616 mal mehr als bei einem gleich langen md5-String. Unglaublich, aber wahr 😀

Aber wie genau funktionert „mein“ Verfahren?

  public function getHash()
  {
    $hash = "";
    for($i = 0; $i < $this->len; $i++)
    {
      $hash .= $this->chars{mt_rand(0, strlen($this->chars)-1)};
    }

    return $hash;
  }

Eigentlich extrem einfach. Es wird einfach len Mal eine Zufallszahl erzeugt (mit mt_rand). Diese Zufallszahl liegt zw. 0 und der Anzahl verfügbarer Zeichen -1. Anhand dieser Zufallszahl wird einfach ein Zeichen aus $chars ausgepickt und an den Hash angehängt. Am Schluss haben wir einen ziemlich zufälligen Hash! Sehr wichtig dabei ist, dass man mt_rand() verwendet. rand() würde (ohne vorherige Initialisierung) immer die gleichen Zufallszahlen ausspucken, was recht sinnlos wäre.

Anwendung

Die Anwendung der Klasse ist nicht schwer:

$hash_generator = new FW_Tool_Hash(8); //Die 8 legt die Länge fest
$hash = $hash_generator->getHash();
echo $hash; //gibt den Hash aus

Selbstverständlich kann man die 8 durch eine beliebige Zahl ersetzen. Übrigens vllt. interessant: Bei der Länge 1 gibt es genau 64^1 Möglichkeiten 😛

Ich hoffe, euch hat der Artikel gefallen und vor allem weitergeholfen!

(6 Stimme, durchschnittlich 4,33 / 5)

Loading...