解同余方程，如N= p*q c1 = (2*p + 3*q)**e1 mod N c2 = (5*p + 7*q)**e2 mod N
这里有一个CTF密码挑战“喜欢”(它的编写在https://ctftime.org/writeup/15438上公开)：
在我将这些转化之后：
在乘积5^{e_1e_2},2^{e_1e_2}从两个方程中取消p之后，我可以解决这个问题，直到得到方程liks：
这意味着把左边和右边的区别分开。
但我不知道为什么p或q可以从：
有人能解释一下这些知识或原因吗？
回答 1
Cryptography用户
发布于 2023-05-04 14:06:14
这个问题已经表明
如果一个同余包含两个整数的乘积，那么它保持每个整数的模。因此，同余保持模q。
同余的右边是q的倍数。因此
是q的倍数。
N也是q的倍数。因此，q是{c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}和N的除数。
N的唯一除数是1、p、q、N和q，它们只除以后两个除法。因此，\gcd\left({c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2},N\right)要么是q，要么是N。只有当p拆分{c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}时，后者才能成立，这没有什么特别的理由，因此不太可能。
因此，\gcd\left({c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2},N\right)很可能是q。我们可以计算{c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}，或者更有效地计算{c_1}^{e_2}\times5^{e_1e_2}-{c_2}^{e_1}\times2^{e_1e_2}\bmod N，然后通过欧氏算法将它与N一起取为GCD，并分解N。
https://crypto.stackexchange.com/questions/106396
复制相似问题
腾讯云开发者
