'''
# Das Ziel des Programms: Compromising a congruence PRNG
# Date: 30.Mai 2020
# Die Sprache des Programms: Python
'''
import math
import gmpy2

# Step 1: Get the random numbers
f_ptr = open('C:\\path\\to\\file.txt')    # open the file
                                          # where random number sequence is stored
random_list = f_ptr.readlines()     # store the numbers in random_list

random_list = [int(ran_seq) for ran_seq in random_list] # to convert the numbers from
                                                        # string to integer format

print("The given random number sequence is:")
print(random_list)
f_ptr.close()   # close the file since we stored the numbers in the list from the file

# Step 2: Analyze those numbers and obtain a, b, m, and seed-value
# Step 2.1: Obtain m
'''
according to the formula for random numbers generated by LCG
    r1 = a*S + b mod m
    r2 = a*r1 + b mod m
    r3 = a*r2 + b mod m .... and so on
    To break LCG, we must find m first.
    The following method is based on this answer posted on Security StackExchange
    Link: https://security.stackexchange.com/a/4306/235626
    Here, we calculate Tn+1 = Sn+1 - Sn = (a.Sn - b) - (a.Sn-1 - b) = a.Sn - a.Sn-1 = a.Tn mod m
    Similarily, Tn+2 = a^2 .Tn mod m and Tn+3 = a^3 .Tn mod m
    Therefore, Tn+2.Tn - Tn+1.Tn+1 = 0 mod m. The absolute value of this expression will be a random multiple of m
    When the GCD is calculated of two random multiples of m, the GCD will be m with the probability of (6/pi^2) = 0.61
    If we calculate GCD of more numbers, the probability will get very near to 1.
'''
# Step 2.1.1: Compute Tn, Tn+1,...Tn+6
t_n = []    # list of Tn values
i = 0
temp = 4    # just a temporary variable
for i in range(0,6):
    tn = random_list[temp] - random_list[temp+1]
    t_n.append(tn)
    temp = temp + 1

# Step 2.1.2: Compute Un, Un+1...Un+3
i = 0
temp = 0    # just a temporary variable
u_n = []    # list of Un values
for i in range(0,4):
    un = abs(t_n[temp+2]*t_n[temp] - t_n[temp+1]*t_n[temp+1])
    u_n.append(un)
    temp = temp + 1

# Step 2.1.3: Obtain m using Tn and Un values
i = 0
m = 0
for i in range(0,4):
    m = math.gcd(m, u_n[i])

print("For the given random sequence, m found out to be: ", m)

# Step 2.2: Obtain a and b
'''
The logic used here was obtained from a GitHub code
Link: https://github.com/EnrisNVT/LCG-breaking-example/blob/master/example.py
To find a and b we use the following equations:
a = ( (s3-s4) * inverse_modulo( (s2-s3), m) ) mod m
b = ( s4 - a*s3 ) mod m
'''
mod_inv_a = gmpy2.invert( (random_list[1]-random_list[2]), m)
a = ( (random_list[2]-random_list[3]) * mod_inv_a ) % m
b = ( random_list[3] - a*random_list[2] ) % m
print("Values of a:", a, "and b:", b)

# TODO: Step 2.3: Obtain the seed value s0

# Step 3: Predict the next value
next_random_number = ( a*random_list[-1] + b ) % m  # take the last number
                                                    # from the sequence and apply the formula
                                                    # Sn+1 = (a*Sn + b) mod m
print("The next random number in the sequence would be: ", next_random_number)
