Bash Einweg-Hashfunktion programmieren, die feste Ausgabelänge hat und pseudozufällig ist

[xpad.c]

Ich bewundere die Ausdauer, mit der ihr euch weiterhin die Köpfe zerbrecht, wie man diese merkwürdige Aufgabenstellung lösen könnte.

Ich möchte erneut die Frage ins Spiel bringen, wieso das überhaupt in diesen Wertebereich muss? Vermutlich will der OP damit irgendwie weiterrechnen, aber was kann es denn bitte für eine Rechnung geben, die nicht auch mit einer n-bit Zahl in Hex-Schreibweise funktionieren würde?
Dazu dann noch diese 4 Zeichen aus den angeblichen URLs, wo man sich fragt, welche 4, warum überhaupt 4?

http://foo.bar/baz/bla.html
http://foo.bar/baz/bla?q=$hash#fragment

Hm, "http" wohl eher nicht, "html"... auch nicht?
Am Ende kommt er noch mit einem URL-Parser in bash um die Ecke oder fragt nach einem regulären Ausdruck dafür, dabei könnte es so einfach sein! Einfach die URL so nehmen, wie sie ist. Arbeit, die man sich gar nicht macht, ist am schnellsten fertig, oder so. Aber was weiß ich schon. Falle ja unter "Neuanmeldung", obwohl sein Account 1 Monat jünger ist als meiner...

Eins noch, das hatte ich gestern nicht gesehen:

ChatGPT hat ein wenig erklärt warum es diesen Wert benutzt habe

Bei dieser Begründung hat ChatGPT Dich offenbar kackdreist angelogen, denn 33 ist keine Primzahl.

xpad.c

 

[Piktogramm]

Wie oft denn noch, dass das nicht ausreicht?

Deswegen steht ja auch als Denkaufgabe für dich, dass du dir überlegen sollstest, wie die Menge der möglichen SHA und/oder AES Hashes auf den Wertebereich [0..9999] abzubilden wäre, mit welchen Effekten.

Wobei

Wobei bei 2**256 (115792089237316195423570985008687907853269984665640564039457584007913129639936)
der "Bias" recht gering ist.

und

Stimmt, guter Punkt. Wobei der Bias ziemlich klein ist bei einer 256 Bit Zahl Modulo 10.000. Ich vage zu behaupten, dass man den in vielen Anwendungsfällen akzeptieren kann.

80% der Lösung liefern. Die Beiden waren bestimmt schon in der Schule diese Streber die in der ersten Reihe sitzend immer den Arm oben hatten und dazu noch laut schnipsten..

[...]daher habe ich eine zweite Variante hinzugefügt, die stattdessen (2^256-1)*10000/2^256<10 000 rechnet und dadurch ein Abrunden erzwingt.

Die Probleme von Modulo bleiben im Tausch für (viel) mehr CPU-Zyklen

Außerdem sind es dann angeblich zwei Verfahren?!?

Das ist der Grund wieso ich da eine Hausaufgabe vermute. Auf Prod würde da allenfalls ein Überschlag fällig werden, wie gut die Reduktion des Ergebnisraums über Modulo für das Ziel taugt. Das klingt halt schon arg nach eine Aufgabe aus einem Grundlagenkurs, wo der/die/das Prof offensichtliche Lösungen ausschließen will.

 

[CyborgBeta]

80% der Lösung liefern. Die Beiden waren bestimmt schon in der Schule diese Streber die in der ersten Reihe sitzend immer den Arm oben hatten und dazu noch laut schnipsten.

Ja, und es gibt (zum Glück) keine Kopfnoten mehr, wodurch beleidigendes Verhalten kein Malus mehr ist. Das scheint alles unwichtig geworden zu sein.

 

[KitKat::new()]

Die Probleme von Modulo bleiben im Tausch für (viel) mehr CPU-Zyklen

inwiefern? da jede Zahl der Bildmenge gleich viele Elemente aus dem Urbild* bekommt, sollte das Problem aus dem Weg geräumt sein

Ergänzung (14. April 2025)

@KitKat::new() Das führt den selben Bias ein wie die Modulovariante (weil 2^256 nämlich nicht durch 10 000 teilbar ist [2^256 mod 10 000 = 9 936])

Zum selben führt sie auf jeden Fall nicht, da ich gar nicht durch 10 000 teile.
*Der Bias wird sich darauf beschränken, dass manche der 10.000 Werte nicht 1.15 * 10^73 aus dem Urbild bekommen, sondern 1.15 * 10^73 - 1

 

[Piktogramm]

