Common - Question 2 (Principy sifer)

Question 1

Formalni definice symmetricke sifrovani

Answer 1

5-tuple (P, C, K, E, D). P je mnozina vsech moznych plaintextu. C je mnozina vsech moznych ciphertextu. K jsou vsechny mozne klice. E a D jsou funkce - E= encryption, D=decryption.

Question 2

Vlastnosti symmetrickych sifer

Answer 2

Sdileni klice
c=E(p, k) - musi byt snadne zasifrovat jakkykoliv plaintext pomoci libovolneho klice
p=D(c, k) - musi byt obtizne zjistit plaintext, kdyz zname pouze ciphertext. Musi byt ale snadne ziskat plaintext, kdyz zname ciphertext a klic.

Melo by byt mozno vygenerovat velke mnozstvi klicu, at neni mozne odhadnout klic pouzit k zasifrovani plaintextu.

Encryption plaintextu pomoci konkretniho klice produkuje stejny ciphertext, ktery se da jednoznacne desifrovat (encryption, decryption maji bijektivni zobrazeni)

Question 3

Co jsou block ciphers

Answer 3

Symetricka sifra, ktera zpracovava data postupne po blocich pevne delky. Data jsou doplnena o padding, pokud jsou kratsi nebo delsi nez delka bloku.

Question 4

Examples of block ciphers

Answer 4

DES, 3DES, AES, Blowfish, Twofish

Question 5

Co jsou stream ciphers

Answer 5

Symetricka sifra, ktera je zpracovana bit po bitu

Question 6

Examples of stream ciphers

Answer 6

RC4, vernam cipher ale i blokove sifry s urcitym modem jde predelat na stream

Question 7

Jake dve techniky vyuzivaji block ciphers

Answer 7

Confusion and diffusion techniques

Confusion - mela by stizit najiti vztahu mezi klicem a ciphertextem (S-boxy)

Diffusion by melo stizit najiti vztahu mezi vstupem a vystupem. Zmena jednoho bitu ve vstupu by mela mit velky dopad na vystup (P-boxy)

Question 8

Feistel ciphers, jak funguji?

Answer 8

Plaintext je rozdelen na pulky (bloky maji sudou delku)

Encryption v kazdem kole:
L_(i)=R_(i-1)
R_(i)=L_(i-1) XOR F(R_(i-1), K_(i-1))

Pro kazdy kolo je odvozen novy sub-key

Decryption je obraceny proces (vcetne klicu generovane v opacnem poradi)

Question 9

DES, popis a jak funguje?

Answer 9

block size: 64
key size: 56 + 8 (parity)
pocet kol: 16 (kazdy blok plaintextu je prohnan 16 koly, nez ciphertext je vyplivnut)

Na encryption/decryption je pouzit klic o velikosti 48 bitu - tedy R ma nasledujici kroky:
1. krok sifrovnani/desifrovani je rozsireni pulky bloku z 32b na 48b (expanze)
2. krok sub-klic XOR blok 48
3. krok proces s S-box
4. krok serazeni podle P-boxu
5. R Xor L

L ma jen:
1. L = R

Z klice se odvodi 16 sub-klicu
48b klic je rozdelen na pulky - kazda rotovana doleva o jeden/dva bity

Question 10

3DES - popis?

Answer 10

Rozsireni DES - vola se 3-krat DES napr. E_k3( D_K2 ( E_K1( plaintext ) ) )

3 metody:
1. Vsechny klice jsou rozdilne
2. Prvni a posledni klic jsou stejny
3. Vsechny klice jsou stejne - pro zpetnou kompatibilitu

Question 11

AES popis

Answer 11

block size: 128b
key size: one of [128, 192, 256]
pocet kol zavisi na velikosti klici: one of [10, 12, 14]

AES nepouziva Feistelovu sit. Stav se drzi v matici 4x4 bytes
Jedno kolo ma 4 kroky:
1. SubBytes: Transformuje kazdy stavovy byte v matici Ab^-1 + c; A=constant matrix, c= constant byte
2. ShiftRows: radky jsou posunuty (rotace doleva). Prvni o 0 byte, dalsi radek o 1 byte, dalsi o 2, atp.
3. MixColumns: Kazdy sloupec je pronasoben matici (constant matrix)
4. AddRoundKey: stavova matice se Xoruje s klicem pro dane kolo

Question 12

Asymmetricka kryptografie - vlastnosti, rozdili oproti symetricke, pouziti

Answer 12

Snazi se vyresit problem symetricke kryptografie, ze je potreba sdilet klic; pouziva dva klice - jeden verejny, druhy soukromy.

Verejny ma byt pro kazdyho - zasifrovat zpravu. Soukromy ma pak byt pro rozsifrovani - pouze vlastnikem.

Obvykle je pomalejsi nez symetricke sifry a jsou s ni spojene dalsi problemy - napr. jak verit, ze verejny klic je daneho cloveka a ne zaskodnika (Man in the middle attack)?

Nejcasteji se pouziva pro inicializaci spojeni=(vymenu klice pro symetrickou sifru) a digitalni podpis.

Question 13

Popis funkcionality RSA

