Datu aizsardzība un kriptogrāfija. 11. Lekcija

"Datu aizsardzība un kriptogrāfija."
Pasniedzējs prof. R.-M. Freivalds

11. lekcija

Protokols "Monētas mešana pa telefonu"

Darbojas divas personas: Alise un Bobs, kas viena otrai neuzticas. Mērķis "mest monētu", lai noskaidrotu "uzvarētāju", tā, lai abiem būtu vienādas izredzes uzvarēt un nevienam no dalībniekiem nebūtu iespējas krāpties.

Protokola realizācija:

Solis 1
A izvēlas divus lielus pirmskaitļus p un q un paziņo to reizinājumu n=p*q.

Solis 2
B izvēlas gadījuma skaitli u no intervāla (1 .. n/2) un paziņo z=u²(mod n).

Solis 3
A izrēķina ± x un ± y , t.i. visas 4 kvadrātsaknes no z. Tas ir iespējams, jo A zin, ka n=p*q. Ar x' apzīmē mazāko no x (mod n), un (-x)(mod n). Līdzīgi ar y' apzīmē mazāko no y (mod n), (-y) (mod n). Pievērsiet uzmanību tam , ka u=x' vai u=y'.

Solis 4
A zin, vai u=x' vai u=y'. Precīzāk, A atrod mazāko skaitli i, tādu, ka i-ais bits skaitlim x' atšķiras no i-tā bita skaitlim y' un dod vienu no paziņojumiem: "i-tais bits skaitlim u ir 0" vai "i-ais bits skaitlim u ir 1"

Solis 5
B pasaka A, vai uzminēts pareizi.

Solis6
B pasaka A skaitli u.

Solis7
A pasaka skaitļa n reizinātājus p un q.

Piemērs:

Solis1:
A izvēlas divus lielus pirmskaitļus p un q un paziņo to reizinājumu n=p*q.

p=37
q=97
n=3589

Solis2:
B izvēlas gadījuma skaitli u no intervāla (1 .. n/2) un paziņo z=u²(mod n).

u=1780
z=1780²(mod 3589)=2902

Solis3:
A izrēķina ± x un ± y , t.i. visas 4 kvadrātsaknes no z. Tas ir iespējams, jo A zin, ka n=p*q. Ar x' apzīmē mazāko no x (mod n), un (-x)(mod n). Līdzīgi ar y' apzīmē mazāko no y (mod n), (-y) (mod n). Pievērsiet uzmanību, ka u=x' vai u=y'.

A saņem z=2902 (mod 3589), tā kā A zin ka 3589=37*97, tad var risināt sistēmu:

{	u²=2902 mod(37)
	w²=2902 mod(97)

{	u²=16 mod(37)
	w²=89 mod(97)

u1=4 mod(37) un u2=33 mod(37)

Rēķinam w1 un w2 pēc devītajā lekcijā aprakstītā varbūtiskā algoritma:

1.
u²=89(mod 97)
p=97 p-1=96=2^e*q=2⁵*3
(n/p)=-1
n=5
z=n^q (mod p)
z=5³ (mod 97)=28

2.
y=28
r=5
x=a^{^(q-1)/2} (mod p)
x=89
b=a*x^² (mod p)=89*89^²(mod 97)=70
x=a*x(mod p)= 89*89(mod 97)=64

3.
(b^²)^{^m}1(mod 97)
m=1 50
m=2 73
m=3 96
No tā redzam ka mazākais m ir 4

4.
t=(y^²)^{^R-m-1}
t=(28^²)^{^5-4-1}=28
y=28^² (mod p) = 8
r=u x=64*28(mod 97) = 46 b=70*8=75

3.
(75^²)^{^m} 1(mod p)
m=1 96
m=2 1 - der.

4.
t=(8^²)^{^4-2-1} =64
y=64^²(mod 97) = 22
r=m
r=2
x=x*t=46*64(mod 97)=34
b=b*y=75*22(mod 97)=1

3.
? b1(mod 97)
Jā 11(mod 97)

No tā ir iegūts x =34
Tātad w134 un w2-w163

Meklē ± x un ± y formā (A*37+B*97) (mod 97*37).
Pirmajai saknei rēķina:
A*3734 (mod 97) un B*974 (mod37)

B*974(mod 37)
meklē tādu s, lai 97*s1(mod 37)
Pēc Fermā teorēmas s97^³⁵(mod 37), jeb s23^³⁵(mod 37)
23^¹=23 (mod 37)
23^²=11 (mod 37)
23^⁴=10 (mod 37)
23^⁸=26 (mod 37)
23^¹⁶=10 (mod 37)
23^³²=26 (mod 37)
s23^³⁵(mod37)26*11*23 (mod 37)29

B4*29 (mod 37)=5

[Turpinājums nākamajā lekcijā]