当前位置：文档之家 › 公钥密码体制实现

公钥密码体制实现

  • 格式：docx
  • 大小：108.85 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

第4章公钥密码体制

第4章公钥密码体制

密钥
为公钥。 不再需要， 以n，e为公钥。私密钥为d。(p, q不再需要， 可以销毁。 可以销毁。)
RSA算法在计算上的可行性
加密和解密
无论是加密还是解密都需要计算某个整数的模n 整数次幂，即C=Me mod n、M=Cd mod n。但不 、 需要先求出整数的幂再对n取模，而可利用模运 算的性质： (a mod n) * (b mod n)= (a*b) mod n 对于Me mod n，可先求出M1 mod n，M2 mod n， M4 mod n……，再求Me mod n
RSA算法 RSA算法
RSA Algorithm
概况
MIT三位年轻数学家, 1979年发现了一种用数 论构造双钥的方法，称作MIT 体制 MIT体制 MIT 体制，后来被 广泛称之为RSA体制 RSA体制 RSA体制。 它既可用于加密、又可用于数字签字。 RSA算法的安全性基于数论中大整数分解的 困难性。 迄今为止理论上最为成熟完善的公钥密码体 制，该体制已得到广泛的应用。
公钥密码体制有4个组成部分
明文：算法的输入，它们是可读信息或数据，用M 表示； 密文：算法的输出。依赖于明文和密钥，对给定的 消息，不同的密钥产生密文不同。用E表示； 公钥和私钥：算法的输入。这对密钥中一个用于加 密，为Ke，此密钥公开；一个用于解密，为Kd，此 密钥保密。加密算法执行的变换依赖于密钥； 加密、解密算法
选p=7，q=17。 求n=p×q=119，φ(n)=(p-1)(q-1)=96。 取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确 定满足d·e=1 mod 96且小于96的d，因为 77×5=385=4×96+1，所以d为77。 因此公开钥为{5，119}，秘密钥为{77，119}。 设明文m=19，则由加密过程得密文为 C=195 mod 119≡2476099 mod 119=66 解密为6677mod 119=19

公钥密码体制公钥密码体制

公钥密码体制公钥密码体制

首次公开提出了“公开密钥密码编码学”的概念。
这是一个与对称密码编码截然不同的方案。
提出公开密钥的理论时，其实用性并没有又得到证明：
❖ 当时还未发现满足公开密钥编码理论的算法； ❖ 直到 1978 年，RSA 算法的提出。
2.基本特征
❖ 加密和解密使用两个不同的密钥 公钥PK：公开，用于加密，私钥SK：保密，用作解密 密钥
3.优点
❖ 密钥管理
加密密钥是公开的； 解密密钥需要妥善保存； 在当今具有用户量大、消息发送方与接收方具有明显的信息不对称
特点的应用环境中表现出了令人乐观的前景。 新用户的增加只需要产生一对公共/私有密钥。
❖ 数字签名和认证
只有解密密钥能解密，只有正确的接收者才拥有解密密钥。
缺点：公共密钥系统的主要弱点是加密和解密速度慢。
加密与解密由不同的密钥完成； 知道加密算法，从加密密钥得到解密密钥在计算上是不可行的； 两个密钥中任何一个都可以作为加密而另一个用作解密。
6.公钥密码算法
除RSA算法以外，建立在不同计算问题上的其他公钥密码算法 有：
基于因子分解问题的Rabin算法； 椭圆曲线公钥算法； 基于有限域中离散对数难题的ElGamal公钥密码算法 基于代数编码系统的McEliece公钥密码算法； 基于“子集和”难题的Merkle-Hellman Knapsack（背包）公钥密码算 法； 目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。
实际应用中的加密方式
❖ 混合加密技术 对称密码体制：密钥分发困难 公钥体制：加解密效率低 将对称加密算法的数据处理速度和公钥算法对密钥的保 密功能相结合 利用对称加密算法加密传输数据 利用非对称加密算法交换会话密钥
实际应用中的加密方式

公钥密码体制加密及签名的原理

公钥密码体制加密及签名的原理

