破解短 RSA 密钥
给定以下 RSA 密钥,如何确定 p 和 q 的值是什么?
Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
Given the following RSA keys, how does one go about determining what the values of p and q are?
Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(12)
你的老师给了你:
这意味着
其中 n 是模数,e 是公共指数。
此外,您还获得
表示
其中 d 是应保密的解密指数。
您可以通过知道如何将“n”分解为其“p”和“q”质因数来“破坏”RSA:
最简单的方法可能是检查从n的平方根下方开始的所有奇数:
您将得到第一个考虑 4 次尝试:
现在我们知道了
,
为什么这很重要?这是因为 d 是一个特殊的数字,这样
我们就可以验证这一点。
这很重要,因为如果您有明文消息 m ,那么密文就是
解密它
,您可以通过以下方式 :我可以使用您老师的公钥“加密”消息 123456789:
这将为我提供以下密文:(
请注意,“e”在实践中应该大得多,因为对于较小的“m”值,您甚至不会超过 n)
不管怎样,现在我们有了“c”,可以用“d”反转它
显然,你不能直接计算“7487844069764171^8114231289041741”,因为它有128,808,202,574,088,302位,所以你必须使用 模幂技巧。
在“现实世界”中,n 显然要大得多。如果您想了解 HTTPS 如何在幕后使用 RSA(包含 617 位 n 和 e 65537)的真实示例,请参阅我的博客文章“< a href="http://www.moserware.com/2009/06/first-few-milliseconds-of-https.html" rel="noreferrer">HTTPS 连接的前几毫秒。"
Your teacher gave you:
which means
where n is the modulus and e is the public exponent.
In addition, you're given
meaning that
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:
The easiest way is probably to check all odd numbers starting just below the square root of n:
You would get the first factor in 4 tries:
So we have
Now,
Why is this important? It's because d is a special number such that
We can verify this
This is important because if you have a plaintext message m then the ciphertext is
and you decrypt it by
For example, I can "encrypt" the message 123456789 using your teacher's public key:
This will give me the following ciphertext:
(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"
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."
这是一种相对简单的查看方法(并且可以手动完成)。如果您要将数字完全分解,那么您需要考虑的最高因子是 sqrt(N):
下面的第一个质数是 100711409,仅比 sqrt(N) 低 6。
因此,这是 N 的两个因素。您的教授使它变得非常简单 - 诀窍是认识到没有人会选择小 p 或 q,因此从底部开始检查(如 python 脚本中所示)有人发帖)是一个坏主意。如果要手动实用,则大的 p 和 q 必须位于 sqrt(N) 附近。
Here's a relatively simple way to look at it (and one that is doable by hand). If you were to factor the number completely, then the highest factor you would need to consider is sqrt(N):
The first prime below this is 100711409, just 6 below the sqrt(N).
therefore these are two factors of N. Your professor made it pretty easy - the trick is to recognize that no one would choose a small p or q so starting your check from the bottom (as in the python script someone posted) is a bad idea. If it's going to be practical by hand, the large p and q must lie near sqrt(N).
有多种快速算法可以解决给定
n
、e
和d
的因式分解问题。您可以在《应用密码学手册》中找到对此类算法的详细描述,第 8 章,第 8.2.2 节。您可以在此处在线免费下载这些章节。该算法本质上是对 Henno Brandsma 对这个问题的回答的仔细阐述。在下面的评论中,用户Imperishable Night提出了一种替代方法,至少在概念上应该更容易理解。
他指出,通常
e
很小。事实上,e
几乎总是 65537。在e
很小的情况下,您可以在未知素数p
中建立一个二次方程,从而轻松地使用例如二次公式来解决它。首先,我们设置 x=p 并求解 x,以遵循约定。我们知道ed = 1 mod phi(n)
,或者等价ed - 1 = k * (p-1)*(q-1)
。现在设置x=p
,因此设置n/x=q
,将两边乘以x
并重新排列我们的项k*x2 + (d*e - k*n - k - 1)*x + k*n = 0。
现在我们有一个方程
形式为 ax2 + bx + c = 0,我们可以使用二次公式求解 x。因此,我们可以在
e
周围的小范围内尝试k
的值,并且二次方程应该只有一个整数解,即正确的 k 的解。注意:
2*k
整除。g
始终是偶数,通常为 2,并且几乎总是 2 的小倍数。当
e
为小的。通过方程ed - 1 = k * (p-1)*(q-1)
两边除以n
很容易看出floor(( ed-1)/n) + 1 == k
。现在使用方程MJ Wiener 的“短 RSA 秘密指数的密码分析” 的第 31 和 32 条可以直接恢复
p
和q
。There are various fast algorithms to solve the problem of factoring
n
givenn
,e
, andd
. You can find a good description of one such algorithm in the Handbook of Applied Cryptography, Chapter 8, section 8.2.2. You can find these chapters online for free download here. The algorithm is essentially a careful elaboration of Henno Brandsma's answer to this very question.In the comment below, user Imperishable Night suggests an alternative method that should be at least conceptually easier to understand.
He notes that usually
e
is small. In facte
is almost always 65537. In the case thate
is small you can develop a quadratic equation in the unknown primep
and thus easily solve for it using e.g. the quadratic formula. To proceed, let's set x=p and solve forx
, to stick with convention. We know thated = 1 mod phi(n)
, or equivalentlyed - 1 = k * (p-1)*(q-1)
. Now settingx=p
, and thereforen/x=q
, multiplying both sides byx
and rearranging terms we havek*x2 + (d*e - k*n - k - 1)*x + k*n = 0.
Now we have an equation
of the form ax2 + bx + c = 0 and we can solve for x using the quadratic formula. So we can try values of
k
in a small range arounde
and there should be only one integer solution to the quadratic, the solution for the correct k.Notes:
2*k
.g = gcd(p-1, q-1)
.g
is always even, is often 2, and is otherwise almost always a small multiple of 2.Finding
k
is actually very easy whene
is small. By taking the equationed - 1 = k * (p-1)*(q-1)
and dividing both sides byn
it is fairly easy to see thatfloor((ed-1)/n) + 1 == k
. Now using equations31 and 32 of M.J. Wiener's "Cryptanalysis of Short RSA Secret Exponents" one can directly recover
p
andq
.Wolframalpha 告诉我因子是 100711409 和 100711423
我刚刚写了一个简单的 Python 脚本来暴力破解它。
正如 amdfan 指出的那样,从顶部开始是一种更好的方法:
这可以大大改进,但它仍然可以正常工作。您可以通过仅测试原始因子来改进它,但对于像您这样的小值,这应该足够了。
Wolframalpha tells me that the factors are 100711409 and 100711423
I just wrote a naive Python script to bruteforce it.
As amdfan pointed out, starting from the top is a better approach:
This could be heavily improved, but it still works without a problem. You could improve it by just testing primfactors, but for small values like yours this should be enough.
RSA 的定义告诉您模数
n = pq
。您知道n
,因此您只需找到两个数字p
和q
,它们相乘即可产生n
。您知道p
和q
是素数,所以这就是素数分解问题。对于相对较小的数字,您可以通过暴力破解来解决此问题,但 RSA 的整体安全性取决于此问题通常难以解决的事实。
The definition of RSA tells you that the modulus
n = pq
. You known
so you just need to find two numbersp
andq
that multiply to producen
. You know thatp
andq
are prime, so this is the prime factorisation problem.You can solve this by brute force for relatively small numbers but the overall security of RSA depends on the fact that this problem is intractable in general.
这是《应用密码学手册》章节中快速因式分解方法的 Java 实现8 第 8.2.2 节(感谢 GregS 找到它):
典型的输出是
Here is a Java implementation of the fast factoring method from the Handbook of Applied Cryptography chapter 8 section 8.2.2 (thanks to GregS for finding it):
A typical output is
执行此操作的算法是(这适用于任何示例,而不仅仅是任何计算机都可以轻松分解的这个小示例):
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)
,通过
e
和d
的构造,最后一个保证为1。我们现在寻找该序列中的第一个 1。前面的那个要么是
+1
要么是-1
(1 的微分根,
mod n
),我们用不同的 a 或某个不等于+1
的数字x
重做,或者-1
mod n
。在后一种情况下,
gcd(x-1, n)
是n
的非平凡除数,因此p
或q
,我们就完成了。可以证明,随机 a 的概率约为 0.5,因此我们需要进行几次尝试,但一般不会进行太多尝试。The algorithm to do this is (and this will work for any example, not only this small one that can be factored easily by any computer):
ed - 1
is a multiple ofphi(n) = (p-1)(q-1)
, so is at least a multiple of 4.ed - 1
can be computed as 40571156445208704 which equals2^7 * 316962159728193
,and we call
s=7
andt = 316962159728193
.(in general: any even number is a power of 2 times an odd number).
Now pick a in
[2,n-1)
at random, and compute (by successive squaring modulon
) the sequencea^t (mod n), a^(2t) (mod n), a^(4t) (mod n)..
until at mosta^((2^7)*t) (mod n)
,where the last one is guaranteed to be 1, by the construction of
e
andd
.We now look for the first 1 in that sequence. The one before it will either be
+1
or-1
(a trivial root of 1,
mod n
) and we redo with a different a, or some numberx
which does not equal+1
or-1
mod n
.In the latter case
gcd(x-1, n)
is a non-trivial divisor ofn
, and sop
orq
, and we are done. One can show that a random a will work with probability about 0.5, so we need a few tries, but not very many in general.这两篇论文可能会有用
当我对连分数进行一些基础研究时遇到了它们。
These two papers could possibly come in useful
Came across them when I was doing some basic research on continued fractions.
很抱歉使用死灵术,但是一位朋友问过我这个问题,在把他指到这里后,我意识到我并不真正喜欢其中的任何答案。对模进行因式分解并获得素数(p 和 q)后,您需要找到 totient,即
(p-1)*(q-1)
。现在,要找到私有指数,您需要找到公共指数的逆模 totient。
现在您有了私钥,就这么简单。对于大整数,除了因式分解之外的所有这些几乎可以立即完成。
我写了一些代码:
我使用的因式分解算法很愚蠢,但很简洁,所以对此持怀疑态度。在这个特定的示例中,代码几乎立即运行,但这主要是因为所讨论的讲师提供了一个连续使用两个素数的示例,这对于 RSA 来说并不现实。
如果您想消除我愚蠢的迭代搜索,您可以放入一些真正的因式分解算法,并且在合理的时间内将密钥分解为大约 256 位。
Sorry for the necromancy, but a friend asked me about this, and after pointing him here, I realized that I didn't really like any of the answers. After factoring the modulus and getting the primes (p and q), you need to find the totient, which is
(p-1)*(q-1)
.Now, to find the private exponent, you find the inverse of the public exponent mod the totient.
And now you have your private key, that easy. All of this except for the factorization can be done almost instantly for huge integers.
I wrote some code:
The factorization algorithm I used is stupid, but concise, so grain of salt there. In this particular example the code runs almost instantly, but that is largely because the instructor in question provided an example that uses two primes in a row, which isn't really realistic for RSA.
If you wanted to cut out my stupid iterative search, you could put in some real factorization algorithm, and factor keys likely up to around 256 bits in a reasonable amount of time.
您需要对模数进行因式分解,这是公钥的第一个参数 10142789312725007。尽管存在更复杂/快速的算法,但可以使用蛮力(检查从 3 到 sqrt(n) 的每个奇数,如果它是一个因数)。
由于数字太大而无法放入传统整数(甚至 64 位)中,因此您可能需要一个支持任意长度整数的数字库。对于 C,有 GMP 和 MPIR(对 Windows 更友好)。对于 PHP,有 Bignum。 Python 带有一个内置的 - 内置的整数数据类型已经是任意长度的。
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.
关于大半素数的因式分解有很多不好的猜测,这些猜测会涉及暴力或筛选,而这两种方法都不需要分解半素数。在我的电脑上,64 位需要 1 - 2 秒,256 位通常不到 2 天
There is a lot of bad speculation about factorization of large semi primes which go into brute force or sieving neither of which is required to factorise the semi prime. 64 bit takes 1 - 2 seconds on my pc, and 256 bit generally less than 2 days
我建议您阅读二次筛。如果你自己实现一个,这肯定是值得的。如果你明白了原理,你就已经有所收获了。
I suggest you read about the Quadratic Sieve. If you implement one yourself, this is surely worth the credit. If you understand the principles, you already gained something.