《ghpks公钥密码体制算法改进》由会员分享，可在线阅读，更多相关《ghpks公钥密码体制算法改进（3页珍藏版）》请在金锄头文库上搜索。
1、G H P K S 公钥密码体制算法改进 李娅莉1 ，王衍波2 1 解放军6 1 0 8 1 部队，北京，1 0 0 0 9 4 ： 2 解放军理工大学通信工程学院电子信息工程系，江苏南京，2 1 0 0 0 7 擅要：G H P K S 是一种计算基于卯( p ) ，安全性基于G F ( p 3 ) 上离散对数难题的新公钥密码体制。本文利 用G H P K S 产生序列的周期性对其核心算法D S E A 进行了有效改进，计算每对公钥、共享密钥平均减少 4 5 1 0 9 ( 1 m ) 次G 脚) 上模P 乘法( = l o g k ，m = l o g ( Q p ，k 是私钥) 。 关t
2、 词：线性反馈移位寄存器；不可约多项式；随机性 一、引言 。 G H P K S 是由G u a n gG o n g 和L e i nH a r n l 9 9 8 年提出的是一种基于G F ( p ) 上3 级线性反馈移位寄存器 ( L F S R ) 序列的公钥密码体制【l 】。虽然现在已经出现的公钥密码体制的实现方案很多。但是一方面由于算法 的速度问题一直是公开密码体制的瓶颈，真正投入实际应用的公钥密码体制并不多。另一方面，分解大整数 能力的日益增强，给密钥的长度提出了更高的要求。在这种情况下，研究者致力于构造更高效安全的公钥密 码体制。G H P K S 公钥密码体制最大的特点在于其
3、安全性基于G 坳J 上离散对数难题，但所有运算仅在G F ( p ) 上进行。这使得该体制在同等安全等级下，模P 的大小与椭圆曲线密码体制相同( 见表1 【2 】) ，但单位比特计 算开销更小。因此G H P K S 大大地改进了公钥密码体制的运算效率。例如，高效的公钥密码体制X T R 实际 上是G H P K S 的一个特例【3 】。可见，作为一种新的公钥密码体制，G H P K S 虽然还没有投入真正的实践应用， 但其较高的运算效率和安全性使其具有很好的发展潜力，正受到国外密码学界的关注。W a t e r l o o 大学已把 G H P K S 公钥密码体制的学习和研究作为课程内容加
4、入到密码学课程中。 目前基于该体制密码协议有：D i f f i e H c l l m a n 密钥交换协议G H D H 1 】、类R S A 公钥加密算法G H R S A 2 】 和类E I G a m a l 数字签名算法G H D S A 3 1 。在给出G H P K S 的同时G u a n gG o n g 和L e i n H a m 提出了该体制的 核心算法D S E A 。正是由于D S E A 快速算法，G H P K S 具备了较快的运算速度，本文的着眼点是对D S E A 进 行了改进，有效地减少了计算次数更大限度的发挥了G H P K S 的运算优势。 二、G
5、H - P K S 的理论知识及G H - D H 算法描述 1 、3 级特征序列及其反序列 设多项式f ( x ) 3 一a x 2 + k 一1 ，口，b F ，F = G F ( p ) ，P 是一素数。若存在S = s t 满足 S t = a s - b s 一2 + S k _ 3k 3 ，Rs 具有初始状态：s o = 3 ，s l = a ，s 2 = a 2 一拍，则称s = s t ) 是f ( x ) 产生的3 级特征序列。序列s 记作S ( 口，6 ) ，第k 项s 记为s t ( 口，6 ) 。，( j c ) 的周期记为p e r ( x ) 。当，( x ) 在
6、F 上不可约时，序列s 的周期等于f ( x ) 的周期p e r ( x ) 。 f _ 1 ( x ) 称为f ( x ) 的反多项式，如果f _ 1 ( z ) - - X3 一搬2 + a x - 1 ，口，b F 。f 叫( z ) 的特征序列为 J 一( 口，易) ，同时有s t ( 口，易) = S k ( 易，口) ，k = 1 , 2 ，。设s 的周期为Q ，有s t = s Q t 。 2 、重要定理及G H - D H 算法描述 j 设s 是，上不可约多项式厂( x ) ：硝3 一a x 2 + b x 一1 的特征序列，则对于任意正整数忌，e 有 s t ( s 。(
7、口，易) ，s 。( n ，易) ) = s b ( D ，b ) 成立。此结论构成了密钥交换的基础。G H D H 的算法描述如下： ( 1 ) 系统公开参数：P 是一个大素数，厂( x ) 爿3 一a x 2 + b x 一1 ，a ，b G F ( p ) 是F = G F ( p ) 上周 期Q = P 2 + P + l 的不可约多项式。 ( 2 ) 密钥产生：A l i c e ，B o b 各自选择整数e ，r 作为其私钥，要求0 e Q 且g c d ( e ，Q ) = 1 ，0 弦l 。因此得到改进的方法如下：、 计算前判断e 的大小，若P 等，则计算聊= Q P ，s 。
8、= s 一。，s 一。= s 。，否则直接计算J 。，s 一。 由于选择私钥P 大于导的概率为丢，因此计算一对公钥或共享密钥平均减少的计算量为： 去触= 吉觚g 七一9 l o “) “5 l 。g 乏k 7 哆( G F ( p ) 上模p 獬。 一次成功会话需要计算公钥、共享密钥共四次，平均减少的计算量为： 4 吉龇= 4 x l ( 9 1 0 9 k - 9 1 0 9 七) = 1 8 l 。g 7 XG F ( p ) 上模p 乘法。 例如：设P = II ，f ( x ) 硝3 + 4 x - 1 ，选取私钥e = 1 2 4 ，计算公钥( 3 1 2 4s m 4 ) 。判断：
9、 2 2 6 一 江苏省通信学会论文集 二二一 Q = 1 1 2 + 1 1 + 1 = 1 3 3 ，1 2 4 孚，令聊= Q 一8 = 9 ，聊= 毛哎屯= 1 0 0 1 ，计算步骤如表2 。若按原算 法直接计算e = 1 2 4 = k o k l k 2 k 3 k 4 k 5 k 6 = 1 1111 0 0 ， 七= 9 1 0 9 7 9 l 0 9 4 = 2 7 次G F ( p ) 上模p 乘法。 表2 ：改进后计算步骤 k ， tS f 步骤 k o = 1r o = k o = 1 s l 1 k l = 0互= 2 r o + k l = 2S 2 2 k ，=
10、 0 互= 2 互+ k 2 = 4 s 4 3 k 3 = 1互= 2 疋+ k 3 = 9s 9 4 计算步骤如表3 。计算单个公钥减少的计算量为 当安全等级达至U R S A 1 0 2 4 时，必须选用3 4 1 B i t s 的大素 数，例如我们选用： 表3 ：原计算步骤 k f互 s i 步骤 k o = 11 0 = k o = 1S I 1 k l = 1互= 2 r o + k I = 3S 3 2 k 2 = 1疋= 2 r , + k 2 = 7 s ， 3 k 3 = 1五= 2 兀+ k 3 = 1 5S 1 5 4 k 4 = 1瓦= 2 瓦+ k 4 = 3 1
11、S 3 l 5 k 5 = 0瓦= 2 r , + k 5 = 6 2s 6 2 6 k 6 = 0瓦= 2 疋+ k 3 = 1 2 4S 1 2 4 7 p = 2 5 2 4 1 0 0 1 4 2 8 0 2 0 6 5 0 9 1 3 1 9 9 8 6 4 7 5 3 4 6 6 2 0 4 3 9 4 4 2 7 8 2 5 2 8 1 2 2 3 8 1 6 4 0 8 1 2 8 1 6 3 8 4 3 8 4 3 6 4 1 9 5 8 9 2 6 2 8 8 1 8 4 4 0 0 2 412 9 4 0 7 5 9 5 2 0 9 2 9 1 ( 3 4 1b i t
12、s ) ， a = 1 0 0 9 6 7 8 4 6 2 4 6 6 6 3 4 5 3 4 5 7 3 2 3 6 1 6 5 9 9 5 4 7 8 9 7 7 7 9 1 3 2 2 8 6 4 1 5 3 2 0 7 1 4 9 3 3 0 4 9 0 7 7 6 2 0 9 1 4 8 2 7 9 7 3 3 0 7 7 1 7 9 9 3 8 3 9 7 1 0 9 1 1 5 1 4 8 7 0 8 9 5 1 ( 3 3 9 b i t s ) ， b = 2 0 6 2 1 6 0 2 2 6 4 4 1 8 4 7 5 9 8 1 5 0 2 4 5 4 9 9 5 4
13、2 2 7 8 4 8 1 0 8 7 0 8 7 2 3 6 5 9 8 5 4 5 4 8 1 7 4 0 8 8 2 9 3 5 0 0 2 9 3 9 0 6 2 3 7 0 6 8 9 5 4 0 6 3 7 3 9 2 1 9 2 9 3 8 8 3 6 1 6 2 6 8 3 ( 3 4 0 b i t s l ， 一 Q = 6 3 7 1 0 8 1 5 3 0 8 9 3 4 0 5 3 8 6 4 3 1 3 5 0 0 7 0 4 3 5 1 0 6 5 4 4 8 7 2 9 6 3 6 6 3 2 3 0 6 6 9 0 3 1 6 1 1 6 6 1 4 6 2
14、0 0 9 9 6 8 4 8 2 9 3 1 1 6 6 9 3 6 9 2 8 4 4 1 2 0 6 9 2 2 8 5 2 3 1 5 8 8 0 9 2 7 8 3 9 6 4 1 1 0 6 4 0 7 9 7 4 8 2 2 2 3 3 7 4 3 6 9 0 5 5 7 4 7 2 9 1 9 3 8 5 9 0 1 9 2 1 4 8 4 4 9 4 3 6 6 3 4 4 1 2 5 1 5 0 5 7 3 9 3 0 5 8 0 6 1 9 9 6 6 2 6 3 8 4 3 8 4 4 3 8 1 6 8 7 9 3 1 9 7 3 ( 6 8 l b i t s )
15、， 、 在这种情况下，如果选择6 8 1 B i t s 的私钥，采用先判断后计算的方法每次会话计算公钥和共享密钥各两 对，则平均计算量将减少： 4 4 5l 0 9 6 8 1 2 = 1 5 1 4 2 次G F ( p ) 上模P 乘法。 四、结论 本文对G H P K S 公钥密码体制的核心算法进行了有效改进。根据产生序列的周期特性，采用先判断计算 的方法得到每对公钥、共享密钥平均减少4 5l o g ( k k ) 次模P 乘法，在每次成功交换密钥的情况下共减少 1 8 l o g ( k 七) 次模P 乘法( k = l o g e ，k = l b g ( Q o ，P 是私钥) 。这对于G H P K S 的快速实现是具有较好的实际价 值。针对此改进算法进行更多的仿真和与原方法在实现上的比较将是下一步工作的重点。G H - P K S 正受到国 内外密码学界越来越多的关注，随着研究地深入进行，该体制所具备的安全而高效的特点预示了它将在移动 通信、C D M A 通信和电子商务加密等应用中拥有的良好发展前景。 参考文献 【I 】G G o n ga n dL H a m , An e wa p p r o a c ho nu b l i c k e yd i s t r i b u t i o n ”【A 】，C h i n a C R Y P
