數(shù)據(jù)加密與PKI應(yīng)用第6章公鑰加密算法公鑰加密算法的思想是由W.Difie和Hellman在1976年提出的。使用公鑰加密算法，加密和解密時使不同密鑰，即Ke≠Kd。用于加密的密鑰稱為公鑰，可以公開；用于解密的密鑰稱為私鑰，必須被所有者秘密保存。公鑰加密算法均基于數(shù)學(xué)難解問題，目前常用的數(shù)學(xué)難解問題有“大數(shù)分解”難題和“離散對數(shù)”難題。目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識別05046.4數(shù)字簽名與驗證

例如，{1,5}構(gòu)成模6的簡化剩余系；{1,2,3,4,5,6}構(gòu)成模7的簡化剩余系。簡化剩余定理設(shè)m是一個正整數(shù)，對任意正整數(shù)a，稱：

為模m的a的剩余類。若有m個整數(shù)r0,r1,...,rm，其中任意兩個數(shù)都不在同一個剩余類中，則r0,r1,...,rm叫作模m的一個完全剩余系。在模m的一個剩余類中，如果有一個數(shù)與m互素，那么這個剩余類中所有的數(shù)均與m互素。如果模m的一個剩余類中存在與m互素的數(shù)，則稱它是模m的一個簡化剩余類。在模m的所有簡化剩余類中，從每個類任取一個數(shù)組成的集合，叫作模m的一個簡化剩余系，也叫既約剩余系、縮系。

【例6-1】計算120的歐拉函數(shù)值。120=23·3·5，因此：歐拉函數(shù)

設(shè)m是一個正整數(shù)，稱m個整數(shù)0,1,…,m-1中與m互素的整數(shù)個數(shù)為歐拉函數(shù)，記作

(m)。歐拉函數(shù)具有下列性質(zhì)：

(1)若p為素數(shù)，則

(p)=p-1。

(2)若p和q為不同的素數(shù)，則

(p·q)=(p-1)·(q-1)=

(p)·

(q)。

定理6.1設(shè)正整數(shù)n的標(biāo)準分解式為：

則：歐拉定理

歐拉定理給出了模m的簡化剩余系中所有元素都具備的一個特性。

定理6.2（歐拉定理）設(shè)正整數(shù)m>1，如果整數(shù)a滿足gcd(a,m)=1，

則：中國剩余定理

定理6.3（中國剩余定理）設(shè)正整數(shù)m1,m2,...,mk兩兩互素，令：

則對任意整數(shù)a1,a2,...,ak，同余方程組：

有唯一解，即：其中：

【例6-2】按照中國剩余定理，計算“物不知數(shù)”問題。

(1)根據(jù)“物不知數(shù)”問題的定義，可知：a1=2,a2=3,a3=2，并且m1=3,m2=5,m3=7。

(2)計算：m=m1·m2·m3=105。

(3)計算：M1=35,M2=21,M3=15。

(4)計算：M1-1=2,M2-1=1,M3-1=1。

(5)根據(jù)中國剩余定理，得到：中國剩余定理原根與指數(shù)

設(shè)m,a為正整數(shù)，m>1,gcd(a,m)=1，稱使得：成立的最小正整數(shù)x為a模m的階，記作：

【例6-3】當(dāng)m=7，a分別為1,2,3,4,5,6時，計算a模m的階。

a模m的階如表6-1所示。

因為

(7)=6，所以

中最大的值是6。

如果

=

(m)，則稱a為模m的原根。

定理6.4（指數(shù)定理）設(shè)r是正整數(shù)m的一個原根，則

，

當(dāng)且僅當(dāng)

。

目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識別05046.4數(shù)字簽名與驗證2.加密

首先對明文進行比特串分組，使得每個分組對應(yīng)的十進制數(shù)小于n，然后依次對每個分組m進行加密，所有分組的密文構(gòu)成的序列即是原始消息的加密結(jié)果，即m滿足0<m<n，則加密算法為：RSA算法描述1.密鑰生成(1)選取兩個保密的大素數(shù)p和q。(2)計算

n=p·q，

(n)=(p-1)·(q-1)。其中

