Skip to content

Instantly share code, notes, and snippets.

@samueltangz
Created February 13, 2021 13:37
Show Gist options
  • Save samueltangz/2b961660fb1d3b60e013f40ba1ef5000 to your computer and use it in GitHub Desktop.
Save samueltangz/2b961660fb1d3b60e013f40ba1ef5000 to your computer and use it in GitHub Desktop.
#!/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
'''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment