Shellbye
模运算与公开密钥加密算法(非对称加密)Modular arithmetic and public-key cryptography(asymmetric cryptography)
同余的定义
在模运算中，同余是一个很重要的定义，比如最简单的求余，我们有
5 ÷ 3 = 1 …… 2
表示5除以3之后余2，同样的，11除以3之后也余2
11 ÷ 3 = 3 …… 2
即5和11的余数是相同的，这在数学上叫做同余，可以表示为
5 ≡ 11 (mod 3)
这个表示5和11除以3之后，他们的余数是相同的（都是2）。
同余的性质
- 如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)
- 如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)
- 如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m)
加密
假设现在有三个人小a、小b和小c住在一个小区里，现在考试结束了，小a和小b想互相告诉对方自己的成绩，但是他们只能通过隔着窗户互相喊话的形式来交换，但是他们又不想让小c知道，于是他们俩在学校时就偷偷约定了一个数字 32（别问为什么没在学校告知对方成绩），作为他们之间通信的密钥，然后回家之后，他们把自己的真实成绩乘以32，然后大声喊出来，比如小a喊3200，小b喊2880，然后他们在听到对方的成绩之后，再除以32，就知道了对方的成绩。于此同时，就算有人听到了他们喊的3200和2880，也不知道他们在说什么，这就实现了对称加密，这里的对称，指的是小a和小b的手里的密钥是一样的，都是32。但是这样有一个问题，就是两人必须得在学校见面，并提前约定好密钥，万一他们在偷偷约定的时候被小c听到了，那么他们后面所有的加密过程就都没有意义了。有没有其他方法呢？当然有，那就是非对称加密，又叫公开密钥加密
非对称加密 公开密钥加密
非对称加密的后半部分就是对称加密，它的关键点是如何通过公开的方式，而不是偷偷的方式，来确定他们的公共密钥，也就是上面的32。
- 首先，小a和小b公开喊话，约定了一个很大的素数P，和一个很大的基数N，这个小c也会知道，但是没关系啦
- 接着，小a选择一个与N互素的数字A定义为自己的密钥，小b也同样选择了与N互素的B最为自己的密钥，他们彼此都不知道自己的密钥。
- 然后，小a计算
并把J公开的发给小b。然后小b也做同样的事儿，计算
并把K公开的发给小a。 - 最后，小a拿到K之后计算
小b拿到J之后计算
然后得到是同样的数字！那么为什么他们得到的是同样的数字呢？下面我们结合相关性质，进行分析。
分析
从小a的角度分析，
从小b的角度分析，
所以他们得到的结果当然就是一样的喽。
那么问题来了，既然小c知道N, P, J, K，也知道其中的计算规则，那么为什么他不能从
中反解出A呢？
实际上，这是一个已知的非常难的问题（discrete logarithm problem 离散对数难题），而如果要提前计算所有N并存储起来的话，需要的存储空间大到完全无法存储，所以就认为它是不可破解的了。
那么既然计算这么难，小a和小b互相之间是怎么计算的呢？因为其中包含了取模运算，且取模运算有上面我们提到的性质，所以实际用的计算量是非常小的。下面我们用
来做一个简单的demo
其中的替换过程，使用的就是互余的性质。最后我们就可以轻松算出：
参考
- http://pi.math.cornell.edu/~mec/2003-2004/cryptography/diffiehellman/diffiehellman.html
- http://www.matrix67.com/blog/archives/236
- http://www.isnowfy.com/application-tonumber-theory-and-introduction-to-rsa/
- https://en.wikipedia.org/wiki/Modular_arithmetic
