描述RSA的實作步驟介紹文章非常多，但說明并證明其原理，并進而討論為什么這樣設計的文章不多，本人才疏學淺，不敢說理解了R.S.A.三位泰斗的設計初衷，簡單就自己的理解寫一寫，博大家一笑，
以下原創內容歡迎網友轉載，但請注明出處： https://www.cnblogs.com/helesheng
一、用到的數論基礎定理
R.S.A.三位一定是數學大神歐拉的粉絲，因為所有用到的基本原理和定理都是以歐拉命名的，
1、歐拉函式
小于m的書中，所有與m互質的數的個數定義為“歐拉函式”，寫為：Φ(m)，若m的質因數分解為： 
（其中Pi為素數，ei為正整數），Φ(m) 的計算公式為：
2、歐拉定理
若gcd(a,m)=1（a和m互質），則有：
啟示：
1）歐拉定理是“環”到“域”的重要過渡，只要把左邊的乘方運算拆為兩個乘方運算的乘積，拆成的兩個部分就可以理解為“域”中的“元”及其乘法“逆元”，這樣環上的模逆元就存在了，“環”就可以變成“域”了，但需要注意的是歐拉定理存在的條件是gcd(a,m)=1這個條件，為滿足這個條件，密碼學（cryptology）如果作業在有限域上，經常會進行選擇m為素數，或者非常接近素數的情況；而a則之需要是小于m的任意數，作為明文或密文，但嚴格說，RSA不是作業在伽羅瓦域上的，因為RSA的模數n是兩個素數p、q的乘積，n很接近一個素數，在證明RSA時，需要專門證明gcd(a,n)不為1的情況，
2）費馬小定理是歐拉定理的“特例中的特例”，其描述為：當p是一個素數時
， 或 
，證明：若p為素數gcd(a,p)=1；而歐拉函式Φ(m)=p-1，代入歐拉定理，即可得到費馬小定理，
二、RSA程序
Step 1.選擇兩個大素數p和q，當n為7680位（960位元組）的數時，p和q約為3072位，在這樣長度的奇數中尋找一個素數的可能性約為：
即約1065個奇數中有一個素數，
計算n=p*q，
Step 2.計算n的歐拉函式Φ(n)，
因為n的兩個質因數已知為p和q，代入公式（1）有Φ(n)=(p-1)(q-1)，
Step 3.選擇一個與Φ(n)互質的數e，
a)要求e與Φ(n)互質的原因是要保證e的模n乘法逆的存在，而這個乘法逆就是私鑰d，
b)e將作為公鑰，e取值不大，一般有3、17、65537幾種選擇，因為公鑰e遠小于私鑰d，持有公鑰的一方，在不論是進行加密（用RSA做密鑰交換）還是進行解密（用RSA作數字簽名）的速度都遠遠快于持有私鑰d的一方，
e之所以選擇這幾個數，除了是素數之外，還因為這幾個數3（b101）、17（b1_0001）、65537（b1_0000_0001）的二進制表達中1的個數特別少，這樣在計算xe時將會特別簡便，
c)在整個RSA運算中，計算d是唯一一次使用Φ(n)作為模的地方，其他地方都是使用n作為模，
Step 4.使用公鑰e和私鑰d進行加解密
a）上面的公式中并沒有指定x和y誰是明文誰是密文，也就是說兩者都可以作為明文和密文，
b）RSA找到了一種“一一對應”的映射關系f：因為e較小，且公開，所以x映射到y很容易；y映射到x很困難，d較大，且不知道p、q時很難得到，這樣的映射f被稱為單向映射，
三、RSA的證明
證明RSA程序，等價于證明：
其中
n=p×q，n只有p、q兩個質因數，
根據n和x的情況分兩種情況討論：
情況一：當x不含有p和q兩個質因數時，n和x互質，gcd(n,x)=1，根據歐拉定理有：
根據d的定義，d和e對模Φ(n)互逆，有：
將上式寫成另一種形式：
將其代入欲證明的(2)，有：
情況二：當n和x不互質時，由于n=p×q，x可以寫成：x=r×p或s×q（但不能寫成x=r×p×q，因為這會使得x > n），不失一般性，假設x=r×p，由于
，根據歐拉定理和歐拉函式有：
根據d的定義，同樣有(5)式，而（6）式則變為：
其中使用了歐拉函式計算公式
將（7）代入上式有：
至此，證明了不論在那種情況下都有 ，證畢！
四、RSA的設計思路
不自量力的揣測一下R.S.A.三位的設計思路，是利用歐拉定理構造了以n作為模的環上互逆的一對數x和y作為明文和密文，x和y各自是對方的e次方和d次方，如果知道n的質因數分解（p×q）的，可以通過歐拉函式方便的計算出e和d，否則只能靠對方告知其中之一，從而形成了單向映射，構成了所謂“非對稱加密”，
另外，在e和d的復雜度的分割上，并不是相等的，設計者讓知道質因數分解的一方的密鑰d遠遠復雜于e，原因有二：其一，知道質因數分解的一方可以通過中國余數定理CRT加速計算；其二，不知道質因數分解的諸多“非對稱”通信者，可以使用較低的算力執行加、解密，
較簡單密鑰e稱為公鑰，較復雜密鑰d稱為私鑰，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300338.html
標籤：其他
上一篇：[第二十篇]——Docker 安裝 Tomcat之Spring Cloud直播商城 b2b2c電子商務技術總結
下一篇：FastAPI 學習之路（二）