同余（七）——密码学中的应用

欢迎大家来到IT世界,在知识的湖畔探索吧!

当你想向某个同学传纸条，又不想让传递的人看到内容，怎么办？

欢迎大家来到IT世界,在知识的湖畔探索吧!

（图片源自百度）

那就在信息中设定密码。从古到今，商业、安全部门等领域发送一些消息，需要对内容保密，不想让其他人知道。因此人们就发明了加密方式。

双方制定一种规则，把信息转化成对方才能识别的信息。这就是密码通信。

密码通信

一般我们通过把文字或字母转化为数字信息，这些数字称为“码子”，分为明码和密码。例如，出国时填写表格，个人姓名对应的标准中文电码就是明码。明码没有保密性。

（图片源自百度）

密码就是通过加密程序把明码变为密码，对方收到密码后还需通过解密程序，把密码还原成明码，帮助执行加密或解密的工具就是密钥和解钥。

RSA体制

早期加密时经常运用的数学运算有移位、代换。例如，移位式密码，代换式密码、乘积密码。

（图片源自百度）

随着科技的发展，这种加密方式很容易激活成功教程，并且在商业等方面，对每个客户都需要约定好一种密钥和解钥，导致非常麻烦。

1977年，麻省理工学院的Rivest、Shamir、Adleman,提出了一种公开密钥体制，被称为RSA体制。

设p、q是两个较大的素数，N=pq，e和d满足同余式

e^d≡1（mod φ(N) ）

其中 φ(n)是欧拉函数(小于或等于n的正整数中与n互质的数的数目)

密钥（锁）：e、N;

解钥（钥匙）：d;

加密解密过程如下：设明码为a（0≤a≤N-1）,加密程序是将a通过同余式

a^e≡b（mod N）0≤b≤N-1

转化为b. 再将b发送给对方，对方收到后在通过解密同余式

b^d≡a^(ed)≡a^(1+kφ(N))≡a (mod N）

将b还原成明码a。（上面的同余式成立是由欧拉定理和费马小定理保证的。费马小定理已经介绍过了，欧拉定理以后再单独介绍。）

（图片源自百度）

密钥e、N是可以公开的，只要d（钥匙）保存好后，只有有钥匙的人才可以解读出信息。没有d（钥匙）的人想解出信息几乎是不可能的，这是因为当N足够大时，求出φ(N)就有困难。

面对的客户数量较大时，可以有很多对ei, di满足

ei di≡1（mod φ(N) ） i=1、2、…

客户数量大的问题也就解决了。

假设我们想传递“5、2、0”

考虑较小的素数p=5，q=7，此时

N=35，φ(35)=24. 取e=5 d=5,

5^5≡10（mod 35）

2^5≡32（mod 35）

0^3≡0（mod 35）

我们把“5、2、0”转为了“10、32、0”，对方收到“10、32、0”时，利用d，解密同余式

10^5≡5（mod 35）

32^5≡2（mod 35）

再将“10、32、0”还原为“5、2、0”。

除了密码学上的应用，同余知识还可以用在纠正和纠错上。例如，录音设备里能够精准的复制声音，是因为有纠错码。