王永恒

（上海中僑職業(yè)技術(shù)學(xué)院，上海，201316）

標(biāo)量乘算法屬于橢圓曲線運(yùn)算中最耗時(shí)同時(shí)也是最為重要的運(yùn)算之一，現(xiàn)階段應(yīng)用較為廣泛的標(biāo)量乘算法實(shí)現(xiàn)快速算法的方式包括二進(jìn)制法、m-ary 方法以及NAF 編碼等，其他還有窗口法和滑動(dòng)窗口法等。本文對(duì)上述算法做了細(xì)致的闡釋和討論，并基于并行運(yùn)算的理念，對(duì)于混合坐標(biāo)下點(diǎn)加點(diǎn)倍中的運(yùn)算序列進(jìn)行了改進(jìn)，以期能夠給使運(yùn)算序列高效實(shí)現(xiàn)并行運(yùn)算。

1 橢圓曲線密碼的研究意義

早在四千多年前，人們就已經(jīng)開始在軍事及外交通信中應(yīng)用密碼技術(shù)，然而其真正成為一門獨(dú)立的學(xué)科則是在1949 年，由學(xué)者Shannon 在其撰寫的“保密通信的信息理論”中被首次提出。在Shannon 提出之后，由于當(dāng)時(shí)人們的大數(shù)分解能力，只需要使用不太大的模數(shù)，如RSA 算法就已經(jīng)可以很安全，所以學(xué)界并沒有立即將橢圓曲線密碼當(dāng)作一種理論上的選擇，也未能引起人們的高度重視。但是即使如此，學(xué)界對(duì)于橢圓曲線密碼的研究卻一直再繼續(xù)，隨著研究的持續(xù)深入，人們開始總結(jié)出了一般的標(biāo)量乘法，也就是IEEEPl363，該種算法無論是在速度上，還是在安全性方面均取得了重大突破。然而，隨著攻擊能力的逐漸增強(qiáng)，基域也越來越多，標(biāo)量乘法的效率始終是橢圓曲線密碼得以順利應(yīng)用的一個(gè)關(guān)鍵條件，人們對(duì)密碼以及基于GAP 群的密碼的研究和應(yīng)用必須以高效的標(biāo)量乘法作為基礎(chǔ)。

新階段，人們始終未停止過對(duì)安全高效的標(biāo)量乘法的研究。不斷加大對(duì)于橢圓曲線密碼的研究力度，不僅具有重要的學(xué)術(shù)價(jià)值，也具有一定的現(xiàn)實(shí)意義。

2 橢圓曲線密碼體制的優(yōu)勢(shì)

和RSA 體制和EIGamal 類體制體制比較，本文所探討的橢圓曲線密碼的優(yōu)勢(shì)主要包括以下幾個(gè)方面：

第一，和所述其他兩種體制相比，其具有最強(qiáng)的單比特安全性。

第二，假設(shè)基域完全相同的條件下，其能夠擁有更多的可選擇性。

第三，能夠主動(dòng)選取基域中的素?cái)?shù)，從而能夠有效選取更加有利于計(jì)算機(jī)處理的素?cái)?shù)。

第四，其密鑰和系統(tǒng)參數(shù)均相對(duì)較小。

第五，對(duì)于帶寬的要求較低，適用性強(qiáng)。

3 橢圓曲線密碼體制中標(biāo)量乘算法的研究現(xiàn)狀

橢圓曲線上點(diǎn)的標(biāo)量乘法是橢圓曲線密碼體制得以順利實(shí)現(xiàn)的一個(gè)重要因素。所謂標(biāo)量乘法，實(shí)際上就是在橢圓曲線上點(diǎn)P 以及一個(gè)大整數(shù)k 一定的條件下，計(jì)算kp 的大小，話句話說，就是通過橢圓曲線上加法來對(duì)P 和自身進(jìn)行連續(xù)相加，相加次數(shù)為k 次。在實(shí)現(xiàn)橢圓曲線公鑰密碼體制的過程中，無論是加密環(huán)節(jié)，還是驗(yàn)證環(huán)節(jié)，其中均必須應(yīng)用標(biāo)量乘法。我們從近年來研究出的基于雙線性對(duì)的密碼體制來看，標(biāo)量乘法也在其中充當(dāng)了快速實(shí)現(xiàn)的基礎(chǔ)?，F(xiàn)階段，計(jì)算標(biāo)量乘算法的算法主要包括以下幾種：常用的如二進(jìn)制展開法、窗口法以及帶符號(hào)的二進(jìn)制法，其他還有m 進(jìn)制法以及帶符號(hào)的m 進(jìn)制法等。而其中又以IEEE P1363 標(biāo)準(zhǔn)中所推薦使用的投影坐標(biāo)條件下完全不連接形式的二進(jìn)制法應(yīng)用最為廣泛，同時(shí)也是最快的算法。

