有限域切比雪夫多项式算法性能测试与分析

刘亮

(中央电视台新闻制作部，北京100859)

在L.Kocarev和Z.Tasev首次利用切比雪夫多项式的混沌特性构造了一种公钥加密算法［1］后，很快 Pina Bergamo 等就对其进行了破解［2］。文献［3］通过将切比雪夫多项式扩展到有限域上，使得文献［2］的攻击方式对其无效，并进一步提出了具体的公钥算法。文献［4］通过理论证明和实验分析，解决了文献［3］中忽略的切比雪夫多项式在有限域上仍然可能存在破解方法［5-6］，指出有限域切比雪夫多项式作为公钥加密体系的基础是可行的。

本文对文献［3］所提出的密钥协商、公钥加密和数字签名算法做了具体的编程实现，并对其计算性能进行了精确的测量。然后，结合有限域切比雪夫多项式的性质对实验数据进行分析，并选择一定的比较策略和相应的安全参数，将之与公钥体系中常用的RSA、ELGAMAL和ECC算法性能进行比较。发现有限域切比雪夫多项式算法具有加密简单，计算量小，处理速度快，存储空间占用小和所需带宽小的优势，更加适合于带宽有限的无线公钥加密系统。

1 有限域切比雪夫多项式的矩阵迭代算法及其计算量

有限域切比雪夫多项式算法的迭代形式如下:

其中 n∈Z，变量 x∈ZP，多项式 Tn(x):ZP→ZP。

在编程实验中，采用矩阵迭代方法，利用系数矩阵的累乘简化了代数多项式的迭代计算的复杂性，关系式如下:

其中，k是n转换成二进制表示时的总位数;h是n转换成二进制表示时1的总个数，即汉明距。又因为0＜h＜k，所以有如下计算量关系:

其中，式(3)是在已知比特位数n和汉明距h的情况下的精确的次数，而式(6)是在只知道比特位数n而不知道汉明距h的情况下的估算次数。

2 测试参数的选择

2.1 安全参数的选择

现有公钥体系中常用的非对称加密算法主要分为三类:

1)大整数分解难题(integer factorization problem，IFP):如 RSA;

2)离散对数难题(discrete logarithm problem，DLP):如 ElGamal，DSA;

3)椭圆曲线离散对数难题(elliptic curve discrete logarithm problem，ECDLP):如 EC ElGamal，ECDSA。

而一个系统的安全性主要取决于它自身算法的几个安全参数，比如:RSA的安全参数是它的模N。DLP的安全参数有两个，一个是它的群生成元p，一个是它的子群生成元q，它们都是素数;ECDLP的安全参数是它的椭圆曲线点所组成的加法群的生成元n。这些安全参数是相应算法的安全保障，同时它也是破解的主要对象。安全度相同时，三者的安全参数满足关系如下:

其中，|n|表示其中参数的比特长度，k是对称加密算法的密钥长度。表1给出了相同安全度下，这三种加密算法安全参数的比特长度。

表1 安全参数的比特长度

有限域切比雪夫多项式的安全度是由生成域Zp决定的。因此，素数P就是有限域切比雪夫多项式加密系统的安全参数，对应着RSA的N和Elgamal的p。又由于目前只有穷举搜索可以有效地破解基于有限域切比雪夫多项式的加密体系，因此，它的安全度可以类比于对称密钥加密算法。于是，对应表1中安全参数的比特位数，选择一系列测试域(P)进行实验，如表2所示。

表2 测试域P的选取

续表

2.2 公钥x和私钥n的选择

由于性能测试主要针对有限域切比雪夫多项式常规算法的密钥生成时间、加/解密时间、签名和验证签名时间以及密钥协商时间，因此，可以不考虑有限域切比雪夫多项式中易破解的特殊点［4］，而在域内随机选择x和n。

另外，由于x的值对计算时间影响很小，可以忽略不计，而n的取值却对计算时间有较大影响。因此，在具体测试中，将根据实验不同的侧重点对n做一定的设置或限制。

3 测试方案及测试结果

3.1 单次矩阵乘法时间

