RSA算法

爱丽丝将她的公钥( n {displaystyle n\,} & e {displaystyle e\,} )交给鲍勃，并对她的私钥保密。鲍勃想向爱丽丝发送消息M。

首先，他通过使用一个被称为填充方案的商定的可逆协议，将M变成一个比n {displaystyle m} 小的数字m {displaystyle n} 。然后，他计算出密码文本c {displaystyle c\,} ，对应于。

c = m e mod n {displaystyle c=m^{e}mod {n}}.

这可以用平方的指数化方法快速完成。然后鲍勃将c {displaystyle c\,} 发送给爱丽丝。

Alice可以通过使用她的私钥d {displaystyle d\,} ，在以下程序中从c {displaystyle c\,} 恢复m {displaystyle m,} 。

m = c d mod n {displaystyle m=c^{d}{bmod {n}}}.

给定m {displaystyle m,} ，她可以恢复原来的独立素数，将中国余数定理应用于这两个全等式中，可以得到

m e d ≡ m mod p q {displaystyle m^{ed}\equiv m{bmod {pq}}} 。

因此。

c d≡m mod n {displaystyle c^{d}\equiv m{bmod {n}}} 。

一个工作实例

这里是一个RSA加密和解密的例子。这里使用的参数是人为的小，但你也可以使用OpenSSL来生成和检查一个真正的密钥对。