公钥密码体制加密及签名的原理
公钥密码体制是一种基于非对称密码算法的密码体制，其中包括加密和签名两个过程。

加密原理：
1. 首先，生成一对密钥，即公钥和私钥。

公钥可以公开，供他人使用，而私钥只能由密钥的拥有者保密。

2. 使用公钥对要传输的明文进行加密。

公钥加密是一种单向操作，即使用公钥加密的数据只能使用相应的私钥进行解密。

3. 将加密后的密文发送给接收者。

4. 接收者收到密文后，使用自己的私钥进行解密，得到原始的明文。

签名原理：
1. 所发送的消息使用发送者的私钥进行加密生成签名。

加密操作可以确保除发送者外的其他人无法更改签名。

2. 发送签名和原始消息给接收者。

3. 接收者使用发送者的公钥对签名进行解密，得到原始的消息。

4. 接收者还可以使用发送者的公钥对原始的消息进行解密，以验证签名的真实性和完整性。

总结：
公钥密码体制通过使用非对称密钥对（公钥和私钥）进行加密和解密，实现了加密和签名的功能。

加密过程使用接收者的公钥对消息进行加密，只有接收者的私钥才能解密。

签名过程使用发送者的私钥对消息进行加密，接收者使用发送者的公钥对
签名进行解密，以验证签名的真实性和完整性。

这种体制保证了信息的机密性和完整性。

公钥密码体制加密及签名的原理

公钥密码体制加密及签名的原理

公钥密码体制加密及签名的原理
公钥密码体制是一种使用公钥加密和私钥解密的密码体制。

它有两个主要的应用：加密和签名。

加密的原理：加密方使用接收方的公钥将明文加密，加密后的密文只能使用接收方的私钥进行解密。

这样，只有接收方才能解密得到明文，从而实现了加密和保护数据的目的。

签名的原理：签名方使用自己的私钥对消息进行签名，签名后的消息和签名一起传送给验证方。

验证方使用签名方的公钥对接收到的签名进行验证，如果验证成功，则说明消息的真实性和完整性得到了保证。

因为私钥是唯一的，只有签名方能够生成正确的签名，其他人无法伪造签名，因此可以使用签名来验证消息的身份和完整性。

公钥密码体制的安全性基于两个关键问题：一是计算性难题的难解性，例如大数分解问题和离散对数问题；二是公钥和私钥的关联性，即通过公钥无法计算出私钥。

公钥密码体制通过使用不同的数学原理和算法来实现加密和签名功能，常用的公钥密码体制包括RSA算法、椭圆曲线密码算法（ECC）和椭圆曲线数字签名算法（ECDSA）等。

这些算法利用数论、代数和椭圆曲线等数学原理，结合计算机算法的运算和模运算，在保证安全性的前提下，实现了公钥密码体制的加密和签名功能。

公钥证书的原理

公钥证书的原理

公钥证书的原理
公钥证书的原理是利用公钥密码体制实现数字签名，保证公钥的唯一性和真实性。

具体来说，公钥密码体制包括公钥、私钥和加密解密算法三个部分。

公钥是公开的，可以由任何人使用，用于加密信息；私钥是保密的，只能由私钥持有者使用，用于解密信息。

加密解密算法则是公钥密码体制的核心，用于实现加密和解密操作。

在公钥证书中，公钥和私钥通过一种算法得到一个密钥对，将其中的一个向外界公开，称为公钥；另一个自己保留，称为私钥。

通过这种算法得到的密钥对能保证在世界范围内是唯一的。

使用这个密钥对的时候，如果用其中一个密钥加密一段数据，必须用另一个密钥解密。

比如用公钥加密数据就必须用私钥解密，如果用私钥加密也必须用公钥解密，否则解密将不会成功。

公钥证书用于管理公钥。

私钥在服务器端，公钥一般在证书中（证书可以简单理解就是比较安全防篡改的私钥）。

比方证书好比身份证（公钥+姓名+数字签名）。

在实际的使用中，有需要的人会生成一对公钥和私钥，把公钥发布出去给别人使用，自己保留私钥。

