🚀 RSA: O Algoritmo que Revolucionou a Criptografia

Imagina que você quer mandar uma carta supersecreta para alguém. Se você só colocar num envelope comum, qualquer pessoa no caminho pode abrir e ler. O RSA é como se fosse um cadeado especial: só a pessoa que vai receber tem a chave certa para abrir.

💡 O truque do RSA

Ele usa duas chaves diferentes:

Uma pública (qualquer um pode ter, como o cadeado que você entrega para todo mundo).

Uma privada (só você tem, como a chave que abre o cadeado).

🌍 Onde isso aparece no dia a dia

Quando você acessa um site com “https://”, o RSA (ou outros algoritmos parecidos) está lá garantindo que ninguém espie sua senha ou número do cartão.

Em aplicativos de mensagem, ele ajuda a manter as conversas privadas.

Em bancos online, protege transações para que só você e o banco saibam o que está acontecendo.

👉 Em resumo: o RSA existe porque precisamos de uma forma segura e confiável de trocar informações na internet, sem que man-in-the-middle consigam bisbilhotar.

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

// Algoritmo de Euclides Estendido
int euc_ext(int valor, int denominador, int *x, int *y) {
    if (denominador == 0) {
        *x = 1;
        *y = 0;
        return valor;
    }

    int x1, y1;
    int g = euc_ext(denominador, valor % denominador, &x1, &y1);

    *x = y1;
    *y = x1 - (valor / denominador) * y1;

    return g;
}

// Inverso modular usando Euclides Estendido
int mod_inv(int valor, int modulo) {
    int x, y;
    int g = euc_ext(valor, modulo, &x, &y);

    if (g != 1) {
        return 0; // não existe inverso
    }

    int res = x % modulo;
    if (res < 0) {
        res += modulo;
    }

    return res;
}

// Exponenciação modular rápida
int mod_exp(int base, int exp, int mod) {
    int result = 1 % mod;
    int b = base % mod;

    while (exp > 0) {
        if (exp & 1) {
            result = (result * b) % mod;
        }
        b = (b * b) % mod;
        exp >>= 1;
    }

    return result;
}

// Máximo divisor comum (para verificar coprimalidade)
int max_div(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// Lista de primos pequenos
int primos[] = {
     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
  };

// Escolhe um primo aleatório da lista
int random_primo(void) {
    size_t total = sizeof(primos) / sizeof(primos[0]);
    return primos[rand() % total];
}

int main(void) {
    srand((unsigned) time(NULL));

    // RECEPTOR GERA KEYS
    int p = random_primo();
    int q;
    do {
        q = random_primo();
    } while (q == p);

    int n = p * q;
    int phi = (p - 1) * (q - 1);

    int e = 3;
    while (e < phi && max_div(e, phi) != 1) {
        e += 2;
    }

    int d = mod_inv(e, phi);

    printf("\nPublic key  (e, n): (%-7d, %d)\n", e, n);
    printf("Private key (d, n): (%-7d, %d)\n\n", d, n);

    // EMISSOR CRIPTOGRAFA A MENSAGEM
    char *mensagem = "Internet Revolution";

    size_t len = 0;
    while (mensagem[len] != '\0') {
        len++;
    }

    int *cifrado = malloc(len * sizeof(*cifrado));
    for (size_t i = 0; i < len; ++i) {
        cifrado[i] = mod_exp((int) mensagem[i], e, n);
    }

    // LOG DEMONSTRATIVO
    printf("Mensagem original: \"%s\"\n\n", mensagem);
    printf("Cifrado:\n");
    for (size_t i = 0; i < len; ++i) {
        printf("%d ", cifrado[i]);
    }
    printf("\n\n");

    // RECEPTOR DECIFRA
    int *decifrado = malloc(len * sizeof(*decifrado));
    for (size_t i = 0; i < len; ++i) {
        decifrado[i] = mod_exp(cifrado[i], d, n);
    }

    // LOG DEMONSTRATIVO
    printf("Decifrado: \"");
    for (size_t i = 0; i < len; ++i) {
        putchar(decifrado[i]);
    }
    printf("\"\n");

    free(cifrado);
    free(decifrado);

    return 0;
}

Quase todas as requisições na internet usam o algoritmo RSA.
As pessoas deveriam falar mais sobre ele.