某人向3个人发送了一个消息，$ m $（没有任何填充），并带有公共密钥$ n_b $，$ n_c $和$ n_d $，公共指数为3。说：
通过中国剩余定理，窃听者计算出一个数字$ c $，使得$ c = m ^ 3 \ mod n_b \ cdot n_c \ cdot n_d $。 />
也许我不完全了解中国余数定理，但是我不明白如何选择一个全等系统来解决，最终将等于$ c = m ^ 3 \ mod n_b \ cdot n_c \ cdot n_d $当您不知道$ m $是什么时。能否请您帮助我了解使用什么作为达到该点的一致性系统，因为我想我理解其余部分。
#1 楼
您不需要知道$ m $。您知道$ m ^ 3 $以每个模为模，这就足够了。您想找到：$$ c \ equiv m ^ 3 \ pmod {n_b} $$
$$ c \ equiv m ^ 3 \ pmod {n_c} $ $
$$ c \ equiv m ^ 3 \ pmod {n_d} $$
因为$ n_b $，$ n_c $，$ n_d $是成对的互质数（假设它们没有共同因素）必须存在一个解决方案。
维基百科页面对找到$ c $的算法做了很好的解释。实际表达式为：
$$ c = c_b（n_c \ cdot n_d）[（n_c \ cdot n_d）^ {-1}] _ {n_b} + c_c（n_b \ cdot n_d）[ （n_b \ cdot n_d）^ {-1}] _ {n_c} + c_d（n_b \ cdot n_c）[（n_b \ cdot n_c）^ {-1}] _ {n_d} $$
其中$ [a ^ {-1}] _ b $是$ a $模$ b $的乘法逆。注意$ \ gcd {（a，b）} = 1 $总是满足的。另外，我使用了符号$ c_b = m ^ 3〜\ text {mod}〜n_b $，$ c_c = m ^ 3〜\ text {mod}〜n_c $，$ c_d = m ^ 3〜\ text {mod} 〜n_d $。
让我们尝试一些数字。假设某人将消息$ m = 102 $发送给三个不同的人，使用RSA教科书，其模数为$ n_b = 377 $，$ n_c = 391 $和$ n_d = 589 $。因此：
$$ c_b = 102 ^ 3〜\ text {mod}〜377 = 330 $$
$$ c_c = 102 ^ 3〜\ text {mod}〜391 = 34 $$
$$ c_d = 102 ^ 3〜\ text {mod}〜589 = 419 $$
所以攻击者想解决以下一致性问题：
$$ c \ equiv 330 \ pmod {377} $$
$$ c \ equiv 34 \ pmod {391} $$
$$ c \ equiv 419 \ pmod {589} $$
使用上面的公式，我们得到（为清楚起见，分别计算每个项）：
$$ t_b = c_b（n_c \ cdot n_d ）[（n_c \ cdot n_d）^ {-1}] _ {n_b} = 330（391 \ times 589）[（391 \ times 589）^ {-1}] _ {377} = 24471571740 $$
$$ t_c = c_c（n_b \ cdot n_d）[（n_b \ cdot n_d）^ {-1}] _ {n_c} = 34（377 \ times 589）[（377 \ times 589）^ { -1}] _ {391} = 505836734 $$
$$ t_d = c_d（n_b \ cdot n_c）[（n_b \ cdot n_c）^ {-1}] _ {n_d} = 419 （377 \ times 391）[（377 \ times 391）^ {-1}] _ {589} = 35452267942 $$
$$ \因此c = t_b + t_c + t_d〜\ text {mod}〜（n_b \ cdot n_c \ cdot n_d）= 1061208 $$
，我们得到$ m = \ sqrt [3] {c} = \ sqrt [3] {1061208} = 102 = m $。 3 $是最现实的设置（出于明显的原因，它也是最容易演示的方法。）
当然，该想法是使用这些与CRT的关系来制造形式为$ m ^的关系。 3 \ equiv x \ pmod {n'} $其中$ n'$的顺序为$ n ^ 3 $（更重要的是，其中$ 1
评论
$ \ begingroup $
为了使用此攻击，我似乎需要$ e = 3 $的等价物。 e如何以及为什么影响同余数？如果我是正确的话，CRT并没有说明寻找解决方案所需的全等数量-那么为什么它不仅仅适用于两个全等？
$ \ endgroup $
– CGFoX
2014年7月24日在7:24
$ \ begingroup $
@CGFoX如果只有两个全等，则$ n'$大约为$ n ^ 2 $（两个模的乘积），因此$ m ^ 3 $会大于$ n ^ 2 $（按$ n $的阶数），如果不知道模数的因式分解，就无法轻易地求取立方根，因此它不起作用。
$ \ endgroup $
–托马斯
2014年7月24日在7:40
评论
从这种攻击中得到的教训是，RSA加密必须（如PKCS＃1 RSAES中所述）对要加密的消息进行随机加密，对于每个目的地而言都是不同的。第二个教训是，RSA的不良使用在指数较低的情况下会变得更糟；不应认为低指数的RSA总是很弱。很高兴您找到了正确的网站:)