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ů

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ů: 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.