RSA和Rabin算法(上)課件

第七講RSA和Rabin算法(上)第七講RSA和Rabin算法(上)1Diffie和Hellman提出了建立公鑰密碼系統(tǒng)的可能性。但是，他們并沒有提出公鑰密碼算法。接下來的幾年，一些公鑰密碼算法相繼被提出。其中最為成功的依賴大整數(shù)分解困難性的公鑰密碼算法于1977年由Rivest，Shamir，和Adleman提出。這也就是我們熟知的RSA算法。Diffie和Hellman提出了建立公鑰密碼系統(tǒng)的2

雖然經(jīng)過長期的密碼分析并不能證明也不能否定RSA的安全，但是這也無疑給算法的安全性一定承諾。Rabin提出了一個(gè)基于計(jì)算模合數(shù)平方根困難的公鑰密碼算法。Rabin的工作在理論上具有重要價(jià)值，這是因?yàn)镽abin算法的安全性等價(jià)于大整數(shù)分解困難問題。雖然經(jīng)過長期的密碼分析并不能證明也不能否定RSA的安全3

攻擊者攻擊公鑰密碼系統(tǒng)的基本目標(biāo)是針對特定實(shí)體可以系統(tǒng)的從密文消息恢復(fù)出明文消息。如果能實(shí)現(xiàn)這一目標(biāo)，就說公鑰密碼系統(tǒng)被破譯。一個(gè)更具破壞性的目標(biāo)是恢復(fù)出秘密密鑰。

可以想到的攻擊是選擇密文攻擊，也就是攻擊者選擇密文消息，之后以某種手段得到其所對應(yīng)的明文消息。

(1)(冷漠)選擇密文攻擊。(2)適應(yīng)性選擇密文攻擊。攻擊者攻擊公鑰密碼系統(tǒng)的基本目標(biāo)是針對特定實(shí)體可以系4

注意這里講到的公鑰密碼算法都是假定發(fā)送消息者已經(jīng)得到接受者一份真實(shí)的公開密鑰拷貝?，F(xiàn)實(shí)中有許多技術(shù)保障真實(shí)公開密鑰分配，包括：在可信信道上交換密鑰，使用可信公開文件，使用在線可信服務(wù)器或使用離線服務(wù)器和證書。注意這里講到的公鑰密碼算法都是假定發(fā)送消息者已經(jīng)得到5

這一講的公鑰密碼方案假定明文消息都是以某個(gè)固定比特長度被加密。如果消息明文的長度超過規(guī)定長度，需要將其按規(guī)定長度分組。為了提供對非法控制分組(例如，重新排序)的防護(hù)，可以使用密碼分組鏈接(CBC)模式。這一講的公鑰密碼方案假定明文消息都是以某個(gè)固定比特長6本講提要RSA加密算法RSA加密的執(zhí)行RSA加密的安全本講提要RSA加密算法71RSA加密算法1.1加密1RSA加密算法1.1加密81.1加密(續(xù))1.1加密(續(xù))91.1加密(續(xù))1.1加密(續(xù))101.1加密(續(xù))1.1加密(續(xù))11

1.1加密(續(xù))

1.1加密(續(xù))121.2例子1.2例子132RSA加密的執(zhí)行2.1素性測試

存在一個(gè)奇妙的事實(shí)，就是分解大整數(shù)雖然十分困難但測試整數(shù)的素性并不困難。也就是說證明一個(gè)數(shù)為合數(shù)要比分解它容易的多。我們知道很多大整數(shù)是合數(shù)但卻并不能分解它們。2RSA加密的執(zhí)行2.1素性測試14

2.1素性測試(續(xù))2.1素性測試(續(xù))152.2模冪2.2模冪163RSA加密的安全3.1安全參數(shù)，dp，q3RSA加密的安全3.1安全參數(shù)，dp，q173.1安全參數(shù)，dp，q(續(xù))3.1安全參數(shù)，dp，q(續(xù))183.2關(guān)于整數(shù)分解3.2關(guān)于整數(shù)分解193.2.1指數(shù)分解方法3.2.1指數(shù)分解方法203.2.1指數(shù)分解方法(續(xù))3.2.1指數(shù)分解方法(續(xù))213.2.1指數(shù)分解方法(續(xù))3.2.1指數(shù)分解方法(續(xù))223.2.1指數(shù)分解方法(續(xù))3.2.1指數(shù)分解方法(續(xù))233.2.2Pollard的p-1算法3.2.2Pollard的p-1算法243.2.2Pollard的p-1算法(續(xù))3.2.2Pollard的p-1算法(續(xù))253.2.2Pollard的p-1算法(續(xù))3.2.2Pollard的p-1算法(續(xù))263.2.2Pollard的p-1算法(續(xù))3.2.2Pollard的p-1算法(續(xù))273.2.3二次域篩法3.2.3二次域篩法283.2.3二次域篩法(續(xù))3.2.3二次域篩法(續(xù))293.2.4整數(shù)分解的進(jìn)展3.2.4整數(shù)分解的進(jìn)展303.3小加密指數(shù)e3.3小加密指數(shù)e313.3小加密指數(shù)e(續(xù))3.3小加密指數(shù)e(續(xù))323.4小解密指數(shù)d3.4小解密指數(shù)d333.5乘法特性3.5乘法特性343.5乘法特性(續(xù))3.5乘法特性(續(xù))353.5乘法特性(續(xù))3.5乘法特性(續(xù))363.6共模攻擊3.6共模攻擊373.7部分密鑰泄露攻擊3.7部分密鑰泄露攻擊383.7部分密鑰泄露攻擊(續(xù))3.7部分密鑰泄露攻擊(續(xù))39謝謝!謝謝!40第七講RSA和Rabin算法(上)第七講RSA和Rabin算法(上)41Diffie和Hellman提出了建立公鑰密碼系統(tǒng)的可能性。但是，他們并沒有提出公鑰密碼算法。接下來的幾年，一些公鑰密碼算法相繼被提出。其中最為成功的依賴大整數(shù)分解困難性的公鑰密碼算法于1977年由Rivest，Shamir，和Adleman提出。這也就是我們熟知的RSA算法。Diffie和Hellman提出了建立公鑰密碼系統(tǒng)的42

