密碼學(xué)可以追溯到兩千多年前的凱撒大帝，他發(fā)明了一種加密方式把明文的每個(gè)字符向后移動(dòng)3位。為了方便理解，假設(shè)凱撒大帝說英語，用字母a-z寫信，那么如果凱撒大帝想寫一封內(nèi)容為helloworld的信，他加密后的內(nèi)容應(yīng)該是khoorzruog。
為了方便運(yùn)算，把a(bǔ)-z映射為數(shù)字0-25那么凱撒密碼可以表示為f(p)=(p+3)mod 26。符號(hào)mod表示模運(yùn)算，意思是除26取余數(shù)。比如信中的h對應(yīng)數(shù)字7，f(8)=(7+3)mod 26=10對應(yīng)字符k。有加密就有解密，解密就是把加密的過程反過來p=(f(p)-3)mod 26。
可以用更加通用的公式表示凱撒密碼f(p)=(p+k)mod 26其中k叫做安全密鑰，持有相同密鑰的雙方可以正常加解密通信。
隨著密碼學(xué)的出現(xiàn)，同時(shí)出現(xiàn)了另兩項(xiàng)技術(shù)密碼分析和密碼破譯，光與暗總是相生相伴。其中一種破譯方式是對比字符出現(xiàn)的概率，通過一些語料可以統(tǒng)計(jì)出字符的出現(xiàn)概率這個(gè)是已知的。然后統(tǒng)計(jì)出密文出現(xiàn)頻率最高的字符，然后假設(shè)這兩個(gè)字符相等，解出k然后進(jìn)行解密，看看解出來的文字是否有意義，如果有意義認(rèn)為破解完成，如果沒有意義換一個(gè)字符繼續(xù)試。
凱撒密碼很容易被破解，直接爆破都行，反正就26個(gè)字母。那么就需要對凱撒密碼進(jìn)行加固，一種方式是調(diào)整加密公式為f(p)=(ap+b)mod 26，叫做仿射密碼（affine ciphers），加密過程依然簡單，但是解密過程沒有那么直觀。
為了解密這里引入同余式的概念，假設(shè)a mod m=b mod m那么就記為
同余式滿足一些定理。
假設(shè)有2個(gè)同余式
那么
這個(gè)和四則運(yùn)算有點(diǎn)像，同樣的也滿足交換律、結(jié)合律和分配律。四則運(yùn)算還有兩個(gè)逆元：加法逆元和乘法逆元（倒數(shù)），模運(yùn)算里面也有，而且這個(gè)乘法逆元是上述解密時(shí)要用的。
a模m的乘法逆元和a滿足等式
假設(shè)密文是d為了解出p相當(dāng)于解方程
根據(jù)前面提到的定理我們可以知道
解密的重任落到了如何求解a模m的乘法逆元上。這時(shí)候需要最大公約數(shù)上場，在我的印象中求解最大公約數(shù)的方法叫輾轉(zhuǎn)相除法，就是兩個(gè)數(shù)交替取余數(shù)。比如10,24的最大公約數(shù)是
所以最大公約數(shù)gcd(10,24)=2。這種算法還有一個(gè)名字叫歐幾里得算法，2000多年前就有記載了。
和最大公約數(shù)有關(guān)的還有個(gè)貝祖定理：如果a b是正整數(shù)，那么存在s t使得gcd(a,b)=sa+tb成立，(s,t)叫做貝祖系數(shù)。
回到乘法逆元，我們先假設(shè)gcd(a,m)=1那么根據(jù)貝祖定理存在(s,t)使得等式sa+tm=1成立，tm肯定整除m那么
也就是說貝祖系數(shù)中的s就是我們需要的a模m的乘法逆元，問題轉(zhuǎn)到如何求貝祖系數(shù)了。
貝祖系數(shù)的一種解法是把輾轉(zhuǎn)相除法倒過來再算一遍（還有很多別的算法）。以gcd(10,24)為例，輾轉(zhuǎn)相除法的3個(gè)等式也可以寫成
最后一個(gè)等式丟棄不用，從倒數(shù)第二個(gè)開始，把上一個(gè)等式帶入到下一個(gè)等式中，得到
2=10-4*2=10-(24-10*2)*2=5*10-2*24
那么貝祖系數(shù)就是(5,-2)也就是說gcd(10,24)=5*10+(-2)*24
到此解密需要的要素都集齊了。實(shí)際來用一下假設(shè)加密算法是f(p)=(7p+3)mod 26,gcd(7,26)=1乘法逆元一定存在，假設(shè)收到的密文是8需要解密出原文是多少。
首先算出貝祖系數(shù)，先來一遍輾轉(zhuǎn)相除法
丟棄最后一個(gè)等式不用，開始按順序倒著代入得到
得出(7,26)的貝祖系數(shù)是(-11,3)也就是7模26的乘法逆元是-11?，F(xiàn)在收到的密文是8代入解密公式
因?yàn)?＜＝p＜26所以p=23。
當(dāng)然針對這個(gè)例子還有一個(gè)更簡單的解法，p的取值范圍就[0,26)一共不過26個(gè)值，按照加密公式算出所有密文，保存到表里，要用的時(shí)候select一下就好了，哈希加密的破解用了類似方式，叫彩虹表（rainbow table）來著。
前面的加密算法都是對單個(gè)字符進(jìn)行加密，為了更強(qiáng)的安全性，開發(fā)出分組密碼（block ciphers）這種方式不再以單個(gè)字符為單位進(jìn)行加密，而是以一組字符為單位進(jìn)行加密。比如4個(gè)字符組成一組那么helloworld就可以分成3組，分別是he llow orld然后每個(gè)字符用2個(gè)數(shù)字表示，比如a=00,b=01,...,z=25分組的字符可以表示為0704 11111422 14171103在然后對這3組數(shù)字進(jìn)行加密，這時(shí)候再統(tǒng)計(jì)密文頻率，只能統(tǒng)計(jì)個(gè)寂寞。
凱撒密碼和仿射密碼都是私鑰密碼系統(tǒng)。這種密碼系統(tǒng)只要知道了私鑰，那么加密解密的過程都知道了。與之相對的還有公鑰密碼系統(tǒng)，比如RSA密碼。
RSA密碼在我接觸的項(xiàng)目中用的比較多，數(shù)據(jù)比較敏感的接口可能就會(huì)用上，比如支付啥的。RSA秘鑰有2個(gè)，公鑰和私鑰。公鑰公開，交給對方用來加密數(shù)據(jù)，私鑰自己保存用來解密。
RSA的工作原理是這樣的，生成5個(gè)數(shù)p q n e d其中p q是兩個(gè)很大的質(zhì)數(shù)。這5個(gè)數(shù)滿足兩個(gè)等式
假設(shè)m是明文，c是密文
RSA加密算法
RSA解密算法
為了證明RSA加解密算法是正確的需要用到費(fèi)馬小定理。
費(fèi)馬小定理的描述是對于質(zhì)數(shù)p任何不整除p的整數(shù)m滿足等式
然后開始操作
因?yàn)閜 q互質(zhì)
m的取值范圍是[0,n)所以
也就是解密算法。對于RSA密碼系統(tǒng)來說n e c這3個(gè)信息是暴露的，但是解密需要的d要通過p q來計(jì)算，對于破解者來說先通過n分解出p q這是非常龐大的計(jì)算量，運(yùn)行時(shí)間至少是按年來算的，所以在超級(jí)牛逼的計(jì)算機(jī)出來前RSA算法是安全的，另外定期更換密鑰是好習(xí)慣。第一次看到這里的時(shí)候震驚了，萬萬沒想到本來一個(gè)無解的東西居然也能被利用起來。
為了求證下，我用python庫cryptography讀取了本地ssh-keygen生成的公鑰和私鑰，的確是這么回事。
輸出的結(jié)果里除了e其他幾個(gè)數(shù)字都巨長。
這幾個(gè)數(shù)字都很大，直接用二進(jìn)制表示肯定會(huì)溢出，剛好余數(shù)可以用來表示很大的數(shù)，這塊會(huì)用到中國余數(shù)定理。
中國余數(shù)定理在《孫子算經(jīng)》里有描述
今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？
答曰：二十三。
術(shù)曰：三三數(shù)之剩二，置一百四十；五五數(shù)之剩三，置六十三；七七數(shù)之剩二，置三十，并之，得二百三十三。以二百一十減之，即得。凡三三數(shù)之剩一，則置七十；五五數(shù)之剩一，則置二十一；七七數(shù)之剩一，則置十五。一百六以上，以一百五減之，即得。
問題翻譯過來就是求解x滿足同余式
答案翻譯過來就是140+63+30-210=23。它求得是最少的數(shù)量。后半句是解題思路：就是說余數(shù)是x,y,z時(shí)，計(jì)算70x+21y+15z結(jié)果超過106就-105直到小于106。
反過來理解23可以用(2,3,2)來表示，而且運(yùn)算也可以通過余數(shù)來計(jì)算，比如7可以表示為(1,2,0)那么23+7=(2+1,3+2,2+0)=(0,0,2)。根據(jù)這個(gè)思路可以挑幾個(gè)比較大的兩兩互質(zhì)的數(shù)，比如
這3個(gè)數(shù)就可以表示2的100次方以內(nèi)的數(shù)了，而且還可以運(yùn)算，數(shù)學(xué)真是門神奇的學(xué)科。
上面的內(nèi)容參考《離散數(shù)學(xué)》第4章，書上有更多更詳細(xì)的內(nèi)容，感興趣的小伙伴可以一看，還是有很多有趣的東西的。
題圖：Photo by Bella White from Pexels
