/* $Id: t_dibigdRSACrack.cpp $ */

/*
* Copyright (C) 2026 David Ireland, D.I. Management Services Pty Limited
* <https://di-mgt.com.au/contact/> <https://di-mgt.com.au/bigdigits.html>
* SPDX-License-Identifier: MPL-2.0
*
* Last updated:
* $Date: 2026-05-05 02:02 $
* $Revision: 1.0.1 $
* $Author: dai $
*/

/* Crack RSA if used incorrectly to three recipients.
Ref: <https://di-mgt.com.au/crt.html#crackingrsa>
Alice sends the same message m encrypted using the RSA algorithm to three recipients 
with different moduli n1,n2,n3 all coprime to each other but using the same exponent e=3. 
Eve recovers the three ciphertext values c1,c2,c3 and knows the public keys (ni,e=3) of all the recipients. 
Can Eve recover the message without factoring the moduli? Yes.
*/

#ifdef NDEBUG
#undef NDEBUG
#endif
#include <iostream>
#include <string>
#include <iomanip>
#include <stdexcept>
#include <assert.h>
#include "dibigd.hpp"
using std::cout;
using std::endl;
using namespace dibigd;


void do_test() {
    cout << "Crack RSA if used incorrectly to three recipients." << endl;
    cout << "==================================================" << endl;
    // INPUT:
    BigDigit n1("0xa9c737dd808d02866fbf1acf05de2eb124137007a4965ec4dcbfa6d02f97e0123a8fd3691e414a1382f38ab39b09975705eceaf1131a283c937b309f1c1417f9");
    BigDigit n2("0xb7e9e114a08adff12f762d7f0e1f16202e1eb7a7f2852369bdf44865783d19111e6d61b31de987bcb9775099e220a798d4f99cd3e5f04c64f87a35c0268a83e9");
    BigDigit n3("0xc2bdbd4e36ba20d37d5d1e968f09f2fc7b41a97f3052274e4892d50d5fb337c923048aed7d393135ee55711e5c74975867f13d3845bac9588b4be170d08bab57");
    cout << "Three public modulus values of bit lengths: " << n1.bitlen() << " " << n2.bitlen() << " " << n3.bitlen() << endl;
    n1.printhex("n1="); n2.printhex("n2="); n3.printhex("n3=");
    // Common public exponent
    BigDigit e = 3;
    e.print("common public exponent, e=");
    // Message to be encrypted...
    BigDigit m("0x2ffffffffffffffffffffffffffffffffffffffffff0000deadbeefcafe");
    m.printhex("message, m=");

    // Compute three ciphertexts (identical messages, no random padding: do not do this!)
    BigDigit c1 = m.mod_exp(e, n1);
    BigDigit c2 = m.mod_exp(e, n2);
    BigDigit c3 = m.mod_exp(e, n3);

    /* Send these 3 ciphertexts to the three recipients, assume they are recovered by an eavesdropper
    and that she has the recipients' public keys (n1,e), (n2,e), (n3,e)) */
    cout << "Three ciphertexts, m^e(mod n1), m^e(mod n2), m^e(mod n3):" << endl;
    c1.printhex("c1="); c2.printhex("c2="); c3.printhex("c3=");

    /* For our method to work we require that the three moduli (n1,n2,n3) are pairwise coprime 
    (this is most likely in practice, and is the case with this example, but we check anyway).
    */ 
    assert(n1.gcd(n2) == 1);  // gcd(n1,n2)==1
    assert(n2.gcd(n3) == 1);  // gcd(n2,n3)==1
    assert(n3.gcd(n1) == 1);  // gcd(n3,n1)==1

    cout << "Do calculations..." << endl;
    /* Use Gauss's algorithm to find a solution x, in the range 0 <= x < n1.n2.n3, 
    to the three simultaneous congruences
    x = c1 (mod n1)
    x = c2 (mod n2)
    x = c3 (mod n3)
    */

    // Compute N=n1*n2*n3
    BigDigit N = n1 * n2 * n3;
    // Compute Ni = N/ni, di = Ni^-1 (mod ni) for i = 1,2,3
    BigDigit N1 = N / n1;
    BigDigit N2 = N / n2;
    BigDigit N3 = N / n3;
    BigDigit d1 = N1.mod_inv(n1);
    BigDigit d2 = N2.mod_inv(n2);
    BigDigit d3 = N3.mod_inv(n3);
    // Compute x = c1.N1.d1 + c2.N2.d2 + c3.N3.d3 (mod N)...
    BigDigit x = c1.mod_mult(N1, N).mod_mult(d1, N);
    x += c2.mod_mult(N2, N).mod_mult(d2, N);
    x += c3.mod_mult(N3, N).mod_mult(d3, N);
    x %= N;
    x.printhex("x=");
    /* We know from the Chinese Remainder Theorem that m^3 < n1.n2.n3, so it follows that x = m^3 
    and so m can be recovered by simply computing the integer cube root of x
    */
    BigDigit m1 = x.cbrt();
    m1.printhex("m'=cbrt(x)=");
    // Do we have a match ?
    bool ok = m == m1;
    cout << "Match? (m'==m) is " << std::boolalpha << ok << endl;
    if (ok)
        cout << "SUCCESS. We cracked it!" << endl;
    else
        cout << "FAILED!" << endl;
}

int main() {
    /* MSVC memory leak checking stuff */
#if _MSC_VER >= 1100
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
    _CrtSetReportMode(_CRT_WARN, _CRTDBG_MODE_FILE);
    _CrtSetReportFile(_CRT_WARN, _CRTDBG_FILE_STDOUT);
    _CrtSetReportMode(_CRT_ERROR, _CRTDBG_MODE_FILE);
    _CrtSetReportFile(_CRT_ERROR, _CRTDBG_FILE_STDOUT);
#endif

    /* Catch any exceptions */
    try {
        do_test();
    }
    catch (const std::exception& e) {
        // Handle standard exceptions with a specific message
        std::cerr << "Standard exception: " << e.what() << std::endl;
    }
    catch (...) {
        std::cerr << "Caught unknown exception." << std::endl;
    }
    cout << endl << "ALL DONE." << endl << endl;

    return 0;
}