(n)是n的歐拉函數(shù)值。(3)隨機選取整數(shù)e，1<e<

(n)，滿足gcd(e,

(n))=1。(4)計算d，滿足(5)公鑰為(e,n)，私鑰為(d,n)。3.解密

對于密文c，解密算法為：對RSA算法的攻擊選擇密文攻擊計時攻擊數(shù)學(xué)攻擊窮舉攻擊對RSA算法的攻擊目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識別05046.4數(shù)字簽名與驗證2.加密首先對明文進行比特串分組，使得每個分組對應(yīng)的十進制數(shù)小于p，然后依次對每個分組m進行加密。對于明文分組，首先隨機選取一個整數(shù)k，1≤k≤p-2，然后計算：則密文c=(c1,c2)。ElGamal算法描述1.密鑰生成(1)選取大素數(shù)p，且要求p-1有大素數(shù)因子。是一個生成元。

是一個生成元。(2)隨機選取整數(shù)x，1≤x≤p-2，計算。(3)公鑰為y，私鑰為x。3.解密

為了解密一個密文c=(c1,c2)，計算：ElGamal的安全性

在ElGamal公鑰密碼體制中，。由公開參數(shù)g和y求解私鑰x需要求解離散對數(shù)問題。目前還沒有找到一個有效算法來求解有限域上的離散對數(shù)問題。因此，ElGamal公鑰密碼體制的安全性基于有限域上離散對數(shù)問題困難性。為了抵抗已知的攻擊，p應(yīng)該選取至少1024位以上的大素數(shù)，并且p-1至少應(yīng)該有一個長度不小于160比特的大的素因子。目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識別05046.4數(shù)字簽名與驗證RSA簽名算法1)RSA簽名算法

RSA算法公鑰為（e,n），私鑰為（d,n）。對于消息m（

），簽名為：2)RSA驗證算法

對于消息簽名對兒（m,s），如果有：RSA數(shù)字簽名安全分析

1)消息破譯

2)騙取仲裁簽名

3)騙取用戶簽名數(shù)字簽名標(biāo)準DSS1.參數(shù)與密鑰生成

(1)選取大素數(shù)p，滿足，其中512≤L≤1024且L是64的倍數(shù)。(2)選取大素數(shù)q，q是p-1的一個素因子且，即q是160位的素數(shù)且是p-1的素因子。(3)選取一個生成元，其中h是一個整數(shù)，滿足1<h<p-1并且

。(4)隨機選取整數(shù)x，0<x<q，計算。(5)p、q和g是公開參數(shù)，y為公鑰，x為私鑰。數(shù)字簽名標(biāo)準DSS2.簽名

對于消息m，首先隨機選取一個整數(shù)k，0<k<q，然后計算：r=f2(k,p,q,g)，

s=f1(h(m),k,x,r,q)，數(shù)字簽名標(biāo)準DSS3.驗證

對于消息簽名對兒（m,(r,s)），首先計算：w=f3(s,q)，

v=f4(y,q,g,h(m),w,r)，

然后驗證：v=r簽密1.參數(shù)與密鑰生成(1)選取大素數(shù)p和q，q為（p-1）的素因子。(2)g為乘法群中的一個q階元素。(3)H()是一個Hash函數(shù)。(4)E()和D()是對稱密碼體制中的一種加密和解密算法。(5)xs是簽密方的私鑰，1<xs<q；ys是簽密方的公鑰，。xv是驗證方的私鑰，1<xv<q；yv是驗證方的公鑰。

保密性和認證性是當(dāng)代密碼系統(tǒng)最主要的兩個安全目標(biāo)，如果需要同時實現(xiàn)保密性和認證性，那么可以采用“先簽名，再加密”的方式。這種方式相當(dāng)于兩種運算“串連”在一起，其運算代價是兩種運算之和。

