數學加密演算法原理

A. 加密基礎知識二 非對稱加密RSA演算法和對稱加密

上述過程中，出現了公鑰(3233,17)和私鑰(3233,2753)，這兩組數字是怎麼找出來的呢？參考 RSA演算法原理（二）
首字母縮寫說明：E是加密（Encryption）D是解密（Decryption）N是數字（Number）。

1.隨機選擇兩個不相等的質數p和q。
alice選擇了61和53。（實際應用中，這兩個質數越大，就越難破解。）

2.計算p和q的乘積n。
n = 61×53 = 3233
n的長度就是密鑰長度。3233寫成二進制是110010100001，一共有12位，所以這個密鑰就是12位。實際應用中，RSA密鑰一般是1024位，重要場合則為2048位。

3.計算n的歐拉函數φ(n)。稱作L
根據公式φ(n) = (p-1)(q-1)
alice算出φ(3233)等於60×52，即3120。

4.隨機選擇一個整數e，也就是公鑰當中用來加密的那個數字
條件是1< e < φ(n)，且e與φ(n) 互質。
alice就在1到3120之間，隨機選擇了17。（實際應用中，常常選擇65537。）

5.計算e對於φ(n)的模反元素d。也就是密鑰當中用來解密的那個數字
所謂"模反元素"就是指有一個整數d，可以使得ed被φ(n)除的余數為1。ed ≡ 1 (mod φ(n))
alice找到了2753，即17*2753 mode 3120 = 1

6.將n和e封裝成公鑰，n和d封裝成私鑰。
在alice的例子中，n=3233，e=17，d=2753，所以公鑰就是 (3233,17)，私鑰就是（3233, 2753）。

上述故事中，blob為了偷偷地傳輸移動位數6，使用了公鑰做加密，即6^17 mode 3233 = 824。alice收到824之後，進行解密，即824^2753 mod 3233 = 6。也就是說，alice成功收到了blob使用的移動位數。

再來復習一下整個流程：
p=17,q=19
n = 17 19 = 323
L = 16 18 = 144
E = 5(E需要滿足以下兩個條件：1<E<144,E和144互質)
D = 29(D要滿足兩個條件，1<D<144,D mode 144 = 1)
假設某個需要傳遞123，則加密後：123^5 mode 323 = 225
接收者收到225後，進行解密，225^ 29 mode 323 = 123

回顧上面的密鑰生成步驟，一共出現六個數字：
p
q
n
L即φ(n)
e
d
這六個數字之中，公鑰用到了兩個（n和e），其餘四個數字都是不公開的。其中最關鍵的是d，因為n和d組成了私鑰，一旦d泄漏，就等於私鑰泄漏。那麼，有無可能在已知n和e的情況下，推導出d？
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有將n因數分解，才能算出p和q。
結論：如果n可以被因數分解，d就可以算出，也就意味著私鑰被破解。
可是，大整數的因數分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。維基網路這樣寫道："對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。假如有人找到一種快速因數分解的演算法，那麼RSA的可靠性就會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA密鑰才可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。"

然而，雖然RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何。此外，RSA的缺點還有：
A)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。
B)分組長度太大，為保證安全性，n 至少也要 600bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼演算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標准化。因此， 使用RSA只能加密少量數據，大量的數據加密還要靠對稱密碼演算法 。

加密和解密是自古就有技術了。經常看到偵探電影的橋段，勇敢又機智的主角，拿著一長串毫無意義的數字苦惱，忽然靈光一閃，翻出一本厚書，將第一個數字對應頁碼數，第二個數字對應行數，第三個數字對應那一行的某個詞。數字變成了一串非常有意義的話：
Eat the beancurd with the peanut. Taste like the ham.

這種加密方法是將原來的某種信息按照某個規律打亂。某種打亂的方式就叫做密鑰(cipher code)。發出信息的人根據密鑰來給信息加密，而接收信息的人利用相同的密鑰，來給信息解密。 就好像一個帶鎖的盒子。發送信息的人將信息放到盒子里，用鑰匙鎖上。而接受信息的人則用相同的鑰匙打開。加密和解密用的是同一個密鑰，這種加密稱為對稱加密（symmetric encryption）。

如果一對一的話，那麼兩人需要交換一個密鑰。一對多的話，比如總部和多個特工的通信，依然可以使用同一套密鑰。 但這種情況下，對手偷到一個密鑰的話，就知道所有交流的信息了。 二戰中盟軍的情報戰成果，很多都來自於破獲這種對稱加密的密鑰。

為了更安全，總部需要給每個特工都設計一個不同的密鑰。如果是FBI這樣龐大的機構，恐怕很難維護這么多的密鑰。在現代社會，每個人的信用卡信息都需要加密。一一設計密鑰的話，銀行怕是要跪了。

對稱加密的薄弱之處在於給了太多人的鑰匙。如果只給特工鎖，而總部保有鑰匙，那就容易了。特工將信息用鎖鎖到盒子里，誰也打不開，除非到總部用唯一的一把鑰匙打開。只是這樣的話，特工每次出門都要帶上許多鎖，太容易被識破身份了。總部老大想了想，乾脆就把造鎖的技術公開了。特工，或者任何其它人，可以就地取材，按照圖紙造鎖，但無法根據圖紙造出鑰匙。鑰匙只有總部的那一把。

上面的關鍵是鎖和鑰匙工藝不同。知道了鎖，並不能知道鑰匙。這樣，銀行可以將「造鎖」的方法公布給所有用戶。 每個用戶可以用鎖來加密自己的信用卡信息。即使被別人竊聽到，也不用擔心：只有銀行才有鑰匙呢！這樣一種加密演算法叫做非對稱加密(asymmetric encryption)。非對稱加密的經典演算法是RSA演算法。它來自於數論與計算機計數的奇妙結合。

1976年，兩位美國計算機學家Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構思，可以在不直接傳遞密鑰的情況下，完成解密。這被稱為"Diffie-Hellman密鑰交換演算法"。這個演算法啟發了其他科學家。人們認識到，加密和解密可以使用不同的規則，只要這兩種規則之間存在某種對應關系即可，這樣就避免了直接傳遞密鑰。這種新的加密模式被稱為"非對稱加密演算法"。

1977年，三位數學家Rivest、Shamir 和 Adleman 設計了一種演算法，可以實現非對稱加密。這種演算法用他們三個人的名字命名，叫做RSA演算法。從那時直到現在，RSA演算法一直是最廣為使用的"非對稱加密演算法"。毫不誇張地說，只要有計算機網路的地方，就有RSA演算法。

1.能「撞」上的保險箱（非對稱/公鑰加密體制，Asymmetric / Public Key Encryption）

數據加密解密和門鎖很像。最開始的時候，人們只想到了那種只能用鑰匙「鎖」數據的鎖。如果在自己的電腦上自己加密數據，當然可以用最開始這種門鎖的形式啦，方便快捷，簡單易用有木有。

但是我們現在是通信時代啊，雙方都想做安全的通信怎麼辦呢？如果也用這種方法，通信就好像互相發送密碼保險箱一樣…而且雙方必須都有鑰匙才能進行加密和解密。也就是說，兩個人都拿著保險箱的鑰匙，你把數據放進去，用鑰匙鎖上發給我。我用同樣的鑰匙把保險箱打開，再把我的數據鎖進保險箱，發送給你。

這樣看起來好像沒什麼問題。但是，這裡面 最大的問題是：我們兩個怎麼弄到同一個保險箱的同一個鑰匙呢？ 好像僅有的辦法就是我們兩個一起去買個保險箱，然後一人拿一把鑰匙，以後就用這個保險箱了。可是，現代通信社會，絕大多數情況下別說一起去買保險箱了，連見個面都難，這怎麼辦啊？

