本文主要是使用北太天元演示橢圓曲線加密算法（ECC）的加密/解密過程，內(nèi)容包括密鑰、公鑰生成，以及通過加密并解密一個(gè)簡單數(shù)字的過程來描述其使用方法。我實(shí)際上就是把參考文獻(xiàn)的文章中的代碼移植到北太天元上來。這個(gè)移植工作非常容易，在最新版本的北太天元下幾乎一行程序都不用改。 因此，我把原來的文章稍微精簡一下，方便和我類似的人更容易理解吧。

按道理說，ECC加密還是挺難的，涉及到有限域(finite field, 又稱為伽羅瓦域).但是實(shí)際上，我們只要這樣想, 我們會取定一個(gè)素?cái)?shù)p, 然后，我們所要考慮的數(shù)最后都會對p 取余數(shù).

例如:? 7 是一個(gè)素?cái)?shù)，那么 3 和 10 就看成相等的，因?yàn)?3 除以7 所得余數(shù) (北太天元用 mod(3,7) 來計(jì)算) 和 10 除以 7 所得余數(shù)是相等。 我們計(jì)算 3 * 5 之后得到了15， 然后回到7再取余數(shù), 得到 1. 我們還可以定義 3 的逆， 因?yàn)?mod(3*5, 7) = 1, 因此 我們就說5是3的逆。
從而，我們還可以對 2/3 對 7 取余數(shù)進(jìn)行定義了，因?yàn)?1/3 = 5 (mod 7)因此? 2/3 = 2*5? (mod 7)? 從而? 2/3 對7 取余數(shù)就可以定義為mod(2*5, 7) , 計(jì)算結(jié)果得到3.
從而我們可以定義 2/3 對7的余數(shù)是 3.


橢圓曲線加密涉及到一個(gè)橢圓曲線 ?
???? y^2 = x^3 + a*x + b
其中 a,b? 是滿足一定條件的常數(shù).

工具
當(dāng)指定x的值時(shí)，計(jì)算區(qū)間[0,p]內(nèi)所有滿足
???? y^2 = x^3 + a*x + b?? ?
的y值, 當(dāng)然上面的等號成立也是在對p取余數(shù)的條件下。當(dāng)然，這里我有一個(gè)疑問，為啥不是求{0,,1,...,p-1} 之內(nèi)的數(shù)呢？對p取余數(shù)的話 0 == p (mod p) 和 0^2 == p^2 (mod p) 總是成立啊。不過，也許另有玄機(jī)啊，我這里保持了參考文獻(xiàn)的做法。

這個(gè)工具功能很容易理解，通俗點(diǎn)說就是給定x求y,y的取值范圍為[0,p]

%file:ECCCal.m
%a,b為橢圓參數(shù)，p為質(zhì)數(shù)，x為給定的值
function [ y ] = ECCCal( a,b,p,x )
y=[];

mm = mod(x^3+a*x+b,p);

index = 1;

for yy = 0:1:p
??? if mod(yy^2,p) == mm
??????? y(index)=yy;
??????? index=index+1;
??? end
end

end

我們考慮 y^2 = x^3 +x +1 , 也就是橢圓曲線 y^2 = x^3 +a*x+b 中的 a = 1, b= 1
的情況。我們選定素?cái)?shù)p =23,? 計(jì)算x=3時(shí)的 y 值,
在北太天元的命令行輸入
>> ECCCal(1,1,23,3)
我們會得到
ans =

?? 10?? 13
我們可以得到可以得到兩個(gè)結(jié)果 y =10和y = 13
（有多個(gè)結(jié)果是正常的不用在意，因?yàn)橐辉畏匠踢€有兩個(gè)根，何況這是一個(gè)
更加奇怪的方程呢, 實(shí)際上如果不限定y的范圍，理論上是有無數(shù)個(gè)解).

我們可以求出所有滿足橢圓曲線方程
???? y^2 = x^3 + a*x + b
的解，
其中 a= 1, b= 1, 滿足的意思是說方程左右兩邊在對p取余數(shù)之后是相等的，

自然，我們可以僅僅考慮x 和 y 都是屬于 {0,1,....p} 這個(gè)集合的。 然后我把求的解作成一對(x,y), 作為平面上的點(diǎn)畫出來。

計(jì)算(0,0)->(p,p)正方形范圍內(nèi)所有滿足"橢圓曲線"的點(diǎn)

