初识密码学-可汗学院公开课

发布时间：2026/10/28 18:46:11

2026.5.20 （本地obsidian）

1.算数基本定理

引入：古代如何知道时间？——观天象
现代时钟依据某种重复性规律，将时间分成相等的片段；而在古代，这些重复规律可以通过观察天空得到。

质数与合数

如一个月有29天，而29无法分成等份，只能分成基本单元，则29被认为是质数，不可分；
若一个数能被分为大于1的等份，就称之为合数。

好奇：质数的个数，可以有多大？——无数个，无穷大。

技巧：质数螺旋，发现持续到永远的质数规律，仍是未解之谜。

质数是积木

欧几里得意识到，所有数都可以分到质数和合数这两个类别中。
他首先意识到，任何数能不断进行除法，直到得到一组最小的不能进行除法的数字。根据定义，这些最小数字就是质数。所有数字都构建于这些质数之上，任何数字都能表示为一组质数，用质数之和表示。

![[Pasted image 20260520111322.png]]

算数基本定理的发现

质因数分解

![[Pasted image 20260520111430.png]]
得到质因数
![[Pasted image 20260520111850.png]]

将这些质因数相乘特定次数，可以得到原数
![[Pasted image 20260520112043.png]]
这里只需要把他们都相乘一次就可以得到30，也就是x=y=z=1
30的质因数分解=2×3×5

质因数分解的唯一性

这个分解过程可以被认为是特殊的钥匙和组合，没有其他质数相乘方式能得到同样的原数，也就是说，任意数字有且只有一种质因数分解。
可以将每个数字描述为一个不同的“锁”，它的钥匙就是该数的质因数分解，任意两个锁钥匙都不同
任意两个数质因数分解不同

2.公开密匙密码学

密钥引入

现在很多网络应用需要加密——保证安全
加密需要双方共享一个秘密的随机数——密钥，互联网拥有大量用户，两个互不见面的人，如何就共享密钥达成一致且不让第三方监听者知道？

单向函数

颜色的启示

混合两种颜色得到第三种颜色很容易，但已知混合色后，想知道原来两种颜色很难——这是锁的原理：朝一个方向容易，朝反方向难。这被称为单向函数。

构建单向函数（颜色为例）

先公开对某种颜色达成一致；随机选取私有颜色，混合到公开颜色中，从而掩饰掉私有颜色；互相发送混合色；

公开颜色：P 各自混合：A+P->C B+P->D

关键：再各自将私有颜色混合到另一个人的混合色，得到共享秘密颜色。

A+D->K D=B+P, K=A+B+P B+C->K C=A+P, K=B+A+P 确实得到同一种颜色，混合颜色的顺序不同

回看整个过程，K = P + A + B
第三方必须有一种私有颜色，才能确定这个共有颜色。

构建单向函数（数值）

对数字使用此技巧时，需要一个数值过程，该过程朝一方向容易，反方向难。

3.离散对数问题

模算术

时针算术

例：求46%12（46除以12的余数，取余=模运算）
找一根长46单位的绳子，将其缠绕在12单位的时钟周围，绳子终止的地方就是答案

![[Pasted image 20260520120535.png]]
![[Pasted image 20260520120526.png]]

离散对数问题（质模数、生成元、单向函数）

我们考虑质数作模数，x mod p （p是质数）

17作模数，找到17的原根 3，它具有以下重要性质
3^x mod 17 取不同幂次（x）时，结果会在时钟上均匀分布
3是一个生成元
![[Pasted image 20260520120911.png]]
取3的x次方
![[Pasted image 20260520121121.png]]

但相反的过程很难
3^x mod 17 = 12，给定12，求是3的多少次方，被称为离散对数问题
![[Pasted image 20260520121530.png]]

这样我们就拥有了单向函数，一个方向容易，但反向很难。已知12，我们只能采用试错法，求出匹配的指数。如果模数是长达数百位的质数，那么想解密是不切实际的。单向函数的强度取决于反向过程所需要的时间。
![[Pasted image 20260520121811.png]]

4.迪菲-赫尔曼密钥交换

密匙交换解决方法

3 mod 17
公开地就质模数(17)和生成元(3)达成一致，然后各自选择一个私有随机数

私有数A B 计算： 3^A mod17 = C 3^B mod17 = D

将结果公开发送
关键：

D^C mod 17 = K C^D mod 17 = K K = 3^A^B

相同运算，顺序不同
![[Pasted image 20260520124357.png]]

没有私有数字，则无法求出K（无法解决的离散对数问题，当数字足够大时，有限时间内，实践中无法破解）
至此我们解决了交换密匙的问题。
可以和伪随机数生成器结合使用，为未曾谋面的人提供通信加密

5.RSA加密：第一步

对称密匙

直到1970，密码学都是基于对称密匙：
发送者使用特定密匙加密信息，接受者使用相同密匙解密。

加密就是一种来自信息的映射，使用特定密匙来加密信息，要解密密文，你需要使用相同密匙，将映射逆转过来。

A和B想要安全通信，必须共享相同密匙。如果不见面，通常无法建立共享密匙，或者需要额外的通信开销，比如迪菲赫尔曼密钥交换。
如果A希望和多人通信，她需要和每个人交换不同密匙（私有密匙），则她需要管理好所有密匙，信息过多时就不方便了。

公开密匙加密

基于简单但聪明的概念：加锁和解锁是互逆操作。
A可以买一把锁，钥匙留在手上，把打开的锁发给B；B将自己的信息上锁发回给A。

