[crypto] reiwa_rot13 (SECCON CTF 13 Quals) writeup

---

- Source: SECCON CTF 13 Quals
- Author: [kurenaif](https://x.com/fwarashi)

---

ソースコードと出力結果が与えられる。
```py
from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))
```

```
n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"
```

10文字のランダムな文字列`key`とそれを13ずつずらした文字列`rot13_key`をそれぞれRSAで暗号化した値`c1`,`c2`が与えられている。AESで暗号化されたflagの値が分かっているので、`key`の値が分かればflagは復元できる。

`key`と`rot13_key`の差は各文字について+13か-13のいずれかだということが分かっているので、Franklin-Reiter's Related Message Attackが有効。

Franklin-Reiter's Related Message Attackは2つの暗号文があってそれぞれ原文の差が既知の時に原文を復元できるという攻撃。この問題では`key`と`rot13_key`の関係は線形なので適用できる。

10文字全てについて+13か-13の総当たりをしても2^10=1024通りで済む。総当たりで`key`と`rot13_key`の差分を求めるコードはこんな感じ。
```py
for i in range(1<<10):
  diff = 0
  for j in range(10):
    mask = 1<<j
    if i & mask:
      diff += 13*(256**j)
    else:
      diff -= 13*(256**j)
```

`key`を求めることができれば、あとはflagをAESで復号するだけ。[Flanklin-Reiter's Related Message Attackのコード](https://zenn.dev/anko/articles/ctf-crypto-rsa#%E4%B8%8A%E4%BD%8D%E3%83%93%E3%83%83%E3%83%88%E3%81%8C%E5%85%B1%E9%80%9A%E3%81%99%E3%82%8B%E4%BA%8C%E3%81%A4%E3%81%AE%E5%B9%B3%E6%96%87%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B%E6%9A%97%E5%8F%B7%E6%96%87%E3%82%92%E7%9F%A5%E3%82%89%E3%82%8C%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84-(franklin-reiter-related-message-attack))を拝借してsolverを実装する。
```py
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import *


n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"


# ref: https://zenn.dev/anko/articles/ctf-crypto-rsa
def franklinReiter(n, e, r, c1, c2):
  R.<x> = Zmod(n)[]
  f1 = x^e - c1
  f2 = (x + r)^e - c2
  return - polygcd(f1, f2).coefficients()[0]

def polygcd(a, b):
  if(b == 0):
    return a.monic()
  else:
    return polygcd(b, a % b)


for i in range(1<<10):
  print("progress:", i)
  diff = 0
  for j in range(10):
    mask = 1<<j
    if i & mask:
      diff += 13*(256**j)
    else:
      diff -= 13*(256**j)

  key = int(franklinReiter(n, e, diff, c1, c2))
  hash_key = hashlib.sha256(long_to_bytes(key)).digest()
  flag = AES.new(hash_key, AES.MODE_ECB).decrypt(encyprted_flag)
  if flag.startswith(b'SECCON{'):
    print(flag)
    break
```

これをsagemathに投げるとflagが得られた。
`SECCON{Vim_has_a_command_to_do_rot13._g?_is_possible_to_do_so!!}`