公钥密码系统及RSA公钥算法.doc

公钥密码系统及RSA公钥算法
07301910张云霖
随着电脑连网的逐步实现，Internet前景越来越美好，全球经济发展正在进入信息经济时代，知识经济初见端倪。电脑信息的保密问题显得越来越重要，无论是个人信息通信还是电子商务发展，都迫切需要确保Internet网上信息传输的安全，需要确保信息安全。信息安全技术是一门综合学科，他涉及信息论、电脑科学和密码学等多方面知识，他的主要任务是研究电脑系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和完整。其中，信息安全的核心是密码技术。密码技术是集数学、电脑科学、电子和通信等诸多学科于一身的交叉学科。他不但能够确保机密性信息的加密，而且能够实现数字签名、身份验证、系统安全等功能。是现代化发展的重要科学之一。本文将对公钥密码系统及该系统中现在最广泛流行的RSA算法做一些简单介绍。
公钥密码体制，突破性地解决了困扰着无数科学家的密钥分发问题，事实上，在这种体制中，人们甚至不用分发需要严格保密的密钥，这次突破同时也被认为是密码史上两千年来自单码替代密码发明以后最伟大的成就。这一全新的思想是本世纪70年代，美国斯坦福大学的两名学者Diffie和Hellman提出的，该体制和单钥密码最大的不同是：在公钥密码系统中，加密和解密使用的是不同的密钥（相对于对称密钥，人们把他叫做非对称密钥），这两个密钥之间存在着相互依存关系：即用其中任一个密钥加密的信息只能用另一个密钥进行解密。这使得通信双方无需事先交换密钥就可进行保密通信。其中加密密钥和算法是对外公开的，人人都能够通过这个密钥加密文档然后发给收信者，这个加密密钥又称为公钥；而收信者收到加密文档后,他能够使用他的解密密钥解密，这个密钥是由他自己私人掌管的，并无需分发，因此又成称为私钥，这就解决了密钥分发的问题。当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。他是个基于数论的非对称(公开钥)密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。他的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此能够确保RSA算法的安全性。RSA系统是公钥系统的最具备典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此他为公用网络上信息的加密和鉴别提供了一种基本的方法。他通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文档发送给个人，个人就能够用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。该算法基于下面的两个事实,这些事实确保了RSA算法的安全有效性：1)已有确定一个数是不是质数的快速算法；2)尚未找到确定一个合数的质因子的快速算法。工作原理1)任意选取两个不同的大质数p和q，计算乘积r=p*q；2)任意选取一个大整数e，e和(p-1)*(q-1)互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，任何大于p和q的质数都可用。3)确定解密密钥d：d*e=1modulo（p-1）*（q-1）根据e、p和q能够容易地计算出d。4)公开整数r和e，但是不公开d；5)将明文P(假设P是个小于r的整数)加密为密文C，计算方法为：C=Pemodulor6)将密文C解密为明文P，计算方法为：P=Cdmodulor然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是现在最优秀的公钥方案之一。该算法的加密密钥和加密算法分开，使得密钥分配更为方便。他特别符合电脑网络环境。对于网上的大量用户，能够将加密密钥用电话簿的方式印出。假如某用户想和另一用户进行保密通信，只需从公钥簿上查出对方的加密密钥，用他对所传送的信息加密发出即可。对方收到信息后，用仅为自己所知的解密密钥将信息脱密，了解报文的内容。由此可看出，RSA算法解决了大量网络用户密钥管理的难题，这是公钥密码系统相对于对称密码系统最突出的长处。现在，日益激增的电子商务和其他因特网应用需求使公钥体系得以普及，这些需求量主要包括对服务器资源的访问控制和对电子商务交易的保护，连同权利保护、个人隐私、无线交易和内容完整性（如确保新闻报道或股票行情的真实性）等方面。公钥