Common - Question 2 (Principy sifer) Flashcards
(33 cards)
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
