《密码学系列》轻松搞定公钥加密算法。

多点头发，少点代码。

本文已经收录至我的GitHub，欢迎大家踊跃star????。
GitHub
Hello，小伙伴们，《密码学系列》终于又要更新啦，今天小冯童学（没错，这是除了龙叔以外的另一位小姐姐）认真的分析了分析，发现《密码学系列》从第一期开始到现在已经两个多月了，虽然还有很多知识没有细细道来，但是基础框架已经基本完善了，如果小伙伴们在密码学方面还有别的问题，可以直接在公众号后台私信，随时在线，也欢迎大家多多关注微信公众号【龙跃十二】，龙叔和小冯童学继续为你分享知识。

在公要加密体制的分析之前，我们先聊聊数论…

数论：

数论是密码学特别是公钥密码学的基本工具，也是理解密码学的前提，所以还是要适当的了解一些简单的数论知识。或许当你看完数论知识，再回去看之前的密码学文章会有其他味道哦。

以下几个基本的数论知识，是小冯童学精心挑选出来的，看懂这几个，其他的都不是问题。

模运算 ：

设 n 是一正整数，a是整数，如果用 n 除 a，得商为 q， 余数为 r，则

a = qn + r， 0 ≤ r < n， q = [a/ n]

其中 [x] 为小于或等于 x 的最大整数。

用 a mod n 表示余数 r，则 a = [a/ n]· n + a mod n。 （ a mod n也就是常说的a模n取余）

费尔玛定理：

若 p 是素数, a 是正整数且 gcd( a, p) = 1,则 a^{p - 1} ≡ 1 mod p。（gcd是指最大公约数）

欧拉定理 ：

• 欧拉函数：设 n 是一正整数，小于 n 且与 n 互素的正整数的个数称为 n 的欧拉函数，记为 φ( n)。
• 欧拉定理：若 a 和 n 互素, 则 a^{φ( n)} ≡1 mod n

欧几里得算法:

欧几里得算法是数论中的一个基本技术,主要是用来求两个正整数的最大公因子的简化过程。

而推广的欧几里得算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。（emm…逆元是不是有是个新词，百度一下吧）

• 求最大公因子欧几里得算法是基于下面一个基本结论:

  对任意非负整数 a 和正整数 b，有 gcd( a, b) = gcd( b, a mod b)。

  因此可假定算法的输入是两个正整数，设为 d、f，并设 f > d。

• 2 求乘法逆元

  如果 gcd( a, b) = 1 ,则 b 在 mod a 下有乘法逆元( 不妨设 b< a) ,即存在一 x ( x < a) , 使得 bx≡1 mod a。推广的 Euclid 算法先求出 gcd ( a, b) , 当 gcd ( a, b) = 1 时, 则返回 b 的逆元。

平方剩余

设 p 是一素数，a 小于 p，称 a 是 p 的平方剩余，如果方程 x² ≡ a ( mod p) 有解。否则称为非平方剩。

emmm…小冯童学还是觉着这几个是平日里用的多的，小伙伴们还是需要多了解一下。

公要密码体制：

在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。

而公钥密码体制则为密码学的发展提供了新的理论和技术基础。

• 公钥密码算法的基本工具不再是代换和置换，而是数学函数。
• 公钥密码算法是以非对称的形式使用两个**。

公钥密码算法的最大特点，概括起来就一句话：

采用两个相关**将加密和解密能力分开，其中一个**是公开的，简称公开钥，用于加密; 另一个**是为用户专用，因而是保密的，简称秘**，用于解密

因此公钥密码体制也称为双钥密码体制。

算法有以下重要特性: 已知密码算法和加***，求解***在计算上是不可行的。

加密：

我们来分解一下加密过程：

• ① 要求接收消息的端系统，产生一对用来加密和解密的**，如图中的接收者 B，产生一对** PK_B , SK_B ,其中 PK_B 是公开钥，SK_B 是秘**。
• ② 端系统 B 将加*** ( 如图中的 PK_B) 予以公开。另一**则被保密 ( 图中的 SK_B)。
• ③ A 要想向 B 发送消息m，则使用 B 的公开钥加密 m，表示为 c= E PK_B [ m]， 其中 c 是密文，E 是加密算法。
• ④ B 收到密文 c 后用自己的秘** SK_B 解密，表示为 m =DSK_B [ c] ， 其中 D 是解密算法。

认证：

公钥加密算法不仅能用于加、解密,还能用于对发方 A 发送的消息 m 提供认证。

户 A 用自己的秘** SK_A对 m 加密,表示为 c = ESK_A [ m]

将 c 发往 B。B 用 A 的公开钥 PK_A 对 c解密, 表示为 m = DPK_A [ c]，因为从 m 得到 c 是经过 A 的秘** SK_A 加密,只有 A 才能做到。因此 c 可当做 A 对 m 的数字签字。

