بینهایت ! هیچ سوال دیگری تا به حال به این اندازه روح انسان را متحول نساخته .
دیوید هیلبرت
خوب این هم حل مسئله قبلی که جوابش 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 = Cd % N=53476605 % 16781=?
6605=4096+2048+256+128+64+8+4+1
53472 % 16781=12366
53474 % 16781=123662 % 16781=9484
53478 % 16781=94842 % 16781=96
534716 % 16781=962 % 16781=9216
534732 % 16781=92162 % 16781=6015
534764 % 16781=60152 % 16781=389
5347128 % 16781=3892 % 16781=292
5347256 % 16781=2922 % 16781=1359
5347512 % 16781=13592 % 16781=971
53471024 % 16781=9712 % 16781=3105
53472048 % 16781=31052 % 16781=8731
53474096 % 16781=87312 % 16781=11059
=> 53476605 % 16781=53474096+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
