|
轉(zhuǎn)載請(qǐng)注明http://blog.csdn.net/boksic 如有疑問(wèn)歡迎留言
如果不知道數(shù)學(xué)上的群、循環(huán)群等概念，可以先了解ElGamal加密算法 后再回過(guò)來(lái)橢圓曲線(xiàn)加密
這兩個(gè)算法有共通之處，都是在離散問(wèn)題難解群上的加密算法，橢圓曲線(xiàn)是進(jìn)一步的加深
首先，什么是橢圓曲線(xiàn)
橢圓曲線(xiàn)(Elliptic curve)
叫橢圓曲線(xiàn)只是因?yàn)榉匠谈鷻E圓的曲線(xiàn)積分比較相似
橢圓曲線(xiàn)方程可以統(tǒng)一為
 - 當(dāng)然還有要求
至于長(zhǎng)什么樣，繪個(gè)圖看看
用matlab寫(xiě)了一個(gè)模擬程序，可以控制a,b變化，顯示曲線(xiàn)的圖像。
- clear;clc;figure(1);
- a=0;
- b=0;
- h_text1=uicontrol('Style','text','String','a','Position',[50 20 50 20]);
- h_text1=uicontrol('Style','text','String','b','Position',[50 0 50 20]);
- ezplot(strcat('x+',num2str(a),'*y'));
- h_slider1=uicontrol('Style','slider','Position',[100 20 200 20],...
- 'Max',10,'Min',-10,'callback',['a=num2str(get(gcbo,''value''));',...
- 'ezplot(strcat(num2str(b),''+x^3+'',num2str(a),''*x-y^2''))']);
- %h_text2=uicontrol('Style','text','String','b');
- h_slider2=uicontrol('Style','slider','Position',[100 0 200 20],...
- 'Max',10,'Min',-10,'callback',['b=num2str(get(gcbo,''value''));',...
- 'ezplot(strcat(num2str(b),''+x^3+'',num2str(a),''*x-y^2''))']);
再直觀一點(diǎn)
（不得不說(shuō)在這方面，Mathematica比Matlab要方便強(qiáng)力太多，用MATLAB做這個(gè)圖像速度慢代碼長(zhǎng)步驟復(fù)雜效果爛）
| b=0,a在[-20,20]上變動(dòng)時(shí)的圖像 |
a=-6,b在[-20,20]上變動(dòng)時(shí)的圖像 |
| Plot3D[{(x^3+y*x)^0.5,-(x^3+y*x)^0.5},{x,-7,7},{y,-20,20}] |
Plot3D[{(x^3-6x+y)^0.5,-(x^3-6x+y)^0.5},{x,-7,7},{y,20,-20}] |
 |
 |
