Hashfunktionen begegnet man überall, wo es darum geht, Zeichenketten (z.B. Nutzernamen oder Passwörter) oder beliebige Daten (z.B. Download – Archive) voneinander zu unterscheiden. Oft werden Hashs im Hintergrund gerechnet, ohne dass der User das sieht. Anders beim Download von Programmen über das Internet: Hier wird auf der Downloadseite oft ein Hashwert des Downloads (syn. Hash- oder Programm-„Signatur“) angegeben, damit man nach dem Herunterladen (und vor dem Starten des Programms) noch einmal prüfen kann, ob das Programm vollständig und unverändert geladen wurde. Hashfunktionen sind vor allem im Verborgenen unverzichtbar – sie übernehmen das Encoding/Decoding von Zeichenfolgen zu Hashtables, die der schnellen Zuweisung von Befehlen zu Codes im Kern der Programmiersprachen und beim Kompilieren dienen (Wer mehr dazu wissen will, findet hier einen Videomitschnitt vom 29. CCC-Kongress, der das Dilemma (Hash-Table Flooding) „schlechter“ Hashfunktionen verdeutlicht.

Das Berechnen des Hashwerts kann eine rechenintensive Aufgabe sein. Ein Hash-Algorithmus liest Daten schrittweise ein und verrechnet den Stream zu einem Hashwert, der je nach Güte und Art des Hashprogramms in einen „seltenen“ oder sogar „einzigartigen“ Zahlenwert besteht (oft im Hexadezimalformat ausgegeben).

Hashfunktionen allgemein werden nach der Länge des Ausgabewertes (Angabe in Bit) unterschieden, kryptologische Hashfunktionen liefern Hashs mit einer fixen Länge (z.B. SHA256->256Bits ; SHA512->512Bits) , andere Funktionen liefern Hashwerte bis zu einem Maximalwert.

Kryptologisch sichere Hashfunktionen sind unter anderem dahingehend optimiert, dass es keine – nicht einmal theoretische – Kollisionen gibt (Kollisionen sind gleiche Hashwerte für ungleiche Eingangsdaten). Außerdem sind die Algorithmen so gestaltet, dass zwei Eingaben, die sich nur sehr geringfügig unterscheiden, bereits stark unterschiedliche Hashergebnisse (Signaturen) ergeben. Dabei ist es wichtig, dass der Rechenweg so konzipiert ist, dass sie sogenannte „Einwegfunktionen“ darstellen und vom Hash nicht auf die Eingabedaten zurück gerechnet werden kann. Will man also von einer kryptologischen Signatur auf den Eingabewert zurückschließen, so ginge dies nur, wenn man eine Tabelle mit allen möglichen Eingabewerten und zugehörigen Hash-Ausgaben hat. Liegen solche Tabellen (z.B. „Rainbow-Tables“ für Strings in typischer Passwortlänge) einmal vor, so ist diese Hashfunktion natürlich nicht mehr sicher und sollte im sicherheitsrelevanten Zusammenhängen – zum Beispiel fürs Speichern von Passwörtern – nicht weiter benutzt werden: MD5, SHA-1; Weiteres siehe: https://de.wikipedia.org/wiki/Kryptologische_Hashfunktion ).

Erwähnenswert: Zu den ganz neuen kryptologischen Hashfunktionen gehören BLAKE2s (32 Bit Maschinen) und BLAKE2b (64 Bit Maschinen) https://blake2.net, die Jean-Philippe Aumasson et al. unter Verwendung von Daniel Bernsteins ChaCha Code entwickelt haben. Blake2 Hashfunktionen sind so schnell wie MD5 oder SHA-1, im Unterschied zu vorgenannten sind sie jedoch (derzeit) kryptologisch sicher.

Nicht kryptologische Hashfunktionen

Im Gegenzug sind aufgrund zusätzlicher Rechenschritte kryptologische Hashfunktionen vergleichsweise langsamer als nicht kryptologische Hashfunktionen (Faktor 30x-300x). Für die Verarbeitung nicht sicherheitsrelevanter Daten, bei denen kryptologische Eigenschaften des Hashs keine Rolle spielen, werden darum einfachere (= schnellere) Hashfunktionen eingesetzt. Eventuell ist auch Kollisionsfreiheit weniger wichtig als Geschwindigkeit oder das Risiko von Kollisionen wird verringert, indem mehrere (zwei +) Hashs mit verschiedenen schnellen, aber nicht kollisionssicheren Hashfunktionen berechnet und kombiniert werden. Trotzdem speilt Kollisionssicherheit eine grosse Rolle und die neuesten Hash-Algorithmen punkten hier deutlich.

0815 Nutzen: Hashen jenseits von Passwort/Nutzernamen

Nehmen wir an, eine Reihe Bilder, die sich eventuell nur um den Farbwert einzelner Pixel unterscheiden, sollen daraufhin geprüft werden, ob sie exakt einer Referenz (Original) entsprechen. Ein „naiver“ Ansatz wäre, jedes der Bilder Pixel für Pixel mit der Referenz zu vergleichen. Geht es aber nur darum festzustellen, ob sich die Bilder von der Referenz unterscheiden, so ist die Verwendung eines Hashes die effektivere Lösung.

    Erstelle einen Hash der Referenz
    Für jedes Bild
        erstelle einen Hasch
        vergleiche den Bild-Hash mit dem Referenz-Hash
            gib zurück: gleich / ungleich

Habe ich einen schnellen Hash-Algorithmus so kann ich die Vergleichsdaten auch in Segmente unterteilen und dann die Segment-Hashs untersuchen und vergleichsweise resourcen-sparsam und schnell Unterschiede lokalisieren.

    Erstelle einen Hash der Referenz
    Für n-Segmente der Referenz 
        erstelle je einen Referenz-Segment-Hash
    Für jedes Bild
        erstelle einen Hasch
        vergleiche den Bild-Hash mit dem Referenz-Hash
            wenn ungleich
                für n-Segmente des Bildes 
                    erstelle Bild-Segment-Hash
                        vergleiche Bild-Segment-Hash mit Referenz-Segment-Hash
                            gib zurück: ungleiche Segmente
    

Statt ganze Bilder, Pixel für Pixel mit einer Referenz zu vergleichen, ist dann nur noch ein Vergleich der Segmente, die ungleiche Hashwerte hatten, nötig, um unterschiedliche Pixel exakt zu lokalisieren.

Welche Hashfunktion ist die richtige für meinen Zweck

Viele Hashfunktionen sind optimiert für die schnelle Verarbeitung großer Datenmengen. Das geschieht z.B. durch die Verarbeitung von Byte-Gruppen in einem Durchgang. Dass die Hashrechnung selbst etwas aufwendiger ist, fällt dabei dann weniger ins Gewicht, als bei Funktionen, die einen Stream/String Byte für Byte verrechnen. In der Gegenüberstellung zu Googles xxHash http://code.google.com/p/xxhash/ finden sich Vertreter dieses (neueren) Hashtyps auf den oberen sechs Plätzen der Rankingtabelle. Siehe auch hier: http://brainspec.com/blog/2012/10/29/fast-hashing-with-cityhash/ Zur Entwicklung von Hashfunktionen neueren Typs, die bei großen Datenmengen auch die Möglichkeiten aktueller Prozessoren zur parallelen Berechnungen ausnutzen: http://web.stanford.edu/class/ee380/Abstracts/121017-slides.pdf

Für eine Aufgabe, wie die oben geschilderten Vergleiche von Bilddateien, können diese „modernen“ hochperformanten Hashfunktionen gut geeignet sein. Wenn man allerdings nur kurze Strings hashen muss (z.B. IP-Adressen oder Log-Einträge) und ohnehin nur 32Bit oder 64Bit Ergebnisse braucht, waren die Hash-Funktionen 2. und 3. Generation bei meinen eigenen Benchmarks allesamt langsamer als SDBM, FNV oder DJB2, da die Byte-Gruppen-Verarbeitung einen recht großen Overhead (Initialisierung, Finalisieren) mitbringt.

Schnelle, nicht kryptologische Hashfunktionen

Im Folgenden eine Liste mit Links zu verschiedenen Webseiten, die sich mit Hash-Berechnungen beschäftigen:

FNV-Hash Family http://www.isthe.com/chongo/tech/comp/fnv/index.html based on prime calculations.

Bob Jenkins Sites http://burtleburtle.net/bob/

Arash Partow Zusammen-&Gegenüberstellung klassischer Hashfunktionen http://partow.net/programming/hashfunctions/index.html

Die Seite diskutiert verschiedenste Hashfunktionen und erlaubt den Download in verschiedenen Programmiersprachen z.B. CPP oder Python:

// citation: An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3,
// under the topic of sorting and search chapter 6.4.
def DEKHash(key):
    hash = len(key);
    for i in range(len(key)):
      hash = ((hash << 5) ^ (hash >> 27)) ^ ord(key[i])
    return hash

DEKHash in Go:

func (bl Bloom) DEKHash(b *[]byte) (hash uint64) {
  hash := uint64(len(*b))
  for _, c := range *b {
    hash = ((hash << 5) ^ (hash >> 27)) ^ uint64(c)
  }
  return hash
}

http://www.cse.yorku.ca/~oz/hash.html – DJB2 und SDBM-Hash Funktionen in C

Google-Code Seiten

http://code.google.com/p/cityhash/ CityHash

http://code.google.com/p/xxhash/ xxHash und ein Benchmarking verschiedener Hash-Funktionen: xxHash, cityHash, lookUp3, SpookyHash2, Murmur3, FNV …

Eine ausführliche Diskussion verschiedener Hashfunktionen mit vielen Links findet sich auch hier:http://blog.reverberate.org/2012/01/state-of-hash-functions-2012.html

Euler project „Project Euler“ http://projecteuler.net inspired some coders to think about prime generation in python. Even if the primes are already known, the pure python implementations are interesting to get information about fast computation models for big number arrays.

Das „Project Euler“ http://projecteuler.net hat eine Reihe Programmierer inspiriert, sich mit der Frage der Erzeugung von Primzahlen auseinanderzusetzen. Das ist in erster Linie ein akademisches Unterfangen, weil die entsprechenden Primzahlen (<10**10 u.Ä.) natürlich bereits bekannt sind. Trotzdem eine spannende Aufgabe, fand ich, und habe eine Routine programmiert, von der ich hoffte, sie könne im Vergleich mithalten, indem sie durch Deduction die Anzahl der Kalkulationen drückt. Hat nur bedingt geklappt.

Hier ist der Sieger-Code von Robert William Hanks:

def rwh_primes(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
  if sieve[i]:
  sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]

def rwh_primes1(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes < n """ 
sieve = [True] * (n/2) 
for i in xrange(3,int(n**0.5)+1,2): 
  if sieve[i/2]: sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] 

def rwh_primes2(n): 
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188 
""" Input n>=6, Returns a list of primes, 2 <= p < n """ 
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n/3)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
  if sieve[i]:
    k=3*i+1|1
  sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
  sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

Link zur stackoverflow-Seite

However – meine Lösung ist auf einem MBPro15/i7 als schnellste hinter RWHs Lösungen 1 und 2 dennoch ziemlich gut weggekommen:

def primeSieveSeq(MAX_Int):
    if MAX_Int > 5*10**8:
        import ctypes
        int16Array = ctypes.c_ushort * (MAX_Int >> 1)
        sieve = int16Array()
        #print 'uses ctypes "unsigned short int Array"'
    else:
        sieve = (MAX_Int >> 1) * [False]
        #print 'uses python list() of long long int'
    if MAX_Int < 10**8:
        sieve[4::3] = [True]*((MAX_Int - 8)/6+1)
        sieve[12::5] = [True]*((MAX_Int - 24)/10+1)
    r = [2, 3, 5]
    n = 0
    for i in xrange(int(MAX_Int**0.5)/30+1):
        n += 3
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 3
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
    if MAX_Int < 10**8:
        return [2, 3, 5]+[(p << 1) + 1 for p in [n for n in xrange(3, MAX_Int >> 1) if not sieve[n]]]
    n = n >> 1
    try:
        for i in xrange((MAX_Int-2*n)/30 + 1):
            n += 3
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 3
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
    except:
        pass
    return r

Auf jeden Fall bleibt festzuhalten, dass in python der Fill mit Array Access über Indexranges array[start:stop:step] = [True]*(((MAX_Int >> 1) – n2q – 1) / n2 + 1) jeder Schleifenkontrolle in Bezug auf processing-speed deutlich überlegen ist.

Eventually i needed some prime numbers to play around with Bloom filtering.
The Python – script (see below) will produce primes below 2**x base number by stepping backward using the step parameter.
python primes.py <number of file> <2**x exponent x> <step> <number of primes to produce>

if the <number of file> parameter is a character output to a file will be omitted and the primes will print to stdout instead.

<number of primes to produce> defaults to 10

I tested the performance of a single threaded and multi-threaded approach on some PC of various age. The outcome was interesting:

On one hand the script performance benefits very much from improvements of CPU architecture. Nonetheless clock speed and number of real cores seem to be of highest importance.

#! /usr/bin/python
# procuces scripts < 2**x by testing in a by 
import os
import sys
import subprocess
import threading
import pprint
import time

cnt = totcnt = 0
erg = []
max_concurrentThreads = 32
thread_limiter = threading.Semaphore(value=max_concurrentThreads)

# check 4 gmpy 
try:
  # raise
  from gmpy import mpz
  gmpy_ready = True
  print "Message: Using gmpy/GMP mpz.is_prime instead of openSSL prime. (up to 10times faster)"
except:
  gmpy_ready = False
  print """Message: 
  If you try to produce many or really large primes, 
  consider installing GMP ( http://gmplib.org ) 
  and gmpy/gmpy2 ( http:http://www.aleax.it/gmpy.html )"""

class checkr(threading.Thread):

  def __init__(self, num):
    threading.Thread.__init__(self)
    self.num = num

  def run(self):
    global erg, cnt
    thread_limiter.acquire()
    prm = check(self.num)
    if prm:
      erg.append(prm)
      cnt += 1
    thread_limiter.release()

def check(num):
  r = None
  if gmpy_ready:
    try:
      if mpz(num).is_prime() == 1:
        r = num
    except:
      print '#', num, '#'
  else:
    e = subprocess.Popen(['/usr/bin/openSSL', 'prime', num], stdout=subprocess.PIPE)
    if e.communicate()[0][-9:-7] == "is":
      r = num
  return r

def longnumget(start, step):
  start = str(start+step)
  step = 2*step
  lenstep = 2*len(str(step))
  def numSeperator(numAsString, lenstep):
    formatter = '%%0%ii' % lenstep
    frst, secnd = numAsString[:-lenstep], start[-lenstep:]
    diff = int(secnd)-step
    secnd = formatter % diff
    r = frst + secnd
    if diff < 0:
      r = numSeperator(numAsString, lenstep+1)
    return r
  while True:
    start = numSeperator(start, lenstep)
    while start[-1] == '5':
      start = numSeperator(start, lenstep)
    yield start

def shortnumget(start, step):
  start = start+step
  step = 2*step
  while True:
    start -= step
    while str(start)[-1] == '5':
      start -= step
    yield str(start)

if __name__ == '__main__':
  if len(sys.argv) == 5:
    p, seqNum, base2exp, step, count = map(str, sys.argv)
    if count:
      count = int(count) or 10
    step = abs(int(step))
    if step % 2 == 0:
      print("Step must be odd!")
      sys.exit()
    if int(base2exp) < 4000:
      numget = shortnumget
    else:
      numget = longnumget
      print "custom string-cut partitional substraction"
    if gmpy_ready:
      startnum = mpz('0b1'+int(base2exp)*'0', 0)
    else:
      startnum = eval('2**'+base2exp)
    nums = numget(startnum, step)
    sTime = time.time()
    while cnt <= count:
      # uncomment the next 2 lines to test of the single threaded approach
      # check(nums.next())
      # totcnt += 1
      # 
      # uncomment next 5 lines to test the threaded approach 
      startNewThread = threading.active_count() < max_concurrentThreads
      if startNewThread:
        t = checkr(nums.next())
        t.start()
        totcnt += 1

    print 'Time elapsed:', time.time() - sTime, 'seconds'
    print totcnt, 'numbers checked for prime' 
    print len(erg), 'primes found (', round(100.0*len(erg)/totcnt, 1), '%)'

    try:
      seqNum = int(seqNum)
      with file('primes_%s_%sK_%s.txt' % (seqNum, count/1000, base2exp), 'wb') as outFle:
        for i in xrange(len(erg)):
          print >> outFle, '2**%s-%s' % (base2exp, startnum - int(erg[i])), erg[i], hex(int(erg[i]))
    except Exception as e:
      pp = pprint.PrettyPrinter()
      pp.pprint(erg)

das Setzen einer entsprechenden Berechtigung, die bei aktuellen Browser cross domain requests ermöglicht , ist ganz einfach. Im python code die cross domain Authorisierung „Access-Control-Allow-Origin:*\n“ der HTML- Bestätigung vorangestellt: Also folgendermassen
10 print „Access-Control-Allow-Origin:*\nContent-Type:text/html;charset=utf-8\n\n“

Cherrypy allows to define functions to be so called „tools“ (cherrypy docs). These helper functions might be „hooked“ at various processing points within cherrypys serving process: on_start_resource, before_request_body, before_handler, before_finalize, on_end_resource, before_error_response, after_error_response, on_end_request.

Making the tool is working straight forward. According to the working draft http://www.w3.org/TR/cors/ cross origin access allowance needs to be declared within the response header (see RFC for further information on CORS headers). The following example will add a response header to allow CORS to any („*“) client; change the ‚*‘ to an uri-scheme have provide more granular scaling.

import cherrypy

def CORS():
…cherrypy.response.headers[„Access-Control-Allow-Origin“] = „*“ #

attaching the function to a process stage hook needs to be done in the main proc:

if __name__==“__main__“:
(…)
…cherrypy.tools.CORS = cherrypy.Tool(‚before_finalize‘, CORS)

# insert tool declaration within def main() or even directly
# before cherrypy.tree.mount command to prevent Error like

If you try to declare the toll earlier an TypeError starting with:
The ‚CORS‘ Tool does not accept positional arguments … is likely to be thrown.

Like with other cherrypy tools you might use them globally by adding „cherrypy.tool.CORS.on : True“ to the general.configs or by using the decorator @cherrypy.tools.CORS right after the exposure decorator of a
page/wsgi def.

In dieser Post werde ich kurz ein paar Links aufführen, die direkt zu verschiedenen online Umgebungen für das Bearbeiten und Testen von Code leiten.

Zuerst einmal HTML5 und Javascript:

http://jsfiddle.net/
ist eine prima javascript Umgebung zum Ausprobieren und Versuchen. Es gibt eine saubere Trennung von HTML-DOM, CSS, Javascript und zur Darstellung des verarbeiteten Resultats. Da jsFiddle als webapp im Browser läuft, ist alles möglich, was vom Browser unterstützt wird. Funzt auch mit nur wenigen Ausnahmen mit dem iPad – also wirklich eine gute Möglichkeit Javascript-Code cross zu testen.

Ist der Code dann fertig, kann man ihn unter http://jsapp.us/
mit einer nodeJS Engine auf die Eignung als browser side JS testen.

http://www.cdnjs.com/
ist eine (derzeit kostenfreie) hosting-Plattform für bekannte (und exotische) Javascript-Frameworks und -Extensions. Die Plattform verspricht hohe Performanz und Optimierung (eventuell zukünftig auch durch Kombination von Frameworks wie jQuery udn jQuery UI o.ä.)

Als besonders erwähnenswert erscheint mir unter den Exoten D3 , ein Framework zur Erzeugung dynamischer Datendarstellungen mit javascript, das zur Manipulation und Erzeugung auf CSS, DOM und SVG zugreift. (By the way: schade, dass so wenige Dev sich mit SVG auseinandersetzen – SVG sollte sich für HTML-DOM Profis eigentlich „natürlicher“ anfühlen als CANVAS, trotzdem ist es erheblich weniger im Einsatz.

Für alle, die ihren Horizont erweitern und eine neue Programmiersprache lernen wollen:
Über 20 verschiedene Programmiersprachen online coden und ausprobieren kann man bei http://ideone.com/
Da ist wirklich von den diversen C Dialekten bis zu Javascript, Ruby, Python, …. alles dabei – sogar Assembler, wer’s braucht.
Zu jeder Sprache gibt es auch ein paar Zeilen sample Code zum Vergleichen. Die Programme werden auf dem Server ausgeführt, wenn man auf den m. E. etwas unglücklich platzierten „submit“-Button klickt. Es öffnet sich eine neue Seite, auf der Code, Input und Output in textareas dargestellt sind, und auch ein weiteres Editieren möglich ist.