一种基于MDP的快速公开密钥数字签名算法  

An MDP Public-Key Digital Signature Scheme

作　　者：郑建德[1] 

机构地区：[1]厦门大学计算机科学系,厦门361005

出　　处：《计算机研究与发展》2005年第2期280-285,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目 (60 3 73 0 77)

摘　　要：基于Zn 上的矩阵对角化问题 (MDP)能够建立一种新的公开密钥数字签名算法 ,当n取为一个RSA模数时 ,其安全性依赖于因素分解问题 (IFP)的难度或联立求解Rabin方程与Ong Schnorr Shamir方程的复杂性 该算法的重要特点之一是不涉及大指数乘方运算 ,完成一个签名的主要运算量是少数几个取模整数乘 (除 )法 ,其中必须在线完成的仅为 4个 ,效率远远高于其他依赖大指数乘方运算的数字签名算法 ,是公开密钥数字签名技术的一个重要突破 该算法还能够直接以用户身份构造其公钥 。A new public-key digital signature scheme is developed in this paper by exploring the hard matrix diagonalization problem (MDP) over Z n, the ring of integers with modulo-n addition and multiplication, where n is an RSA modulus. In the proposed system, a digital signature is obtained by embedding simple functions of a message into two 2×2 matrices as their eigenvalues, while the eigenvectors of the matrices are computed from the signer's private key. Security of the new scheme depends on the problem of solving three simultaneous quadratic equations with total five variables. It remains to be proved that the new crypto problem is as hard as solving Rabin equations, but it is apparently harder than solving pure bi-variate quadratic equations, i.e., Ong-Schnorr-Shamir equations, and it is not vulnerable by Pollard-Schnorr attack. The most important feature of the new scheme is its high efficiency. Since no high crder exponentiation is involved, it takes only a dozen of multiplications to sign a message, among which only 4 multiplications should be performed online, the rest can be pre-computed, while more than 1000 modulo-n multiplications are required to obtain an RSA signature. new scheme can also be used for identity-based digital signature.

关 键 词：计算机安全 公钥密码技术 基于身份的数字签名 矩阵对角化 

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]