34y (mod 97) A·?
1 (mod 97) 34y
1 (mod 97) 12.
lekcija kursā "Kriptogrāfija"lektors : prof. R.-M. Freivalds
[Turpinājums iepriekšējā (11.) lekcijā sāktajam uzdevumam -
protokola "Monētas mešana pa telefonu" piemērs]
p=37
q=97
n=p·q=3589
Z=u2=2902
{ |
u=±4(mod 37) |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
u=±34(mod 97) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
u1,u2,u3,u4="Ö 2902"(mod 3589)
|
|
+34(mod 97) |
-34(mod 97) |
|
+4(mod 37) |
|
|
|
-4(mod 37) |
|
|
A·37y34y (mod 97)
A·? 1 (mod 97)
34y 1 (mod 97)
3495 1
y=3495(mod 97)
|
341=34 (mod 97) |
|
|
342=89 (mod 97) |
|
|
344=64 (mod 97) |
|
|
348=22 (mod 97) |
|
|
3416=96 (mod 97) |
|
|
3432=1 (mod 97) |
|
|
3464=1 (mod 97) |
3495=3464·3416·348·344·342·341
3495 (mod97)=(1·96·22·64·89·34)(mod97)=20
A·37y(mod 97) 37y(mod 97)
{ |
A·? |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
34·y |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
37·20(mod 97)=61
{ |
A·61 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
34·20 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A·61 1(mod 97)
6195(mod 97) ?
|
611=61 (mod 97) |
|
|
612=35 (mod 97) |
|
|
614=61 (mod 97) |
|
|
618=35 (mod 97) |
|
|
6116=61 (mod 97) |
|
|
6132=35 (mod 97) |
|
|
6164=61 (mod 97) |
6195(mod 97)=6164+6116+618+614+642+611=(61·61·35·61·61·35)(mod 97)=35
(A·37+B·97)(mod 3589)=(35·37+5·97)(mod 3589)=
=(1295+485) (mod 3589)=1780
3589-1780=1809
|
|
+34(mod 97) |
-34(mod 97) |
|
+4(mod 37) |
1780 |
|
|
-4(mod 37) |
|
1809 |
B·97(mod 37) -4(mod 37) -4(mod 37)=33
B·23 33(mod 37)
{ |
B·? |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
33·y |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
y=3335(mod 37)
|
331=33 (mod 37) |
|
|
332=16 (mod 37) |
|
|
334=34 (mod 37) |
|
|
338=9 (mod 37) |
|
|
3316=7 (mod 37) |
|
|
3332=12 (mod 37) |
3335(mod 37)=(3332+332+331)(mod 37)=(12·16·33)(mod 37)=9
B·(9·23)(mod 37) 1(mod 37)
B·22 1(mod 37)
B=2235(mod 37) 221=22
|
221=22 (mod 37) |
|
|
222=2 (mod 37) |
|
|
224=9 (mod 37) |
|
|
228=7 (mod 37) |
|
|
2216=12 (mod 37) |
|
|
2232=33 (mod 37) |
2235(mod 37)=(2232+222+221)(mod 37)=(33·3·22)(mod 37)=32
(A·37+B·97)(mod 3589)=(35·37+32·97)(mod 3589)=810
3589-810=2779
|
|
+34(mod 97) |
-34(mod 97) |
|
+4(mod 37) |
1780 |
2779 |
|
-4(mod 37) |
810 |
1809 |
[Beigas iepriekšējā lekcijā sāktajam uzdevumam]
Protokols par to
"Kā salīdzināt vecumu, neatklājo to ?" Alise un Bobs nolēmuši apprecēties, taču ir liela problēma: Alise ļoti vēlas uzzināt, vai Bobs
ir par viņu vecāks, taču neviens no viņiem negrib otram atklāt savu vecumu. (Līdzīgi var gadīties
diviem miljonāriem, kas grib uzzināt, kurš ir bagātāks, bet negrib atklāt mantas apmērus u.c.
noslēpumainiem, bet zinātgribošiem cilvēkiem.)
Tūdaļ tiks piedāvāts brīnišķīgs protokols, kā salīdzināt skaitļus
Alises (A) vecums: i 1£ i£ 100
Boba (B) vecums: j 1£ j£ 100
Abi lieto RSA kriptosistēmu. E
A,EB (encryption) - publiski zināmas, DA,DB (decryption) - katrs zina tikai savu.
Solis #1: B izvēlas lielu gadījuma skaitli X un slepeni izrēķina
EA(X)=K
Solis#2: B paziņo A skaitli
K-j
Solis #3: A izrēķina skaitļus
Yu=DA(K-j+u), 1£ u£ 100
Tad A izvēlas lielu gadījuma pirmskaitli
p (skaitļa p aptuvenam izmēram jābūt drusku mazākam
A izrēķina skaitļus
Zu=Yu(mod p), 1£ u£ 100.
Viņa pārbauda, vai taisnība, ka
|Zu-Zv| ³ 2 un 0£ Zu<p-1
Ja tā nav, tad A izvēlas citu pirmskaitli, līdz izdodas.
Solis #4: A paziņo B skaitļu virkni šādā secībā:
Z1,...,Zi,...,Zi+1+1,Zi+2,...,Z100+1,p
Solis#5: B pārbauda, vai j-ais skaitlis šajā virknē ir kongruents ar x(mod p)
Ja jā, tad
i³ jJa nē, tad i<j
Solis #6: B paziņo A rezultātu.