TSG CTF 2020 Beginner's Crypto

問題

配布ファイルは以下の通り。

assert(len(open('flag.txt', 'rb').read()) <= 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000).endswith('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'))

フラグを整数値に変換して左に10000ビットシフトした値の末尾175桁の値が与えられる。すなわち

$$c=\text{flag}\cdot 2^{10000}mod{10}^{175}$$

からflagを復元するのが本問の趣旨である。

解法

$F_{{10}^{175}}$での

$2^{10000}$の逆元を取りたくなるが、これは互いに素でないため存在しない。

正しくは

$$c=\text{flag}\cdot 2^{10000}mod{5}^{175}$$

を考えて、オイラーの定理より

$$\begin{array}{rl}(2^{10000}{)}^{-1}mod{5}^{175}& =(2^{10000}{)}^{\phi (5^{175})-1}\\ & =(2^{10000}{)}^{5^{175}-5^{174}-1}\end{array}$$

を計算して

$$\text{flag}=c\cdot (2^{10000}{)}^{-1}mod{5}^{175}$$

よりflagを得る。

${256}^{50}<5^{175}$であるためこれが正しいフラグである。

ソルバ

c = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576
mod = 5 ** 175
phi = 5 ** 175 - 5 ** 174
inv = pow(pow(2, 10000, mod), phi - 1, mod)
print(((c * inv) % mod).to_bytes(50, byteorder='big'))

答えはTSGCTF{0K4y_Y0U_are_r3aDy_t0_Go_aNd_dO_M0r3_CryPt}である。

別解1 (by @naan112358)

$$c=\text{flag}\cdot 2^{10000}mod{5}^{175}$$
とするところまでは同じ。

$$2x=\{\begin{array}{l}2x(2x<M)\\ 2x-M(2x\ge M)\end{array}modM$$
において、上なら偶数で下なら奇数であることを利用すると、

def divide_by_two(x):
    if x % 2 == 0:
        return x // 2
    else:
        return (x + mod) // 2

のようにして2で割る操作を実現できる。
これを10000回繰り返せばflagを得られる。

ソルバ

mod = 5 ** 175
c = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576 % mod

def divide_by_two(x):
    if x % 2 == 0:
        return x // 2
    else:
        return (x + mod) // 2

for i in range(10000):
    c = divide_by_two(c)

print(c.to_bytes(50, byteorder='big'))

別解2 (by @satos___jp)

$$C=\text{flag}\cdot 2^{10000}$$

とおく (modが無いことに注意)。

いま

$C$ の末尾175桁

$c$ がわかっているので、

$$C=c_0\cdot {10}^{175}+c$$

とおける。

ここで、

$C$ を2進数表記したときに末尾10000桁が0になるような

$c_0$ を求める。

いま、

$c_0$ を

$c_0^{\prime }=c_0+2^x$ に置き換えて得られる

$C^{\prime }$ について考えてみる。このとき

$$\begin{array}{rl}{C}^{\prime }& =c_0^{\prime }\cdot {10}^{175}+c\\ & =(c_0+2^x)\cdot {10}^{175}+c\\ & =c_0\cdot {10}^{175}+c+2^x\cdot {10}^{175}\\ & =C+5^{175}\cdot 2^{x+175}\end{array}$$

より、

$C$ を2進数で表記したときの末尾

$x+175$ bitは変化しない。

よって、

$c_0$ の値を下のビットから定めることによって、末尾10000bitが0であるような

$C$ を求めることができる。

flagは

$C$ を右に10000bitシフトすると得られる。

ソルバ

c = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576
c0 = 0
bit = 1
mask = 1 << 175
while '1' in bin(c0 * 10 ** 175 + c)[-10000:]:
  if (c0 * 10 ** 175 + c) & mask != 0:
    c0 += bit
  bit <<= 1
  mask <<= 1
C = c0 * 10 ** 175 + c
flag = (C >> 10000).to_bytes(50, byteorder='big')
print(flag)