第七講 RSA和Rabin算法(上)ppt課件

1、第七講 RSA和Rabin算法(上). Diffie和Hellman提出了建立公鑰密碼系統(tǒng)的能夠性。但是，他們并沒有提出公鑰密碼算法。接下來的幾年，一些公鑰密碼算法相繼被提出。其中最為勝利的依賴大整數(shù)分解困難性的公鑰密碼算法于1977年由Rivest，Shamir，和Adleman提出。這也就是我們熟知的RSA算法。. 雖然經(jīng)過長期的密碼分析并不能證明也不能否認RSA的平安，但是這也無疑給算法的平安性一定承諾。Rabin提出了一個基于計算模合數(shù)平方根困難的公鑰密碼算法。Rabin的任務(wù)在實際上具有重要價值，這是由于Rabin算法的平安性等價于大整數(shù)分解困難問題。. 攻擊者攻擊公鑰密碼系統(tǒng)的根本

2、目的是針對特定實體可以系統(tǒng)的從密文音訊恢復(fù)出明文音訊。假設(shè)能實現(xiàn)這一目的，就說公鑰密碼系統(tǒng)被破譯。一個更具破壞性的目的是恢復(fù)出密鑰。 可以想到的攻擊是選擇密文攻擊，也就是 攻擊者選擇密文音訊，之后以某種手段得到其所對應(yīng)的明文音訊。 (1) (冷漠)選擇密文攻擊。 (2) 順應(yīng)性選擇密文攻擊。. 留意這里講到的公鑰密碼算法都是假定發(fā)送音訊者曾經(jīng)得到接受者一份真實的公開密鑰拷貝。現(xiàn)實中有許多技術(shù)保證真實公開密鑰分配，包括：在可信信道上交換密鑰，運用可信公開文件，運用在線可信效力器或運用離線效力器和證書。. 這一講的公鑰密碼方案假定明文音訊都是以某個固定比專長度被加密。假設(shè)音訊明文的長度超越規(guī)定長度

3、，需求將其按規(guī)定長度分組。為了提供對非法控制分組(例如，重新排序)的防護，可以運用密碼分組鏈接(CBC)方式。.本講提要 RSA加密算法 RSA加密的執(zhí)行 RSA加密的平安.1 RSA加密算法1.1 加密.1.1 加密 (續(xù)).1.1 加密 (續(xù)).1.1 加密 (續(xù)).1.1 加密 (續(xù)).1.2 例子.2 RSA 加密的執(zhí)行 2.1 素性測試 存在一個奇妙的現(xiàn)實，就是分解大整數(shù)雖然非常困難但測試整數(shù)的素性并不困難。也就是說證明一個數(shù)為合數(shù)要比分解它容易的多。我們知道很多大整數(shù)是合數(shù)但卻并不能分解它們。. 2.1 素性測試 (續(xù)).2.2 模冪.3 RSA加密的平安3.1 平安參數(shù)，d p，q .3.1 平安參數(shù)，d p，q (續(xù)).3.2 關(guān)于整數(shù)分解.3.2.1 指數(shù)分解方法.3.2.1 指數(shù)分解方法 (續(xù)).3.2.1 指數(shù)分解方法 (續(xù)).3.2.1 指數(shù)分解方法 (續(xù)).3.2.2 Pollard的p-1算法.3.2.2 Pollard的p-1算法 (續(xù)).3.2.2 Pollard的p-1算法 (續(xù)).3.2.2 Pollard的p-1算法 (續(xù)).3.2.3 二次域篩法.3.2.3 二次域篩法 (續(xù)).3.2.4 整數(shù)分解的進展.3.3 小加密指數(shù) e.3.3 小加密指數(shù) e (續(xù)).3.4 小解密指數(shù)d.3.5 乘法特性.3.5 乘法特性