我們給出在北太天元上代碼來完成這個(gè)工作, 使用這個(gè)工具可以方便我們將該范圍內(nèi)所有滿足“橢圓曲線”畫出來，
并且把數(shù)值也數(shù)出來。

%file:ECCPlot.m
%a,b分別為橢圓的參數(shù)，p為一個(gè)質(zhì)數(shù)
function [x,y] =? ECCPlot( a,b,p)
?? ?if (nargin == 0)
?? ??? ?a = 1;
?? ??? ?b = 1;
?? ??? ?p = 23;
?? ?end

x=[];
y=[];
index = 1;
for xr = 0:1:p
??? mm = mod(xr^3+a*xr+b ,p);?? ?
??? for yr=0:1:p
??????? if mod(yr^2,p) == mm
??????????? x(index)=xr;
??????????? y(index)=yr;
??????????? index = index+1;
??????? end
??? end
end
plot(x,y,'.','MarkerSize',50)
hold on
grid on
end

假設(shè)橢圓曲線y^2 = x^3 + a*x+b 的 a= 1, b=1, 然后選取素素p =23,
在北太天元命令行輸入
>>[x,y] = ECCPlot(1,1,23)
我們可以看到如下圖片

因?yàn)闄E圓曲線加密算法的特殊性我們需要自己實(shí)現(xiàn)幾個(gè)操作方法分?jǐn)?shù)的模運(yùn)算

我們很容易知道 2對23取模的結(jié)果是2，但1/2對23的模是多少呢？北太天元暫時(shí)是沒有這種計(jì)算的方法的，我們可以使用下面的modfrac函數(shù)來完成這個(gè)操作

%file:modfrac.m
% n 分子? d 分母?? m 模數(shù)
function y = modfrac( n,d,m )

n=mod(n,m);
d=mod(d,m);


i=1;
while mod(d*i,m) ~=1
??? i=i+1;
end

y=mod(n*i,m);
end

我們還需要橢圓曲線加密而定義的一個(gè)特殊的加法, 具體規(guī)則此處不再贅述了，下面的北太天元代碼得到點(diǎn)(resx, resy) 就是點(diǎn)(x1,y1)和(x2,y2)的和，當(dāng)然這種和是用特殊的加法得到。

%file:Add.m
%a,b 橢圓參數(shù)? p 質(zhì)數(shù) x1,y1 第一個(gè)點(diǎn)的坐標(biāo) x2,y2 第二個(gè)點(diǎn)的坐標(biāo)
function [ resx,resy ] = Add( a,b,p,x1,y1,x2,y2 )

if x1==x2 && y1==y2
??? k=modfrac(3*x1^2+a,2*y1,p);
??? resx = mod(k^2-x1-x2,p);
??? resy = mod(k*(x1-resx)-y1,p);
end

if x1==x2 && y1~=y2
??? resx = inf;
??? resy = inf;
end

if x1 ~= x2
??? k=modfrac(y2-y1,x2-x1,p);
??? resx = mod(k^2-x1-x2,p);
??? resy = mod(k*(x1-resx)-y1,p);?? ?
end
end

如兩點(diǎn)P(3,10)，Q(9,7) 計(jì)算P+Q：我們在北太天元的命令行輸入
[x,y]=Add(1,1,23,3,10,9,7)
得到結(jié)果是
x =
?? 17
y =
?? 20
也就是? P(3,10) + Q(9,7) 得到了 (17,20).


常量乘法

什么是常量乘法呢？實(shí)際上就是N（N為正整數(shù)）乘以點(diǎn)P。同時(shí)也需要說明的是下邊北太天元的實(shí)現(xiàn)是來源于參考文獻(xiàn)的MATLAB代碼

%file:NP.m
%a,b 橢圓參數(shù)，p 質(zhì)數(shù)，n表示 n個(gè)點(diǎn)P相加也就是n*P ,x,y 表示P點(diǎn)的橫縱坐標(biāo)
function [resx,resy] = NP( a,b,p,n,x,y )

if n ==1
??? resx = x;
??? resy = y;
??? return;
end
if n>=2
??? [xsub,ysub]=NP(a,b,p,n-1,x,y);
??? if xsub==Inf && ysub == Inf
??????? resx=Inf;
??????? resy=Inf;
??? else
??????? [resx,resy]=Add(a,b,p,x,y,xsub,ysub);
??? end
end
end

