參考：密碼學之RSA加密RSA加密：非對稱金鑰，公開金鑰演算法RSA加密利用了單向函式正向求解很簡單，反向求解很複雜的特性。具體是利用了：1.對兩個質數相乘容易，而將其合數分解很難的這個特點進行的加密演算法。 n=p1*p2，已知p1、p2求n簡單，已知n求p1、p2困難。2.(m^e) mod n=c，已知m、e、n求c簡單，已知e、n、c求m很難。RSA加密，實現了公開金鑰，就是A可以給所有人傳送鎖，其他人把要加密的資訊用這把鎖加密後傳送給A，A用自己的鑰匙開鎖就可以獲得加密的資訊了。反過來，A要傳送加密資訊給B，只要知道B的鎖就可以了，而這個鎖是公開的。公開金鑰n、e的生成：隨機選取兩個質數p1、p2，n=p1*p2，再隨機選取一個整數e，e與φ(n)互質。加密過程：(m^e) mod n=c，其中m為原資訊，c為加密資訊，n、e為公開金鑰。解密過程：(c^d) mod n=m，其中d為解密金鑰。解密金鑰d的求解：(c^d) mod n=(((m^e) mod n)^d) mod n=((m^e)^d) mod n=(m^ed) mod n=m ①根據費馬定理(m^φ(n)) mod n≡1，又1^k≡1，所以(m^k*φ(n)) mod n≡1，兩邊同乘以m得m*((m^k*φ(n)) mod n)≡1*m，化簡(m^(k*φ(n)+1)) mod n≡m ②由①、②得ed=(k*φ(n)+1)，解得d=(k*φ(n)+1)/e。費馬定理：若p是素數，a與p互素，則a^(p-1）≡1 （mod p）過程如下：A：有一個公鑰n、e。例如：3127、3。B：有一個資訊m。例如：89。C：偷聽者A：第一步：隨機找兩個質數p1、p2，一個奇數e。例如：53、59、3。第二步：計算n=p1*p2得到n，計算尤拉函式φ(n)=(p1-1)*(p2-1)得到φ(n)，計算鑰匙d=(k*φ(n)+1)/e得到d。例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。第三步：傳送n、e給大家知道 //n、e就是公鑰也做鎖，d就是n、e的鑰匙。C：獲得n、eB：第一步：獲得n、e第二步：加密資訊m，(m^e) mod n=c，獲得加密資訊c。例如：(89^3) mod 3127=1394。第三步：傳送c給AC：第一步：截獲加密資訊c第二步：破解資訊c，此時C只有n、e、c，只有把n分解質因數才能破解，而此分解很困難特別是當n很大的時候。A：第一步：收到加密資訊c第二步：解密資訊c，(c^d) mod n=m，獲得資訊m。例如：(1394^2011) mod 3127=89。完成
參考：密碼學之RSA加密RSA加密：非對稱金鑰，公開金鑰演算法RSA加密利用了單向函式正向求解很簡單，反向求解很複雜的特性。具體是利用了：1.對兩個質數相乘容易，而將其合數分解很難的這個特點進行的加密演算法。 n=p1*p2，已知p1、p2求n簡單，已知n求p1、p2困難。2.(m^e) mod n=c，已知m、e、n求c簡單，已知e、n、c求m很難。RSA加密，實現了公開金鑰，就是A可以給所有人傳送鎖，其他人把要加密的資訊用這把鎖加密後傳送給A，A用自己的鑰匙開鎖就可以獲得加密的資訊了。反過來，A要傳送加密資訊給B，只要知道B的鎖就可以了，而這個鎖是公開的。公開金鑰n、e的生成：隨機選取兩個質數p1、p2，n=p1*p2，再隨機選取一個整數e，e與φ(n)互質。加密過程：(m^e) mod n=c，其中m為原資訊，c為加密資訊，n、e為公開金鑰。解密過程：(c^d) mod n=m，其中d為解密金鑰。解密金鑰d的求解：(c^d) mod n=(((m^e) mod n)^d) mod n=((m^e)^d) mod n=(m^ed) mod n=m ①根據費馬定理(m^φ(n)) mod n≡1，又1^k≡1，所以(m^k*φ(n)) mod n≡1，兩邊同乘以m得m*((m^k*φ(n)) mod n)≡1*m，化簡(m^(k*φ(n)+1)) mod n≡m ②由①、②得ed=(k*φ(n)+1)，解得d=(k*φ(n)+1)/e。費馬定理：若p是素數，a與p互素，則a^(p-1）≡1 （mod p）過程如下：A：有一個公鑰n、e。例如：3127、3。B：有一個資訊m。例如：89。C：偷聽者A：第一步：隨機找兩個質數p1、p2，一個奇數e。例如：53、59、3。第二步：計算n=p1*p2得到n，計算尤拉函式φ(n)=(p1-1)*(p2-1)得到φ(n)，計算鑰匙d=(k*φ(n)+1)/e得到d。例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。第三步：傳送n、e給大家知道 //n、e就是公鑰也做鎖，d就是n、e的鑰匙。C：獲得n、eB：第一步：獲得n、e第二步：加密資訊m，(m^e) mod n=c，獲得加密資訊c。例如：(89^3) mod 3127=1394。第三步：傳送c給AC：第一步：截獲加密資訊c第二步：破解資訊c，此時C只有n、e、c，只有把n分解質因數才能破解，而此分解很困難特別是當n很大的時候。A：第一步：收到加密資訊c第二步：解密資訊c，(c^d) mod n=m，獲得資訊m。例如：(1394^2011) mod 3127=89。完成