作為一種經(jīng)典且應(yīng)用較為廣泛的數(shù)學(xué)工具，橢圓曲線在密碼學(xué)界的應(yīng)用領(lǐng)域也較多，除了橢圓曲線公鑰密碼體系之外，在其他多種領(lǐng)域橢也同樣發(fā)揮著重要作用。當(dāng)前，橢圓曲線上的代數(shù)運(yùn)算，無論是在硬件還是在軟件上均得到了越來越高效的實(shí)現(xiàn)，也正是因?yàn)槿绱?，人們?duì)于利用橢圓曲線來構(gòu)造偽隨機(jī)序列的課題研究也越來越重視，并將其命名為橢圓曲線序列。

4 快速標(biāo)量乘算法在橢圓曲線密碼體制中的應(yīng)用

4.1 攻擊標(biāo)量乘算法

實(shí)際上，橢圓曲線密碼中最為基本的一個(gè)算法就是二進(jìn)制算法，同時(shí)其也是近年來改進(jìn)標(biāo)量乘算法的一個(gè)最為基本的算法，其所遭受到的邊信道攻擊也成為影響改進(jìn)成果的一個(gè)關(guān)鍵問題，而之所以造成這種攻擊的主要原因，就在于標(biāo)量乘的實(shí)現(xiàn)和密鑰k 之間存在著密切的關(guān)系。在該算法中，倍點(diǎn)運(yùn)算與點(diǎn)加運(yùn)算二者實(shí)現(xiàn)所需要的計(jì)算量存在著很大的差異，因此也就導(dǎo)致不同能量曲線的存在。對(duì)于標(biāo)量乘運(yùn)算的能量曲線，采用運(yùn)算的密鑰就可以將其破解。

用k 可來代表唯一的二進(jìn)制：

采取二進(jìn)制算法

由此可以推測(cè)出標(biāo)量乘運(yùn)算的AD 序列：DAIDAIDIDAIDI...

最終可以計(jì)算出密鑰為11010…

定義：如果攻擊者可以借助一個(gè)單獨(dú)的標(biāo)量乘來計(jì)算出能量曲線區(qū)分點(diǎn)加和倍點(diǎn)，那么我們就可以認(rèn)為攻擊者具有了點(diǎn)加與倍點(diǎn)可區(qū)分，又可以稱之為AD 可區(qū)分。

定理：分析二進(jìn)制算法對(duì)于能量曲線實(shí)現(xiàn)的過程，可以得出AD 可區(qū)分的攻擊者可以獨(dú)立實(shí)現(xiàn)私鑰k 的推出。

證明：通常情況下，點(diǎn)加與私鑰的非零位之間存在著密切的關(guān)系。舉例來說，在二進(jìn)制算法中，(1101)2P=13P 所對(duì)應(yīng)AD 序列是：ADADDA。其中，DA 和1 二者互為對(duì)應(yīng)，獨(dú)立的D 則和0 之間存在著對(duì)應(yīng)關(guān)系：這個(gè)序列完成表明了私鑰k=13。為了可以得到明確的私鑰中非零位的具體區(qū)域，攻擊者可以有效識(shí)別點(diǎn)加的能量信號(hào)，話句話說即：在能量曲線上可以有效分辨出點(diǎn)加與倍點(diǎn)所表現(xiàn)出來的不同形狀。

4.2 標(biāo)量乘算法的馬爾科夫模型

關(guān)于攻擊者的能力，可以做出一些假定，具體如下：

