公開密鑰加密算法總是基于一個數(shù)學(xué)上的難題，比如RSA加密算法的安全性基于數(shù)論中大素?cái)?shù)分解的困難性，所以，RSA需采用足夠大的整數(shù)。因子分解越困難，密碼就越難以破譯，加密強(qiáng)度就越高。橢圓曲線加密算法的提出正好可以解決這個問題，其依據(jù)就是定義在橢圓曲線點(diǎn)群上的離散對數(shù)問題的難解性。

一、橢圓曲線加密算法

1、橢圓曲線基本協(xié)議

設(shè)橢圓曲線為E(Fq)，在加法群中的階為n，我們設(shè)點(diǎn)P0(1，1)為該橢圓曲線上的點(diǎn)，A和B為進(jìn)行通信的雙方用戶。該橢圓曲線上的消息加密及解密協(xié)議如下：

設(shè)素?cái)?shù)p和q滿足q=p；A的公鑰為點(diǎn)Pa=ka×P0，私鑰為ka；B的公鑰為點(diǎn)Pb=kb×P0，私鑰為kb；m為消息。

(1)隨機(jī)產(chǎn)生k，計(jì)算(x,y)=k×Pb；計(jì)算R=k×P0；計(jì)算c=m×x(modp)；發(fā)送密文(R,c)->b。

(2)計(jì)算(x,y)=kb×R；計(jì)算m=c÷x(modp)，m即為經(jīng)由解密得到的明文。

2、橢圓曲線加密體制中的有關(guān)計(jì)算

作為公開密鑰加密算法的一種，橢圓曲線加密體制要用到點(diǎn)乘、點(diǎn)加、模乘、模加、模逆、模冪這些基本運(yùn)算，點(diǎn)加和點(diǎn)乘屬于橢圓曲線群上的運(yùn)算，它們的執(zhí)行速度直接決定著橢圓曲線的加密速度。為了提高速度，可從采用高速算法或?qū)崿F(xiàn)并行性兩方面解決。

二、大數(shù)計(jì)算的典型算法

對于大數(shù)，大家比較關(guān)心的是整型數(shù)據(jù)類型，因此僅對整型數(shù)據(jù)類型部分展開討論。

1、大數(shù)的常規(guī)運(yùn)算的實(shí)現(xiàn)

對于加減法運(yùn)算，通過將A、B按位對齊；低位開始逐位相加(減)；對結(jié)果做進(jìn)進(jìn)(借)位調(diào)整即可實(shí)現(xiàn)。乘法運(yùn)算引入sum2、sum1作為中間量；在n的每一位上處理m；通過每一層循環(huán)，實(shí)現(xiàn)乘法的加法化；對結(jié)果做進(jìn)借位調(diào)整。出發(fā)運(yùn)算則要引入al來標(biāo)識a的長度，bl來標(biāo)識b的長度；測算a和b的長度；從高位開始，對位做減法，并完成借位；然后高位開始逐位計(jì)算商并整理商，產(chǎn)生余數(shù)。余數(shù)也可作為取模的結(jié)果。

2、大數(shù)模乘算法

大數(shù)模乘算法在密碼學(xué)領(lǐng)域有廣泛的應(yīng)用，它是公鑰密碼的基本運(yùn)算。模乘一般表示為：C=(AB)modN,0≤A,B<N，其中A、B、N都為k比特二進(jìn)制大整數(shù)。

以下是目前具有代表性的幾種大數(shù)模乘算法：

（1）Blakley的加法型模乘算法

Blakley算法每次計(jì)算都對累加中間結(jié)果C進(jìn)行模簡化，以使結(jié)果小于N。Blakley算法不含乘法和除法，但加法法和模簡化過程只能逐位處理,實(shí)現(xiàn)效率不夠理想。針對Blakley算法，人們相繼提出了不少改進(jìn)方法，這些改進(jìn)主要可分為二大類：減少乘法過程的加法次數(shù)，即減少乘數(shù)中非0個數(shù)；提高模簡化速度等。F.E.Su和T.H.Wang于1996年提出了一種無需大數(shù)比較而直接將C限制在范圍內(nèi)的模簡化方法，明顯提高了效率。圍繞減少加法次數(shù)，Koc利用窗口技術(shù)，通過以m位為一組結(jié)合冗余二進(jìn)制數(shù)方法從右到左對乘數(shù)重編碼和預(yù)計(jì)算，提出了窗口模乘算法。不久又出現(xiàn)了有符號滑動窗口模乘算法和無符號滑動窗口模乘算法，也是目前較為理想的加法型模乘算法。

