#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
===============================================================================
PHM Tech & PHM Open Source · Prof. Paulo Henrique Maciel
Módulo 03 (Segurança): Criptografia Assimétrica de Chave Pública (Algoritmo RSA)
===============================================================================

OBJETIVO PEDAGÓGICO:
Demonstrar passo a passo a matemática fascinante da Criptografia de Chave Pública
(Algoritmo RSA de Rivest, Shamir e Adleman), baseada na dificuldade de fatoração
de números primos grandes e na Aritmética Modular de Euler.

ETAPAS DA CRIPTOGRAFIA RSA:
1. Escolha de dois números primos distintos (p e q).
2. Cálculo do módulo RSA (n = p * q) e da função Totiente de Euler: phi(n) = (p-1)*(q-1).
3. Escolha do expoente público (e) tal que mdc(e, phi(n)) == 1.
4. Cálculo do expoente privado (d) como o inverso multiplicativo modular: (d * e) % phi(n) == 1.
5. Cifragem da mensagem M com a Chave Pública (e, n): C = (M^e) mod n.
6. Decifragem do criptograma C com a Chave Privada (d, n): M = (C^d) mod n.

COMO EXECUTAR:
  Windows / Linux / macOS: python 03_algoritmo_rsa_chave_publica.py
===============================================================================
"""

import math

def mdc(a, b):
    """Calcula o Máximo Divisor Comum (Algoritmo de Euclides)."""
    while b:
        a, b = b, a % b
    return a

def inverso_modular(e, phi):
    """Calcula o inverso multiplicativo modular de e mod phi (Algoritmo Estendido de Euclides)."""
    d_ant, d = 0, 1
    r_ant, r = phi, e
    while r != 0:
        quociente = r_ant // r
        r_ant, r = r, r_ant - quociente * r
        d_ant, d = d, d_ant - quociente * d
    if d_ant < 0:
        d_ant += phi
    return d_ant

def cifrar(mensagem_texto, e, n):
    """Cifra uma string de texto caractere a caractere em inteiros usando a Chave Pública."""
    return [pow(ord(char), e, n) for char in mensagem_texto]

def decifrar(criptograma, d, n):
    """Decifra a lista de inteiros de volta para texto usando a Chave Privada."""
    return "".join(chr(pow(num, d, n)) for num in criptograma)

def main():
    print("=" * 65)
    print("  MÓDULO 03: SIMULADOR DIDÁTICO DO ALGORITMO RSA (CHAVE PÚBLICA)")
    print("  Prof. Paulo Henrique Maciel · PHM Tech Open Source")
    print("=" * 65)

    # [1] Seleção didática de números primos (em produção usam-se primos de 2048+ bits)
    p = 61
    q = 53
    print(f"\n[PASSO 1] Números Primos Escolhidos: p = {p}, q = {q}")

    # [2] Cálculo de n e phi(n)
    n = p * q
    phi = (p - 1) * (q - 1)
    print(f"[PASSO 2] Módulo RSA (n = p * q): {n}")
    print(f"          Função Totiente de Euler: phi(n) = ({p}-1)*({q}-1) = {phi}")

    # [3] Escolha do expoente público 'e'
    e = 17
    while mdc(e, phi) != 1:
        e += 2
    print(f"[PASSO 3] Expoente Público (e): {e} (Coprimo com {phi})")

    # [4] Cálculo da chave privada 'd'
    d = inverso_modular(e, phi)
    print(f"[PASSO 4] Expoente Privado (d): {d} (Inverso Modular)")

    print("\n" + "-" * 65)
    print(f"  🔑 CHAVE PÚBLICA (Distribuível):  (e = {e}, n = {n})")
    print(f"  🔒 CHAVE PRIVADA (Segredo Total): (d = {d}, n = {n})")
    print("-" * 65)

    # [5] Demonstração de Cifragem
    mensagem_original = "PHM TECH OPEN SOURCE 2026"
    print(f"\n[5] Mensagem Original em Texto Claro: \"{mensagem_original}\"")

    cifrado = cifrar(mensagem_original, e, n)
    print(f"\n[6] Criptograma Gerado (C = M^{e} mod {n}):")
    print(f"    {cifrado}")

    # [6] Demonstração de Decifragem
    mensagem_recuperada = decifrar(cifrado, d, n)
    print(f"\n[7] Decifragem com Chave Privada (M = C^{d} mod {n}):")
    print(f"    Recuperado: \"{mensagem_recuperada}\"")

    assert mensagem_original == mensagem_recuperada
    print("\n✅ VALIDAÇÃO: Mensagem recuperada com 100% de exatidão e integridade!")
    print("=" * 65)

if __name__ == "__main__":
    main()