2026.5.20 本地obsidian1.算数基本定理引入古代如何知道时间——观天象现代时钟依据某种重复性规律将时间分成相等的片段而在古代这些重复规律可以通过观察天空得到。质数与合数如一个月有29天而29无法分成等份只能分成基本单元则29被认为是质数不可分若一个数能被分为大于1的等份就称之为合数。好奇质数的个数可以有多大——无数个无穷大。技巧质数螺旋发现持续到永远的质数规律仍是未解之谜。质数是积木欧几里得意识到所有数都可以分到质数和合数这两个类别中。他首先意识到任何数能不断进行除法直到得到一组最小的不能进行除法的数字。根据定义这些最小数字就是质数。所有数字都构建于这些质数之上任何数字都能表示为一组质数用质数之和表示。![[Pasted image 20260520111322.png]]算数基本定理的发现质因数分解![[Pasted image 20260520111430.png]]得到质因数![[Pasted image 20260520111850.png]]将这些质因数相乘特定次数可以得到原数![[Pasted image 20260520112043.png]]这里只需要把他们都相乘一次就可以得到30也就是xyz130的质因数分解2×3×5质因数分解的唯一性这个分解过程可以被认为是特殊的钥匙和组合没有其他质数相乘方式能得到同样的原数也就是说任意数字有且只有一种质因数分解。可以将每个数字描述为一个不同的“锁”它的钥匙就是该数的质因数分解任意两个锁钥匙都不同任意两个数质因数分解不同2.公开密匙密码学密钥引入现在很多网络应用需要加密——保证安全加密需要双方共享一个秘密的随机数——密钥互联网拥有大量用户两个互不见面的人如何就共享密钥达成一致且不让第三方监听者知道单向函数颜色的启示混合两种颜色得到第三种颜色很容易但已知混合色后想知道原来两种颜色很难——这是锁的原理朝一个方向容易朝反方向难。这被称为单向函数。构建单向函数颜色为例先公开对某种颜色达成一致随机选取私有颜色混合到公开颜色中从而掩饰掉私有颜色互相发送混合色公开颜色P 各自混合AP-C BP-D关键再各自将私有颜色混合到另一个人的混合色得到共享秘密颜色。AD-K DBP, KABP BC-K CAP, KBAP 确实得到同一种颜色混合颜色的顺序不同回看整个过程K P A B第三方必须有一种私有颜色才能确定这个共有颜色。构建单向函数数值对数字使用此技巧时需要一个数值过程该过程朝一方向容易反方向难。3.离散对数问题模算术时针算术例求46%1246除以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可以买一把锁钥匙留在手上把打开的锁发给BB将自己的信息上锁发回给A。这里无需交换密匙锁可以公开可以让世界上任何人用它来发消息而A只需要一把钥匙。关键将密匙分为两部分加密密匙解密密匙。解密密匙用于解密这一逆操作加密通过加密密匙进行加密和解密密匙颜色为例B如何发给A一个颜色并且防监听每种颜色都有互补色和互补色叠加会得到白光去掉了第一种颜色的作用。假设混合颜色是一个单向函数![[Pasted image 20260520125848.png]]反向难A生成自己的私有密匙任意颜色a假设A有一个秘密的机器能找到这个颜色a的互补色没有其他人知道她将a的互补色发给B作为公开密匙假设B想发一种秘密的颜色b给A他将颜色b与公开颜色混合将混合色发给AA将私有色叠加到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 得到me表示加密d表示解密。因此A需要有一种方法构建e和d导致其他人很难求出d的值。这需要第二个单向函数用于生成d。7.RSA加密第三步回顾欧几里得证明了每个数只有一种质因数分解这可以考虑为一个密钥。质因数分解从时间复杂度角度看很难需要采用试错法直到找到某数能均分n此时求解问题所需的时间会随着数字的增大而飞速增长。构建陷门——质因数分解step1.A随机生成一个超过150位的质数记作P1随机生成位数相当于第二个质数P2将两个质数相乘得到合数NN超过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 60step3.将φ函数和模幂运算联系起来——欧拉定理φ函数和模幂运算的关系如下m^φ(n) 1 mod n这意味着你可以选择任意两个数字让它们没有公因数。假设mn满足 m^φ(n) mod n 1下面只需使用两条简单规则处理这个等式1^k 1同理m^(k * φ(n) ) mod n 11 * m mm^(k * φ(n) 1) mod n mm^(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)。第三方知道enc想知道d只能通过计算φ(n)这要求他们知道n的质因数分解。RSA是使用最广泛的公开密匙算法。其强度依赖于质因数分解的困难程度这是质数分布这一深层问题的结果。10.后面应该学什么知识体系结构——树从树根到树枝。不断提问引出新内容再互动形成正向循环。积极思考寻求解决方案不能把书读死了。