公鑰密碼學中的素數以及對稱加密

    密碼學，一向被人們認為門檻很高，特别高端...這也是實際，但是這決不意味着普通人無法了解它的精髓，對于喜歡畫圓的人來講，即便是了解了密碼技術背後的哪怕一點理論，也是激動人心的。

最近，一次聯調SSLVPN協定的機會，讓我終于有時間可以弄點關于密碼學的東西，隻是簡單的沾個邊兒，是以本文既不是技術文檔亦非學術論文，你不可能通過閱讀本文學到Howto，這隻是一篇随筆或者說科普，而已。

        聲明之後是我的一些悲歎！

        有太多人精通加密算法，卻不了解群環域的實質，反對者聲稱隻要會用隻要懂操作步驟就可以了，然而這個理由對于理性而言總是不那麼perfect，是啊，太 多的人知道RSA密鑰産生的步驟，知道p，q和n，還知道p，q都是素數，背得滾瓜爛熟，但是卻對為什麼這麼産生一無所知，然而很多人已經沾到了歐拉函數 的邊兒，......

        ......

任何機制都要有個作用範圍，機制必須在該作用範圍内運轉，其效果也必須展現在該作用範圍。比如法律之于國民，TCP狀态機之于TCP連接配接...

        現代密碼學建立在代價收益不均衡的基礎上。什麼是好的算法？當你破解該算法使用的密鑰的代價遠遠超過破解之後所得到的收益時，該算法就是好的！現代密碼學 的另一個基礎是現代計算機技術，可以說計算機是現代密碼學的載體！在此我們可以對比一下另一種密碼學，那就是心理學，同樣，攻心術也是建立在代價收益不均 衡之基礎上，然而和計算機密碼學不同，心理學的另一個基礎是人腦！如果說現代非對稱密碼學建立在數學難題之上，那麼心理學則是建立在“人心隔肚皮”之上。

        計算機上的現代密碼學，顯然要受到計算機的限制，什麼限制呢？那就是計算機無法處理抽象的集合，它隻能處理具體的數字！比如計算機不能處理整個實數集合， 但它卻能處理你能給出的不管多大的數字！是以在計算機裡面提到數字，你必須指定一個有限的範圍，即便這個範圍囊括的數字範圍巨大，該範圍一定是具體的！

        據科學估計，宇宙中的原子數量在2的千級次幂範圍内，而這個數在計算機内并不算什麼大不了的！計算機可以快速處理這麼大的數字，這種數字被叫做大數 (BIG NUMBER)，事實上，在計量上，這類數字确實不小，但是在數學上，這類數字卻也不大，計算機就是處理這些計量上的大數的。由于現代數學建立在抽象的基 礎上，然而計算機又無法直接處理抽象的概念，比如無窮遠，比如無窮大等，是以就需要一定的規則，将運算框在一個有限的框框内，在這個有限的框框内，一切數 學上的運算法則依然适用。

 我們國小的時候學習過四則混合運算，後來又将運算的作用範圍擴大到了整個實數集 合，再後來又引入了虛數...實際上，這些都不重要，關鍵點在于運算法則本身。給定一個集合，如果集合内的任意元素在進行四則混合運算(要滿足交換率，結 合率...)後的結果仍然在該集合内，如果該集合又是一個有限的集合，那麼該集合就可以作為計算機上密碼學使用的那個有限的框框。

        如何來生成一個有限的集合，方法很多，最顯而易見的就是“取模”，即對一個數字做除法然後取餘數，比如如果我們将所有的正整數集合内的任意數字對數字5取 模，那麼結果無非也就0，1，2，3，4這5個數，不管怎麼樣結果也跑不出這5個數，就算你用1000和1234相加，結果2234除以5所得的餘數4， 也在這個範圍内，這就是一個有限的集合，即我們說的那個有限的框框，計算機在這個集合裡面做運算剛剛好，對于上一節所舉的這個大數而言，任意正整數對它取 模便可以形成一個很大的集合，而計算機密碼學的很多運算就是在這類集合内運轉的。

        到此為止，我們已經知道如何生成一個有限的集合來友善計算機進行任意的運算，但是光這還不夠，因為我們僅僅定義了一些運算法則以及一個有限的集合，機關元 我們還沒有，對于機關元而言，它可以作為集合内任意元素之間的媒介，事實上它是一個衡量的尺度，比如對于整數加法，機關元就是0，任何一個數字和0相加結 果都是它本身，通過機關元0還可以找到任意一個整數的相反數，與其相加的結果就是機關元，對于乘法而言也類似，乘法的機關元是1，而對應加法相反數的概念 則是倒數，不管是加法的相反數，還是乘法的倒數，都可以被稱作逆元。那麼對于取模的結果生成的集合内，有沒有機關元呢？在回答這個問題之前，必須要聲明的 一點就是：對于集合内的任意一個元素，都必須擁有逆元，這樣整個集合才可能是閉合的，否則一旦讓一個沒有逆元的元素參與運算，結果将是不可預知的(跑飛 了...)。了解了這一點之後，我們就可以瞬間了解“為什麼在密碼學中素數這麼重要”，“為什麼循環群一定要有生成元”等問題。