"受ElGamal密碼啟發(fā)，在其它離散對(duì)數(shù)問(wèn)題難解的群中，同樣可以構(gòu)成ELGamal密碼。于是人們開(kāi)始尋找其它離散問(wèn)題難解的群。研究發(fā)現(xiàn)，有限域GF（p）上的橢圓曲線(xiàn)的解點(diǎn)構(gòu)成交換群，而且離散對(duì)數(shù)問(wèn)題是難解的。于是可在此群上建立ELGamal密碼，并稱(chēng)為橢圓曲線(xiàn)密碼。"
解點(diǎn)交換群
為了構(gòu)成加法交換群，需要定義元素、單位元、逆元素、加法
解點(diǎn)
設(shè)p是大于3的素?cái)?shù)，且4a3+27b2 ≠0 mod p ，稱(chēng)
y^2 =x^3 +ax+b ，a,b∈GF(p)
為GF（p）上的橢圓曲線(xiàn)。
由橢圓曲線(xiàn)可得到一個(gè)同余方程：
y^2 =x^3 +ax+b mod p
其解為一個(gè)二元組<x,y>，x,y∈GF(p)，將此二元組描畫(huà)到橢圓曲線(xiàn)上便為一個(gè)點(diǎn)，于是又稱(chēng)其為解點(diǎn)。
單位元
引進(jìn)一個(gè)無(wú)窮點(diǎn)O（∞,∞），簡(jiǎn)記為0，作為0元素。
O（∞,∞）＋O（∞,∞）＝0＋0＝0 。
并定義對(duì)于所有的解點(diǎn)P（x ，y）有
P（x ,y）+O＝O+ P（x ,y）＝P（x ,y）
逆元素
任何解點(diǎn)R（x ,y）的逆就是 R（x ,-y）。
加法
P（x1 ，y1）＋Q（x2 ，y2）＝R（x3 ，y3）
(提醒一下，這里的運(yùn)算都是模運(yùn)算，值都是整數(shù)，像除法是模逆運(yùn)算)
定義s = (yP ? yQ)/(xP ?xQ)，即PQ線(xiàn)的斜率
總共3種情況
1.一般情況下 R = P + Q = (xR, ? yR)其中
2.如果xP = xQ,yP = ?yQ(包括yP =yQ = 0的情形)
結(jié)果R就是無(wú)窮遠(yuǎn)點(diǎn)0
3 盡管xP = xQ但yP = yQ ≠ 0那么R =P +P = 2P = (xR,?yR)有
加法的幾何意義
設(shè)P和Q是橢圓曲線(xiàn)的兩個(gè)點(diǎn)，則連接P和Q的直線(xiàn)與橢圓曲線(xiàn)的另一交點(diǎn)關(guān)于橫軸的對(duì)稱(chēng)點(diǎn)即為R點(diǎn)。在該群中P + Q + R = 0
橢圓曲線(xiàn)交換群實(shí)例
對(duì)于標(biāo)準(zhǔn)方程y^2=x^3+ax+b (mod p) 設(shè)定基本參數(shù)
p=31,a=2,b=17
隨便找一個(gè)在曲線(xiàn)上(即滿(mǎn)足該方程)的點(diǎn)P=(10,13)
然后按照上面提到的公式來(lái)逐一計(jì)算2P,3P,4P.....
我用的Python來(lái)計(jì)算（調(diào)用的mod_inv是模下的除運(yùn)算，代碼可參看前面的文章）:
- px,py=10,13
- x,y=px,py
- a,b=2,17
- p=31
- for i in range(p+20):
- if(x==px and y==py):
- x3=(9*x**4-8*x*y**2+6*a*x**2+a**2)\
- *mod_inv(4*y**2,p)%p
- y3=((3*x**2+a)*(x-x3)*mod_inv(2*y,p)-y)%p
- elif(x==px):
- x3,y3=0,0
- elif(x==0 and y==0):
- x3,y3=px,py
- else:
- x3=(((y-py)*mod_inv(x-px,p))**2-x-px)%p
- y3=((y-py)*(px-x3)*mod_inv(x-px,p)-py)%p
- str = "%dP= (%d,%d)"%(i+2,x3,y3)
- print str,
- x,y=x3,y3
可以得到
- 2P= (21,19) 3P= (19,30) 4P= (27,10)
- 5P= (29,25) 6P= (24,1) 7P= (30,13)
- 8P= (22,18) 9P= (8,24) 10P= (20,11)
- 11P= (6,11) 12P= (23,27) 13P= (12,23)
- 14P= (3,22) 15P= (7,23) 16P= (1,19)
- 17P= (17,2) 18P= (9,12) 19P= (13,15)
- 20P= (5,11) 21P= (5,20) 22P= (13,16)
- 23P= (9,19) 24P= (17,29) 25P= (1,12)
- 26P= (7,8) 27P= (3,9) 28P= (12,8)
- 29P= (23,4) 30P= (6,20) 31P= (20,20)
- 32P= (8,7) 33P= (22,13) 34P= (30,18)
- 35P= (24,30) 36P= (29,6) 37P= (27,21)
- 38P= (19,1) 39P= (21,12) 40P= (10,18)
- 41P= (0,0) 42P= (10,13)
matlab顯示一下，點(diǎn)的分布與順序都是雜亂無(wú)章
|
