破裂的短RSA键

https://stackoverflow.com/questions/4078902

28-09-2019
|

题

给定以下RSA键，如何确定 p 和问是？

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)

解决方案

你的老师给了你：

公钥：（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

显然，您不能计算“ 748784069764171^8114231289041741”直接是因为它具有128,808,202,574,088,302位，因此您必须使用该数字模块化指数诡计。

在现实世界”， n 显然要大得多。如果您想查看HTTPS如何在封面下使用617位数的RSA的真实示例 n 和 e 65537，请参阅我的博客文章”HTTPS连接的前几毫秒."

其他提示

这是一种相对简单的观察方法（可以手工处理的方法）。如果您要完全考虑数字，那么您需要考虑的最高因素是SQRT（n）：

sqrt(10142789312725007) = 100711415.9999997567

下面的第一个素数为100711409，低于SQRT（N）的6个。

10142789312725007 / 100711409 = 100711423

因此，这是N的两个因素。小的 p或q因此，从底部开始支票（如某人发布的python脚本）是一个坏主意。如果要手工实用，则大P和Q必须位于SQRT（N）附近。

有各种快速算法可以解决保理问题 n 给出 n, e, ，和 d. 。您可以在应用加密手册中找到对这样一种算法的很好描述，第8章, ，第8.2.2节。您可以在线找到这些章节以免费下载这里. 。该算法实质上是对 Henno Brandsma的答案这个问题。

更新2019年9月25日：

在里面下面评论, ，用户夜晚提出了一种替代方法，至少应该在概念上更容易理解。

他指出通常 e 是小。实际上 e 几乎总是65537。 e 很小，您可以在未知素数中开发二次方程式 p 因此，可以轻松地使用EG解决二次公式. 。要继续，让我们设置x = p并解决 x, ，只是坚持惯例。我们知道 ed = 1 mod phi(n), ，或等效ed - 1 = k * (p-1)*(q-1). 。现在设置 x=p, ，因此 n/x=q, ，将双方乘以 x 和重新安排术语我们有
K*X² +（d*e -k*n -k -1）*x + k*n = 0。
现在我们有一个形式的斧头方程式² + Bx + C = 0，我们可以使用二次公式求解X。因此我们可以尝试 k 在周围的范围很小 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. 。现在使用等式31和32 MJ Wiener的“简短RSA秘密指数的密码分析” 一个人可以直接恢复 p 和 q.

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

这可能会大大改善，但仍然没有问题。您只需测试启动器即可改进它，但是对于像您这样的小价值观，这应该足够了。

RSA的定义告诉您模量 n = pq. 。你知道 n 因此，您只需要找到两个数字 p 和 q 乘产生 n. 。你知道的 p 和 q 是主要的，所以这是主要的分解问题。

您可以通过蛮力解决相对较小的数字解决此问题，但是RSA的总体安全性取决于这个问题通常是棘手的事实。

这是从应用加密手册中的快速分解方法的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)

这两篇论文可能有用

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

要这样做的算法是（这对任何示例都起作用，不仅可以通过任何计算机易于考虑）：

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。之前的那个 +1 或者 -1（1的琐碎根， mod n），我们用不同的a或一些数字重做 x 不等 +1 或者 -1 mod n。在后一种情况下 gcd(x-1, n) 是一个非平凡的除数 n, ，所以 p 或者 q, ，我们完成了。可以表明，随机a的概率约为0.5，因此我们需要一些尝试，但通常不是很多。

我建议您读到二次筛. 。如果您自己实施一个，这肯定值得一提。如果您了解原则，那么您已经获得了一些东西。

对不起，为死灵症，但一个朋友问我这一点，在将他指向这里之后，我意识到我真的不喜欢任何答案。考虑模量并获得素数（P和Q）后，您需要找到构架， (p-1)*(q-1).

现在，要找到私人指数，您可以找到公共指数mod的倒数。

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位。

您需要对模量进行分解，这是公共密钥的第一个参数，10142789312725007。蛮力将执行（如果是一个因素，请检查每个奇数从3到sqrt（n），尽管存在更复杂/快速/快速的算法。

由于该数字太大，无法适应传统的整数（甚至64位），因此您可能需要一个支持任意LONTEGER的数字库。对于C，有GMP和Mip Pir（更适合Windows）。对于PHP，有bignum。 Python带有一个内置的 - 内置整数数据类型已经是任意长度。

关于大型半刺激物的分解，有很多不良的猜测，这些素数变成蛮力或筛分都不需要分解半prime。 64位在我的PC上需要1-2秒，而256位通常少于2天

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow