什么是RSA

RSA算法是應(yīng)用最廣泛的公鑰密碼算法。

1977年，RSA算法由MIT的羅納德 · 李維斯特（Ron Rivest）、阿迪 · 薩莫爾（Adi Shamir）和倫納德 · 阿德曼（Leonard Adleman）共同設(shè)計(jì)，于1978年正式發(fā)布，以他們?nèi)说氖鬃帜该?/p>

在這之前所用的對稱加密方式只采用一個密鑰，知道加密密鑰就可以知道解密密鑰。但是由于雙方需要事先約定加密的規(guī)則，就導(dǎo)致沒有辦法安全地交換密鑰，建立安全的傳遞通道。

但是1976年出現(xiàn)的非對稱加密算法的思想就可以解決密鑰的交換和存放問題。它使用兩個密鑰，一個用來加密消息和驗(yàn)證簽名，叫公鑰，另一個用來解密，叫私鑰，加解密雙方是不平等的。這種新的構(gòu)思是由美國計(jì)算機(jī)科學(xué)家Whitfield Diffie和Martin Hellman提出的，被稱為Diffie-Hellman密鑰交換算法，RSA算法就是受到它的啟發(fā)產(chǎn)生的，是這種構(gòu)思的具體實(shí)現(xiàn)方式，既可以用來加密，解密，也可以用于密鑰交換。

RSA主要使用大整數(shù)分解這個數(shù)學(xué)難題進(jìn)行設(shè)計(jì)，巧妙地利用了數(shù)論的概念。給了RSA公鑰，首先想到的攻擊就是分解模數(shù)，給了的因子攻擊者可以計(jì)算得到，從而也可以計(jì)算得到解密指數(shù)，我們稱這種分解模數(shù)的方法為針對RSA的暴力攻擊。雖然分解算法已經(jīng)穩(wěn)步改進(jìn)，但是在正確使用RSA情況下，當(dāng)前的技術(shù)水平仍遠(yuǎn)未對RSA的安全性構(gòu)成威脅。如今，只有短的 RSA 密鑰才有可能被強(qiáng)力方式解破。

目前，RSA部署在許多商業(yè)系統(tǒng)中。Web服務(wù)器和瀏覽器使用它來保護(hù)Web流量，它可以用于保障電子郵件的隱私和真實(shí)性，還可以用于保護(hù)遠(yuǎn)程登錄會話，同時它也是電子信用卡支付系統(tǒng)的核心。簡而言之，RSA常用于需要考慮數(shù)字?jǐn)?shù)據(jù)安全性的應(yīng)用中。

算法步驟

可以通過以下步驟生成一個公鑰/私鑰對：

1.隨計(jì)選擇兩個不相等的質(zhì)數(shù)p，q
2.計(jì)算它們的乘積N=p*q
3.計(jì)算歐拉函數(shù)φ(N)=(p-1)(q-1)，N的二進(jìn)制長度作為密鑰的長度，
4.隨機(jī)選擇一個加密密鑰e,這里1<e<φ(N),gcd(e,φ(N))=1
5.根據(jù)以下公式求解得到解密密鑰d
ed=1 mod φ(N)，0≤d≤N
6.發(fā)布加密密鑰：(e,N)
7.保密解密密鑰：(d,N)

實(shí)例

在實(shí)際應(yīng)用中e和N都是大整數(shù)，為了方便理解，下面選取非常小的整數(shù)來實(shí)現(xiàn)一次密鑰生成過程。

1.隨機(jī)選擇兩個質(zhì)數(shù)

p=17 ，q=11

2.計(jì)算它們的乘積

N=p*q=17×11=187

3.計(jì)算歐拉函數(shù)

φ(N)=(p-1)(q-1)=16×10=160

4.選擇e，e是與φ(N)互質(zhì)的整數(shù)，且1<e<φ(N)

e=7

5.決定d

d*e=1 mod φ(N)且d<φ(N)
23×7=160+1
d=23

6.得到公鑰(7,187)

7.得到私鑰(23,187)

用途

生成了公鑰和私鑰，就可以用來加密和解密了。

1.發(fā)送方加密消息M
拿到對方的公鑰e和N后，計(jì)算C = M^e mod N,這里0≤M<N,將C作為密文發(fā)送給接收方；
例如M=88，C=88^7 mod 187=11

2.接收方解密密文C
拿出自己的私鑰d和N，計(jì)算M=C^d mod N， 得到原消息M=11^23 mod 187=88

總結(jié)

以上是生活随笔為你收集整理的RSA简介的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。