Infomácie o KŠ

Prednášky

Otázky ku skúške

Zadania

Hodnotenie

Úlohy na vypracovanie

Získané body sa spočítavajú do výsledného hodnotenia ku skúške.

Zadanie č.16 (10 bodov)

Text zadania môžete nájsť tu.

Odovzdať do 6.4.2004


Zadanie č.15 (10 bodov)

Majme prahový generátor tvorený tromi lineárnymi spätnoväzobnými registrami. Register LFSR1 realizuje riešenie lineárnej diferenčnej rovnice ai + ai-1 + ai-3 = 0. Register LFSR2 realizuje riešenie lineárnej diferenčnej rovnice bi + bi-1 + bi-4 = 0. Register LFSR3 realizuje riešenie lineárnej diferenčnej rovnice ci + ci-2 + ci-5 = 0. Registre sa posúvajú pravidelne, v každom časovom okamihu o jeden bit. Výstupom generátora v čase t je hodnota ((at.bt) xor (at.ct) xor (bt.ct)).
Zvoľte si počiatočné naplnenia jednotlivých registrov a vygenerujte dostatočne veľkú výstupnú postupnosť (20 bitov by malo stačiť) prahového generátora. Pomocou tejto výstupnej postupnosti nájdite počiatočné naplnenia jednotlivých registrov (predstavte si, že ich nepoznáte). Pri útoku na jeden z registrov použite Meier-Staffelbachov algoritmus A, útok na zvyšné registre je ľubovoľný. Snažte sa o efektívnosť pri útoku na zvyšné registre!

Odovzdať do 23.3.2004


Zadanie č.14 (10 bodov)

Majme prahový generátor tvorený tromi lineárnymi spätnoväzobnými registrami. Register LFSR1 realizuje riešenie lineárnej diferenčnej rovnice ai + ai-1 + ai-3 = 0. Register LFSR2 realizuje riešenie lineárnej diferenčnej rovnice bi + bi-1 + bi-4 = 0. Register LFSR3 realizuje riešenie lineárnej diferenčnej rovnice ci + ci-2 + ci-5 = 0. Registre sa posúvajú pravidelne, v každom časovom okamihu o jeden bit. Výstupom generátora v čase t je hodnota ((at.bt) xor (at.ct) xor (bt.ct)).
Zvoľte si počiatočné naplnenia jednotlivých registrov a vygenerujte dostatočne veľkú (snažte sa ale čo najkratšiu) výstupnú postupnosť prahového generátora. Pomocou tejto výstupnej postupnosti nájdite počiatočné naplnenia jednotlivých registrov (predstavte si, že ich nepoznáte). Použite Siegenthalerov korelačný útok. Snažte sa útok urobiť efektívne !

Odovzdať do 16.3.2004


Zadanie č.13 (10 bodov)

Text v slovenskom jazyku je zašifrovaný pomocou "mriežky". (Text súvisí s predmetom, dokonca priamo so zadaním samotným.) Voľné políčka mriežky sú označené písmenom X. Dešifrujte text. Nájdite anagramový a kryptografický sled.

E,F,N,S,A,A,M,A,X,
I,A,E,N,I,E,C,K,X,
D,V,M,C,I,E,H,A,X,
S,R,O,I,K,L,J,R,X

Odovzdať do 16.3.2004


Zadanie č.12 (10 bodov)

Majme prahový generátor tvorený tromi lineárnymi spätnoväzobnými registrami. Register LFSR1 realizuje riešenie lineárnej diferenčnej rovnice ai + ai-1 + ai-2 = 0. Register LFSR2 realizuje riešenie lineárnej diferenčnej rovnice bi + bi-1 + bi-3 = 0. Register LFSR3 realizuje riešenie lineárnej diferenčnej rovnice ci + ci-2 + ci-5 = 0. Registre sa posúvajú pravidelne, v každom časovom okamihu o jeden bit. Výstupom generátora v čase t je hodnota ((at.bt) xor (at.ct) xor (bt.ct)).
Zvoľte si počiatočné naplnenia jednotlivých registrov a vygenerujte dostatočne veľkú výstupnú postupnosť prahového generátora. Pomocou tejto výstupnej postupnosti nájdite počiatočné naplnenia jednotlivých registrov (predstavte si, že ich nepoznáte), pričom pri útoku na jeden z registrov použijete Meierov-Staffelbachov algoritmus A, na ďalší register zasa Siegenthalerov útok, spôsob útoku na tretí register si zvoľte sami.

