这篇讨论一下中国剩余定理(Chinese Remainder Theorem),高斯算法(Gauss's algorithm)解决同步线性同余(simultaneous linear congruences)的问题、简单的方法去解决小模数(small moduli)同余、RSA低加密指数广播攻击的原理(theorem to break the RSA algorithm when someone sends the same encrypted message to three recipients using the same exponent of e=3，又叫Johan Hastad广播攻击)
中国剩余定理 The Chinese Theorem
定理：有整数
，
，那么线性同余系统
定理说有唯一解，并不是说如何去求解。这个通常使用高斯算法(Gauss's algorithm)。中国剩余定理更多的时候是用在对RSA算法进行提速。
中国剩余定理在《孙子算经》中的问题是：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？在现代数论种我们把它写成解同余问题。
高斯算法 Gauss's algorithm
算法：有
那么
《孙子算经》的例子
《孙子算经》上面原始的中国剩余定理的题目有：
低加密指数广播攻击RSA Johan Hastad attack
Alice发送您相同的RSA加密消息m给三个接收方，使用了不同的模数，这些模数互质，但是他们使用了相同的指数
。Eve恢复出了密文值
并且知道三个接收方的公钥
。Eve是否可以在不分解模数的情况下，恢复出消息？
可以。Eve使用高斯算法可以找到解x，在范围内，
我们知道，因此可以得到，
,
可以通过简单的对整数
求立方根恢复出来。
例子
有三个接收方的公钥，我们知道
并且
（实际使用中，会使用更大的N，不可以分解）
Alice使用RSA算法加密消息给三个接收方，如下：
这三个密文值被中间人Eve拦截，Eve知道公钥
。她可以使用高斯算法如下：
所以明文消息是1000的立方根，
。所以Eve不需要对模数进行分解就可以恢复出明文消息。
如何防止以上的攻击
- 使用大指数，比如65537(0x10001)。这样使用上面的攻击方法将会变得很困难。
- 添加一些随机比特到消息中，至少64比特。确保每次消息加密都添加了不同的随机数。这种加盐的方法也可以防止许多其他的攻击。显然，接收方也需要知道如何在解密后去除填充的随机数。
