BBAD Challange

/*
Made by IamLupo!

Challange: https://backdoor.sdslabs.co/challenges/BBAD

key < 12000

Secret message:
2933070^67
3232427352382723^3475
33^8923
1752173996578580830630^3617
47^1205
1334324742249840763104115177915406053196992583180688299430^5620
*/

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

#include "gmp.h"

int prime[] = {
    2,   3,   5,   7,   11,  13,  17,  19,  23,  29,
    31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
    73,  79,  83,  89,  97,  101, 103, 107, 109, 113,
    127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
    179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
    233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
    283, 293,
    307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
    367, 373, 379, 383, 389, 397, 401, 409, 419, 421,
    431, 433, 439, 443, 449, 457, 461, 463, 467, 479,
    487, 491, 499
};

char keyboard[] = {
    '1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
    'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p',
    'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'z',
    'x', 'c', 'v', 'b', 'n', 'm', 'Q', 'W', 'E', 'R',
    'T', 'Y', 'U', 'I', 'O', 'P', 'A', 'S', 'D', 'F',
    'G', 'H', 'J', 'K', 'L', 'Z', 'X', 'C', 'V', 'B',
    'N', 'M', '?'
};

/* Crypt Data */
struct crypt_data {
    int* list;          // list with prime numbers
    int list_len;

    mpz_t a;
    mpz_t key;
    mpz_t x;
    mpz_t y;

    //Analise
    int min_char;
    int max_char;
};

void cryptDataInit(struct crypt_data* cdata) {
    mpz_init(cdata->a);
    mpz_init(cdata->key);
    mpz_init(cdata->x);
    mpz_init(cdata->y);
}

void cryptDataClear(struct crypt_data* cdata) {
    mpz_clear(cdata->a);
    mpz_clear(cdata->key);
    mpz_clear(cdata->x);
    mpz_clear(cdata->y);
}

/* Function */
int findPrimePos(int input) {
    int i;

    for(i = 0; i < 62; i++) {
        if(prime[i] == input)
            return i;
    }

    return 63;
}

/* Draw */
void drawCipherText(struct crypt_data* cdata) {
    mpz_out_str(stdout, 10, cdata->x);
    printf("^");
    mpz_out_str(stdout, 10, cdata->y);
    printf("\n");
}

void drawList(struct crypt_data* cdata) {
    int i;

    printf("{");
    for(i = 0; i < cdata->list_len; i++) {
        if(i == 0)
            printf(" %d", cdata->list[i]);
        else
            printf(", %d", cdata->list[i]);
    }
    printf(" }\n");
}

void drawConvertedList(struct crypt_data* cdata) {
    int i;
    char* text = malloc((cdata->list_len + 1) * sizeof(char));

    for(i = 0; i < cdata->list_len; i++) {
        text[i] = keyboard[findPrimePos(cdata->list[i])];
    }

    text[cdata->list_len] = '\0';

    printf("%s", text);
}

void drawInfo(struct crypt_data* cdata) {
    printf("list = ");
    drawList(cdata);

    printf("\na = ");
    mpz_out_str(stdout, 10, cdata->a);

    printf("\nkey = ");
    mpz_out_str(stdout, 10, cdata->key);

    printf("\nCryptText = ");
    drawCipherText(cdata);

    printf("min = %d\n", cdata->min_char);
    printf("max = %d\n", cdata->max_char);
}

/* Calculate */
void calcAnalise(struct crypt_data* cdata) {
    mpz_t e, f, temp;
    int i;              // charters

    //Init
    mpz_init(e);
    mpz_init(f);
    mpz_init(temp);

    /* Maximum charters */
    i = 1;

    mpz_mul_ui(e, cdata->x, 12000);
    mpz_set_ui(f, 2);

    while(mpz_cmp(e, f) > 0) {
        i++;

        mpz_set_ui(temp, 2);
        mpz_pow_ui(temp, temp, i);
        mpz_mul(f, f, temp);
    }

    cdata->max_char = i;

    /* Minimum charters */
    i = 1;

    mpz_add_ui(e, cdata->y, 1);         // (y + 1) is lowest key it can be
    mpz_mul(e, cdata->x, e);
    mpz_set_ui(f, 293);                 // highest prime known

    while(mpz_cmp(e, f) > 0) {
        i++;

        mpz_set_ui(temp, 293);
        mpz_pow_ui(temp, temp, i);
        mpz_mul(f, f, temp);
    }

    cdata->min_char = i - 1;

    //Clear
    mpz_clear(e);
    mpz_clear(f);
    mpz_clear(temp);
}

/* Bruteforcer */
int bruteforce(struct crypt_data* cdata, mpz_t progress_a, int level) {
    if(level <= 0) {
        return 0;
    }

    int i;
    mpz_t a, b, c;

    //Init
    mpz_init(a);
    mpz_init(b);
    mpz_init(c);

    for(i = 0; i < 62; i++) {
        mpz_set(a, progress_a);

        mpz_set_ui(b, prime[i]);
        mpz_pow_ui(b, b, level);
        mpz_mod(c, a, b);

        if(mpz_cmp_ui(c, 0) == 0) {
            mpz_div(c, a, b);
            if(mpz_cmp_ui(c, 1) == 0 || bruteforce(cdata, c, level - 1) == 1) {
                //printf("prime[%d] = %d\n", level, prime[i]);

                cdata->list[level - 1] = prime[i];

                mpz_clear(a);
                mpz_clear(b);
                mpz_clear(c);
                return 1;
            }
        }
    }

    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(c);
    return 0;
}