RSA公钥密码体制

RSA公钥密码体制
96 mol 5 = 1 用1代替96
5*d – k = 1 d=1 当k的系数最后化为1时，令d=1 情形2：
RSA公钥密码系统 算法示例
密钥生成： 取p=11，q=13，则 n=pq=11x13=143 φ(n)=(p-1)(q-1)=(11-1)x(13-1)=120 因为e与φ(n)互素，则选取e=17 通过ed = 1 mod φ(n)计算得d=113 公钥为(n,e)=(143,17)，私钥为d=113
通过例子来探讨如何求解d
例1 取p=3 q=11 f(n)=(p-1)(q-1)=2×10=20 即3×d = 1 mod 20
得出 n=p×q=3×11=33 取e=3，(3与20互质) 则 e×d = 1 mod f(n)
d怎样求解呢？ 怎样求解呢？ 怎样求解呢
可以用试算的办法来寻找。试算结果见下表：
79*d = 1 mod 3220
d
这里就要用到辗转相除法，解法如下：
79*d = 1 mod 3220
d=1019
k=25 d=19 k=6 d=1 k=0
79*d - 3220*k = 1
用3220对79取模到的余数60代替3220
79*d - 60*k = 1
用79对60取模到的余数19代替79
17*d = 1 mol 120
d = 113 17*d – 120*k = 1 k =16 d=1 当k的系数最后化为1时，令d=1
120 mol 17 = 1 用1代替120
17*d – k = 1
加密： 用公钥e=17对明文m=24进行加密，则密文为：
平方—乘算法
如何求解
解密： 收到密文c=7，利用私钥d=113进行解密：

SSL协议工作原理简述与应用

SSL协议工作原理简述与应用SSL（Secure Socket Layer）协议是一种用于保护互联网通信安全的协议。

它基于公钥密码体制来实现加密通信和身份验证，广泛应用于HTTP、FTP、SMTP等协议上，以保障数据的机密性和完整性。

下面将对SSL协议的工作原理和应用进行简述。

1.握手阶段：握手是SSL协议通信的第一步，用于建立安全通道。

通信的双方首先协商加密算法、密钥长度等参数，然后进行密钥交换。

握手过程中主要涉及以下几个步骤：- 客户端发送客户端Hello消息，其中包含客户端支持的加密算法、协议版本等信息。

- 服务器端发送服务器Hello消息，其中包含服务器支持的加密算法、协议版本等信息。

-服务器端对客户端进行身份验证，通常采用数字证书。

服务器向客户端发送数学证书，客户端对证书进行验证，确认服务器身份的合法性。

-客户端生成对称加密密钥，并使用服务器的公钥对其进行加密，然后发送给服务器。

-服务器使用私钥解密客户端发送的密钥，然后双方都拥有了同一份对称加密密钥。

2.加密通信阶段：握手阶段完成后，双方就可以开始加密通信了。

在此阶段，通信的双方使用对称加密算法来对数据进行加密和解密，以保障数据的机密性和完整性。

发送方使用对称加密密钥对数据进行加密，接收方使用相同的对称加密密钥对数据进行解密。

3.完整性校验阶段：为了确保数据在传输过程中没有被篡改，SSL协议在通信的数据中添加了一份摘要信息，该摘要信息在客户端和服务器之间进行传递。

接收方通过计算数据的摘要信息，然后与传输过来的摘要信息进行比较，以验证数据的完整性。

1.HTTPS：HTTPS是基于HTTP协议的加密通信协议，它使用SSL协议对HTTP请求和响应进行加密，以保证数据的安全性。

在浏览器访问HTTPS网站时，通信的数据会通过SSL协议进行加密和解密，从而提供更安全的通信环境。

2.FTPS：FTPS是在FTP协议的基础上加入了SSL协议的安全文件传输协议。

第7讲 公钥密码体制