Odovzdať do 14.5.2002


Zadanie č.11 (10 bodov)

a) (8 bodov)
Zachytený prúdový kľúč 00101001100100101111 bol vytvorený generátorom, tvoreným dvoma lineárnymi spätnoväzobnými registrami s časovým riadením. Register LFSR1 realizuje riešenie lineárnej diferenčnej rovnice ai + ai-1 + ai-3 = 0. Register LFSR2 realizuje riešenie lineárnej diferenčnej rovnice bi + bi-1 + bi-4 = 0. Činnosť generátora:
Počiatočné naplnenie registra LFSR1 je (a0, a1, a2).
Počiatočné naplnenie registra LFSR2 je (b0, b1, b2, b3).
i = 0.
j = 0.
Krok 1: výstupom registra LFSR1 je ai.
Krok 2: obsah registra LFSR1 sa zmení na (ai+1, ai+2, ai+3).
Krok 3: ak je ai = 0, tak výstupom generátora bude bj, obsah registra LFSR2 sa zmení na (bj+1, bj+2, bj+3, bj+4), j = j + 1,
inak výstupom generátora bude bj+1, obsah registra LFSR2 sa zmení na (bj+2, bj+3, bj+4, bj+5), j = j + 2.
Krok 4: i = i + 1.
Krok 5: choď na Krok 1.
Útokom rozdeľuj a panuj nájdite počiatočné naplnenia registrov generátora.
b) (1 bodov)
Predstavte si, že časové riadenie posuvu registra LFSR2 (zmena jeho aktuálneho naplnenia) je závislé od všetkých bitov registra LFSR1. Ako by takéto časové riadenie posuvu registra LFSR2 ovplyvnilo útok rozdeľuj a panuj.
c) (1 bodov)
Predstavte si, že výstupom generátora je hodnota booleovskej funkcie, ktorej vstupom sú všetky bity aktuálneho naplnenia registra LFSR2. Časové riadenie posuvu registra LFSR2 závisí iba od ai. Ako to ovplyvní útok rozdeľuj a panuj.

Odovzdať do 14.5.2002


Zadanie č.10 (5 bodov)

a)
Zachytený prúdový kľúč 11011 bol vytvorený generátorom, tvoreným jedným lineárnym spätnoväzobným registrom s časovým samoriadením. Samotný register realizuje riešenie lineárnej diferenčnej rovnice si + si-1 + si-3 = 0.
Činnosť generátora:
Počiatočné naplnenie generátora je (s0, s1, s2).
i = 0.
Krok 1: výstupom generátora je si.
Krok 2: ak je si = 0, tak zmeň obsah registra na (si+1, si+2, si+3) a i=i+1 (inými slovami register sa posunie 1 krát),
inak zmeň obsah registra na (si+2, si+3, si+4) a i=i+2 (inými slovami register sa posunie 2 razy).
Krok 3: choď na Krok 1.
Nájdite počiatočné naplnenie registra.

b)
Zachytený prúdový kľúč 1110100 bol vytvorený generátorom, tvoreným jedným lineárnym spätnoväzobným registrom, s časovým riadením s krokom 2. Samotný register realizuje riešenie lineárnej diferenčnej rovnice si + si-1 + si-3 = 0.
Register generuje postupnosť s0, s1, s2, ..., výstupom generátora je postupnosť s0, s2, s4,...
Nájdite počiatočné naplnenie registra.

Odovzdať do 14.5.2002


Zadanie č.9 (10 bodov)

Aplikujte Hellmanov útok na Hillovsku šifru.

Odovzdať do 14.5.2002


Zadanie č.8

I)
a) Pomocou Pollardovej (p-1)-metódy rozložte dané číslo.
(26869, 13861, 753881, 1677803, 2717723, 1478671, 83527, 1542323, 534419, 7331117)
b) Pomocou Pollardovej rho metódy rozložte dané číslo.
(36287, 48227, 17653, 34571, 46513, 47477, 73543, 48959, 47959, 63433)
Každý študent si zvolí po jednom čísle z daných dvoch zoznamov. Rieši iba jednu z úloh (ktorú dokáže) za 10 bodov.