Answer 13

1. Generujeme dve nahodne prvocisla: p a q
2. Vypocita se N = p * q; N se aktualne casto vyuziva nejcasteji 2048 a 4196
3. Vypocita se coprime e pro cislo 𝜑(N)=(p-1)*(q-1) ( -> gcd(𝜑(N), e)). Male e jsou rychlejsi, ale mene bezpecny. Nejcasteji se voli 65537 - kompromis mezi malym cislem (rychlym), ale bezpecnym
4. Vypocita se prevracena hodnota (multiplicative inverse) d (d ≡ e^-1 mod 𝜑(N))

Verejny klic je potom (N, e)
Privatni klic je potom (N, d)

Encryption: c ≡ m^e mod N
Decryption: m ≡ (m^e)^d mod N = m^(ed) mod N

Mozne diky Eulerovy theoremu:
Jestli (a, N) = 1 potom a^(𝜑(N)) ≡ 1 mod N

ed ≡ 1 mod 𝜑(N) therefore ed= k𝜑(N) + 1 mod N therefore m^(ed)=m^(k𝜑(N) + 1)

Question 14

Diffie-Helman key exchange popis

Answer 14

Neni Asymetricky - pouziva se vsak v asymetrickem protokolu ElGamal.

1. Alice vybere prvocislo p a genereator g
2. Alice nasledne vybere cislo a ktere si necha v tajnosti a vypocita A ≡ g^a mod p
3. Alice posle Bobovi (A, g, p)
4. Bob vybere nahodne cislo b, ktere si necha v tajnosti a vypocita B ≡ g^b mod p
5. Bob posle Alici B

Oba pak znaji g^(ab)= (A=g^a) * (B=g^b).

Ma snadny Man in the middle attack (Eva dela prostrednika mezi Alici a Bobem - Alice ustanovila klic s Evou a zaroven Eva s Bobem)

Question 15

ElGamal popis

Answer 15

1. Alice vybere prvocislo p a genereator g
2. Alice nasledne vybere cislo a ktere si necha v tajnosti a vypocita A ≡ g^a mod p
3. Alice posle Bobovi (A, g, p)
4. Bob vybere nahodne cislo b, ktere si necha v tajnosti dela nasledne dva vypcty:
   4.1 c_1 ≡ g^b mod p
   4.1 c_2 ≡ m*g^(ab) mod p
5. Bob posle Alici (c_1, c_2)
6. Decryption pak probiha: c_2 * (c_1^a)^-1 = m * g^(ab) * (g^(ab))-1 = m

ElGamal spoliha na problemu diskretniho logaritmu. Je narocne najit a takove, ze a = log_a (x)

Question 16

Co jsou hashovaci funkce a priklad pouziti?

Answer 16

Jednosmerne funkce; vstup do teto funkce muze byt libovolne dlouhy avsak vysledek je o fixni velikosti. Znaci to i, ze vice vstupu ma stejny vysledek (surjektivni zobrazeni)

Priklad pouziti: hesla (salt+password, casto pouzivane bcrypt, scrypt ktere vycerpavaji resource a schvalne prodluzuji vypocet), digitalni podpis, zaruceni integrity

Question 17

Vlastnosti dobre hashovaci funkce

Answer 17

• Jednosmernost (neni mozne z hashe ziskat puvodni hodnotu - zpusobeno i ztratovosti funkce)
• Deterministicka funkce: stejna zprava obdrzi stejny vysledek
• Avalanche effect: I jedina zmena zpusobi velkou zmenu ve vysledku
• Melo by byt narocne narazit na kolize - narazit na par m, m’ ze h(m)=h(m’)

Question 18

Priklady hash funkci

Answer 18

MD5 - 128b
MD4
SHA1 - 160b
SHA2 - [224, 256, 384, 512]
SHA3 - [224 - 1024]
Bcrypt
Scrypt

Question 19

Obecna funkcionalita hash funkci (jak funguje)

Answer 19

Hash funkce ma vnitrni stav s pred definovanou hodnotou (nothing up my sleeve numbers). Zprava se mixuje se stavem a vzdy se uklada do stavu - ztraci se tedy informace ze vstupni zpravy. Zprava dostane padding.

Question 20

Hashing hesel

Answer 20

Hesla se kombinuji se soli aby nemohla byt predvypocitana (rainbow tables).

Caste pouzite funkce:
Bcrypt: zalozene na blowfish blokove sifre - definuje se pocet kol (chceme prodlouzit vypocet at je obtizne najit odpovidajici heslo danemu hashi)
Scrypt: byla vytvorena s cilem byt memory heavy - aby se nedali pouzit specialni HW na zrychleni vypoctu

Question 21

Eliptic curve cryptography - popis (vyhody, na cem jsou zalozene)

Answer 21

ECC se pouzivaji s mensimi klici s porovnanim vuci RSA ale zajistujici stejnou bezpecnost. Zalozene na problemu diskretnim log. Eliptic curves se vyuzivaji v problemu faktorizaci a diskretnim logaritmu.