(1)假設(shè)標(biāo)量乘運(yùn)算的所有執(zhí)行的邊信道軌跡均能夠獲得：

(2)假設(shè)在軌跡中，可以清楚的分辨出點(diǎn)加運(yùn)算與倍點(diǎn)運(yùn)算；

(3)假設(shè)標(biāo)量乘算法為已知。

首先，攻擊者需要結(jié)合邊信道軌跡而對(duì)出倍點(diǎn)以及點(diǎn)加序列做出較為準(zhǔn)確的推測(cè)?？梢允褂脅A，D)所構(gòu)成的字母序列來進(jìn)行表示，其中最左邊的字母對(duì)應(yīng)的運(yùn)算應(yīng)當(dāng)是最先運(yùn)行的。對(duì)于攻擊者來說，其根本目標(biāo)是利用在得到的AD 序列基礎(chǔ)上而推測(cè)出私鑰k。需要注意的是，由于相同的AD 序列所對(duì)應(yīng)的私鑰實(shí)際上是存在差異的，所以，其次就應(yīng)當(dāng)是確定出所有可能的密鑰，形成密鑰集合。再次，通過對(duì)密鑰集合的觀察和分析，來找到正確的密鑰。

在這一過程中，對(duì)于條件概率的計(jì)算存在著較大的難度，其較為復(fù)雜。不過可以通過計(jì)算X 以及Y 的子序列來進(jìn)行實(shí)現(xiàn)，其中還需應(yīng)用到標(biāo)量乘算法特殊狀態(tài)中的概率問題。而對(duì)于這些概率的計(jì)算則可以利用馬爾科夫鏈來進(jìn)行。

計(jì)算中可以將標(biāo)量乘算法視為馬爾科夫鏈。

定義：假設(shè)T 表示的是k×k 矩陣，其中的元素用pij 來表示，同時(shí)滿足1 ≤i，j ≤k 的條件。一個(gè)有限狀態(tài)空間為｛s1，s2，......，sk｝的隨機(jī)過程｛X0，X1，......｝，可以將其命名成轉(zhuǎn)變矩陣為T 的馬爾科夫鏈。

從中我們能夠推出公式：

馬爾科夫鏈狀態(tài)間所進(jìn)行的轉(zhuǎn)變被隨機(jī)變量決定，同時(shí)會(huì)以一定的概率的形式來出現(xiàn)，而這個(gè)概率可以是已知的，也可以是需要通過計(jì)算而得出的。馬爾科夫鏈具有兩個(gè)關(guān)鍵特征，一個(gè)是不可約性，一個(gè)是非周期性。前者表明了每個(gè)狀態(tài)都能夠在有限步在之內(nèi)通過其他狀態(tài)來實(shí)現(xiàn)。后者則表明所有狀態(tài)實(shí)際上均沒有周期。我們假設(shè)一個(gè)狀態(tài)的周期是l，也就意味著這個(gè)狀態(tài)屬于非周期的，兩者共同構(gòu)成了馬爾科夫鏈基本原理的重要條件。在對(duì)于這個(gè)基本原理進(jìn)行描述之前，首先需要確定固定分布的概念：

定 義：令｛X0，X1，......｝是｛s1，s2，......，sk｝與T 之間的馬爾科夫鏈。那么滿足

定理：所有不可約以及非周期馬爾科夫鏈，均具有唯一的固定分布π 以及鏈的任意分布，如果n 趨近無窮時(shí)接近π，那么我們就可以判定這個(gè)與初始分布和之間不存在任何關(guān)系。從中我們可以看出馬爾科夫過程帶有不可約性以及非周期性兩種性質(zhì)。需要注意的是，該算法的初始條件應(yīng)當(dāng)滿足馬爾科夫過程的初始狀態(tài)為（1，0，0）。

基于此，我們認(rèn)為穩(wěn)定狀態(tài)僅為兩個(gè)狀態(tài)后達(dá)到，而馬爾科夫過程則屬于不可約的，究其原因，主要在于狀態(tài)轉(zhuǎn)變圖中并不存在不連接的區(qū)域。由于其回到狀態(tài)的概率都是正的，所以我們可以得出馬爾科夫過程為非周期的。

