基于滑动窗口技术的有限域GF(2n)乘法算法_

摘要：在分析现有有限域GF(2n)乘法算法的基础上，将滑动窗口技术应用到有限域GF(2n)的乘法运算中，提出了一个基于滑动窗口技术的有域GF(2n)乘法算法，分析和仿真结果表明，与被认为目前最快的有限域GF(2n)乘法算法——固定窗口算法相比，该算法有更好的实现效率。
关键词：有限域GF(2n)乘法运算；滑动窗口算法；固定窗口算法；椭圆曲线密码
1引言
1985年，Neal Koblitz和Victor Miller分别独立地提出了椭圆曲线密码(ECC)体制。因其具有更高的安全性、计算量小、存储空间占用小、带宽要求低等突出优点使得其具有广泛的应用前景，尤其是在IC卡、无线网络等领域具有广泛的应用前景，被认为是最值得关注的密码体制，是目前信息安全领域研究的一个热点。由于ECC的运算是基于有限域运算的，从而有限域运算的有效实现是有效实现ECC的重要的先决条件[1]，其中有效的乘法运算是有效实现ECC的关键之一。
ECC的有效实现主要用到3种域：素域GF(p)、二进制域GF(2n)和最佳扩域(OEF)。但从方便实现来看，二进制域是最有吸引力的，其运算只涉及移位（SHIFT）和按位的模2加（XOR），这在通用处理器上用软件实现是十分诱人的。有限域GF(2n)上乘法运算的最基本算法是shift-and-add算法，Koc与Acar在文献[2]中给出了一种应用在有限域GF(2n)上的Montgomery算法，其实现要么依赖于特定的处理器（Emulation方法），要么需要较大的辅助存储空间（查表法），导致其难于实现。C.Lim和P.Lee在文献[3]中给出了comb乘法算法,由于它大大减少了移位运算次数，其效率明显优于shift-and-add算法，在此基础上，J.López与R.Dahab在文献[4]中将固定窗口技术应用到有限域GF(2n)的乘法运算上，提出了一种新的乘法算法（以下简称其为固定窗口算法），其运算效率比shift-and-add算法的运算效率快大约3~5倍，被认为是目前有限域GF(2n)上乘法运算最快的算法之一[1]。
本文在充分分析上述乘法算法的基础上，将滑动窗口技术应用到有限域GF(2n)上的乘法运算中，提出了一个关于有限域GF(2n)上乘法运算的新算法。分析和仿真结果表明，与固定窗口算法相比，该算法的实现效率提高了20%~25%，并且不需使用更多的存储空间。构成有限域GF(2n)的最常用的2种方法是采用正规基表示法和采用多项式基表示法，正规基表示法更适合于硬件实现[5]，本文采用多项式基表示法构成域GF(2n)，在这种表示法中，域GF(2n)的元素是次数最多为n?1次的二进制多项式.J.López与R.Dahab扩展了C.Lim和P.Lee所提出的comb算法，下面介绍J.López与R.Dahab提出的固定窗口算法（FWA）。
FWA在进行每一次计算时，不是按位而是按照一定宽度w(w>1)的块来进行处理的算法。上述算法虽然比shift-and-add算法要快大约3~5倍，但是它需用一定的内存空间来存储预计算结果，所以在内存受限的应用领域（如智能卡等）该算法就无法得到有效应用。下面将采用滑动窗口技术设计有限域GF(2n)的乘法算法。
我们所设计的基于滑动窗口技术的有限域GF(2n)乘法算法的效率与窗口间隔紧密相关，窗口间隔越大，计算量就越小，其效率也就越高。为提高算法效率，需将表示域元素的正数二进制序列转化为带符号的二进制序列。尽管目前计算有限域GF(2n)上的乘法有shift-and-add算Montgomery算法、comb算法、FWA等，但从其效率来说，FWA的效率明显优于其他几种，从而在本节将仅就上述所设计的SWA与FWA的效率进行较。由于两者取模运算的次数相同，并且可以使用同一种取模运算算法，因此不考虑取模运算对双方的影响，主要比较2个算法需要的异或（XOR）运算、移位（SHIFT）运算次数。以下分析中z、k、n的含义同前，并用w表示窗口最大宽度，s表示上述设计的算法中的窗口数。显然，FWA需要k(11+n/4)次异或运算和3+2(z/4?1)次k字移位运算。而新算法需要s次异或运算和s?1次k字移位运算。有限域GF(2n)上乘法运算是影响椭圆曲线密码有效实现的关键技术之一，本文在充分分析现有乘法算法的基础上，将滑动窗口技术应用到有限域GF(2n)上的乘法运算中，提出了一种关于有限域GF(2n)上乘法运算的新算法（SWA）。理论分析和仿真结果表明，所得算法适合于定义在二进制域GF(2n)上ECC的软件实现，并有较好的实现效率且不需使用更多的存储空间。

文章来自：滑模机械网

文章作者：信息一部

『新闻推荐』

『关闭窗口』

网站建设 | 广告刊登 | 汇款说明 E-mail: admin@chinasfm.com 技术支持:简双工作室
电话：0371-69131532 传真：0371-63942657-8001
版权说明：本站部分文章来自互联网，如有侵权，请与信息处联系