RSA 2048 sample

def uoc_chung_lon_nhat(a, b):
    while b:
        a, b = b, a % b
    return a

def nghich_dao_modulo(e, phi):
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y

    _, x, _ = extended_gcd(e, phi)
    return x % phi

def tao_khoa_rsa(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)

    e = 65537
    if uoc_chung_lon_nhat(e, phi) != 1:
        e = 3
        while uoc_chung_lon_nhat(e, phi) != 1:
            e += 2

    d = nghich_dao_modulo(e, phi)

    return (e, n), (d, n)

def ma_hoa(thong_diep, khoa_cong_khai):
    e, n = khoa_cong_khai
    return pow(thong_diep, e, n)

def giai_ma(ban_ma, khoa_bi_mat):
    d, n = khoa_bi_mat
    return pow(ban_ma, d, n)

p = 61
q = 53

print(f"Số nguyên tố p: {p}")
print(f"Số nguyên tố q: {q}")
print()

khoa_cong_khai, khoa_bi_mat = tao_khoa_rsa(p, q)
e, n = khoa_cong_khai
d, _ = khoa_bi_mat

print(f"n = p × q = {n}")
print(f"φ(n) = (p-1)(q-1) = {(p-1)*(q-1)}")
print(f"Khóa công khai (e, n): ({e}, {n})")
print(f"Khóa bí mật (d, n): ({d}, {n})")
print()

thong_diep = 1234
print(f"Thông điệp gốc: {thong_diep}")

ban_ma = ma_hoa(thong_diep, khoa_cong_khai)
print(f"Sau khi mã hóa: {ban_ma}")

thong_diep_giai_ma = giai_ma(ban_ma, khoa_bi_mat)
print(f"Sau khi giải mã: {thong_diep_giai_ma}")
print()

print("✓ Thông điệp gốc == Thông điệp sau giải mã!" if thong_diep == thong_diep_giai_ma else "✗ Lỗi!")