另一方面，任何人只要得不到 A 的秘** SK_A就不能篡改 m,所以这个过程获得了对消息来源和消息完整性的认证。

以上认证过程中，由于消息是由用户自己的秘**加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性, 可使用双重加、解密。

双重加解密：

发方首先用自己的秘** SK_A对消息 m 加密，用于提供数字签字。再用收方的公开钥 PK_B第 2 次加密，表示为

c = E_PKB [ E_SKA [ m]] 解密过程为 m = D_PKA [ D_SKB [c]] 即收方先用自己的秘**, 再用发方的公开钥对收到的密文两次解密。

这就是公要加密体制的基本内容，你是不是想问怎么还不讲算法，下来我们就看看关于公要加密体制的算法。

RSA算法：

RSA 算法是 1978 年由 R.Rivest , A.Shamir 和L.Adleman 提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制。

**的产生：

① 选两个保密的大素数 p 和 q。

② 计算 n = p× q，φ( n) = ( p - 1 ) ( q - 1) ,其中 φ( n)是 n 的欧拉函数值。

③ 选一整数 e, 满足 1 < e<φ( n) ，且 gcd(φ( n) , e)= 1。

④ 计算 d，满足 d·e≡1 mod φ( n) ,即 d 是 e 在模φ( n)下的乘法逆元， 因 e与φ( n)互素, 由模运算可知，它的乘法逆元一定存在。

⑤ 以{ e, n}为公开钥,{ d, n}为秘**。

加密：

加密时首先将明文比特串分组,使得每个分组对应的十进制数小于 n,即分组长度小于 log2 n。然后对每个明文分组 m,作加密运算:

c ≡ m^e mod n

解密：

对密文分组的解密运算为:m ≡ c^dmod n

计算问题：

RSA 的加密、解密过程都为求一个整数的整数次幂, 再取模。如果按其含义直接计算, 则中间结果非常大，有可能超出计算机所允许的整数取值范围，所以我们应该考虑如何提高加、解密运算中指数运算的有效性。

椭圆曲线密码体制：

为保证 RSA 算法的安全性，它的**长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制 ECC( elliptic curve cryptography) 可用短得多的**获得同样的安全性，所以也就具有更大的使用空间。

我们先来看看什么是椭圆曲线？

高中毕业没几年的我们这个东西应该还有印象…hhhhh

密码中普遍采用的是有限域上的椭圆曲线, 有限域上的椭圆曲线是指曲线方程定义 式y² +axy + by = x

³ +cx² +dx +e，所有系数都是某一有限域 GF( p) 中的元素 ( 其中 p 为一大素数) 。其中最为常用的是由方程 y² +axy + by = x³ +ax +b( mod p) ，其中( a, b ∈ GF( p) , 4a³ + 27b²( mod p) ≠ 0) 。

Diffie-Helmlan**交换：

• 首先取一素数 p≈2¹⁸⁰ 和两个参数 a、b，则得上边说到的方程来表达的椭圆曲线及其上面的点构成的 Abel 群 Ep ( a, b)。

• 第 2 步,取 Ep ( a, b)的一个生成元 G( x1 , y1 )，要求 G 的阶是一个非常大的素数， G 的阶是满足 nG = O的最小正整数 n。Ep ( a, b) 和 G作为公开参数。

两用户 A 和 B 之间的**交换如下进行:

① A 选一小于 n 的整数 n_A ，作为秘密，并由 P_A= n_A G产生 Ep ( a, b)上的一点作为公开钥。

② B 类似地选取自己的秘** n_B 和公开钥P_B 。

③ A、B 分别由 K = n_AP_B和 K =n_BP_A 产生出双方共享的秘**。

EGlamal密码体制

• **产生过程: 首先选择一素数 p 以及两个小于 p 的随 机数 g 和 x，计算 y≡ g^x mod p。以( y、g、p)作为公开**，x作为秘***。

加密过程: 设欲加密 明文 消 息 M, 随 机 选一 与 p - 1 互 素 的整 数 k, 计 算 C₁ ≡ g^k mod p，C₂ ≡ y^k Mmod p, 密文为 C = ( C1 , C2 )。

解密过程: M = (C₂/ C₁^x) mod p

关于公要密码体制，还有很多算法，在文中所提到的算法都是应用广泛的算法，这里的内容就更加的偏数学方面。

相信看到这里的小伙伴，一定有人是这种表情…

还有人…

小伙伴们如果有不理解的，可以直接在龙叔公众号后天点击【联系我】，添加龙叔微信，留下你的问题，定时回复哦，也希望大家多多关注小冯童学和龙叔的公众号【龙跃十二】，一个分享互联网技术和心路历程的地方。
如果文章对你有帮助，点个赞可好？