URAL 1141. RSA Attack RSA加密演算法

意甲冠軍：給你e n c 并有m^e = c(mod n) 求 m

過程大緻是

1.發送的資訊是m

2.随機選擇兩個質數 p和q, n = q*p, n的歐拉函數值φ(n）= (p-1)*(q-1)這個須要證明 

3.選擇一個與φ(n)互質的而且小于φ(n)的數e, 計算c = m^e(mod n)

4.發送c

5解密 求e的逆元d 逆元就是2個數乘一下在mod一個數等于1 這裡就是e*d = 1(mod φ(n))

求逆元用擴充歐幾裡德或者直接求高速幂

6.計算c^d(mod n) 就是m

版權聲明：本文部落格原創文章，部落格，未經同意，不得轉載。

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/4663333.html，如需轉載請自行聯系原作者