如我們計(jì)算N=2, 點(diǎn)P(3,10), 計(jì)算N*P （特殊定義的加法把N個(gè)p相加的結(jié)果)
在北太天元上輸入
>>[x,y]=NP(1,1,23,2,3,10)
x =
?? 7
y =
?? 12
N=2, P(3,10) 時(shí)N*P的結(jié)果是(7,12).
如果N=3, P(3,10) 相乘，
[x,y]=NP(1,1,23,3,3,10)
x =
?? 19
y =
?? 5
得到的結(jié)果(19,5).

加密解密過程
至此我們加密解密需要的所有算法模塊就全部足夠了。
流程以摘要中提到的第一篇文章中給的示例為例

??? Alice選定一條橢圓曲線E，并取橢圓曲線上一點(diǎn)作為基點(diǎn)G 假設(shè)選定的橢圓為a=4,b=20,p=29所示示的橢圓，基點(diǎn)G(13,23) , 基點(diǎn)G的階數(shù)n=37（階數(shù)的概念本文沒提,你可以理解為在進(jìn)行常量乘法運(yùn)算的時(shí)候常量的最大值要小于n ）
??? Alice選擇一個(gè)私有密鑰k（k<n）并生成公開密鑰K=kG 比如k=25, K= kG = 25G = (14,6）(使用我們的乘法運(yùn)算函數(shù)去測試一下）
??? Alice將E和點(diǎn)K、G傳給Bob （ 這沒什么說的，E,K,G 共同組成了公鑰，需要把公鑰發(fā)給對方）
??? Bob收到信息后，將待傳輸?shù)拿魑木幋a到上的一點(diǎn)M（編碼方法略），并產(chǎn)生一個(gè)隨機(jī)整數(shù)r（r<n,n為G的階數(shù)） 假設(shè)r=6 要加密的信息為3,因?yàn)樵撔畔⒁残枰獫M足曲線方程E，所以我們很容易能夠選取到一點(diǎn)(3,28)（其他的點(diǎn)如(3,1)也是可以的）
??? Bob計(jì)算點(diǎn)C1=M+rK和C2=rG
??? Bob將C1、C2傳給Alice（容易理解，將加密信息傳回給Bob，由Bob解密以知道Alice給他傳的是啥）
??? Alice收到信息后，計(jì)算C1-kC2得到的結(jié)果應(yīng)該是(3,28) （解密過程）

至此橢圓曲線加密、解密的整個(gè)流程就結(jié)束了。將其寫成一個(gè)MATLAB腳本 如下：

%file:ECC.m
%演示曲線加密算法加/解密過程
a=4;
b=20;
p=29;
GX=13;
GY=23;
k=25;
[KX,KY]=NP(a,b,p,k,GX,GY);

r=6;

MX = 3;
MY = 28;

[rKX,rKY] = NP(a,b,p,r,KX,KY);

[C1X,C1Y]=Add(a,b,p,MX,MY,rKX,rKY);

[C2X,C2Y]=NP(a,b,p,r,GX,GY);


[kC2X,kC2Y]=NP(a,b,p,k,C2X,C2Y);

kC2Y=mod(-1*kC2Y,p);

[resx,resy]=Add(a,b,p,C1X,C1Y,kC2X,kC2Y)

在北太天元上執(zhí)行m腳本ECC
>>ECC
resx =
?? 3
resy =
?? 28
我們執(zhí)行一下可以看到輸出結(jié)果 resx=3,resy=28 。
這里的3正是Bob給Alice傳的數(shù)字內(nèi)容，其他人因?yàn)闆]有私鑰k所以無法像Alice
那樣簡單地還原出數(shù)字3

總結(jié)
橢圓加密算法看似簡單, 僅僅通過一個(gè)加法運(yùn)算和一個(gè)常量乘法運(yùn)算便完成了加密解密算法, 當(dāng)然背后的原來涉及到數(shù)學(xué)知識這里沒有討論。這個(gè)文章僅僅是起演示功能。
另外, 這里的代碼是從參考文獻(xiàn)的MATLAB代碼移植到北太天元上的，一行不改也是可以
運(yùn)行的。我修改了ECCPlot.m這么一行
plot(x,y,'*')
成了下面這么一行，這樣畫出的點(diǎn)更大
plot(x,y,'.','MarkerSize',50)

原來的代碼在北太天元上畫的圖是

參考: https://blog.csdn.net/alphags/article/details/79660819