Santraukos funkcija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

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.

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

Kriptografinei santraukos funkcijai keliami keli svarbūs reikalavimai.

[taisyti] Kriptografinė santraukos funkcija

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. \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.

[taisyti] Santraukos funkcijų pavyzdžiai

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