二、RSA密码体制
参数选择：
独立地选取两大素数p1和p2(各512bit的数)， 计算 n=p1×p2 其欧拉函数值(n)=(p1－1)(p2－1) 随机选一整数e， 1e<(n)，((n), e)=1(因而在模(n)下e有逆元) d=e-1 mod (n) 公钥为n，e; 私钥为d (p1, p2不再需要，可以销毁)
* MIPS-年指以每秒执行1,000,000条指令的计算机运行一年
二、RSA密码体制
安全性:分解模数n
技术进展使分解算法和计算能力在不断提高，计算所需的硬件费用在不断下降 RSA-129： 110位十进制数字早已能分解。 Rivest等最初悬赏$100的RSA-129，已经 由包括五大洲43个国家600多人参加，用1600台机子同时产生820条指令数据， 通过Internet网，耗时8个月，于1994年4月2日
但数学上至今还未证明分解模就是攻击RSA的最佳方法，
也未证明分解大整数就是NP问题， 可能有尚未发现的多项式时间分解算法。 人们完全可以设想有另外的途径破译RSA， 如求出解密指数d或找到(p1－1)(p2－1)等。 但这些途径都不比分解n来得容易。 甚至Alexi等[1988]曾揭示，从RSA加密的密文恢复某些比特的困难性也和 恢复整组明文一样困难。 这一视在困难性问题是个NP问题，但还没人证明它为NPC问题。
因为(e1, e2,)=1，所以由Euclidean算法有r e1+s e2=1
计算 (y1-1)-r y2s = x mod n (假设r是负数)
二、RSA密码体制
安全性:低加密指数攻击
小的e可加快加密和验证签字速度，且所需的存储密钥空间小
但若加密钥e选择得太小，则容易受到攻击 网中三用户的加密钥e均选3，分别模n1, n2, n3 (互素，否则可求出公因子，而降低安全性)

RSA公钥密码体制简介

当要对明文进行加密时，可先进行预处理， 计算出m2、m3等，这种方法我们称之为窗口法。
32
例：
计算: 152013(mod 2539) 13 23 1 22 0 2 1 1101 B
(e3 , e2 , e1, e0 ) (1,1,0,1)
152013 mod2539
(((1520e3 )2 1520e2 )2 1520e1 )2 1520e0 (mod 2539) ((15202 1520)2 15200 )2 1520 (mod 2539)
14
RSA算法论证
假设截获密文C，从中求出明文M。他知道 M≡Cd mod n ，
因为n是公开的，要从C中求出明文M，必须先求 出d，而d是保密的。但他知道，
ed≡1 mod φ(n)， e是公开的，要从中求出d，必须先求出φ(n)，而 φ(n)是保密的。但他又知道，
φ(n)=(p-1)(q-1)，
9
RSA算法论证
于是，M tφ(n) ＝bq+1，其中b为某整数。 两边同乘M， M tφ(n)+1 ＝bqM+M 。 因为M＝ap，故 M tφ(n)+1 ＝bqap+M =abn+M 。 取模n得， M φ(n)+1 ＝M mod n 。
10
RSA算法论证
第二种情况：M＝0 当M＝0时，直接验证，可知命题成立。
加密过程：c=me mod n 解密过程：m=cd mod n
3
2、工作原理
定义：任给一个正整数m，如果用m去除任意两个整 数a、b所得的余数相同，称a、b对模m同余。记 为： a bmodm，若余数不同，则a、b对模m不同余。 记为： a b modm。
定理： a bmodm ，当且仅当m|(a-b)。

简述公钥密码体制的加密解密模型

公钥密码体制是一种常用的加密解密模型，它涉及到公钥和私钥两种不同的密钥，分别用于加密和解密数据。

在这篇文章中，我将深入探讨公钥密码体制的原理、应用以及安全性，以便读者能够全面了解这一加密解密模型。

### 第一部分：公钥密码体制的原理和基本概念1. 公钥密码体制的定义公钥密码体制是一种使用非对称密钥的加密解密模型，它包括公钥和私钥两种密钥。

公钥用于加密数据，私钥用于解密数据。

这种非对称密钥的设计使得通讯双方不需要共享相同的密钥，提高了信息安全性。

