Santraukos funkcija

Santraukos funkcija (Šablonas:En) – 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.

$h:A\to B,|A|>|B|$.

Kriptografinei santraukos funkcijai keliami keli svarbūs reikalavimai.

Kriptografinė santraukos funkcija

Šablonas:Bekonteksto 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. $\mathrm{\exists }x,y,x\ne 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 $x$, reikšmę $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 $y=h(x)$ surasti $x$ yra sunku.
   2. Kolizijom atsparios santraukos funkcijos (ang. collision resistant hash function, CRHF): sunku surasti $x,y$, kad $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 $x$ surasti $\hat{x},x\ne \hat{x}$, kad būtų $h(x)=h(\hat{x})$ yra sunku.

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

Santraukos funkcijų pavyzdžiai

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

pl:Funkcja skrótu#Kryptograficzne funkcje skrótu