Elipticka krivka je vyjadrena jako par (E, O)
* E = mnozina bodu definovana rovnici y^2=x^3+ax+b (a a b takove, ze 4a^3+27b^2 != 0)
* O = Bod v nekonecnu na rovnici

ECC ma pak dve operace - * a +:
* operace * = X * Y = Z . Vedeme body X,Y primkou na krivce E a ziskame tim -Z na miste, ktere protne primka krivku (musim tedy invertovat pomoci osi x na Z). Nekdy Z muze splynout s X,Y. (spocita se pres kubickou rovnici, kde dva koreny jsou zname - X,Y - a treti koren je Z)
* operace + = X + Y = (X * Y) * O

Question 22

DSA - popis inicializaci klice

Answer 22

DSA se pouziva z libovolnou hashovaci funkci

Generovani klice:
1. zacina volbou delkou klicu (L, N). N musi byt rovno nebo mensi nez vystup hash funkce, L ma byt dlouhe.
2. Zvolise prvocisla q (velikost N-bitu), p (modulus o velikost L-bitu). P ale musi byt takove, ze p-1 je nasobkem q
3. Nasledne se zvoli cislo g takove, ze g^q ≡ 1 mod p
4. zvoli se x takove, ze 0 < x < q
5. y = g^x mod p

Verejny klic je potom (p, q, g, y)
Soukromy klic je pomot (x)

Question 23

DSA - Podepisovania popsat

Answer 23

1. Nahode cislo k pro zpravu takove, ze 0 < k < q
2. r = (g^k mod p) mod q; pokud r = 0 tak reset do kroku 1.
3. s = (k^-1 * (H(m) + x*r)) mod q ; pokud s = 0 zacni reset do kroku 1.

podpis je: (r, s)

cislo k se nesmi opakovat casto - muze rozbit DSA (respektivne slo by odvodit soukromy klic)

Question 24

DSA - overeni podpisu popsat

Answer 24

1. overeni, jestli r a s jsou ve spravnych mezich
2. w = s^-1 mod q
3. u_1 = H(m)*w mod q
4. u_2 = r*w mod q
5. v = ((g^u_1 * y^u_2) mod p ) mod q

platny pokud v=r

Question 25

ECC na cem spociva problem?

Answer 25

Problem diskretniho logaritmu.

Je
G * k = P mod p
G, P jsou body na krivce
Soukromy klic je ‘k’
Verejny klic jsou souradnice P

(p je Galloid field p - finite field)

Question 26

Naivni metoda faktorizace cisla ‘n’

Answer 26

Zkousime prvocisla do sqrt(n)

Question 27

Co je faktorizace

Answer 27

Rozklad cisla na soucin cisel (prvocisel). Je problem najit takova cisla (NP problem) a vsak podobna uloha “test prvociselnosti” ma polynomialnim case

Question 28

Algoritmy pro faktorizaci cisla

Answer 28

Naivni metoda pokusu
Pollard rho algorithm
Pollard p-1 metoda
Fermatova faktorizacni metoda
Eulerova faktorizacni metoda
Quadratic sieve

Shor algorithm (kvantove pocitace)

Question 29

Algoritmy/metody pro testovani prvociselnosti

Answer 29

Zalozene na pravdepodobnostni:
Fermat primality test
Miller–Rabin
Solovay–Strassen

Obcas maji false positive (oznaci slozene cislo jako prvocislo) - vyresi se opakovanim testu vicekrat s ruznymi pocatecnimi hodnotami

Testy, ktere produkuji certifikaci prvociselnosti (100% jisti, ze je to prvocislo)
Pocklington primality test
Lucas primality test
AKS
Elliptic curve primality test (nejcasteji pouzivany - povazovan za nejrychlejsi)

Question 30

Fermat primality test - popis, kde selhava

Answer 30

Small fermat theorem - a^(p-1) ≡ 1 mod p; pro vsechna 0 < a < p-1

Pokud test najde libovolne a, pro ktere fermatova veta neplati -> slozene cislo

Neodhali ale tzv Carmichael cisla - splnuji rovnici ale nejsou prvocisla

proto pravdepodobnostni test

Question 31

Solovay–Strassen - popis, kde selhava

Answer 31

zesilena fermatova veta
a^((p-1)/2) ≡ (a/p) mod p; pro vsechna 0 < a < p, (a/p) je Legendre symbol - funkce vracejici jestli a je quadratic residue mod p.

Neodhali tzv. Eulerovo pseudoprvocisla

proto pravdepodobnostni test

Question 32

Shor algorithm - popis

Answer 32

Algoritmus pro kvantovy pocitac, ktery by mel bezet v polyn case (ma tedy rozbit RSA)

hadame pres rovnici g^(x + kp) = mN + r

N = slozene hledane cislo

gcd( g^p, m*N)

volime:
* p = suda cisla

Dve podminky:
* p at neni liche
* g^p nema v sobe N samotne

Question 33

Quadratic sieve

Answer 33

1. najic pocatecni x ~ sqrt(N) (zaokrouhlit)
2. Zkusit y^2 = x^2 - N; y je cele cislo
   2.1 pokud y neni cele - zvysit x o jedna
   2.2 pokud je cele, tak (x - y) (x + y) = p * q