ångstromCTF 2021 - Circle of Trust

問題概要

Clam created a 1337 secret sharing scheme for his 1337 trio of friends. Can you crack it?

output source

gen.py

import random
import secrets
import math
from decimal import Decimal, getcontext
from Crypto.Cipher import AES

BOUND = 2 ** 128
MULT = 10 ** 10

getcontext().prec = 50

def nums(a):
    b = Decimal(random.randint(-a * MULT, a * MULT)) / MULT
    c = (a ** 2 - b ** 2).sqrt()
    if random.randrange(2):
        c *= -1
    return (b, c)


with open("flag", "r") as f:
    flag = f.read().strip().encode("utf8")

diff = len(flag) % 16
if diff:
    flag += b"\x00" * (16 - diff)

keynum = secrets.randbits(128)
ivnum = secrets.randbits(128)

key = int.to_bytes(keynum, 16, "big")
iv = int.to_bytes(ivnum, 16, "big")

x = Decimal(random.randint(1, BOUND * MULT)) / MULT
for _ in range(3):
    (a, b) = nums(x)
    print(f"({keynum + a}, {ivnum + b})")

cipher = AES.new(key, AES.MODE_CBC, iv=iv)
enc = cipher.encrypt(flag)
print(enc.hex())

三平方を使った面白めの問題です。

解説

ランダムに生成されたxという変数から、a,bが$a^2+b^2 = x^2$を満たすように$3$ペア生成されます。ただ、このa,bにそれぞれkey,ivがノイズとして追加され、そもそも知りたい情報はkey,ivの方です。

ここから思いっきり数式を弄るパートです。

1. 与えられたペアの数値（a+key,b+iv）を$x, y$とします。$x = a + key$、$y = b + iv$で、$x, y$は既知です。
2. $x,y$は3ペア与えられるので、$x_i, y_i$という表記で区別します。同様に$a_i, b_i$も使用します。
3. $a, b$について$a_1^2 + b_1^2 = a_2^2 + b_2^2 = a_3^2 + b_3^2$が成立します。
4. 3に$a=x-key, b=y-iv$を代入すると、以下のような式になります。

$$\begin{aligned} a_1^2 + b_1^2 &= a_2^2 + b_2^2\\ (x_1 - key)^2 + (y_1 - iv)^2 &= (x_2 - key)^2 + (y_2 - iv)^2\\ 2(x_1 - x_2) \times {\rm key} + 2(y_1 - y_2) \times {\rm iv} &= (x_1^2 - x_2^2) + (y_1^2 - y_2^2) \end{aligned}$$

5. このように変数key, ivを用いた1次方程式になりました。ところで$(x_2, y_2), (x_3, y_3)$を用いてもう1つ式を作ることが出来ます。これらを連立させて解くことで、keyとivの値を求めることが出来ます。

key、ivを求めることでAESの復号が出来ます。

solve.py

from decimal import *
from Crypto.Util.number import *
from Crypto.Cipher import AES

getcontext().prec = 128
MULT = 10 ** 10
bc = [
    (Decimal("45702021340126875800050711292004769456.2582161398"), Decimal("310206344424042763368205389299416142157.00357571144")),
    (Decimal("55221733168602409780894163074078708423.359152279"), Decimal("347884965613808962474866448418347671739.70270575362")),
    (Decimal("14782966793385517905459300160069667177.5906950984"), Decimal("340240003941651543345074540559426291101.69490484699")),
]
c = bytes.fromhex("838371cd89ad72662eea41f79cb481c9bb5d6fa33a6808ce954441a2990261decadf3c62221d4df514841e18c0b47a76")

equations = [
        (2 * (bc[0][0] - bc[1][0]), 2 * (bc[0][1] - bc[1][1]), (bc[0][0] ** 2 - bc[1][0] ** 2) + (bc[0][1] ** 2 - bc[1][1] ** 2)),
        (2 * (bc[1][0] - bc[2][0]), 2 * (bc[1][1] - bc[2][1]), (bc[1][0] ** 2 - bc[2][0] ** 2) + (bc[1][1] ** 2 - bc[2][1] ** 2))
    ]

xn = (equations[0][2] * equations[1][1] - equations[0][1] * equations[1][2])
xd = (equations[0][0] * equations[1][1] - equations[0][1] * equations[1][0])
yn = (equations[0][2] * equations[1][0] - equations[0][0] * equations[1][2])
yd = (equations[0][1] * equations[1][0] - equations[0][0] * equations[1][1])
print("xn:", xn)
print("xd:", xd)
print("mod:", xn % xd)
print("yn:", yn)
print("yd:", yd)
print("mod:", yn % yd)

x = int(xn / xd) + 1
y = int(yn / yd)

key = int.to_bytes(x, 16, "big")
iv = int.to_bytes(y, 16, "big")
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
dec = cipher.decrypt(c)
print(dec)