应用密码学作业

由天下分享时间：2025/1/13 11:48:46 加入收藏我要投稿点赞

应用密码学作业

姓名：隋鑫学号：03111326 班级：031113班学院：计算机学院电话：15109228792 任课教师：王超

RSA算法原理与实现

姓名：隋鑫学号：03111326 班级：031113班

摘要

RSA算法是目前使用最广的公钥密码算法,本文比较全面地从原理到实现介绍了这个得到广泛接受和实现的算法，并简要讨论了RSA的安全性。最后，提出了自己对RSA算法理论和应用发展的一些想法。

1.引言

公开密钥密码算法的提出是整个密码学历史上最大的而且也是一场真正的变革。从最初一直到现代，几乎所有密码系统都建立在基本的替代和置换工具的基础上。在用了数千年的本质上可以手算完成的算法之后，常规的密码学随着转轮加密/解密机的发展才出现了一个重大进步。机电式变码旋转软件使得极其复杂的密码系统被研制出来。有了计算机后，更加复杂的系统被设计出来。但是不管是转轮机还是后来的DES（数据加密标准），虽然代表了重要的进展，却仍然依赖于替代和置换这样的基本工具。

公钥密码学则与以前的所有方法都截然不同。一方面公开密钥算法基于数学函数而不是替代和置换，更重要的是，公开密钥密码学是非对称的，它用到两个不同的密钥，而对称的常规加密则只使用一个密钥。使用两个密钥对于保密通信，密钥分配和鉴别等领域都有着深远的影响。

RSA算法是目前应用最广的公钥密码，由Rivest,Shamir和Adleman在1977年提出。它基于一个非常简单的数论难题，很容易将两个素数乘起来，但分解该乘积却非常困难，从而，该乘积可以公开且可作为加密公钥。不能从该乘积恢复这两个素数。解密需要用到这两个素数。从而用很简单的形式实现了非常可靠的密码系统.

2.RSA算法描述

RSA公钥密码体制描述如下：

<1>. 选取两个大素数p,q。

<2>. 计算n=pq, Φ(n)=(p-1)(q-1)。

<3>. 随机选取正整数e, 1. 计算d,满足de≡1(mod Φ(n))。p,q,Φ(n), d是保密的，丢弃p,q,Φ(n);只保留d，则n,d为私钥；n,e是公开，为公钥。

<5>. 加密变换：对明文m, 1. 解密变换：对密文c, 1

证明：

由于de≡1(mod Φ(n)),所以存在正整数t，使得de = 1 + tΦ(n))。对于任意明文m, 1

当gcd(m,n)=1时，根据欧拉定理有cd≡(me)d≡(mΦ(n))tm≡1tm≡m(mod n); 当gcd(m,n)≠1时，因为n=pq且p,q是两个素数，所以gcd(m,n)=p或q。不妨设gcd(m,n)=p,则m=bp, 1?b

举例：如果p=47,q=71,那么n=pq=3337，Φ(n)=(p-1)(q-1)=3220。加密密钥e满足gcd(e,Φ(n))=1,则随机选取e,如79,那么 d=e-1(mod Φ(n))=79-1(mod 3220)=1019。这时获得：

公钥：e,n 即79,3337

私钥：d,n即1019,3337