第七章椭圆曲线密码系统.doc

第七章　橢圓曲線密碼系統 本章摘要 7.1　橢圓曲線定義 7.2　橢圓曲線運算規則 7.3　橢圓曲線密碼演算法 7.4　橢圓曲線共用秘密推導機制 7.5　橢圓曲線數位簽章機制 7.6　小結 本章前言 橢圓曲線密碼系統是由Neil Koblitz(Koblitz, 1985)和Victor Miller(Miller, 1985)兩位學者分別於1985年首先提出，大多數的橢圓曲線密碼系統是在模或下運算。此密碼系統仍是存有RSA或ElGamal常見的弱點(e.g. 同模數攻擊、低指數攻擊)。RSA與ElGamal系統中需要使用長度為1024位元的模數，才能達到足夠的安全等級，而ECC只需使用長度為160位元的模數即可，且傳送密文或簽章所需頻寬(bandwidth)較少，並已正式列入IEEE 1363標準。 學習路徑 橢圓曲線密碼系統植基於橢圓曲線離散對數問題(Elliptic Curve Discrete Logarithm Problem, ECDLP)。即在有限體K之下，給定橢圓曲線E上的兩相異點P及Q，其中當點P的秩(order)若夠大時(大於160位元)，要找出一整數l使得是很難的計算難題。 本章主要探討橢圓曲線定義、橢圓曲線運算規則、橢圓曲線密碼演算法、橢圓曲線共用秘密推導機制，與橢圓曲線數位簽章機制。在橢圓曲線定義方面，分別介紹橢圓曲線所運用之數學理論，並說明其在幾何學上的意義。在橢圓曲線運算規則方面，將探討橢圓曲線在模與下的運算規則。在橢圓曲線密碼演算法方面，將說明Koblitz與Menezes-Vanstone橢圓曲線密碼系統(Menezes Vanstone, 1993)。在橢圓曲線共用秘密推導機制，介紹IEEE 1363中ECSVDP-DH、ECSVDP-DHC、ECSVDP-MQV，與ECSVDP-MQVC。在橢圓曲線數位簽章機制，介紹IEEE 1363中簽章產生機制(ECSP-NR, ECSP-DSA)與驗證機制(ECVP-NR, ECVP-DSA)。 本章內容 7.1 橢圓曲線定義 在實數系中，橢圓曲線可定義成所有滿足方程式的點所構成的集合。若方程式沒有重複的因式或 ，則能成為群(group)。例如，橢圓曲線的圖形如圖7-1所示。若，則此曲線將會形成退化(某些數的反元素(inverse)將不存在)。 圖7-1 橢圓曲線之圖形 橢圓曲線密碼系統在模(或)下定義為橢圓曲線，其中；模下定義為橢圓曲線，其中，此曲線稱為nonsuper-singular。橢圓曲線有一個特殊的點，記為O，它並不在橢圓曲線E上，此點稱為無限遠的點(the point at infinity)。為在K之下橢圓曲線E上所有的點所構成的集合，點對X座標軸反射的點為，而稱為點的負點。若且n為最小的正整數，則n為橢圓曲線E上點的秩。除了無限遠的點O之外，橢圓曲線E上任何可以生成所有點的點都可視為是E的生成數(generator)，但並不是所有在E上的點都可視為生成數。以下我們將介紹橢圓曲線運算在幾何學上的定義。包括兩個相異的點相加與雙倍(doubling)的點P，分別說明如下。 兩個相異的點相加：假設P和Q是橢圓曲線上兩個相異的點，而且不等於。若，則點R是經過P、Q兩點的直線與橢圓曲線相交之唯一交點的負點。如圖7-2所示。 雙倍的點：令，則點2P是經過P的切線與橢圓曲線相交之唯一交點的負點。如圖7-3所示。 圖7-2 兩個相異的點相加 圖7-3 雙倍的點 7.2 橢圓曲線運算規則 本節將探討橢圓曲線在模與下的運算規則，並輔以實例加以說明。 ※ 橢圓曲線在模p下的運算規則 加法規則： (i) 對所有的點，則， (ii) 令及，且，則，其中， (iii) 如果，則對所有的點而言， 乘法規則： 如果，則對所有的點而言， (ii) 如果，則對所有的點而言， 例子1：有限體之下，點是橢圓曲線的生成數。 P = (0, 1) 2P = (13, 13) 3P = (5, 5) 4P = (3, 15) 5P = (6, 17) 6P = (19, 2) 7P = (17, 9) 8P = (18, 0) 9P = (17, 14) 10P = (19, 21) 11P = (6, 6) 12P = (3, 8) 13P = (5, 18) 14P = (13, 10) 15P = (0, 22) [說明]： 圖7-4 橢圓曲線生成數說明圖(模p下) 註：；點P的秩n = 16。 例子2：在有限體之下，取橢圓曲線上的兩點　及。若，則R = ? [說明]： 圖7-5 橢圓曲線加法運算說明圖(模p下) 例子3：承例子2，若，則R = ? [說明]： 圖7-6 橢圓曲線雙倍運算說明