2. 加密和解密流程在公钥密码体制中，发送者使用接收者的公钥对数据进行加密，而接收者使用自己的私钥进行解密。

这一流程保证了只有接收者能够解密并获取原始数据，从而保护了数据的安全性。

3. 公钥密码体制的应用公钥密码体制被广泛应用于网络通讯、数字签名、加密货币等领域，为信息安全提供了重要保障。

它也为安全传输大量数据提供了有效的技术手段。

### 第二部分：公钥密码体制的安全性分析1. 公钥密码体制的安全性原理公钥密码体制的安全性建立在数学难题的基础上，如大数分解、离散对数等。

这些数学难题被认为是计算机无法在较短时间内解决的问题，因此数据得到了安全的保护。

2. 公钥密码体制的攻击方式尽管公钥密码体制被广泛应用，但也存在一些攻击方式，如中间人攻击、社会工程学攻击等。

这些攻击方式会威胁到公钥密码体制的安全性，因此需要采取相应的防护措施。

### 第三部分：个人观点与总结1. 个人对公钥密码体制的理解我个人认为公钥密码体制是一种非常强大且灵活的加密解密模型，它为信息安全提供了重要保障。

然而，随着计算机技术的发展，我们也需要不断升级和改进公钥密码体制，以应对新的安全挑战。

2. 总结公钥密码体制作为一种非对称加密解密模型，在信息安全领域发挥着重要作用。

通过深入了解其原理、应用和安全性，我们可以更好地理解和应用公钥密码体制，从而保护数据的安全性。

