Math 加密算法

数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码为“密文”，使其只能在输入相应的密钥之后才能显示出原容，通过这样的途径来达到保护数据不被非法人窃取、阅读的目的。 该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程。

对称加密算法

对称加密（也叫私钥加密）指加密和解密使用相同密钥的加密算法，就是加密密钥能够从解密密钥中推算出来，同时解密密钥也可以从加密密钥中推算出来。而在大多数的对称算法中，加密密钥和解密密钥是相同的，所以也称这种加密算法为单密钥算法。它要求发送方和接收方在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都可以对他们发送或接收的消息解密，所以密钥的保密性对通信的安全性至关重要。

对称算法可分为两类。一次只对明文中的单个位（有时对字节）运算的算法称为序列算法。另一类算法是对明文的一组位进行运算，这些位组称为分组，相应的算法称为分组算法。现代计算机密码算法的典型分组长度为 64 位――这个长度大到足以防止分析破译，但又小到足以方便作用。

常见的对称加密算法

1. DES 算法

   DES 算法把 64 位的明文输入块变为数据长度为 64 位的密文输出块，其中 8 位为奇偶校验位，另外 56 位作为密码的长度。首先，DES 把输入的 64 位数据块按位重新组合，并把输出分为 L0、R0 两部分，每部分各长32位，并进行前后置换，最终由 L0 输出左 32 位，R0 输出右 32 位，根据这个法则经过 16 次迭代运算后，得到 L16、R16，将此作为输入，进行与初始置换相反的逆置换，即得到密文输出。

2. RC 算法
   RC4 算法的原理是“搅乱”，它包括初始化算法和伪随机子密码生成算法两大部分，在初始化的过程中，密钥的主要功能是将一个 256 字节的初始数簇进行随机搅乱，不同的数簇在经过伪随机子密码生成算法的处理后可以得到不同的子密钥序列，将得到的子密钥序列和明文进行异或运算（XOR）后，得到密文。

   由于 RC4 算法加密采用的是异或方式，所以，一旦子密钥序列出现了重复，密文就有可能被破解，但是目前还没有发现密钥长度达到 128 位的 RC4 有重复的可能性，所以，RC4 也是目前最安全的加密算法之一。

3. BlowFish 算法

   BlowFish 算法是一个 64 位分组及可变密钥长度的分组密码算法，该算法是非专利的。

   BlowFish算法使用两个“盒”：pbox[18]和sbox[4256]，BlowFish算法有一个核心加密函数。该函数输入 64 位信息，运算后以 64 位密文的形式输出。用 BlowFish 算法加密信息，需要密钥预处理和信息加密两个过程。BlowFish 算法的原密钥 pbox 和 sbox 是固定的，要加密一个信息，需要选择一个 key，用这个 key 对 pbox 和 sbox 进行变换，得到下一步信息加密所用到的 key_pbox 和 key_sbox。

   BlowFish 算法解密，同样也需要密钥预处理和信息解密两个过程。密钥预处理的过程和加密时完全相同。信息解密的过程就是把信息加密过程的key_pbox逆序使用即可。

非对称加密算法

非对称加密算法需要两个密钥：公开密钥（public key：简称公钥）和私有密钥（private key：简称私钥）。公钥与私钥是一对，如果用公钥对数据进行加密，只有用对应的私钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。

非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将公钥公开，需要向甲方发送信息的其他角色(乙方)使用该密钥(甲方的公钥)对机密信息进行加密后再发送给甲方；甲方再用自己私钥对加密后的信息进行解密。甲方想要回复乙方时正好相反，使用乙方的公钥对数据进行加密，同理，乙方使用自己的私钥来进行解密。另一方面，甲方可以使用自己的私钥对机密信息进行签名后再发送给乙方；乙方再用甲方的公钥对甲方发送回来的数据进行验签。甲方只能用其私钥解密由其公钥加密后的任何信息。

非对称密码体制的特点：算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂，而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥，并且是非公开的，如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全，而非对称密钥体制有两种密钥，其中一个是公开的，这样就消除了最终用户交换密钥的需要。这样安全性就高了很多。

常见的非对称加密算法

1. RSA

   RSA 是一种目前应用非常广泛、历史也比较悠久的非对称秘钥加密技术，在1977年被麻省理工学院的罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）三位科学家提出，由于难于破解，RSA 是目前应用最广泛的数字加密和签名技术，比如国内的支付宝就是通过 RSA 算法来进行签名验证。它的安全程度取决于秘钥的长度。目前业界推荐使用 2048 位或以上的秘钥，当然更长的秘钥更安全，但也意味着会产生更大的性能开销。

2. DSA

   Digital Signature Algorithm，数字签名算法，他是由美国国家标准与技术研究所（NIST）与1991年提出。和 RSA 不同的是 DSA 仅能用于数字签名，不能进行数据加密解密，其安全性和 RSA 相当，但其性能要比RSA快。

3. ECDSA

   Elliptic Curve Digital Signature Algorithm，椭圆曲线签名算法，是 ECC（Elliptic curve cryptography，椭圆曲线密码学）和 DSA 的结合，椭圆曲线在密码学中的使用是在 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出的，相比于 RSA 算法，ECC 可以使用更小的秘钥，更高的效率，提供更高的安全保障，据称 256 位的 ECC 秘钥的安全性等同于 3072 位的 RSA 秘钥，和普通 DSA 相比，ECDSA 在计算秘钥的过程中，部分因子使用了椭圆曲线算法。

