RSAElgamalECC加密碼體制

1、產(chǎn)生密鑰對選擇兩個大素數(shù)p,q, pqn=pq,(n)=(p-1)(q-1)選擇整數(shù)e,使得gcd(e,(n)=1d e-1 mod (n) KU=e,n, 私鑰: KR=d,n使用加密: C = Me mod nM = Cd mod nRSA加密過程：1例子：選p7，q17則npq119且(n)(p-1)(q-1)61696取e5則d77 (57738549611 mod 96)公鑰（5，119），私鑰（77，119） 加密m19則cme mod n= 195 mod 119 = 66 mod 119解密c66mcd mod n = 6677mod 11919 mod 1192再例：p =

2、53，q = 61，n = pq = 3233，(n)52x60 = 3120令d = 791，則e = 71令m = RE NA IS SA NC E即m = 1704 1300 0818 1800 1302 0426170471 mod 3233 = 3106 mod 3233， C = 3106 0100 0931 2691 1984 29273RSA總結(jié)：找素數(shù)選取兩個大的隨機(jī)的素數(shù)p，q（采用Miller-Rabin概率測試方法）計算模n和Euler函數(shù)(n)，npq(n)=(p-1)(q-1)找ed1 mod (n)隨機(jī)取一個數(shù)e(與(n)互素)，用擴(kuò)展Euclid算法求d即可發(fā)布

3、d保密，(d, n)是私鑰 KU發(fā)布(e,n)，這是公鑰KR銷毀p、q注意： 選擇足夠大的n(1024位以上),并且使得e,d之間相差不太大,也不太小，防指數(shù)攻擊。4RSA的低指數(shù)攻擊令三用戶的加密鑰e均選3，而有不同的模n1, n2, n3，若有一用戶將消息m傳給三個用戶的密文分別為 y1=m 3 mod n1 , m n1 y2=m 3 mod n2 , m n2 y3=m 3 mod n3 , m n3一般選n1, n2, n3互素(否則，可求出公因子，而降低安全性)，利用中國余定理，可從y1, y2, y3求出 m 3 mod (n1 n2 n3)。 由mn1, mn2, mn3，可得

4、m3 n1 n2, n3，故通過開立方可求m。5計時攻擊Timing Attacks on Implementations of DH, RSA, DSS, and Other Systems，1994，Paul C. Kocher1995年有人提出了一種非常意想不到的攻擊方式：假如攻擊者對加密者的硬件有充分的了解，而且知道它對一些特定的消息加密時所需要的時間的話，那么她可以很快地推導(dǎo)出d。這種攻擊方式之所以會成立，主要是因?yàn)樵谶M(jìn)行加密時所進(jìn)行的模指數(shù)運(yùn)算是一個位元一個位元進(jìn)行的，而位元為1所花的運(yùn)算比位元為0的運(yùn)算要多很多，因此若能得到多組訊息與其加密時間，就會有機(jī)會可以反推出私鑰的內(nèi)容。可

5、研究，類似于ECC中的旁道攻擊，它們是利用硬件實(shí)現(xiàn)的特征進(jìn)行。6ElGamal密碼體制密鑰產(chǎn)生過程選擇一個素數(shù)p，以及GF(p)的本原元g(g p), xp,計算公鑰 ygx mod p, =(y,g,p)為公鑰，x為私鑰加密過程M是發(fā)送明文組，選擇隨機(jī)數(shù)k，且(k,p1)=1，計算： C1=g k mod p (隨機(jī)數(shù)k被加密) C2=Myk mod p(明文被隨機(jī)數(shù)k和公鑰加密)密文由C1、C2級連構(gòu)成，即密文C=C1|C2。解密過程M=C2/C1x=My k/gkx=Mgxk/gkx mod p 7例：p = 17，g = 3，xA = 2，xB = 5，m = 11，m從A發(fā)送到B，A

6、選擇k = 7.求：密文(c1, c2)并解密加密：YA = gxA mod P = 32 mod 17 = 9YB = gxB mod P = 35 mod 17 = 5K = (YB)k mod P = 57 mod 17 = 10c1 = gk mod P = 37 mod 17 = 11c2 = mK mod P = 11 10 mod 17 = 8所以，密文C = (c1, c2) = (11, 8)解密：K = c1xB mod P = 115 mod 17 = 10c2 = mK mod P = 10m mod 17 = 8m = c2/K mod P = c2K-1 mod P

7、K K-1 mod P = 1，即10 K-1 mod 17 = 1，得K-1 = 12所以，明文m = c2K-1 mod P = 8x12 mod 17 = 118橢圓曲線密碼體制 -加密體制9橢圓曲線加密-ECES1、系統(tǒng)的建立 選取:一個基域GF(p)定義在該基域上的橢圓曲線Ep(a,b)：E上的一個擁有大素數(shù)階n的點(diǎn)P其中有限域GF(p) 、橢圓曲線參數(shù)a,b、點(diǎn)P和階n都是公開信息102、密鑰的生成在區(qū)間1,n-1中隨機(jī)選取一個整數(shù)d作為私鑰。計算公鑰:Q=d*P公開密鑰:Q（橢圓曲線上的一個點(diǎn)） 而私鑰d保密。 113、加密過程 待發(fā)送消息：AliceBob:M。過程如下：查找Bob的公開密鑰：Q將消息M表示成一個域元素:m在區(qū)間1, n-1中隨機(jī)選取一個整數(shù)k計算點(diǎn):(x1,y1)=kP計算點(diǎn):(x2,y2)=kQ，如果x2=0，則返回第(3)步計算:c=mx2傳送加密數(shù)據(jù)(x1, y1, c)給Bob 124、解密過程 當(dāng)實(shí)體Bob解密從Alice收到的密文(x1, y1, c)時