实验中，将不同域下一次系数矩阵乘法的时间作为标准单位，以获得较精确的算法性能。具体测试时，首先选择一个域(即P)，接着随机生成一个x，然后选取一个n值。采用式(3)计算乘法次数。同时，设ni=1(i=0…k)，即n转换为二进制后的各位全为1。这样，乘法次数就达到最大，为2(k+1)，测试精度也就达到最高。需要注意的是，对不同的域，要选取不同的n，使得n较接近P，以达到较好的效果。

由于在具体的实验中采用的是一般的PC机(奔腾 4代 CPU，主频 2.5GHz，256M 内存)，WIN2000 SERVER的操作系统和VC6的编译环境结合GNU大数运算库，因此整个实验环境的精度就不太高。所以，在每个域，对同一个n值测量10次，每次随机生成x，以获得现有条件基础上较理想的测试结果。同时还对每一次乘法反复测量1000次，以减小系统时间的分辨率低，而每次计算的时间短对测试结果精度的影响。由此，便形成了两个循环嵌套，将两个循环的时间累加，然后在循环外做一次除法，便得到较高精度的某一域中一次矩阵乘法所用的时间。再对不同的域重复上述算法，得到不同域的单次矩阵乘法所用的时间。如表3所示，其中，P的取值同表2对应。

表3 不同域下单次矩阵乘法时间

3.2 密钥生成和加、解密时间

这里，不需要准确的知道n转换成二进制表示后的汉明距，而只需要知道n的位数，然后利用式(6)估算出平均矩阵乘法次数，再用测量到的时间除以平均矩阵乘法次数得到的时间与表3中不同域下单次矩阵乘法时间进行比较，便可以知道两者是否在方法误差范围的许可内一致。从而进一步推出不同域下密钥生成和加、解密的最大时间(n等于P-2)和最小时间(n等于1)，得知其计算时间的范围和平均计算时间。

为了比较不同域下密钥生成和加、解密的时间，我们把切比雪夫多项式计算中的n都设定为40位的随机数，P和x的选取同3.1。仍旧采用3.1中的双重循环嵌套的方法，进行多次测量再取平均值以获得最佳测试结果。测试中，采用文献［3］中的加、解密方案，设密钥生成过程中的SK为40位，加密过程中的R也为40位，得到测试结果如表4所示。

3.3 签名、验证签名及密钥协商时间

由于数字签名、验证签名以及密钥协商也都是基于有限域切比雪夫多项式构造，因此测试方法同3.2中密钥生成和加解密时间。

表4 不同域下密钥生成和加、解密时间

测试签名和验证签名时间时，采用文献［3］中的签名和验证签名的方案。P的取值同表3，签名过程中签名的私钥SK为40位，签名的消息M也为40位，得到测试结果如表5所示。

表5 不同域下签名和验证签名时间

测试密钥协商时，采用文献［3］中的密钥协商算法。P的取值同表3，Alice和Bob的协商密钥KA和KB都为40位，得到测试结果如表6所示。

表6 密钥协商时间

4 实验数据分析

从表3-6可以看出，随着P位数的增加，域越来越大，单次矩阵乘法时间、密钥生成和加解密时间、签名和验证签名时间以及密钥协商时间都随之增加。这是符合密码学特性的，因为P是基于有限域切比雪夫多项式的公钥体系的安全参数，而安全参数越大则计算量越大，计算时间越长［7］。此外，模运算更加复杂导致的计算量增大也是计算时间增加的原因。

还可以看到，随着P位数的不断增加，尽管计算时间变长，但是计算时间的增加幅度比P位数的增加幅度要小很多。这就使得在设计基于有限域切比雪夫多项式的公钥体系时，可以通过不断增大P的位数来获得更高的安全性，而由于计算时间增加并不显著，因此，整个公钥体系的性能仍能保持较高，从而保证一定的效率。