RSA算法原理

生成公钥密钥

第一步，随机选择两个不相等的质数 p 和 q。

Sender 选择了 $p=2$ 和 $q=7$。

第二步，计算 p 和 q 的乘积 n。

Sender 计算出 $n = 2 × 7 = 14$

n 的长度就是密钥长度。14 写成二进制是 1110，一共有 4 位，所以这个密钥就是 4 位。

第三步，计算 n 的欧拉函数 $\varphi(n)$。

当 p 是质数，则 $\varphi(p)=p-1$。由于 $n = p1 \times p2$，因此

$$\varphi(n) = \varphi(p1 \times p2) = \varphi(p1) \times \varphi(p2) = (p1-1) \times (p2-1)$$

Sender 计算出 $\varphi(n) = 6$。

第四步，随机选择一个整数 e，条件是 $1 < e < \varphi(n)$，且 e 与 $\varphi(n)$ 互质。

Sender 选择了 $e = 5$。

第五步，计算 e 对于 $\varphi(n)$ 的模反元素 d。

所谓”模反元素”就是指有一个整数 d，可以使得 ed 被 $\varphi(n)$ 除的余数为 1。

$$ed \equiv 1 \ (mod \ \varphi(n))$$

这个式子等价于

$$ed - 1 = k \times \varphi(n)$$

于是，找到模反元素 d，实质上就是对下面这个二元一次方程求解（可使用辗转相除法求解）。

$$5 \times d - 6 \times k = 1$$

计算得出其中一组解为 $(d = 5, k = 4)$。

证明模反元素必然存在

$$a^{\varphi(n)} = a \times a^{\varphi(n)-1} \equiv 1 \ (mod \ n)$$

可以看到，$a^{\varphi(n)-1}$，就是 a 的模反元素。

第六步，将 n 和 e 封装成公钥，n 和 d 封装成私钥。

因此，公钥为 $(14, 5)$，私钥为$(14, 5)$。

RSA算法的加解密

假设 Recver 要向 Sender 发送加密信息 m，他就要用 Sender 的公钥 $(n,e)$ 对 m 进行加密。这里需要注意，m 必须是整数（字符串可以取 ascii 值或 unicode 值），且 m 必须小于 n。

所谓”加密”，就是算出式中的 c：$m ^ e \equiv c \ (mod \ n)$

假设 $m = 12$，公钥为 $(14, 5)$，可计算出密文 c 为 10。

Sender 拿到 Recver 发来的 10 以后，就用自己的私钥 $(14, 5)$ 进行解密。

所谓”解密”，就是算出式中的 m：$c ^ d \equiv m \ (mod \ n)$。

Sender 经计算后得到 12。

你可能会问，公钥$(n,e)$只能加密小于 n 的整数 m，那么如果要加密大于 n 的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种”对称性加密算法”（比如DES），用这种算法的密钥加密信息，再用 RSA 公钥加密 DES 密钥。

RSA密钥推测

假设我们当前只知道公钥 $(n, e)$，推导私钥 $(n,d)$。

首先，由于 d 是通过 $e \times d \equiv 1 \ (mod \ \varphi(n))$ 计算得出，因此需要知道 $\varphi(n)$。

我们知 $\varphi(n) = (p1-1) \times (p2-1)$，我们需要知道 p1 和 p2 才能知道 $\varphi(n)$。

因为 $n = p1 \times p2$，因此只有将 n 因式分解才能算出 p1 和 p2。此时意味着私钥被破解。

非对称加密算法的证明

下面证明：

$$c ^ d \equiv m \ (mod \ n)$$

根据加密规则 $m ^ e \equiv c \ (mod \ n) => c = m^e + kn$，

将 c 代入要证明的解密规则：$(m^e + kn)^d \equiv m \ (mod \ n)$

观察可知，等式左边的多项式拆开以后，只要是有 kn 的项都能被 n 整除，所以可以去掉所有含有 kn 的项，即等同于求证 $m^{ed} \equiv m \ (mod \ n)$。

由于 $ed \equiv 1 \ (mod \ \varphi(n)) => ed = h\varphi(n) + 1$

将 ed 代入：$m^{h\varphi(n) + 1} \equiv m \ (mod \ n)$

情况一：m 与 n 互质

根据欧拉定理，$m^{\varphi(n)} \equiv 1 \ (mod \ n)$ 得证。

情况二：m 与 n 不是互质关系

当 m 与 n 不互质时 (m < n)，由于 n = p * q，那么 $gcd(m,n) = p$ 或者 $gcd(m,n)=q$。

假设 $m=k_1 \times p$ 且已知 $m<n$，此时，m 必然与 q 互质。

根据欧拉定理，我们可以推导出：

$$(m^{(q-1)})^{h(p-1)} \ mod \ q = 1$$

根据之前的式子我们可以进行如下推导：

$$\varphi(n) = (p-1)(q-1) \\ ed=h\varphi(n)+1 \\ => m^{ed-1} \ mod \ q = 1$$

改写这个等式到

$$m^{ed-1} = k_3q + 1 => m^{ed} = k_3qm + m$$

将 $m=k_1 \times p$ ，$n=p \times q$ 代入上式

$$m^{ed} = k_1k_3 \times n + m$$

也就是 $m^{ed} \equiv m \ (mod \ n)$。得证。