Bash Einweg-Hashfunktion programmieren, die feste Ausgabelänge hat und pseudozufällig ist
- Ersteller CyborgBeta
- Erstellt am
0x8100
Fleet Admiral
- Registriert
- Okt. 2015
- Beiträge
- 10.953
ich zitiere einfach mal deine eigene anforderung:CyborgBeta schrieb:
CyborgBeta schrieb:
das ist hier ja wohl ganz klar nicht gegeben. dein output wiederholt sich ständig (und als weitere regelmässigkeit wird der hash-wert in jedem block immer nur kleiner), es ist möglich von einem "hash" auf vorherige werte zurückzuschliessen.
Code:
aaaa 0000 awki 1111 atgj 2222
aaab 9615 awkj 0727 atgk 1838
aaac 9230 awkk 0342 atgl 1453
aaad 8846 awkl 9957 atgm 1069
aaae 8461 awkm 9573 atgn 0684
aaaf 8076 awkn 9188 atgo 0299
-- -- --
azoh 0000 axva 1111 aurb 2222
azoi 9615 axvb 0726 aurc 1837
azoj 9231 axvc 0341 aurd 1453
azok 8846 axvd 9957 aure 1068
azol 8462 axve 9572 aurf 0683
azom 8077 axvf 9188 aurg 0299
-- -- --
bkhn 0000 bhdo 1111 bezo 2222
bkho 9615 bhdp 0727 bezp 1838
bkhp 9231 bhdq 0342 bezq 1453
bkhq 8846 bhdr 9957 bezr 1069
bkhr 8462 bhds 9573 bezs 0684
bkhs 8077 bhdt 9188 bezt 0299
-- -- --
cvzs 0000 biog 1111 bfkh 2222
cvzt 9615 bioh 0726 bfki 1837
cvzu 9231 bioi 0341 bfkj 1453
cvzv 8846 bioj 9957 bfkk 1068
cvzw 8462 biok 9572 bfkl 0683
cvzx 8077 biol 9188 bfkm 0299
-- -- --
dgsy 0000 csvt 1111 cpru 2222
dgsz 9615 csvu 0727 cprv 1838
dgta 3447 csvv 0342 cprw 1453
dgtb 3062 csvw 9957 cprx 1069
dgtc 2678 csvx 9573 cpry 0684
dgtd 2293 csvy 9188 cprz 0299
-- -- --
erke 0000 ctgm 1111 cqcn 2222
erkf 9615 ctgn 0726 cqco 1837
erkg 9231 ctgo 0341 cqcp 1453
erkh 8846 ctgp 9957 cqcq 1068
erki 8462 ctgq 9572 cqcr 0683
erkj 8077 ctgr 9188 cqcs 0299
-- -- --
fcdk 0000 ddoz 1111 daka 2222
fcdl 9615 ddpa 4943 dakb 1838
fcdm 9231 ddpb 4558 dakc 1453
fcdn 8846 ddpc 4173 dakd 1069
fcdo 8461 ddpd 3789 dake 0684
fcdp 8077 ddpe 3404 dakf 0299
-- -- --
gnvp 0000 dezr 1111 dbvs 2222
gnvq 9615 dezs 0726 dbvt 1837
gnvr 9231 dezt 0341 dbvu 1453
gnvs 8846 dezu 9957 dbvv 1068
gnvt 8461 dezv 9572 dbvw 0683
gnvu 8077 dezw 9188 dbvx 0299
-- -- --
hxcd 0000 eogf 1111 elcg 2222
hxce 9616 eogg 0727 elch 1838
hxcf 9231 eogh 0342 elci 1453
hxcg 8847 eogi 9957 elcj 1068
hxch 8462 eogj 9573 elck 0684
hxci 8077 eogk 9188 elcl 0299
-- -- --
hynv 0000 eprx 1111 emny 2222
hynw 9615 epry 0726 emnz 1837
hynx 9231 eprz 0341 emoa 5669
hyny 8846 epsa 4173 emob 5284
hynz 8461 epsb 3788 emoc 4899
hyoa 2293 epsc 3403 emod 4515
-- -- --
iivi 0000 fakd 1111 fwul 2222
iivj 9616 fake 0726 fwum 1838
iivk 9231 fakf 0341 fwun 1453
iivl 8847 fakg 9957 fwuo 1068
iivm 8462 fakh 9572 fwup 0684
iivn 8077 faki 9187 fwuq 0299
-- -- --
ijgb 0000 fzyk 1111 fxfe 2222
ijgc 9615 fzyl 0727 fxff 1837
ijgd 9231 fzym 0342 fxfg 1453
ijge 8846 fzyn 9957 fxfh 1068
ijgf 8461 fzyo 9573 fxfi 0683
ijgg 8077 fzyp 9188 fxfj 0299
-- -- --
jtno 0000 gkrq 1111 ghnr 2222
jtnp 9616 gkrr 0726 ghns 1838
jtnq 9231 gkrs 0342 ghnt 1453
jtnr 8847 gkrt 9957 ghnu 1068
jtns 8462 gkru 9573 ghnv 0684
jtnt 8077 gkrv 9188 ghnw 0299
-- -- --
juyg 0000 glcj 1111 giyj 2222
juyh 9615 glck 0726 giyk 1837
juyi 9231 glcl 0341 giyl 1452
juyj 8846 glcm 9957 giym 1068
juyk 8461 glcn 9572 giyn 0683
juyl 8077 glco 9187 giyo 0299
-- -- --
kegu 0000 hvjw 1111 hsfx 2222
kegv 9616 hvjx 0726 hsfy 1838
kegw 9231 hvjy 0342 hsfz 1453
kegx 8847 hvjz 9957 hsga 5284
kegy 8462 hvka 3789 hsgb 4900
kegz 8077 hvkb 3404 hsgc 4515
-- -- --
kfrm 0000 hwuo 1111 htqp 2222
kfrn 9615 hwup 0726 htqq 1837
kfro 9231 hwuq 0341 htqr 1452
kfrp 8846 hwur 9957 htqs 1068
kfrq 8461 hwus 9572 htqt 0683
kfrr 8077 hwut 9187 htqu 0299
-- -- --
lpyz 0000 igcc 1111 idyc 2222
lpza 3832 igcd 0726 idyd 1838
lpzb 3447 igce 0342 idye 1453
lpzc 3063 igcf 9957 idyf 1068
lpzd 2678 igcg 9573 idyg 0684
lpze 2293 igch 9188 idyh 0299
-- -- --
lqjs 0000 jruh 1111 iejv 2222
lqjt 9615 jrui 0726 iejw 1837
lqju 9231 jruj 0342 iejx 1452
lqjv 8846 jruk 9957 iejy 1068
lqjw 8461 jrul 9573 iejz 0683
lqjx 8077 jrum 9188 ieka 4515
-- -- --
marf 0000 kcnn 1111 joqi 2222
marg 9616 kcno 0726 joqj 1838
marh 9231 kcnp 0342 joqk 1453
mari 8847 kcnq 9957 joql 1068
marj 8462 kcnr 9573 joqm 0684
mark 8077 kcns 9188 joqn 0299
-- -- --
mbcy 0000 lnft 1111 jpbb 2222
mbcz 9615 lnfu 0726 jpbc 1837
mbda 3447 lnfv 0342 jpbd 1452
mbdb 3062 lnfw 9957 jpbe 1068
mbdc 2677 lnfx 9573 jpbf 0683
mbdd 2293 lnfy 9188 jpbg 0299
-- -- --
nljl 0000 myxy 1111 kaug 2222
nljm 9616 myxz 0726 kauh 1837
nljn 9231 myya 4558 kaui 1452
nljo 8847 myyb 4173 kauj 1068
nljp 8462 myyc 3788 kauk 0683
nljq 8077 myyd 3404 kaul 0299
-- -- --
nmud 0000 njqe 1111 kzio 2222
nmue 9615 njqf 0726 kzip 1838
nmuf 9231 njqg 0342 kziq 1453
nmug 8846 njqh 9957 kzir 1068
nmuh 8461 njqi 9572 kzis 0684
nmui 8077 njqj 9188 kzit 0299
-- -- --
owbr 0000 ouik 1111 lkbu 2222
owbs 9616 ouil 0726 lkbv 1838
owbt 9231 ouim 0342 lkbw 1453
owbu 8846 ouin 9957 lkbx 1068
owbv 8462 ouio 9572 lkby 0684
owbw 8077 ouip 9188 lkbz 0299
-- -- --
oxmj 0000 peqx 1111 llmm 2222
oxmk 9615 peqy 0727 llmn 1837
oxml 9231 peqz 0342 llmo 1452
oxmm 8846 pera 4174 llmp 1068
oxmn 8461 perb 3789 llmq 0683
oxmo 8077 perc 3404 llmr 0299
-- -- --
phuw 0000 pfbq 1111 mvtz 2222
phux 9616 pfbr 0726 mvua 6054
phuy 9231 pfbs 0342 mvub 5669
phuz 8846 pfbt 9957 mvuc 5284
phva 2678 pfbu 9572 mvud 4900
phvb 2293 pfbv 9188 mvue 4515
-- -- --
pifp 0000 qpid 1111 mwes 2222
pifq 9615 qpie 0727 mwet 1837
pifr 9231 qpif 0342 mweu 1452
pifs 8846 qpig 9958 mwev 1068
pift 8461 qpih 9573 mwew 0683
pifu 8077 qpii 9188 mwex 0299
-- -- --
qsmc 0000 qqtv 1111 ngmf 2222
qsmd 9616 qqtw 0726 ngmg 1838
qsme 9231 qqtx 0342 ngmh 1453
qsmf 8846 qqty 9957 ngmi 1068
qsmg 8462 qqtz 9572 ngmj 0684
qsmh 8077 qqua 3404 ngmk 0299
-- -- --
qtxu 0000 rabj 1111 nhxx 2222
qtxv 9615 rabk 0727 nhxy 1837
qtxw 9230 rabl 0342 nhxz 1452
qtxx 8846 rabm 9958 nhya 5284
qtxy 8461 rabn 9573 nhyb 4899
qtxz 8077 rabo 9188 nhyc 4514
-- -- --
rdfi 0000 rbmb 1111 orel 2222
rdfj 9616 rbmc 0726 orem 1837
rdfk 9231 rbmd 0342 oren 1453
rdfl 8846 rbme 9957 oreo 1068
rdfm 8462 rbmf 9572 orep 0684
rdfn 8077 rbmg 9188 oreq 0299
-- -- --
reqa 0000 slto 1111 ospd 2222
reqb 9615 sltp 0727 ospe 1837
reqc 9230 sltq 0342 ospf 1452
reqd 8846 sltr 9958 ospg 1068
reqe 8461 slts 9573 osph 0683
reqf 8077 sltt 9188 ospi 0298
-- -- --
soxn 0000 smeh 1111 pcxq 2222
soxo 9616 smei 0726 pcxr 1837
soxp 9231 smej 0342 pcxs 1453
soxq 8846 smek 9957 pcxt 1068
soxr 8462 smel 9572 pcxu 0684
soxs 8077 smem 9188 pcxv 0299
-- -- --
spig 0000 twlu 1111 pdij 2222
spih 9615 twlv 0727 pdik 1837
spii 9230 twlw 0342 pdil 1452
spij 8846 twlx 9958 pdim 1068
spik 8461 twly 9573 pdin 0683
spil 8077 twlz 9188 pdio 0298
-- -- --
tabm 0000 txwm 1111 qnpw 2222
tabn 9615 txwn 0726 qnpx 1837
tabo 9230 txwo 0342 qnpy 1453
tabp 8846 txwp 9957 qnpz 1068
tabq 8461 txwq 9572 qnqa 4900
tabr 8077 txwr 9188 qnqb 4515
-- -- --
tzpt 0000 uhea 1111 ryhc 2222
tzpu 9616 uheb 0727 ryhd 1837
tzpv 9231 uhec 0342 ryhe 1453
tzpw 8846 uhed 9958 ryhf 1068
tzpx 8462 uhee 9573 ryhg 0684
tzpy 8077 uhef 9188 ryhh 0299
-- -- --
ukiz 0000 uips 1111 sjai 2222
ukja 3832 uipt 0726 sjaj 1837
ukjb 3447 uipu 0342 sjak 1453
ukjc 3062 uipv 9957 sjal 1068
ukjd 2678 uipw 9572 sjam 0684
ukje 2293 uipx 9188 sjan 0299
-- -- --
ultr 0000 vswf 1111 tusn 2222
ults 9615 vswg 0727 tuso 1837
ultt 9230 vswh 0342 tusp 1453
ultu 8846 vswi 9958 tusq 1068
ultv 8461 vswj 9573 tusr 0684
ultw 8077 vswk 9188 tuss 0299
-- -- --
vvaf 0000 vthy 1111 uflt 2222
vvag 9616 vthz 0726 uflu 1837
vvah 9231 vtia 4558 uflv 1453
vvai 8846 vtib 4173 uflw 1068
vvaj 8462 vtic 3788 uflx 0684
vvak 8077 vtid 3404 ufly 0299
-- -- --
vwlx 0000 wdpl 1111 vqdz 2222
vwly 9615 wdpm 0727 vqea 6053
vwlz 9230 wdpn 0342 vqeb 5669
vwma 3062 wdpo 9957 vqec 5284
vwmb 2677 wdpp 9573 vqed 4899
vwmc 2293 wdpq 9188 vqee 4515
-- -- --
wgtk 0000 weae 1111 wbwe 2222
wgtl 9616 weaf 0726 wbwf 1837
wgtm 9231 weag 0342 wbwg 1453
wgtn 8846 weah 9957 wbwh 1068
wgto 8462 weai 9572 wbwi 0683
wgtp 8077 weaj 9188 wbwj 0299
-- -- --
whed 0000 xohr 1111 xlds 2222
whee 9615 xohs 0727 xldt 1838
whef 9230 xoht 0342 xldu 1453
wheg 8846 xohu 9957 xldv 1069
wheh 8461 xohv 9573 xldw 0684
whei 8077 xohw 9188 xldx 0299
-- -- --
xrlq 0000 xpsj 1111 xmok 2222
xrlr 9616 xpsk 0726 xmol 1837
xrls 9231 xpsl 0342 xmom 1453
xrlt 8846 xpsm 9957 xmon 1068
xrlu 8462 xpsn 9572 xmoo 0683
xrlv 8077 xpso 9188 xmop 0299
-- -- --
xswi 0000 yalp 1111 ywvx 2222
xswj 9615 yalq 0726 ywvy 1838
xswk 9230 yalr 0341 ywvz 1453
xswl 8846 yals 9957 ywwa 5285
xswm 8461 yalt 9572 ywwb 4900
xswn 8076 yalu 9188 ywwc 4515
-- -- --
ycew 0000 yzzw 1111 yxgq 2222
ycex 9615 yzzx 0727 yxgr 1837
ycey 9231 yzzy 0342 yxgs 1453
ycez 8846 yzzz 9957 yxgt 1068
ycfa 2678 zaaa 0525 yxgu 0683
ycfb 2293 zaab 0141 yxgv 0299
-- -- --
ydpo 0000 zksc 1111 zhod 2222
ydpp 9615 zksd 0727 zhoe 1838
ydpq 9230 zkse 0342 zhof 1453
ydpr 8846 zksf 9957 zhog 1069
ydps 8461 zksg 9573 zhoh 0684
ydpt 8076 zksh 9188 zhoi 0299
-- -- --
znwb 0000 zldv 1111 zizv 2222
znwc 9615 zldw 0726 zizw 1837
znwd 9231 zldx 0341 zizx 1453
znwe 8846 zldy 9957 zizy 1068
znwf 8462 zldz 9572 zizz 0683
znwg 8077 zlea 3404 zjaa 5446
- Registriert
- Jan. 2021
- Beiträge
- 3.958
Vielleicht sehe ich das ja gerade nicht richtig, aber wieso sind denn aaaa, azoh, bkhn und cvzs "ähnliche Eingaben"?
@ Mods : Da ich hier eigentlich schon eine Lösung gefunden habe, könnte dieses Thema bitte geschlossen werden.
Zuletzt bearbeitet:
foofoobar
Rear Admiral
- Registriert
- Dez. 2011
- Beiträge
- 5.226
Damit könnte man ansatzweise testen: https://www.google.com/search?q=nist+randomness+test0x8100 schrieb:
Ergänzung ()
Aber vorher verrätst du uns bitte noch für welches Problem du eine Lösung gefunden hast.CyborgBeta schrieb:
0x8100
Fleet Admiral
- Registriert
- Okt. 2015
- Beiträge
- 10.953
da ich heute noch was anderes vorhabefoofoobar schrieb:
, habe ich einfach mal https://mzsoltmolnar.github.io/random-bitstream-tester/ genommen. der eine screenshot zeigt diesen algo, der andere die ersten 4 zeichen des outputs von sha512sum. welcher screenshot welchen algo zeigt, sollte klar sein.Anhänge
- Registriert
- Jan. 2021
- Beiträge
- 3.958
Jetzt drehen wir uns im Kreis, denn
Es käme darauf an, wie du die Ausgabe von
sha<256/512>sum hat doch eine zu lange Ausgabelänge.Es käme darauf an, wie du die Ausgabe von
sha gekürzt hast. Sonst vergleichen wir wieder Birnen und Äpfel.Ich auch.0x8100 schrieb:
0x8100
Fleet Admiral
- Registriert
- Okt. 2015
- Beiträge
- 10.953
an dem punkt waren wir schon vor zwei seiten...CyborgBeta schrieb:
- Registriert
- Jan. 2021
- Beiträge
- 3.958
- Registriert
- Jan. 2021
- Beiträge
- 3.958
Ja ok, mein Browser hatte sich quer gestellt (Chrome gerade). 
Für das Problem, nicht zufrieden zu sein. Und ihr versucht schon wieder, da kaputt zu machenfoofoobar schrieb:
. Allerdings ist der Code jetzt ja "gut genug für <<das Problem>>". sha kann man schließlich nicht verwenden, denn einen string zu verlängern ist offensichtlich noch schwerer, als ihn zu kürzen.Ich bin in solchen Momenten immer so dankbar für meinen Arbeitsplatz und meine Kollegen
.Ich finde das schon ziemlich unfair eine Diskussion anzufangen, und weil man sie im Verlauf zu anstrengend findet, dann den Thread schliessen zu wollen. Ich hoffe die Mods leisten dem nicht Folge, weil ich das unfair gegenüber Usern wie @0x8100 finde, die scheinbar viel Zeit in ihre Beiträge investiert haben.CyborgBeta schrieb:
Ergänzung ()
Meine Vorlesungen in Informatik sind leider schon viel zu lange her (ich habe in den 80ern studiert...) als das meine formalen Kenntnisse noch sattelfest sind.
Ich glaube die Diskussion hier wird davon bestimmt, dass man Hash Funktionen heutzutage fast ausschließlich und sofort mit kryptografischen Hashes (wie SHA) verknüpft. Sowas sollte man tatsächlich nicht selber machen, vor allem nicht ohne Kentnisse in Kryptographie und der zugehörigen Mathematik.
Aber Hash Funktionen werden ja noch für andere Zwecke eingesetzt, unter anderem auch für Hashtables. Das hat glaube jeder, der mal eine Vorlesung zu "Algorithmen und Datenstrukturen" geniessen durfte, gelernt.
Wikipedia schreibt zu Hashfunktionen:
In dieser Definition ist die Implementierung des TE durchaus eine Hash Funktion. Und es kann auch Anwendungsfälle geben, für die sie ausreichend "gut" ist.
Wenn man Hashfunktionen z.B. für String Internalisierung nimmt man häufig sehr einfache und schnell zu berechnende Hashes. Da ist eigentlich nur Surjektivität und eine brauchbare Diffusion wichtig.
Das Anforderung von @CyborgBeta, Alpha-Strings der Länge 4 auf einen 4 stelligen Integer abzubilden, ist allerdings auch sehr speziell, mir erschliesst sich bisher kein nützlicher Anwendungsfall dafür.
Wenn es als Bash Script ausgeführt wird, sehe ich auch keinen Performance Nutzen.
Zuletzt bearbeitet:
0x8100
Fleet Admiral
- Registriert
- Okt. 2015
- Beiträge
- 10.953
das bezweifelt ja niemand. es ist eben nur keine gute implementierung. warum sich die ganze arbeit machen, und als bash-script was eigenes ausdenken, wenn es erprobte, sogar kryptografische anforderungen erfüllende und optimierte (sha512sum und co. haben auch avx/2/512 codepfade, die bash wohl kaum) alternativen gibt? der eigene ansatz macht nichts besser, aber alles schlechter als die vorhandenen tools.TomH22 schrieb:
So wie ich es verstanden habe, ist das schöne bei SHA ist, dass man einen beliebigen Ausschnitt des SHA Hashes nehmen kann (also z.B. die ersten 4 oder die letzten 4 Zeichen) und dieser Ausschnitt, bis auf eine höhere Menge an Kollisionen, immer noch die gleichen Eigenschaften ausweist.CyborgBeta schrieb:
Das nutzt z.B. Git aus, es reicht Git Commits mit den ersten 7 Stellen des SHA256 Hashes zu identifizieren.
Bei Deiner Funktion sieht man ja schon mit bloßem Auge, dass sich einige Hash Werte, wie 0000, 1111,2222 oder auch 9231,8846,9957 extrem häufig wiederholen. Und auch die anderen Werte weichen nur um +/-1 von diesen Häufungen ab. Du hast also eine extreme "Klumpennbildung" und nutzt die 4 Stellen garnicht aus, Deine Funktion ist nicht surjektiv:
Quelle: https://de.wikipedia.org/wiki/Hashfunktion
Du könntest auch die Funktion auf zwei Stellen (0..99) reduzieren und hättest nicht mehr Kollisionen...
Das ist klar, sie ist sogar bemerkenswert schlecht.0x8100 schrieb:
- Registriert
- Jan. 2021
- Beiträge
- 3.958
Jein, das ist der springende Punkt, weshalb ich etwas Eigenes möchte. Wenn du nur die ersten (oder letzten) 4 Zeichen von sha nimmst, dann ist die Diffusion nicht mehr gegeben, wenn ich es richtig verstanden habe.TomH22 schrieb:
Also, dann gibt es Werte, auf die gar nicht abgebildet wird, oder andere, auf die überdurchschnittlich oft abgebildet wird.
Ergänzung ()
Doch, das ist sie. Jedes Ergebnis kommt zwischen 45- und 46-mal vor. Das wäre sogar "optimal".TomH22 schrieb:
.Das wohl eben nicht.CyborgBeta schrieb:
OK, vielleicht täuscht der Auschnitt in dem Post oben. Also mir wären diese Muster, die man mit bloßem Auge sieht, nicht geheuer.CyborgBeta schrieb:
Ein Problem Deiner Idee ist der dezimale Zahlenbereich 0..9999. Die meisten etablierten Hash Funktionen arbeiten mit 2er Potenzen, weil das eben bei binär arbeitenden Computern viele Vorteile bringt.
Die nächste 2er Potenz in Deinem Zahlenbereich ist 2^13 (8192)
Ein schneller und einfacher Algorithmus den ich eben mal gefunden habe ist FNV-1a und ich habe ChatGPT dazu Python Code generieren lassen (war jetzt zu faul selber zu programmieren):
Python:
def hash(s):
hash_val = 0x11C # Offset basis: 284
prime = 0x21 # Prime: 33
mask = 0x1FFF # 13-bit mask (8191)
for char in s:
hash_val ^= ord(char)
hash_val = (hash_val * prime) & mask # Use bitmask to keep within 13 bits
return hash_valAls Stichprobe:
aaaa -> 8156 aaab->63
Den Rest überlasse ich Dir
Aus Deinen bisherigen Kommentaren entnehme ich dass Du nicht unbedingt die Mathematik hinter Hash Funktionen durchdringst, kein Vorwurf, tue ich auch nicht.
Und gerade weil es so ist, wäre mein Ansatz, etwas etabliertes zu verwenden. Ich habe jetzt erst mal nicht geprüft ob FNV-1a wirklich was taugt, aber das wäre dann der nächste Schritt.
- Registriert
- Jan. 2021
- Beiträge
- 3.958
Hm, Danke fürs Recherchieren. Ich schaue mal, ob es Xor (und bitweise Operatoren) in Bash gibt ... dann könnte ich eigentlich FNV-1a nachimplementieren.
- Registriert
- Jan. 2021
- Beiträge
- 3.958