1. 随机选择两个质数。
2. : p = 61 {displaystyle p=61} and q = 53 ; {displaystyle q=53;}.计算n = p q {displaystyle n=pq\,}
3. : n = 61 ∗ 53 = 3233 {displaystyle n=61*53=3233}。
4. 计算总商j ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle phi (n)=(p-1)(q-1)\,}。
5. ：j ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {displaystyle phi (n)=(61-1)(53-1)=3120}。
6. 选择e>1 {displaystyle e>1} 与3120的共质数
7. : e = 17 {displaystyle e=17}
8. 选择d {displaystyle d,} ，以满足d e mod j ( n ) ≡1 {displaystyle de{bmod {phi (n)}\equiv 1\,}。
9. : d = 2753 {displaystyle d=2753}
10. : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {displaystyle 17*2753=46801=1+15*3120} 。

公钥是( n = 3233 {displaystyle n=3233} , e = 17 {displaystyle e=17} ) 。对于一个填充的信息m {displaystyle m\,} ，加密函数c = m e mod n {displaystyle c=m^{e}{\bmod {n}} 成为。

c = m 17 mod 3 233 {displaystyle c=m^{17}{bmod {3}}233\,}

私钥是( n = 3233 {displaystyle n=3233} , d = 2753 {displaystyle d=2753} ) 。解密函数m = c d mod n {displaystyle m=c^{d}{bmod {n}}} 成为。

m = c 2753 mod 3 233 {displaystyle m=c^{2753}{bmod {3}}233\,}

例如，为了加密m=123 {displaystyle m=123}，我们要计算出m=123。，我们计算出

c = 123 17 mod 3 233 = 855 {displaystyle c=123^{17}{bmod {3}}233=855}

要解密c=855 {displaystyle c=855}，我们要计算出c=855。，我们计算出

m = 855 2753 mod 3 233 = 123 {displaystyle m=855^{2753}{bmod {3}}233=123}。

这两种计算都可以用模块指数化的平方和乘法算法来有效计算[en]。

使用欧拉定理和欧拉全等函数可以很容易地得出RSA。

从欧拉定理开始。

m j ( n ) ≡ 1 ( mod n ) {displaystyle m^{phi (n)}equiv 1{pmod {n}}.

我们必须证明，用正确的密钥解密一个加密信息，将得到原始信息。给定一个填充的信息m，密码文本c，计算方法是

c ≡ m e ( mod n ) {displaystyle c\equiv m^{e}{{pmod {n}}}.

将其代入解密算法，我们有

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{pmod {n}}。

我们想证明这个值也与m全等，e和d的值被选为饱和。

e d ≡ 1 ( mod ϕ ( n ) ){displaystyle edequiv 1{\pmod {\phi (n)}}.

这就是说，存在一些整数k，使得

e d = k × j ( n ) + 1 {\displaystyle ed=k\times phi (n)+1}。

现在我们代入加密后的信息，然后再解密。

m e d ≡ m k j ( n ) + 1 ≡ m × m k j ( n ) ≡ m × ( m j ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\&equiv m\times m^{k\phi (n)}\&equiv m\times \left(m^{\phi (n)}\right)^{k}{pmod {n}}end{aligned}}.

我们应用欧拉定理，得到了这个结果。

m × ( 1 ) k ≡ m ( mod n ) {displaystyle m\times (1)^{k}\equiv m{pmod {n}}.

在实践中使用时，RSA必须与某种形式的填充方案相结合，以便M的值不会导致不安全的密码文。没有填充的RSA可能有一些问题。

• 由于指数化的特性，m=0或m=1的值总是分别产生等于0或1的密码文本。
• 当用小的加密指数（例如，e = 3）和小的m值进行加密时，m e {displaystyle m^{e}}的（非模数）结果 ，可能严格小于模数n。在这种情况下，密码文本可能很容易通过取密码文本的eth根而不考虑模数来解密。
• RSA加密是一种确定性的加密算法。它没有随机成分。因此，攻击者可以成功地对密码系统发起选择明文攻击。他们可以通过在公钥下对可能的明文进行加密，并存储所得到的密码文来制作一个字典。然后，攻击者可以观察通信渠道。一旦他们看到与他们的字典中的密码文本相匹配，攻击者就可以使用这个字典，以了解信息的内容。

在实践中，当发送短的ASCII信息时，会出现前两个问题。在这种信息中，m可能是一个或多个ASCII编码字符的连接。一个由单个ASCII NUL字符（其数值为0）组成的信息将被编码为m = 0，这将产生一个0的密码文本，无论e和N的值是什么。同样，单个ASCII SOH（其数值为1）将始终产生1的密码文本。对于通常使用小e值的系统，如3，所有使用此方案编码的单字符ASCII信息将是不安全的，因为最大的m将有一个255的值，而255³ 是小于任何合理的模数。这样的明文可以通过简单地获取密码文本的立方根来恢复。

为了避免这些问题，实际的RSA实现通常在加密前将某种形式的结构化、随机化的填充嵌入到值m中。这种填充确保m不落入不安全的明文范围，并且一个给定的信息，一旦填充，将加密到大量不同的可能的密码文本中的一个。后者的特性可以增加字典攻击的成本，超过一个合理的攻击者的能力。

像PKCS这样的标准已经被精心设计，以便在RSA加密之前安全地填充信息。因为这些方案用一些额外的比特来填充明文M，所以未填充的信息M的大小必须小一些。RSA填充方案必须被精心设计，以防止复杂的攻击。这可以通过一个可预测的信息结构而变得更容易。PKCS标准的早期版本使用了临时性的结构，后来发现这些结构容易受到实用的自适应选择密码文本攻击。现代结构使用安全技术，如最佳非对称加密填充（OAEP）来保护信息，同时防止这些攻击。PKCS标准也有旨在为RSA签名提供额外安全性的处理方案，例如，RSA的概率签名方案（RSA-PSS）。

假设Alice使用Bob的公钥向他发送一个加密信息。在信息中，她可以声称自己是Alice，但Bob没有办法验证该信息是否真的来自Alice，因为任何人都可以使用Bob的公钥向他发送加密信息。因此，为了验证信息的来源，RSA也可以用来签署信息。

假设Alice希望向Bob发送一个签名信息。她产生一个信息的哈希值，将其提高到d mod n的幂（就像解密信息时一样），并将其作为一个 "签名 "附加到信息上。当Bob收到签名的信息时，他将签名提高到e mod n的幂（就像加密信息一样），并将所得的哈希值与信息的实际哈希值进行比较。如果两者一致，他就知道消息的作者拥有Alice的密匙，而且此后该消息没有被篡改过。

请注意，像RSA-PSS这样的安全填充方案对于信息签署的安全性和信息加密同样重要，而且同一密钥决不能同时用于加密和签署目的。