# 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}\cdot2^{10000}\bmod10^{175}
$$

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

## 解法

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

正しくは

$$
c=\text{flag}\cdot2^{10000}\bmod5^{175}
$$

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

$$
\begin{aligned}
(2^{10000})^{-1}\bmod5^{175}&=(2^{10000})^{\varphi(5^{175})-1}\\&=(2^{10000})^{5^{175}-5^{174}-1}
\end{aligned}
$$

を計算して

$$
\text{flag}=c\cdot(2^{10000})^{-1}\bmod5^{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](https://twitter.com/naan112358))
$$
c=\text{flag}\cdot2^{10000}\bmod5^{175}
$$
とするところまでは同じ。
$$
2x=\begin{cases}2x\qquad\ \ (2x<M)\\2x-M\ (2x\geq M)\end{cases}\bmod M
$$
において、上なら偶数で下なら奇数であることを利用すると、

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](https://twitter.com/satos___jp))

$$
C=\text{flag}\cdot2^{10000}
$$

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

いま $C$ の末尾175桁 $c$ がわかっているので、

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

とおける。

ここで、$C$ を2進数表記したときに末尾10000桁が0になるような $c_0$ を求める。

いま、$c_0$ を $c'_0=c_0+2^x$ に置き換えて得られる $C'$ について考えてみる。このとき

$$
\begin{aligned}
C'&=c'_{0}\cdot10^{175}+c\\&=\left(c_{0}+2^{x}\right)\cdot10^{175}+c\\&=c_{0}\cdot10^{175}+c+2^{x}\cdot10^{175}\\&=C+5^{175}\cdot2^{x+175}
\end{aligned}
$$

より、$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)