RSA 算法简述

RSA是什么

• 计算机的加密技术分为对称加密和非对称加密两类。在对称加密中，信息的加解密使用同一秘钥key，其可简化加解密的过程，较为简单，但不足之处在于由于加解密使用同一个key，信息传送双方都要接触这个key，密钥key更容易泄露。
• 在公开密钥加密即非对称加密中，密钥分为公钥PK（发送方通过PK对数据加密，然后发送给接收方，PK可公开），私钥SK（SK解密方保存，接收方通过SK对密文解密，SK不公开）。RSA公钥密码体制是最具代表性的非对称加密方式。

RSA算法原理

• RSA定理：若P和Q是两个相异质数，另有正整数D和E，其中E的值与
• (P-1)(Q-1)的值互质，并使得DE%(P-1)(Q-1)=1，有正整数M，且M<PQ，设：
• C=ME%PQ，B=CD%PQ，则有M=B。

生成公钥和密钥

• 随意选择两个大的素数P和Q，且P不等于Q
• 令N=PQ
• 令T=(P-1)(Q-1)
• 选择一个整数E，作为一个密钥，使E与T互质(即E与T的最大公约数为1)，且E必须小于T
• 由公式DE%T=1，计算得到D的值，作为另一密钥
• 将(N，E)作为公钥，(N，D)作为私钥，当然也可互换。

用公钥加密信息

• 发送方收到公钥(N，E)后，通过公钥对数据进行加密，操作如下：
• 明文：M
• 加密：ME%N=C
• 密文：C

用私钥解密信息

• 接收方收到密文C后，通过私钥(N，D)进行解密，得到明文M，操作如下：
• 密文：C
• 解密：CD%N=M
• 明文：M

RSA算法模拟

为了计算方便，选取较小素数

生成公钥和密钥

• 取P=11，Q=13
• 令N=PQ=11*13=143
• 令T=(P-1)(Q-1)=10*12=120
• 取E=7
• 由公式DE%T=1，D*7%120=1得：D=103
• (143，103)作为公钥，将(143，7)作为私钥。

用公钥加密信息

• 明文：取M=2
• 加密：ME%N=C,2103%143=63
• 密文：C=63

用私钥解密信息

• 密文：C=63
• 解密：CD%N=M，637%143=2
• 明文：M=2

RSA的应用：数字签名

数字签名是实现安全的核心技术之一，它的实现基础就是RSA加密技术，它是RSA的典型应用。 以往的书信或文件是通过亲笔签名或印章证明其真实性的，但在计算机网络中，要解决报文的验证问题，就要使用数字签名，其必须保证以下几点：

• 接受者能够核实发送者对报文的签名
• 发送者事后不能抵赖对报文的签名
• 接受者不能伪造对报文的签名
• 在现有的多种实现数字签名的方法中，采用公开秘钥算法比常规算法更容易实现。
• 采用RSA实现数字签名的过程：
• 发送者A用其私钥SKA对报文M进行运算，将结果DSKA(M)发送给接受者B。
• 接受者B用已知的A的公钥得出EPKA(DSKA(M))=M。
• 因为除了A没人有A的私钥SKA，所以除了A没有人能产生密文DSKA(M)，这样，报文M就被签名了。用私钥加密的报文发给对方，对方只能用持有的公钥解密，这样就实现了核实发送者对报文的报文的签名。
• 如果发送者A要抵赖曾经发送过报文M给用户B，则用户B可将M和DSKA(M)出示给第三方监管机构，第三方很容易用公钥PKA去证实A确实发送报文M给用户B。反之，若用户B将M伪造为M’，则用户B就不能在第三方面前出示DSKA(M’)，这样就证明了用户B伪造了对报文M的签名。由此，可看出，实现数字签名的同时也实现了对报文来源的鉴别。

RSA算法的缺点

再强的加密算法，也有被破解的一天。RSA算法是被研究得最广泛的公钥算法，从提出到现在经历了各种攻击，被普遍认为是目前最优秀的公钥方案之一。 RSA的缺点主要有两点：

• 产生密钥很麻烦，由于素数产生技术的限制，难以做到一次一密。
• 分组长度太大，为保证安全性，N至少要600bit二进制位以上，运算代价高，速度慢。RSA算法的安全性依赖于大数分解，对于一个大数N，没有有效的方法能够将其分解，从而在已知(N，D)的情况下，无法获得E，同样在已知(N，E)的情况下无法求得D。目前，SET协议中要求CA采用2048bit二进制位长的密钥，其他实体使用1024比特的密钥。现在小于1024比特的N已被证明是不安全的，因此不应使用小于1024比特的RSA，最好使用2048位的N。

公钥加密

• 假设一下，我找了两个数字，一个是1，一个是2。我喜欢2这个数字，就保留起来，不告诉你们(私钥），然后我告诉大家，1是我的公钥。
• 我有一个文件，不能让别人看，我就用1加密了。别人找到了这个文件，但是他不知道2就是解密的私钥啊，所以他解不开，只有我可以用
• 数字2，就是我的私钥，来解密。这样我就可以保护数据了。
• 我的好朋友x用我的公钥1加密了字符a，加密后成了b，放在网上。别人偷到了这个文件，但是别人解不开，因为别人不知道2就是我的私钥，
• 只有我才能解密，解密后就得到a。这样，我们就可以传送加密的数据了。

私钥签名

• 如果我用私钥加密一段数据（当然只有我可以用私钥加密，因为只有我知道2是我的私钥），结果所有的人都看到我的内容了，因为他们都知
• 道我的公钥是1，那么这种加密有什么用处呢？
• 但是我的好朋友x说有人冒充我给他发信。怎么办呢？我把我要发的信，内容是c，用我的私钥2，加密，加密后的内容是d，发给x，再告诉他
• 解密看是不是c。他用我的公钥1解密，发现果然是c。
• 这个时候，他会想到，能够用我的公钥解密的数据，必然是用我的私钥加的密。只有我知道我得私钥，因此他就可以确认确实是我发的东西。
• 这样我们就能确认发送方身份了。这个过程叫做数字签名。当然具体的过程要稍微复杂一些。用私钥来加密数据，用途就是数字签名。

　　　　总结：公钥和私钥是成对的，它们互相解密。

　　　　公钥加密，私钥解密。

　　　　私钥数字签名，公钥验证。

举例

比如有两个用户Alice和Bob，Alice想把一段明文通过双钥加密的技术发送给Bob，Bob有一对公钥和私钥，那么加密解密的过程如下：

• Bob将他的公开密钥传送给Alice。
• Alice用Bob的公开密钥加密她的消息，然后传送给Bob。
• Bob用他的私人密钥解密Alice的消息。

　　上面的过程可以用下图表示，Alice使用Bob的公钥进行加密，Bob用自己的私钥进行解密。

公钥算法与私钥算法

私钥算法

私钥加密算法，又称 对称加密算法，因为这种算法解密密钥和加密密钥是相同的。也正因为同一密钥既用于加密又用于解密，所以这个密钥是不能公开的。

公钥算法

公钥加密算法，也就是非对称加密算法，这种算法加密和解密的密码不一样，一个是公钥，另一个是私钥：

公钥和私钥成对出现

• 公开的密钥叫公钥，只有自己知道的叫私钥
• 用公钥加密的数据只有对应的私钥可以解密
• 用私钥加密的数据只有对应的公钥可以解密
• 如果可以用公钥解密，则必然是对应的私钥加的密
• 如果可以用私钥解密，则必然是对应的公钥加的密
• 公钥和私钥是相对的，两者本身并没有规定哪一个必须是公钥或私钥。

实现数据的安全传输

• 要实现数据的安全传输，当然就要对数据进行加密了。
• 如果使用对称加密算法，加解密使用同一个密钥，除了自己保存外，对方也要知道这个密钥，才能对数据进行解密。如果你把密钥也一起传过去，就存在密码泄漏的可能。所以我们使用非对称算法，过程如下：
• 首先 接收方 生成一对密钥，即私钥和公钥；
• 然后，接收方 将公钥发送给 发送方；
• 发送方用收到的公钥对数据加密，再发送给接收方；
• 接收方收到数据后，使用自己的私钥解密。
• 由于在非对称算法中，公钥加密的数据必须用对应的私钥才能解密，而私钥又只有接收方自己知道，这样就保证了数据传输的安全性。

公钥算法的缺点

现实中，公钥机制也有它的缺点，那就是效率非常低，比常用的私钥算法（如 DES 和 AES）慢上一两个数量级都有可能。所以它不适合为大量的原始信息进行加密。为了同时兼顾安全和效率，我们通常结合使用公钥算法和私钥算法：

• 首先，发送方使用对称算法对原始信息进行加密。
• 接收方通过公钥机制生成一对密钥，一个公钥，一个私钥。
• 接收方 将公钥发送给 发送方。
• 发送方用公钥对对称算法的密钥进行加密，并发送给接收方。
• 接收方用私钥进行解密得到对称算法的密钥。
• 发送方再把已加密的原始信息发送给接收方。

接收方使用对称算法的密钥进行解密。

总结：

• 每个用户都有一对私钥和公钥。
• 私钥用来进行解密和签名，是给自己用的。
• 公钥由本人公开，用于加密和验证签名，是给别人用的。
• 当该用户发送文件时，用私钥签名，别人用他给的公钥解密，可以保证该信息是由他发送的。即数字签名。
• 当该用户接受文件时，别人用他的公钥加密，他用私钥解密，可以保证该信息只能由他看到。即安全传输。