📝

# kurenaif Valentine Problems - the_big_five

2021/04/08に公開

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))


## 解説

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))
`

ログインするとコメントできます