188宝金博页面版

基于单向陷门函数的加密算法郭 姝 施滔滔 张新玉（中国矿业大学 计算机科学与技术学院 江苏 徐州 221116）[摘 要]单向陷门是密码学领域中的一个非常重要的算法思想，在此基础上产生许多有效的算法，阐述单向陷门函数的基本内涵，并详细介绍与单向陷门函数有关的几种加密算法。[关键词]单向陷门 RSA EIGamal Menezes-Vanstone中图分类号：TP309.7 文献标识码：A 文章编号：1671－7597（2009）0920097－01一、引言a=gkmodP，b=ykMmodP，a和b是密文对，将a和b连接将得到最终的密文，它的长度是密文的两倍。解密的时候，M=b/ax（modP）。日常生活中的一些现象常常能够给我们以启发，比如，破镜不能重EIGamal算法的安全性依赖于计算有限域上离散对数的难度，对于方圆，打碎了的镜子很难恢复到打碎前的状态，同理，让水从低处流向高处程y=gkmodP来说，其中P是大素数，g是有限域Zp的生成元。已知k很容易求要比使它从高处流向低处难得多，将挤出的牙膏弄回管子里要比把牙膏挤出y，但已知y，很难求出k。出来困难得多。这个道理在数学中也有体现，比如，将许多大质数相乘要该算法的破译方法基本上都是根据模指运算等式y=gxmodP。在获得比将其乘积因式分解容易得多。这就是单向的意义所在。y，g和P的条件下来求出私钥x。但是根据离散对数问题的困难性，是无法二、单向陷门函数求出x的。这就是陷门函数的力量所在。单向陷门函数（One-way Trapdoor Function）：“可逆”函数F若满五、椭圆曲线上的Menezes-Vanstone密码体制足下列两条件，则函数F称为单向陷门函数：椭圆曲线密码体制ECC（Elliptic Curves Cryptosystem）是目前加1．对于属于F定义域的任一x，可算出F（x）=y；密领域中最重要的密码体制之一。椭圆曲线密码（ECC）的基本思想是找到2．对于几乎所有属于F值域的任一y，若获得陷门，则能求出x，即使一条安全的椭圆曲线，将明文嵌入到其中，然后对椭圆曲线上的点进行加得x=F-1（y），F-1为F的反函数；否则不能。但若有一额外数据z（称为陷密。其安全性是基于椭圆曲线上离散对数求解的困难性的。其方程如下：门），则可很容易求出x=F-1（y）。y2=x3+ax+b（modP）单向函数的特点决定了它计算上的复杂性，而陷门的性质又决定了某其中：p是素数，a和b为两个小于p的非负整数，它们满足：4a3+27b2一额外数据z会成为破解该函数的密钥。（ModP）≠0。其中，x，y，a，b∈Fp，则满足式（2）的点（x，y）和一三、RSA算法个无穷点O就组成了椭圆曲线E。椭圆曲线公钥系统是代替RSA的强有力的竞RSA基于此数学假设：对大数进行质因数分解是困难的。RSA用到的是争者。椭圆曲线加密方法与RSA方法相比，有以下的优点：两个大质数的乘积，用目前的计算机水平是无法分解的。（后面删除了一1．安全性能更高。如160位ECC与1024位RSA、DSA有相同的安全强些句子）度。RSA加密步骤如下：2．计算量。硭俣瓤。在私钥的处理速度上（解密和签名），1．任取两个大素数p和q保密。ECC远比RSA、DSA快得多。2．计算n=p*q公开和φ（n）=（p-1）*（q-1）保密。3．存储空间占用小。ECC的密钥尺寸和系统参数与RSA、DSA相比要小3．随机选取一个解密密钥d，d要满足0<d<n，而且gcd（d，φ（n））得多，所以占用的存储空间小得多。=1保密。4．带宽要求低使得ECC具有广泛得应用前景。4．计算加密密钥e，满足0<e<φ（n），而且de≡1（modφ（n））（公开）。利用RSA加密第一步需要将明文数字化，并取长度小于log2n位的数字作为明文块。5．加密明文：c=E（m）≡m（modn）。参考文献：6．解密密文：m=D（c）≡c（modn）。[1]Wailed Othman等，大数运算库[DB/OL].http://triade.studentenweb.其中：m表示明文，c表示密文，e表示加密密钥，d表示解密密钥，org/Cint/gint.html(Delphi)，2004-01-26.E（m）表示加密函数，D（c）表示解密函数。[2]William S，Cryptogrphy and Network Security，Principles and 它的安全性基于数论中的Euler定理和计算复杂性理论中的大数的因Practicep[M].2nd清华大学出版社，2002：19-30.子分解，优点是密钥空间大，缺点主要有：第一，受到素数诞生技术的限[3]Douglas R Stison著，冯登国译，密码学原理与实践[M].电子工业出制，产生密钥麻烦且难以做到一次一密；第二，分组长度太大，运算代价版社，2003.高且速度慢。但是RSA是目前应用最广泛的公钥加密算法，特别适用于通过[4]杨波，现代密码学[M].清华大学出版社，2007.Internet传输数据。同时，伴随着计算机技术及密码技术的快速发展，[5]周玉洁、冯登国，公开密钥密码算法及其快速实现[M].北京：国防工RSA算法的破解方法也会应运而生。业出版社，2002.四、EIGamal算法[6]陈鲁生、沈世镒，现代密码学[M].北京：科学出版社，2002.EIGamal算法是一种既可以用于数字签名又可以用于数据加密的算法，应用非常广泛，该算法要产生一对密钥，首先选择一个大素数P，两个作者简介：随机数g和x，且g，x<P，然后计算y=gxmodP。公钥是y，g和P，私钥是x。郭姝，在读本科，江苏徐州中国矿业大学计算机科学与技术学院信息安全对消息M加密时，也先选择一个以P-1互素的随机数k，并计算专业，研究方向：信息安全。97