第一章信息安全概述-RSA算法計(jì)算機(jī)系統(tǒng)與網(wǎng)絡(luò)安全技術(shù)

1977年由RonRivest、AdiShamir和LenAdleman發(fā)明，1978年公布。RSA算法的提出AdiShamirRonaldL.RivestLeonardM.Adleman為什么需要公鑰密碼體制第一章信息安全概述

公鑰：n（兩素?cái)?shù)p和q的乘積）和e（與(p-1)(q-1)互素）私密：d（ed1(mod(p-1)(q-1))加密c=memodn解密m=cdmodnRSA算法的描述RSA算法第一章信息安全概述

令n=pq,p

q都是素?cái)?shù),

(n)=(p-1)(q-1)是n的Euler數(shù)Euler定理推論:若n=pq,p

q都是素?cái)?shù),k是任意整數(shù),則mk(p-1)(q-1)+1

mmodn,對(duì)任意0

m

n只要選擇公鑰e,則私鑰d滿足ed=k

(n)+1,即

ed

1mod

(n)

de-1mod

(n)公鑰:KU={e,n},私鑰:KR={d,n}RSA算法密鑰的生成原理RSA算法第一章信息安全概述每個(gè)用戶生成一對(duì)密鑰（公鑰和私鑰）：（1）用戶選擇兩個(gè)大的隨機(jī)素?cái)?shù)

p,q

（2）計(jì)算N=p.q（3）計(jì)算n的歐拉數(shù)：

?(N)=(p-1)(q-1)

（4）隨機(jī)算則一個(gè)加密密鑰e：1<e<?(n),gcd(e,?(n))=1（5）解以下方程得到解密密鑰

d

：e.d=1mod?(n)and0≤d≤n

（6）加密消息M得到密文

C=MemodN（7）解密密文得到明文

M=CdmodN

使用RSA算法的過程RSA算法第一章信息安全概述算則兩個(gè)素?cái)?shù):p=17&q=11計(jì)算

n=pq=17×11=187計(jì)算?(n)=(p–1)(q-1)=16×10=160選擇e:gcd(e,160)=1;其中e=7計(jì)算d:de=1mod160andd<160

d=23

（因?yàn)?3×7=161=10×160+1）公布公鑰KU={7,187}保存私鑰KR={23,17,11}RSA算法示例RSA算法第一章信息安全概述如果待加密的消息M=88(注意：88<187)加密：C=887mod187=11

解密:M=1123mod187=88

RSA算法示例RSA算法第一章信息安全概述

若Bob選擇了p=101和q＝113那么，n=11413,

(n)=100×112＝11200然而11200＝26×52×7，一個(gè)正整數(shù)e能用作加密指數(shù)，當(dāng)且僅當(dāng)e不能被2，5，7所整除。假設(shè)Bob選擇了e=3533，那么用擴(kuò)展的Euclidean算法將求得：d=e-1

6597(mod11200),于是Bob的解密密鑰d=6597RSA算法示例RSA算法第一章信息安全概述

Bob在一個(gè)目錄中公開n=11413和e=3533現(xiàn)假設(shè)Alice想發(fā)送明文9726給Bob，她計(jì)算：97263533(mod11413)=5761，且在一個(gè)信道上發(fā)送密文5761。當(dāng)Bob接收到密文5761時(shí)，他用他的秘密解密指數(shù)（私鑰）d＝6597進(jìn)行解密：57616597（mod11413)=9726RSA算法示例RSA算法第一章信息安全概述理論：歐拉定理（Euler‘sTheorem）:a?(n)modN=1gcd(a,N)=1在RSA中有:N=p.q?(N)=(p-1)(q-1)

如果仔細(xì)選擇e&d使得對(duì)某些k有：

e.d=1+k.?(N)成立于是就有：

Cd=(Me)d=M1+k.?(N)=M1.(M?(N))q=M1.(1)q=M1=MmodN

RSA算法正確性證明RSA算法第一章信息安全概述RSA算法加密的安全性是基于加密函數(shù)ek(x)=xe(modn)是一個(gè)單向函數(shù)，所以對(duì)攻擊的人來說求逆計(jì)算不可行。而Bob能解密的陷門是分解n=pq，知

(n)=(p-1)(q-1)