Common - Question 2 (Principy sifer) Flashcards
Formalni definice symmetricke sifrovani
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.
Vlastnosti symmetrickych sifer
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)
Co jsou block ciphers
Symetricka sifra, ktera zpracovava data postupne po blocich pevne delky. Data jsou doplnena o padding, pokud jsou kratsi nebo delsi nez delka bloku.
Examples of block ciphers
DES, 3DES, AES, Blowfish, Twofish
Co jsou stream ciphers
Symetricka sifra, ktera je zpracovana bit po bitu
Examples of stream ciphers
RC4, vernam cipher ale i blokove sifry s urcitym modem jde predelat na stream
Jake dve techniky vyuzivaji block ciphers
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)
Feistel ciphers, jak funguji?
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)
DES, popis a jak funguje?
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
3DES - popis?
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
AES popis
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
Asymmetricka kryptografie - vlastnosti, rozdili oproti symetricke, pouziti
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.
Popis funkcionality RSA
- Generujeme dve nahodne prvocisla: p a q
- Vypocita se N = p * q; N se aktualne casto vyuziva nejcasteji 2048 a 4196
- 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
- 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)
Diffie-Helman key exchange popis
Neni Asymetricky - pouziva se vsak v asymetrickem protokolu ElGamal.
- Alice vybere prvocislo p a genereator g
- Alice nasledne vybere cislo a ktere si necha v tajnosti a vypocita A ≡ g^a mod p
- Alice posle Bobovi (A, g, p)
- Bob vybere nahodne cislo b, ktere si necha v tajnosti a vypocita B ≡ g^b mod p
- 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)
ElGamal popis
- Alice vybere prvocislo p a genereator g
- Alice nasledne vybere cislo a ktere si necha v tajnosti a vypocita A ≡ g^a mod p
- Alice posle Bobovi (A, g, p)
- 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 - Bob posle Alici (c_1, c_2)
- 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)
Co jsou hashovaci funkce a priklad pouziti?
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
Vlastnosti dobre hashovaci funkce
- 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’)
Priklady hash funkci
MD5 - 128b
MD4
SHA1 - 160b
SHA2 - [224, 256, 384, 512]
SHA3 - [224 - 1024]
Bcrypt
Scrypt
Obecna funkcionalita hash funkci (jak funguje)
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.
Hashing hesel
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
Eliptic curve cryptography - popis (vyhody, na cem jsou zalozene)
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
DSA - popis inicializaci klice
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)
DSA - Podepisovania popsat
- Nahode cislo k pro zpravu takove, ze 0 < k < q
- r = (g^k mod p) mod q; pokud r = 0 tak reset do kroku 1.
- 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)
DSA - overeni podpisu popsat
- overeni, jestli r a s jsou ve spravnych mezich
- w = s^-1 mod q
- u_1 = H(m)*w mod q
- u_2 = r*w mod q
- v = ((g^u_1 * y^u_2) mod p ) mod q
platny pokud v=r
ECC na cem spociva problem?
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)
Naivni metoda faktorizace cisla ‘n’
Zkousime prvocisla do sqrt(n)
Co je faktorizace
Rozklad cisla na soucin cisel (prvocisel). Je problem najit takova cisla (NP problem) a vsak podobna uloha “test prvociselnosti” ma polynomialnim case
Algoritmy pro faktorizaci cisla
Naivni metoda pokusu
Pollard rho algorithm
Pollard p-1 metoda
Fermatova faktorizacni metoda
Eulerova faktorizacni metoda
Quadratic sieve
Shor algorithm (kvantove pocitace)
Algoritmy/metody pro testovani prvociselnosti
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)
Fermat primality test - popis, kde selhava
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
Solovay–Strassen - popis, kde selhava
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
Shor algorithm - popis
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
Quadratic sieve
- najic pocatecni x ~ sqrt(N) (zaokrouhlit)
- 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
