as2634_task4a.py

# To show RSA encryption scheme is not IND-CCA secure

"""
Task 4: IND-CCA security. 
In each of the tasks below, you will have to demonstrate that the the decryption
of a ciphertext and its related but modifed form can lead us to the same plaintext.

Write a program to demonstrate that Naive RSA is insecure with respect to an IND-CCA adversary. The
program will take as input a public key (N; e) and a ciphertext c created by the program written for Task
1. It will then output the modied ciphertext c0 = 2^e . c (mod N). It will then output the element 2^1
(mod N). It will take as input the message m0 found by decrypting c0 using the program written for Task
1. It will finally output the original message m that was encrypted to c.
"""

def print_separators() -> None:
    """
    The function prints the separators on console

    :return: None
    """
    print(20 * '-')


def exponential(base: int, power: int) -> int:
    """
    This is the function to calculate exponential

    :param base: the value to want to raise to a power
    :param power: the value of the power
    :return: the value of the base raised to the given power
    """
    if power == 0:
        return 1
    elif power == 1:
        return base
    elif power < 0:
        return exponential(1 / base, base * (-1))
    elif power % 2 == 0:
        return exponential(base * base, power / 2)
    else:
        return base * exponential(base * base, (power - 1) / 2)


def extended_euclidean_algorithm(a: int, b: int) -> tuple[int, int, int]:
    """
    This is the function to get the greatest common divisor between two numbers and also returns inverses for the numbers

    :param a: the value of the first number
    :param b: the value of the second number
    :return: a tuple containing gcd of two params, multiplicative inverse of the first param and multiplicative inverse
    of the second param respectively
    """
    r1, r = a, b
    s1, s = 1, 0
    t1, t = 0, 1

    # until remainder is not zero this loop continues
    while r != 0:
        q1 = int((r1 // r))
        r1, r = r, (r1 - (q1 * r))
        s1, s = s, (s1 - (q1 * s))
        t1, t = t, (t1 - (q1 * t))
        d = r1
        x = s1
        y = t1
        rr = r
        if rr == 0:
            return d, x, y


def modify_cipher(c: int, e: int, N: int) -> int:
    """
    This function modifies the cipher text using Homomorphism property by multiplying it to another cipher text 2^e
    :param c: initial ciphertext that needs to be modified
    :param e: public key parameter
    :param N: the public parameter N
    :return: the modified ciphertext
    """
    # calculating a new ciphertext with m = 2 and then multiplying it with given ciphertext to generate a new
    # modified cipher text
    return (exponential(2, e) * c) % N


def get_negative_number_representation(neg: int, n: int) -> int:
    """
    This function maps a negative number to find its representation within the set Z/nZ

    :param neg: The negative number to be mapped to Z/nZ
    :param n: The value of n to generate the set Z/nZ
    :return: the representation of the negative number from the set Z/nZ
    """
    neg = abs(neg)

    # if the number is out of the set of Z/nZ we first find its representation within the set
    if neg > (n - 1):
        neg = neg % n

    # we then find the inverse of the negative number which is a positive number and from within the set Z/nZ
    neg = n - neg
    return neg


# taking input the public key paramters N and e
N = int(input(f"Please enter the public parameter N:"))
e = int(input(f"Please enter the encryption exponent e:"))
print_separators()

# taking ciphertext as input
c = int(input(f"Please enter the ciphertext c:"))
print_separators()

# calculating a new ciphertext with m = 2 and then multiplying it with given ciphertext to generate a new
# modified cipher text
c1 = modify_cipher(c, e, N)
print(f"The modified ciphertext c` is = {c1}")

# calculating inverse of the ciphertext generated by message m = 2
gcd, inverse, y = extended_euclidean_algorithm(2, N)
if inverse < 0:
    inverse = get_negative_number_representation(inverse, N)

print(f"The inverse of 2 mod {N} is {inverse}")

# getting the decryption of the modified ciphertext
print("Please decrypt the modified ciphertext c` using your program from Task 1.")
m1 = int(input("Please input the plaintext m` decrypted from c`:"))

# nullifying the effect of the plaintext of the modified cipher to obtain the original plain text to show RSA in not
# IND-CCA secure
m = (m1 * inverse) % N
print(f"The original plaintext message m computed from m` is: {m}")