RSA公开密钥体制及其主要数学基础

《RSA公开密钥体制及其主要数学基础》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、RSA公开密钥体制及其主要数学基础江西省上犹县教师进修学校(341200)舒昌勇在密码学发展的历史上，1976年是一个值得纪念的年份.这一年，美国斯坦福大学年轻的数学家狄菲(Diffie)和计算机专家海尔曼(Hellman)联名发表了《密码学的新方向》一文，开创了现代密码学的新领域——公开密钥体制(简称公钥体制).30年來，公钥体制获得了巨大的发展，它不仅消解了传统的秘密密钥体制存在的一些困难，而且解决了信息安全的一些问题，推动了包括电了商务在内的一大批网络应用的深入和发展.1公开密钥体制的提出1・1传统密钥体制遭遇的

2、困难(1)用户的增加使大量密钥管理成为严重问题在传统的秘密密钥保密通信中，每一对发方和收方都耍拥有一对密钥：加密密钥E和解密密钥发方把要发送的明文信息x用加密密钥加密成密文y发送；收方收到密文p后用解密密钥D将Z解密为明文儿所以从数学上说，加密密钥E和解密密钥D是互逆的，经过它们的共同作用，明文信息x经过加密和解密仍］口变换为明文信M：D(£⑴)二E(D⑴)所以，只要知道E、D中的任何一个就能很容易地求出另一个.因而密钥E、D都要保密.从20世纪60年代起，由于因特网络为通信提供的便利，保密通信的应用领域不断扩大,用户

3、人量增加.假设2000个用户彼此进行保密通信，因每2个用户就需一对密钥，整个通信系统一共需要C22(mx)=(2()OOX1999)-4-2=1999000对密钥，每个用户要保管他和其余1999个用户间的1999对密钥，这讣我们不难理解巨人的密钥量给密钥管理、分配和为了确保信息安全而对密钥定期更换方面带来的困难.(2)数字签名和身份认证的问题亟待解决在通常的书信和文件屮，人们常帘卅签名、印章或指纹來表明白己的身份，收方也凭此来确认信、文是否來自发方，在数字通信中同样存在这类问题•但发方如何在信息上签名？收方如何确认发方

4、的身份？如何辨认信息是否系伪造或被修改？这些问题因与信息的安全密切相关都亟待解决.1.2大整数因子分解的无奈根据算术基本定理：任何人于1的整数总可以分解成素因数乘积的形式，并且，如果不计分解式屮素因数的次序，这种分解式是唯一的.这个定理在理论上I分漂亮，但操作起来对大整数却非易事甚至实际并不可能.表1列出了用现代蝕快速的分解算法，在人型计算机上分解一个人整数所需的时间.这让我们看到人整表1数分解在目前是一个非常闲难的问题.让人未曾想幣数的位数操作次数所需时间到的是，正是这种困难为一种新的密钥体制的“核501.4X1O1

5、03.9小时心部件”——单向函数的构造提供了重要的机会•759.0X1012104天1.3公开密钥思想的提出1002.3X101574年(1)单向函数2001.2X1O233.8XI(P年1976年，狄菲和海尔曼在《密码学的新方向》3001.3X10294.9X1015年一文中，提出米川“单向函数”來设计公钥体制的5001.3X10394.2X1017亿年思路.所谓“单向函数”，是指加密函数E和解密函数D的运算都容易实现，但由E求其逆运算D却非常困难.这样，即使把加密函数E和具体的加密■解密的算法过程都公开，如果不知道

6、解密函数Q,把密文解密成明文的计算也无法实现.(2)公钥体制的基本思想在公钥体制中，密钥管理中心为每个用户设计一对密钥——加密密钥和解密密钥，加密密钥可以公开，称为公钥，解密密钥由用户白己秘密保管，称为私钥.每个用户与其它任何-个用户的密钥都不相同，在他拥有的一对密钥中，公钥与私钥也不和同，而且由公钥推导出私钥也绝不对行.但它们又密切联系着：用公钥加密的信息只能用与Z配对的私钥才能解密，用私钥加密的信息也只能用与之配对的公钥才能解密.1.4公钥体制的工作原理设某公司的个用户要进行保密通信，密钥管理中心分別为每个用户人(

7、匸1,2,…，力设计一对密钥(E‘,将公钥Q汇编成公钥簿供所有用八查找，将私钥0秘密提供给用户4使用并由人•秘密保管.当某用户要发信息X给川户人•时，先在公钥簿上查找到的公钥耳，用它将明文信息x加密成密文信息y=E.然后通过公开信道发给川・人收到密文信息y后，用私钥D作用于y：D(y)=D(匕⑴)二儿由于用人的公钥Q加密的密文信息，只有用人的私钥0才能解密成明文信息，所以即使密文信息被他人截获，也无法解密成明文，因而保证了公钥体制通信的安全性.在前述2000个川户秘密通信的问题屮，假如采川公钥体制，市于1个用户只需要拥

8、有1对密仞，所以整个通信系统只需2000个密钥对，每个用八也需记忆与保管属于自己的1个私钥就行，与前述相应的1999000对和1999对相比，分别减少了近1000倍和近2000倍!2RSA公钥体制的基本原理其实，由狄菲和海尔曼提岀的公钥体制只是一种思想，他们开创性的论文引进了密码学的一种新方法，但同时也给密码学专家提出了一个挑战性