/* Encrypt & Decrypt */
void decrypt(char* str_x, char* str_y, struct crypt_data* cdata) {
    int i, j;
    mpz_t temp, progress_a;

    //Init
    mpz_init(temp);
    mpz_init(progress_a);

    mpz_set_str(cdata->x, str_x, 10);
    mpz_set_str(cdata->y, str_y, 10);

    calcAnalise(cdata);
    cdata->list = malloc(cdata->max_char * sizeof(*(cdata->list)));

    for(i = mpz_get_ui(cdata->y) + 1; i < 12000; i++) {

        mpz_mul_ui(temp, cdata->x, i);
        mpz_add(cdata->a, temp, cdata->y);      //a = y + (key * x)
        mpz_set(progress_a, cdata->a);

        for(j = cdata->min_char; j < cdata->max_char; j++) {
            if(bruteforce(cdata, progress_a, j) == 1) {
                cdata->list_len = j;

                //End Loops
                i = 12000;
                j = cdata->max_char;
            }
            else
            {
                cdata->list_len = 0;
            }
        }
    }

    //Clear
    mpz_clear(temp);
}

void encrypt(char* input, int int_key, struct crypt_data* cdata) {
    int i, j;
    mpz_t temp;

    //Init
    mpz_init(temp);

    mpz_set_ui(cdata->key, int_key);
    cdata->list_len = strlen(input);
    cdata->list = malloc(cdata->list_len * sizeof(*(cdata->list)));

    for(i = 0; i < cdata->list_len; i++) {
        for(j = 0; j < 62; j++) {
            if(input[i] == keyboard[j])
                cdata->list[i] = prime[j];
        }
    }

    mpz_set_ui(cdata->a, cdata->list[0]);
    for(i = 1; i < cdata->list_len; i++) {
        mpz_set_ui(temp, cdata->list[i]);

        //a *= list[i] ^ ( i + 1 )
        mpz_pow_ui(temp, temp, i + 1);
        mpz_mul(cdata->a, cdata->a, temp);
    }

    //y = a % key
    mpz_mod(cdata->y, cdata->a, cdata->key);

    //x = (a - y) / key
    mpz_sub(temp, cdata->a, cdata->y);
    mpz_div(cdata->x, temp, cdata->key);

    //Clear
    mpz_clear(temp);
}

/*
    Found:
        'V'                 5           55^2
        'V'                 13          21^4
        'V'                 45          6^7
        'HJ'                13          1067796^11
        'abcd'              1           150479977324775996363^0
        'abcd'              13          11575382871136615104^11
        'VAcD4'             22          56237954319988116321523858^13
        'VKMAP VAcD4'       5           54306932426718011115164597401855430^1 247446999007947711814704977^4
*/
void test() {
    struct crypt_data cdata;

    //Init
    cryptDataInit(&cdata);

    printf("Found:\n");

    /* ----------------------- */
    encrypt("V", 5, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    /* ----------------------- */
    encrypt("V", 13, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    /* ----------------------- */
    encrypt("V", 45, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    /* ----------------------- */
    encrypt("HJ", 13, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    /* ----------------------- */
    encrypt("abcd", 1, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    /* ----------------------- */
    encrypt("abcd", 13, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    /* ----------------------- */
    encrypt("VAcD4", 22, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    /* ----------------------- */
    encrypt("VKMAP", 5, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    encrypt("VAcD4", 5, &cdata);
    printf("    ");
    drawCipherText(&cdata);
    /* ----------------------- */

    //Clear
    cryptDataClear(&cdata);
}

/*
    CipherText:
        2933070^67
        3232427352382723^3475
        33^8923
        1752173996578580830630^3617
        47^1205
        1334324742249840763104115177915406053196992583180688299430^5620
*/
void crack() {
    struct crypt_data cdata;

    //Init
    cryptDataInit(&cdata);

    decrypt("2933070", "67", &cdata);
    drawConvertedList(&cdata);
    printf(" ");
    decrypt("3232427352382723", "3475", &cdata);
    drawConvertedList(&cdata);
    printf(" ");
    decrypt("33", "8923", &cdata);
    drawConvertedList(&cdata);
    printf(" ");
    decrypt("1752173996578580830630", "3617", &cdata);
    drawConvertedList(&cdata);
    printf(" ");
    decrypt("47", "1205", &cdata);
    drawConvertedList(&cdata);
    printf(" ");
    decrypt("1334324742249840763104115177915406053196992583180688299430", "5620", &cdata);
    drawConvertedList(&cdata);
    printf("\n");

    //Clear
    cryptDataClear(&cdata);
}

int main(int argc, char *argv[]) {
    //test();
    crack();

    return 0;
}