Andrew Kozlík @

Domácí úkol č. 8 z předmětu Kryptografické systémy

---

Kolize hashovací funkce

Definujme funkci SHA-40 jako funkci, která na vstupu x vrací prvních 40 bitů SHA-256(x). Najděte dva různé řetězce x a y, které

1. jsou tvořené výhradně velkými a malými písmeny anglické abecedy,
2. začínají vašim jménem a příjmením,
3. splňují SHA-40(x) = SHA-40(y).

Příkladem správného řešení studenta, který se jmenuje Jan Novák, je dvojice řetězců "JanNovakBUCVU" a "JanNovakYVOF". To lze ověřit například příkazem sha256sum:

echo -n JanNovakBUCVU | sha256sum
c69ee99823604bb344ef0b3ae1bbe96242825ef4d919280b7431ef5cabbf62f3 -

echo -n JanNovakYVOF | sha256sum
c69ee99823c344b114ed92101bde7e18ad1b21b76d62f016e3f5cea8f55f4eb1 -

Z výstupu obou příkazů vidíme, že otisky funkce SHA-256 se shodují v prvních 40 bitech, tj. 5 bajtech c69ee99823.

Bonus

Definujme funkci SHA-56 jako funkci, která na vstupu x vrací prvních 56 bitů SHA-256(x). Podaří-li se vám najít kolizi SHA-56, dostanete za úkol celkem 7 bodů při odevzdání v řádném termínu, nebo 6 bodů při odevzdání v dodatečném termínu 18. 1. 2015, 18:00.

Jak to naprogramovat

V jazyce Perl nebo Python lze otisk SHA-40 vypočíst pohodlně jediným příkazem:

Python

import hashlib
otisk = hashlib.sha256(retezec).hexdigest()[:10]

Perl

use Digest::SHA qw(sha256_hex);
otisk = substr(sha256_hex(retezec), 0, 10);

C/C++

Budete potřebovat knihovnu OpenSSL (na Ubuntu balíček libssl-dev).

#include <openssl/sha.h>
unsigned char otisk[SHA256_DIGEST_LENGTH];
SHA256_CTX sha256;
SHA256_Init(&sha256);
SHA256_Update(&sha256, retezec.c_str(), retezec.size());
SHA256_Final(otisk, &sha256);

Kompilaci provedete příkazem g++ -o nazev_programu nazev_zdrojaku.cc -lcrypto.

C#

using System.Security.Cryptography;
using System.Text;
byte[] otisk = SHA256.Create().ComputeHash(Encoding.ASCII.GetBytes(retezec));

---