حل تمرین RSA

بینهایت ! هیچ سوال دیگری تا به حال به این اندازه روح انسان را متحول نساخته .
دیوید هیلبرت

خوب  این هم  حل مسئله قبلی که جوابش 16657  بود:
 
فرض مسئله :

 
N=p.q=97x173=16781

M=(p-1)(q-1)=96x172=16512

(غ.ق.ق)e = 2 => gcd(e, 16512) = 2
(غ.ق.ق)e = 3 => gcd(e, 16512) = 3
(غ.ق.ق)e = 4 => gcd(e, 16512) = 4
e = 5 => gcd(e, 16512) = 1=> e=5

؟=C = Pe % n=5347                  &            p

حل مسئله :

برای حل مسئله مجبوریم d را پیدا کنیم اما کاملا دقت داشته باشید که تنها کسی می تواند d  را پیدا کند که از m و در نتیجه از q و p مطلع باشد :

ed=1(mod (p-1)(q-1))   =>   ed=1(mod  M)   =>    

= > de % M = 1   =>     de = 1 + nM

=>  d = (1 +nM) / e

 

n = 1 => d = 16513 / 5 (غ.ق.ق)
n = 2 => d = 33025/ 5 =6605 (ق.ق)     => d= 6605

 

خوب حالا برای رمزگشایی بصورت زیر عمل می کنیم :

P = C^d % N=5347⁶⁶⁰⁵ % 16781=?

 

6605=4096+2048+256+128+64+8+4+1

 

 

5347² % 16781=12366

 

5347⁴ % 16781=12366² % 16781=9484

 

5347⁸ % 16781=9484² % 16781=96

 

5347¹⁶ % 16781=96² % 16781=9216

 

5347³² % 16781=9216² % 16781=6015

 

5347⁶⁴ % 16781=6015² % 16781=389

 

5347¹²⁸ % 16781=389² % 16781=292

 

5347²⁵⁶ % 16781=292² % 16781=1359

 

5347⁵¹² % 16781=1359² % 16781=971

 

5347¹⁰²⁴ % 16781=971² % 16781=3105

5347²⁰⁴⁸ % 16781=3105²  % 16781=8731

 

5347⁴⁰⁹⁶ % 16781=8731²  % 16781=11059

 

 

=>  5347⁶⁶⁰⁵ % 16781=5347^{4096+2048+256+128+64+8+4+1} % 16781

 

=11059 x 8731 x 1359 x 292 x 389 x 96 x 9484 x 5347  % 16781

 

=16657