Specialization IB - Question 3 (Coding theory)

Question 1

Co je kodovani, druhy/typy kodovaci teorie

Answer 1

Total function (mapping): z S do T.

druhy:
Noisy coding theory
Noiseless coding theory

Question 2

Co je kanal (channel)

Answer 2

Kanal je fyzicke medium

Question 3

Jake typy kanalu

Answer 3

Diskretni
* Discrete Shannon stochastic channel: trojice (∑, Ω, Pr) - ∑=vstupni abeced, Ω=vystupni abeceda, Pr= pravdepodobnostni funkce, ze se element ze vstupni abecedy mapuje na element z vystupni abecedy
* Hamming adversarial (worst-case) noise model

kontuniualni (nepretrzity)

Question 4

Co je cilem kodovani?

Answer 4

Metody upravy/transformace kodu, aby kod sedel vice ucelu. Napr. pri kompresi chceme kodovat caste znaky do kratsich posloupnosti, chceme detekovat chyby pri prenosu po siti. Zaroven chceme jednoznacnost pri dekodovani atp.

Question 5

Co je hammingova vzdalenost

Answer 5

Pocet symbolu, ve kterych se dve slova lisi.

Question 6

Minimalni vzdalenost

Answer 6

Nejmensi Hammingova vzdalenost v kodu C - mezi dvemi slovy kodu C

Question 7

Error-correction theorem

Answer 7

pro detekci ‘s’ chyb h(C) ≥ s + 1 (proof: s by bylo dalsi slovo v C)
pro opravu ‘t’ chyb h(C) ≥ 2t + 1

Question 8

Zapis/definice code C, idealni hodnoty

Answer 8

(n, M, d)-code C
n = delka slov v kodu C
M = pocet slov v kodu C
d = minimalni vzdalenost kodu C

ideal = kratke n, velke M, velke d

Question 9

Code rate of code C- (n, M, d) (rovnice, co to je)

Answer 9

(log_q (M))/n

pomer potrebnych pocet vstupnich symbolu k poslani kodu

Question 10

Shannon noisless theorem

Answer 10

pro prenos n hodnot informace X potrebujem pouzit: n * S(X) bitu.

napr.
bit 1 = p=1/4
bit 0 = p=3/4

pro 4-bit block -> 3.245 bitu

Question 11

Entropie

Answer 11

Mira chaosu (nejistoty) - cim nizsi entropie, tim vetsi predvidatelnost (nulova entropie - vime presne, co bude vystupem)

I(x)= -log_2 { P(x) } // Mira informace ve zprave x
S(X) = - sum (𝑃 ( 𝑥_𝑖) · 𝐼(𝑥_𝑖)) // Entropie

Question 12

Generování skutečně náhodných sekvencí - vlastnosti + jake jsou idealni, dobre, prijatelne zdroje

Answer 12

TRNG (True random generators) - byvaji pomale, maji nedeterministicke chovani= jejich kvalita zalezi na zdroji nahodnosti:
* Idealni zdroj: Pouzije fakt nahodny prvek - radioaktivni rozpad, kosmicka radiace, atmosfericky sum
* Excelentni: HW-based (zabudovany cip), pridavne kart
* Dobry: Mikrofon, kamera, I/O HW, pohyb mysi
* Prijatelny: SW-based (procesy, sitova komunikace)

Question 13

Generování pseudonáhodných sekvencí

Answer 13

Deterministicky konecny automat:
- ma vnitrni stav
- stav se meni

Ze stavu se deterministicky da zjistit cela posloupnost generovanych dat

Question 14

Priklad algoritmu pseudonahodnych sekvenci

Answer 14

• LFSR - Linear Feedback Shift Register
• RSA PRNG (slow)
• BBS PRNG (slow)
• ANSI X9.17
• Yarrow
• Fortuna

Question 15

Jak funguje Linear Feedback Shift Register

Answer 15

Vybere se startovaci stav (nesmi mit same nuly)

Pri vyberu vhodne stavu mame 2^n - 1 kombinaci (pri delce stavu 128+ nemozne zkusit vsechny)

XOR 2 bitu ze dvou vybranych pozicich ve slove, nasledne shift a umisteni vysledku XORu na prvni/posledni pozici (v zavislosti na smeru shiftu)

napr. XOR bitu na poslednich dvou pozicich, shift 1&raquo_space;, novy bit umisten na prvni pozici
1. 1001 (output: 1)
2. 1100 (output: 0)
3. 0110 (output: 1)
…
x-1. 0010 (output: 1)
x<=>1. 1001 (pocatecni stav)

Question 16

Zlepseni Linear Feedback Shift Register

