Santraukos funkcija

Santraukos funkcija (angl. hash function, fingerprint function, digest function) – bendru atveju, vienos (didesnės) aibės atvaizdavimas į kitą (mažesnę) aibę. Santraukos funkcija labai svarbi kriptografijoje, tačiau gali būti naudojama ir kitose srityse.

${\displaystyle h:A\to B,\ |A|>|B|\,}$.

Kriptografinei santraukos funkcijai keliami keli svarbūs reikalavimai.

Kriptografinė santraukos funkcija

Šį straipsnį gali būti gana sunku suprasti be papildomų informacijos šaltinių. Galite perrašyti dėstomus teiginius plačiau ir suteikiant daugiau konteksto.

Kriptografijoje naudojamos santraukos funkcijos, kurios atvaizduoja kintamo ilgio (baigtinio) žodžius į fiksuoto ilgio žodžius. Pastebėsime, kad tai neišvengiamai sudaro galimybę kolizijoms, t. y. ${\displaystyle \exists x,\ y,\ x\neq y:h(x)=h(y)\,}$.

Apibrėžimas. Santraukos funkcija vadiname funkciją h, kuri turi mažiausiai šias savybes:

1. Suspaudimą – funkcija paverčia kintamo ilgio eilutę į fiksuoto ilgio eilutę.
2. Paprastumą – duotajam ${\displaystyle x\,}$, reikšmę ${\displaystyle h(x)\,}$ lengva apskaičiuoti.

Santraukos funkcijos skirstomos į keletą rūšių:

1. Modifikacijas nustatančios funkcijos (ang. modification detection codes, MDC)
   1. Vienakryptės santraukos funkcijos (ang. one - way hash function, OWHF): turint ${\displaystyle y=h(x)\,}$ surasti ${\displaystyle x\,}$ yra sunku.
   2. Kolizijom atsparios santraukos funkcijos (ang. collision resistant hash function, CRHF): sunku surasti ${\displaystyle x,y\,}$, kad ${\displaystyle h(x)=h(y)\,}$
2. Santraukos funkcijos su raktu (ang. message authentication code, MAC): šios funkcijos rezultatas priklauso dar nuo papildomo argumento – rakto.

Apibrėžimas. Santraukos funkcija yra atspari silpnai kolizijai (ang. weak collision resistant), jeigu turint ${\displaystyle x\,}$ surasti ${\displaystyle {\hat {x}},\ x\neq {\hat {x}}\,}$, kad būtų ${\displaystyle h(x)=h({\hat {x}})\,}$ yra sunku.

Apibrėžimas. Santraukos funkcija yra atspari stipriai kolizijai (ang. strong collision resistant), jeigu surasti ${\displaystyle x\,}$ ir ${\displaystyle {\hat {x}},\ x\neq {\hat {x}}\,}$, kad būtų ${\displaystyle h(x)=h({\hat {x}})\,}$ yra sunku.

Santraukos funkcijų pavyzdžiai

• Message-Digest algorithm 5 (MD5)
• Secure Hash Algorithm (SHA)