RSA 密码学 C C++

使用 C++ 和 GMPXX 库破解弱 RSA - 第一部分

Daniel Ramnath

5.00/5 (3投票s)

2024 年 6 月 30 日

CPOL

6分钟阅读

6094

使用 C++ 和 GMPXX 库破解弱 RSA

引言

Rivest-Shamir-Adleman (RSA) 算法是一种非对称加密算法，我在以下链接中提供了 RSA 的解释，该链接是我的 LinkedIn 个人资料。

“公钥或 RSA 算法，如何计算和使用。简单的解释。”

“用于 4096 位整数的 C/C++ 代码，使用多精度算术库 GMP 进行 RSA 公钥加密”

如果素数因子 p 和 q 接近，我将在本文中详细介绍如何仅使用公模 N 来破解弱 RSA。我提供了使用 GMPXX (C++ GNU 多精度算术) 包编写的 C++ 代码。此外，如果给定数字对的差值很大，例如 |p - q|² < 2²²√N 或 |p - q| < 2¹¹，即使 |p - q| < 2¹⁰²⁴，该代码也能正常工作。而且，如果 p 和 q 在数学上有关联，仍然可以破解 RSA。

背景

本文基于 @Profssor Bill Buchanan 在 LinkedIn 上发布的一篇文章，他在其中提出了挑战：“仅给定公钥 (N, e)，其中素数因子 p 和 q 接近，如何解密给定的密文？

https://www.linkedin.com/feed/update/urn:li:activity:7202375661129216000/

我还将提供另外两个示例，其中一个示例的模数 N 为 4096 位，并被分解为 p 和 q，它们之间存在巨大差异，但没有密文。

计算机安全实验室负责人、应用密码学组领导者 @Dan Boneh 教授有一个作业问题，可以作为另一个例子。

有两个示例，其中包含解决方案 1 以及 C++ 代码和输出结果。第三个示例只有解决方案 2，没有代码和输出结果。

输出

示例 1

来自 @Professor Bill Buchanan 的问题陈述。给定公模 N

引用

N=139985042453534191530814338630181605151083085316793042716222557353976947 315273177835521525749840053133030855380542806571666507770967095566644784849 872363216671790790178991932306774136746501625197899629158716598807039762413 315491667057829160271196105730383640876012723708906672870020514209809347940669608802423

素数因子 p 和 q 的值如下面图片所示。找到私钥后，密文 C 的解密消息已突出显示。

引用

C=759403557749605329827397277511270391153358711253814758994265586537563834 069578951317106641271769359009763155459549100243237444918414776051520819739 308951078932471044935528938901932839125585139958615291047606279321516578306 03055827610345212590943506302746823964240665504252713259356862520153054934758430461775

如下面图片所示。解密的消息是 “led zepplin”。

请注意，p 和 q 之间的差值在橙色框中标记，非常小。

示例 2

此示例中的模数非常大，是 4096 位模数，其中 [(A - √N) < 2³²] 或 |p - q| < 2¹⁰²⁴。给定公模 N

引用

N=136701171352748557830760791067094073451052752717330296857467287200427749 314688454994360294350385596122243967672715335028160598238200895345922797530 312396745491689826853365977473725783879527408074801633878039202701433848516 058779075653300544455805093591770085766567220922624447839794244041182174834 468239556270336669113098148086565069103792403512719311465515121288449125459 571651433490921460112580652868108100301221860197231066864120475986292904735 279305068898762832182264929029689869871909358261877551847323992509552576244 184871370554211041507630648451495598193666647444177437656319076781277943805 078597732600807500600893552081283155774820550135171212021686309341249855432 864490067347685237436212916753489269022611304526341310619253728832585519231 291972763114367440503019507423972430439294427235477110880889644167852035630 823920209429788013804119315895906963850736459907145365807106222701707550220 744229452130569352399727351142786657144424992223335899295744976046212307204 299032048140436036417832629288639445270301178913821429373055988904096433718 415454333119110661673671969783466126593115213492392854396433838395287150461 016374371342854881582427787463795478474958675936693110335523210170294494217 747530167920687561509467853544120731