Answer 16

Zkombinovat vice LFSR at mame nelinearni kombinaci

Question 17

Jak funguje RSA PRNG

Answer 17

Klasicke RSA
seed/stav = zprava (seed^e mod n nebo state^e mod n)

x_0 = random(2, n-2)
x_i = x_(i-1)^e mod n
vystup generatoru: lsb(x_i) // lsb = Least Significant Bit

Question 18

Jak funguje BBS PRNG

Answer 18

Podobne RSA. Jedinny rozdil - misto state^e -> state^2

x_0 = random(2, n-2)
x_i = x_(i-1)^2 mod n # rozdil
vystup generatoru: lsb(x_i) // lsb = Least Significant Bit

Question 19

Jak funguje ANSI X9.17 PRNG

Answer 19

Zalozen 64-bit 3DES-3 nebo 128-bit AES

K = klic
DT = Datum/cas/nahodne inicializovany counter
s = Seed

alg:
1. t = E_k (DT)
2. r = E_k (s XOR t)
3. s = E_K (r XOR t)

vysledek (output) je ‘r’ - nahodne cislo

Question 20

Jak funguje YARROW PRNG

Answer 20

Blockova sifra CTR modu (napr. DES, AES, …) + hash funkce

Ma dva pooly: Fast - slow (rychlejsi pro castejsi ressed, slow mene casty reseed)

Ma Reseed control mechanismus - odhaduje na zaklade vypocitane entropie, jestli je potreba reseed nebo ne

K = klic
s = K = Seed
reseed = zmena klice
alg:
1. C_i = C_(i-1) + 1 mod 2^n
2. output = E_k (C_i)

Question 21

Jak funguje Fortuna PRNG

Answer 21

Nasleduje Yarrow

blokove sifry AES, Twofish, Serpent
hash: SHA-256

32 poolu pro sber entropy.
P_i = i-th Pool
reseed:
* P_0 kazde kolo
* P_1 kazde druhe kolo
* P_2 kazde ctvrte kolo
* P_3 kazde osme kolo
Vysledek je, ze pokazde bude pool s dostatecnou entropii

Question 22

Staticke analyza nahodnosti

Answer 22

NIST test (15 testu)
DIEHARD

Jde o to, jestli pseudonahody generator cisel generauje sekvenci, ktera je vskutku tvarici se nahodne (napr. tedy sekvence ma +- stejne mnozstvi 0/1, avsak nemuze byt n 0 na zacatku, nasledne nasledovane n 1).

Question 23

Kryptografické protokoly

Answer 23

Algoritmy, kde musi byt dodrzena posloupnost kroku, aby protokol splnil svuj ucel
- cile muzou byt: authentication, integrity, key establishment
Protokoly muzou spolehat i na tajemstvi:
* symetricke maji sdilene klice - duvera je ve znalosti sdileneho klice
* asymetricke - duvera je zalozena na vlastnictvi privatniho klice a v duvere propojeni mezi privatnim a verejnym klicem

Question 24

Co je Nonce

Answer 24

Cislo puzite maximalne jednou pro komunikaci (sekvencni cislo, uuid, timestamp)

Question 25

Priklad protokolu pro authentication (Asym)

Answer 25

n = randome nonce

Komunikace sifrovana verejnymi klici Alice, Boba

Alice -> Bob: E_B (n)
Alice <- Bob: E_A (n+1)
Alice -> Bob: E_B (n+1)

vedi, ze komunikuji spolu Alice a Bob.

Question 26

Priklad protokolu pro Challenge-Response

Answer 26

Alice -> Bob: Challenge (send me secret)
Alice <- Bob: Response (secret)
Alice -> Bob: OK/NOK (verifikace)

Question 27

Commitment scheme - Remote coin flip

Answer 27

H = hash function
g = guess
n = nonce

Alice -> Bob: x = H(g + n)
Bob: hodi minci
Alice -> Bob: rekne vysledek sveho odhadu (g) a pripoji nonce
Bob: muze si uverit ze poskytnute hodnoty splnuji: H(g + n) == x

Bob nevi, k cemu se Alice zavala pri hodu a vsak vi, ze Alice nedokazi zmenit svuj odhad.
commitment: Alice nemuze zmenit svuj vysledek

Question 28

Protokoly/metody ustavení klíčů

Answer 28

Key Transport: Alice bezpecne posle tajemstvi bobovi (napr. Asym komunikace)
Key Aggrement: Alice and Bob each contribute data on which the key is derived (e.g. Diffie-Helman)

Question 29

Ustanoveni klice - vlastnosti (concepts of assurance)

Answer 29