这里无需交换密匙，锁可以公开，可以让世界上任何人用它来发消息，而A只需要一把钥匙。

关键：将密匙分为两部分，加密密匙，解密密匙。
解密密匙用于解密这一逆操作，加密通过加密密匙进行

加密和解密密匙（颜色为例）

B如何发给A一个颜色，并且防监听？

每种颜色都有互补色，和互补色叠加会得到白光，去掉了第一种颜色的作用。

假设混合颜色是一个单向函数
![[Pasted image 20260520125848.png]]
反向难

A生成自己的私有密匙（任意颜色a），假设A有一个秘密的机器，能找到这个颜色a的互补色，没有其他人知道，她将a的互补色发给B作为公开密匙；
假设B想发一种秘密的颜色b给A，他将颜色b与公开颜色混合，将混合色发给A；
A将私有色叠加到B的混合色，解除公开色的作用，得到b。

A + (-A) = O A发送私有色的互补色-A B将要发送的颜色与-A混合，得到C -A+ B = C A将私有色和混合色C混合，得到B C + A = -A + B + A = B 第三方有-A和C，

则第三方无法简单破译B的私有色，除非她有A的私有色。

我们还需要一种数学方法让这能用于实践。

6.RSA加密：第二步

陷门单向函数

需要构建一种特殊的单向函数，陷门单向函数，从一个方向计算容易，反过来难，除非有关于陷门的特殊信息。
![[Pasted image 20260520130910.png]]
![[Pasted image 20260520130929.png]]

模幂运算

回顾迪菲-赫尔曼密钥交换，时钟算术。

假设B有一段信息被化为数字m，他可以将这个数字自乘e次，e是公开指数，将结果除以随机数N ，m^e mod N = c，输出除法的余数c。
但反向难——已知c和e，难求m，需要试错过程。（?^e mod N = C）

这就是可以用于m的单向函数——数字锁
钥匙就是陷门，是某种让加密逆过程很容易的信息。
![[Pasted image 20260520175845.png]]
![[Pasted image 20260520175910.png]]

我们需要取c的其它次幂，比如d次幂，解除我们原来对m所进行的运算。

c^d mod N = m m^e mod N = c 将2式带入1式 (m^e)^d mod N = m m^(ed) mod N = m 得到m

e表示加密，d表示解密。
因此A需要有一种方法构建e和d，导致其他人很难求出d的值。
这需要第二个单向函数，用于生成d。

7.RSA加密：第三步

回顾：欧几里得证明了，每个数只有一种质因数分解，这可以考虑为一个密钥。

质因数分解从时间复杂度角度看很难，需要采用试错法，直到找到某数能均分n，此时，求解问题所需的时间，会随着数字的增大而飞速增长。

构建陷门

——质因数分解

step1.
A随机生成一个超过150位的质数，记作P1；随机生成位数相当于第二个质数，P2；将两个质数相乘，得到合数N，N超过300位（乘法计算时间短）；将N的分解——P1P2隐藏（陷门*），而将N告诉所有人。

step2.需要找一个函数，依赖于知道N的因数分解

8.欧拉函数

欧拉继续研究了质数分布的性质，定义了重要函数：φ函数，衡量数的可分性。对于给定数N，φ(N) 输出有多少个小于等于N，且和N没有公因数的整数

例：φ(8) = 找1~8中，和8没有公因数的整数有几个。

计算φ函数很难，除了一种情况

任意质数P，φ§ = p - 1

φ的乘法性质：φ(A* B) = φ(A) * φ(B)
已知N = P1 * P2
则φ(N) = 两个质数分别φ值的乘积 = （P1-1) * (P2-1)

9.RSA加密：第四步

现在有了求解φ的陷门（欧拉函数）
如果知道如何因式分解N ，那么求φ(N)就很容易。

eg. 77 = 7 * 11 -> φ(77) = 6 * 10 = 60

step3.

将φ函数和模幂运算联系起来

——欧拉定理
φ函数和模幂运算的关系如下
m^φ(n) = 1 mod n

这意味着你可以选择任意两个数字，让它们没有公因数。假设m，n，满足 m^φ(n) mod n = 1

下面只需使用两条简单规则处理这个等式

1^k = 1
同理，m^(k * φ(n) ) mod n = 1
1 * m = m
m^(k * φ(n) + 1) mod n = m
m^(e * d ) mod n = m
现在我们有了求e乘以d的等式，这依赖于φ(n)，只有当n的因数分解已知时计算d才容易。则d可以作为A的私有密钥，作为陷门，让她能解除e的作用。

RSA加密

B有一条信息，他使用某填充方案将其转化为数字m，爱丽丝按如下方式生成她的公开和私有密钥
首先生成2个大小类似的随机质数，将两者相乘得到n，计算φ(n)；选取一个小的公开指数，且必须是奇数，不同φ(n)具有公因数 e；求出私有指数d的值；
将这些都隐藏起来，只留下n和e的值，组成公开密匙，可以理解为开着的锁，发给B。让B锁上自己的信息。B上锁是通过计算m^e mod n，记作c，这是他的加密信息。发回给A。最后A用私有密匙d解密这个信息，通过陷门来访问（c^d mod n = m)。

第三方知道e，n，c，想知道d，只能通过计算φ(n)，这要求他们知道n的质因数分解。

RSA是使用最广泛的公开密匙算法。其强度依赖于质因数分解的困难程度，这是质数分布这一深层问题的结果。