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

[BeBur]

Dein Bash-Skript:

Das wäre zu einfach und so gar nicht besonders, es muss schon was ganz besonderes sein.

Aber der Ablauf ist "hier" ganz normal. Wirre Anforderungen, Klärung nicht möglich, Lösungen gefallen nicht, am Ende irgendein Eigenbau, der natürlich ganz toll und genau richtig ist.
Ich schreibe in solche Threads für mich und für den Austausch unter Gleichgesinnten. TE macht das im Prinzip auch so, dass hier ein Dialog mit anderen stattfindet der irgendeine Fragestellung behandelt ist im Prinzip nur Show. Du darfst halt nicht erwarten, dass eine sinnvolle Lösung erarbeitet wird, sondern nur, dass sich noch weitere Dritte einfinden, mit denen gut zu einem Thema diskutieren kannst

 

[foofoobar]

Suchst du sowas: https://www.gnu.org/software/gperf/

 

[CyborgBeta]

was man machen bzw. lassen sollte und warum

Ich glaube, dich interessiert meine Frage gar nicht, bzw. dir kommt es nicht darauf an, was richtig ist, sondern nur, was deiner Meinung nach richtig sei.

 

[foofoobar]

Naja...
Ist jetzt zwar nicht extrem unterschiedlich, aber die Häufigkeiten bewegen sich immerhin zwischen 1685 und 1929.

Wahrscheinlich würde sich das mit einer größeren Eingabemenge weiter angleichen.
Bei kleinen Stichproben sind auch die Abweichungen größer.

 

[CyborgBeta]

@foofoobar Eigentlich bräuchte ich nur folgendes Verfahren als Bash-Script:

    public static String hashCode2(String s) {
        if (s.length() < 4) {
            s += "a".repeat(4 - s.length());
        }

        // fisher yates shuffle
        int[] indices = {0, 1, 1, 0};
        char[] chars = new char[4];
        for (int i = 0; i < 4; i++) {
            int j = indices[i];
            chars[i] = s.charAt(i);
            chars[i] = chars[j];
            chars[j] = s.charAt(i);
        }
        s = new String(chars);

        int hash = 0;
        int multiplier = 1;
        for (int i = 0; i < 4; i++) {
            hash += multiplier * (s.charAt(i) - 'a');
            multiplier *= 26;
        }
        return String.format("%04d", (int) (10_000 / Math.pow(26, 4) * hash));
    }

Aber das bekomme ich wahrscheinlich auch selber hin.

Ergänzung (12. April 2025)

Wahrscheinlich würde sich das mit einer größeren Eingabemenge weiter angleichen.

Du hattest doch schon alle Kombinationen aus vier Buchstaben aus a-z gewählt ...

Ergänzung (12. April 2025)

Suchst du sowas: https://www.gnu.org/software/gperf/

Ich glaube, ich suche eher das:

https://en.wikipedia.org/wiki/Perfect_hash_function#k-perfect_hashing

 

[xpad.c]

Ich glaube, dich interessiert meine Frage gar nicht, bzw. dir kommt es nicht darauf an, was richtig ist, sondern nur, was deiner Meinung nach richtig sei.

EIN Geisterfahrer?! HUNDERTE!1!elf

 

[foofoobar]

Du hattest doch schon alle Kombinationen aus vier Buchstaben aus a-z gewählt ...

In 4 Bytes passt mehr als 26**4 Möglichkeiten.

Ich glaube

Dann wundert sich jetzt niemand mehr über deine "Anforderung".

 

[0x8100]

@foofoobar Eigentlich bräuchte ich nur folgendes Verfahren als Bash-Script:

        // fisher yates shuffle
        int[] indices = {0, 1, 1, 0};
        char[] chars = new char[4];
        for (int i = 0; i < 4; i++) {
            int j = indices[i];
            chars[i] = s.charAt(i);
            chars[i] = chars[j];
            chars[j] = s.charAt(i);
        }

