基于单向陷门函数的加密算法

郭　姝　施滔滔　张新玉

[摘要]单向陷门是密码学领域中的一个非常重要的算法思想,在此基础上产生许多有效的算法,阐述单向陷门函数的基本内涵,并详细介绍与单向陷门函数有关的几种加密算法。

[关键词]单向陷门 RSA EIGamal Menezes-Vanstone

中图分类号:TP309.7文献标识码:A文章编号:1671-7597(2009)0920097-01

一、引言

日常生活中的一些现象常常能够给我们以启发,比如,破镜不能重圆,打碎了的镜子很难恢复到打碎前的状态,同理,让水从低处流向高处要比使它从高处流向低处难得多,将挤出的牙膏弄回管子里要比把牙膏挤出来困难得多。这个道理在数学中也有体现,比如,将许多大质数相乘要比将其乘积因式分解容易得多。这就是单向的意义所在。

二、单向陷门函数

单向陷门函数(One-way Trapdoor Function):“可逆”函数F若满足下列两条件,则函数F称为单向陷门函数:

1.对于属于F定义域的任一x,可算出F(x)=y;

2.对于几乎所有属于F值域的任一y,若获得陷门,则能求出x,即使得x=F-1(y),F-1为F的反函数;否则不能。但若有一额外数据z(称为陷门),则可很容易求出x=F-1(y)。

单向函数的特点决定了它计算上的复杂性,而陷门的性质又决定了某一额外数据z会成为破解该函数的密钥。

三、RSA算法

RSA基于此数学假设:对大数进行质因数分解是困难的。RSA用到的是两个大质数的乘积,用目前的计算机水平是无法分解的。(后面删除了一些句子)

RSA加密步骤如下:

1.任取两个大素数p和q保密。

2.计算n=p*q公开和φ(n)=(p-1)*(q-1)保密。

3.随机选取一个解密密钥d,d要满足0

=1保密。

4.计算加密密钥e,满足0

5.加密明文:c=E(m)≡m(modn)。

6.解密密文:m=D(c)≡c(modn)。

其中:m表示明文,c表示密文,e表示加密密钥,d表示解密密钥,E(m)表示加密函数,D(c)表示解密函数。

它的安全性基于数论中的Euler定理和计算复杂性理论中的大数的因子分解,优点是密钥空间大,缺点主要有:第一,受到素数诞生技术的限制,产生密钥麻烦且难以做到一次一密;第二,分组长度太大,运算代价高且速度慢。但是RSA是目前应用最广泛的公钥加密算法,特别适用于通过Internet传输数据。同时,伴随着计算机技术及密码技术的快速发展,RSA算法的破解方法也会应运而生。

四、EIGamal算法

EIGamal算法是一种既可以用于数字签名又可以用于数据加密的算法,应用非常广泛,该算法要产生一对密钥,首先选择一个大素数P,两个随机数g和x,且g,x

对消息M加密时,也先选择一个以P-1互素的随机数k,并计算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的。这就是陷门函数的力量所在。

五、椭圆曲线上的Menezes-Vanstone密码体制

椭圆曲线密码体制ECC(Elliptic Curves Cryptosystem)是目前加密领域中最重要的密码体制之一。椭圆曲线密码(ECC)的基本思想是找到一条安全的椭圆曲线,将明文嵌入到其中,然后对椭圆曲线上的点进行加密。其安全性是基于椭圆曲线上离散对数求解的困难性的。其方程如下:

y2=x3+ax+b(modP)

其中:p是素数,a和b为两个小于p的非负整数,它们满足:4a3+27b2

(ModP)≠0。其中,x,y,a,b∈Fp,则满足式(2)的点(x,y)和一个无穷点O就组成了椭圆曲线E。椭圆曲线公钥系统是代替RSA的强有力的竞争者。椭圆曲线加密方法与RSA方法相比,有以下的优点:

1.安全性能更高。如160位ECC与1024位RSA、DSA有相同的安全强度。

2.计算量小,处理速度快。在私钥的处理速度上(解密和签名),ECC远比RSA、DSA快得多。

3.存储空间占用小。ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多,所以占用的存储空间小得多。

4.带宽要求低使得ECC具有广泛得应用前景。

参考文献:

[1]Wailed Othman等,大数运算库[DB/OL].http://triade.studentenweb.org/Cint/gint.html(Delphi),2004-01-26.

[2]William S,Cryptogrphy and Network Security,Principles and Practicep[M].2nd清华大学出版社,2002:19-30.

[3]Douglas R Stison著,冯登国译,密码学原理与实践[M].电子工业出版社,2003.

[4]杨波,现代密码学[M].清华大学出版社,2007.

[5]周玉洁、冯登国,公开密钥密码算法及其快速实现[M].北京:国防工业出版社,2002.

[6]陈鲁生、沈世镒,现代密码学[M].北京:科学出版社,2002.

作者简介:

郭姝,在读本科,江苏徐州中国矿业大学计算机科学与技术学院信息安全专业,研究方向:信息安全。