第30卷 第17期Vol.30 № 17
・开发研究与设计技术・
计 算 机 工 程Computer Engineering
文章编号：1000—3428(2004)17 —0184 —02
2004年9月September 2004
中图分类号：TN918
文献标识码：A
有限域逆元算法的实现
刘文江，董 威，戎蒙恬
(上海交通大学信息安全学院，上海200030)
摘 要：在扩展欧几里得算法的基础上提出了有限域乘法逆元的计算方法。给出了该算法的硬件结构图。该算法的优点是其时间复杂度和空间复杂度较优，便于VLSI 的实现。关键词：有 限域；乘法逆元；椭圆曲线；欧几里得
Implementation for Computing Division in Galois Fields
LIU Wenjiang, DONG Wei, RONG Mengtian
(College of Information Security, Shanghai Jiaotong University, Shanghai 200030)
【Abstract 】An implementation for computing multiplicative inverses in Galois fields GF(2m ) is presented. The algorithm is based on a modification of Euclid's algorithm. The architecture of circle for VLSI is also presented.【Key words】Finite field; Multiplicative inverse; ECC; Euclid
随着非对称密码学的发展，椭圆曲线（ECC ）密码学因数器的变化。
表1 寄存器和计数器数据为其独特的优势，渐渐取代RSA 在非对称密码学中的地位，
现在ECC 广泛使用在无线通信和Smart 卡中，完成加密、签Signals Registers Counter 名等功能。ECC 的优势在于它可以使用比RSA 少得多的比特r m s m Delta=0R S U V Delta 数目的密钥达到同样的保密效果。尽管这样，ECC 中的密钥0X X x.R S x.U V Delta+1长度还是比较大的，实际应用中的密钥长度有192、256等100s.S R x.V U Delta+1不同等级，应用中涉及到大数的存储和运算，因此对空间和101R x.S U/xV Delta-1
时间的要求特别高，本文充分考虑了二者的复杂度，提出了110x.(S-R)R x.(V-U)U Delta+1扩展欧几里得算法，具有很好的效果。1R x.(S-R)U/xV-U Delta-1111 欧几里得算法
简化上表, 同时引进两个变量T 和W, 这两个变量的值是:
有限域GF （2m ）是包含了2m 个元素的代数系统，该系统
T
＝S W＝V rm ＝0 s或者m ＝0
的每个元素都能够表示成小于m 次的多项式，该多项式的每
T ＝S －R W＝V －U rm ＝s m ＝1个系数要么是1，要么是0。在有限域上定义了加法、减法、
简化后寄存器和计数器数据见表2。乘法、求逆运算。下面提到的B(x)是需要求逆的多项式，它是定义在GF （2m ）中的元素。F(x)是一个定义在GF （2m ）不
可约多项式。求逆的算法有很多种，本文在利用扩展欧几里德的计算两个多项式的最大公约数的基础上，提出了一个基于有限域的乘法逆元的算法。
Inversion ：
F:=F(x); Delta:=0; S:=F(x); R:=B(x); V:=0; U:=1;For i:=1 to 2m doIf rm =0
then R:=x.R; U=(x.U) MOD F; Delta+=1;Else
If sm =1 then S:=S－R;V:=(V－U) MOD F ; End;S:=x.S;
If delta=0 then
(R←→S); (UV); U:=(x.U) MOD F; delta:=1 Else
U: = (U/x) MOD F; Delta－=1; End;End;
-1
End; (B(x)=U=V)
表2 简化后寄存器和计数器数据
r m =0
Delta=0
R S U V
B(X)F(x)10
x.R T x.U W
x.T R x.W U
Init
rm =1
Delta0
R x.T U/xW
0Delta+1Delta+1Delta-1Delta
寄存器R 和S 有数据来往，U 和V 寄存器有数据来往。R 、S 和U 、V 之间没有数据交换，引入下面4个控制信号：
MultR ：=（r m ＝0）
MultU ：＝（r m ＝0）or （delta ＝0）Swtich ：＝（r m =1）&（delta ＝0）Reduce ：＝（r m ＝1）&（s m ＝1）
多项式R 和S 放在（m ＋1）比特的寄存器〔r m …r 0〕和〔s m …s 0〕中。U 和V 分别放在m 比特寄存器〔u m …u 0〕和
2 硬件实现
首先观察一下R 、S 、U 、V 寄存器的数据流，表1根据r m
和s m 以及delta 的值确定了R 、S 、U 、V 寄存器的数据流和计
—184—
〔v m …v 0〕中。另外还有一个log 2（m ＋1）比特的加减计数器存储delta 的值。
在计算U 时涉及到对U x x乘以和除以，然后将结果对F(x)求模，假设
F(x)＝x m +fm-1x m-1+fm-2x m-2+…+f1x+f0x.U x.[u＝＝m-2…u 0,0]＋u m-1x m m-1卽0] [u [u＝m-2卽0,0]＋u m-1 [fm-1…f 0]
-1
U/x [u＝m-1卽0]/x [0,u＝m-1…u 1]＋u 0.x [0,u＝m-1卽1]＋u 0 [1,fm-2…f 1]
根据上面的结果，对U －V 引入第5个控制信号：
Carry ＝(~Rm &Um-1) OR (Rm &~Sm &Zero&Vm-1) OR (Rm &
S m &Zero&(Vm-1^ Um-1))OR(~MultU&U0) 其中，Zero ：= ( Delta =0)。
该算法的总体硬件结构图如图1所示。D-Cell 电路图如图2所示，M-Cell 电路图如图3所示。
图D －Cell 电路 2
－Cell 电路图3 M
参考文献
1 Wang C C, Truong T K, Shao H M, et al. VLSI Architectures for Com-puting Multiplications and Inverses in GF(2m). IEEE Trans.Comput., 1985, C-34(8): 709-717
2 Araki K, Fujita I, Morisue M. Fast Inverters over Finite Field Based on Euclid's Algorithm. Trans. IEICE,1998,E-72(11):1230-1234
图1 总体硬件结构图
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
（上接第113页）
X ，Y 各异，因此攻击者重放已经截获的信息是无法通过服务器认证的。
(3)认证过程是安全的。假设入侵者可以截获合法认证过程中的任何通信数据进行分析，他从截获的ID' 中是无法获取uid 的，当然他直接发送截获的ID' 也能通过服务器的初步认证，但由于口令pwd 根本不通过网络传输，因而他不可能从截获的数据中解析出pwd ，准确算出校验符A 的值，从而无法通过下一步的认证，故方案的整个认证过程是安全的。由于用户标识uid 加密传输，口令pwd 和密钥K 不通过网络传输以及随机数R i 的不重复性，因而字典攻击、口令字猜测等常用的攻击手段对此是无能为力的。
(4)假冒攻击。方案的认证过程可以抵抗来自客户端的假冒攻击，这是因为攻击者不知道用户标识uid 、口令pwd ，从而不能算出校验符A 的值，不能进一步构造出验证数据X 、Y 而无法通过服务器的认证。
同样的，该认证过程也能有效地防御来自服务器端的假冒攻击，不会使合法用户的合理要求得不到满足。当用户向服务器提出认证请求时，要求服务器发送的挑战报文中包含用户标识uid 和密钥K 的Hash 值，用户可以对此Hash 值来进行校验，防止来自服务器的欺骗。
在效率方面，本方案将生成随机数R i 的工作移到客户端执行，大大减少了服务器的额外开销，提高了服务器的运行效率。
4 结束语
本文分析了当前较为常见的几种一次性口令身份认证方案。以挑战/应答方案为基础，基于安全单向散列函数设计了一种能有效适用于网络环境的一次性身份认证方案。该方案能够对通信双方实行相互认证，减少了服务器的开销，克服了传统的挑战/应答方案的弱点，有效地保护了用户身份信息，能防止重放攻击等常用攻击手段的攻击，通过传送两个验证数据X 、Y 增强了认证过程的安全性。但本方案还存在着计算量较大的缺陷：在一次身份认证过程中服务器需执行2次Hash 运算，客户端需执行4次Hash 运算。所以本方案将来还需进一步完善和提高。
参考文献
1 Lamport L. Password Authentication with Insecure Communication[J]. Communications of the ACM，1981，24(11)：770-772
应用密码学－协议、算法与C 源程序[M]. 北京：机2 (美)Schneier B.
械工业出版社，2000
张建伟李鑫张梅峰基于算法的身份鉴别技术的研究与 3 , , . MD5实现[J]. 2003计算机工程，，29(4):118-119
—185—
第30卷 第17期Vol.30 № 17
・开发研究与设计技术・
计 算 机 工 程Computer Engineering
文章编号：1000—3428(2004)17 —0184 —02
2004年9月September 2004
中图分类号：TN918
文献标识码：A
有限域逆元算法的实现
刘文江，董 威，戎蒙恬
(上海交通大学信息安全学院，上海200030)
摘 要：在扩展欧几里得算法的基础上提出了有限域乘法逆元的计算方法。给出了该算法的硬件结构图。该算法的优点是其时间复杂度和空间复杂度较优，便于VLSI 的实现。关键词：有 限域；乘法逆元；椭圆曲线；欧几里得
Implementation for Computing Division in Galois Fields
LIU Wenjiang, DONG Wei, RONG Mengtian
(College of Information Security, Shanghai Jiaotong University, Shanghai 200030)
【Abstract 】An implementation for computing multiplicative inverses in Galois fields GF(2m ) is presented. The algorithm is based on a modification of Euclid's algorithm. The architecture of circle for VLSI is also presented.【Key words】Finite field; Multiplicative inverse; ECC; Euclid
随着非对称密码学的发展，椭圆曲线（ECC ）密码学因数器的变化。
表1 寄存器和计数器数据为其独特的优势，渐渐取代RSA 在非对称密码学中的地位，
现在ECC 广泛使用在无线通信和Smart 卡中，完成加密、签Signals Registers Counter 名等功能。ECC 的优势在于它可以使用比RSA 少得多的比特r m s m Delta=0R S U V Delta 数目的密钥达到同样的保密效果。尽管这样，ECC 中的密钥0X X x.R S x.U V Delta+1长度还是比较大的，实际应用中的密钥长度有192、256等100s.S R x.V U Delta+1不同等级，应用中涉及到大数的存储和运算，因此对空间和101R x.S U/xV Delta-1
时间的要求特别高，本文充分考虑了二者的复杂度，提出了110x.(S-R)R x.(V-U)U Delta+1扩展欧几里得算法，具有很好的效果。1R x.(S-R)U/xV-U Delta-1111 欧几里得算法
简化上表, 同时引进两个变量T 和W, 这两个变量的值是:
有限域GF （2m ）是包含了2m 个元素的代数系统，该系统
T
＝S W＝V rm ＝0 s或者m ＝0
的每个元素都能够表示成小于m 次的多项式，该多项式的每
T ＝S －R W＝V －U rm ＝s m ＝1个系数要么是1，要么是0。在有限域上定义了加法、减法、
简化后寄存器和计数器数据见表2。乘法、求逆运算。下面提到的B(x)是需要求逆的多项式，它是定义在GF （2m ）中的元素。F(x)是一个定义在GF （2m ）不
可约多项式。求逆的算法有很多种，本文在利用扩展欧几里德的计算两个多项式的最大公约数的基础上，提出了一个基于有限域的乘法逆元的算法。
Inversion ：
F:=F(x); Delta:=0; S:=F(x); R:=B(x); V:=0; U:=1;For i:=1 to 2m doIf rm =0
then R:=x.R; U=(x.U) MOD F; Delta+=1;Else
If sm =1 then S:=S－R;V:=(V－U) MOD F ; End;S:=x.S;
If delta=0 then
(R←→S); (UV); U:=(x.U) MOD F; delta:=1 Else
U: = (U/x) MOD F; Delta－=1; End;End;
-1
End; (B(x)=U=V)
表2 简化后寄存器和计数器数据
r m =0
Delta=0
R S U V
B(X)F(x)10
x.R T x.U W
x.T R x.W U
Init
rm =1
Delta0
R x.T U/xW
0Delta+1Delta+1Delta-1Delta
寄存器R 和S 有数据来往，U 和V 寄存器有数据来往。R 、S 和U 、V 之间没有数据交换，引入下面4个控制信号：
MultR ：=（r m ＝0）
MultU ：＝（r m ＝0）or （delta ＝0）Swtich ：＝（r m =1）&（delta ＝0）Reduce ：＝（r m ＝1）&（s m ＝1）
多项式R 和S 放在（m ＋1）比特的寄存器〔r m …r 0〕和〔s m …s 0〕中。U 和V 分别放在m 比特寄存器〔u m …u 0〕和
2 硬件实现
首先观察一下R 、S 、U 、V 寄存器的数据流，表1根据r m
和s m 以及delta 的值确定了R 、S 、U 、V 寄存器的数据流和计
—184—
〔v m …v 0〕中。另外还有一个log 2（m ＋1）比特的加减计数器存储delta 的值。
在计算U 时涉及到对U x x乘以和除以，然后将结果对F(x)求模，假设
F(x)＝x m +fm-1x m-1+fm-2x m-2+…+f1x+f0x.U x.[u＝＝m-2…u 0,0]＋u m-1x m m-1卽0] [u [u＝m-2卽0,0]＋u m-1 [fm-1…f 0]
-1
U/x [u＝m-1卽0]/x [0,u＝m-1…u 1]＋u 0.x [0,u＝m-1卽1]＋u 0 [1,fm-2…f 1]
根据上面的结果，对U －V 引入第5个控制信号：
Carry ＝(~Rm &Um-1) OR (Rm &~Sm &Zero&Vm-1) OR (Rm &
S m &Zero&(Vm-1^ Um-1))OR(~MultU&U0) 其中，Zero ：= ( Delta =0)。
该算法的总体硬件结构图如图1所示。D-Cell 电路图如图2所示，M-Cell 电路图如图3所示。
图D －Cell 电路 2
－Cell 电路图3 M
参考文献
1 Wang C C, Truong T K, Shao H M, et al. VLSI Architectures for Com-puting Multiplications and Inverses in GF(2m). IEEE Trans.Comput., 1985, C-34(8): 709-717
2 Araki K, Fujita I, Morisue M. Fast Inverters over Finite Field Based on Euclid's Algorithm. Trans. IEICE,1998,E-72(11):1230-1234
图1 总体硬件结构图
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
（上接第113页）
X ，Y 各异，因此攻击者重放已经截获的信息是无法通过服务器认证的。
(3)认证过程是安全的。假设入侵者可以截获合法认证过程中的任何通信数据进行分析，他从截获的ID' 中是无法获取uid 的，当然他直接发送截获的ID' 也能通过服务器的初步认证，但由于口令pwd 根本不通过网络传输，因而他不可能从截获的数据中解析出pwd ，准确算出校验符A 的值，从而无法通过下一步的认证，故方案的整个认证过程是安全的。由于用户标识uid 加密传输，口令pwd 和密钥K 不通过网络传输以及随机数R i 的不重复性，因而字典攻击、口令字猜测等常用的攻击手段对此是无能为力的。
(4)假冒攻击。方案的认证过程可以抵抗来自客户端的假冒攻击，这是因为攻击者不知道用户标识uid 、口令pwd ，从而不能算出校验符A 的值，不能进一步构造出验证数据X 、Y 而无法通过服务器的认证。
同样的，该认证过程也能有效地防御来自服务器端的假冒攻击，不会使合法用户的合理要求得不到满足。当用户向服务器提出认证请求时，要求服务器发送的挑战报文中包含用户标识uid 和密钥K 的Hash 值，用户可以对此Hash 值来进行校验，防止来自服务器的欺骗。
在效率方面，本方案将生成随机数R i 的工作移到客户端执行，大大减少了服务器的额外开销，提高了服务器的运行效率。
4 结束语
本文分析了当前较为常见的几种一次性口令身份认证方案。以挑战/应答方案为基础，基于安全单向散列函数设计了一种能有效适用于网络环境的一次性身份认证方案。该方案能够对通信双方实行相互认证，减少了服务器的开销，克服了传统的挑战/应答方案的弱点，有效地保护了用户身份信息，能防止重放攻击等常用攻击手段的攻击，通过传送两个验证数据X 、Y 增强了认证过程的安全性。但本方案还存在着计算量较大的缺陷：在一次身份认证过程中服务器需执行2次Hash 运算，客户端需执行4次Hash 运算。所以本方案将来还需进一步完善和提高。
参考文献
1 Lamport L. Password Authentication with Insecure Communication[J]. Communications of the ACM，1981，24(11)：770-772
应用密码学－协议、算法与C 源程序[M]. 北京：机2 (美)Schneier B.
械工业出版社，2000
张建伟李鑫张梅峰基于算法的身份鉴别技术的研究与 3 , , . MD5实现[J]. 2003计算机工程，，29(4):118-119
—185—