DAY 13- 《公钥密码》-RSA(1)

第一个要来看的公钥加密演算法是 RSA。
记得我们在 DAY6 的时候介绍到 RC4 时提到一个人吗，
设计RC4 的 Ron Rivest 就是RSA 的R，
他和其他两人 Adi Shamir 和 Leonard Adleman 共同提出了 RSA 演算法。

今天比较硬一点（可能?）
因为要理解 RSA 的算法需要一点先备（仙贝）的小知识，
我们知道仙贝是用米做的，所以

质数 Prime numbers

我记得快一年前的一个晚上我在宿舍和室友争论一件事，
我们在争论为什麽数学家要浪费时间找一个非常大的质数，
就算找到了可以干嘛？

你知道世界上目前发现最大的质数是多少吗。

在2017年日本人甚至出版了一本书就叫做最大的质数，
他们花了719页印完了上一个最大的质数。

我不知道其他的质数对数学家有什麽意义（他们甚至有快乐质数这种东西）
不过质数对 RSA 来说非常重要。

质因数分解

RSA的安全性建立在数字的质因数分解难度。
随便讲个数字，98好了，拿给一个国小小朋友要他做质因数分解应该都做得出来，
小朋友就会开始从2、3、5、7...
找遍所以质数（prime number）看能不能整除98，所以很幸运的他第一个2就找到了。

所以你发现质因数分解的困难度就在於你找到第几个质数可以整除这个数。
那我们来试试这个：323。
所以一样你从2开始找，找到17的时後 bingo!
你发现他可以整除，323=17×19，problem solved。

所以随着质数越来越大，质因数分解的难度就会提高，
当我们将709×941时可以很容易地得到 667,169，而别人很难将667,169分解。
这就是 RSA 安全性的来源，而 RSA 使用的是非常大的质数。

接下来会频繁用到 mod 的概念，如果忘记的话，可以（一定要）回去 DAY2 复习。
另外，运算中会使用到Euler's Phi function，

Euler's Phi function

Euler 念作「欧伊乐」，中文翻作欧拉或尤拉，18世纪瑞士数学家。
就是发现世界最美公式的那个( 崇拜 )，
他还有一堆奇奇怪怪公式。

欧拉函数是用来算「小於等於 n 的正整数中与 n 互质的数的数目」，写作，
举例来说：，因为小於5的数中1、2、3、4总共4个数字和5互质。

而在这里我们会将两个质数相乘在一起，
所以我们得知道这个公式：

不过不用担心，毕竟我们没有要探究原理，只是讲一下怎麽算而已。

乘法反元素

n 的乘法反元素就是跟自己相乘之後会等於1，我们写作。

最简单的，在实数里面 2 的乘法反元素就是 ，因为

所以你要说是除法也可以。

高中有学过矩阵的人就知道，矩阵的乘法反元素，也就是反矩阵，
并不像整数的乘法反元素这麽好求，反矩阵跟原本的矩阵也涨得一点都不像。
在这里我们会需要计算在mod n 之下的乘法反元素，

什麽意思呢？

举个例子：我们考虑一个所有运算都 mod 5 的集合里面，
这个集合里有{0, 1, 2, 3, 4}，5就是0，6就是1，一直下去，每个数字都除以5取余数。

2和3互为乘法反元素，因为2×3 ≡ 6 (mod 5) ≡ 1 (mod 5)，（"≡"视同余的符号，我们可以看成 "=" 就好）
4的乘法反元素就是自己，因为4×4 ≡ 16 (mod 5) ≡ 1 (mod 5)

在更大的模数之下，也就是mod n 的 n 很大时，乘法反元素并不容易看出来，
所以如果要用手算的话，会需要使用到「扩展欧几里得算法（Extended euclidean algorithm）」。

不过我们都是依靠电脑的废物吧（至少不是数学家?），
所以这种事就交给电脑来做就好了，
我们知道他在干嘛就好了。

如果使用python 的话有个简单的指令可以马上得到乘法反元素。
奉上。

# inverse of a modulo n
pow(a,-1,n)

好了各位，我们已经有能力看懂 RSA 怎麽运作了，
我们，
明天再看...
(掰)

图片来源：
https://www.ettoday.net/dalemon/post/33540
https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/
https://www.reddit.com/r/mathmemes/comments/c1prja/eulers_formulareimann_zetaeulers_identityanalytic/
https://www.reddit.com/r/memes/comments/atda9f/maths_can_be_whatever_i_want_it_to_be/