1997年，Y.Zheng首次提出了“簽密”的概念，在一個邏輯步驟內(nèi)，同時完成認證和加密運算，從而提高整體效率，該簽密方案稱為SCS。簽密3.解密與驗證驗證方收到簽密密文（c,r,s）后，執(zhí)行如下操作。(1)計算，并將k分為適當(dāng)長度的k1和k2。(2)計算m=Dk1(c)。(3)如果r=H(k2,m)，那么可以驗證消息來自簽密方。2.簽密對于消息m，簽密方執(zhí)行如下操作。(1)選擇隨機數(shù)x，1<x<q。(2)計算，并將k分為適當(dāng)長度的k1和k2。(3)計算r=H(k2,m)。(4)計算。(5)計算c=Ek1(m)。對消息m的簽密密文為（c,r,s）。目錄016.1公鑰秘密數(shù)學(xué)基礎(chǔ)026.2RSA公鑰密碼體制036.3ElGamal公鑰密碼體制6.5身份識別05046.4數(shù)字簽名與驗證身份識別強身份識別：

(1)P能向V證明他的確是P。

(2)P向V證明身份后，V不能獲得冒用P的身份的信息。

(3)除了P以外的第三者能夠以P的身份執(zhí)行協(xié)議，能夠讓V相信他是P的概率可以忽略不計。弱身份識別：

(1)生物特征：利用生物所具有的獨一無二的特征，例如指紋、虹膜、DNA等來進行身份識別。

(2)口令：用戶提供賬戶信息的同時，提供只有他本人才用戶的口令，來向驗證方證明自己的身份。

(3)智能卡：智能卡中存放著用戶的身份數(shù)據(jù)，智能卡由合法用戶隨身攜帶，通過專用的讀卡器讀出卡中的數(shù)據(jù)，從而識別用戶的身份。(4)USBKey：USBKey存儲著用戶的密鑰或數(shù)字證書，可以實現(xiàn)對用戶身份的識別。Guillou-Quisquater身份識別協(xié)議2.TA向P頒發(fā)身份證書

(1)TA為P建立身份信息IDP。

(2)P選擇一個整數(shù)u，0≤u≤n-1，且gcd(u,n)=1。計算，u作為P的私鑰，v作為P的公鑰，并將v發(fā)送給TA。

(3)TA計算簽名s=SignTA(IDP,v)，將證書CertP=(IDP,v,s)發(fā)送給P。1.參數(shù)選擇

(1)TA選擇兩個大素數(shù)p和q，計算n=p·q，p和q保密，n公開。

(2)TA選擇一個大素數(shù)b，b滿足gcd(b,

(n))=1，且b的長度為40bit。TA計算

作為私鑰。b作為TA公鑰公開。(3)TA確定自己的簽名算法SignTA和哈希函數(shù)h，h公開。Guillou-Quisquater身份識別協(xié)議3.P向V證明其身份

(1)P隨機選取整數(shù)k，0≤k≤n-1，計算，并將證書CertP和R發(fā)送給V。(2)V驗證s是否是TA對(IDP,v)的簽名，如果是，V隨機選取整數(shù)r，0≤r≤b-1，并將r發(fā)送給P。(3)P計算，并將y發(fā)送給V。(4)V驗證是否有：成立，如果成立，V就接受P的身份證明；否則，V拒絕P的身份證明。Guillou-Quisquater身份識別協(xié)議4.協(xié)議分析

在GQ協(xié)議中，由于P掌握了秘密信息u，對于任何挑戰(zhàn)r，P都可以計算y，使得成立。如果一個攻擊者能夠猜出V隨機選取的整數(shù)r，則攻擊者可以隨機選取一個y，計算出。攻擊者將R和y發(fā)送給V，則V一定能夠驗證成立，V接受攻擊者的身份證明，攻擊者成功地冒充了P。攻擊者能夠猜中r的概率為1/b，因為b是一個非常大的整數(shù)，隨意攻擊者成功冒充P的概率是非常小的。Schnorr身份識別協(xié)議2.TA向P頒發(fā)身份證書

(1)TA為P建立身份信息IDP。

(2)P選定加密私鑰u，，同時計算相應(yīng)的私鑰。(3)TA對P的身份信息IDP和公鑰v計算簽名s=SignTA(IDP,v)，將證書CertP=(IDP,v,s)發(fā)送給P。1.參數(shù)選擇

(1)TA選擇兩個大素數(shù)p和q，其