素数因子 p 和 q 的值如以下输出所示。在我机器上花了大约 1 小时。也请看橙色框中标记的素数 p 和 q 之间的差值。迭代次数为 1483934994。而在上面的解决方案中，迭代次数仅小于 2。这意味着具有 2048 位模数 N 的 RSA 可以轻松破解。

使用 C++ 代码

此代码适用于以上两个示例，并且自解释。

#define NOMINMAX 

#include <stdio.h>

#include <iostream>
using namespace std;

#include "gmp.h"
#include "gmpxx.h"
#pragma comment(lib, "mpir.lib")
#pragma comment(lib, "mpirxx.lib")

// Conver the hexa decimal string to ASCII string
string HexToStr(string szHex)
{
    string szMsg;
    for (int i = 0; i < szHex.length(); i += 2)
    {
        string szSub = szHex.substr(i, 2);
        //char ch = stoul(szSub, nullptr, 16);
        char ch = stoul(szSub, nullptr, 16);
        szMsg += ch;
    }
    return szMsg;
}
void wmain()
{
    mpz_class N("0");

    cout << "Please input the public modulo N: ";
    string szN;
    cin >> szN;
    N = szN;

    // Since there is no ceiling function in GMP so we increment by 1
    // and perform sqrt and then decrement by 1 to get ceiling effect.
    mpz_class A = N + 1; 
    mpz_sqrt(A.get_mpz_t(), A.get_mpz_t());
    A -= 1;

    // We iterate till 2^128 and to find A(i) using √N
    mpz_class pow;
    mpz_ui_pow_ui(pow.get_mpz_t(), 2, 128); // 2^128

    mpz_class p, q;
    // Iterate A(i) by one and fine x(i)
    for (mpz_class i = 0; i < pow; i++)
    {
        mpz_class AS = A * A;
        mpz_class XS = AS - N;
        // We perform absolute is in case XS is negative.
        mpz_abs(XS.get_mpz_t(), XS.get_mpz_t());
        // Find x
        mpz_class X;
        mpz_sqrt(X.get_mpz_t(), XS.get_mpz_t());
        // Find p(i) and q(i)
        p = A - X;
        q = A + X;
        // Multiply p(i) and q(i) and compare with the original modulo N
        // If both are same then p(i) and q(i) are the prime factors of N
        // and stop iterating.
        mpz_class NN = p * q;
        if (N == NN)
        {
            cout << endl << "The prime factors of N are:" << endl << endl;
            cout << "p=" << p.get_str() << endl << endl;
            cout << "q=" << q.get_str() << endl << endl;
            //cout << "N=" << NN.get_str() << endl;
            break;
        }
        A++;
    }
    mpz_class e(0);
    cout << "Please input the public component e: ";
    string sze;
    cin >> sze;
    e = sze;
    if (e != 0)
    {
        cout << "e = " << e.get_str() << " (PUBLIC KEY)" << endl << endl;

        mpz_class enc(0);
        cout << "Please input the cypher test: ";
        string szenc;
        cin >> szenc;
        enc = szenc;

        // Calculate the totient of N
        mpz_class phi;
        phi = (p - 1) * (q - 1);

        // Calculate the private key d. d and n together form the private key.
        // d = (e ^ -1) mod phi. d is the inverse of e mod phi.
        mpz_class d;
        // This was giving wrong result. It worked for small number.
        //mpz_powm_ui(d, e, -1, phi);
        // So I used mpz_invert to find the inverse of e.
        mpz_invert(d.get_mpz_t(), e.get_mpz_t(), phi.get_mpz_t());
        cout << endl << "d = " << d.get_str() << " (PRIVATE KEY)" << endl << endl;

        // Decrypte the encrypted message enc using the PRIVATE KEY d such that
        // dec = (enc ^ d) mod n
        mpz_class dec;
        mpz_powm(dec.get_mpz_t(), enc.get_mpz_t(), d.get_mpz_t(), N.get_mpz_t());
        cout << "dec = " << dec.get_str() << " (DECRYPTED MESSAGE)" << endl;

        string szMsg = "";
        szMsg = HexToStr(dec.get_str(16));
        cout << "msg = " << szMsg.c_str() << " (MESSAGE)" << endl;
    }
}

