2.3 Rabin’s Crypto System

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

系統說明如下：

1.      選兩個大質數P1、P2  得N= P1xP2

公開N  保留P1、P2

2.      加密過程：

　 C≡M²    mod N   其中C為密文 (Ciphertext)

                                          M為明文 (Plaintext)

3. 解密過程：

   M≡C^(P1+1)/4   mod P1

   M≡C^(P2+1)/4   mod P2

 利用中國餘式定理 解出M

                     

例題：給定p為19  q為23  得N為 437   明文M為30

解：

　　加密

C≡M² ≡900≡26   mod 437

   解密

M²≡26   mod 19

M²≡26   mod 23

M²≡7   mod 19

M²≡3   mod 23

得

M≡+- 11   mod 19

M≡+- 16   mod 23

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

(1)

M≡11   mod 19

M≡16   mod 23

(2)

M≡11   mod 19

M≡-16   mod 23

(3)

M≡-11   mod 19

M≡16   mod 23

(4)

M≡- 11   mod 19

M≡- 16   mod 23

解第(1)組

M≡11   mod 19

M≡16   mod 23

M≡(23xa1x11+19xa2x16)    mod437

其中 4a1≡1  mod19

     19a2≡1  mod23  得 a1=5  a2=-6   帶入

M≡23x5x11+19x(-6)x16     mod437

M≡-559    mod437

M≡315    mod437  ---(1)

解第(2)組

M≡11   mod 19

M≡-16   mod 23

M≡(23xa1x11+19xa2x7)    mod437

其中 4a1≡1  mod19

     19a2≡1  mod23  得 a1=5  a2=-6   帶入

M≡23x5x11+19x(-6)x7     mod437

M≡467    mod437

M≡30   mod437  ---(2)

解第(3)組

M≡-11   mod 19

M≡16   mod 23

M≡(23xa1x8+19xa2x16)    mod437

其中 4a1≡1  mod19

     19a2≡1  mod23  得 a1=5  a2=-6   帶入

M≡23x5x8+19x(-6)x16     mod437

M≡-904   mod437

M≡407   mod437  ---(3)

解第(4)組

M≡-11   mod 19

M≡-16   mod 23

M≡(23xa1x8+19xa2x7)    mod437

其中 4a1≡1  mod19

     19a2≡1  mod23  得 a1=5  a2=-6   帶入

M≡23x5x8+19x(-6)x7     mod437

M≡122    mod437  ---(4)

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