Infomácie o ZK

Prednášky

Zadania

Archív

Hodnotenie

Test č.3

Záverečný test sa uskutočnil 18.12.2000 a jeho hodnotenie bolo 50 bodov.

Zadanie

1a) Zistite či číslo N=2021 je provčíslo s pomocou Solovayovho testu? Za náhodne zvolené číslo zvoľte a=15. Popíšte postup! (6+6+3 bodov)
1b) Nájdite faktorizáciu N s pomocou Fermatovej faktorizácie. (3 body)

2. Kraitchikovou metódou faktorizujte číslo 697. (7 bodov)

3a) Pre RSA systém boli zvolené prvočísla p=5, q=7 a šifrovací exponent e=5. Vysvetlite, prečo je táto voľba zlá. (Rozsah čísel neuvažujeme!) (3 body)
3b) Dokážte, že idempotent pologrupy Zn sa nikdy nezašifruje. Nájdite ich (nie hrubou silou!), ak p=5, q=7, e=11. (5+5 bodov)

4. Pre RSA systém boli zvolené provočísla p=11, q=13 a exponenty e=7 a d=103. Rýchlym dešifrovaním zistite x, ak y=42. (9 bodov)

5. V sieti sa používa ruksakový kryptosystém a šifrujú sa 8 bitové správy. Vysvetlite, čo sa stane, ak Alica pošle rovnakú správu 8 rôznym adresátom. (3 body)


Riešenie

1a)
J(a/n)=J(15/2021)=J(3/2021)*J(5/2021)=J(2/3)*J(1/5)=-1 (6 bodov)
a(p-1)/2=a1010=1988 (6 bodov)
n=2021 neprešlo Solovayovým prvočíselným testom (3 body)

1b)
k=CELL(SQRT(2021))=CELL(44.95)=44
xi=i+k=i+44
yi=SQRT[xi2-n]=SQRT[(i+44)2-2021]
i=1 => x=45 => y=2 => p=x-y=43 => q=47
2021=43*47

2.
yi=SQRT((26+i)^2-697)
y1=25, y2=3*29, y3=2^4*3^2=12^2
teda 29^2=12^2 mod 697 odkiaľ:
(29-12)(29+12)=7*41, nsd(697,41)=17
697=17*41

3a)
nezašifruje sa 15 z 35 správ (1 bod)
d=e (1 bod)
obežník pre 5 ľudí (1 bod)

3b)
x2=x mod n
e je nepárne --> xe=x

idempotentné prvky v Z35:
x=0 a x=1 (1 bod)
x=15 (2 body)
x=21 (2 body)

4.
(1 bod za každú správnu hodnotu)
d1=d (mod p)=103 (11)=3
d2=d (mod q)=103 (13)=7
uq=1 (mod p) => 13*u=1 (11) => u=6
vp=1 (mod q) => 11*v=1 (13) => v=6
y1=y (mod p)=42 (11)=9
y2=y (mod q)=42 (13)=3
x1=yd1 (mod p)=423 (11)=3
x2=yd2 (mod q)=427 (13)=3
x=x1uq+x2vp=3

5.
zašifrovanie správy b: c=w'*b
ak má správa 8 bitov a je poslaná 8-mim osobám: c=A*b,
dostaneme systém lineárnych rovníc a môžeme vyrátať b - t.j. určiť pôvodnú správu
(1 bod za podmienku det A > 0)