觸碰標題下面一行的「邵勇老師」查看所有文章；觸碰「數學教學研究」, 關注本微信公眾號(sx100sy)。本公眾號內容均由邵勇本人獨創，歡迎轉發，但未經許可不能轉載。特別聲明，本人未曾授權任何網站（包括微博）和公眾號轉載邵勇「數學教學研究」公眾號的內容。每周推送兩到三篇內容上有份量的數學文章，但在行文上力爭做到深入淺出。幾分鐘便可讀完，輕鬆學數學。
祝您2020年新春快樂！平安！健康！
前兩期的文章在最後都提及RSA公鑰密碼。它的原理已經應用於我們已經使用多年的網絡傳輸當中。而我們不知不覺。這其中的數學原理就是歐拉定理。我很多年前曾經講過一些對稱密碼的加密和解密，但對稱密碼不管設計得多麼精緻巧妙，仍然會有被破解的危險。正像從一個函數可以求出它的反函數。比如，加密函數為y=x+1，由這個函數可以把1,2,3,4,...,n變換成2,3,4,5,...,n+1；那麼，很容易導出它的反函數：y=x－1，這個反函數可以把2,3,4,5,...,n+1再變回到1,2,3,4,...,n。可以說，知道兩個函數中的任意一個，就可以導出另一個。所以，一旦加密規則被截獲，解密規則隨之無秘密可言，保密工作必將以失敗告終。於是，人們便想方設法去發明不對稱的加密方法。RSA公鑰密碼就是一種不對稱的加密機制，可以確保不被破譯。打個比方，我是信息接收方，那麼，要由我來主宰信息的傳輸過程：我準備一個箱子和一把打開了的掛鎖；把它們寄給信息發送方；信息發送方把要發送的絕密信息放入箱子中，並用這把打開著的掛鎖把箱子鎖上；然後把上了鎖的箱子寄回給接收方；接收方有開鎖的鑰匙，打開箱子取出絕密信息，於是，便成功完成信息的安全傳輸任務。RSA公鑰密碼機制本質上就是運用了類似這個掛鎖傳遞絕密信息的機制。但是，原理說起來簡單，真正實現可就沒那麼容易了。於是數學出場了。數論中的歐拉定理在RSA中扮演著重要角色。
好的，下面我們就具體來講解。
有A和B兩方，A方是發送方，它要把一段不想被其他人知曉的信息（任何信息都可以轉換成數字，以數字的形式發送）加密後發送給B方。B方是接收方，它有解密的鑰匙可以把A方發送的加密信息還原成原來信息。那麼RSA公鑰密碼機制是怎樣做到的呢？這就用到了數學上的歐拉定理及數論中有關同餘的一些性質。
歐拉定理：有正整數m與n，m與n互素。設φ(m)為小於m且與m互素的正整數的個數。那麼，
能被m整除。其中的φ(m)叫做歐拉函數。歐拉函數很重要，我們必須會求它的值。這個函數的表達式如下：
其中的p1，p2，…，pk都為素數，且p1<p2<…<pk。它們來自m的標準分解式：
上式中的α1，α2，…，αk是確定的正整數。這個標準分解式叫做一個正整數的素因數分解。這個標準分解式是唯一的。
若m正好是兩個素數p和q的乘積，即m=p×q，那麼，根據上面公式，可以得出歐拉函數φ(m)的值等於 (p－1)×(q－1)。
下面就來詳細講解RSA的工作流程。
（1）接收方（B方）首先選取兩個比較大甚至很大的素數p和q。把p和q相乘，得到m=p×q。所以，m也是一個很大的正整數。注意，這個p和q是B方也就是接收方選定的，不告訴任何人，甚至也不告訴發送方（A方）。這個p和q將是RSA機制的核心，沒有這麼兩個大素數，也就沒有RSA。只有掌握了p和q這兩個大素數的接收方，才能最終解密。
（2）接收方（B方）知道p和q，當然可以計算出(p－1)×(q－1)（這個乘積在以後的解密過程中發揮著重要作用）。然後B方再選取一個與(p－1)×(q－1)互素的正整數k。
（3）接收方(B方)把p和q的乘積m（而不是p和q）及k這一對正整數（m，k）告訴發送方(A方)。m和k這兩個數就是所謂的公鑰密碼。現在，接收方(B方)就處於等待狀態，等待著發送方(A方)把加了密的信息傳送給自己。A方必須利用m和k來給要發送的信息加密。我們說過RSA是由接收方主宰的，所以，發送方(A方)一定要使用接收方(B方)發來的公鑰密碼（m，k），否則聯繫如何建立起來？！
（4）發送方(A方)收到接收方(B方)發來的公鑰密碼m和k。設A方要發送的機密信息是正整數n（任何信息都可以轉換成某個正整數）。注意，這個n要小於B方發來的正整數m，這一般是沒有什麼問題的，因為B方一定選取了兩個很大的素數p和q從而m=p×q也一定很大。並且n與m互素也幾乎是肯定的，這是因為我們把一個很大的數進行素因數分解這件事本身就很難，何況現在這個大數m只是兩個大素數的乘積，A方所要發送的信息n正好就是p或q中的一個這種可能性基本不存在，所以，n與m互素可以得到保證。好的，我們繼續。這時，A方已經準備好了要發送的信息n ，也知道了B方發來的正整數k。於是，他就計算n的k次方，並用所得結果除以m（k和m都使用上了），於是將獲得一個餘數。我們記這個餘數為r。用同餘式表示就是：
（5）發送方(A方)把這個r當成密碼發送給接收方(B方)。注意，這個密碼r就算被第三方截獲也沒有用，因為第三方是很難從這個r反推出原信息n的，這是因為數m可能是一個很大很大的數，與它互素的數也很多很多，想要 一 一 驗證這些數的k次方除以m後的餘數是不是r，幾乎是不可能的。（發送方當然不會傻到直接把n的k次方當成密碼發送，因為第三方獲取後把結果簡單地開k次方就得到原文n了。這就成了對稱密碼了：發送規則與接收規則是正反函數的關係。而我們的RSA機制就是要極力避免類似的對稱關係的出現！）
（6）這時又該輪到接收方(B方)進行數據處理了。B方接收到A方發來的密碼r後，把r進行a次方，使得r的a次方除以m後的餘數正好是n：
但是，如何確定這個正整數a呢？這就要用到歐拉定理。這是解密的關鍵。我們前面已經說過，發送方(A方)要發送的機密信息n是與接收方(B方)給他的公鑰密碼m(=p×q)互素的，於是由歐拉定理，我們就有：
根據同餘的乘法性質，我們得到：
其中b為任意正整數。把上式兩邊同時乘以n，就將得到：
（7）我們比較上面得到的(1)式與(2)式：
發現，我們若可以求出a和b，使得上面兩式左側的指數相等，即
那麼，便可以通過
求出n。也就說，接收方(B方)就成功解密了發送方(A方)發送的機密信息n。
（8）上面的成功得助於(4式)的成功求解。我們把(4)式變形為：
這不就是一個一次不定方程麼！其中的k和(p－1)×(q－1)是已知的且兩者是互素的，完全符合一次不定方程中的係數的要求。從而這個一次不定方程有整數解a和b（我在前不久的某期講過求解方法）。解a和b有無窮多組，我們選取a是最小正整數的那個組解。(4)式或(5)式就像是一座橋，發送方(A方)要發送的存在風險的信息，過了這座橋到達接收方(B方)後就安全了！因為只有接收方(B方)知道p和q，也就是只有B方可以算出(p－1)×(q－1)，也就是只有B方可以解不定方程(5)，最終也就是只有B方可以把發送方發送來的機密信息n解密。
上面就講解了RSA的傳輸機制，有些複雜，但確實做到了保密和安全。原本數學中純之又純的數論知識，卻神奇般地在密碼學及網絡傳輸中發揮了重要作用。
參考書：