於是，人們想到了「撞門」的方法。我這有個可以「撞上」的保險箱，你那裡自己也買一個這樣的保險箱。通信最開始，我把保險箱打開，就這么開著把保險箱發給你。你把數據放進去以後，把保險箱「撞」上發給我。撞上以後，除了我以外，誰都打不開保險箱了。這就是RSA了，公開的保險箱就是公鑰，但是我有私鑰，我才能打開。

2.數字簽名
這種鎖看起來好像很不錯，但是鎖在運輸的過程中有這么一個嚴重的問題：你怎麼確定你收到的開著的保險箱就是我發來的呢？對於一個聰明人，他完全可以這么干：
(a)裝作運輸工人。我現在把我開著的保險箱運給對方。運輸工人自己也弄這么一個保險箱，運輸的時候把保險箱換成他做的。
(b)對方收到保險箱後，沒法知道這個保險箱是我最初發過去的，還是運輸工人替換的。對方把數據放進去，把保險箱撞上。
(c)運輸工人往回運的時候，用自己的鑰匙打開自己的保險箱，把數據拿走。然後復印也好，偽造也好，弄出一份數據，把這份數據放進我的保險箱，撞上，然後發給我。
從我的角度，從對方的角度，都會覺得這數據傳輸過程沒問題。但是，運輸工人成功拿到了數據，整個過程還是不安全的，大概的過程是這樣：

這怎麼辦啊？這個問題的本質原因是，人們沒辦法獲知，保險箱到底是「我」做的，還是運輸工人做的。那乾脆，我們都別做保險箱了，讓權威機構做保險箱，然後在每個保險箱上用特殊的工具刻上一個編號。對方收到保險箱的時候，在權威機構的「公告欄」上查一下編號，要是和保險箱上的編號一樣，我就知道這個保險箱是「我」的，就安心把數據放進去。大概過程是這樣的：

如何做出刻上編號，而且編號沒法修改的保險箱呢？這涉及到了公鑰體制中的另一個問題：數字簽名。
要知道，刻字這種事情吧，誰都能幹，所以想做出只能自己刻字，還沒法讓別人修改的保險箱確實有點難度。那麼怎麼辦呢？這其實困擾了人們很長的時間。直到有一天，人們發現：我們不一定非要在保險箱上刻規規矩矩的字，我們乾脆在保險箱上刻手寫名字好了。而且，刻字有點麻煩，乾脆我們在上面弄張紙，讓人直接在上面寫，簡單不費事。具體做法是，我們在保險箱上嵌進去一張紙，然後每個出產的保險箱都讓權威機構的CEO簽上自己的名字。然後，CEO把自己的簽名公開在權威機構的「公告欄」上面。比如這個CEO就叫「學酥」，那麼整個流程差不多是這個樣子：

這個方法的本質原理是，每個人都能夠通過筆跡看出保險箱上的字是不是學酥CEO簽的。但是呢，這個字體是學酥CEO唯一的字體。別人很難模仿。如果模仿我們就能自己分辨出來了。要是實在分辨不出來呢，我們就請一個筆跡專家來分辨。這不是很好嘛。這個在密碼學上就是數字簽名。

上面這個簽字的方法雖然好，但是還有一個比較蛋疼的問題。因為簽字的樣子是公開的，一個聰明人可以把公開的簽字影印一份，自己造個保險箱，然後把這個影印的字也嵌進去。這樣一來，這個聰明人也可以造一個相同簽字的保險箱了。解決這個問題一個非常簡單的方法就是在看保險箱上的簽名時，不光看字體本身，還要看字體是不是和公開的字體完全一樣。要是完全一樣，就可以考慮這個簽名可能是影印出來的。甚至，還要考察字體是不是和其他保險櫃上的字體一模一樣。因為聰明人為了欺騙大家，可能不影印公開的簽名，而影印其他保險箱上的簽名。這種解決方法雖然簡單，但是驗證簽名的時候麻煩了一些。麻煩的地方在於我不僅需要對比保險箱上的簽名是否與公開的筆跡一樣，還需要對比得到的簽名是否與公開的筆跡完全一樣，乃至是否和所有發布的保險箱上的簽名完全一樣。有沒有什麼更好的方法呢？

當然有，人們想到了一個比較好的方法。那就是，學酥CEO簽字的時候吧，不光把名字簽上，還得帶上簽字得日期，或者帶上這個保險箱的編號。這樣一來，每一個保險箱上的簽字就唯一了，這個簽字是學酥CEO的簽名+學酥CEO寫上的時間或者編號。這樣一來，就算有人偽造，也只能偽造用過的保險箱。這個問題就徹底解決了。這個過程大概是這么個樣子：

3 造價問題（密鑰封裝機制，Key Encapsulation Mechanism）
解決了上面的各種問題，我們要考慮考慮成本了… 這種能「撞」門的保險箱雖然好，但是這種鎖造價一般來說要比普通的鎖要高，而且鎖生產時間也會變長。在密碼學中，對於同樣「結實」的鎖，能「撞」門的鎖的造價一般來說是普通鎖的上千倍。同時，能「撞」門的鎖一般來說只能安裝在小的保險櫃裡面。畢竟，這么復雜的鎖，裝起來很費事啊！而普通鎖安裝在多大的保險櫃上面都可以呢。如果兩個人想傳輸大量數據的話，用一個大的保險櫃比用一堆小的保險櫃慢慢傳要好的多呀。怎麼解決這個問題呢？人們又想出了一個非常棒的方法：我們把兩種鎖結合起來。能「撞」上的保險櫃裡面放一個普通鎖的鑰匙。然後造一個用普通的保險櫃來鎖大量的數據。這樣一來，我們相當於用能「撞」上的保險櫃發一個鑰匙過去。對方收到兩個保險櫃後，先用自己的鑰匙把小保險櫃打開，取出鑰匙。然後在用這個鑰匙開大的保險櫃。這樣做更棒的一個地方在於，既然對方得到了一個鑰匙，後續再通信的時候，我們就不再需要能「撞」上的保險櫃了啊，在以後一定時間內就用普通保險櫃就好了，方便快捷嘛。

以下參考 數字簽名、數字證書、SSL、https是什麼關系？
4.數字簽名（Digital Signature）
數據在瀏覽器和伺服器之間傳輸時，有可能在傳輸過程中被冒充的盜賊把內容替換了，那麼如何保證數據是真實伺服器發送的而不被調包呢，同時如何保證傳輸的數據沒有被人篡改呢，要解決這兩個問題就必須用到數字簽名，數字簽名就如同日常生活的中的簽名一樣，一旦在合同書上落下了你的大名，從法律意義上就確定是你本人簽的字兒，這是任何人都沒法仿造的，因為這是你專有的手跡，任何人是造不出來的。那麼在計算機中的數字簽名怎麼回事呢？數字簽名就是用於驗證傳輸的內容是不是真實伺服器發送的數據，發送的數據有沒有被篡改過，它就干這兩件事，是非對稱加密的一種應用場景。不過他是反過來用私鑰來加密，通過與之配對的公鑰來解密。
第一步：服務端把報文經過Hash處理後生成摘要信息Digest，摘要信息使用私鑰private-key加密之後就生成簽名，伺服器把簽名連同報文一起發送給客戶端。
第二步：客戶端接收到數據後，把簽名提取出來用public-key解密，如果能正常的解密出來Digest2，那麼就能確認是對方發的。
第三步：客戶端把報文Text提取出來做同樣的Hash處理，得到的摘要信息Digest1，再與之前解密出來的Digist2對比，如果兩者相等，就表示內容沒有被篡改，否則內容就是被人改過了。因為只要文本內容哪怕有任何一點點改動都會Hash出一個完全不一樣的摘要信息出來。

