# ångstromCTF 2021 - I'm so Random

2021/04/12に公開

### 問題概要

Aplet's quirky and unique so he made my own PRNG! It's not like the other PRNGs, its absolutely unbreakable!

nc crypto.2021.chall.actf.co 21600

chall.py
import time
import random
import os

class Generator():
DIGITS = 8
def __init__(self, seed):
self.seed = seed
assert(len(str(self.seed)) == self.DIGITS)

def getNum(self):
self.seed = int(str(self.seed**2).rjust(self.DIGITS*2, "0")[self.DIGITS//2:self.DIGITS + self.DIGITS//2])
return self.seed

r1 = Generator(random.randint(10000000, 99999999))
r2 = Generator(random.randint(10000000, 99999999))

query_counter = 0
while True:
query = input("Would you like to get a random output [r], or guess the next random number [g]? ")
if query.lower() not in ["r", "g"]:
print("Invalid input.")
break
else:
if query.lower() == "r" and query_counter < 3:
print(r1.getNum() * r2.getNum())
query_counter += 1;
elif query_counter >= 3 and query.lower() == "r":
print("You don't get more random numbers!")
else:
for i in range(2):
guess = int(input("What is your guess to the next value generated? "))
if guess != r1.getNum() * r2.getNum():
print("Incorrect!")
exit()
with open("flag", "r") as f:
print(fleg)
exit()


### 解説

かなり競プロチックな問題ですが、解くとこんな感じです。

solve.py
from pwn import *

r = remote("crypto.2021.chall.actf.co",  21600)

r.recvuntil(b"Would you like to get a random output [r], or guess the next random number [g]? ")
r.sendline(b"r")
num = int(r.recvline().decode())

def updateVal(x):
return int(str(x ** 2).rjust(16, "0")[4:12])

sml = num // 10**8
candidates = set()
for i in range(sml, 10**8):
if num % i == 0:
j = num // i

for _ in range(2):
r.recvuntil(b"Would you like to get a random output [r], or guess the next random number [g]? ")
r.sendline(b"r")
num = int(r.recvline().decode())

next_candidates = set()
for candidate in candidates:
i, j = candidate
i = updateVal(i)
j = updateVal(j)
if i * j == num:
candidates = next_candidates

print(candidates)
assert(len(candidates) == 1)
i, j = list(candidates)[0]

r.recvuntil(b"Would you like to get a random output [r], or guess the next random number [g]? ")
r.sendline(b"g")
for _ in range(2):
r.recvuntil(b"What is your guess to the next value generated? ")
i = updateVal(i)
j = updateVal(j)