Håstad's Broadcast Attack

Segue implementação de Håstad's Broadcast Attack em MPIR. Usei esse código para resolver um challenge famoso de criptografia.


 

/*
 * RSA Broadcast Attack using MPIR.
 *
 *
 * Glaudson Ocampos - <glaudson@securitylabs.com.br>
 * Nash Leon - <nashleon@gmx.de>
 *
 * Compile com:
 * $ gcc -o rsa_bcast_mpir rsa_bcast_mpir.c -lmpir -Wall
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <mpir.h>

void uso(char *progname) {
    fprintf(stdout, "%s <C1> <C2> <C3> <N1> <N2> <N3> <valor_de_e>\n",
            progname);
    fflush(stdout);
    _exit(0);
}

int main(int argc, char *argv[]) {
    mpz_t rop, x0, x1, y0; /* Need many variables, linux glibc crashes easily! */
    mpz_t ax0, ax1, ay0;
    mpz_t bx0, bx1, by0;
    mpz_t cx0, cx1, cy0, cy1;
    mpz_t oper_1, oper_2, oper_3, oper_4;
    mpz_t c1, c2, c3;
    mpz_t n1, n2, n3;
    mpz_t expoente_negativo;
    unsigned long int e = 3;

    if (argc < 7) {
        uso(argv[0]);
    }

    mpz_init(c1);
    mpz_init(c2);
    mpz_init(c3);
    mpz_init(n1);
    mpz_init(n2);
    mpz_init(n3);
    mpz_init(expoente_negativo);

    mpz_init_set_str(c1, argv[1], 16); //hexadecimal to int;
    mpz_init_set_str(c2, argv[2], 16);
    mpz_init_set_str(c3, argv[3], 16);
    mpz_init_set_str(n1, argv[4], 16);
    mpz_init_set_str(n2, argv[5], 16);
    mpz_init_set_str(n3, argv[6], 16);

    e = atoi(argv[7]);

    mpz_init_set_str(expoente_negativo, "-1", 16);

    /*
     * X^3 = C1 * (N2*N3) * ((N2N3)^-1 mod N1) +
     *       C2 * (N1*N3) * ((N1N3)^-1 mod N2) +
     *       C3 * (N1*N2) * ((N1N2)^-1 mod N3) (mod N1 * N2 * N3)
     *
     * M = X^1/3
     *
     * Então,
     *
     * oper_1 = C1 * (N2*N3) * ((N2N3)^-1 mod N1)
     * oper_2 = C2 * (N1*N3) * ((N1N3)^-1 mod N2)
     * oper_3 = C3 * (N1*N2) * ((N1N2)^-1 mod N3)
     * oper_4 = oper_1 + oper_2 + oper_3 (mod N1 * N2 * N3)
     *
     *
     */

    mpz_init(rop);
    mpz_init(x0);
    mpz_init(x1);
    mpz_init(y0);

    mpz_init(oper_1);
    mpz_init(oper_2);
    mpz_init(oper_3);
    mpz_init(oper_4);

    /*
     * oper_1 = C1 * (N2*N3) * ((N2N3)^-1 mod N1)
     * x0 = N2 * N3
     * x1 = C1 * x0
     * y0 = (x0)^-1 mod N1
     * oper_1 = x1 * y0
     *
     */

    mpz_mul(x0, n2, n3);
    mpz_mul(x1, c1, x0);
    mpz_powm(y0, x0, expoente_negativo, n1);
    mpz_mul(oper_1, x1, y0);

    mpz_clear(x0);
    mpz_clear(x1);
    mpz_clear(y0);

    /*
     * oper_2 = C2 * (N1*N3) * ((N1N3)^-1 mod N2)
     * x0 = N1 * N3
     * x1 = C2 * x0
     * y1 = (x0)^-1 mod N2
     * oper_2 = x1 * y0
     */

    mpz_init(ax0);
    mpz_init(ax1);
    mpz_init(ay0);

    mpz_mul(ax0, n1, n3);
    mpz_mul(ax1, c2, ax0);
    mpz_powm(ay0, ax0, expoente_negativo, n2);
    mpz_mul(oper_2, ax1, ay0);

    mpz_clear(ax0);
    mpz_clear(ax1);
    mpz_clear(ay0);

    /*
     * oper_3 = C3 * (N1*N2) * ((N1N2)^-1 mod N3)
     * x0 = N1 * N2
     * x1 = C3 * x0
     * y1 = (x0)^-1 mod N3
     * oper_3 = x1 * y0
     */

    mpz_init(bx0);
    mpz_init(bx1);
    mpz_init(by0);

    mpz_mul(bx0, n1, n2);
    mpz_mul(bx1, c3, bx0);
    mpz_powm(by0, bx0, expoente_negativo, n3);
    mpz_mul(oper_3, bx1, by0);

    mpz_clear(bx0);
    mpz_clear(bx1);
    mpz_clear(by0);

    /*
     * oper_4 = oper_1 + oper_2 + oper_3 (mod N1 * N2 * N3)
     * x0 = N1 * N2
     * x1 = N3 * x0
     * y0 = oper_1 + oper_2
     * y1 = oper_3 + y0
     * oper_4 = y1 mod x1
     */

    mpz_init(cx0);
    mpz_init(cx1);
    mpz_init(cy0);
    mpz_init(cy1);

    mpz_mul(cx0, n1, n2);
    mpz_mul(cx1, n3, cx0);
    mpz_add(cy0, oper_1, oper_2);
    mpz_add(cy1, oper_3, cy0);
    mpz_mod(oper_4, cy1, cx1);

    mpz_clear(cx0);
    mpz_clear(cx1);
    mpz_clear(cy0);
    mpz_clear(cy1);

    /*
     * M = oper_4 ^ 1/e
     * M = oper_4 ^ 1/3
     */

    mpz_root(rop, oper_4, e);

    gmp_printf("\n\n\n\nM= %Zx\n\n\n\n", rop, rop);

    return 0;
}