- 1
: .. -10-13
.
. 103222
: ..
2012 .
:
充..3
充.4
..5
1..5
2..7
䅅10
.11
, RSA.
, .
1
RSA . . i ( ) , j- p q.
:
:
j=2
p=3
q=11
2
2, - m - , .509. H .
RSA , - m .
.
1
RSA . . i ( ) , j- p q.
:
:
j=2
p=3
q=11
1. n:
n=p*q
n=3*11=33
2.
f(p*q)=(p-1)*(q-1)
f(p*q)=(3-1)*(11-1)=2*10=20
1 n, , 1.
3. , , f(p*q)
e*d=k*f(p,q)+1
, =3, , =2
3*d=1*20+1
3*d=21
d=7
e=3
4. d ,
e*d(mod f(p*q))=1
3*7(mod20)=1, , , , d .
|
|
|
n . d n.
5. . L , L- ,
L>=log2(N+1);
L>=log2(33+1);
L=5
X(i), (0, n-1). , X(i), (i=1.I). I .
6. 0 32:
0 32:
13,9,14,20,18.
6 , 33 , :
7.
(Y(i))=(Y(i))^e*(mod n)
, {3,33}
Y1=(133)mod33=19;
Y2=(93)mod33=3;
Y3=(143)mod33=5;
Y4=(203)mod33=14;
Y5=(183)mod33=24;
8. , {27,33}
Y1=(1927)mod33=13;
Y2=(327)mod33=9;
Y3=(527)mod33=14;
Y4=(1427)mod33=20;
Y5=(2427)mod33=18;
, <13,9,14,20,18> . .
2
2, - m - , .509. 0 .
RSA , - m d.
.
- .509 :
Hi=[(Hi-1+ Mi)2](modn),
i=1,n,H0 ;
Mi=M1,M2,M3Mn .
. . - .509 p=3,q=11.
1. :
n=p*q
n=3*11=33
2. :
3. , Mi
|
|
|
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 10 |
4. :
1 2
| 1 | |
| + | |
| 0 | |
| 1+ 0 | 11110000=24010 |
| [(0+ 1)2](mod33) | 2402mod33=15 |
| H1 |
| 2 | |
| + | |
| 1 | |
| 2+ 1 | 11110010=24210 |
| [(1+ 2)2](mod33) | 2422mod33=22 |
| H2 |
3 7
| 3 | |
| + | |
| 2 | |
| 3+ 2 | 11100110=23010 |
| [(2+ 3)2](mod33) | 2302mod33=1 |
| H3 |
| 7 | |
| + | |
| 6 | |
| 7+ 6 | 11101110=23810 |
| [(6+ 7)2](mod33) | 2382mod33=16 |
| H7 |
4 8
| 4 | |
| + | |
| 3 | |
| 4+ 3 | 11111000=24810 |
| [(3+ 4)2](mod33) | 2482mod33=25 |
| H4 |
| 8 | |
| + | |
| 7 | |
| 8+ 7 | 11100100=22810 |
| [(7+ 8)2](mod33) | 2282mod33=9 |
| H8 |
5 9
| 5 | |
| + | |
| 4 | |
| 5+ 4 | 11101001=23310 |
| [(4+ 5)2](mod33) | 2332mod33=4 |
| H5 |
| 9 | |
| + | |
| 8 | |
| 9+ 8 | 11111000=24810 |
| [(8+ 9)2](mod33) | 2482mod33=25 |
| H9 |
6 10
| 6 | |
| + | |
| 5 | |
| 6+ 5 | 11111010=25010 |
| [(5+ 6)2](mod33) | 2502mod33=31 |
| H6 |
| 10 | |
| + | |
| 9 | |
| 10+ 9 | 11101011=23510 |
| [(9+ 10)2](mod33) | 2352mod33=16 |
| H10 |
, - m=16
:
S=md(modn)=167(mod33)=25
(M,S) , S, S d.
(M,S), - :
- m, S :
m=Se(modn)=253mod33=16
-: m=H(M)=16
m m (M,S) .
- RSA , .
:
n=55;
f(p*q)=20
d=7
e=3
, :
13,9,14,20,18.
{3,33}; {27,33}.
RSA , - m=16 d=7.
1. . , . ,2006 .
2. .. . 2- . - : 2000 .
3. .. ./ . ... - : 1999 .
