1978年 rsa加密算法是最常用非對稱加密算法

《1978年 rsa加密算法是最常用非對稱加密算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、1978年　　RSA加密算法是最常用的非對稱加密算法，CFCA在證書服務(wù)中離不了它。但是有不少新來的同事對它不太了解，恰好看到一本書中作者用實例對它進(jìn)行了簡化而生動的描述，使得高深的數(shù)學(xué)理論能夠被容易地理解。我們經(jīng)過整理和改寫特別推薦給大家閱讀，希望能夠?qū)r間緊張但是又想了解它的同事有所幫助?！　SA是第一個比較完善的公開密鑰算法，它既能用于加密，也能用于數(shù)字簽名。RSA以它的三個發(fā)明者RonRivest,AdiShamir,LeonardAdleman的名字首字母命名，這個算法經(jīng)受住了多年深入的密碼分析，雖然密碼分析者既不能證明也不能否定RSA的安全性，但這恰恰說明該算法有一定的可

2、信性，目前它已經(jīng)成為最流行的公開密鑰算法?！　SA的安全基于大數(shù)分解的難度。其公鑰和私鑰是一對大素數(shù)（100到200位十進(jìn)制數(shù)或更大）的函數(shù)。從一個公鑰和密文恢復(fù)出明文的難度，等價于分解兩個大素數(shù)之積（這是公認(rèn)的數(shù)學(xué)難題）?！　SA的公鑰、私鑰的組成，以及加密、解密的公式可見于下表：　　可能各位同事好久沒有接觸數(shù)學(xué)了，看了這些公式不免一頭霧水。別急，在沒有正式講解RSA加密算法以前，讓我們先復(fù)習(xí)一下數(shù)學(xué)上的幾個基本概念，它們在后面的介紹中要用到：一、什么是“素數(shù)”？　　素數(shù)是這樣的整數(shù)，它除了能表示為它自己和1的乘積以外，不能表示為任何其它兩個整數(shù)的乘積。例如，15＝3＊5，所以1

3、5不是素數(shù)；又如，12＝6＊2＝4＊3，所以12也不是素數(shù)。另一方面，13除了等于13＊1以外，不能表示為其它任何兩個整數(shù)的乘積，所以13是一個素數(shù)。素數(shù)也稱為“質(zhì)數(shù)”。二、什么是“互質(zhì)數(shù)”（或“互素數(shù)”）？　　小學(xué)數(shù)學(xué)教材對互質(zhì)數(shù)是這樣定義的：“公約數(shù)只有1的兩個數(shù)，叫做互質(zhì)數(shù)?！边@里所說的“兩個數(shù)”是指自然數(shù)?！　∨袆e方法主要有以下幾種（不限于此）：（1）兩個質(zhì)數(shù)一定是互質(zhì)數(shù)。例如，2與7、13與19。（2）一個質(zhì)數(shù)如果不能整除另一個合數(shù)，這兩個數(shù)為互質(zhì)數(shù)。例如，3與10、5與26。（3）1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個自然數(shù)在一起都是互質(zhì)數(shù)。如1和9908。（4）相鄰的兩個自然

4、數(shù)是互質(zhì)數(shù)。如15與16。（5）相鄰的兩個奇數(shù)是互質(zhì)數(shù)。如49與51。（6）大數(shù)是質(zhì)數(shù)的兩個數(shù)是互質(zhì)數(shù)。如97與88。（7）小數(shù)是質(zhì)數(shù)，大數(shù)不是小數(shù)的倍數(shù)的兩個數(shù)是互質(zhì)數(shù)。如7和16。（8）兩個數(shù)都是合數(shù)（二數(shù)差又較大），小數(shù)所有的質(zhì)因數(shù)，都不是大數(shù)的約數(shù)，這兩個數(shù)是互質(zhì)數(shù)。如357與715，357=3×7×17，而3、7和17都不是715的約數(shù)，這兩個數(shù)為互質(zhì)數(shù)。等等。三、什么是模指數(shù)運算？　　指數(shù)運算誰都懂，不必說了，先說說模運算。模運算是整數(shù)運算，有一個整數(shù)m，以n為模做模運算，即mmodn。怎樣做呢？讓m去被n整除，只取所得的余數(shù)作為結(jié)果，就叫做模運算。例如，10mod3=1；

5、26mod6=2；28mod2=0等等。　　模指數(shù)運算就是先做指數(shù)運算，取其結(jié)果再做模運算。如　　好，現(xiàn)在開始正式講解RSA加密算法。算法描述：（1）選擇一對不同的、足夠大的素數(shù)p，q。（2）計算n=pq。（3）計算f(n)=(p-1)(q-1)，同時對p,q嚴(yán)加保密，不讓任何人知道。（4）找一個與f(n)互質(zhì)的數(shù)e，且1

6、結(jié)果都等于1；符號的左邊d與e的乘積做模運算后的結(jié)果也必須等于1。這就需要計算出d的值，讓這個同余等式能夠成立。（6）公鑰KU=(e,n)，私鑰KR=(d,n)。（7）加密時，先將明文變換成0至n-1的一個整數(shù)M。若明文較長，可先分割成適當(dāng)?shù)慕M，然后再進(jìn)行交換。設(shè)密文為C，則加密過程為：。（8）解密過程為：。實例描述：　　在這篇科普小文章里，不可能對RSA算法的正確性作嚴(yán)格的數(shù)學(xué)證明，但我們可以通過一個簡單的例子來理解RSA的工作原理。為了便于計算。在以下實例中只選取小數(shù)值的素數(shù)p,q,以及e，假設(shè)用戶A需要將明文“key”通過RSA加密后傳遞給用戶B，過程如下：（1）設(shè)計公私密鑰(e

7、,n)和(d,n)。令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3與20互質(zhì)）則e×d≡1modf(n)，即3×d≡1mod20。d怎樣取值呢？可以用試算的辦法來尋找。試算結(jié)果見下表：　　通過試算我們找到，當(dāng)d=7時，e×d≡1modf(n)同余等式成立。因此，可令d=7。從而我們可以設(shè)計出一對公私密鑰，加密密鑰（公鑰）為：KU=(e,n)=(3,33)，解密密鑰（私鑰）為：K