Source: SECCON CTF 13 Quals
Author: kurenaif

ソースコードと出力結果が与えられる。

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の差分を求めるコードはこんな感じ。

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のコードを拝借してsolverを実装する。

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!!}