5.數字證書（Certificate Authority）
數字證書簡稱CA，它由權威機構給某網站頒發的一種認可憑證，這個憑證是被大家（瀏覽器）所認可的，為什麼需要用數字證書呢，難道有了數字簽名還不夠安全嗎？有這樣一種情況，就是瀏覽器無法確定所有的真實伺服器是不是真的是真實的，舉一個簡單的例子：A廠家給你們家安裝鎖，同時把鑰匙也交給你，只要鑰匙能打開鎖，你就可以確定鑰匙和鎖是配對的，如果有人把鑰匙換了或者把鎖換了，你是打不開門的，你就知道肯定被竊取了，但是如果有人把鎖和鑰匙替換成另一套表面看起來差不多的，但質量差很多的，雖然鑰匙和鎖配套，但是你卻不能確定這是否真的是A廠家給你的，那麼這時候，你可以找質檢部門來檢驗一下，這套鎖是不是真的來自於A廠家，質檢部門是權威機構，他說的話是可以被公眾認可的（呵呵）。
同樣的， 因為如果有人（張三）用自己的公鑰把真實伺服器發送給瀏覽器的公鑰替換了，於是張三用自己的私鑰執行相同的步驟對文本Hash、數字簽名，最後得到的結果都沒什麼問題，但事實上瀏覽器看到的東西卻不是真實伺服器給的，而是被張三從里到外（公鑰到私鑰）換了一通。那麼如何保證你現在使用的公鑰就是真實伺服器發給你的呢？我們就用數字證書來解決這個問題。數字證書一般由數字證書認證機構（Certificate Authority）頒發，證書裡麵包含了真實伺服器的公鑰和網站的一些其他信息，數字證書機構用自己的私鑰加密後發給瀏覽器，瀏覽器使用數字證書機構的公鑰解密後得到真實伺服器的公鑰。這個過程是建立在被大家所認可的證書機構之上得到的公鑰，所以這是一種安全的方式。

常見的對稱加密演算法有DES、3DES、AES、RC5、RC6。非對稱加密演算法應用非常廣泛，如SSH,
HTTPS, TLS，電子證書，電子簽名，電子身份證等等。
參考 DES/3DES/AES區別

B. 加密演算法的演算法

一個加密系統S可以用數學符號描述如下：
S={P, C, K, E, D}
其中
P——明文空間，表示全體可能出現的明文集合，
C——密文空間，表示全體可能出現的密文集合，
K——密鑰空間，密鑰是加密演算法中的可變參數，
E——加密演算法，由一些公式、法則或程序構成，
D——解密演算法，它是E的逆。
當給定密鑰kÎK時，各符號之間有如下關系：
C = Ek(P), 對明文P加密後得到密文C
P = Dk(C) = Dk(Ek(P)), 對密文C解密後得明文P
如用E-1 表示E的逆，D-1表示D的逆，則有：
Ek = Dk-1且Dk = Ek-1
因此，加密設計主要是確定E，D，K。
RSA是Rivest、Shamir和Adleman提出來的基於數論非對稱性(公開鑰)加密演算法。大整數的素因子難分解是RSA演算法的基礎。
RSA在國外早已進入實用階段，已研製出多種高速的RSA的專用晶元。盡管RSA的許多特性並不十分理想，但迫於信息安全的實際需要，許多重要的信息系統還是採用RSA作為基礎加密機制。從RSA提出不久，我國有關部門就一直對它進行研究。從應用的角度看，軟體實現的RSA已經開始用於計算機網路加密，用來完成密鑰分配、數字簽名等功能。
除了RSA之外，還有DES(數據加密標准)。盡管DES公開了其加密演算法並曾被美國列為「標准」，但很快被廢棄。加密技術又回歸到「演算法保密」的傳統上。

C. RSA  加密演算法（原理篇）

前幾天看到一句話，「我們中的很多人把一生中最燦爛的笑容大部分都獻給了手機和電腦屏幕」。心中一驚，這說明了什麼？手機和電腦已經成為了我們生活中的一部分，所以才會有最懂你的不是你，也不是你男朋友，而是大數據。

如此重要的個人數據，怎樣才能保證其在互聯網上的安全傳輸呢？當然要靠各種加密演算法。說起加密演算法，大家都知道有哈希、對稱加密和非對稱加密了。哈希是一個散列函數，具有不可逆操作；對稱加密即加密和解密使用同一個密鑰，而非對稱加密加密和解密自然就是兩個密鑰了。稍微深入一些的，還要說出非對稱加密演算法有DES、3DES、RC4等，非對稱加密演算法自然就是RSA了。那麼當我們聊起RSA時，我們又在聊些什麼呢？今天筆者和大家一起探討一下，有不足的地方，還望各位朋友多多提意見，共同進步。

RSA簡介：1976年由麻省理工學院三位數學家共同提出的，為了紀念這一里程碑式的成就，就用他們三個人的名字首字母作為演算法的命名。即 羅納德·李維斯特 （Ron Rivest）、 阿迪·薩莫爾 （Adi Shamir）和 倫納德·阿德曼 （Leonard Adleman）。

公鑰：用於加密，驗簽。

私鑰：解密，加簽。

通常知道了公鑰和私鑰的用途以後，即可滿足基本的聊天需求了。但是我們今天的主要任務是來探究一下RSA加解密的原理。

說起加密演算法的原理部分，肯定與數學知識脫不了關系。

我們先來回憶幾個數學知識：

φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。

這個公式主要是用來計算給定一個任意的正整數n，在小於等於n的正整數中，有多少個與n構成互質的關系。

其中n=A*B，A與B互為質數，但A與B本身並不要求為質數，可以繼續展開，直至都為質數。

在最終分解完成後，即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之後，p1，p2，p3都是質數。又用到了歐拉函數的另一個特點，即當p是質數的時候，φp = p - 1。所以有了上面給出的歐拉定理公式。

舉例看一下：

計算15的歐拉函數，因為15比較小，我們可以直接看一下，小於15的正整數有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互質的數有1、2、4、7、8、11、13、14一共四個。

對照我們剛才的歐拉定理： 。

其他感興趣的，大家可以自己驗證。

之所以要在這里介紹歐拉函數，我們在計算公鑰和私鑰時候，會用到。

如果兩個正整數m 和 n 互質，那麼m 的 φn 次方減1，可以被n整除。

 其中  .

其中當n為質數時，那麼  上面看到的公式就變成了

 mod n   1.

這個公式也就是著名的 費馬小定理 了。

如果兩個正整數e和x互為質數，那麼一定存在一個整數d，不止一個，使得 e*d - 1 可以被x整除，即 e * d mode x   1。則稱 d 是 e 相對於 x的模反元素。

了解了上面所講的歐拉函數、歐拉定理和模反元素後，就要來一些化學反應了，請看圖：

上面這幅圖的公式變化有沒有沒看明白的，沒看明白的咱們評論區見哈。

最終我們得到了最重要的第5個公式的變形，即紅色箭頭後面的：

 mod n   m。

其中有幾個關系，需要搞明白，m 與 n 互為質數，φn = x，d 是e相對於x的模反元素。

有沒有看到一些加解密的雛形。

從 m 到 m。 這中間涵蓋了從加密到解密的整個過程，但是缺少了我們想要的密文整個過程。

OK，下面引入本文的第四個數學公式：

我們來看一下整個交換流程：

1、客戶端有一個數字13，服務端有一個數字15;

2、客戶端通過計算 3的13次方 對 17 取余，得到數字12; 將12發送給服務端；同時服務端通過計算3的15次方，對17取余，得到數字6，將6發送給客戶端。至此，整個交換過程完成。

3、服務端收到數字12以後，繼續計算，12的15次方 對 17取余，得到 數字10。

4、客戶端收到數字 6以後，繼續計算，6的13次方 對 17 取余，得到數字 10。

有沒有發現雙方，最終得到了相同的內容10。但是這個數字10從來沒有在網路過程中出現過。

好，講到這里，可能有些人已經恍然大悟，這就是加密過程了，但是也有人會產生疑問，為什麼要取數字3 和 17 呢，這里還牽涉到另一個數學知識，原根的問題。即3是17的原根。看圖

有沒有發現規律，3的1~16次方，對17取余，得到的整數是從1~16。這時我們稱3為17的原根。也就是說上面的計算過程中有一組原根的關系。這是最早的迪菲赫爾曼秘鑰交換演算法。

