椭圆曲线密码体制与智能卡研究

引言

人们根据密钥的特点，将密码系统分为私钥和公钥两大密码系统。在私钥密码系统中，解密密钥和加密密钥相同或者很容易从加密密钥导出，这一特点致使加密系统变得不安全。1976年Diffie和Hellman发表了著名的“密码学的新方向”一文［1］，提出公开密钥密码的思想，从此开始公钥密码的发展。在公钥密码体制中，解密密钥和加密密钥不同，从一个难于推出另一个，加密和解密是可分离的，通信双方事先无须交换密钥就可建立起保密通信。1978年由Rivest、Shamir和Adleman提出的RSA［2］方案及1984年提出的ELGamal［3］方案均属于公钥密码体制。RSA的安全性依赖于大整数分解因子问题的困难性，ELGamal的安全性则是建立在有限域上离散对数问题困难性基础上的。

随着计算机网络的迅速发展，相互之间进行通信的用户数量的增多，RSA与ELGamal公钥密码体制的公钥位数较大（一般为512比特以上）的弱点逐渐暴露出来。1985年Koblitz［4］和Miller［5］分别独立地提出利用椭圆曲线上离散对数代替有限域上离散对数，可以构作公钥位数较小的ELGamal类公钥密码。

1& nbsp; 椭圆曲线

定义1：设K=GF(q)（其中q=p