工作原理

解决方案 1

假设我们有两个点 p 和 q，所以，

N = p X q，以及

A 是 p 和 q 的中点。p, q, A 和 N 之间的关系如下图所示。

以上图中唯一已知的值是 N；其他值是未知的。x 分别是 p 和 A、q 和 A 之间的距离。请始终记住 √N < A。我下面为初学者进行了解释。我们的目标是找到 N, p 和 q 的素数因子。我们可以通过从 √N 开始迭代到 p 或 q 来找到素数因子，但这不可行。但是，通常有更好的方法。从上图中，我们也知道 N = p X q。

因为 A 是 p 和 q 之间的中点，所以 p = (A - x) & q = (A + x)，

因为 N = p X q，将上面方程中的 p 和 q 代入，我们得到：

N = (A - x) X (A + x) = (A² - x²)。所以，N = A² - x²。因此，

通过迭代查找 'A'

由于 N 是已知的，我们需要找到 A。我们将使用 √N 来找到 A。我们将迭代 √N 以找到 A，如下所示：

A₀=ceiling(√N) <- 通过 ceiling 我们忽略了小数部分。

A₁=A₀+1 <- 每次迭代增加一

.......

A_(i-1)=A_(i-2)+1

A_i=A_(i-1)+1.

对于 A_i 的每个值，我们将将其代入上面的方程中，并找到 x_i(即 x)。

我们有了 A_i 和 x_i，得到：

p_i=(A_i-x_i) 和 q_i=(A_i+x_i)

如果 N = (p_i X q_i)，那么 p_i 和 q_i 就是 N 的素数因子。

p=p_i 和 q=q_i

解决方案 2

以下是 Dan Boneh 教授提出的问题。给定模数 N，它是两个接近的素数 p 和 q 的乘积。找到这两个因子。提示

令 p' = 3p 且 q' = 2q 且 N' = p' X q' = 3p X 2q = 6N。

给定 p', q' 和 N'，我们可以使用下面图片中所示的解决方案 1 中描述的相同技术。

然而，上述困境有一个转折。p 和 q 是奇数，因为它们是素数。也就是说，2q 是偶数，而 3p 是奇数，此外，3p+2q 是奇数。结果，中点 A 是一个分数而不是整数，其小数部分始终是 .5。由于解决方案 1 是以 1 为步长进行迭代，因此解决方案 1 无法解决上述问题。如果我们改为以 .5 而不是 1 为步长进行迭代，解决方案 1 将适用于此情况，并且您可以轻松地分解模数。如果您宁愿不处理分数，您可以将上面的直线中的每个点（包括 A）乘以 2。这将使 A 的中点成为一个整数，如下图所示。

然而，解决方案 2 仍然不允许 C++ 代码工作。除非您对代码进行一些更改，否则它将无法工作，而我并未提供这些更改。

致初学者

如果您对理解上述问题仍有困难，请阅读此文。

给定两个点 a 和 b

令 N = a X b。如果 a = b，则

N = a X a 或 b X b = a² 或 b²

平均值 A 是：

因此，

如果 a 和 b 之间的距离在增长，那么

结论

大多数专业的程序员，在有足够的时间/动力的情况下，都可以实现一个椭圆曲线加密应用程序，该应用程序能够加密和解密数据。然而，这样的应用程序不可避免地容易受到一系列侧信道攻击，因此实际上并不安全。实现加密本身并不困难，但安全地实现加密很难，并且出于与发明自己的密码系统相同的原因而不被推荐。这是第一部分，意味着还有一种称为 Wiener 攻击的攻击，我将在稍后发布。