@KitKat::new()
Die Frage könnte ein paar mehr Worte vertragen, welchen Teil der Aussage meinst du?
Das Grundlegend Problem der Abbildung einer großen Menge auf einen deutlich kleineren Raum hast du halt immer.
Und CPU-Zyklen braucht es tendenziell deutlich mehr, da es eine Temporäre Erweiterung auf u512 gibt. Sehr viele CPUs bekommen das nicht nativ hin, selbst auf den Architekturen auf denen es geht erzeugen die meisten Compiler das bisschen kein entsprechenden Code (Der Wechsel auf AVX512 ist bei den meisten X86 CPUs zu teuer)

 

[KitKat::new()]

Die Frage könnte ein paar mehr Worte vertragen, welchen Teil der Aussage meinst du?

Dass das Problem von Modulo bleibt.

Das Grundlegend Problem der Abbildung einer großen Menge auf einen deutlich kleineren Raum hast du halt immer.

Wenn ich 10.000 Zufallszahlen auf 2 reduziere, habe ich warum welches grundlegende Problem bzgl. Gleichverteilung?

 

[simpsonsfan]

Wenn ich 10.000 Zufallszahlen auf 2 reduziere, habe ich warum welches grundlegende Problem bzgl. Gleichverteilung?

Ich bedanke mich für diese Frage und möchte eine andere beantworten.
Wenn du einen perfekten Zufallsgenerator hast, der dir gleichverteilte Zahlen aus einem Wertebereich mit 10 000 Elementen generiert und du den als Grundlage für eine zufällige Zahl aus einem Wertebereich mit 2 Elementen verwenden willst, dann hast du da kein grundlegendes Problem der Gleichverteilung, weil 10 000 durch 2 teilbar ist.

*Der Bias wird sich darauf beschränken, dass manche der 10.000 Werte nicht 1.15 * 10^73 aus dem Urbild bekommen, sondern 1.15 * 10^73 - 1

Das grundlegend selbe Problem wie bei der Modulovariante.

 

[Marco01_809]

Ich hab mal fix ne Implementation geschrieben die sha256sum macht, die letzten 15 Zeichen (60 Bits) in dezimal umwandelt und dann modulo 10000. Das für den ganzen Eingaberaum aaaa-zzzz einmal durchrechnen.
Der Bias ist tatsächlich das geringste Problem. Es garantiert ja grundsätzlich nichts, dass SHA256 auch für jede beliebige endliche Eingabemenge gleichverteilt ist. Dafür ist unsere Eingabemenge mit 26**4 einfach zu klein. Und in der Tat gibt es bei der SHA256%10000 Lösung einen Hash auf den nur 17 Eingaben entfallen und ein anderer für den es 73 gibt.

WENN man also genau die Anforderungen hat dass es Dezimalzahlen sein müssen, einen sehr kleinen Definitionsbereich, die gleichmäßigst-mögliche Verteilung und es soll nach viel Diffusion aussehen weil der Algorithmus so mysteriös ist, aber keine Eigenschaften braucht die einen Hash zum Hash machen... dann ist die Lösung vom OP womöglich das Mittel der Wahl.

Alle anderen sollten einfach 3-4 Zeichen des SHA256 hashs nehmen.

Am Ende kommt er noch mit einem URL-Parser in bash um die Ecke

Ha!!! Damit kann ich dienen!! Letztes Jahr erst geschrieben den Mist

Spoiler

Braucht mindestens Bash 4.2 und set -eu. Leider kein support für prozent-encoding

declare -r RFC3986_GEN_DELIMS="]:/?#[@"
declare -r RFC3986_SUB_DELIMS="!\$&'()*+,;="
declare -r RFC3986_RESERVED="$RFC3986_GEN_DELIMS$RFC3986_SUB_DELIMS"

# Resembles https://www.rfc-editor.org/rfc/rfc3986#section-3
declare -r URL_SCHEME_PART="([a-zA-Z][a-zA-Z0-9+\-\.]*):"
declare -r URL_USERINFO_PART="([^$RFC3986_GEN_DELIMS]*)@"
declare -r URL_HOST_PART="([^$RFC3986_GEN_DELIMS]+)"
declare -r URL_PORT_PART=":([1-9][0-9]*)"
declare -r URL_PATH_PART="(/[^?#]*)?"
declare -r URL_AUTHORITY_PART="($URL_USERINFO_PART)?$URL_HOST_PART($URL_PORT_PART)?"
declare -r URL_QUERY_PART="\\?([^#]*)"
declare -r URL_FRAGMENT_PART="#([^#]*)"