解決了為什麼取3和17的問題後，下面繼續來看最終的RSA是如何產生的：

還記得我們上面提到的歐拉定理嗎，其中 m 與 n 互為質數，n為質數，d 是 e 相對於 φn的模反元素。

當迪菲赫爾曼密鑰交換演算法碰上歐拉定理會產生什麼呢？

我們得到下面的推論：

好，到這里我們是不是已經看到了整個的加密和解密過程了。

其中 m 是明文；c 是密文； n 和 e 為公鑰；d 和 n 為私鑰 。

其中幾組數字的關系一定要明確：

1、d是e 相對於 φn 的模反元素，φn = n-1，即 e * d mod n = 1.

2、m 小於 n，上面在講迪菲赫爾曼密鑰交換演算法時，提到原根的問題，在RSA加密演算法中，對m和n並沒有原根條件的約束。只要滿足m與n互為質數，n為質數，且m < n就可以了。

OK，上面就是RSA加密演算法的原理了，經過上面幾個數學公式的狂轟亂炸，是不是有點迷亂了，給大家一些時間理一下，後面會和大家一起來驗證RSA演算法以及RSA為什麼安全。

D. 用於文件加密的演算法有哪些，以及它們的原理

MD5全稱"message-digest algorithm 5"(信息-摘要演算法)。

90年代初由MIT計算機科學實驗室和RSA Data Security Inc聯合開發。

MD5演算法採用128位加密方式，即使一台計算機每秒可嘗試10億條明文，要跑出原始明文也要1022年。在802.1X認證中，一直使用此演算法。

加密演算法之二---ELGamal

ELGamal演算法是一種較為常見的加密演算法，他基於1984年提出的公鑰密碼體制和橢圓曲線加密體系。即能用於數據加密，又能用於數字簽名，起安全性依賴於計算有限領域上離散對數這一數學難題。

著名的DSS和Schnorr和美國國家標准X9.30-199X中ELGamal為唯一認可加密方式。並且橢圓曲線密碼加密體系增強了ELGamal演算法的安全性。

ELGamal在加密過程中，生成的密文長度是明文的兩倍。且每次加密後都會在密文中生成一個隨即數K。

加密演算法之三---BlowFish

BlowFish演算法由著名的密碼學專家部魯斯·施耐爾所開發，是一個基於64位分組及可變密鑰長度[32-448位]的分組密碼演算法。

BlowFish演算法的核心加密函數名為BF_En，為一種對稱演算法，加密強度不夠。

加密演算法之四---SHA

SHA（即Secure Hash Algorithm，安全散列演算法）是一種常用的數據加密演算法，由美國國家標准與技術局於1993年做為聯邦信息處理標准公布，先版本SHA-1，SHA-2。

SHA演算法與MD5類似，同樣按2bit數據塊為單位來處理輸入，但它能產生160bit的信息摘要，具有比MD5更強的安全性。

SHA收到一段明文，然後以不可逆方式將它轉為一段密文，該演算法被廣泛運用於數字簽名及電子商務交易的身份認證中。(

E. DES加密演算法原理

網路安全通信中要用到兩類密碼演算法，一類是對稱密碼演算法，另一類是非對稱密碼演算法。對稱密碼演算法有時又叫傳統密碼演算法、秘密密鑰演算法或單密鑰演算法，非對稱密碼演算法也叫公開密鑰密碼演算法或雙密鑰演算法。對稱密碼演算法的加密密鑰能夠從解密密鑰中推算出來，反過來也成立。在大多數對稱演算法中，加密解密密鑰是相同的。它要求發送者和接收者在安全通信之前，商定一個密鑰。對稱演算法的安全性依賴於密鑰，泄漏密鑰就意味著任何人都能對消息進行加密解密。只要通信需要保密，密鑰就必須保密。

對稱演算法又可分為兩類。一次只對明文中的單個位（有時對位元組）運算的演算法稱為序列演算法或序列密碼。另一類演算法是對明文的一組位進行運算，這些位組稱為分組，相應的演算法稱為分組演算法或分組密碼。現代計算機密碼演算法的典型分組長度為64位――這個長度既考慮到分析破譯密碼的難度，又考慮到使用的方便性。後來，隨著破譯能力的發展，分組長度又提高到128位或更長。
常用的採用對稱密碼術的加密方案有5個組成部分（如圖所示）

1)明文：原始信息。
2)加密演算法：以密鑰為參數，對明文進行多種置換和轉換的規則和步驟，變換結果為密文。
3)密鑰：加密與解密演算法的參數，直接影響對明文進行變換的結果。
4)密文：對明文進行變換的結果。
5)解密演算法：加密演算法的逆變換，以密文為輸入、密鑰為參數，變換結果為明文。

對稱密碼當中有幾種常用到的數學運算。這些運算的共同目的就是把被加密的明文數碼盡可能深地打亂，從而加大破譯的難度。

◆移位和循環移位
移位就是將一段數碼按照規定的位數整體性地左移或右移。循環右移就是當右移時，把數碼的最後的位移到數碼的最前頭，循環左移正相反。例如，對十進制數碼12345678循環右移1位（十進制位）的結果為81234567，而循環左移1位的結果則為23456781。
◆置換
就是將數碼中的某一位的值根據置換表的規定，用另一位代替。它不像移位操作那樣整齊有序，看上去雜亂無章。這正是加密所需,被經常應用。
◆擴展
就是將一段數碼擴展成比原來位數更長的數碼。擴展方法有多種,例如,可以用置換的方法，以擴展置換表來規定擴展後的數碼每一位的替代值。
◆壓縮
就是將一段數碼壓縮成比原來位數更短的數碼。壓縮方法有多種，例如，也可以用置換的方法，以表來規定壓縮後的數碼每一位的替代值。
◆異或
這是一種二進制布爾代數運算。異或的數學符號為⊕ ，它的運演算法則如下：
1⊕1 = 0
0⊕0 = 0
1⊕0 = 1
0⊕1 = 1
也可以簡單地理解為，參與異或運算的兩數位如相等，則結果為0，不等則為1。
◆迭代
迭代就是多次重復相同的運算，這在密碼演算法中經常使用，以使得形成的密文更加難以破解。

下面我們將介紹一種流行的對稱密碼演算法DES。

DES是Data Encryption Standard（數據加密標准）的縮寫。它是由IBM公司研製的一種對稱密碼演算法，美國國家標准局於1977年公布把它作為非機要部門使用的數據加密標准，三十年來，它一直活躍在國際保密通信的舞台上，扮演了十分重要的角色。

DES是一個分組加密演算法，典型的DES以64位為分組對數據加密，加密和解密用的是同一個演算法。它的密鑰長度是56位（因為每個第8 位都用作奇偶校驗），密鑰可以是任意的56位的數，而且可以任意時候改變。其中有極少數被認為是易破解的弱密鑰，但是很容易避開它們不用。所以保密性依賴於密鑰。

DES加密的演算法框架如下：
首先要生成一套加密密鑰，從用戶處取得一個64位長的密碼口令，然後通過等分、移位、選取和迭代形成一套16個加密密鑰，分別供每一輪運算中使用。

DES對64位(bit)的明文分組M進行操作，M經過一個初始置換IP，置換成m0。將m0明文分成左半部分和右半部分m0 = (L0，R0)，各32位長。然後進行16輪完全相同的運算（迭代），這些運算被稱為函數f，在每一輪運算過程中數據與相應的密鑰結合。

在每一輪中，密鑰位移位，然後再從密鑰的56位中選出48位。通過一個擴展置換將數據的右半部分擴展成48位，並通過一個異或操作替代成新的48位數據，再將其壓縮置換成32位。這四步運算構成了函數f。然後，通過另一個異或運算，函數f的輸出與左半部分結合，其結果成為新的右半部分，原來的右半部分成為新的左半部分。將該操作重復16次。