II)
Pomocou Shanksovej metódy vypočítajte diskrétny logaritmus daného čísla.
(p=857, log3(621)=?, p=859, log2(340)=?, p=863, log5(599)=?, p=877, log2(855)=?, p=881, log3(244)=?, p=883, log2(38)=?, p=887, log5(452)=?, p=907, log2(394)=?, p=919, log7(29)=?, p=929, log3(89)=?).
Každý študent volí jedno číslo z daného zoznamu a rieši individuálnu úlohu za 10 bodov.

III)
Pomocou metódy kvadratického sita rozložte dané číslo (39617, 34087).
Skupina v počte 5 študentov si vyberie jedno zo zadaných čísel. Každý zo skupiny musí preukázať znalosti v postupe riešenia.
Za vyriešenie úlohy a preukázanie znalosti riešenia každý študent zo skupiny získava 5 bodov.

IV)
Pomocou metódy eliptických kriviek rozložte dané číslo.
(n=899, krivka y2 = x3 + ax + 4, n = 3551, krivka y2 = x3 + ax + 1).
Prémiová úloha. Jedno číslo si môžu zvoliť najviac dvaja študenti. Za správne vyriešenie úlohy a preukázanie znalosti riešenia môže získať každý študent maximálne 5 bodov.

Odovzdať do ???


Zadanie č.7 (8 bodov)

Nájdite pôvodnú správu zašifrovanú 3 rotormi podľa zadania z prednášky.

Odovzdať do 11.3.2002


Zadanie č.6 (5 bodov)

Nájdite text zašifrovaný mriežkou.

SZEDTUMNCSAXRMBERNUXPUDVEXAKKEXXLIAO

Odovzdať do 20.2.2002


Zadanie č.5 (5 bodov)

Majme Geffeho generátor tvorený tromi lineárnymi spätnoväzobnými registrami R1, R2 a R3. Nech lineárne diferenčné rovnice asociované s jednotlivými registrami sú známe:
R1: ai + ai-1 + ai-2 = 0,
R2: bi + bi-1 + bi-3 = 0,
R3: ci + ci-1 + ci-4 = 0,
ai, bi, ci sú z GF(2).
Registre sa posúvajú synchrónne, v každom časovom okamihu o jeden bit. Výstup generátora zi je daný vzťahom: zi = aibi xor (1 xor ai)ci. Zo známeho úseku výstupnej postupnosti generátora z0, z1, ..., z14 = 0,0,1,1,1,0,1,0,0,0,1,1,0,1,0 nájdite počiatočné naplnenia jednotlivých registrov útokom typu rozdeľuj a panuj.

Odovzdať do 11.5.2001


Zadanie č.4 (5 bodov)

Zadanie: Riešia vždy dve dvojice študentov (A,B) a (C,D). Každá z dvojíc zvolí tajné kľúče (a,b) a (c,d). Členovia dvojice (A,B) si "vymenia" hodnoty ga a gb, ktoré "zachytia" členovia dvojice (C,D). Podobne výmenu gc a gd "zachytí" dvojica (C,D).

Úloha: Pomocou Shanksovej metódy dvojica (A,B) získa tajné kľúče (c,d) a aj spoločný kľúč dvojice (C,D). Podobnú úlohu rieši aj dvojica (C,D). Úlohu riešime v grupe Z*113 pri známom generátore g=3. Za získanie kľúča každý člen dvojice získa 5 bodov. V prípade neúspešného pokusu získava 5 bdov dvojica, ktorá volila tajné kľúče. Súčasťou riešenia je stručný popis Shanksovej metódy.

Odovzdať do 3.4.2001


Zadanie č.3 (5 bodov)

Text zadania č.3

Odovzdať do 26.3.2001


Zadanie č.2 (5 bodov)

Vyberte ľubovoľnú nelineárnu booleovskú funkciu f: Z24->Z24.
Napíšte jej algebraický normálny tvar a vytvorte jej lineárny profil. Vytvorte diferenčnú tabuľku a určte diferenciálnu uniformitu a nelinearitu funkcie f. Určte ord(f).

Odovzdať do 26.3.2001


Zadanie č.1 (5 bodov)

Text je zašifrovaný pomocou "mriežky" v slovenskom jazyku. Voľné políčka mriežky sú označené písmenom X. Dešifrujte text. Nájdite aj anagramový a kryptografický sled.

S N E M A K Y V X
R V I J O S N T X
F A E L A C E I X
I O J A A L Z O X

Odovzdať do 26.2.2001


Požiadavky na vypracovanie

Vytlačený dokument by mal obsahovať:
  • zadanie,
  • analýzu problému,
  • riešenie
a mal by byť odovzdaný včas.