https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

j soll also ein random wert sein, kommt bei dir aber aus einem definierten array. da kann man auch gleich die referenzimplementierung nehmen:

deswegen macht man keine eigene crypto.

 

[CyborgBeta]

Ok, ich sehe schon, diese Frage könnt ihr schlicht nicht beantworten. Auch gut (wenn auch etwas nervig, immer angefeindet zu werden).

Ergänzung (12. April 2025)

In 4 Bytes passt mehr als 26**4 Möglichkeiten.

Dann lies das Thema vielleicht noch mal ...

 

[xpad.c]

https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

Es sei insbesondere auf den Abschnitt https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Modulo_bias verwiesen.

deswegen macht man keine eigene crypto.

Auch schön: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Implementation_errors

xpad.c

 

[CyborgBeta]

@0x8100 Die Indizes dürfen doch nicht zufällig sein, sonst wäre die Funktion nicht mehr replizierbar.

 

[xpad.c]

Ok, ich sehe schon, diese Frage könnt ihr schlicht nicht beantworten. Auch gut (wenn auch etwas nervig, immer angefeindet zu werden).

Teil 1 könnte damit zusammenhängen, dass die Frage so wie gestellt nicht nur von den Anwesenden, sondern generell überhaupt nicht beantwortet werden kann.

Teil 2... ja, lass mal überlegen.
Du stellst eine Frage mit sehr besonderen Anforderungen, bekommst Antworten, die Dir nicht gefallen, aus $Gründen.
Auf die Frage nach dem Sinn kommst Du mit Begründungen, die die Anforderungen gar nicht rechtfertigen.
Mehr als eine Person teil Dir mit, dass, und vor allem auch WARUM das so nicht sinnvoll ist.
Du fasst die ganze Diskussion als Anfeindung zusammen.

Passt. plonk

 

[CyborgBeta]

Ok, ich will (aus (noch) nicht näher genannten Gründen) eine kryptografisch sichere (oder starke) Hashfunktion haben, die den eingangs erwähnten Anforderungen entspricht, die es bislang aber noch nicht gibt.

Besser?

Und ich habe auch nicht behauptet, dass ich absoluter Experte auf diesem Gebiet sei ... aber durch den Verlauf dieser Diskussion sollte sich doch langsam herausgestellt haben, dass es noch nichts "fertiges" dafür gibt, oder nicht?

Für sha... ist die Eingabemenge zu klein.

 

[BeBur]

Also für mich passt das so mit deiner Implementierung.

 

[CyborgBeta]

Juhu. Hier ist das Bash-Script:

