密码学基本算法的探讨

《密码学基本算法的探讨》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第20卷第3期吉林建筑工程学院学报V01．20No．32003年9月JournalofJilinArchitecturalandCivilEngineeringInstituteSep．2003文章编号：1009—0185(2003)03—0043—03密码学基本算法的探讨宋维平蔡大鹏2(1：吉林建筑工程学院网络信gee心，长春130021；2：锦州师范学院电子信息系，锦州121003)摘要：针对密码学中的RSA算法进行了描述，指出RSA算法的指数表达式；明文以分组为单位加密，其中，每个分组是小于某个数N的二进制值，说

2、明分组大小必须小于或等于log2‘；并给出了相应的图解．同时，对RSA算法的安全性进行了介绍，并假定采用数学攻击、定时攻击两种方式进行测试其相应的防范措施、RSA算法是被广泛使用的安全协议，是密码学的核心算法之一、关键词：算法；安全性；密钥；加密；解密中图分类号：TP309．7文献标识码：A1997年的一次评估表明，512位RsA(Rivest—Shamir—Adleman)算法可以在8个月内被破解(花费不超过i00万美元)，RSA实验室建议个人用户采用768位，机构采用1024位，而认证机关则需采用2048位密钥．768位的密钥至少在2004年以前是安全的．许多因

3、特网上著名的安全协议和工具都基于RSA算法，包括已被广泛采用的SSL，PGP，以及最新推出的s／MIME等．因此，RSA算法是密码学的核心算法，它是一种分组密码，其中的明文和密文都是对于某个数的从0到一1之间的整数．本文就其算法和安全性进行如下探讨．1RSA算法的描述RSA使用了指数表达式．明文以分组为单位加密，其中每个分组是小于某个数的二进制值．也就是说，分组大小必须小于或者等于log2(．实践中分组大小是K比特，其中2<<2¨．对于某个明文分组M和密文分组C。加密及解密的形式如下：C=modnM=Cmodn=()modn=modn发送方和接收方都必须知道的值．发

4、送方知道e的值，而只有接收方知道d的值．因此，这是一种公开密钥为KU={e，}，且私有密钥为KR={d，}的公开密钥加密算法．要使这个算法能够满足公开密钥加密的要求，必须符合如下条件：(1)有可能找到eXd的值，使得对所有M<有Me=Mmodn．(2)对于所有m<的值，要计算Me和C相对来说是简单的．(3)在给定e和时，判断出d是不可行的．那么，如何找到modn的关系呢?假定：给定两个素数P和q，以及两个整数和m，使得=Pq，而且，0

5、，也就是不超过，且与互素的整数个数．因而，可以得到需要的关系，如果ed=足()+1，等价于ed三lmod9()，d三e-1mod9()．也就是说，d和e是以()为模的乘法逆元．注意根据模运算规则，它的必要条件是d(并有e)与()是互素的，等价于gcd((7／)，d)=1．收稿日期：2003—03—03．作者简介：宋维平(1960~)，男，吉林省长春市人，副教授，硕士维普资讯http://www.cqvip.com吉林建筑工程学院学报第20卷现在可以给出RSA方法．它的成分有P，q两个素数(私有，选择)：P口(公开，计算出)e，其中，god(9()，e)=1；1

6、(n)(公开，选择)d三e～mod9()(私有，计算出)私有密钥由{d，}组成，而公开密钥由{e，}组成．假设用户A公布了它的公开密钥，而用户B希望向A发送一个报文M，那么，B计算出C=M(modn)并传输c．在收到这个密文时，用户A通过计算M=(modn)进行解密．图1归纳了RSA算法．图1RSA算法2RSA的安全性假定两种攻击RSA算法的方法是：①数学攻击：对两个素数乘积的因子分解．②定时攻击：这个依赖于解密算法的运行时间．第一种：因子分解．在此基础上，我们可以划分出三种以数学方式攻击RSA的方法：(1)将分解为两个素数因子．可以计算9()=P(一1)×(q一1

7、)，可以确定d=e-1m0d()．(2)在不先确定P和q的情况下直接确定()，可以确定d=e-1m0d9()．(3)不先确定9(玎)而直接确定d．大部分关于RSA密码分析的讨论都集中在对进行素因子分解上．给定确定9(Y／)就等价于对进行因子分解．所以，把因子分解的性能作为一个评价RSA安全性的基准．表1说明因子分解的进展，工作量的大小是用MZPS年为单位衡量的。这个单位的含义是一个每秒100万个指令的处理器运行一年时间的工作量，即3×10条指令．例如，一个200MHz的pentium处理器是一个大约50MZPS的机器．表1中有一个显著的事实与因子分解的方法有关．