6. sada úloh (celkem 25 b, z této sady je možné dostat maximálně 21 b)
Úloha 1 (3 body, možné 2 extra)
Najděte dva různé textové řetězce, jejichž SHA-256 hash se shoduje na prvních 40 bitech. Tyto dva řetězce musí začínat vaším jménem (tj. např. JanNovakBUCVU a JanNovakYVOF). Nabízím 2 bonusové body pro toho, kdo najde dva různé textové řetězce obsahující vaše jméno, jejichž SHA-256 hash se shoduje na prvních 56 bitech.
Pozn.: doporučuji použít jednu z následujících funkcí/nástrojů
- echo -n retezec | sha256sum (Bash)
- hashlib.sha256(retezec).hexdigest()[:10] (Python - knihovna hashlib)
- SHA256().Create().ComputeHash(Encoding.ASCII.GetBytes(retezec)) (C# -- knihovna System.Security.Cryptography)
- MessageDigest.getInstance("SHA-256").digest(retezec.getBytes())
V případě dalších jazyků se mě nebojte kontaktovat, pokud si nevíte rady.
RC4
RC4 je proudová šifra z roku 1987. Její výhodou je rychlost softwarové implementace. Kvůli praktickým útokům na původní návrh se používá v mírně pozměněné podobě. Popis šifry je velmi jednoduchý na najdete ho třeba na Wiki.
Úloha 2 (0 + 4 body)
Naimplementujte tuto šifru ve svém oblíbeném programovacím jazyce. Najděte dvoubajtový klíč, pro který RC4 generuje proud začínající takto (posloupnost bajtů):
\[EF, F8, 5B, 0B, 95, 14, FF, 09, CB, 0E\].
Úloha 3 (2 body)
Pokud na začátku smyčky generující výstup (smyčka začínající while GeneratingOutput:)platí
\[j=i+1\]
\[S[j]=1,\]
pak je šifra v tzv. Finneyově stavu. Dokažte, že pokud je v kroku $k$ šifra ve Finneyově stavu, pak i v kroku $k+1$ je ve Finneyově stavu.
Úloha 4 (3 body)
Dokažte, že Finneyův stav nemůže nikdy nastat.
Úloha 5 (4 body)
Def.: Merkleovo-Damgardovo schéma (2. varianta)
Mějme zprávu $M$, kterou rozdělíme na $n-1$ bloků ($M_i$) délky $d$ a jeden blok ($M_n$) délky $q < d$.
\[
M_1' := 0 \parallel M_1
\]
\[
M_i' := 1 \parallel M_i, 1 < i < n
\]
\[
M_n' := 1 \parallel M_n \parallel 0^{d-q}
\]
\[
M_{n+1}' := 1 \parallel d - q,
\]
kde $d-q$ v $M_{n+1}$ je myšleno jako $d$-bitové číslo. Nyní postupujeme jak v klasickém M-D schématu, tj. $S_0:=IV,\ S_i:=f(S_{i-1}, M_i')$ a výstup $h(M_1\parallel \dots \parallel M_n):=S_{n+1}$
Rozhodněte, zda-li i pro toto schéma platí věta:
"Jestliže kompresní funkce $f$ je bezkolizní, pak i $h$ je bezkolizní." Pokud tato věta platí, pak ji dokažte. V opačném případě uveďte protipříklad.
Úloha 6 (4 body)
K dispozici máte $N$ a $\varphi(N)$ (viz níže). Najděte $p, q \in \mathbb{N}: N=pq$.
\[
N = 687843408455555596887850580402609857785668530350586396107215152615244115797907314471092772685646559431244830543839684809653694073242826554478070646717961720875519901367618409848153371111093617956324971262667003645110905778820265559619488424415390427707341351131337161474098124091102195606278867799433508170216452697232714301390759533779206510518711123253979421483489062436976148026112676864096844775107996844292086522765763254224370833410019819273555313076082135714267018750562294478964278258432179108212950425629656807853813696366406732485087845501025104921061653160317685324945794554716999841355174419714755067283504303232761150022955979448777193048107049741939754592024085750029305782029030958688532514957176528911691760279975106784819968818724744351725980701252729651119284364996788989602934823371255229212759057925483026765855279582445127666036257686847619655866654062197252557416252269461133758357752024197621789286521228256541622723740586005630125687435626671193884796401877402345410500755019491093366703375616392079484403527121753869493416780891799719076950798510787809655070300505590254410787952715981877029392268723701856717209178494219642807097230291658332989058325060675471270781599048257196312774996804568071
\]
\[
\varphi(N)=687843408455555596887850580402609857785668530350586396107215152615244115797907314471092772685646559431244830543839684809653694073242826554478070646717961720875519901367618409848153371111093617956324971262667003645110905778820265559619488424415390427707341351131337161474098124091102195606278867799433508170216452697232714301390759533779206510518711123253979421483489062436976148026112676864096844775107996844292086522765763254224370833410019819273555313076082135714267018750562294478964278258432179108212950425629656807853813696366406732485087845501025104921061653160317685324945794554716999841355174419714755014829527716460065900844958374007471610626442346554314237828073147661202515009233232250655586283930691177130692228612246202107812254309735472958853681556000917777227350007100668854322767052105450868194702434477182221765000602308748537981155613495918351178184945481722328698584716663220515415645959036120495965432175043092503319298897844473873427776971191874001611104772175104444821092392406104697313015182345739624072334005962617653097455503471244309276643736523406513671768576614838276989129064059237133926914876906274747865067462659809673144858534121188050077596250811883645633620257613816407844416386493412832
\]
Doporučuji si rozmyslet, v čem řešení spočíst. Některé programovací jazyky sice zvládnou velká čísla, ale jen s omezenými operacemi (např. Python). Wolfram Mathematica (licenci máte v rámci fakulty k dispozici
ZDE) si poradí bez problémů, ev. lze použít
Wolfram Alpha pro problematické části.
Úloha 7 (3 body)
Napište mi elektronicky podepsaný email (libovolný obsah, SMIME nebo PGP). Certifikát si můžete vygenerovat např. skrze Cesnet
ZDE (tímto certifikátem podepisuji své e-maily), alternativně můžete použít například OpenSSL za pomoci následující sekvence příkazů:
- openssl genrsa -aes256 -out ca.key 4096 # vygeneruj klic CA
- openssl req -new -x509 -days 365 -key ca.key -out ca.crt
# vytvor certifikat CA
- openssl genrsa -aes256 -out smime.key 4096 # vygeneruj klic pro uzivatele
- openssl req -new -key smime.key -out smime.csr # vytvor zadost o certifikat
- openssl x509 -req -days 365 -in smime.csr -CA ca.crt -CAkey ca.key -set_serial 1 -out smime.crt -setalias "Self Signed SMIME" -addtrust emailProtection -addreject clientAuth -addreject serverAuth -trustout # vytvor uzivateli certikat podepsany nasi CA
- openssl pkcs12 -export -in smime.crt -inkey smime.key -out smime.p12 # export do PCKS12
Většina e-mailových klientů používání těchto certifikátů nějakým způsobem podporuje (Thunderbird - zabezpečení v nastavení účtu), Gmail v prohlížeči bohužel jen skrze doplněk prohlížeče.