由表4-6看到密钥协商的时间同加密和签名的时间大致相同，而约是密钥生成、验证签名和解密时间的两倍。这是因为，前者都进行两次有限域切比雪夫多项式计算，而后者都只进行了一次有限域切比雪夫多项式计算，又由于它们在计算时选择的n都是40位，所以得出的数据有以上规律。这说明，测得实验数据同理论分析是相符的。

另外，可以利用表4-6中的测试数据估算出不同算法得单次矩阵乘法时间。结果，在相同域中，它们与表3中精确测量出来的单次的矩阵乘法时间极为接近。这就更加肯定了算法的正确性，为算法性能的评测提供依据。

5 有限域切比雪夫多项式算法在WPKI中的优势

由上述测试数据可以看出有限域切比雪夫多项式作为公钥算法相对于RSA和Elgamal算法具备如下优势。

(1)安全性更高。由于它本身数学难题的复杂度高于RSA和Elgamal所基于的数学难题，因此，其抗攻击性具有绝对的优势。又由于目前针对它并没有有效的破解方法，所以，它的安全性近似对称密钥加密系统。

(2)计算量小，处理速度快，存储空间小，带宽要求低。由于有限域切比雪夫多项式所需的安全参数位数低，密钥尺寸小，因此它整个系统的计算速度就快，效率高，而所需的存储空间相对就小，对带宽要求也低。这对无线终端来说是非常重要的。

(3)密钥的生成和选取更加灵活方便。RSA和Elgamal算法本身对密钥的选择就有很高要求，而有限域切比雪夫多项式算法对密钥的选择可以十分随意［4］，因此，整个公钥系统开销也可以大大降低。

同ECC相比，有限域切比雪夫多项式算法优势如下:

(1)数学原理通俗简单，便于采用。ECC算法建立的数学模型相对来说比较复杂晦涩，给算法的具体实现和推广带来不少麻烦。而有限域切比雪夫多项式算法却是在原来切比雪夫多项式算法基础上的改进，原理浅显易懂，计算较前者也更加简单，效率更高。

(2)加密简单。ECC在利用公钥进行加密时需要计算点(x1，y1)=kP(k个P相⊕)，同时要防止点(x2，y2)=kQ 中的 x2=0，否则，就要重新选取［7］。而有限域切比雪夫多项式算法实现的条件宽松得多［4］。

由此可以看出，有限域切比雪夫多项式算法具备了RSA、Elgamal和ECC的优点，而鄙弃了它们的缺点。因此，可以将其很好的应用于WPKI体系的数字证书中。

6 结论

本文对采用有限域切比雪夫多项式的密钥协商、公钥加密和数字签名算法做了具体的编程实现，并选择一定的比较策略和相应的安全参数，对其计算性能进行了精确的测量。然后，结合有限域切比雪夫多项式的性质对实验数据进行分析，并将之与公钥体系中常用的RSA、Elgamal和ECC算法性能和应用进行比较。得知有限域切比雪夫多项式算法具有安全性高，加密简单，计算量小，处理速度快，存储空间占用小和所需带宽小的优势，更加适合于带宽有限，计算能力受限的无线公钥加密系统。

［1］Kocarev L，Tasev Z.Public-key encryption based on Chebyshev maps［J］.The 2003 IEEE International Symposium on Circuits and Systems Proceedings，2003，28-31.

［2］P Bergamo，P D Arco，A D Santis.Security of public key cryptosystems based on Chebyshev polynomials［OL］.http://citebase.eprints.org，2004.

［3］宁红宙，刘云，何德全.基于有限域上 Chebyshev多项式的新公钥加密系统［J］.

［4］刘亮，刘云，宁红宙.公钥体系中切比雪夫多项式的改进与特性研究［J］.北京交通大学学报，2005.

［5］G Maze.Algebraic Methods for Constructing oneway Trapdoor Functions［D］.Notre Dame:University of Notre Dame，2003

［6］Yoshimura T，Kohda T.Resonance properties of Chebyshev chaotic sequences［J］.Proceedings of the 2004 International Symposium on Circuits and Systems Volume 4 New York:IEEE，2004，23-26.

［7］L Fibìkov，J Vyskoc.Practical cryptography-the key size problem:PGP after year［J］.2001，11.