kurenaif Valentine Problems - the_big_five

kurenaifさんがCryptoの問題をプレゼントしてくれました。ちょっと忙しかったので今から解きます。一応既に公式writeupが出ているはずですので、そちらを見た方が分かりやすい説も。

問題概要

problem.py

import os
import math
import binascii
import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
from flag import *

class MyLCG:
    def __init__(self, S):
        self.A = int(binascii.hexlify(os.urandom(16)), 16)
        self.B = int(binascii.hexlify(os.urandom(16)), 16)
        self.M = getPrime(16*8)

        self.x = (S % self.M)
    def next(self):
        self.x = ((self.A * self.x) + self.B) % self.M
        return self.x

r = MyLCG(int(binascii.hexlify(os.urandom(16)), 16))
# print("A = " + str(r.A))
# print("B = " + str(r.B))
# print("M = " + str(r.M))
print("# M is prime number!")

cnt = 5
for i in range(cnt):
    print("X[{}] = {}".format(i,r.next()))

print("X[{}] = ?".format(cnt))

key = r.next()
cipher = AES.new(long_to_bytes(key), AES.MODE_CTR)
nonce = cipher.nonce
ct_bytes = cipher.encrypt(flag)
print("nonce = ", nonce)
print("ct_bytes = ", ct_bytes)

# decrypt
# cipher_dec = AES.new(long_to_bytes(key), AES.MODE_CTR, nonce=nonce)
# print(cipher_dec.decrypt(ct_bytes))

乱数生成の手法である線形合同法の結果をいくつか与えるので、推測してください。というやつです。

解説

流石に自分も線形合同法が乱数的にヤバイのは知っていたのですが、具体的にどう推測可能かは知らなかったです。ということでググって記事を拾います。今回事前に5つも数字をくれるので、結構気楽に$a,b,m$が求まります。

solve.py

from math import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from functools import reduce
# M is prime number!
X = [171988490999968958074461906163126253991,
  149759767375550138601832127658924300851,
  21392649857558566532141954695914673807,
  52236160143411890255640980579270361316,
  22081153611165744867415455406756477578
]
nonce =  b'\x0b:\xce<\xb0\xe8@,'
ct_bytes =  b'\\\x8f\xfayc\xce\xfc<`\xc7\xe1\x91Jh\x0c6 \x8a\xd8\x0f\xdc^\xa3\xb9\xa1Kv\x96O<\xbcx\x8e\xea\xc3&'

diffs = [X_1 - X_0 for X_0, X_1 in zip(X, X[1:])]
multiples_of_M = [T_2 * T_0 - T_1 ** 2 for T_0, T_1, T_2 in zip(diffs, diffs[1:], diffs[2:])]
m = reduce(gcd, multiples_of_M)
a = diffs[1] * inverse(diffs[0], m)
b = (X[1] - a * X[0]) % m

X.append((a * X[-1] + b) % m)

cipher = AES.new(long_to_bytes(X[-1]), AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(ct_bytes))