破解短 RSA 密钥

发布于 2024-09-30 14:49:24 字数 166 浏览 1 评论 0原文

给定以下 RSA 密钥,如何确定 pq 的值是什么?

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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(12

∝单色的世界 2024-10-07 14:49:24

你的老师给了你:

公钥:(10142789312725007, 5)

这意味着

n = 10142789312725007
e = 5 

其中 n 是模数,e 是公共指数。

此外,您还获得

私钥:(10142789312725007、8114231289041741)

表示

 d = 8114231289041741

其中 d 是应保密的解密指数。

您可以通过知道如何将“n”分解为其“p”和“q”质因数来“破坏”RSA:

n = p * q

最简单的方法可能是检查从n的平方根下方开始的所有奇数:

Floor[Sqrt[10142789312725007]] = 100711415

您将得到第一个考虑 4 次尝试:

10142789312725007 mod 100711415 = 100711367
10142789312725007 mod 100711413 = 100711373
10142789312725007 mod 100711411 = 100711387
10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n

现在我们知道了

 p = 100711409

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

为什么这很重要?这是因为 d 是一个特殊的数字,这样

d = e^-1 mod phi(n)
  = e^-1 mod (p-1)*(q-1)

我们就可以验证这一点。

d * e = 40571156445208705 = 1 mod 10142789111302176

这很重要,因为如果您有明文消息 m ,那么密文就是

c = m^e mod n

解密它

m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)

,您可以通过以下方式 :我可以使用您老师的公钥“加密”消息 123456789:

m = 123456789

这将为我提供以下密文:(

c = m^e mod n 
  = 123456789^5 mod 10142789312725007
  = 7487844069764171

请注意,“e”在实践中应该大得多,因为对于较小的“m”值,您甚至不会超过 n)

不管怎样,现在我们有了“c”,可以用“d”反转它

m = c^d mod n
  = 7487844069764171^8114231289041741 mod 10142789312725007
  = 123456789

显然,你不能直接计算“7487844069764171^8114231289041741”,因为它有128,808,202,574,088,302位,所以你必须使用 模幂技巧。

在“现实世界”中,n 显然要大得多。如果您想了解 HTTPS 如何在幕后使用 RSA(包含 617 位 ne 65537)的真实示例,请参阅我的博客文章“< a href="http://www.moserware.com/2009/06/first-few-milliseconds-of-https.html" rel="noreferrer">HTTPS 连接的前几毫秒。"

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."

Spring初心 2024-10-07 14:49:24

这是一种相对简单的查看方法(并且可以手动完成)。如果您要将数字完全分解,那么您需要考虑的最高因子是 sqrt(N):

sqrt(10142789312725007) = 100711415.9999997567

下面的第一个质数是 100711409,仅比 sqrt(N) 低 6。

10142789312725007 / 100711409 = 100711423 

因此,这是 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):

sqrt(10142789312725007) = 100711415.9999997567

The first prime below this is 100711409, just 6 below the sqrt(N).

10142789312725007 / 100711409 = 100711423 

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).

烟酉 2024-10-07 14:49:24

有多种快速算法可以解决给定 ned 的因式分解问题。您可以在《应用密码学手册》中找到对此类算法的详细描述,第 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 的解。

注意:

  1. 一切都必须是整数,因此判别式必须是完全平方,否则我们可以丢弃 k 并尝试下一个。此外,分子必须能被2*k整除。
  2. 有时使用 Carmichael lambda 函数代替 Euler phi 函数。这让事情变得有点复杂,因为我们现在还必须猜测 g = gcd(p-1, q-1)。 g 始终是偶数,通常为 2,并且几乎总是 2 的小倍数。

e 为小的。通过方程
ed - 1 = k * (p-1)*(q-1) 两边除以 n 很容易看出 floor(( ed-1)/n) + 1 == k。现在使用方程
MJ Wiener 的“短 RSA 秘密指数的密码分析” 的第 31 和 32 条可以直接恢复pq

There are various fast algorithms to solve the problem of factoring n given n, e, and d. 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 fact e is almost always 65537. In the case that e is small you can develop a quadratic equation in the unknown prime p and thus easily solve for it using e.g. the quadratic formula. To proceed, let's set x=p and solve for x, to stick with convention. We know that ed = 1 mod phi(n), or equivalently
ed - 1 = k * (p-1)*(q-1). Now setting x=p, and therefore n/x=q, multiplying both sides by x and rearranging terms we have
k*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 around e and there should be only one integer solution to the quadratic, the solution for the correct k.