經過16輪迭代後，左，右半部分合在一起經過一個末置換（數據整理），這樣就完成了加密過程。
加密流程如圖所示。

DES解密過程：
在了解了加密過程中所有的代替、置換、異或和循環迭代之後，讀者也許會認為，解密演算法應該是加密的逆運算，與加密演算法完全不同。恰恰相反，經過密碼學家精心設計選擇的各種操作，DES獲得了一個非常有用的性質：加密和解密使用相同的演算法！

DES加密和解密唯一的不同是密鑰的次序相反。如果各輪加密密鑰分別是K1，K2，K3…K16，那麼解密密鑰就是K16，K15，K14…K1。這也就是DES被稱為對稱演算法的理由吧。

至於對稱密碼為什麼能對稱? DES具體是如何操作的？本文附錄中將做進一步介紹，有興趣的讀者不妨去讀一讀探個究竟

4.DES演算法的安全性和發展
DES的安全性首先取決於密鑰的長度。密鑰越長，破譯者利用窮舉法搜索密鑰的難度就越大。目前，根據當今計算機的處理速度和能力，56位長度的密鑰已經能夠被破解，而128位的密鑰則被認為是安全的，但隨著時間的推移，這個數字也遲早會被突破。

另外，對DES演算法進行某種變型和改進也是提高DES演算法安全性的途徑。

例如後來演變出的3-DES演算法使用了3個獨立密鑰進行三重DES加密，這就比DES大大提高了安全性。如果56位DES用窮舉搜索來破譯需要2∧56次運算，而3-DES 則需要2∧112次。

又如，獨立子密鑰DES由於每輪都使用不同的子密鑰，這意味著其密鑰長度在56位的基礎上擴大到768位。DES還有DESX、CRYPT、GDES、RDES等變型。這些變型和改進的目的都是為了加大破譯難度以及提高密碼運算的效率

F. 常見密碼演算法原理

PBKDF2(Password-Based Key Derivation Function)是一個用來導出密鑰的函數，用來生成加密的密碼，增加破解的難度，類似bcrypt/scrypt等，可以用來進行密碼或者口令的加密存儲。主要是鹽值+pwd，經過多輪HMAC演算法的計算，產生的密文。
PBKDF2函數的定義
DK = PBKDF2(PRF, Password, Salt, c, dkLen)
• PRF是一個偽隨機函數，例如HASH_HMAC函數，它會輸出長度為hLen的結果。
• Password是用來生成密鑰的原文密碼。
• Salt是一個加密用的鹽值。
• c是進行重復計算的次數。
• dkLen是期望得到的密鑰的長度。
• DK是最後產生的密鑰。
https://segmentfault.com/a/1190000004261009

下面我們以Alice和Bob為例敘述Diffie-Hellman密鑰交換的原理。
1,Diffie-Hellman交換過程中涉及到的所有參與者定義一個組，在這個組中定義一個大質數p，底數g。
2,Diffie-Hellman密鑰交換是一個兩部分的過程，Alice和Bob都需要一個私有的數字a，b。
下面是DH交換的過程圖：
本圖片來自wiki
下面我們進行一個實例
1.愛麗絲與鮑伯協定使用p=23以及g=5.
2.愛麗絲選擇一個秘密整數a=6, 計算A = g^a mod p並發送給鮑伯。
A = 5^6 mod 23 = 8.
3.鮑伯選擇一個秘密整數b=15, 計算B = g^b mod p並發送給愛麗絲。
B = 5^15 mod 23 = 19.
4.愛麗絲計算s = B a mod p
19^6 mod 23 = 2.
5.鮑伯計算s = A b mod p
8^15 mod 23 = 2.

ECDH:
ECC演算法和DH結合使用，用於密鑰磋商，這個密鑰交換演算法稱為ECDH。交換雙方可以在不共享任何秘密的情況下協商出一個密鑰。ECC是建立在基於橢圓曲線的離散對數問題上的密碼體制，給定橢圓曲線上的一個點P，一個整數k，求解Q=kP很容易；給定一個點P、Q，知道Q=kP，求整數k確是一個難題。ECDH即建立在此數學難題之上。密鑰磋商過程：
假設密鑰交換雙方為Alice、Bob，其有共享曲線參數（橢圓曲線E、階N、基點G）。

來自 http://www.cnblogs.com/fishou/p/4206451.html

https://zh.wikipedia.org/wiki/SHA%E5%AE%B6%E6%97%8F

exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
-----END RSA PRIVATE KEY-----
while a RSA public key contains only the following data:
-----BEGIN RSA PUBLIC KEY-----
RSAPublicKey ::= SEQUENCE {
molus INTEGER, -- n
publicExponent INTEGER -- e
}
-----END RSA PUBLIC KEY-----
and this explains why the private key block is larger.
Note that a more standard format for non-RSA public keys is
-----BEGIN PUBLIC KEY-----
PublicKeyInfo ::= SEQUENCE {
algorithm AlgorithmIdentifier,
PublicKey BIT STRING
}
AlgorithmIdentifier ::= SEQUENCE {
algorithm OBJECT IDENTIFIER,
parameters ANY DEFINED BY algorithm OPTIONAL
}
-----END PUBLIC KEY-----
More info here.
BTW, since you just posted a screenshot of the private key I strongly hope it was just for tests :)

密鑰的長度
C:\herong>java RsaKeyGenerator 128
p: 17902136406704537069
q: 17902136406704537077
m:
Molus:
Key size: 128
Public key:
Private key:
C:\herong>java RsaKeyGenerator 256
p:
q:
m: ...
Molus: ...
Key size: 256
Public key: ...
Private key: ...

https://security.stackexchange.com/questions/90169/rsa-public-key-and-private-key-lengths
https://stackoverflow.com/questions/2921508/trying-to-understand-java-rsa-key-size >

http://www.herongyang.com/Cryptography/RSA-BigInteger-Keys-Generated-by-RsaKeyGenerator-java.html

update() adds data to the Cipher』s internal buffer, then returns all currently completely encoded blocks. If there are any encoded blocks left over, they remain in the Cipher』s buffer until the next call, or a call to doFinal(). This means that if you call update() with a four byte array to encrypt, and the buffer size is eight bytes, you will not receive encoded data on the return (you』ll get a null instead). If your next call to update() passes five bytes of data in, you will get an 8 byte (the block size) array back, containing the four bytes passed in on the previous call, the first four bytes from the current call – the remaining byte from the current call is left in the Cipher』s buffer.
doFinal() on the other hand is much simpler: it encrypts the passed data, pads it out to the necessary length, and then returns it. The Cipher is essentially stateless.

來自 https://segmentfault.com/a/1190000006931511

DH演算法的中間人攻擊
在最初的描述中，迪菲－赫爾曼密鑰交換本身並沒有提供通訊雙方的身份驗證服務，因此它很容易受到中間人攻擊。 一個中間人在信道的中央進行兩次迪菲－赫爾曼密鑰交換，一次和Alice另一次和Bob，就能夠成功的向Alice假裝自己是Bob，反之亦然。而攻擊者可以解密（讀取和存儲）任何一個人的信息並重新加密信息，然後傳遞給另一個人。因此通常都需要一個能夠驗證通訊雙方身份的機制來防止這類攻擊。

