Infomácie o ZK

Prednášky

Zadania

Archív

Hodnotenie

Test č.2

Test sa uskutočnil 10. týždeň - 28.11.2000 a jeho hodnotenie bolo 25 bodov + 12 bonus.

Zadanie

1. Feistelovský kryptosystém šifruje 8 bitové správy s pomocou funkcie f(.,k) f: V4 x V4 -> V4, f(m,k) = m + k v troch kolách.
a) dešifrujte správu y = 10101010 ak k = (1 1 1 1)
b) Nájdite priamo funkcie Ek(x) = y a Dk(y) = x pre ľubovolné k. Vzťahy dokážte.
5+2b

2. Vykonajte analýzu booleovskej funkcie f: Z23 --> Z2 podľa nasledujúcej schémy:
a) určte hodnotu kritéria SAC 3b
b) určte nelinearitu funkcie 5b
c) určte entrópie "bit na bit" H(Xi/f(X)) 6b
f(x) = 1, 0, 1, 0, 1, 0, 1, 0 pre x = 0,1,2,3,4,5,6,7.

3. Na šifrovanie používame blokový šifrátor B s rozsahom kľúča 32 bitov. Ak budeme používať opakované šifrovanie E(x) = B(B(x,k1),k2), aká bude pre oponenta efektívna dĺžka kľúča, ak uvažujeme aj tzv. narodeninový paradox? Popíšte aj príslušný útok.
4b.

Úlohy navyše

f: Z2n --> Z2, f' = f+1. Dokážte nasledujúce tvrdenia (každá správna odpoveď 3 body):
1. SAC(f) = SAC(f').
2. Ak f je afinná funkcia, potom SAC(f) = 0 alebo 2n.
3. H(Xi/f(X)) = H Xi/f'(X)).
4. N(f) = N(f'). Čo z toho vyplýva pre výpočet nelinearity?

Riešenie

1.
a) y = (10101010) -> m3 = (1010) m4 = (1010)
m2 = m4+f(m3,k) = m4+m3+k = (1010)+(1010)+(1111) = (1111)
m1 = m3+f(m2,k) = m3+m2+k = (1010)+(1111)+(1111) = (1010)
m0 = m2+f(m1,k) = m2+m1+k = (1111)+(1010)+(1111) = (1010)
x = (m1,m0) = (101010101)

b) šifrovanie:
x = (m0,m1), y = (m4,m3) nie (m3,m4)
m2 = m0+m1+k
m3 = m1+[m0+m1+k]+k = m0
m4 = m2+f(m3,k) = m2+m0+k = m0+m1+k+m0+k = m1
Ek(x) = Ek(x1x2x3x4x5x6x7x8) = (x5x6x7x8x1x2x3x4)
dešifrovanie:
m2 = m4+m3+k
m1 = m3+m2+k = m3+[m4+m3+k]+k = m4
m0 = m2+m1+k = m4+m3+k+m4+k = m3
Dk(y) = Dk(y1y2y3y4y5y6y7y8) = (y5y6y7y8y1y2y3y4)

2.
a) SAC(f)=SUMA(f(x)+f(x+ci)) = 8,0,0 = 8
b) N(f) = 0, pretože funkcia f(x) sa dá presne popísať afinnou funkciou x0+1, ktorej stupeň je 1
c) H(Xi/f(X)) = H(Xi,f(x))-H(f(x))
H(f(x)) = 1 pre balansované funkcie,
H(X0,f(x)) = -SUMA(p*log2p) = 1 => H(X0/f(x)) = 0
H(X1,f(x)) = -SUMA(p*log2p) = 2 => H(X1/f(x)) = 1
H(X2,f(x)) = -SUMA(p*log2p) = 2 => H(X2/f(x)) = 1

3. E(X)=B(B(X,k1),k2)=Y, B(X,k1)=B-1(Y,k2)
Hľadáme 2 kľúče dĺžky 32 bitov (t.j. spolu 64 bitov), keď poznáme jeden pár otvoreného a zašifrovaného textu X, Y=B(X,k). Otvorený text šifrujeme kľúčom k1 a zašifrovaný text dešifrujeme kľúčom k2, pričom k1 a k2 volíme náhodne (ale rozumne). Ak nastane zhoda B(X,k1)=B-1(Y,k2), potom hľadaný kľúč dĺžky 32 bitov k = k1 je odhalený. Pri použití narodeninového paradoxu platí, že priemerný počet realizácií testu možno odhadnúť n = 1,2*|V|0,5, kde V predstavuje množinu všetkých kľúčov K, t.j |V|=264. Potom odhad n=233, čiže efektívna dĺžka kľúča pre oponenta je 33 bitov.

Riešenie úloh navyše

1. SAC(f) = SUMA[f(x)+f(x+ci)] = SUMA[f(x)+1+f(x+ci)+1] = SUMA[f'(x) + f'(x+ci)] = SAC(f')

2. f(x) = A + SUMA[aixi], f(x+ci) = A + SUMAi<>j[aixi+aj(xj+1)]
f(x)+f(x+ci) = (A+SUMA[aixi]) + (A+SUMA[aixi+aj(xj+1)]) = aj
=> SAC(f) = SUMAj[aj] = 0 ak aj=0 alebo 2n ak aj=1

3. H(Xi/f(X)) = p(f(X)=0) H(Xi/f(X)=0) + p(f(X)=1) H(Xi/f(X)=1) = p(f'(x)=1)H(Xi/f'(X)=1) + p(f'(x)=0)H(Xi/f'(X)=0) = H(Xi/f'(X))

4. g je afinná funkcia, |a| je Hammingova váha
|f+g| = n-|f'+g| = n-|(f+g')'| = n-(n-|f'+g'|) = |f'+g'|
=> {f+g} je totožná s {f'+g'}
=> N(f) = N(f')