rsa公钥密码系统new

《rsa公钥密码系统new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、RSA公钥密码系统徐厚骏[摘要]RSA加密算法是由Rivest、Shamir和Adleman提出的基于素数理论的密码系统，是第一个较为成功的公钥密码系统，也是目前应用比较广泛的公钥密码系统，本文较详细地给出了RSA公钥密码系统的证明，同时给出了操作方法和安全性说明。[关键词]数据通讯信息加密公钥密码系统RSA加密算法⒈前言我国的因特网(Internet)现已经发展到商业网，E-Mail已广为应用，另外还有三金工程，各部门、各行业、各省市的行业网、地区网的建成，数据传输比当年CHINAPAC网的应用更为普遍。金融、商业、政府等的通信对保密的要求愈来愈高，从而激起了对数据通讯中的

2、信息加密研究的热情。从商业角度来说，DES是一个很好的加密算法，而为了提高安全性和避开传递密钥的麻烦，人们广泛地使用临时随机密钥，这需要用RSA算法对其密钥加密。RSA公钥密码系统由于加密密钥公开，为信息加密带来了极大的方便，更由于RSA加密算法可以方便地实现数字签名，在网络通信高度发达的今天，意义更加显得突出。自1994年四季度起，我国CHINAPAC网加大了宣传力度并实行了一系列优惠措施。1995年．使用E-Mail的用户迅速增加．数据通讯中的信息加密开始在我国民间受到重视。由于DES数据加密标准算法较早传人我国，相对来说掌握此项技术的人也较多．所以相当多的用户使用了DE

3、S算法。但是DES算法的密钥只有2^56≈7.21e16。显然有些不足，所以DES算法的可靠性一直受到广泛关注。1995年，129位十进制数RSA129在1993年被成功破译的信息传来后，人们根据运算工作量估算，对当前速度最快的计算机，穷举搜索这7.21e16个密钥大概只需要几天或十几天的时间。又考虑到美国已经提出了第三方保管密钥的加密标准(TheEscrowEncryptionStandard简称为‘EES’)采用80bit密钥称作SKIPJACK的加密算法，欧洲提出了128bit密钥处理64bit数据块的加密算法称作国际数据加密算法(TheInternotionalDat

4、aEncryptionAlgorithm简称为‘IDEA’)。另外，使用三个不同密钥的三重DES加密算法也在使用，因此出现了完善现有加密算法以适应Internet和E-Mail的要求。经过充分比较，认识到把公钥密码技术和密钥密码技术相结合，可以获得安全性和高性能的结合。为此选择了使用临时随机密钥的DES算法加密信息，再使用RSA算法对DES密钥进行数字签名和加密，为了避免冒充，数字签名是必须的。因此，解决RSA算法的关键问题成为这一工作成功的保证。笔者在实施过程中对其有了一个较全面的了解，现介绍如下。⒉必要的数论知识2．1因子分解素数：只能被1和该数自身除尽的整数。合数：不是

5、l且非素数的整数。最大公因子：若a能除尽b且a也能除尽c，即a是b和c的公因子，若b和c的每个公因子都能除尽a，则a是b和c的最大公因子，表示为：a=gcd{b，c}定义：若gcd{a，b}=士1。则称a和b互素。定理l：每一个正合数都可表示为正素数的乘积，且当不考虑乘积的顺序时，表示方法是唯一的。素数的个数是无限的，不大于正整数N的素数个数P，有比较精确的近似式如下：1PLi(N)=−Li(N)2其中xdtLi(x)=∫ln(t)2展开式为：23(ln(x))(ln(x))Li(x)=ln(ln(x))+ln(x)+++…2×2!3×3!2．2同余模运算：b=mod(a，m

6、)，表示a除以m的余数为b。定义：若mod(a，m)=mod(b，m)，则可写作a＝km十b，k为一整数，我们称a和b模m同余，记作：a≡b(modulom〕其中m称为这个同余式的模。定理2：模m的同余关系满足(1)自反性：即a≡a(modulom)；(2)对称性：即若a≡b(modulom)，则b≡a(modulom)；(3)传递性：即若a≡b(modulom)，且b≡c(modulom)，则a≡c(modulom)。定理3：若a≡b(modulom)且c≡d(modulom)，则(1)a±c≡b±d(modulom)；(2)a×c≡b×d(modulom)。定理4：若a×

7、c≡b×c(modulom)且d=gcd{c，m}，则a≡b(modulom/d)。2．3同余类Euler函数：在0、l、2、……m-1这m个数中，和m互素的数的个数称为数m的Euler函数，表示为Φ(m)。每个整数，总是与0、1、2……m-1这m个数中的一个数r模m同余，且仅和这一个数模m同余，所有模m和r(0<=r<=m-1)同余的整数，组成一个“同余类”，用[r]表示。如果r与模数m互素，则同余类[r]中的每个数都与m互素，称作同余类[r]与模数m互素。所以模数m的Euler函数Φ(m)即代表了和