資源描述：
《RSA公鑰密碼體制簡介》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、1公鑰密碼技術(shù)2RSA公鑰密碼算法主要內(nèi)容：RSA公鑰密碼算法，RSA公鑰密碼的實現(xiàn)。重點：RSA算法，脫密的快速實現(xiàn)，素數(shù)生成算法。難點：素數(shù)生成算法。3RSA體制由Rivest、Shamir、Adleman于1978年首次發(fā)表；最容易理解和實現(xiàn)的公鑰算法;經(jīng)受住了多年深入的攻擊;其理論基礎(chǔ)是一種特殊的可逆模冪運算，其安全性基于分解大整數(shù)的困難性；RSA既可用于加密，又可用于數(shù)字簽名，已得到廣泛采用；RSA已被許多標(biāo)準(zhǔn)化組織(如ISO、ITU、IETF和SWIFT等)接納；目前許多國家標(biāo)準(zhǔn)仍采用RSA或它的變型4假設(shè)m為要傳送的報
2、文。1、任產(chǎn)生兩個素數(shù)p與q，使得n=pq>m2、隨機選擇數(shù)e：e與(p-1)(q-1)互素3、用輾轉(zhuǎn)相除法求d：ed=1mod(p-1)(q-1)4、公開：（e，n），保密：d加密過程：c=memodn解密過程：m=cdmodn一、RSA算法1、RSA算法描述5定義：任給一個正整數(shù)m，如果用m去除任意兩個整數(shù)a、b所得的余數(shù)相同，稱a、b對模m同余。記為：，若余數(shù)不同，則a、b對模m不同余。記為：。定理：，當(dāng)且僅當(dāng)m
3、(a-b)。定理：歐拉定理，對任意有推論:費爾馬定理，若p為素數(shù)，則其中2、工作原理6RSA算法論證①E和D的可逆
4、性要證明：D(E(M))=MM＝Cd＝(Me)d＝Medmodn因為ed＝1modφ(n)，這說明ed＝tφ(n)+1,其中t為某整數(shù)。所以,Med＝Mtφ(n)+1modn。因此要證明Med＝Mmodn，只需證明Mtφ(n)+1＝Mmodn。7RSA算法論證在（M，n）＝1的情況下，根據(jù)數(shù)論(Euler定理)，Mtφ(n)＝1modn，于是有，Mtφ(n)+1＝Mmodn。8RSA算法論證在（M，n）≠1的情況下，分兩種情況：第一種情況：M∈{1,2,3,…,n-1}因為n=pq，p和q為素數(shù)，M∈{1,2,3,…,n-1}，且（
5、M，n）≠1。這說明M必含p或q之一為其因子，而且不能同時包含兩者，否則將有M≥n，與M∈{1,2,3,…,n-1}矛盾。9RSA算法論證10RSA算法論證不妨設(shè)M＝ap。又因q為素數(shù)，且M不包含q，故有（M，q）＝1，于是有，Mφ(q)＝1modq。進(jìn)一步有，Mt(p-1)φ(q)＝1modq。因為q是素數(shù)，φ(q)＝（q-1），所以t(p-1)φ(q)＝tφ(n)，所以有Mtφ(n)＝1modq。11于是，Mtφ(n)＝bq+1，其中b為某整數(shù)。兩邊同乘M，Mtφ(n)+1＝bqM+M。因為M＝ap，故Mtφ(n)+1＝bqap
6、+M=abn+M。取模n得，Mφ(n)+1＝Mmodn。RSA算法論證12第二種情況：M＝0當(dāng)M＝0時，直接驗證，可知命題成立。RSA算法論證13RSA算法論證②加密和解密運算的可交換性D(E(M))=(Me)d=Med=(Md))e=E(D(M))modn所以，RSA密碼可同時確保數(shù)據(jù)的秘密性和數(shù)據(jù)的真實性。14RSA算法論證③加解密算法的有效性RSA密碼的加解密運算是模冪運算，有比較有效的算法。15RSA算法論證④在計算上由公開密鑰不能求出解密鑰小合數(shù)的因子分解是容易的，然而大合數(shù)的因子分解卻是十分困難的。關(guān)于大合數(shù)的因子分解的
7、時間復(fù)雜度下限目前尚沒有一般的結(jié)果，迄今為止的各種因子分解算法提示人們這一時間下限將不低于O（EXP（lnNlnlnN）1/2）。根據(jù)這一結(jié)論，只要合數(shù)足夠大，進(jìn)行因子分解是相當(dāng)困難的。16RSA算法論證假設(shè)截獲密文C，從中求出明文M。他知道M≡Cdmodn，因為n是公開的，要從C中求出明文M，必須先求出d，而d是保密的。但他知道，ed≡1modφ(n)，e是公開的，要從中求出d，必須先求出φ(n)，而φ(n)是保密的。但他又知道，φ(n)=(p-1)(q-1)，17要從中求出φ(n)，必須先求出p和q，而p和q是保密的。但他知道，
8、n=pq，要從n求出p和q，只有對n進(jìn)行因子分解。而當(dāng)n足夠大時，這是很困難的。RSA算法論證只要能對n進(jìn)行因子分解，便可攻破RSA密碼。由此可以得出，破譯RSA密碼的困難性≤對n因子分解的困難性。目前尚不能證明兩者是否能確切相等，因為不能確知除了對n進(jìn)行因子分解的方法外，是否還有別的更簡捷的破譯方法。183、例子：假設(shè)RSA體制中p=3,q=11,取加密密鑰e=7.(1)求脫密密鑰d;(2)寫出相應(yīng)的加密算法和脫密算法;(3)對明文m=8加密。7dmod20=1因e=7與互素,故可解模方程，即解:此時n＝p×q＝33，且得到d＝3
9、。19故RSA體制明、密文空間:Z/(33)加密密鑰：(e,n)=(7,33)脫密密鑰：(d,p,q)=(3,3,11)加密算法:c＝m7mod33脫密算法:m＝c3mod33對明文m＝8加密，得:c＝87mod33=220二、RSA
