给定以下 RSA 密钥，如何确定p和q的值是多少？
Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
问问题
98394 次
12 回答
145
Your teacher gave you:
Public Key: (10142789312725007, 5)
which means
n = 10142789312725007
e = 5
where n is the modulus and e is the public exponent.
In addition, you're given
Private Key: (10142789312725007, 8114231289041741)
meaning that
d = 8114231289041741
where d is the decryption exponent that should remain secret.
You can "break" RSA by knowing how to factor "n" into its "p" and "q" prime factors:
n = p * q
The easiest way is probably to check all odd numbers starting just below the square root of n:
Floor[Sqrt[10142789312725007]] = 100711415
You would get the first factor in 4 tries:
10142789312725007 mod 100711415 = 100711367
10142789312725007 mod 100711413 = 100711373
10142789312725007 mod 100711411 = 100711387
10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n
So we have
p = 100711409
Now,
q = n / p
= 10142789312725007 / 100711409
= 100711423
Why is this important? It's because d is a special number such that
d = e^-1 mod phi(n)
= e^-1 mod (p-1)*(q-1)
We can verify this
d * e = 40571156445208705 = 1 mod 10142789111302176
This is important because if you have a plaintext message m then the ciphertext is
c = m^e mod n
and you decrypt it by
m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)
For example, I can "encrypt" the message 123456789 using your teacher's public key:
m = 123456789
This will give me the following ciphertext:
c = m^e mod n
= 123456789^5 mod 10142789312725007
= 7487844069764171
(Note that "e" should be much larger in practice because for small values of "m" you don't even exceed n)
Anyways, now we have "c" and can reverse it with "d"
m = c^d mod n
= 7487844069764171^8114231289041741 mod 10142789312725007
= 123456789
Obviously, you can't compute "7487844069764171^8114231289041741" directly because it has 128,808,202,574,088,302 digits, so you must use the modular exponentiation trick.
In the "Real World", n is obviously much larger. If you'd like to see a real example of how HTTPS uses RSA under the covers with a 617-digit n and an e of 65537, see my blog post "The First Few Milliseconds of an HTTPS Connection."
于 2010-11-02T15:22:26.180 回答
16
这是一种相对简单的查看方法（并且可以手动完成）。如果你要完全分解这个数字，那么你需要考虑的最高因素是 sqrt(N)：
sqrt(10142789312725007) = 100711415.9999997567
下面的第一个素数是 100711409，仅比 sqrt(N) 低 6 个。
10142789312725007 / 100711409 = 100711423
因此这是 N 的两个因素。你的教授让它变得很容易 - 诀窍是认识到没有人会选择一个小的p 或 q 所以从底部开始检查（就像有人发布的 python 脚本一样）是一个坏主意. 如果它要手动实用，那么大的 p 和 q 必须位于 sqrt(N) 附近。
于 2010-11-02T15:14:03.633 回答
14
有多种快速算法可以解决n给定n、e和的因式分解问题d。您可以在《应用密码学手册》第 8 章第 8.2.2 节中找到对此类算法的一个很好的描述。您可以在此处在线找到这些章节并免费下载。该算法本质上是对Henno Brandsma对这个问题的回答的仔细阐述。
2019 年 9 月 25 日更新：
在下面的评论中，用户Imperishable Night提出了一种替代方法，至少在概念上应该更容易理解。
他指出，通常e很小。事实上e，几乎总是 65537。在这种情况下，e您可以在未知素数中建立一个二次方程，从而使用例如二次公式p轻松求解它。为了继续，让我们设置 x=p 并求解，只是为了遵守约定。我们知道，或者等价
的。现在设置，因此，将两边乘以并重新排列项，我们有
k*x 2 + (d*e - k*n - k - 1)*x + k*n = 0。
现在我们有一个形式为ax 2 + bx + c = 0 我们可以使用二次公式求解 x。所以我们可以尝试xed = 1 mod phi(n)ed - 1 = k * (p-1)*(q-1)x=pn/x=qxk在一个很小的范围内e，二次方程应该只有一个整数解，即正确 k 的解。
笔记：
- 一切都必须是整数，因此判别式必须是完全平方，否则我们可以丢弃 k 并尝试下一个。此外，分子必须能被 整除
2*k。 - 有时使用 Carmichael lambda 函数代替 Euler phi 函数。这使事情稍微复杂了一点，因为我们现在还必须猜测
g = gcd(p-1, q-1).g总是偶数，通常是 2，否则几乎总是 2 的小倍数。
2019 年 9 月 26 日更新：
小的时候找k其实很容易e。通过取等式
ed - 1 = k * (p-1)*(q-1)并将两边除以n它很容易看出floor((ed-1)/n) + 1 == k。现在使用MJ Wiener 的“短 RSA 秘密指数的密码分析”的方程 31 和 32，可以直接恢复p和q。
于 2010-11-03T01:21:52.803 回答
11
Wolframalpha告诉我因子是 100711409 和 100711423
我只是写了一个简单的 Python 脚本来暴力破解它。正如 amdfan 所指出的，从顶部开始是一种更好的方法：
p = 10142789312725007
for i in xrange(int(p**0.5+2), 3, -2):
if p%i == 0:
print i
print p/i
break
这可以大大改进，但它仍然可以正常工作。您可以通过仅测试 primfactors 来改进它，但是对于像您这样的小值，这应该足够了。
于 2010-11-02T15:01:22.787 回答
4
RSA 的定义告诉你模数n = pq. 你知道n，所以你只需要找到两个数字p，q然后乘以产生n。你知道p并且q是素数，所以这是素数分解问题。
对于相对较小的数字，您可以通过蛮力解决这个问题，但 RSA 的整体安全性取决于这个问题通常难以解决的事实。
于 2010-11-02T15:13:38.220 回答
4
这是来自应用密码学手册第 8 章第 8.2.2 节的快速分解方法的 Java 实现（感谢 GregS 找到它）：
/**
* Computes the factors of n given d and e.
* Given are the public RSA key (n,d)
* and the corresponding private RSA key (n,e).
*/
public class ComputeRsaFactors
{
/**
* Executes the program.
*
* @param args The command line arguments.
*/
public static void main(String[] args)
{
final BigInteger n = BigInteger.valueOf(10142789312725007L);
final BigInteger d = BigInteger.valueOf(5);
final BigInteger e = BigInteger.valueOf(8114231289041741L);
final long t0 = System.currentTimeMillis();
final BigInteger kTheta = d.multiply(e).subtract(BigInteger.ONE);
final int exponentOfTwo = kTheta.getLowestSetBit();
final Random random = new Random();
BigInteger factor = BigInteger.ONE;
do
{
final BigInteger a = nextA(n, random);
for (int i = 1; i <= exponentOfTwo; i++)
{
final BigInteger exponent = kTheta.shiftRight(i);
final BigInteger power = a.modPow(exponent, n);
final BigInteger gcd = n.gcd(power.subtract(BigInteger.ONE));
if (!factor.equals(BigInteger.ONE))
{
break;
}
}
}
while (factor.equals(BigInteger.ONE));
final long t1 = System.currentTimeMillis();
System.out.printf("%s %s (%dms)\n", factor, n.divide(factor), t1 - t0);
}
private static BigInteger nextA(final BigInteger n, final Random random)
{
BigInteger r;
do
{
r = new BigInteger(n.bitLength(), random);
}
while (r.signum() == 0 || r.compareTo(n) >= 0);
return r;
}
}
一个典型的输出是
100711423 100711409 (3ms)
于 2010-11-03T20:31:11.367 回答
3
执行此操作的算法是（这适用于任何示例，不仅是可以被任何计算机轻松分解的小示例）：
ed - 1是 的倍数phi(n) = (p-1)(q-1)，因此至少是 4 的倍数。
ed - 1可以计算为 40571156445208704 等于2^7 * 316962159728193，我们称s=7和t = 316962159728193。（一般来说：任何偶数都是奇数的 2 次方）。现在[2,n-1)随机选择一个，并计算（通过连续平方模n）序列
a^t (mod n), a^(2t) (mod n), a^(4t) (mod n)..直到最多a^((2^7)*t) (mod n)，其中最后一个保证为 1，通过 和 的e构造d。
我们现在寻找该序列中的第一个 1。它之前的那个要么是+1or -1
（1 的平凡根），我们用不同的 a 或不等于ormod n的某个数字重做。在后一种情况下，是, 等或的一个重要除数，我们就完成了。可以证明一个随机的 a 会以大约 0.5 的概率起作用，所以我们需要尝试几次，但通常不会很多。x+1-1 mod ngcd(x-1, n)npq
于 2010-12-17T20:37:07.277 回答
3
这两篇论文可能有用
当我对连分数进行一些基础研究时遇到了它们。
于 2010-11-05T23:07:07.300 回答
1
对不起，死灵术，但一个朋友问我这个问题，在把他指到这里之后，我意识到我并不喜欢任何答案。在分解模数并得到素数（p 和 q）后，您需要找到总分，即(p-1)*(q-1).
现在，要找到私有指数，您可以找到公共指数的倒数 mod the totient。
public_exponent * private_exponent = 1 mod totient
现在你有了你的私钥，就这么简单。对于大整数，除了因式分解之外的所有这些几乎都可以立即完成。
我写了一些代码：
// tinyrsa.c
//
// apt-get install libgmp-dev
// yum install gmp-devel
//
// gcc tinyrsa.c -o tinyrsa -lm -lgmp
#include<stdio.h>
#include<gmp.h>
int main()
{
// declare some multi-precision integers
mpz_t pub_exp, priv_exp, modulus, totient, fac_p, fac_q, next_prime;
mpz_init_set_str(pub_exp,"5",10);
mpz_init_set_str(modulus,"10142789312725007",10);
mpz_init(priv_exp);
mpz_init(totient);
mpz_init(fac_p);
mpz_init(fac_q);
// now we factor the modulus (the hard part)
mpz_init(next_prime);
mpz_sqrt(next_prime,modulus);
unsigned long removed=0;
while(!removed)
{
mpz_nextprime(next_prime,next_prime);
removed=mpz_remove(fac_p,modulus,next_prime);
}
mpz_remove(fac_q,modulus,fac_p);
// we now have p and q
// the totient is (p-1)*(q-1)
mpz_t psub, qsub;
mpz_init(psub);
mpz_init(qsub);
mpz_sub_ui(psub,fac_p,1);
mpz_sub_ui(qsub,fac_q,1);
mpz_mul(totient,psub,qsub);
// inverse of the public key, mod the totient..
mpz_invert(priv_exp,pub_exp,totient);
gmp_printf("private exponent:\n%Zd\n",priv_exp);
}
我使用的分解算法很愚蠢，但简洁，所以那里有一点盐。在这个特定示例中，代码几乎立即运行，但这主要是因为有问题的讲师提供了一个连续使用两个素数的示例，这对于 RSA 来说并不现实。
如果你想去掉我愚蠢的迭代搜索，你可以使用一些真正的分解算法，并且在合理的时间内分解密钥可能高达 256 位左右。
于 2012-06-19T20:22:42.340 回答
1
我建议您阅读有关二次筛的内容。如果你自己实现一个，这肯定是值得的。如果你理解了这些原则，你已经有所收获。
于 2010-11-02T15:13:11.847 回答
0
You need to factorize the modulus, that's the first parameter of the public key, 10142789312725007. Brute force will do (check every odd number from 3 to sqrt(n) if it's a factor), although more sophisticated/fast algorithms exist.
Since the number is too big to fit into a conventional integer (even 64-bit), you might want a numeric library that supports arbitrary-lenth integers. For C, there's GMP and MPIR (more Windows-friendly). For PHP, there's Bignum. Python comes with a built-in one - the built-in integer datatype is already arbitrary-length.
于 2010-11-02T15:20:01.077 回答
0
关于大半素数的因式分解有很多不好的猜测，这些半素数进入蛮力或筛分都不需要分解半素数。64 位在我的电脑上需要 1 - 2 秒，而 256 位通常不到 2 天
于 2017-05-31T12:13:42.983 回答