2012年6月12日 星期二

2.3 Rabin’s Crypto System


※使用二次剩餘的近代密碼系統

系統說明如下:

1.      選兩個大質數P1P2  N= P1xP2
公開保留P1P2

2.      加密過程:

  CM2    mod N   其中C為密文 (Ciphertext)
                                          M為明文 (Plaintext)

3.
解密過程:

   MC(P1+1)/4   mod P1
   MC(P2+1)/4   mod P2

 利用中國餘式定理 解出M













例題:給定p19  q23  N 437   明文M30

解:
  加密

CM2 90026   mod 437

   解密

M226   mod 19
M226   mod 23

M27   mod 19
M23   mod 23


M+- 11   mod 19
M+- 16   mod 23

由上結果可知分別有四組可能

(1)
M11   mod 19
M16   mod 23
(2)
M11   mod 19
M-16   mod 23
(3)
M-11   mod 19
M16   mod 23
(4)
M- 11   mod 19
M- 16   mod 23

解第(1)
M11   mod 19
M16   mod 23

M(23xa1x11+19xa2x16)    mod437
其中 4a11  mod19
     19a21  mod23  a1=5  a2=-6   帶入

M23x5x11+19x(-6)x16     mod437
M-559    mod437

M315    mod437  ---(1)

解第(2)
M11   mod 19
M-16   mod 23

M(23xa1x11+19xa2x7)    mod437
其中 4a11  mod19
     19a21  mod23  a1=5  a2=-6   帶入

M23x5x11+19x(-6)x7     mod437
M467    mod437

M30   mod437  ---(2)

解第(3)
M-11   mod 19
M16   mod 23

M(23xa1x8+19xa2x16)    mod437
其中 4a11  mod19
     19a21  mod23  a1=5  a2=-6   帶入

M23x5x8+19x(-6)x16     mod437
M-904   mod437

M407   mod437  ---(3)

解第(4)
M-11   mod 19
M-16   mod 23

M(23xa1x8+19xa2x7)    mod437
其中 4a11  mod19
     19a21  mod23  a1=5  a2=-6   帶入

M23x5x8+19x(-6)x7     mod437

M122    mod437  ---(4)





由四組答案可知第(2)M30   mod437  ---(2) 符合!!!!










沒有留言:

張貼留言