Infomácie o ZK

Prednášky

Zadania

Archív

Hodnotenie

Test č.1

Test sa uskutočnil 5. týždeň - 24.10.2000 a jeho hodnotenie bolo 25 bodov.

Zadanie

Používa sa základná 26-znaková telegrafná abeceda.
Najväčšiu frekvenciu v SJ majú: A,E,O,S,N,I,T,...

1. Text je zašifrovaný afinnou šifrou: LHGFUXQNTJMXSHOH
Nájdite priamy text.
5b

2. Používa sa telegrafná abeceda (26 znakov) a Hillovská šifra šifrujúca bigramy. Určte maticu K, ak viete, že friday -> PQCFKU.
5b

3. Uvažujte kryptosystém P={a,b,c}, K={k1,k2,k3}, C={1,2,3,4}. Frekvencie vstupných znakov sú 1/2, 1/3 a 1/6 a všetky kľúče sú rovanko pravdepodobné. Pravidlá kryptovania sú dané tabuľkou:

    a b c
k1  1 2 3
k2  2 3 4
k3  3 4 1
Vypočítajte H(P) - 3b, H(C) - 3b, H(K) - 3b, H(K/C) - 4b.

4. Definujte "unicity distance".
2b


Riešenie

1. početnosti najčastejších písmen: H - 3 krát, X - 2 krát

Afinná šifra: y = e(x) = ax + b (mod 26)

Hypotéza 1: e(a) = H, e(e) = X, dostávame rovnice:

7 = 0a + b (26)
23 = 4a + b (26)

=> b=7 => 4a=16 (26) => a=4

a sa nemôže rovnať 4, pretože (4,26)=2 sú súdeliteľné a šifra by nebola jednoznačne dešifrovateľná.

Hypotéza 2: e(a) = H, e(o) = X, dostávame rovnice:

7 = 0a + b
23 = 14a + b

=> b=7 => 14a=16 (26) => a=3

dostávame šifru: y = 3x + 7 (26) ktorej prevodová tabuľka je:

P: ABCDEFGHIJKLMNOPQRSTUVWXYZ
C: HKNQTWZCFILORUXaDGJMPSVYBE

a teda šifrový text odpovedá:

ŠT: LHGFUXQNTJMXSHOH
OT: KARINODCESTOVALA

2.

(y1,y2) = e(x1,x2) = (x1,x2) (k11 k12)
                            (k21 k22)   (mod 26)

zo OT/ŠT friday --> PQCFKU vieme, že:
e(f,r) = (P,Q)
e(i,d) = (C,F)
e(a,y) = (K,U)

z toho dostávame rovnice: (K je matica 2x2)
(15 16) = (5 17)K
( 2  5) = (8  3)K
(10 20) = (0 24)K

čiže sústavu rovníc:
15=5k11      +17k21
16=     5k12       +17k22
 2=8k11      + 3k21
 5=     8k12       + 3k22
10=0k11      +24k21
20=     0k12       +24k21

z ktorej dostávame maticu K:
k11=7, k12=19, k21=8, k22=3

K= (7 19)
   (8  3)

3. H(P), P={a,b,c}, p(P=a)=1/2, p(P=b)=1/3, p(P=c)=1/6

H(P) = - (1/2)*log2(1/2) - (1/3)*log2(1/3) - (1/6)*log2(1/6) = 1,4591 bit

H(K), K={k1,k2,k3}, p(K=k1)=1/3, p(K=k2)=1/3, p(K=k3)=1/3

H(K) = - (1/3)*log2(1/3) - (1/3)*log2(1/3) - (1/3)*log2(1/3) = 1,5850 bit

H(C), C={1,2,3,4}
p(C=1) = p(K=k1,P=a) + p(K=k3,P=c) = p(K=k1)*p(P=a) + p(K=k3)*p(P=c) = 2/9
p(C=2) = p(K=k1,P=b) + p(K=k2,P=a) = 5/18
p(C=3) = p(K=k1,P=c) + p(K=k2,P=b) + p(K=k3,P=a) = 1/3
p(C=4) = p(K=k2,P=c) + p(K=k3,P=b) = 1/6

H(C) = - (2/9)log2(2/9) - (5/18)log2(5/18) - (1/3)log2(1/3) - (1/6)log2(1/6) = 1,9547 bit

H(K/C), H(K/C) = H(K,C) - H(C)
alebo H(K/C) = H(K) + H(P) - H(C)

p(K=ki,C=j) |  1    2    3    4
---------------------------------
         k1 | 1/6  1/9  1/18  0
         k2 |  0   1/6  1/9  1/18
         k3 | 1/18  0   1/6  1/9
H(K,C) = - SUMAi=1,2,3;j=1,2,3,4 [ p(K=ki,C=j)*log2(p(K=ki,C=j)) ] = 3,0441 bit
H(K/C) = H(K,C) - H(C) = 1,0894 bit

4. UNICITY DISTANCE (dĺžka jednoznačnosti) je taká minimálna dĺžka n správy (alebo počet zašifrovaných textov Y1...Yn), pri ktorej E(Sn) = 0. Dôsledkom je, že už máme skoro úplnú informáciu o kľúči a môžeme na základe tohoto zavrhnúť všetky falošné kľúče. Takže platí H(K/Y1...Yn) -> 0 (neurčitosť o kľúči sa blíži k nule).