（2）Knuth算法

Knuth算法的優(yōu)點(diǎn)是將商計(jì)算轉(zhuǎn)化為一個25位數(shù)與t位數(shù)的除法，由于算法中仍含除法，實(shí)現(xiàn)效率受影響較大。1987年Barrett提出了第一種無除法的估商型模乘算法，其基本思想是用乘法和預(yù)計(jì)算替代除法。Barrett算法的最大優(yōu)點(diǎn)在于整個計(jì)算不含除法，僅用最基本的字乘和字加即可完成。1992年Quisquater提出了另一種估商型模乘算法，其特點(diǎn)是可快速進(jìn)行商計(jì)算，后來Walter亦提出了類似的思想。Quisquater算法進(jìn)一步簡化了估商計(jì)算，但整個模冪過程中需附加一次歸范化和反歸范化計(jì)算。

（3）Montgomery算法

Montgomery算法采用模加右移法，避免了公鑰加密中求模算法的除法運(yùn)算，使運(yùn)算量大為減少。Montgomery算法不含除法，基本運(yùn)算為字乘和字加，通過剩余系轉(zhuǎn)換方法計(jì)算模乘，極大地提高了模乘計(jì)算速度，被廣泛應(yīng)用于各種軟硬件實(shí)現(xiàn)中，人們也從高效率、低空間、高安全等角度對算法進(jìn)行了各種改進(jìn)。Montgomery型算法最后都需對作一次條件減法，由于不同乘數(shù)所耗費(fèi)的時間和能量不同，給時間攻擊、能量攻擊及電磁攻擊留下了余地，為此Walter、Hachez和Quisquater通過深入研究，提出了一種可有效阻止這些攻擊的Montgomery型無減法模乘算法，而且實(shí)現(xiàn)效率也相當(dāng)理想。

3、大數(shù)分解

大數(shù)分解問題涉及到高可信度的計(jì)算問題及很多數(shù)學(xué)技術(shù)的進(jìn)一步研究和運(yùn)用，包括信息論，競爭的復(fù)雜性等。數(shù)論學(xué)者和計(jì)算機(jī)學(xué)者已經(jīng)得到了許多實(shí)際有效的方法并已經(jīng)引起人們的普遍關(guān)注。大數(shù)分解質(zhì)因子問題涉及到了素?cái)?shù)判別和大數(shù)分解兩方面的內(nèi)容。

而進(jìn)行素?cái)?shù)判別和大數(shù)分解最直接的方法就是試除法，即對于整數(shù)n來說，用2,…,n-1去試除，然后判定n是否素?cái)?shù)，分解式是什么。作為最簡單的一個方法，試除法對較大的數(shù)(20位左右)進(jìn)行分解是要耗費(fèi)很多時間。費(fèi)馬方法給定n，若n是兩數(shù)平方差n=a2-b2，則n=(a+b)(a-b)是n的一個因子分解，但該方法只有當(dāng)n有兩個幾乎相等的因子時，才比較快。

三、橢圓曲線加密的實(shí)現(xiàn)

encryptogram()//加密

{

inti;time_tt;

srand((unsigned)time(&t));

rando(p2);

intproduct〔301〕,quo〔301〕,arith〔201〕;

for(i=1;i<301;i++)　product〔i〕=0;multiply(p1,p2,product);

rando(p3);

division(product,p3,quo,arith);

intp4〔101〕,prod〔301〕;

random(p4);

for(i=1;i<301;i++)prod〔i〕=0;

multiply(p4,arith,prod);

}

decryptogram()//解密

{

intpro〔301〕,qu〔301〕,arit〔201〕,q〔301〕,ari〔201〕;

for(i=1;i<301;i++)pro〔i〕=0;

multiply(p1,p2,pro);

division(pro,p3,qu,arit)division(prod,arit,q,ari);

return0;

}

admin

收藏 海報(bào)分享