• Implicit Key Authentication: Jistota Boba, ze nikdo jiny krom alice nemohl precist klic
• Key Confirmation: Alice ujisti Boba, ze jen ona zna klic
• Explicit Key Authentication: Implicit Key Authentication a Key Confirmation
• Entity Authentication: Ujisteni jedne strany o identite druhe strany.

Question 30

Co je session klic

Answer 30

Kratkodoby klic - posle se mensi mnozstvi zprav a je jedno leaknuti klice

• Perfect Forward Secrecy - Kompromitace dlouhodobeho klice neovlivni zpravy z minulosti. Napr RSA + Diffie Hellman - ikdyz se leakne RSA klic, nevi klic k Diffie Hellman
• Perfect Backward Secrecy - Kompromitace session klice neovlivni zpravy v budoucnosti

Question 31

Shamir no-key protocol

Answer 31

Protokol bez sdileneho tajemstvi

A -> B: E_A (x)
A <- B: E_B( E_A (x) )
A -> B: E_B (x)

Question 32

Encrypted Key Exchange (EKE) - sifrovana vymena public klice

Answer 32

1. A a B sdili heslo H
2. A generuje par klicu s VA (verejny klic A)
3. A -> B E_H ( VA ) // E = symmetric cipher, vyuzije H
4. B ted vi VA (desifruje si pres H)
5. B generuje klic K
6. A <- B: E_H( E_VA( K ) )
7. A -> B: E_K ( x )
8. A <- B: E_K ( x, y )
9. A -> B: E_K ( y )

x, y = nahodne cisla, timestamp. Ma overit, ze K sdili spravne strany a nahodna cisla x, y by meli zamezit replay utoku

Question 33

protokoly s nulovým rozšířením znalostí (Zero-Knowledge protocols) - co to je, vlastnosti

Answer 33

Strana dokaze prokazat znalost urcite hodnoty, aniz by tu hodnotu zdelila

Soundess - zanedbatelne pravdepodobnost, ze utocnik zvladne podvadet
Completness - honest parties always achieve desirable outcome
Zero-knowledge - nevi nic krom znalosti, kterou chceme dokazat

Question 34

Simple example with Doors (Zero-Knowledge protocols)

Answer 34

Mame kruhovou chodbu s dvermi uprostred.

Alice ma klic a chce prokazat Bobovi, ze ho ma

Alice projde chodbou dokola (prokaze tak, ze zvladla projit dvermi). Neukazala tedy, ze ma klic a ani otevirani dveri. Jelikoz ale nemohla jit jinam, Bob musi verit.

Question 35

Feige-Fiat-Shamir identification scheme

Answer 35

Trusted authority (T):
* choose p,q; n=p*q
* choose s, s^2 ≡ v mod n; gcdn(s, n) = 1

Alg:
1. Alice vybere nahodne r < n
2. Alice -> Bob: posle x (x = r^2 mod n)
3. Alice <- Bob: random bit b (b ∈ {0, 1})
4. Alice -> Bob: posle y (y=r * s^b mod n)
5. Bob identifikuje Alice pokud y^2 = x * v^b

Protokol se opakuje do te doby, dokud Bob neni presvedceny. Pri opakovani t-times, Alice ma sanci 2^-t oklamat Boba.

Question 36

Kvantová kryptografie

Answer 36

Zalozena na fyzice (ne na predpokladu, ze je neco obtizne vypocitat)

moznost vyuziti pro one-time pad, key generation/distribution, factorization

Question 37

BB-84 shared key establishment

Answer 37

Natoceni fotonu (+ prevod na bit):
base 0° = 1, 90° = 0
base 45° = 1, 135° = 0

Pokud merime spravnou bazi, jsme schopni zjistit rotaci -> vime na 100%, jestli bit je 0 nebo 1. Kdyz merime spatnou bazi, foton polarizujem a sance se nam rozdeli na 50/50 jestli bude vybran spravny bit (0 nebo 1)

1. Alice vygeneruje radu bitu a zakoduje do q-ubitu
2. Alice posle bobovi fotony - nahodne polarizovane (vybran nahodny smer)
3. Bob vybira nahodny baze
4. Bob a Alice se spoji (klidne po nezabezpecenym kanalu - je jedno, kdo je uslysi) a hledaji schody v bazi (pro ktere bity zvolily stejnou bazi)
5. Klic je sestaven z namerenych bitu, kde meli Bob a Alice vybranou stejnou bazi

Pokud Eva bude naslouchat poslane qubity a zvoli spatnou bazi (coz je pravdepodobne), tak je 50% sance, ze posle Bobovi spatny qubit