通过以上文章的撰写，我希望能够帮助您更深入地了解公钥密码体制的加密解密模型，并为您提供有价值的参考信息。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1) ，如果 ，则 ，否则 ，转向2)
2) ，若 ，转向5)，否则转向3);
3) ，转向4)；
4)若 ， ，转向2)；
5)计算出的y为 的结果，退出；
4RSA的实现
出了以上的算法，RSA还需要解决大数存储和运算的问题。目前一般计算机的字长都为32/64，而且一般的编译器只能编译64位以内的整数，即在程序中只能使用64位以内的整数，这对于要求几百上千位大整数的RSA体制来说是远远不够的。如何解决大整数的存储及运算对于RSA体制来说是十分关键的。目前常采用的大整数表示方法有两种，一种是使用数组存储二进制序列，另一种方法是直接存储十进制序列。前一种方法表示形式直观，编程简单，但是占用内存空间十分大，而且在显示和存储之间要进行进制转换，对如此长的序列进行运算效率较低。所以采用第二种方法要优于第一种方法。
若模数n被分解，则RSA系统被破解。根据RSA使用的领域，模数n的位数也有不同的要求：临时性使用384位，经过努力可以破解；商用512位，专业组织可以破解；军用1024位，10年内难以破解。电子邮件安全协议PDG中RSA使用的位数达到2047位。
私钥e和φ(n)互质的条件比较容易满足，为了加快加密解密的速度和节省存储空间，可以取较小的e，但e太小会导致RSA系统的安全性问题。一般的e的选取需要遵循以下原则：
1)用户A任选大素数p，q(保密)，计算n=p*q(公开)，φ(n) = (p-1)*( q-1)(保密)；
2)任选e满足gcd(φ( n), e) = 1，令e为A的加密密钥(公开)，计算d使得e*d≡1modφ(n)，d保密，e的公开不影响d的安全；
3)用户B欲将信息保密发送给A，先将信息数字化为m(m<n)，查看A的公钥e，n，计算 ，将C发送给A；
4.1大数运算
加法计算比较容易的，先从低位算起，因为只须要对应的位相加，再加上前一位的进位，再去判断是否本位是否有进位，有则把本位数字改为减去它的权，也就是10，再置进位为1。如果没有进位，则给进位赋值0。
减法较为复杂，因为要处理负数。用整型或其它类型时，则在处理、保存时会更为复杂。算法也是从低位开始减。先要判断减数和被减数那一个位数长，减数位数长是正常减；被减数位数长，则被减数减减数，最后还要加上负号；两数位数长度相等时，最好比那一个数字大，否则负号处理会很繁琐；处理每一项时要，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断是否能够减开被减数，如果减不开，就要借位后再去减，同时置借位为1，否则置借位为0。
确定性素数检测法，判断精确度很高，但运算花费的时间较长；概率性素数检测法，运算耗费较小，但要承担把一些合数误判为素数的风险。由于在RSA加密算法当中，合数被错误地当作素数实施加、解密时，除了会出现异常外，对数据的安全性并不会构成太大威胁。因此，采用误判率较低的素数检测法就可以很好的解决这一问题，故当前广泛采用并被深入研究的是素数的概率测试法。
b.计算
c.如果 并且 循环做下面的操作，否则转3：
Ⅰ
Ⅱ当 并且 循环做下面操作，否则跳到Ⅳ
Ⅲ计算 ，如果 返回“合数”，否则
Ⅳ如果 则返回“合数”
3)返回“素数”
Miller-Rabin算法是一个概率算法，算法的计算集中于(b)步和(c)步的循环中，最坏情况是Ⅳ的循环没有中途退出，则一轮Miller-Rabin算法的最坏情况复杂度为 (以模n乘法为基本操作)。如果以单精度乘法操作作为时间复杂度的衡量，则一轮优化的Miller-Rabin算法的最坏情况时间复杂度是 。从时间复杂度来看Miller-Rabin算法的性能是很好的。在实际应用中，Miller-Rabin算法的实际执行速度也很快。
RSA体制常采用Miller-Rabin算法来判断数性，Miller-Rabin算法描述如下：
输入：一个大于3的奇整数n和一个大于等于1的安全参数t（用于确定测试轮数）
输出：返回n是否是素数（概率意义上的，一般误判概率小于 ）即可
步骤：1)将n-1表示成
2)对i从1到t做循环做以下操作：
a.选择一个随机整数a
1公钥密码体制及其基础
不同于传统对称密码体制，在公钥密码体制中有两个不同的密钥。其中一个密钥是公开的，称为公钥，另一个是保密的，称为私钥。举个例子：当用户Bob要向用户Alice用密文通信时，Bob首先查找出Alice的加密密钥k，利用公开的加密算法E对明文m加密得到密文c=Ek(m)，Alice收到密文c后利用自己的解密算法D和解密密钥k′进行解密，得到明文m=Dk′(c)。公钥密码体制的基本方式如图1所示：
虽然RSA算法的安全性得到了人们的认可，但是RSA在进行加密和解密运算时的整数求幂运算耗时很大，所以RSA算法比对称密码体制加密（解密）同样明文（密文）的耗费时间多得多，这在一定程度上制约了RSA的应用广度。
下面就重点讨论RSA公钥密码体制的思想，算法和实现。
RSA算法是利用陷门单向函数的一种可逆模指数运算，它的安全性是基于大数因子分解的困难性。RSA体制的基本步骤如下：
公钥密码体制的实现
摘要：本文介绍了公钥密码体制的优点、缺点及其基本原理，重点分析了公钥体制的相关算法和实现。论文较为详细地介绍了用于数性判断的Miller-Rabin算法、求解最大公约数的Euclid算法、用于产生密钥的幂模运算算法。另外公钥体制加密是私钥与明文之间运算的过程。二者均是大数，要在目前32位和64位的计算机上实现公钥密码体制，必须解决大数存储和运算问题，本文讨论了两种大数表示方式：二进制序列表示和十进制序列表示。
乘法计算的算法，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加得出最后结果。直接用这种方法，需要要用多个链表来保存计算出的分结果，之后结果再相加得到最后结果，可以优化一下，只使用一个链表来表示结果，先把第一位乘数与被乘数的结果保存在链表中，之后把存储结果的头部后移一位，也就是从链表的第二加起，当第二位乘数与被乘数结果加到第二之后的各个项内。以此类推，直到结束。这样就可以用一个链表来存储相乘后的结果。
3.2最大公约数判断
RSA中公钥e与φ(n)的最大公约数应为1。Euclid算法是现在用于计算最大公约数的常用算法之一。Euclid的描述十分简单：记 表示非负整数 的最大公因数，那么： ，也可以写成： 为任意整数，即 。
比如： 。
其证明如下：
假定 ，那么有 和 。对任何正整数 ，可表示为如下形式： ,因此，有 ，k为某个整数。但由于 ，b也能整除kb,而 ，故有 ,这表明d也是b和 的公因子。由于这是可逆的，如果d是b和 的公因子，那么 ，且 ,这等同于 。这样a和b的公因子集合等同于b和(a mod b)的公因子集合。
a.e不可过小。一般选择e为16位的素数。这样既可以有效防止攻击，又有较快的加解密速度。
b.e应使其在mod(n)的阶为最大。
在许多RSA的应用中，希望使用位数较短的密钥以降低解密或数字签名的时间，如RSA在IC卡中的应用。目前已经证明当 时，可以由连分布式算法在多项时间内求出d的值，所以为了保证RSA的安全性，要求d的值不能小于 。
3RSA涉及算法
3.1素数检测算法
在RSA密码中，首先要产生2个大素数。素数在密码理论中占有极其重要的地位，但要判断一个大整数是否为素数却一：确定性素数检测法和概率性素数检测法。通过确定性素数检测法检测的数必定是素数。常见算法包括试除法、基于Lucas定理以及基于Pocslington定理的确定性素数检测法；通过概率性素数检测法检测的数为素数的概率为1-ε，其中ε为素数检测方法中可控制的任意小数，但不能为0。此类方法中较为著名的有Solovay-Strassen检测法、Lehmann检测法和Miller-Rabin检测法等。
关键词：公钥密码体制；RSA体制；算法
传统密钥的加密密钥与解密密钥采用同一个密钥，这个特点使得它有一些优点，但也存在着几个固有的缺点。首先，在进行安全通信之前，双方需要确定一个共同的密钥。这使得对称密钥在网络应用方面存在缺陷。在公共的网络信道中传对称密钥和使用该对称密钥加密的密文，这种信息通信方式是不安全的，其安全性无异于直接传递明文。其次，网络的发展提出了新的需要：如何确定消息来自某个特定的人而各方均无异议。传统加密方法显然不能满足这种需求，通信双方都可以利用密钥加密内容。
为了解决传统加密算法不能解决的问题，1976年，WhitefieldDaffier和Martin Hellman在著名的《NewDirectionsin Cryptography》一文中，为解决信息公开传送和密钥管理问题,首次提出公钥密码体制这一伟大的思想,他奠定了近代密码学的基础，并对近代密码学的发展产生了重大而深远的影响。
单向函数在密码学中起一个中心作用。它对公钥密码体制的构造的研究是非常重要的。虽然目一前许多函数被认为或被相信是单向的，但目前还没有一个函数能被证明是单向的。公钥密码体制也可以用来实现认证系统。
公钥体制加解密的方法与对称密码方法完全不同，所以公钥体制有着对称密码所没有的一些良好优点，并解决了对称密码体制固有的缺点。公钥密码体制密钥分配简单，密钥的保存量少。当互不相识的人需要进行秘密通话时，可以借助可信第三方方便的进行。另外公约密钥还可以完成数字签名和身份鉴别，这是对称密码所无法做到的。
3)存在信息k′，在已知k′时，对给定的任何y若相应的x存在则计算x=f-1(y)是容易的。
仅满足条件(1)和条件(2)的称为单向函数，第(3)条称为陷门性或称为陷门信息。其中，由x计算y的过程即为加密，由y、k′计算x的过程即为解密。
图2 单向陷门函数
设计公钥密码体制的关键是先要寻找一个合适的单向函数，大多数的公钥密码体制都是基于计算单向函数的逆的困难性建立的。例如，RSA体制就是典型的基于单向函数模型的实现。这类密码的强度取决于它所依据的问题的计算复杂性。值得注意的是，公钥密码体制的安全性是指计算安全性，而绝不是无条件安全性，这是由它的安全性理论基础即复杂性理论决定的。