计算机网络安全基础概论-密码学-RSA

一、加密算法概述

1、加密与解密

    加密是以某种特定的算法，改变原有的数据信息，使得未授权的用户即使获得了加密后的数据，但因不知解密的方法（确切的说是不知道密钥），仍然无法了解其信息内容。而解密则是加密的逆过程。

2、明文和密文

    我们称尚未加密的数据为明文，通过固定算法加密后的数据为密文。

3、加密的密钥

    密钥是一种参数，它是在明文转换为密文或密文转换为明文时算法的输入参数。可以理解成密码的钥匙。

4、对称与非对称

    常见的数字加密方式分为两类：对称加密 和 非对称加密。

对称加密

    对称加密算法中，数据发送方将明文和密钥一起经过特殊加密算法处理成密文后，将它发送出去。接收方收到密文后，若想解读原文，则需要使用加密用到的相同密钥及相同算法的逆算法对密文进行解密，才能使其恢复成原文。
    它的最大优势是加/解密速度快，适用于大数据量进行加密，缺点是密钥管理困难，最典型的问题就是如何同步这个密钥，同步过程如果在公网上，不进行加密是可以抓包拿到的，那么这里就遇到了要对密钥加密的问题。
    常见的对称加密算法有 AES、DES、Blowfish 等等。
    对称加密的核心是只有一把密钥。

非对称加密

    非对称加密算法中，有两个密钥：公钥和私钥。它们是一对，如果用公钥进行加密，只有用对应的私钥才能解密；如果用私钥进行加密，只有用对应的公钥才能解密。
    非对称加密算法实现机密信息的交换过程为：甲方生成一对密钥并将其中一个作为公钥向其他方公开；得到该公钥的乙方使用该密钥对机密信息进行加密后发送给甲方；甲方再用自己的另一个专用密钥对加密后的信息进行解密。
    最有名的非对称加密算法当属 RSA 了，本文将对 RSA 算法的加/解密过程进行详细剖析。
    非对称加密拥有两把密钥。

二、非对称加密-RSA算法流程

1、算法原理

    算法本身基于一个简单的数论知识：给出两个素数，很容易将它们相乘，然而给出它们的乘积，想得到这两个素数就显得尤为困难。如果能够解决大整数（比如几百位的整数）分解的快速方法，那么 RSA 算法将轻易被破解。

2、公钥和私钥的生成

RSA 算法基于大整数因子分解的困难性，该算法的步骤如下：

第一步，生成两个大素数 p和q（p和q互素） 。 

第二步，计算这两个素数的乘积 n=pq

第三步，计算小于n并且与n互素的整数的个数，即欧拉函数φ(n) = (p-1)(q-1)

第四步，选取 1个随机数e ，且满足 1<e< φ(n) ，并且e和φ(n) 互素，即 gcd(e ，φ(n) ) =1

第五步，计算 d=e^(-1) * modφ(n)

第六步，保密d、p、q, 而公开 e, 私钥：（n，d），公钥：（n，e）。

3、RSA 加密

    对于明文 M，用公钥（n，e）对 M 进行加密的过程，就是将 M 转换成数字（字符串的话取其 ASCII码或者 unicode 值），然后通过幂取模计算出 C 就是密文；

加密公式：   C =M^e mod n

4、RSA 解密

 对于密文 C ，用私钥（n，d）对 C 进行解密的过程，和加密类似，同样是计算幂取模；

解密公式：   M =C^d mod n

三、RSA算法示例

设素数 p=3, q=17, 并令 e=13, RSA 的加密操作，如下：

第一步 ，计算 n, n=pq=3 X 17=51, 得出公钥 n=51, e =13；

第二步 ，计算 φ(n) ， φ(n) = (p-1)(q-1) = 2 X 16 = 32 。

因为 d= e^(-1) mod φ(n) ，所以d=(K φ(n) +1) /e，其中k是 p-1和q-1 的最大公约数。由此算出 = (2 x 32 + 1) / 13 = 5, 即解密密钥 d=5。

第三步，加密和解密处理计算。假设 Bob 的公开密钥是 e=13 n=5l, Alice 需要将明文 “2" 发送给 Bob, Alice 首先用 Bob 的公开密钥加密明文，即：

C =M^e mod n  =2^13 mod 51 =8192 mod 51 =32

第四步， Bob 收到 Alice 发来的密文 后，用自己的私钥d解密密文 C, 即：

M =C^d mod n =32 ^5 mod 51 =1024x1024x32mod51=2

四、RSA算法注意事项

    RSA 安全性保证要做到选取的素数p和q足够大，使得给定了它们的乘积n后，在事先不知道p或q的情况下分解n是计算上不可行的。

    因此，破译RSA 密码体制基本上等价千分解n。基于安全性考虑，要求n长度至少应为1024 比特，然而从长期的安全性来看，

n的长度至少应2048比特，或者是616位的十进制数。

原文始发于微信公众号（从放弃到入门）：计算机网络安全基础概论-密码学-RSA