優缺點：
1、 僅當需要時才生成密鑰，減小了將密鑰存儲很長一段時間而致使遭受攻擊的機會。
2、 除對全局參數的約定外，密鑰交換不需要事先存在的基礎結構。
然而，該技術也存在許多不足：
1、 沒有提供雙方身份的任何信息。
2、 它是計算密集性的，因此容易遭受阻塞性攻擊，即對手請求大量的密鑰。受攻擊者花費了相對多的計算資源來求解無用的冪系數而不是在做真正的工作。
3、 沒辦法防止重演攻擊。
4、 容易遭受中間人的攻擊。第三方C在和A通信時扮演B；和B通信時扮演A。A和B都與C協商了一個密鑰，然後C就可以監聽和傳遞通信量。中間人的攻擊按如下進行：
（1） B在給A的報文中發送他的公開密鑰。
（2） C截獲並解析該報文。C將B的公開密鑰保存下來並給A發送報文，該報文具有B的用戶ID但使用C的公開密鑰YC，仍按照好像是來自B的樣子被發送出去。A收到C的報文後，將YC和B的用戶ID存儲在一塊。類似地，C使用YC向B發送好像來自A的報文。
（3） B基於私有密鑰XB和YC計算秘密密鑰K1。A基於私有密鑰XA和YC計算秘密密鑰K2。C使用私有密鑰XC和YB計算K1，並使用XC和YA計算K2。
（4） 從現在開始，C就可以轉發A發給B的報文或轉發B發給A的報文，在途中根據需要修改它們的密文。使得A和B都不知道他們在和C共享通信。

G. RSA加密、解密、簽名、驗簽的原理及方法

RSA加密是一種非對稱加密。可以在不直接傳遞密鑰的情況下，完成解密。這能夠確保信息的安全性，避免了直接傳遞密鑰所造成的被破解的風險。是由一對密鑰來進行加解密的過程，分別稱為公鑰和私鑰。兩者之間有數學相關，該加密演算法的原理就是對一極大整數做因數分解的困難性來保證安全性。通常個人保存私鑰，公鑰是公開的（可能同時多人持有）。

加密和簽名都是為了安全性考慮，但略有不同。常有人問加密和簽名是用私鑰還是公鑰？其實都是對加密和簽名的作用有所混淆。簡單的說，加密是為了防止信息被泄露，而簽名是為了防止信息被篡改。這里舉2個例子說明。

RSA的加密過程如下：

RSA簽名的過程如下：

總結：公鑰加密、私鑰解密、私鑰簽名、公鑰驗簽。

RSA加密對明文的長度有所限制，規定需加密的明文最大長度=密鑰長度-11（單位是位元組，即byte），所以在加密和解密的過程中需要分塊進行。而密鑰默認是1024位，即1024位/8位-11=128-11=117位元組。所以默認加密前的明文最大長度117位元組，解密密文最大長度為128字。那麼為啥兩者相差11位元組呢？是因為RSA加密使用到了填充模式（padding），即內容不足117位元組時會自動填滿，用到填充模式自然會佔用一定的位元組，而且這部分位元組也是參與加密的。

H. 質數的定義是什麼大質數加密的原理是什麼

只能被1和本身整除的數叫質數，例如13，質數是無窮多的。得到兩個巨大質數的乘積是簡單的事，但想從該乘積反推出這兩個巨大質數卻沒有任何有效的辦法，這種不可逆的單向數學關系，是國際數學界公認的質因數分解難題。

R、S、A三人巧妙利用這一假說，設計出RSA公匙加密演算法的基本原理：1、讓計算機隨機生成兩個大質數p和q，得出乘積n；2、利用p和q有條件的生成加密密鑰e；3、通過一系列計算，得到與n互為質數的解密密鑰d，置於操作系統才知道的地方；4、操作系統將n和e共同作為公匙對外發布，將私匙d秘密保存，把初始質數p和q秘密丟棄。

國際數學和密碼學界已證明，企圖利用公匙和密文推斷出明文--或者企圖利用公匙推斷出私匙的難度等同於分解兩個巨大質數的積。這就是Eve不可能對Alice的密文解密以及公匙可以在網上公布的原因。

至於"巨大質數"要多大才能保證安全的問題不用擔心：利用當前可預測的計算能力，在十進制下，分解兩個250位質數的積要用數十萬年的時間；並且質數用盡或兩台計算機偶然使用相同質數的概率小到可以被忽略。

I. 橢圓曲線加密演算法

橢圓曲線加密演算法，即：Elliptic Curve Cryptography，簡稱ECC，是基於橢圓曲線數學理論實現的一種非對稱加密演算法。相比RSA，ECC優勢是可以使用更短的密鑰，來實現與RSA相當或更高的安全。據研究，160位ECC加密安全性相當於1024位RSA加密，210位ECC加密安全性相當於2048位RSA加密。

橢圓曲線在密碼學中的使用，是1985年由Neal Koblitz和Victor Miller分別獨立提出的。

一般情況下，橢圓曲線可用下列方程式來表示，其中a,b,c,d為系數。

例如，當a=1,b=0,c=-2,d=4時，所得到的橢圓曲線為:

該橢圓曲線E的圖像如圖X-1所示，可以看出根本就不是橢圓形。

過曲線上的兩點A、B畫一條直線，找到直線與橢圓曲線的交點，交點關於x軸對稱位置的點，定義為A+B，即為加法。如下圖所示：A + B = C

上述方法無法解釋A + A，即兩點重合的情況。因此在這種情況下，將橢圓曲線在A點的切線，與橢圓曲線的交點，交點關於x軸對稱位置的點，定義為A + A，即2A，即為二倍運算。

將A關於x軸對稱位置的點定義為-A，即橢圓曲線的正負取反運算。如下圖所示：

如果將A與-A相加，過A與-A的直線平行於y軸，可以認為直線與橢圓曲線相交於無窮遠點。

綜上，定義了A+B、2A運算，因此給定橢圓曲線的某一點G，可以求出2G、3G（即G + 2G）、4G......。即：當給定G點時，已知x，求xG點並不困難。反之，已知xG點，求x則非常困難。此即為橢圓曲線加密演算法背後的數學原理。

橢圓曲線要形成一條光滑的曲線，要求x,y取值均為實數，即實數域上的橢圓曲線。但橢圓曲線加密演算法，並非使用實數域，而是使用有限域。按數論定義，有限域GF(p)指給定某個質數p，由0、1、2......p-1共p個元素組成的整數集合中定義的加減乘除運算。

假設橢圓曲線為y² = x³ + x + 1，其在有限域GF(23)上時，寫作：y² ≡ x³ + x + 1 (mod 23)

此時，橢圓曲線不再是一條光滑曲線，而是一些不連續的點，如下圖所示。以點(1,7)為例，7² ≡ 1³ + 1 + 1 ≡ 3 (mod 23)。如此還有如下點：

(0,1) (0,22)(1,7) (1,16)(3,10) (3,13)(4,0)(5,4) (5,19)(6,4) (6,19)(7,11) (7,12)(9,7) (9,16)(11,3) (11,20)等等。

另外，如果P(x,y)為橢圓曲線上的點，則-P即(x,-y)也為橢圓曲線上的點。如點P(0,1)，-P=(0,-1)=(0,22)也為橢圓曲線上的點。

相關公式如下：有限域GF(p)上的橢圓曲線y² = x³ + ax + b，若P(Xp, Yp), Q(Xq, Yq)，且P≠-Q，則R(Xr,Yr) = P+Q 由如下規則確定：

Xr = (λ² - Xp - Xq) mod pYr = (λ(Xp - Xr) - Yp) mod p其中λ = (Yq - Yp)/(Xq - Xp) mod p（若P≠Q）, λ = (3Xp² + a)/2Yp mod p（若P=Q）

因此，有限域GF(23)上的橢圓曲線y² ≡ x³ + x + 1 (mod 23)，假設以(0,1)為G點，計算2G、3G、4G...xG等等，方法如下：

計算2G：λ = (3x0² + 1)/2x1 mod 23 = (1/2) mod 23 = 12Xr = (12² - 0 - 0) mod 23 = 6Yr = (12(0 - 6) - 1) mod 23 = 19即2G為點(6,19)

計算3G：3G = G + 2G，即(0,1) + (6,19)λ = (19 - 1)/(6 - 0) mod 23 = 3Xr = (3² - 0 - 6) mod 23 = 3Yr = (3(0 - 3) - 1) mod 23 = 13即3G為點(3, 13)

