break_encryption.py

"""
Project : Travail Pratique RSA
Authors : Gawen ACKERMANN, Florian BURGENER, Quentin FASLER, Dario GENGA
Date : 2021-2022
"""
import math


def get_bezout_coefficients(a, b):
    """Find the Bézout coefficients for the numbers a and b.

    Args:
        a (int): The number a
        b (int): The number b.

    Returns:
        tuple: The Bézout coefficients.
    """
    r = [a, b]
    x = [1, 0]
    y = [0, 1]
    q = [0, 0]
    i = 1

    while r[i] > 0:
        i += 1

        r.append(r[i - 2] % r[i - 1])
        q.append(int(r[i - 2] / r[i - 1]))

        if r[i] > 0:
            x.append(x[i - 2] - q[i] * x[i - 1])
            y.append(y[i - 2] - q[i] * y[i - 1])

    return x[-1], y[-1]


def modular_inverse(a, n):
    """Calculates the modular inverse of a number a modulo n.

    Args:
        a (int): The number to be reversed.
        n (int): The modulo.

    Returns:
        int: The inverted number.
    """
    coefficients = get_bezout_coefficients(a, n)

    if a * coefficients[0] % n == 1:
        return coefficients[0] % n
    return None


def modular_pow(base, exponent, modulus):
    """Computes the modular exponentiation.

    Args:
        base (int): Power base.
        exponent (int): Power exponent.
        modulus (int): The modulos.

    Returns:
        int: The result of the exponentiation.
    """
    if modulus == 1:
        return 0

    result = 1
    base %= modulus

    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus

        exponent = exponent >> 1
        base = (base * base) % modulus

    return result


def break_encryption(n):
    """Breaks RSA encryption using the brute force technique.

    Args:
        n (int): The component of the public key which is the product of p and q.

    Returns:
        tuple: The prime numbers p and q.
    """
    range_low = 3
    range_high = int(math.ceil(math.sqrt(n)))

    for x in [2] + list(range(range_low, range_high, 2)):
        if n % x == 0:
            return (x, n // x)

    return None


def main():
    e = 5249
    n = 1653973759
    encrypted_data = [1511395078, 260436590, 1630654276, 1190458520, 790492067, 515550941, 297140366, 755589582, 647075331, 1191707844, 901889430, 660956124, 1500654109, 984322720, 1275630738, 1244853107, 1445928913, 1312523810, 265093060, 933013993, 1375592761, 195866064, 534502441, 928270408, 166404031, 621272622, 1304987439, 905393335, 55120151, 772595721, 506609577, 1172751778, 162439707, 233959833, 1468937795, 1358701120, 901889430, 495995733, 1524090698, 1043509086, 934992314, 1545639379, 1061595897, 1348452679, 1135067876, 905393335, 621272622, 55120151, 233959833, 1220119699, 708711266, 517797467, 195866064, 1579814353, 412378626, 498875436, 445485200, 7656659]

    p, q = break_encryption(n)

    # Calculation of the decryption key.
    d = modular_inverse(e, (p - 1) * (q - 1))
    decrypted_data = []

    for x in encrypted_data:
        decrypted_data.append(modular_pow(x, d, n))

    decoded_data = ""

    for x in decrypted_data:
        decoded_data += x.to_bytes((x.bit_length() + 7) // 8, "little").decode("utf-8")

    print(decoded_data)


if __name__ == "__main__":
    main()