4.3 馬爾科夫鏈增強(qiáng)

(1)預(yù)計(jì)算階段

首先，我們需要找到馬爾科夫模型，接著再找到轉(zhuǎn)變矩陣以及穩(wěn)定狀態(tài)向量，然而找到給定的標(biāo)量乘算法。最后對(duì)于全部的X 和Y 組合的條件概率來進(jìn)行分析和計(jì)算.

(2)數(shù)據(jù)收集階段

主要是根據(jù)邊信道軌跡情況來分析得出AD 序列.

(3)數(shù)據(jù)分析階段

從已經(jīng)得到的AD 序列中分成一些子序列，也就是我們通常所說的比特樣品.

(4)密鑰測(cè)試階段

根據(jù)已知明文以及密文對(duì)，來對(duì)于前面所得出的全部比特樣品的組合來進(jìn)行測(cè)試。最后計(jì)算出短密鑰。

由此可以得到以下定理:

定理：如果處于最壞的情況，那么我們就只需要關(guān)注非零條件概率。這種條件下，研究者至多測(cè)試的密鑰數(shù)量為，測(cè)試的平均密鑰數(shù)量為

定理：如果處于平均情況，那么就只需要關(guān)注條件概率。

5 結(jié)語

ECC 是基于橢圓曲線上離散對(duì)數(shù)難題的一種公鑰密碼系統(tǒng)，然而從本質(zhì)上來看，其只是已有密碼體制的一個(gè)翻版，其單比特安全性遠(yuǎn)遠(yuǎn)超出其他密碼體制。處于同樣的安全強(qiáng)度條件下，和其他密碼體制相比，其具有密鑰長度短、計(jì)算量小以及存儲(chǔ)量小等優(yōu)勢(shì)，其對(duì)于帶寬需求不過。因而，當(dāng)前ECC 在全球范圍內(nèi)均得到了廣泛應(yīng)用，被認(rèn)為是本世紀(jì)最重要的一種公鑰密碼體制。

總之，ECC 的高比特安全性以及低內(nèi)存、低帶寬要求等優(yōu)勢(shì)滿足了當(dāng)代社會(huì)對(duì)便攜設(shè)備安全性的需要，今后隨著人們對(duì)其物理安全性關(guān)注度的日益提高，對(duì)于邊信道攻擊中的能量攻擊對(duì)標(biāo)量乘法所構(gòu)成的安全性威脅也越來越重視，能量攻擊能夠避開算法數(shù)學(xué)層的安全性，而直接通過硬件本身的能量消耗發(fā)揮作用，進(jìn)而對(duì)設(shè)備內(nèi)部的密碼系統(tǒng)構(gòu)成不同程度的攻擊。在這種情況喜愛，研究ECC 的快速實(shí)現(xiàn)以及抵抗邊信道攻擊中的能量攻擊，對(duì)進(jìn)一步促進(jìn)ECC 的推廣應(yīng)用具有十分重要的作用。

[1] Katsuyuki Okeya and Tsuyoshi Takagi.The width-W NAF method provides small memory and fast Elliptic Scalar multiplications secure against side channel attacks[J].CT-RSA2003，LNCS 2612,pp 328～343.Springer-Verlag,2003.

[2] Chae Hoon Lim ANew Method for Securing Elliptic Scalar Multiplication Against Side-Channel Attacks[J].ACISP 2004，LNCS 3108,pp 89-300. Springer-Verlag Berlin Heidelberg,2004.

[3] 郝林,羅平.橢圓曲線密碼體制中點(diǎn)的數(shù)乘的一種快速算法[J].電子與信息學(xué)報(bào),2003,25(2)：275～278.

[4] 韓軍,曾曉洋,湯庭鰲.RSA 密碼算法的功耗軌跡分析及其防御措施[J].計(jì)算機(jī)學(xué)報(bào),2006,29(4)：590～596.

[5] 劉鐸,戴一奇,王道順.平穩(wěn)與平衡一橢圓曲線密碼體制抗旁信道攻擊的策略與手段[J].計(jì)算機(jī)研究與發(fā)展,2005,42(10)：1667～1672.