#!/bin/bash
# chr() - converts decimal value to its ASCII character representation
# ord() - converts ASCII character to its decimal value
chr() {
  printf \\$(printf '%03o' "$1")
}
ord() {
  printf '%d' "'$1"
}
round() {
  printf "%.${2}f" "${1}"
}
my_hash_4 () {
  s=$1
  while (( ${#s} < 4 ));
  do
    s="${s}a"
  done
  hash=0
  multiplier=1
  for i in $(seq 0 3);
  do
    j=$(ord "${s:$i:1}")
    hash=$((hash+(multiplier*(j-97)*961)))
    multiplier=$((multiplier*26))
  done
  # (int) (10_000 / Math.pow(26, 4) * hash) % 10_000
  hash=$(bc -l <<< "scale=0; ( 10000 * $hash ) / 456976")
  hash=$((hash%10000))
  printf '%04d\n' "$hash"
}
my_hash_4 "$1"

Dabei wird die chr() und round() Funktion nicht verwendet, und kann eigentlich raus.

Das Ergebnis ist:

bash script_my_hash.sh aaaa
0000

bash script_my_hash.sh baaa
0021

bash script_my_hash.sh abaa
0546

bash script_my_hash.sh bbaa
0567

bash script_my_hash.sh zzzz
9978

bash script_my_hash.sh hallo
2292

also äquivalent zu dem Java-Code ...

Habe ich jetzt noch etwas Wichtiges übersehen, oder passt alles?

Ergänzung (13. April 2025)

Haha, es geht sogar ohne das blöd bc -l (also ohne float), weil die Bash mit 64-bit Ints rechnet!:

#!/bin/bash
# ord() - converts ASCII character to its decimal value
ord() {
  printf '%d' "'$1"
}
my_hash_4 () {
  s=$1
  while (( ${#s} < 4 ));
  do
    s="${s}a"
  done
  hash=0
  multiplier=1
  for i in $(seq 0 3);
  do
    j=$(ord "${s:$i:1}")
    hash=$((hash+(multiplier*(j-97)*961)))
    multiplier=$((multiplier*26))
  done
  # (int) (10_000 / Math.pow(26, 4) * hash) % 10_000
  hash=$((((10000000*hash)/456976000)%10000))
  printf '%04d\n' "$hash"
}
my_hash_4 "$1"

Das Ergebnis ist gleich.

 

[TomH22]

Jetzt musst Du nur noch beweisen, dass Deine Hash Funktion Deine in Beitrag 11 genannten Anforderungen erfüllt.
Intuitiv würde ich sagen, sie tut es nicht, den der Hashwert ist extrem von der Summe der ASCII Werte der Eingabe abhängig, siehe 0000 für aaaa und 9978 für zzzz.

 

[foofoobar]

@TomH22 Kollisionsresistent ist es jedenfalls nicht, aber die gewünschten Eigenschaften hat der TO ja später mit den Attributen "eigentlich" und "glauben" versehen.

 

[CyborgBeta]

"eigentlich" und "glauben"

Was stört dich an meiner Ausdrucksweise?

Kollisionsresistent ist es jedenfalls nicht

Doch doch.

 

[0x8100]

wenn dein algo solche schönen regelmässigkeiten produziert, dann stimmt da was nicht.

aaaa 0000
aaab 9615
aaac 9230
aaad 8846
aaae 8461
aaaf 8076
--
azoh 0000
azoi 9615
azoj 9231
azok 8846
azol 8462
azom 8077
--
bkhn 0000
bkho 9615
bkhp 9231
bkhq 8846
bkhr 8462
bkhs 8077
--
cvzs 0000
cvzt 9615
cvzu 9231
cvzv 8846
cvzw 8462
cvzx 8077
--
dgsy 0000
dgsz 9615
dgta 3447
dgtb 3062
dgtc 2678
dgtd 2293
--
erke 0000
erkf 9615
erkg 9231
erkh 8846
erki 8462
erkj 8077
--
fcdk 0000
fcdl 9615
fcdm 9231
fcdn 8846
fcdo 8461
fcdp 8077
--
gnvp 0000
gnvq 9615
gnvr 9231
gnvs 8846
gnvt 8461
gnvu 8077
--
hxcd 0000
hxce 9616
hxcf 9231
hxcg 8847
hxch 8462
hxci 8077
--
hynv 0000
hynw 9615
hynx 9231
hyny 8846
hynz 8461
hyoa 2293
--
iivi 0000
iivj 9616
iivk 9231
iivl 8847
iivm 8462
iivn 8077
--
ijgb 0000
ijgc 9615
ijgd 9231
ijge 8846
ijgf 8461
ijgg 8077
--
jtno 0000
jtnp 9616
jtnq 9231
jtnr 8847
jtns 8462
jtnt 8077
--
juyg 0000
juyh 9615
juyi 9231
juyj 8846
juyk 8461
juyl 8077
--
kegu 0000
kegv 9616
kegw 9231
kegx 8847
kegy 8462
kegz 8077
--
kfrm 0000
kfrn 9615
kfro 9231
kfrp 8846
kfrq 8461
kfrr 8077
--
lpyz 0000
lpza 3832
lpzb 3447
lpzc 3063
lpzd 2678
lpze 2293
--
lqjs 0000
lqjt 9615
lqju 9231
lqjv 8846
lqjw 8461
lqjx 8077
--
marf 0000
marg 9616
marh 9231
mari 8847
marj 8462
mark 8077
--
mbcy 0000
mbcz 9615
mbda 3447
mbdb 3062
mbdc 2677
mbdd 2293
--
nljl 0000
nljm 9616
nljn 9231
nljo 8847
nljp 8462
nljq 8077
--
nmud 0000
nmue 9615
nmuf 9231
nmug 8846
nmuh 8461
nmui 8077
--
owbr 0000
owbs 9616
owbt 9231
owbu 8846
owbv 8462
owbw 8077
--
oxmj 0000
oxmk 9615
oxml 9231
oxmm 8846
oxmn 8461
oxmo 8077
--
phuw 0000
phux 9616
phuy 9231
phuz 8846
phva 2678
phvb 2293
--
pifp 0000
pifq 9615
pifr 9231
pifs 8846
pift 8461
pifu 8077
--
qsmc 0000
qsmd 9616
qsme 9231
qsmf 8846
qsmg 8462
qsmh 8077
--
qtxu 0000
qtxv 9615
qtxw 9230
qtxx 8846
qtxy 8461
qtxz 8077
--
rdfi 0000
rdfj 9616
rdfk 9231
rdfl 8846
rdfm 8462
rdfn 8077
--
reqa 0000
reqb 9615
reqc 9230
reqd 8846
reqe 8461
reqf 8077
--
soxn 0000
soxo 9616
soxp 9231
soxq 8846
soxr 8462
soxs 8077
--
spig 0000
spih 9615
spii 9230
spij 8846
spik 8461
spil 8077
--
tabm 0000
tabn 9615
tabo 9230
tabp 8846
tabq 8461
tabr 8077
--
tzpt 0000
tzpu 9616
tzpv 9231
tzpw 8846
tzpx 8462
tzpy 8077
--
ukiz 0000
ukja 3832
ukjb 3447
ukjc 3062
ukjd 2678
ukje 2293
--
ultr 0000
ults 9615
ultt 9230
ultu 8846
ultv 8461
ultw 8077
--
vvaf 0000
vvag 9616
vvah 9231
vvai 8846
vvaj 8462
vvak 8077
--
vwlx 0000
vwly 9615
vwlz 9230
vwma 3062
vwmb 2677
vwmc 2293
--
wgtk 0000
wgtl 9616
wgtm 9231
wgtn 8846
wgto 8462
wgtp 8077
--
whed 0000
whee 9615
whef 9230
wheg 8846
wheh 8461
whei 8077
--
xrlq 0000
xrlr 9616
xrls 9231
xrlt 8846
xrlu 8462
xrlv 8077
--
xswi 0000
xswj 9615
xswk 9230
xswl 8846
xswm 8461
xswn 8076
--
ycew 0000
ycex 9615
ycey 9231
ycez 8846
ycfa 2678
ycfb 2293
--
ydpo 0000
ydpp 9615
ydpq 9230
ydpr 8846
ydps 8461
ydpt 8076
--
znwb 0000
znwc 9615
znwd 9231
znwe 8846
znwf 8462
znwg 8077
--
zohu 0000
zohv 9615
zohw 9230
zohx 8846
zohy 8461
zohz 8076

 

[CyborgBeta]

Was bedeutet denn für dich "Regelmäßigkeiten" und wieso ist das ein Problem?

Es ist doch klar, dass es Kollisionen geben muss, weil die Eingabemenge größer als die Ausgabemenge ist.

Wenn der Hashcode zum Beispiel 0000 ist, dann lässt sich der genaue Ursprungswert doch nicht rekonstruieren. Nur die Menge möglicher Eingaben, aber das hast du doch bei anderen Hashfunktionen auch? 🤔