在密碼學中，特别是公鑰密鑰學中，我們經常要面對生成一個大素數的問題，可是為什麼一定要是素數呢？難道就是因為它數量比較少嗎？No！難道因為它的分布不确定嗎？No！那到底是為什麼？

        我們再來看上面那個模5的運算，集合為{0,1,2,3,4}，對于乘法，我們看看每一個元素的逆元分别是什麼，顯然0的逆元不存在，而 1*1%5=1，2*3%5=1，3*2%5=1，4*4%5=1，這樣除了0之外，其它的元素都有逆元，而我們注意到，模數5是一個素數...那麼我們 把特殊的元素0抛棄，留下{1,2,3,4}作為我們需要的有限集合，是不是可以呢？當然可以！

        然而，我上面的論述有點以偏概全了，畢竟這隻是一個特例。那麼接下來就要證明一下這是一個普遍的結論：如果模數p為一個素數，那麼對整個正整數集合取模的 結果去掉0就能生成一個乘法運算閉合的集合，該集合是個素域，集合中的元素數量是p-1(因為去掉了0。Oh yeah，這不就是樸素的歐拉函數嗎？)。證明方法很簡單。

        假設一個集合N={1,2,3,4....p-1}，p為素數，對于其中任意一個元素a，用a去乘整個集合，得到一個新的集合N'= {1*a%p,2*a%p,3*a%p,4*a%p...(p-1)*a%p}，我們隻需要證明這個新的集合中的某一個元素為1即可。對于集合N而言，有 一個條件我們還沒有用過，那就是p為素數！這是關鍵之關鍵！p為素數意味着集合N中所有的元素和p都是互素的，即它們沒有公約數，同時這也意味着，N'中 的元素和p也是互素的(這很容易用反證法證明！)，再看，N集合和N'集合的元素數量是一緻的，而N集合包含了到p為止的正整數全集，我沒隻需要證明N' 集合中的元素兩兩不相等，就可以說明N'集合也是到p為止的正整數全集，進而證明N==N'！還是反證法，假設N'即集合中有m*a%p==n*a%p， 其中m>n，設m=r*p+x1，n=s*p+x2，則x1%p==x2%p，x1和x2均是小于p的數，可以證明m和n模p同餘，由于m和n都小 于p，是以m==n，和假設不符。是以N==N'。

        這能說明什麼呢？這說明集合N'中包含數字1，也就是說對于任何一個N中的元素a，在集合N中均擁有一個元素和其乘積模p等于1，這就說明集合N中的每一 個元素的逆元都是存在的。這就是模數為素數的重要性質！那麼，相反地，如果模數不為素數又如何呢？舉一個反例即可，如果模數p=a*b，即它的因數是 a，b，并且a和b均小于p，那麼集合N={1,2,3,4...p-1}中的a和b将不存在逆元，因為它們除模數p的餘數始終為0，而不是機關元1！

        顯然，模數為素數的重要性質就是可以将集合框在一個範圍内，在此範圍内，四則混合運算照常如舊，乘法機關元1存在！這是模運算的恩惠，也許是上帝的恩惠， 數學如此之美！想想看，在實數範圍内的四則混合運算與機關元，在素數模運算中，竟然如此一緻，這就是抽象代數，實際上，抽象代數不是被發明的，而是被發現 的！

 在了解了基本理論後，我們來看一下逆元為何如此重要，簡單的說，求逆元在算法上是一個規範性的操作， 比如使用輾轉相除法等，然而對于模數p未知的情況下，卻是一個在計算上不可能的問題。至于為什麼不可能，請不要按照學子們的理論來考究，而要用收益/代價 均衡的理論來考慮。比如你破解一個算法花了30年，有意義嗎？在學術環境下是有意義的，那好吧，如果你能把算法強度提高到破解它需要付出300年的時間， 你就可以拿到大獎了。

        求逆元是一個甚是簡便的做法，可以說是一個協定，試想，加密解密雙方在沒有任何互動的前提下，怎麼知道如何操作。那麼運算集中的操作就是協定了，比如就是 求逆元。那麼安全性在哪展現？給你兩堆沙子，你将它們混合在了一起，然後你能再将它們區分出來嗎？這就是大數分解問題的隐喻，這就是有限集合模運算算法安 全性的保障！

        素數模數界定了一個有限的集合，提供了可計算性，大數分解提供了計算的單向性。

        現在我們步入RSA算法，這是一種正常的非對稱密鑰算法。首先選擇兩個比較大的素數p和q，然後計算n=p*q，接下來需要界定一個集合，該集合内全部都 是和n互素的數，顯然n不是素數，這就意味着必須在集合N={1,2,3,4...n-1}中抛棄和n不互素的數字。那麼剩下的集合N'中還剩下多少元素 呢？在進一步讨論之前，我先講一下前提。

        上一節我論述了，如果模數p是一個素數，那麼集合{1,2,3,...p-1}構成一個有限集合N，可以用作非對稱密鑰學計算，那麼推廣一下，如果p不是 素數，那麼這個集合該如何界定呢？結論是，在集合N中抛棄所有和數字p不互素的數。我們假設p=m*n，其中m，n均為素數，那麼集合 {1,2,3,4...m*n-1}中有多少和p互素的數呢？很顯然，這些不和p互素的數字分為兩類，一類是m的倍數，另一類是n的倍數，m的倍數在集合 中是{m,2m,3m...(n-1)m}，而n的倍數則是{n,2n,3n...(m-1)n}，是以集合{1,2,3,4...p-1}中和p互素的 集合N中數字的數量一共有(p-1)-(n-1)-(m-1)=m*n-m-n+1=(m-1)*(n-1)。

        上述集合N中元素都有逆元嗎？答案是肯定的。證明方法和素域p中的元素都有逆元的證明是一樣的。首先将待求逆元的元素乘以集合N中的每一個元素并對m*n 取模，得到新集合N'，證明這個集N'合和集合N是相等的，是以裡面必然有元素1。證明這個隻需要兩點，首先證明N‘中的元素都是和m*n互素的(實際上 代表了全部的和m*n互素的數字組成的集合)，其次證明它們兩兩不相等，這就可以說明兩個集合是一樣的。

        上面的這個結論是極其重要的，畢竟RSA算法的最開始就是要選擇兩個大素數p，q，然後計算n=p*q，并且計算m=(p-1)*(q-1)，看看m是什 麼，m就是集合{1,2,3...n-1}中和n互素的集合N中數字的數量！RSA的計算将全部在集合N中進行！實際上，前幾步的選取大素數p，q以及計 算(p-1)*(q-1)隻是界定了一個計算的集合而已。

        RSA算法在界定了集合N之後，就會在N中選取一個數字e，顯然e的逆元肯定是存在的！那麼計算e的逆元，結果就是私鑰d！公鑰就是e以及n。

        n是明确的，但是你很難得到p和q，這就是算法的根本。技術實作上的關鍵點是，這種算法之是以可行，完全是這些算法過程是建立在一個有限的集合的基礎上， 在該集合中存在機關元，滿足交換率，計算閉合性。到這裡為止，我并沒有提到群，環，域的概念，也沒有給出任何的定義，定理。但是殊途同歸，一個簡單的規則 抽象的設想便可以推出基本上所有的定理，定義，隻是我沒有說哪些是定義，哪些是定理罷了。想了解這些，随便找一本數論，抽象代數的書你就可以學到。讀了這 些書的結果如何呢？結果就是你可以拿起筆寫下試題的答案，然而即便這樣，如果不自己從頭到尾的思考，你可能仍然不知是以然，隻知道某某學科有一個XX定 理，它的證法是這樣的...

       這個簡單的設想就是在一個集合中，其所有元素乘法逆元的存在性。要存在乘法逆元，素數便登上了舞台，因為我們發現，如果一個集合中的元素和模數均是互素 的，那麼乘法逆元就一定存在，最簡單的這種集合就是所謂的素域，當然對于模數是任意值的集合而言，歐拉函數給出了集合中元素的個數。請注意，歐拉函數“隻 是一種找到元素個數的方法”，而和集合的本質沒有太多的關系。

        依然本着乘法逆元，我們來看一下它是怎麼導出在有限集合中的離散對數問題的。

 我 們依然看最初的那個集合N={1,2,3,4...p-1}，其中p為素數。現在我們知道這個集合中均存在乘法逆元，計算也都是閉合的。我們随便拿出該集 合的一個元素a，用它來乘以集合N中的每一個元素并模p，得到新的集合N'={1*a%p,2*a%p,3*a%p,4*a%p...(p- 1)*a%p}，我們知道其中肯定有一個元素為1，對應的該元素去掉*a後就是a的逆元。好的，一切正常，現在沒有完，繼續用a乘以集合N'中的元素并模 p得到N''，我們知道N‘’和N是相等的，再進一步，用a去乘N‘’的每一個元素并模p得到N‘’‘，...N’‘’‘’我們可以得出，所有這些 N，N'，N''，N'''，N'''''...等都是相同的集合，是以我們就知道，a的不管多少次方模p的結果都在集合N内。

        這個結論很重要，這顯然又構成了一個閉合的運算集合，在該集合内，任意一個元素的任意次方模p的結果依然屬于該集合，給定一個集合内的元素a以及另一個元 素b，你能算出a的多少次方模p等于b嗎？這就是離散對數問題。顯然，隻有在模運算的情況下才繪出現如此多的有趣特性，顯然，鐘表上繞圈還是很好玩的。也 許你想知道離散對數問題和乘法逆元有什麼關系，關系并不是那麼明确，然而，一個集合中每一個元素逆元的存在則是必須的要求。如此好玩的在鐘表上繞圈的規則 總結成一門學科就是數論，而密碼學則是利用了數論的諸多定理和定義的學科。

 密碼學，特别是公鑰密碼學， 并不旨在數論領域發現新的天地，它隻是利用了結論。對于密碼學而言，群環域僅僅是為了定義一個框框，将所有的計算限制在這個框框内，而具體限制的方法則是 取模，于是這個框框就成了鐘表。這是密碼學，特别是公鑰密碼學的基礎。在擴充意義上，二項式域僅僅是純粹的數域的另一種抽象，旨在定義新的運算規則，其本 質和上面論述的并無差別。

        對于公鑰密碼學的安全性保證，是在計算意義上的，而非理論意義上的。就是利用一些計算上的單向性導緻的逆向運算難題，而針對這些單向運算的分析，也是在數論範疇的。

        前面提到的數論在公鑰密碼領域很有用武之地，然而在對稱密碼學領域，起關鍵作用的不是數論之類的數學，而是操作技巧。在對稱密碼學領域，最關鍵的是三個基本原則：

1.混淆替換。切斷明文和密文之間的線性對應關系，替換在擴散的作用下會增加非線性特征。

2.作用擴散。将非線性特征擴散到整個密文，明文片斷之間的任何差異均會影響整個密文，使密文無章可循。

3.操作可逆。由于加密/解密使用同一個密鑰，操作必須是可逆的。

落 實到最終對明文的操作上，就是異或操作。異或操作是一種最為均衡的位操作，因為兩個操作數相同結果就是0，兩個操作數不同，結果就是1，這樣要想通過結果 得到明文，你就必須知道密鑰，否則你猜對的可能性就隻有50%，如果密鑰長度達到一定長度，加上上述的替換和擴散作用，密文被破解的可能性就微乎其微了。

        對稱密碼學實際上是很有趣的，不像公鑰密碼學你必須有一定的數學基礎才能玩得轉。事實上，在我們日常生活中，整天都在面對對稱密碼學。平時用的暗号，一些 肢體語言，一個眼神，這些都是對一些資訊的編碼，在指望對方能明白之前，你們之間必須有一個約定，最簡單的比如自然語言，兩個中國人之間的書信在德國人看 來就是密文，而這個德國人解密的唯一途徑就是搞到密鑰，當然這比較簡單，對應的密碼本就是漢德詞典。是以，對稱密碼中的對稱含義就是雙方掌握相同的加密/ 解密資訊。如果我們考慮具體的操作，你如何能隐掉寫在紙上的一個電話号碼呢？

        最常見的方式就是燒掉它，但是燒掉是不可逆的，如果你忘記了這個号碼，你自己也無法恢複它了...另一種選擇就是用同顔色塗掉它，但是當你拿起這張紙，然 後将它對着光，你會看到原始電話号碼的字痕，于是你又想了一個辦法，那就是亂塗，而不是朝着一個方向去塗，但是即便這樣，你也能在混亂的字痕中找到一個規 則的東西，最終将其拼成數字...那怎麼辦？此時需要用替換和擴散了，辦法很簡單。不要再亂塗，而是在那個電話号碼周圍寫入其它起到混淆視聽作用但是卻無 關緊要的電話号碼，接下來将所有的3改成8，辦法就是在3的左邊加個耳朵，同理将1改成7，諸如此類...最後再亂塗一氣...但是，你要記住一些資訊， 那就是這個電話号碼在紙上的位置，另外還有數字改寫的規則。當你拿到一張被原子筆塗得亂七八糟的紙時，對這光找到那個位置的字痕，然後再将數字改寫規則逆 作用于它，就恢複了原始電話号碼，這就是對稱加密。我真的就這麼幹過，當時我和老婆還沒有結婚，老婆第一次去我家時留下了現在丈母娘的電話給我爸，我是不 希望雙方家長取得聯系的，于是我就用上述的辦法将電話号碼改成了一個别的号碼(并沒有用padding和塗抹的方式，因為加密強度沒有必要那麼 大...)，後來我爸真的打電話了，還抱怨，怎麼給他留了一個空号...

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1547050