建立基於橢圓曲線的加密機制，需要找到類似RSA質因子分解或其他求離散對數這樣的難題。而橢圓曲線上的已知G和xG求x，是非常困難的，此即為橢圓曲線上的的離散對數問題。此處x即為私鑰，xG即為公鑰。

橢圓曲線加密演算法原理如下：

設私鑰、公鑰分別為k、K，即K = kG，其中G為G點。

公鑰加密：選擇隨機數r，將消息M生成密文C，該密文是一個點對，即：C = {rG, M+rK}，其中K為公鑰

私鑰解密：M + rK - k(rG) = M + r(kG) - k(rG) = M其中k、K分別為私鑰、公鑰。

橢圓曲線簽名演算法，即ECDSA。設私鑰、公鑰分別為k、K，即K = kG，其中G為G點。

私鑰簽名：1、選擇隨機數r，計算點rG(x, y)。2、根據隨機數r、消息M的哈希h、私鑰k，計算s = (h + kx)/r。3、將消息M、和簽名{rG, s}發給接收方。

公鑰驗證簽名：1、接收方收到消息M、以及簽名{rG=(x,y), s}。2、根據消息求哈希h。3、使用發送方公鑰K計算：hG/s + xK/s，並與rG比較，如相等即驗簽成功。

原理如下：hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s= r(h+xk)G / (h+kx) = rG

假設要簽名的消息是一個字元串：「Hello World!」。DSA簽名的第一個步驟是對待簽名的消息生成一個消息摘要。不同的簽名演算法使用不同的消息摘要演算法。而ECDSA256使用SHA256生成256比特的摘要。
摘要生成結束後，應用簽名演算法對摘要進行簽名：
產生一個隨機數k
利用隨機數k，計算出兩個大數r和s。將r和s拼在一起就構成了對消息摘要的簽名。
這里需要注意的是，因為隨機數k的存在，對於同一條消息，使用同一個演算法，產生的簽名是不一樣的。從函數的角度來理解，簽名函數對同樣的輸入會產生不同的輸出。因為函數內部會將隨機值混入簽名的過程。

關於驗證過程，這里不討論它的演算法細節。從宏觀上看，消息的接收方從簽名中分離出r和s，然後利用公開的密鑰信息和s計算出r。如果計算出的r和接收到的r值相同，則表示驗證成功。否則，表示驗證失敗。

J. 加密解密字元串的演算法原理

我們經常需要一種措施來保護我們的數據，防止被一些懷有不良用心的人所看到或者破壞。在信息時代，信息可以幫助團體或個人，使他們受益，同樣，信息也可以用來對他們構成威脅，造成破壞。在競爭激烈的大公司中，工業間諜經常會獲取對方的情報。因此，在客觀上就需要一種強有力的安全措施來保護機密數據不被竊取或篡改。數據加密與解密從宏觀上講是非常簡單的，很容易理解。加密與解密的一些方法是非常直接的，很容易掌握，可以很方便的對機密數據進行加密和解密。

一：數據加密方法

在傳統上，我們有幾種方法來加密數據流。所有這些方法都可以用軟體很容易的實現，但是當我們只知道密文的時候，是不容易破譯這些加密演算法的（當同時有原文和密文時，破譯加密演算法雖然也不是很容易，但已經是可能的了）。最好的加密演算法對系統性能幾乎沒有影響，並且還可以帶來其他內在的優點。例如，大家都知道的pkzip，它既壓縮數據又加密數據。又如，dbms的一些軟體包總是包含一些加密方法以使復制文件這一功能對一些敏感數據是無效的，或者需要用戶的密碼。所有這些加密演算法都要有高效的加密和解密能力。

幸運的是，在所有的加密演算法中最簡單的一種就是「置換表」演算法，這種演算法也能很好達到加密的需要。每一個數據段（總是一個位元組）對應著「置換表」中的一個偏移量，偏移量所對應的值就輸出成為加密後的文件。加密程序和解密程序都需要一個這樣的「置換表」。事實上，80x86 cpu系列就有一個指令『xlat』在硬體級來完成這樣的工作。這種加密演算法比較簡單，加密解密速度都很快，但是一旦這個「置換表」被對方獲得，那這個加密方案就完全被識破了。更進一步講，這種加密演算法對於黑客破譯來講是相當直接的，只要找到一個「置換表」就可以了。這種方法在計算機出現之前就已經被廣泛的使用。

對這種「置換表」方式的一個改進就是使用2個或者更多的「置換表」，這些表都是基於數據流中位元組的位置的，或者基於數據流本身。這時，破譯變的更加困難，因為黑客必須正確的做幾次變換。通過使用更多的「置換表」，並且按偽隨機的方式使用每個表，這種改進的加密方法已經變的很難破譯。比如，我們可以對所有的偶數位置的數據使用a表，對所有的奇數位置使用b表，即使黑客獲得了明文和密文，他想破譯這個加密方案也是非常困難的，除非黑客確切的知道用了兩張表。

與使用「置換表」相類似，「變換數據位置」也在計算機加密中使用。但是，這需要更多的執行時間。從輸入中讀入明文放到一個buffer中，再在buffer中對他們重排序，然後按這個順序再輸出。解密程序按相反的順序還原數據。這種方法總是和一些別的加密演算法混合使用，這就使得破譯變的特別的困難，幾乎有些不可能了。例如，有這樣一個詞，變換起字母的順序，slient 可以變為listen，但所有的字母都沒有變化，沒有增加也沒有減少，但是字母之間的順序已經變化了。

但是，還有一種更好的加密演算法，只有計算機可以做，就是字/位元組循環移位和xor操作。如果我們把一個字或位元組在一個數據流內做循環移位，使用多個或變化的方向（左移或右移），就可以迅速的產生一個加密的數據流。這種方法是很好的，破譯它就更加困難！而且，更進一步的是，如果再使用xor操作，按位做異或操作，就就使破譯密碼更加困難了。如果再使用偽隨機的方法，這涉及到要產生一系列的數字，我們可以使用fibbonaci數列。對數列所產生的數做模運算（例如模3），得到一個結果，然後循環移位這個結果的次數，將使破譯次密碼變的幾乎不可能！但是，使用fibbonaci數列這種偽隨機的方式所產生的密碼對我們的解密程序來講是非常容易的。

在一些情況下，我們想能夠知道數據是否已經被篡改了或被破壞了，這時就需要產生一些校驗碼，並且把這些校驗碼插入到數據流中。這樣做對數據的防偽與程序本身都是有好處的。但是感染計算機程序的病毒才不會在意這些數據或程序是否加過密，是否有數字簽名。所以，加密程序在每次load到內存要開始執行時，都要檢查一下本身是否被病毒感染，對與需要加、解密的文件都要做這種檢查！很自然，這樣一種方法體制應該保密的，因為病毒程序的編寫者將會利用這些來破壞別人的程序或數據。因此，在一些反病毒或殺病毒軟體中一定要使用加密技術。

循環冗餘校驗是一種典型的校驗數據的方法。對於每一個數據塊，它使用位循環移位和xor操作來產生一個16位或32位的校驗和 ，這使得丟失一位或兩個位的錯誤一定會導致校驗和出錯。這種方式很久以來就應用於文件的傳輸，例如 xmodem-crc。 這是方法已經成為標准，而且有詳細的文檔。但是，基於標准crc演算法的一種修改演算法對於發現加密數據塊中的錯誤和文件是否被病毒感染是很有效的。

二．基於公鑰的加密演算法