# For "/path?query", '?' = may be empty:
# 1? = /path
# 2? = ?query
# 3? = query
declare -r URL_REFERENCE_REGEX="^$URL_PATH_PART($URL_QUERY_PART)?$"
# For "scheme://userinfo@host:port/path?query", '?' = may be empty:
#  1? = scheme:
#  2? = scheme
#  3? = userinfo@
#  4? = userinfo
#  5  = host
#  6? = :port
#  7? = port
#  8? = /path?query
#  9? = /path
# 10? = ?query
# 11? = query
# Fragment is not allowed (because it does not make sense for backend tests)
declare -r URL_ABSOLUTE_REGEX="^($URL_SCHEME_PART)?//$URL_AUTHORITY_PART($URL_PATH_PART($URL_QUERY_PART)?)$"

declare -A url_scheme_ports=(["http"]=80 ["ws"]=80 ["https"]=443 ["wss"]=443)

# Convert reference/URL to an absolute URL
url_qualify() {
  local -r url="$1"
  local -r base="$2"

  if [[ $url =~ $URL_ABSOLUTE_REGEX ]]; then
    if [[ -z "${BASH_REMATCH[2]}" ]]; then
      # url lacks scheme, e.g. //example.com/foo
      url_parse "$base"
      echo -n "${BASH_REMATCH[1]}"
    fi
    # url is absolute, e.g. https://example.com/foo
    echo "$url"
  elif [[ $url =~ $URL_REFERENCE_REGEX ]]; then
    # url is path or the empty string, e.g. /foo
    echo "$base$url"
  else
    conclude_error "URL is invalid: '$url'"
  fi
}

# Parse an absolute URL, requiring scheme
url_parse() {
  [[ $1 =~ $URL_ABSOLUTE_REGEX && -n "${BASH_REMATCH[2]}" ]] || conclude_error "Invalid absolute URL: '$1'"
}

# Extract Origin from absolute URL: Only scheme, host and port (if non-default)
url_origin() {
  url_parse "$1"
  local -r scheme="${BASH_REMATCH[2]}"
  [[ -v url_scheme_ports["$scheme"] ]] || conclude_error "Unknown scheme '$scheme'"
  local port="${BASH_REMATCH[6]}"
  [[ -z $port || $port != ":${url_scheme_ports["$scheme"]}" ]] || port=""
  echo -n "$scheme://${BASH_REMATCH[5]}$port"
}

# Make Referer header from absolute URL: Path contains at least "/", no userinfo, no port if default
url_referer() {
  url_origin "$1"
  echo -n "${BASH_REMATCH[9]:-/}${BASH_REMATCH[10]}"
}

# Determine if two absolute URLs are same-origin, same-site or cross-site
url_relationship() {
  url_parse "$1"
  local -r a_scheme="${BASH_REMATCH[2]}"
  local -r a_host="${BASH_REMATCH[5]}"
  local -r a_port="${BASH_REMATCH[7]}"
  url_parse "$2"
  local -r b_scheme="${BASH_REMATCH[2]}"
  local -r b_host="${BASH_REMATCH[5]}"
  local -r b_port="${BASH_REMATCH[7]}"

  if [[ $a_scheme != "$b_scheme" || $a_host != "$b_host" ]]; then
    echo "cross-site"
    return 0
  elif [[ $a_port == "$b_port" ]]; then
    echo "same-origin"
    return 0
  fi

  if [[ -z $a_port || -z $b_port ]]; then
    [[ -v url_scheme_ports["$a_scheme"] ]] || conclude_error "Unknown scheme '$a_scheme'"
    if [[ ${a_port:-${url_scheme_ports["$a_scheme"]}} == "${b_port:-${url_scheme_ports["$b_scheme"]}}" ]]; then
      echo "same-origin"
      return 0
    fi
  fi

  echo "same-site"
}

 

[xpad.c]

WENN man also genau die Anforderungen hat dass es Dezimalzahlen sein müssen, einen sehr kleinen Definitionsbereich, die gleichmäßigst-mögliche Verteilung und es soll nach viel Diffusion aussehen weil der Algorithmus so mysteriös ist, aber keine Eigenschaften braucht die einen Hash zum Hash machen... dann ist die Lösung vom OP womöglich das Mittel der Wahl.

OK, ersetze WENN durch FALLS, und ich gehe mit.
Allein, ich bezweifle, dass das hier tatsächlich der Fall ist, aber das habe ich ja schon mehrfach geschrieben.

xpad.c

 

[CyborgBeta]

Hier ist das Bash-Script:

Ich habe noch ein wenig "optimiert" und aufgeräumt:

