ECC加密算法.doc

c+ 容易的實現(xiàn)橢圓曲線加密算法c+ 簡單的實現(xiàn)橢圓曲線加密算法橢圓曲線算法橢圓曲線密碼體制來源于對橢圓曲線的研究，所謂橢圓曲線指的是由韋爾斯特拉斯（Weierstrass）方程：y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)所確定的平面曲線。其中系數(shù)ai(I=1,2,6)定義在某個域上，可以是有理數(shù)域、實數(shù)域、復(fù)數(shù)域，還可以是有限域GF（pr），橢圓曲線密碼體制中用到的橢圓曲線都是定義在有限域上的。橢圓曲線上所有的點外加一個叫做無窮遠(yuǎn)點的特殊點構(gòu)成的集合連同一個定義的加法運算構(gòu)成一個Abel群。在等式mP=P+P+P=Q (2)中，已知m和點P求點Q比較容易，反之已知點Q和點P求m卻是相當(dāng)困難的，這個問題稱為橢圓曲線上點群的離散對數(shù)問題。橢圓曲線密碼體制正是利用這個困難問題設(shè)計而來。公鑰算法是基于數(shù)學(xué)函數(shù)（如單向陷門函數(shù)），公鑰密碼體制根據(jù)其所依據(jù)的難題一般分為三類：大整數(shù)分解問題類、離散對數(shù)問題類、橢圓曲線類。本文是在素域Zp上的，以Menezes-Vanstone形式的橢圓加密算法。在素域上的曲線函數(shù)為y2 = x 3 +a* x + b a，b為小于p的非負(fù)數(shù)，且 4*a3+ 27*b2 != 0對于在素域上的加法中，對于所有的點P,Q 屬于E(Zp),有加法規(guī)則：1。P + O = O + P = P ,P + (-P) = O;O為橢圓曲線上的零點或者稱為無限遠(yuǎn)的點，但是O在橢圓曲線的加法域上。2.加法的分配率和結(jié)合律，對于s,t 屬于Zp,有（s + t ）* P = s * P + t* P;3.對于 P = (x1,y1),Q = (x2,y2) ,并且 P != - Q,則P + Q=（x3，y3），x3 = k2 - x1 -x2;y3 = k*(x1-x3) - y1;k = (y2-y1)/(x2-x1) if P != Q;k = (3x12 + a)/(2*y1) if P = Q;橢圓曲線在素域上的運算用到除法，而在除法的規(guī)則是a / b = c mod p 即計算 a x b-1 = c mod p ，其中 b-1為b的乘法逆元， 即 b x b-1 = 1 mod p。對于乘法逆元，當(dāng)b與p互素時，存在唯一解，而這里p是一個素數(shù)，且b不可能為1，則肯定有解。對于求乘法逆元，一般使用歐幾里德算法，如下：int getX_1(int x,int mod)int Q,X1,X2,X3,Y1,Y2,Y3,T1,T2,T3;X1 = 1;X2 = 0;X3 = mod;Y1 = 0;Y2 = 1;Y3 = (x%mod + mod) %mod;/獲得正整數(shù)while(Y3 != 1) Q = X3 / Y3;T1 = X1 - Q * Y1;T2 = X2 - Q * Y2;T3 = X3 - Q * Y3;X1 = Y1;X2 = Y2;X3 = Y3;Y1 = T1;Y2 = T2;Y3 = T3;return Y2;乘法運算規(guī)則：1. 對于任意 k 屬于 Zp，有 k * P = P + . + P (k個P相加）2. 對于任意 s,t 屬于 Zp，有 s *(t *P) = (s*t)*P對于Menezes-Vanstone的橢圓加密算法：1. 產(chǎn)生密鑰，任選一個整數(shù)k ,0kp ,為私鑰，在曲線上任選一點 A ，并計算 B = k*A ，公鑰為（A,，B）。其中又可稱A為基鑰，對于最小整數(shù)n以使 n* A = O ，則n稱為周期，要是周期為素數(shù)，且為一個較大值才合理。2.加密過程：令明文為 M = (m1,m2),M可以不是曲線E上的點。計算得到密文(C1,C2),其中任選一個數(shù)屬于Zp：C1 = r * A;；Y= （y1,y2) = r * B;C2 = (C21,C22) = (y1 * m1 mod p,y2* m2 mod p)3 解密過程；計算Z = (z1,z2) = k*C1;計算明文 M = (C21 * z1-1 mod p, C22 * z2 -1 mod p).c+中的模運算，當(dāng)有負(fù)數(shù)存在時無法達(dá)到正確結(jié)果，簡直是坑，如 -1 % 2，在使用vs2012進(jìn)行測試，會返回-1，而不是1. c+中模運算結(jié)果的符號和被除數(shù)的符號一致。參數(shù)選?。哼x取 p = 127,曲線函數(shù)為: y2 = x3 + 5* x + 37， a = 5 ,b= 37， r = 7.選取私鑰 k = 9選取一個點A為（11,4)則 B = k*A = (120,41)則源代碼如下，這里直接對char進(jìn)行加密，效果不佳#include stdafx.h#include #include using namespace std;const int k = 9;const int a = 5;const int b = 37;const int p = 127;const int r =7;int getX_1(int x,int mod)int Q,X1,X2,X3,Y1,Y2,Y3,T1,T2,T3;X1 = 1;X2 = 0;X3 = mod;Y1 = 0;Y2 = 1;Y3 = (x%mod + mod) %mod;/獲得正整數(shù)while(Y3 != 1) Q = X3 / Y3;T1 = X1 - Q * Y1;T2 = X2 - Q * Y2;T3 = X3 - Q * Y3;X1 = Y1;X2 = Y2;X3 = Y3;Y1 = T1;Y2 = T2;Y3 = T3;return Y2;/獲得其乘法逆元struct pointint x;int y;point A,B;/公鑰typedef pair twopoint;bool operator = (point pa,point pb)return pa.x = pb.x & pa.y = pb.y;point operator + (point pa , point pb)int k;if(pa = pb)k = (3 * pa.x * pa.x + a) * getX_1(2* pa.y ,p) % p ;/必須使用正整數(shù)。這里pa.y的值不能取0./當(dāng)取0時，這就不能進(jìn)行這個計算了，因為 pa = -pb了，則，應(yīng)該進(jìn)行一個判斷。但是，這樣的結(jié)果是 O，是不在橢圓曲線上的，不能進(jìn)行輸出的值。/這里是有一個周期數(shù)在，對于容易一個基值的也就是先給出的A來說，它有一個周期n，使nA = O，而這里所有參數(shù)的選取值/都小于n，使其不會達(dá)到O，保證了不會出錯，應(yīng)該是這樣吧。elsek = (pb.y - pa.y) * getX_1(pb.x - pa.x , p) %p;point c;c.x = (k*k - pa.x -pb.x) %p;c.y = (k * (pa.x - c.x) - pa.y)%p ;c.x = (c.x + p) %p; c.y = (c.y + p) %p; return c;point operator * (point &b,int n)point q = b;n = n -1;for(int i = 1 ; i n;i+)q = q + b ;return q;twopoint ECodePoint(point m)point c1,c2;c1 = A * r ;point Y = B * r ;c2.x = Y.x * m.x % p ;c2.y = Y.y * m.y % p ;return twopoint(c1,c2);point DCodePoint(twopoint t)point Z = t.first * k;point m;m.x = t.second.x * getX_1(Z.x,p) % p ;m.y = t.second.y * getX_1(Z.y,p) % p ;return m;string ECode(string input)/明文的輸入是一個string類型，但是單個的操作應(yīng)該是對單個的字符char轉(zhuǎn)換成的int類型進(jìn)行計算string output = ;point M;twopoint C;for(int i =0; i input.length();i+)M.x = i;M.y = inputi;C = ECodePoint(M);output += (char)C.first.x ;output += (char)C.first.y ;output += (char)C.second.x ;output += (char)C.second.y ;return output;string DCode(string input)string output = ;point M;twopoint C;if(input.length()%4 != 0)return 錯誤輸入;/因為密文肯定是4的倍數(shù)，如果不是，肯定出錯了。for(int i = 0;i input.length();)C.first.x = inputi+;C.first.y = inputi+;C.second.x = inputi+;C.second.y = inputi+;M = DCodePoint(C);output += (char)M.y;return output;int main()A.x = 11;A.y = 4;B = A*k;string s = ;/加密簡單，隨便輸入點東西就可以加密了，但是解密不行啊，隨便輸入肯定是錯誤的結(jié)果，/程序肯定會出錯，所以，只支持對之前加密的結(jié)果進(jìn)行解密。cout使用在素域上的曲線 y2 = x3 + 5*x +37 ，使用Menezes-Vanstone的