Notes:

  1. Everything must be an integer, thus the discriminant must be a perfect square or we can discard k and try the next one. Also, the numerator must be divisible by 2*k.
  2. Sometimes the Carmichael lambda function is used instead of the Euler phi function. This complicates things just a little bit because we must now also guess the 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 when e is small. By taking the equation
ed - 1 = k * (p-1)*(q-1) and dividing both sides by n it is fairly easy to see that floor((ed-1)/n) + 1 == k. Now using equations
31 and 32 of M.J. Wiener's "Cryptanalysis of Short RSA Secret Exponents" one can directly recover p and q.

揪着可爱 2024-10-07 14:49:24

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

这可以大大改进,但它仍然可以正常工作。您可以通过仅测试原始因子来改进它,但对于像您这样的小值,这应该足够了。

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:

p = 10142789312725007
for i in xrange(int(p**0.5+2), 3, -2):
    if p%i == 0:
        print i
        print p/i
        break

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.

红ご颜醉 2024-10-07 14:49:24

RSA 的定义告诉您模数n = pq。您知道 n,因此您只需找到两个数字 pq,它们相乘即可产生 n。您知道 pq 是素数,所以这就是素数分解问题。

对于相对较小的数字,您可以通过暴力破解来解决此问题,但 RSA 的整体安全性取决于此问题通常难以解决的事实。

The definition of RSA tells you that the modulus n = pq. You know n so you just need to find two numbers p and q that multiply to produce n. You know that p and q 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.

初吻给了烟 2024-10-07 14:49:24

这是《应用密码学手册》章节中快速因式分解方法的 Java 实现8 第 8.2.2 节(感谢 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)

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):

/**
 * 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;
    }
}

A typical output is

100711423 100711409 (3ms)
情话难免假 2024-10-07 14:49:24

执行此操作的算法是(这适用于任何示例,而不仅仅是任何计算机都可以轻松分解的这个小示例):

ed - 1phi(n ) = (p-1)(q-1),所以至少是 4 的倍数。
ed - 1 可以计算为 40571156445208704,等于 2^7 * 316962159728193
我们调用 s=7t = 316962159728193
(一般来说:任何偶数都是奇数的2的幂)。
现在随机选择 [2,n-1) 中的一个,并计算(通过连续平方模 n)序列
a^t (mod n)、a^(2t) (mod n)、a^(4t) (mod n).. 直到最多 a^((2^7) *t) (mod n),
通过ed的构造,最后一个保证为1。

我们现在寻找该序列中的第一个 1。前面的那个要么是 +1 要么是 -1
(1 的微分根,mod n),我们用不同的 a 或某个不等于 +1 的数字 x 重做,或者-1 mod n
在后一种情况下,gcd(x-1, n)n 的非平凡除数,因此 pq,我们就完成了。可以证明,随机 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 of phi(n) = (p-1)(q-1), so is at least a multiple of 4.
ed - 1 can be computed as 40571156445208704 which equals 2^7 * 316962159728193,
and we call s=7 and t = 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 modulo n) the sequence
a^t (mod n), a^(2t) (mod n), a^(4t) (mod n).. until at most a^((2^7)*t) (mod n),
where the last one is guaranteed to be 1, by the construction of e and d.

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 number x which does not equal +1 or -1 mod n.
In the latter case gcd(x-1, n) is a non-trivial divisor of n, and so p or q, 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.

天煞孤星 2024-10-07 14:49:24

这两篇论文可能会有用

当我对连分数进行一些基础研究时遇到了它们。

These two papers could possibly come in useful

Came across them when I was doing some basic research on continued fractions.

江湖彼岸 2024-10-07 14:49:24

很抱歉使用死灵术,但是一位朋友问过我这个问题,在把他指到这里后,我意识到我并不真正喜欢其中的任何答案。对模进行因式分解并获得素数(p 和 q)后,您需要找到 totient,即 (p-1)*(q-1)

现在,要找到私有指数,您需要找到公共指数的逆模 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 位。

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.

public_exponent * private_exponent = 1 mod 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:

// 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);

}

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.

情释 2024-10-07 14:49:24

您需要对模数进行因式分解,这是公钥的第一个参数 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.

满地尘埃落定 2024-10-07 14:49:24

关于大半素数的因式分解有很多不好的猜测,这些猜测会涉及暴力或筛选,而这两种方法都不需要分解半素数。在我的电脑上,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

吃颗糖壮壮胆 2024-10-07 14:49:24

我建议您阅读二次筛。如果你自己实现一个,这肯定是值得的。如果你明白了原理,你就已经有所收获了。

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.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文