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

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

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

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

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

隨機(jī)選擇兩個(gè)大素?cái)?shù)p,q

計(jì)算n=p×q計(jì)算秘密的歐拉函數(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.加密過程加密時(shí)明文以分組為單位進(jìn)行加密，每個(gè)分組m的二進(jìn)制值均小于n，對(duì)明文分組m作加密運(yùn)算：c=memodn,且0≤m<n3．解密過程密文解密m=cd

modn

4.簽名過程計(jì)算簽名s=mdmodn5．簽名驗(yàn)證過程簽名驗(yàn)證m=se

modn2023/6/914例選擇素?cái)?shù)：p=47和q=71。計(jì)算

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實(shí)例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)行類似計(jì)算，可得到最終密文為

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

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

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

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

r/grx=Mgxr/gxr

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

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

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

=5058=75mod97?Bob計(jì)算W-1=22mod97?Bob恢復(fù)明文M=31.22=3mod972023/6/924ElGamal方法具有以下優(yōu)點(diǎn)：(1)系統(tǒng)不需要保存秘密參數(shù)，所有的系統(tǒng)參數(shù)均可公開；(2)同一個(gè)明文在不同的時(shí)間由相同加密者加密會(huì)產(chǎn)生不同的密文；但ElGamal方法的計(jì)算復(fù)雜度比RSA方法要大。2023/6/925Diffie-Hellman密鑰交換取一素?cái)?shù)p≈2180,兩個(gè)參數(shù)a,b,得到Ep(a,b).取Ep(a,b)的一個(gè)生成元G(x1,y1),要求G的階是一個(gè)非常大的素?cái)?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兩個(gè)通信主體Alice&Bob,希望在公開信道上建立密鑰初始化:選擇一個(gè)大素?cái)?shù)p(~200digits)一個(gè)生成元aAlice選擇一個(gè)秘密密鑰xA<p)Bob選擇一個(gè)秘密密鑰鑰xB<pAliceandBob計(jì)算他們的公開密鑰:yA=axAmodpyB=axBmodpAlice,Bob分別公開yA,yB2023/6/927Bob計(jì)算共享會(huì)話密鑰:KAB=(yA)^xBmodpAlice計(jì)算共享密鑰KAB=(yB)^xAmodpKAB可以用于對(duì)稱加密密鑰2023/6/928

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

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

x<n1y2=x3modn2

x<