#!/bin/bash
myhash () {
  s=${1}aaaa
  s=${s:0:4}
  a=$(printf '%d' "'a")  # ordinal of 'a'
  hash=0
  multiplier=1
  for i in {0..3};
  do
    j=$(printf '%d' "'${s:$i:1}")  # ordinal of ith char
    hash=$((hash+(multiplier*(j-a)*961)))
    multiplier=$((multiplier*26))
  done
  hash=$((((10000*hash)/456976)%10000))
  printf '%04d\n' "$hash"
}

 

[KitKat::new()]

Das grundlegend selbe Problem wie bei der Modulovariante.

Ich habe mir mal die Mühe gemacht und die jeweiligen Probleme veranschaulicht, sh. Anhang.
Ich sehe da bzgl. Gleichverteilung bei Modulo ein zusätzliches Problem ;-)

1. kleinere Zahlen... rand, scaled, mod (Zufallzahlen: 2^8, intervall: [0;111[, 1 M Samples)

2. größere Zahlen... rand_big, scaled_big, mod_big (zufallszahlen: 2^16, intervall: [0;10 000[, 10 M Samples)

Bei den größeren sieht man z.B. optisch gar keinen Unterschied mehr zwischen der skalierten und originalen Zufallszahlen, während bei mod_big noch eine starke Ungleichverteilung zu erkennen ist.

 

[simpsonsfan]

@KitKat::new() +1 für die Mühe.
Die großen svg Dateien habe ich gerade verpasst. Waren die zu kompliziert zum Rendern oder hast du die jetzt extra durch rausgezoomte jpg ersetzt, bei denen die Lücken mangels Auflösung nicht sichtbar sind?
Ehrlich gesagt sieht die Verteilung histogramm_scaled.svg ja wirklich gleichmäßiger aus als histogramm_mod.svg. Aber trotzdem haben dort 34 Werte eine höhere Häufigkeit als die restlichen ungefähr 76 Werte. GGf. ist es schlechter, wenn die Häufigkeit sich auch noch auf einen Bereich konzentriert. Das Problem der ungleichen Häufigkeit hat man in beiden Fällen grundsätzlich. (Dort, wo eine ungleiche Häufigkeit ein Problem darstellt.)

 

[KitKat::new()]

Ich hab die svgs gerendert, weil ich sie im Forum sonst nicht als Bilder zeigen konnte.
Ich füge sie hier nochmal ein

 

[CyborgBeta]

Hmm, mein Bauchgefühl sagt mir, dass histogramm_scaled (und auch histogramm_scaled_big) weniger Blockbildung haben sollte, also weniger zusammenstehende Bereiche, damit

Chaos oder Lawineneffekt

(Die Hashfunktion soll eine gute Diffusion besitzen; ähnliche Quellelemente (Eingabewerte) sollen zu völlig verschiedenen Hashwerten führen.)

s. https://de.wikipedia.org/wiki/Hashfunktion#Kriterien

besser erfüllt wäre.

Aber verifizieren oder gar beweisen kann ich das nicht.

Praktisch würde das vermutlich bedeuten, dass * 961 zu klein gewählt ist ... imho, distribuiert * 961 "ähnliche bzw. benachbarte" Eingaben zu wenig.

Aber na ja, ich bin kein Mathe-Prof.

 

[foofoobar]

80% der Lösung liefern. Die Beiden waren bestimmt schon in der Schule diese Streber die in der ersten Reihe sitzend immer den Arm oben hatten und dazu noch laut schnipsten..

((26**4)%(10**4)) != 0

Das ist der Grund wieso ich da eine Hausaufgabe vermute.

Who cares?

 

[CyborgBeta]

@foofoobar mod((26^4)*(10^4)/(26^4); 10^4) == 0, aber who cares? 🤷‍♂️ Vielleicht etwas weniger hier antworten ...

 

[foofoobar]

@CyborgBeta

x/x == 1

ist nix neues. Und

y%y == 0

auch.

So geschrieben sticht das besser ins Auge:

mod((26^4)/(26^4)*(10^4); 10^4)

Oder welche andere Botschaft hast du mir versucht zu senden?

 

[simpsonsfan]

Ich füge sie hier nochmal ein

Besten Dank.
Dann füge ich hier noch ein, wie die Verteilung aussieht, wenn man den Rand der Baken entfernt und noch eine Linie mit der durchschnittlichen Häufigkeit einzieht.

 

[TomH22]

Ich bewundere die Ausdauer, mit der ihr euch weiterhin die Köpfe zerbrecht, wie man diese merkwürdige Aufgabenstellung lösen könnte.

War am Sonntag eh am Rechner und das Forum ist für mich manchmal eine Art "Übersprunghandlung" wenn ich bei meinem eigentlichen Problem nicht weiterkomme.

Ich möchte erneut die Frage ins Spiel bringen, wieso das überhaupt in diesen Wertebereich muss? Vermutlich will der OP damit irgendwie weiterrechnen, aber was kann es denn bitte für eine Rechnung geben, die nicht auch mit einer n-bit Zahl in Hex-Schreibweise funktionieren würde?

Das ist mir bisher auch ein Rätsel. Zumal z.B. ein 4 Zeichen lange ASCII String in ein 32 Bit Wort passt, mal spart also noch nicht mal Speicher, und da es um ein Bash Script geht, kann das auch kein Grund sein.

Aber die etwas generalisierte Aufgabe, einen String auf eine relativ kleinen Integer abzubilden wird ja z.B. für die Implementierung klassischer Hash Tabellen genutzt. Und bei der Recherche dazu bin auch auf FNV-1 bzw 1a gestossen. Dies sind explizit nicht als kryptographische Hashes geeignet, aber für Hashtabellen und Prüfsummen. Vor Version 3.4 hat wohl Python auch eine Variante von FNV1 benutzt, mittlerweile nutzt es SipHash.

Bei dieser Begründung hat ChatGPT Dich offenbar kackdreist angelogen, denn 33 ist keine Primzahl.

Ja, ChatGPT hast sich da wohl verrechnet, als ich es angewiesen habe die 32Bit Version auf 13Bit runter zu skalieren, mir ist es nicht aufgefallen, obwohl es bei 33 eigentlich schon fast ins Auge springt
Mir ging es aber auch mehr darum, den TE in die Richtung zu lenken, sich etablierte Verfahren anzuschauen, anstatt sich irgendwas komisches auszudenken.

Aber ChatGPT ist ja auch niemals um eine Ausrede verlegen:

Das ist der Grund wieso ich da eine Hausaufgabe vermute.

Der eingeschränkte Wertebereich von aaaa->zzzz spricht dafür, denn der lässt sich noch einfach komplett durchrechnen.

Hier die Verteilung der Hash Werte für den Wertebereich des TE von FNV-1a 13 Bit mit der "falschen" Primzahl 33 und der nächsten echten Primzahl 37:

Man sieht schön, dass es mit einer Primzahl besser geht...

Das Programm dazu habe ich auch ChatGPT generieren lassen, habe diesmal etwas genauer hingeschaut und hoffe keine Fehler übersehen.

import itertools
import string
import matplotlib.pyplot as plt

# Generate all 4-letter combinations of lowercase a-z
test_inputs = [''.join(chars) for chars in itertools.product(string.ascii_lowercase, repeat=4)]

# FNV-1a 13-bit hash function
def fnv1a_13bit(s, prime):
    hash_val = 0x11C
    mask = 0x1FFF
    for c in s:
        hash_val ^= ord(c)
        hash_val = (hash_val * prime) & mask
    return hash_val

# Compute hash distributions
def compute_distribution(prime):
    distribution = [0] * 8192
    for s in test_inputs:
        h = fnv1a_13bit(s, prime)
        distribution[h] += 1
    return distribution

# Plot distributions
def plot_distributions(dist_33, dist_37):
    plt.figure(figsize=(14, 6))

    plt.subplot(1, 2, 1)
    plt.bar(range(8192), dist_33, width=1)
    plt.title('FNV-1a 13-bit Hash Distribution (Multiplier 33)')
    plt.xlabel('Hash Value')
    plt.ylabel('Frequency')

    plt.subplot(1, 2, 2)
    plt.bar(range(8192), dist_37, width=1, color='orange')
    plt.title('FNV-1a 13-bit Hash Distribution (Multiplier 37)')
    plt.xlabel('Hash Value')
    plt.ylabel('Frequency')

    plt.tight_layout()
    plt.show()

# Compute distributions
dist_33 = compute_distribution(33)
dist_37 = compute_distribution(37)

# Plot the results
plot_distributions(dist_33, dist_37)

 

[CyborgBeta]

Dann füge ich hier noch ein, wie die Verteilung aussieht, wenn man den Rand der Baken entfernt und noch eine Linie mit der durchschnittlichen Häufigkeit einzieht.

Uff, dafür braucht man im Dark Mode gute Augen ...

Ergänzung (15. April 2025)

Oder welche andere Botschaft hast du mir versucht zu senden?

Ja, genau die. Ich glaube, ich habe dich erst missverstanden. 🤷‍♂️