中国剩余定理攻击RSA算法

2020年4月17日11:00:37 发表评论

什么是中国剩余定理?

它来源一个“物不知数”问题。即“有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?”。为了求解,我们列如下方程

x=2%3
x=3%5
x=2%7

按照博主普通人的思维,会先按最大的那个进行套,例如x=2%7有解9,16,23,30...然后再套前面两个式子,发现最小的x=23,通解是x=23+k*3*5*7。数小的时候当然简单,但数大起来就完全不能这么做了。

我们再看看古人怎么解的:

”三人同行七十希,五树梅花廿一支,七子团圆正半月,除百零五便得知“

即 70*2+21*3+15*2 = 233=105*2+23

如何求解普遍性”物不知数“问题?

显然这种方法似乎要简单一点。可惜的是只能应对3,5,7这种问题,下面我们来看普遍性解法:

假设有n个这样的方程
x=a1%m1
x=a2%m2
x=a3%m3
...
x=an%mn
解:
设M=m1*m2*m3*...*mn
Mi-1=M/mi
ti=Mi-1 %mi
那么x=a1t1M1+a2t2M2+...+antnMn+kM   k∈0,1,2,3,4,...

如何攻击RSA加密算法?

已知有三个用户,他们使用不同的公钥对消息M进行加密,生成密文C0,C1,C2

我们列出一元同余线性方程组如下

Me0=C0%N0
Me1=C1%N1
Me2=C2%N2

再根据中国剩余定理,我们可以求得一个Mx满足条件,再通过因式分解,我们就能求得明文消息M。当然,说是这样解的并不严谨,因为它并未经过任何事实验证,然而博主没有构造实例的条件,因此这种方法的正确性值得讨论——至少有实际例子证明。

 

flyingsheep

发表评论