03-the-big-five.py

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

from gmpy2 import is_prime
from Crypto.Util.number import *
from Crypto.Cipher import AES
from math import gcd

def main():
    # M is prime number!
    X = [
        171988490999968958074461906163126253991,
        149759767375550138601832127658924300851,
        21392649857558566532141954695914673807,
        52236160143411890255640980579270361316,
        22081153611165744867415455406756477578
    ]

    # Find A, B, M
    # X[4] - X[3] = A * (X[3] - X[2]) (mod M)
    # X[3] - X[2] = A * (X[2] - X[1]) (mod M)
    # X[2] - X[1] = A * (X[1] - X[0]) (mod M)

    d = [X[i+1] - X[i] for i in range(4)]
    # d[3] = A * d[2] (mod M)
    # d[2] = A * d[1] (mod M)
    # d[1] = A * d[0] (mod M)
    
    # => d[0]*d[2] = d[1]**2
    # => d[1]*d[3] = d[2]**2
    M = gcd(d[0]*d[2] - d[1]**2, d[1]*d[3] - d[2]**2)
    assert is_prime(M) # If not, just factorize it...
    A = d[1] * pow(d[0], -1, M) % M
    B = (X[1] - A * X[0]) % M
    

    assert (A * X[0] + B) % M == X[1]
    assert (A * X[1] + B) % M == X[2]
    assert (A * X[2] + B) % M == X[3]
    assert (A * X[3] + B) % M == X[4]
    key = (A * X[4] + B) % M

    nonce = b'\x0b:\xce<\xb0\xe8@,'
    c =  b'\\\x8f\xfayc\xce\xfc<`\xc7\xe1\x91Jh\x0c6 \x8a\xd8\x0f\xdc^\xa3\xb9\xa1Kv\x96O<\xbcx\x8e\xea\xc3&'

    cipher = AES.new(long_to_bytes(key), AES.MODE_CTR, nonce=nonce)
    flag = cipher.decrypt(c)
    print(flag)
    # kurenaifCTF{Less_numbers_are_better}

if __name__ == '__main__':
    main()

'''
A = 128 bit
B = 128 bit
M = 128 bit prime
S = 128 bit

outputs:
    X0 = (A * S  + B) % M
    X1 = (A * X0 + B) % M
    X2 = (A * X1 + B) % M
    X3 = (A * X2 + B) % M
    X4 = (A * X3 + B) % M
    X5 = (A * X4 + B) % M
'''