公钥密码学 RSA算法 实战

Problem

1. Test all odd numbers in the range from 233 to 241 for primality using the Miller-Rabin test with 2.
2. Encrypt the message M=2 using RSA with the following parameters. n=56153,e=23
3. Compute a private key(d,p,q)corresponding to the public key.  Hint: p and q are in the above range
4. Decrypt the ciphertext obtained above using the CRT.

Answer:

1. we get  233,239,241 is prime.

2.   C=M^e mod n=2^23 mod 56153=

2^1 mod 56153= 2

2^2 mod 56153= 4

2^4 mod 56153= 16

2^8 mod 56153= 256

2^16 mod 56153= 65536

2^23 mod 56153= (2^16 * 2^4 * 2^2 * 2^1) mod 56153 =28211

3.  because p and q are in the above range

 so p q are {233, 241}

Ø(n)=(p-1)(q-1)=232*240=55680 

ed=1 mod Ø(n) --->  d=e^-1 mod Ø(n)

d= 23^-1 mod 55680= 19367  (Using Extended Euclidean algorithm)

thus PR={19367,233,241}  

PU={23,233,241}

 PS：

23d=1 mod 55680

d=23^-1 mod 55680

55680=23*2420 + 20

23= 20*1 + 3

20=3*6 + 2

3= 2 + 1  

/********开始反写********/

1 = 3- 2

1= 3- (20- 3*6)

1= 3-20+3*6 = 7*3 -20=7*(23- 20*1)-20

=7*23-7*20-20=7*23- 8*20=7*23-8*（55680-23*2420）

1 =7*23- 8*55680+ 8*23*2420     //划去8*55680

1=7*23+8*23*2420

1=23*（7+8*2420）

1=23*19367

because 23d=1 

thus d=19367

4.  M=C^d mod n= 28211^ 19367 mod 56153= ??? use CRT

dp=d mod(p-1)=19367 mod 232=111

dq=d mod (q-1)=19367 mod 240 =167

Cp= C mod p

Mp=Cp^dp mod p=141^111 mod 233=2

Cq= C mod q

Mq= Cq^ dq mod q =121^167 mod 241=2

M=2

Adding：Extended Euclidean algorithm

17X =1 (mod 43) 

X=17^-1 mod 43

43= 17*2 + 9

17=9*1+ 8

9=8*1 +1 

1= 9- 8

sub. 8= 17-9 

1= 9 -(17-9)

1= 9-17 +9

1= 2* 9- 17

sub. 9=43- 17*2

1=2(43-17*2)-17

1= 2*43- 4*17 -17

1=2* 43 - 5*17  //2*43可以划去

17^-1 mod 43 =-5=38