一個好的加密演算法的重要特點之一是具有這種能力：可以指定一個密碼或密鑰，並用它來加密明文，不同的密碼或密鑰產生不同的密文。這又分為兩種方式：對稱密鑰演算法和非對稱密鑰演算法。所謂對稱密鑰演算法就是加密解密都使用相同的密鑰，非對稱密鑰演算法就是加密解密使用不同的密鑰。非常著名的pgp公鑰加密以及rsa加密方法都是非對稱加密演算法。加密密鑰，即公鑰，與解密密鑰，即私鑰，是非常的不同的。從數學理論上講，幾乎沒有真正不可逆的演算法存在。例如，對於一個輸入『a』執行一個操作得到結果『b』,那麼我們可以基於『b』，做一個相對應的操作，導出輸入『a』。在一些情況下，對於每一種操作，我們可以得到一個確定的值，或者該操作沒有定義（比如，除數為0）。對於一個沒有定義的操作來講，基於加密演算法，可以成功地防止把一個公鑰變換成為私鑰。因此，要想破譯非對稱加密演算法，找到那個唯一的密鑰，唯一的方法只能是反復的試驗，而這需要大量的處理時間。

rsa加密演算法使用了兩個非常大的素數來產生公鑰和私鑰。即使從一個公鑰中通過因數分解可以得到私鑰，但這個運算所包含的計算量是非常巨大的，以至於在現實上是不可行的。加密演算法本身也是很慢的，這使得使用rsa演算法加密大量的數據變的有些不可行。這就使得一些現實中加密演算法都基於rsa加密演算法。pgp演算法(以及大多數基於rsa演算法的加密方法)使用公鑰來加密一個對稱加密演算法的密鑰，然後再利用一個快速的對稱加密演算法來加密數據。這個對稱演算法的密鑰是隨機產生的，是保密的，因此，得到這個密鑰的唯一方法就是使用私鑰來解密。

我們舉一個例子：假定現在要加密一些數據使用密鑰『12345』。利用rsa公鑰，使用rsa演算法加密這個密鑰『12345』，並把它放在要加密的數據的前面（可能後面跟著一個分割符或文件長度，以區分數據和密鑰），然後，使用對稱加密演算法加密正文，使用的密鑰就是『12345』。當對方收到時，解密程序找到加密過的密鑰，並利用rsa私鑰解密出來，然後再確定出數據的開始位置，利用密鑰『12345』來解密數據。這樣就使得一個可靠的經過高效加密的數據安全地傳輸和解密。

一些簡單的基於rsa演算法的加密演算法可在下面的站點找到：

ftp://ftp.funet.fi/pub/crypt/cryptography/asymmetric/rsa

三．一個嶄新的多步加密演算法

現在又出現了一種新的加密演算法，據說是幾乎不可能被破譯的。這個演算法在1998年6月1日才正式公布的。下面詳細的介紹這個演算法:

使用一系列的數字（比如說128位密鑰），來產生一個可重復的但高度隨機化的偽隨機的數字的序列。一次使用256個表項，使用隨機數序列來產生密碼轉表，如下所示：

把256個隨機數放在一個距陣中，然後對他們進行排序，使用這樣一種方式（我們要記住最初的位置）使用最初的位置來產生一個表，隨意排序的表，表中的數字在0到255之間。如果不是很明白如何來做，就可以不管它。但是，下面也提供了一些原碼（在下面）是我們明白是如何來做的。現在，產生了一個具體的256位元組的表。讓這個隨機數產生器接著來產生這個表中的其餘的數，以至於每個表是不同的。下一步，使用"shotgun technique"技術來產生解碼表。基本上說，如果 a映射到b，那麼b一定可以映射到a，所以b[a[n]] = n.（n是一個在0到255之間的數）。在一個循環中賦值，使用一個256位元組的解碼表它對應於我們剛才在上一步產生的256位元組的加密表。

使用這個方法，已經可以產生這樣的一個表，表的順序是隨機，所以產生這256個位元組的隨機數使用的是二次偽隨機,使用了兩個額外的16位的密碼.現在，已經有了兩張轉換表，基本的加密解密是如下這樣工作的。前一個位元組密文是這個256位元組的表的索引。或者，為了提高加密效果，可以使用多餘8位的值，甚至使用校驗和或者crc演算法來產生索引位元組。假定這個表是256*256的數組,將會是下面的樣子:

crypto1 = a[crypto0][value]

變數'crypto1'是加密後的數據，'crypto0'是前一個加密數據（或著是前面幾個加密數據的一個函數值）。很自然的，第一個數據需要一個「種子」，這個「種子」 是我們必須記住的。如果使用256*256的表，這樣做將會增加密文的長度。或者，可以使用你產生出隨機數序列所用的密碼，也可能是它的crc校驗和。順便提及的是曾作過這樣一個測試: 使用16個位元組來產生表的索引,以128位的密鑰作為這16個位元組的初始的"種子"。然後，在產生出這些隨機數的表之後，就可以用來加密數據，速度達到每秒鍾100k個位元組。一定要保證在加密與解密時都使用加密的值作為表的索引，而且這兩次一定要匹配。

加密時所產生的偽隨機序列是很隨意的，可以設計成想要的任何序列。沒有關於這個隨機序列的詳細的信息，解密密文是不現實的。例如：一些ascii碼的序列，如「eeeeeeee"可能被轉化成一些隨機的沒有任何意義的亂碼，每一個位元組都依賴於其前一個位元組的密文，而不是實際的值。對於任一個單個的字元的這種變換來說，隱藏了加密數據的有效的真正的長度。

如果確實不理解如何來產生一個隨機數序列，就考慮fibbonacci數列，使用2個雙字（64位）的數作為產生隨機數的種子，再加上第三個雙字來做xor操作。 這個演算法產生了一系列的隨機數。演算法如下：

unsigned long dw1, dw2, dw3, dwmask;

int i1;

unsigned long arandom[256];

dw1 = {seed #1};

dw2 = {seed #2};

dwmask = {seed #3};

// this gives you 3 32-bit "seeds", or 96 bits total

for(i1=0; i1 < 256; i1++)

{

dw3 = (dw1 + dw2) ^ dwmask;

arandom[i1] = dw3;

dw1 = dw2;

dw2 = dw3;

}

如果想產生一系列的隨機數字，比如說，在0和列表中所有的隨機數之間的一些數，就可以使用下面的方法：

int __cdecl mysortproc(void *p1, void *p2)

{

unsigned long **pp1 = (unsigned long **)p1;

unsigned long **pp2 = (unsigned long **)p2;

if(**pp1 < **pp2)

return(-1);

else if(**pp1 > *pp2)

return(1);

return(0);

}

...

int i1;

unsigned long *aprandom[256];

unsigned long arandom[256]; // same array as before, in this case

int aresult[256]; // results go here

for(i1=0; i1 < 256; i1++)

{

aprandom[i1] = arandom + i1;

}

// now sort it

qsort(aprandom, 256, sizeof(*aprandom), mysortproc);

// final step - offsets for pointers are placed into output array

for(i1=0; i1 < 256; i1++)

{

aresult[i1] = (int)(aprandom[i1] - arandom);

}

...

變數'aresult'中的值應該是一個排過序的唯一的一系列的整數的數組，整數的值的范圍均在0到255之間。這樣一個數組是非常有用的，例如：對一個位元組對位元組的轉換表，就可以很容易並且非常可靠的來產生一個短的密鑰（經常作為一些隨機數的種子）。這樣一個表還有其他的用處，比如說：來產生一個隨機的字元，計算機游戲中一個物體的隨機的位置等等。上面的例子就其本身而言並沒有構成一個加密演算法，只是加密演算法一個組成部分。

作為一個測試，開發了一個應用程序來測試上面所描述的加密演算法。程序本身都經過了幾次的優化和修改，來提高隨機數的真正的隨機性和防止會產生一些短的可重復的用於加密的隨機數。用這個程序來加密一個文件，破解這個文件可能會需要非常巨大的時間以至於在現實上是不可能的。

四．結論：

由於在現實生活中，我們要確保一些敏感的數據只能被有相應許可權的人看到，要確保信息在傳輸的過程中不會被篡改，截取，這就需要很多的安全系統大量的應用於政府、大公司以及個人系統。數據加密是肯定可以被破解的，但我們所想要的是一個特定時期的安全，也就是說，密文的破解應該是足夠的困難，在現實上是不可能的，尤其是短時間內。