[發明專利]橢圓曲線密碼系統的點加系統

無效

• 申請號: 200810055610.6
• 申請日: 2008-01-04
• 公開（公告）號: CN101221491A
• 公開（公告）日: 2008-07-16
• 發明（設計）人: 李樹國;張霄鵬
• 申請（專利權）人: 清華大學
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及數字簽名與認證技術領域。

背景技術

密碼體制可以分為傳統(或對稱)加密體制和公鑰(或非對稱)加密體制兩類。1976年W.Diffie和M.E.Hellman提出了公鑰密碼的概念，對整個密碼學發展造成了深遠的影響。當前廣泛應用的公鑰密碼系統是RSA，其優點在于原理簡單，使用方便。但隨著大整數因子分解方法的不斷改進以及計算機性能的不斷提升，要保證RSA的安全性所需要的密鑰位數不斷增長，目前一般認為RSA密鑰的位數在1024bit以上才有安全保障。密鑰位數的增加直接導致了加解密速度的大幅下降以及硬件開銷的加大。

橢圓曲線密碼(ECC)是1985年由N.Koblitz和V.Miller提出的，它是利用有限域上的橢圓曲線有限群代替離散對數問題中的有限循環群后得到的一類密碼體制。由于橢圓曲線密碼具有安全性能高，處理速度快，帶寬要求低和存儲空間小等特點，與RSA相比，ECC在密鑰長度和運算速度上具有優越性。

素域上的橢圓曲線E(F_p)由Weierstrass方程定義：

E：y²＝x³+ax+b(modp)????(1)

其中p是素數，a，b為兩個小于p的非負整數(0＜a，b＜∞)，且滿足

4a³+27b²(modp)≠0????(2)

方程(2)基于集合E_p(a，b)可定義一個有限Abel群。

在橢圓曲線密碼體制中，核心運算是點乘(kP)，我們可以將點乘分解為兩種基本運算：點加(ECPADD)以及倍點(ECPDBL)，點加和倍點運算可以采用不同的坐標系來實現。常用的坐標系是仿射坐標系和Jacobi投影坐標系。以下分別介紹仿射坐標系和Jacobi投影坐標系。

仿射坐標系：平面上過一定點O作兩條相交的軸x和y，它們的交角是ω.以定點O為原點，在每條軸上取長度單位(分別是OE₁、OE₂)，這樣就在平面上建立了一個仿射坐標系，如圖1所示。對于平面上任一點M，過M作兩軸的平行線，與兩軸分別交于M₁、M₂，它們在兩軸的坐標分別是x、y，于是點M就對應有序數組(x，y)。

Jacobi投影坐標系：Jacobi投影坐標系下的點(X，Y，Z)和仿射坐標系下的點(x，y)一一對應，且滿足x＝X/Z²、y＝Y/Z³。給定仿射坐標系下的坐標(x，y)，轉換成Jacobi投影坐標系下的坐標為(X，Y，Z)，其中X＝x、Y＝y、Z＝1；給定Jacobi投影坐標系下的坐標(X，Y，Z)，轉換成放射坐標系下的坐標為(x，y)，且滿足x＝X/Z²、y＝Y/Z³。同時，仿射坐標系下的無窮遠點和Jacobi投影坐標系下的點(1，1，0)對應。

以下介紹素數域橢圓曲線點加和倍點在仿射坐標系下的定義：

點加定義：

如圖2所示，在橢圓曲線上取兩點P(x₁，y₁)和Q(x₂，y₂)，令O點表示無窮遠點。計算

R＝P+Q稱為倍點運算，其中R坐標為(x_R，y_R)。

1)如果x₁＝x₂且y₁＝-y₂，則R＝P+Q＝O。

2)若1)條件不成立，則有點R＝P+Q，滿足