首页 密码学

# 简述

1976 年，美国学者 Dime 和 Henman 为解决信息公开传送和密钥管理问题，提出一种新的密钥交换协议 (迪菲 - 赫尔曼密钥交换协议，简称 EDH)，允许在不安全的媒体上的通讯双方交换信息，安全地达成一致的密钥，这就是 “公开密钥系统”。

公钥（Public Key）与私钥（Private Key）是通过加密算法得到的一个密钥对（即一个公钥和一个私钥，也就是非对称加密方式）。公钥可对会话进行加密、验证数字签名，只有使用对应的私钥才能解密会话数据，从而保证数据传输的安全性。公钥是密钥对外公开的部分，私钥则是非公开的部分，由用户自行保管。

使用密钥对的时候，如果用其中一个密钥加密一段数据，只能使用密钥对中的另一个密钥才能解密数据。例如：用公钥加密的数据必须用对应的私钥才能解密；如果用私钥进行加密也必须使用对应的公钥才能解密，否则将无法成功解密。

# RSA 算法

在公私钥加密体系中，常见的加密算法有 RSA、 Cramer-Shoup、 Elgamal、以及椭圆曲线密码学等等。
而在日常中的 SSL 证书使用的基本都是 RSA 2048bit 加密算法。这里只解释 RSA 算法的数学原理。

# 概念

RSA 算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但这时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥（密钥并非只是乘积，还包括了 e）。

素数（质数）：指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。如 2，3，5，7，11，13，17…

# 一些数学概念

# 欧拉函数的定义

思考以下问题：
A：任意给定正整数 n，请问在小于等于 n 的正整数之中，有多少个与 n 构成互质关系？（比如，在 1 到 8 之中，有多少个数与 8 构成互质关系？）
Q：计算这个值的方法就叫欧拉函数，以 φ(n) 表示。在 1 到 8 之中，与 8 形成互质关系的是 1、3、5、7，所以 φ(n) = 4。

# 欧拉函数的计算

通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…*(1-1/pn), 其中 p1, p2……pn 为 n 的所有素因数，n 是不为 0 的整数.

# 欧拉函数的性质

  1. 对于素数 p，φ(p)=p−1
  2. 若 p 为素数，n=pk，则 φ(n)=pk-p^(k-1)
  3. 若 m,n 互素，则 φ(m∗n)=φ(m)∗φ(n)，特殊的，当 m=2，n 为奇数时，φ(2*n)=φ(n)
  4. 当 n>2 时，φ(n) 是偶数
  5. 小于 n 的数中，与 n 互素的数的总和为：φ(n) * n / 2 (n>1)
  6. n=∑d∣n​φ(d)，即 n 的因数（包括 1 和它自己）的欧拉函数之和等于 n

# 模反元素（e 和 d）

如果两个正整数 e 和 n 互素，那么一定可以找到整数 d，使得 ed-1 被 n 整除，或者说 ed 被 n 除的余数是 1. 这时，d 就叫做 e 对模数 n 的模反元素。

image-20220401132001422

# RSA 数学原理

RSA 的算法涉及三个参数，n、e、d。其中，n 是两个大质数 p、q 的积，n 用二进制表示时就是所占用的位数，就是所谓的密钥长度，即多少 bit 的加密长度。e 和 d 是一对相关的值（模反元素），e 可以任意取，d 由于 e 计算而得

要求 e 与 (p-1）*(q-1）互质（互质是公约数只有 1 的两个整数，如 7 和 11 和 13 等等）

再选择 d，要求（de）mod((p-1）(q-1））=1。

（n，e）,(n，d）就是密钥对。其中(n，e）为公钥，(n，d）为私钥。这里不能反过来用，把（n,d)当成公钥发布出去。因为从私钥生成公钥是通过正向的模运算算得的，计算机很快就能产生，但要反过来要计算机从公钥做逆模运算求得私钥，只要位数够长，就几乎是难以算出的。

因此 RSA 破解的难点就在于大素数 n 的因式分解上，我们很难对 n 进行分解得到 p 和 q ，得不到 pq 自然也得不到 e 和 d 。

RSA 加密是对明文的 E 次方后除以 N 后求余数的过程。
公钥加密体制中，一般用公钥加密，私钥解密
e 和 d 可以互换使用，即：

A=B^e mod n；

B=A^d mod n;

# RSA 例子

# RSA 算法密钥生成过程

・随意选择两个大的素数 p 和 q，p 不等于 q，计算 n = pq.
・根据欧拉函数的性质 3，求得 r=φ(n)=φ(p)φ(q)=(p-1)(q-1).
・选择一个小于 r 的整数 e, 且 e 与 r 互素；并求得 e 关于 r 的模反元素，命名为 d.(模反元素存在，当且仅当 e 与 r 互质；求 d 令 ed≡1 (mod r)）
・将 p 和 q 的记录销毁
其中 (n，e) 是公钥，(n，d) 是私钥.

・A 随机选两个不相等的质数 61 和 53，并计算两数的积 n=6153=3233，n 的长度就是密钥长度。3233 的二进制是 110010100001，一共 12 位，
・所以这个密钥就是 12 位。实际应用中，RSA 密钥一般是 1024 位，重要的场合是 2048 位.
・计算 n 的欧拉函数；φ(n)=(p-1)(q-1)=6052=3120.
・A 在 1 到 3120 上随机选择了一个随机数 e=17，与 3120 互素.
・计算 e 对 φ(n) 的模反元素 d，即 ed-1=kφ(n)。
・求解：17x+3120y=1. 用扩展欧几里得算法求解。可以算出一组解 (x,y)=(2753,-15)，即 d=2753. 公钥 (3233, 17)，私钥 (3233,2753)
至此完成计算.

# RSA 加密过程

假设 A 要向 B 发送加密信息 m，他就要用 B 的公钥 (n,e) 对 m 进行加密，但 m 必须是整数（字符串可以取 ascii 值或 unicode 值），且 m 必须小于 n. 所谓加密就是计算下式的 c:
m^e ≡ c (mod n)
假设 m=65,B 的公钥 (3233,17), 所以等式如下：
65^17≡2790（mod 3233）
所以 c 等于 2790，A 就把 2790 发给 B.

# RSA 解密过程

B 收到 A 发来的 2790 后，就用自己的私钥 (3233,2755) 进行解密
c^d ≡ m (mod n)
也就是 c 的 d 次方除以 n 的余数就是 m
2790^2753 ≡ 65 (mod 3233)
因此得到原文 65.