[發明專利]使用混合仿射雅可比坐標進行ECC點加的硬件架構和方法

有效

• 申請號: 201410787996.5
• 申請日: 2014-12-17
• 公開（公告）號: CN104731552B
• 公開（公告）日: 2018-11-16
• 發明（設計）人: 米洛斯拉夫·科內澤維奇;韋茨斯拉夫·尼科夫
• 申請（專利權）人: 恩智浦有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72;G06F21/60
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 王波波

一種引入了簡單算術處理器的優化的硬件架構和方法，所述優化的硬件架構和方法允許高效地實現針對混合仿射雅可比坐標的橢圓曲線密碼學點加算法。此外，優化的架構減少了對中間值的所需存儲。

背景技術

電子設備正成為日常生活無處不在的部分。所用的智能電話和個人平板計算機的數目正在迅速增長。越來越多地使用智能電話和個人平板電腦的副作用在于設備被越來越多地用于存儲諸如個人和銀行數據等的機密數據。保護這種數據不被竊取是十分重要的。

密碼學領域提供用于使這種機密數據保持安全的保護工具。基于難以解決數學問題，密碼學通常需要較高計算強度的計算，所述較高計算強度的計算是在云計算和普適計算(ubicomp)中更廣泛應用的主要障礙。如果無法足夠快速地執行密碼操作，則通常不接受將密碼學工具用于互聯網。為了在提供安全性和數據完整性的同時使密碼工具是透明的，密碼學工具需要遵循由于移動應用中對高速度和低功耗的需求而推動的趨勢。

通常，公鑰算法是密碼學中計算最密集的計算。例如，以橢圓曲線密碼學(ECC)，即，計算效率最高的公鑰算法之一，為例。256位版本的ECC提供等同于128位對稱密鑰的安全性。256位ECC公鑰應提供與3072位RSA公鑰可比的安全性。ECC的基本運算是點乘，點乘是大量基于模乘的運算，即，執行一個ECC 256點乘需要大約256 位整數的3500個模乘。更高安全性等級(更大位整數)需要甚至更多的計算工作。

構建ECC的高效實現方式通常是有意義的，并且涉及多個階段。圖1示出了實現橢圓曲線數字簽名算法(ECDSA)所需的階段101、 102和103，所述ECDSA是ECC的應用之一。階段101處理包括模加、模逆和模乘的有限域算術。階段102處理點加和點倍(pointdoubling)，包括聯合稀疏形式(JSF)、非相鄰形式(NAF)、加窗和投影坐標。最后，階段103處理ECDSA以及數字簽名的接受或拒絕。

可以將任意橢圓曲線寫成由以下形式的方程定義的平面幾何曲線(假定系數域的特性不等于2或3)：

y²＝x³+ax+b ((1)

該方程是非奇異的；也就是說，該方程沒有尖端(cusp)或自相交，公知為短維爾斯特拉斯(Weierstrass)形式，其中，a和b是整數。通常在例如由NIST、SEC和ANSI頒布的若干標準中使用a＝-3的情況，這使得該情況成為通常感興趣的情況。

在用于高效實現點加(PADD)和點倍(PDBL)運算的文獻中，已經提出了許多算法。對這些算法中的很多算法進行優化以便軟件實現。雖然它們通常在特定平臺上是高效的，但是一旦調整底層硬件以適應算法，則該算法通常不是最優的。

Cohen、Miyaji以及Ono在Proceedings of the International Conference onthe Theory and Applications of Cryptography and Information Security；Advancesin Cryptology,ASIACRYPT 1998,pages 51-65,Springer-Verlag,1998中已經描述了混合仿射雅可比 (affine-Jacobian)坐標的PADD算法。雅可比坐標是投影坐標，每個點被表示為三個坐標(X,Y,Z)，其中x＝X/Z²、y＝Y/Z³，仿射坐標是常見的(x,y)坐標。應注意坐標都是整數。PADD算法200需要8個模乘、3個模平方、6個模減以及一個與2模乘，如圖2所示。為了執行PADD，該算法還需要最少4個臨時寄存器，其中對于ECC 256位，每個寄存器需要256位大小。在有限域K內進行所有運算，其中橢圓曲線E被定義在有限域K上。通過質數p定義有限算術域K，使得以 p為模執行所有算術運算。加性單位元素是無窮遠點。

發明內容