雖然經(jīng)過長期的密碼分析并不能證明也不能否定RSA的安全，但是這也無疑給算法的安全性一定承諾。Rabin提出了一個(gè)基于計(jì)算模合數(shù)平方根困難的公鑰密碼算法。Rabin的工作在理論上具有重要價(jià)值，這是因?yàn)镽abin算法的安全性等價(jià)于大整數(shù)分解困難問題。雖然經(jīng)過長期的密碼分析并不能證明也不能否定RSA的安全43

攻擊者攻擊公鑰密碼系統(tǒng)的基本目標(biāo)是針對特定實(shí)體可以系統(tǒng)的從密文消息恢復(fù)出明文消息。如果能實(shí)現(xiàn)這一目標(biāo)，就說公鑰密碼系統(tǒng)被破譯。一個(gè)更具破壞性的目標(biāo)是恢復(fù)出秘密密鑰。

可以想到的攻擊是選擇密文攻擊，也就是攻擊者選擇密文消息，之后以某種手段得到其所對應(yīng)的明文消息。

(1)(冷漠)選擇密文攻擊。(2)適應(yīng)性選擇密文攻擊。攻擊者攻擊公鑰密碼系統(tǒng)的基本目標(biāo)是針對特定實(shí)體可以系44

注意這里講到的公鑰密碼算法都是假定發(fā)送消息者已經(jīng)得到接受者一份真實(shí)的公開密鑰拷貝?，F(xiàn)實(shí)中有許多技術(shù)保障真實(shí)公開密鑰分配，包括：在可信信道上交換密鑰，使用可信公開文件，使用在線可信服務(wù)器或使用離線服務(wù)器和證書。注意這里講到的公鑰密碼算法都是假定發(fā)送消息者已經(jīng)得到45

這一講的公鑰密碼方案假定明文消息都是以某個(gè)固定比特長度被加密。如果消息明文的長度超過規(guī)定長度，需要將其按規(guī)定長度分組。為了提供對非法控制分組(例如，重新排序)的防護(hù)，可以使用密碼分組鏈接(CBC)模式。這一講的公鑰密碼方案假定明文消息都是以某個(gè)固定比特長46本講提要RSA加密算法RSA加密的執(zhí)行RSA加密的安全本講提要RSA加密算法471RSA加密算法1.1加密1RSA加密算法1.1加密481.1加密(續(xù))1.1加密(續(xù))491.1加密(續(xù))1.1加密(續(xù))501.1加密(續(xù))1.1加密(續(xù))51

1.1加密(續(xù))

1.1加密(續(xù))521.2例子1.2例子532RSA加密的執(zhí)行2.1素性測試

存在一個(gè)奇妙的事實(shí)，就是分解大整數(shù)雖然十分困難但測試整數(shù)的素性并不困難。也就是說證明一個(gè)數(shù)為合數(shù)要比分解它容易的多。我們知道很多大整數(shù)是合數(shù)但卻并不能分解它們。2RSA加密的執(zhí)行2.1素性測試54

2.1素性測試(續(xù))2.1素性測試(續(xù))552.2模冪2.2模冪563RSA加密的安全3.1安全參數(shù)，dp，q3RSA加密的安全3.1安全參數(shù)，dp，q573.1安全參數(shù)，dp，q(續(xù))3.1安全參數(shù)，dp，q(續(xù))583.2關(guān)于整數(shù)分解3.2關(guān)于整數(shù)分解593.2.1指數(shù)分解方法3.2.1指數(shù)分解方法603.2.1指數(shù)分解方法(續(xù))3.2.1指數(shù)分解方法(續(xù))613.2.1指數(shù)分解方法(續(xù))3.2.1指數(shù)分解方法(續(xù))623.2.1指數(shù)分解方法(續(xù))3.2.1指數(shù)分解方法(續(xù))633.2.2Pollard的p-1算法3.2.2Pollard的p-1算法643.2.2Pollard的p-1算法(續(xù))3.2.2Pollard的p-1算法(續(xù))653.2.2Pollard的p-1算法(續(xù))3.2.2Pollard的p-1算法(續(xù))663.2.2Pollard的p-1算法(續(xù))3.2.2Pollard的p-1算法(續(xù))673.2.3二次域篩法3.2.3二次域篩法683.2.3二次域篩法(續(xù))3.2.3二次域篩法(續(xù))693.2.4整數(shù)分解的進(jìn)展3.2.4整數(shù)分解的進(jìn)展703.3小加密指數(shù)e3.3小加密指數(shù)e713.3小加密指數(shù)e(續(xù))3.3小加密指數(shù)e(續(xù))72