信息安全認(rèn)證課件 第四章 公鑰密碼技術(shù)

第四章公鑰密碼2023/6/92公鑰密碼公鑰密碼體制的基本概念RSA算法ElGamal密碼Diffie-Hellman密鑰交換

2023/6/93Diffie和Hellmna于1976年在《密碼學(xué)的新方向》中首次提出了公鑰密碼的觀點，標(biāo)志著公鑰密碼學(xué)研究的開始1977年由Rviest，Shmair和Adlmena提出了第一個比較完善的公鑰密碼算法，即RSA算法。2023/6/94、

A.Shamir,R.Revist,L.Adleman,R.Merkle,M.Hellman,W.Diffie2023/6/95公鑰密碼體制

公鑰密碼算法是基于數(shù)學(xué)函數(shù)（如單向陷門函數(shù)）而不是基于代換和置換公鑰密碼是非對稱的，它使用兩個獨立的密鑰，即公鑰和私鑰，任何一個都可以用來加密，另一個用來解密公鑰可以被任何人知道，用于加密消息以及驗證簽名；私鑰僅僅自己知道的，用于解密消息和簽名加密和解密會使用兩把不同的密鑰，因此稱為非對稱2023/6/96一個公鑰密碼體制有6個部分構(gòu)成：明文，加密算法，公鑰和私鑰，密文，解密算法在加密模型中，發(fā)送方用接收方的公鑰作為加密密鑰，用接收方私鑰作解密密鑰，由于該私鑰只有接收方擁有，因此即只有接收者才能解密密文得到明文2023/6/97消息加密算法解密算法消息MMC攻擊者接收方B發(fā)送方A密鑰源PRBPUB圖4.1公鑰加密模型公鑰加密模型2023/6/98公鑰密碼系統(tǒng)滿足的要求同一算法用于加密和解密，但加密和解密使用不同的密鑰。兩個密鑰中的任何一個都可用來加密，另一個用來解密，加密和解密次序可以交換。產(chǎn)生一對密鑰（公鑰和私鑰）在計算上是可行的已知公鑰和明文，產(chǎn)生密文在計算上是容易的。接收方利用私鑰來解密密文在計算上是可行的。僅根據(jù)密碼算法和公鑰來確定私鑰在計算上不可行已知公鑰和密文，在不知道私鑰的情況下，恢復(fù)明文在計算上是不可行的。2023/6/99上面要求的實質(zhì)是要找一個單向陷門函數(shù)單向函數(shù)指計算函數(shù)值是容易的，而計算函數(shù)的逆是不可行的陷門單向函數(shù)則存在一個附加信息，當(dāng)不知道該附加信息時，從函數(shù)逆是困難的，但當(dāng)知道該附加信息時，求函數(shù)逆就變得容易了通常把附加信息稱為陷門信息，陷門信息作為私鑰，公鑰密碼體制就是基于這一原理而設(shè)計的其安全強度取決于它所依據(jù)的問題的計算復(fù)雜度。2023/6/910RSA算法

RSAAlgorithm2023/6/911RSA的安全性|p-q|要大p-1,q-1都應(yīng)有大的素因子。e<n且d<n1/4,則d能被容易的確定。2023/6/912算法描述

1.密鑰的產(chǎn)生

隨機選擇兩個大素數(shù)p,q

計算n=p×q計算秘密的歐拉函數(shù)(n)=(p-1)(q-1)選擇e使得1<e<(n)，且gcd(e,

(n))=1解下列方程求出d

ed≡1mod(n)，且0≤d≤n

公開公鑰：PU={e,N}保存私鑰：PR={d,p,q}2023/6/9132.加密過程加密時明文以分組為單位進(jìn)行加密，每個分組m的二進(jìn)制值均小于n，對明文分組m作加密運算：c=memodn,且0≤m<n3．解密過程密文解密m=cd

modn

4.簽名過程計算簽名s=mdmodn5．簽名驗證過程簽名驗證m=se

modn2023/6/914例選擇素數(shù)：p=47和q=71。計算

n=pq=47×71=3337，

(n)=(p–1)(q-1)=46×70=3220。選擇e：使gcd(e,3220)=1，選取e=79；決定d：de≡1mod3220，得d=1019公開公鑰

{79,3337}，保存私鑰{1019,47,71}；RSA實例2023/6/915假設(shè)消息為M=6882326879666683，進(jìn)行分組，分組的位數(shù)比n要小，我們選取M1

=688，M2=232，M3=687，M4=966，M5=668，M6=003。M1的密文為C1=68879mod3337=1570，繼續(xù)進(jìn)行類似計算，可得到最終密文為

C=1570275620912276158解密時計算M1=15701019mod3337=688，類似可以求出其他明文。2023/6/916RSA算法的安全性

