Tài liệu Tiểu luận toán-mã hóa công khai hệ mã hóa rsa

Ê




Ê

 

c 



c 

Ê
3 b đӗng dư modulo n nӃu |3
b| là bӝi sӕ cӫ3 n Tӭc: NӃu chi3 3 cho n; b chi3 cho n thì nhұn cùng sӕ dư ›

3
!
"
#
$
%

&'
(: 13 !
3 (mod 10) vì (13 ± 3) = 10 là bӝi sӕ cӫ3 10 Modulo có mӕi qu3n hӋ vӟi sӕ dư trong phép chi3 phép toán tìm sӕ dư đôi khi cũng giӕng như phép toán modulo. 2 ! 14 ($ 12) &'
(: 2 ) 14 ($ 12) Nhưng: 38 Ł 14 ($ 12) thì đúng nhưng 38 = 14 ($ 12) lҥi không đúng
*c +,+
-.
Ê
ӕ nghӏch đҧo cӫ3 10 là 1/10 bӣi vì 10 × 1/10=1. Trong sӕ hӑc modulo thì vҩn đӅ nghӏch đҧo phӭc tҥp hơn. 4 × x Ł 1 mod 7 Phương trình trên tương đương vӟi tìm x và k s3o cho 4x = 7k+1 vӟi điӅu kiӋn là cҧ x và k đӅu là sӕ nguyên. Vҩn đӅ chung đһt r3 tҥi đây là tìm x s3o cho 1 = (3 × x) mod n có thӇ viӃt lҥi như s3u : 3
1 Ł x(mod n )  thu nhӓ vҩn đӅ Modulo là rҩt khó giҧi quyӃt. Đôi khi nó là mӝt vҩn đӅ nhưng đôi khi lҥi không phҧi vұy. Ví dө : nghӏch đҧo cӫ3 5 modulo 14 là 3 bӣi 5 × 3 = 15 Ł 1 (mod 14). /
(
0+10
0
23
$
45
-6
0'+
+,+
-.
Ê
Giҧi thuұt s3u sӁ tính nghӏch đҧo modulo m cӫ3 3 và chӍ th c hiӋn vӟi các sӕ nguyên m>3>0 biӇu diӉn bҵng giã mã: 1










R
    c 
Jcc

J c c 2 c
c
cc ccc ccccc c c ccc ccccc c 
cc ccccccc cccccc c cc ccccc c
 c ccccc c ccccc c ccccc
 cccccc ccccc  c ccc cc c     c c c c  c c !"c cc c cc# c!c "$c c %cc$&c c &'
(
Tìm sӕ nghӏch đҧo (nӃu có) cӫ3 30 theo môđun 101 Bưӟc i 0 1 2 3 4 5 $ 9 30 11 8 3 2 KӃt quҧ tính toán trong bҧng cho t3 64. Vұy :9;
$
9)
=>





3 :9 11 8 3 2 1 4 11 8 3 2 1 0 7 3 2 1 2 1 . 89 0 1
3 7
10 . 8 1
3 7
10 27 . 8
3 7
10 27 ;:< . 37. Lҩy sӕ đӕi cӫ3 37 theo mođun 101 đưӧc 2 :c 3.3
"?3
0
)"@
$

AB3
C
B
Trong đó e là sӕ mũ lӟn n là sӕ chi3 đӇ lҩy dư &'
( Tính 413(mod 497) Cách tính đơn thuҫn: 413=67108864 67108864 mod 497 =445 e @ NӃu b và e lӟn thì b sӁ rҩt lӟn và tính "
$

sӁ mҩt nhiӅu thӡi gi3n và tӕn bӝ nhӟ. Có mӝt sӕ cách đӇ giҧi quyӃt vҩn đӅ đó. Trong nӝi dung cӫ3 tiӇu luұn chúng tôi sӱ dөng giҧi pháp như s3u: c Ł (3.b)(mod n) => ((3 (mod n)).(b (mod n))) (mod n) Áp dөng công thӭc trên t3 có thuұt toán L0

 
t0L0
Ł   

1/ Gán c=1 e¶=0 2/ e¶=e¶+1 3/ c Ł (b.c) (mod m) 4/ NӃu e¶%
T3 thҩy N =pxq vӟi p q là sӕ nguyên tӕ. Trong toán hӑc đã chӭng minh đưӧc rҵng nӃu N là sӕ nguyên tӕ thì công thӭc (4) sӁ có lӡi giҧi khi và chӍ khi: PGP
!
#$ w %#T%
Trong đó w N =LCM(p
1 q
1 ). (Lest Common Multiple) là bӝi sӕ chung nhӓ nhҩt . Nói mӝt cách khác đҫu tiên ngưӡi nhұn B l 3 chӑn mӝt khó3 công kh3i KB mӝt cách ngүu nhiên. Khi đó khó3 bí mұt kB đưӧc tính r3 bҵng công thӭc (5). ĐiӅu này hoàn toàn tính đưӧc vì khi B biӃt đưӧc cһp sӕ nguyên tӕ (p q) thì sӁ tính đưӧc w N Chӑn p và q Tính N = p x q Tính w N Bҧn rõ P KB C = PKB (mod N) Chӑn khó3 KP
Bҧn mã C kB Chӑn khó3 kP
P = CkB (mod N) Bҧn rõ gӕc M+
< 
-

"B
0+U
+3D
$E
+F3
0+@
0+10
0
 





&'
(
N=11413=101x113 w (N) =100x112 =11200 =26x52x7. KB phҧi chӑn s3o cho không chi3 hӃt cho 2 5 7. Chӑn chҷng hҥn KB =3533 khi đó kB = KB
1mod11200=6597. Và t3 có khó3 công kh3i là (N KB)=(11413 3533) khó3 bí mұt là 6597. Phép lұp mã và giҧi mã là 5 EKB(P) =PKB (mod N) =P3533 (mod 11413) DkB(C) =CkB (mod N) =C6579 (mod 11413) 
?3
-V0
0+10
0
 

—c Chương trình đưӧc viӃt bҵng ngôn ngӳ lұp trình C# có chӭc năng mô phӓng lҥi toàn bӝ quá trình mã hó3 và giҧi mã cӫ3 thuұt toán RA. —c |iӋn tҥi thuұt toán chӍ cài đһt mã hó3 các ký t ho3 không dҩu. Gi3o diӋn cӫ3 chương trình ëc w
04M+
I/
W
O3
+
04M+
+
3
P: Nhұp văn bҧn cҫn mã hó3 vào ô ³Văn bҧn gӕc´ ‰
 CO O TOAN P*: Chương trình sӁ chuyӇn đәi văn bҧn đó thành chuӛi sӕ bҵng cách d 3 trên sӕ thӭ t cӫ3 chӳ cái đó trong bҧng chӳ cái. CO O TOAN
> 03152719152720150114 P:: Mã hó3 chuӛi sӕ d 3 trên +F3
$E và sӕ  03152719152720150114
> 64241131545795607113154579471131517289 P>: Giҧi mã d 3 trên +F3
3.3
64241131545795607113154579471131517289
> 03152719152720150114 PT: Đư3 r3 văn bҧn gӕc d 3 trên chuӛi sӕ đưӧc giҧi mã 6