橢圓曲線入門詳解

華燈初放l 2016-07-14

展開全文

轉(zhuǎn)載請注明http://blog.csdn.net/boksic 如有疑問歡迎留言

如果不知道數(shù)學(xué)上的群、循環(huán)群等概念，可以先了解ElGamal加密算法后再回過來橢圓曲線加密

這兩個算法有共通之處，都是在離散問題難解群上的加密算法，橢圓曲線是進(jìn)一步的加深

首先，什么是橢圓曲線

橢圓曲線(Elliptic curve)

叫橢圓曲線只是因為方程跟橢圓的曲線積分比較相似

橢圓曲線方程可以統(tǒng)一為

$y^2=x^3+ax+b\,$
當(dāng)然還有要求

至于長什么樣，繪個圖看看

用matlab寫了一個模擬程序，可以控制a,b變化，顯示曲線的圖像。

[cpp] view plain copy

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''))']);

再直觀一點

（不得不說在這方面，Mathematica比Matlab要方便強(qiáng)力太多，用MATLAB做這個圖像速度慢代碼長步驟復(fù)雜效果爛）

b=0,a在[-20,20]上變動時的圖像	a=-6,b在[-20,20]上變動時的圖像
Plot3D[{(x^3+yx)^0.5,-(x^3+yx)^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ā)，在其它離散對數(shù)問題難解的群中，同樣可以構(gòu)成ELGamal密碼。于是人們開始尋找其它離散問題難解的群。研究發(fā)現(xiàn)，有限域GF（p）上的橢圓曲線的解點構(gòu)成交換群，而且離散對數(shù)問題是難解的。于是可在此群上建立ELGamal密碼，并稱為橢圓曲線密碼。"

解點交換群

為了構(gòu)成加法交換群，需要定義元素、單位元、逆元素、加法

解點

設(shè)p是大于3的素數(shù)，且4a3+27b2 ≠0 mod p ，稱
y^2 =x^3 +ax+b ，a,b∈GF(p)
為GF（p）上的橢圓曲線。
由橢圓曲線可得到一個同余方程：
y^2 =x^3 +ax+b mod p
其解為一個二元組<x,y>，x,y∈GF(p)，將此二元組描畫到橢圓曲線上便為一個點，于是又稱其為解點。

單位元

引進(jìn)一個無窮點O（∞,∞），簡記為0，作為0元素。

O（∞,∞）＋O（∞,∞）＝0＋0＝0 。

并定義對于所有的解點P（x ，y）有

P（x ,y）+O＝O+ P（x ,y）＝P（x ,y）

逆元素

任何解點R（x ,y）的逆就是 R（x ,-y）。

加法

P（x1 ，y1）＋Q（x2 ，y2）＝R（x3 ，y3）

(提醒一下，這里的運(yùn)算都是模運(yùn)算，值都是整數(shù)，像除法是模逆運(yùn)算)

定義s = (y_P ? y_Q)/(x_P ?x_Q)，即PQ線的斜率

總共3種情況