RSA密碼體制的安全性是基于分解大整數(shù)的困難性假設(shè)RSA算法的加密函數(shù)c=memodn是一個單向函數(shù)，所以對于攻擊者來說，試圖解密密文是計算上不可行的對于接收方解密密文的陷門是分解n=pq，由于接收方知道這個分解，他可以計算

(n)=(p-1)(q-1)，然后用擴展歐幾里德算法來計算解密私鑰d。2023/6/917對RSA算法的攻擊有下面幾個方法：窮舉攻擊，數(shù)學(xué)攻擊，選擇密文攻擊，公共模數(shù)攻擊等最基本的攻擊是窮舉攻擊，也就是嘗試所有可能的私鑰數(shù)學(xué)攻擊的實質(zhì)是試圖對兩個素數(shù)乘積的分解2023/6/918ElGamal密碼

ElGamal是1985年由T.EIGamal提出的一個著名的公鑰密碼算法該算法既能用于數(shù)據(jù)加密也能用于數(shù)字簽名其安全性是依賴于計算有限域上離散對數(shù)這一難題2023/6/9191.密鑰產(chǎn)生任選一個大素數(shù)p，使得p-1有大素因子，g是模p的一個本原根，公開p與g。使用者任選一私鑰x，x∈[0,p-1]計算公鑰公開公鑰：y,p,g保密私鑰：x2023/6/9202.加密過程對于明文m，選取一個r，r∈[0,p-1]計算則密文為3.解密過程先計算再計算出明文證明M=C2/C1x=My

r/grx=Mgxr/gxr

modp=MMODP2023/6/921ElGamal實例選擇p=97及本原根a=5?Bob選擇秘密鑰xB=58

計算并發(fā)布公鑰yB=558mod97=44mod972023/6/922Alice要加密M=3toBob?首先得到Bob的公開密鑰yB=44選擇隨機k=36計算:yBK=4436mod97

=75mod97?計算密文對:?C1=536=50mod97?C2=75.3mod97=31mod97?發(fā)送{50,31}toBob2023/6/923Bob解密，私鑰XB=58W=C1XB

=5058=75mod97?Bob計算W-1=22mod97?Bob恢復(fù)明文M=31.22=3mod972023/6/924ElGamal方法具有以下優(yōu)點：(1)系統(tǒng)不需要保存秘密參數(shù)，所有的系統(tǒng)參數(shù)均可公開；(2)同一個明文在不同的時間由相同加密者加密會產(chǎn)生不同的密文；但ElGamal方法的計算復(fù)雜度比RSA方法要大。2023/6/925Diffie-Hellman密鑰交換取一素數(shù)p≈2180,兩個參數(shù)a,b,得到Ep(a,b).取Ep(a,b)的一個生成元G(x1,y1),要求G的階是一個非常大的素數(shù)。(階是滿足nG=O的最小正整數(shù)n).Ep(a,b)和G公開，A和B密鑰交換過程如下A選小于n的整數(shù)nA作為秘密鑰，并有PA=nAG作為公鑰B類似選取自己的秘密鑰nB和公開鑰PBA和B分別由K=nAPB和K＝nBPA產(chǎn)生共享的秘密鑰攻擊者如想獲得K，必須由PA和G求出nA或PB和G求出nB2023/6/926兩個通信主體Alice&Bob,希望在公開信道上建立密鑰初始化:選擇一個大素數(shù)p(~200digits)一個生成元aAlice選擇一個秘密密鑰xA<p)Bob選擇一個秘密密鑰鑰xB<pAliceandBob計算他們的公開密鑰:yA=axAmodpyB=axBmodpAlice,Bob分別公開yA,yB2023/6/927Bob計算共享會話密鑰:KAB=(yA)^xBmodpAlice計算共享密鑰KAB=(yB)^xAmodpKAB可以用于對稱加密密鑰2023/6/928

DH算法實例選取素數(shù)p=97,及本根a=5Alice選取秘密xA=36計算公鑰yA=536mod97=50mod97Bob選取秘密xB=58計算公鑰yB=558mod97=44mod97AliceandBob交換公鑰(50&44)Alice計算共享密鑰K=4436=75mod97Bob計算共享密鑰K=5058=75mod972023/6/929對RSA的攻擊－共模攻擊每一用戶有相同的模數(shù)n設(shè)用戶的公開密鑰分別為e1,e2,且e1,e2互素，明文消息為m,密文為因為（e1,e2)=1,用歐幾里德算法可求re1+se2=1假定r為負(fù)數(shù)，從而可知由Euclidean算法可計算(c1-1)r

c2s=mmodn2023/6/930對RSA的攻擊－低指數(shù)攻擊令網(wǎng)中三用戶的加密鑰e均選3，而有不同的模n1,n2,n3，若有一用戶將消息x傳給三個用戶的密文分別為y1=x3modn1

x<n1y2=x3modn2

x<