HarekazeCTF

# divN
>$ cat foo.c
>long long div(long long x) {
>    return x / N;
>}
>$ gcc -DN=$N -c -O2 foo.c
>$ objdump -d foo.o
>
>foo.o:     file format elf64-x86-64
>
>
>Disassembly of section .text:
>
>0000000000000000 
>:
>   0:	48 89 f8             	mov    %rdi,%rax
>   3:	48 ba 01 0d 1a 82 9a 	movabs $0x49ea309a821a0d01,%rdx
>   a:	30 ea 49 
>   d:	48 c1 ff 3f          	sar    $0x3f,%rdi
>  11:	48 f7 ea             	imul   %rdx
>  14:	48 c1 fa 30          	sar    $0x30,%rdx
>  18:	48 89 d0             	mov    %rdx,%rax
>  1b:	48 29 f8             	sub    %rdi,%rax
>  1e:	c3                   	retq   
>$ echo “HarekazeCTF{$N}” > /dev/null
>(Rev, 100 points)

foo.c を N=$N と定義したうえで、最適化してコンパイルした(-O2)もののアセンブリを読み解いて、$Nの値を探る問題。

アセンブラの記法は、%があることから判断してAT&T。つまり、movだったら左から右に移動している。

`mov    %rdi,%rax` で、引数としてわたってきた %rdi が %rax にコピーされる。
`movabs $0x49ea309a821a0d01,%rdx` で、%rdx(データレジスタ)に ‭5326122949484875009‬ が入る。
`sar    $0x3f,%rdi` で、%rdiには最上位1bitが最下位1bitとなり、それ以外はもともとの最上位1bitと同じになる。
`imul   %rdx` で、%raxの値（つまり、引数で渡されたx）と%rdxの値を乗算したものの、上位を%rdxに、下位を%raxに格納する。
`sar    $0x30,%rdx` で、%rdxの上位16bitが下位16bitとなり、上位48bitは最上位のbitと同じになる。
`mov    %rdx,%rax` で、%rdxを%raxにコピーする。
`sub    %rdi,%rax` で、%raxから%rdiを引いた値を%raxに格納する。

‭Nを求めるには、
‭(2**112) // ‭5326122949484875009‬ +1
をする。
（+1がなんで必要か正直分かってない。。）

* 関数の戻り値は rax で戻す。
* 引数はrdi, rsi, rdx, rcx, r8, r9の順でセットされる。（http://inaz2.hatenablog.com/entry/2014/07/04/001851）
* long long型は64bit以上の整数を表現することができる。


# fight

```python
import random
import base64
import key

def xor(msg, key):
    return bytes([ch1^ch2 for ch1, ch2 in zip(msg, key)])

def gcd(x, y):
  while y != 0:
    r = x % y
    x = y
    y = r
  return x

def gen_seed(n):
  seed = 0
  for k in range(1,n):
    if gcd(k,n)==1:
      seed += 1
  return seed

s = 1
for p in b"Enjoy_HarekazeCTF!!":
  s *= p
seed = gen_seed(s)
random.seed(str(seed).rstrip("0"))

flag = key.FLAG
key = bytes([random.randint(0,255) for _ in flag])

enc = xor(flag, key)
print(base64.b64encode(enc).decode('utf-8')) #7XDZk9F4ZI5WpcFOfej3Dbau3yc1kxUgqmRCPMkzgyYFGjsRJF9aMaLHyDU=
```

いろいろ暗号化したものをBASE64エンコードしたら、
7XDZk9F4ZI5WpcFOfej3Dbau3yc1kxUgqmRCPMkzgyYFGjsRJF9aMaLHyDU=
になる。
そのひとつ前で `enc = xor(flag, key)`とあり、暗号化されたビット配列は、flagとkeyの排他的論理和であることが分かる。
そのため、既知である暗号化されたbit配列と、keyの排他的論理和を取れば、flagが分かる。

与えられたソースコードを少しいじって、keyを出そうと試みた。

```python

import random
import base64

def xor(msg, key):
    return bytes([ch1^ch2 for ch1, ch2 in zip(msg, key)])

def gcd(x, y):
  while y != 0:
    r = x % y
    x = y
    y = r
  return x

def gen_seed(n):
  seed = 0
  for k in range(1,n):
    if gcd(k,n)==1:
      seed += 1
  return seed

s = 1
for p in b"Enjoy_HarekazeCTF!!":
  s *= p
# print(s)
seed = gen_seed(s)
random.seed(str(seed).rstrip("0"))
print(seed)
key = bytes([random.randint(0,255) for _ in range(45)])

print(key)
```

しかし、gen_seedに渡す引数が
4529255040439033800342855653030016000
と膨大であるため、for文を素直に回していたら間に合わない。

gen_seed でやっていることは、
1~4529255040439033800342855653030015999
のうち、
4529255040439033800342855653030016000
との最大公約数が1である数の個数を返している。

4529255040439033800342855653030016000
を素因数分解すると以下のよう

```python
import sympy

print(sympy.factorint(4529255040439033800342855653030016000))
```
```
{2: 10, 3: 8, 5: 3, 7: 2, 11: 5, 19: 2, 23: 1, 37: 1, 53: 1, 61: 1, 67: 1, 97: 2, 101: 2, 107: 1}
```

包除原理を用いて、
4529255040439033800342855653030016000
と互いに素であるものの数を数える。
https://ja.wikipedia.org/wiki/%E5%8C%85%E9%99%A4%E5%8E%9F%E7%90%86

```python
import itertools
import functools
import operator
import random
import base64

base64_ans = "7XDZk9F4ZI5WpcFOfej3Dbau3yc1kxUgqmRCPMkzgyYFGjsRJF9aMaLHyDU="
# print(base64.b64decode(base64_ans))

# 最後のBASE64化された文字列のビット配列
enc_flag_bit_array = ""
for tmp in base64.b64decode(base64_ans):
    enc_flag_bit_array += bin(tmp)[2:].zfill(8)

# 最終的な暗号化されたフラグのビット文字列
# print(enc_flag)

import sympy

# Sはランダム関数の種を生成する際に使う数
S = 4529255040439033800342855653030016000

factors = sympy.factorint(S)

# 包除原理を用いて解く
prime_factors_list = [p for p, _ in factors.items()]
# print(prime_factors_list)

# for tup in itertools.combinations(prime_factors_list,2):
#     print(tup)

# Sと互いに素にならない数の個数
not_tagainiso = 0

for i in range(1, len(prime_factors_list) + 1):
    for tup in itertools.combinations(prime_factors_list, i):
        if i & 1:
            not_tagainiso += S // functools.reduce(operator.mul, tup)
        else:
            not_tagainiso -= S // functools.reduce(operator.mul, tup)
seed = S - not_tagainiso
random.seed(str(seed).rstrip("0"))
key = bytes([random.randint(0, 255) for _ in range(45)])

key_bit_array = ""
for i in key:
    key_bit_array += bin(i)[2:].zfill(8)

ans_bit_array = ""
for e, k in zip(enc_flag_bit_array, key_bit_array):
    ans_bit_array += str(int(e) ^ int(k))

ans = ""
for j in range(0, len(enc_flag_bit_array), 8):
    ans += chr(int(ans_bit_array[j:j + 8], 2))

print(ans)
```

HarekazeCTF{3ul3rrrrrrrrr_t0000000t1nt!!!!!}