Cryptoverse CTF 2022 Writeup

この大会は2022/10/22 7:00(JST)~2022/10/23 13:00(JST)に開催されました。
今回もチームで参戦。結果は5083点で349チーム中20位でした。
自分で解けた問題をWriteupとして書いておきます。

Discord (Misc)

Discordに入り、#generalチャネルのトピックを見ると、フラグが書いてあった。

cvctf{let_the_grind_begin!}

Welcome (Misc)

問題にフラグが書いてあった。

cvctf{welcome_to_cvctf!}

Warmup 1 (Crypto)

CyberChefで「From Base64」→「ROT13」の順にデコードする。

cvctf{caesar_64_ftw}

Warmup 2 (Crypto)

Cyberchefで「Vigenere Decode」でKeyにdeterminationを指定して、復号する。

cvctf{vigenere_is_too_guessy_without_the_key?}

Warmup 3 (Crypto)

CyberChefで「From Morse Code」でデコードする。

CVCTFM0R53ISN0T50FUN
cvctf{m0r53isn0t50fun}

Substitution (Crypto)

quipqiupで復号する。

Capture the Flag is a special kind of information security competitions. There are three common types, Jeopardy, Attack Defence and mixed. If you have figured out the above message, here is your flag, please add curly brackets before submission: cvctfaverysimplesubstitution
cvctf{averysimplesubstitution}

Baby Reverse (Reverse)

$ strings chall | grep cvctf
cvctf{7h15_15_4_f4k3_fl4g}
cvctf{r3v3r53_15_4w350m3}
cvctf{r3v3r53_15_4w350m3}

RSA 1 (Crypto)

factordbでnを素因数分解する。

n = 8156072525389912369788197863285751656042515380911795404436333529629416084362735262281722179416240983448945672233749861517470671156357917601583268804973543
  * 10678085245814899631026086851678635624044610674331494223434578587048178556659016077336866548714220013612176819608742965144962254942844889066032236627832071

あとは通常通り復号する。

#!/usr/bin/env python3
from Crypto.Util.number import *

n = 0x7c05a45d02649367ebf6f472663119777ce5f9b3f2283c7b03471e9feb1714a3ce9fa31460eebd9cd5aca7620ecdb52693a736e2fcc83d7909130c6038813fd16ef50c5ca6f491b4a8571289e6ef710536c4615604f8e7aeea606d4b5f59d7adbec935df23dc2bbc2adebbee07c05beb7fa68065805d8c8f0e86b5c3f654e651
e = 0x10001
ct = 0x35b63f7513dbb828800a6bcd708d87a6c9f33af634b8006d7a94b7e3ba62e6b9a1732a58dc35a8df9f7554e1168bfe3de1cb64792332fc8e5c9d5db1e49e86deb650ee0313aae53b227c75e40779a150ddb521f3c80f139e26b2a8880f0869f755965346cd28b7ddb132cf8d8dcc31c6b1befc83e21d8c452bcce8b9207ab76e

p = 8156072525389912369788197863285751656042515380911795404436333529629416084362735262281722179416240983448945672233749861517470671156357917601583268804973543
q = 10678085245814899631026086851678635624044610674331494223434578587048178556659016077336866548714220013612176819608742965144962254942844889066032236627832071
assert n == p * q

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(ct, d, n)
flag = long_to_bytes(m).decode()
print(flag)
cvctf{f4c70rDB_15_p0w3rfu1}

RSA 2 (Crypto)

フラグの前半がstage_one、後半がstage_twoでRSA暗号化されている。
stage_oneはModulusをpにして考え、以下の問題にして復号する。

ct % p = pow(m, e, p)

stage_twoはpとqは近い数値と想定できるため、Fermat法で素因数分解して復号する。

#!/usr/bin/env python3
from Crypto.Util.number import *

def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def fermat(n):
    x = isqrt(n) + 1
    y = isqrt(x * x - n)
    while True:
        w = x * x - n - y * y
        if w == 0:
            break
        elif w > 0:
            y += 1
        else:
            x += 1
    return x - y, x + y

with open('output.txt', 'r') as f:
    params = f.read().splitlines()

p = int(params[1].split(' ')[-1])
e = int(params[2].split(' ')[-1])
dp = int(params[3].split(' ')[-1])
b = int(params[4].split(' ')[-1])
ct = int(params[5].split(' ')[-1])

m = pow(ct % p, dp, p)
flag1 = long_to_bytes(m).decode()

n = int(params[8].split(' ')[-1])
e = int(params[9].split(' ')[-1])
ct = int(params[10].split(' ')[-1])
p, q = fermat(n)
assert n == p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(ct, d, n)
flag2 = long_to_bytes(m).decode()

flag = flag1 + flag2
print(flag)
cvctf{Hensel_Takagi_Lifting,but_Fermat_is_better?}

Big Rabin (Crypto)

primesの各要素がnの素因数。Tonelli-Shanks Algorithmを使って、各要素について、平方剰余を求め、中国人剰余定理により復号する。

#!/usr/bin/env python3
from Crypto.Util.number import *
from sympy.ntheory.modular import crt

def legendre(a, p):
    return pow(a, (p - 1) // 2, p)

def tonelli_shanks(a, p):
    if legendre(a, p) != 1:
        raise Exception("not a square (mod p)")

    q = p - 1
    s = 0
    while q % 2 == 0:
        q >>= 1
        s += 1

    for z in range(2, p):
        if legendre(z, p) == p - 1:
            break

    m = s
    c = pow(z, q, p)
    t = pow(a, q, p)
    r = pow(a, (q + 1) // 2, p)

    t2 = 0
    while True:
        if t == 0: return 0
        if t == 1: return r
        t2 = (t * t) % p
        for i in range(1, m):
            if t2 % p == 1:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        m = i
        c = (b * b) % p
        t = (t * c) % p
        r = (r * b) % p

with open('out.txt', 'r') as f:
    params = f.read().splitlines()

primes = eval(params[0])
c = int(params[1])

ms = [[], []]
for p in primes:
    m = tonelli_shanks(c % p, p)
    ms[0].append(m)
    ms[1].append(p - m)

for i in range(2 ** len(ms[0])):
    b = bin(i)[2:].zfill(len(ms[0]))
    tmp_ms = []
    for j in range(len(b)):
        tmp_ms.append(ms[int(b[j])][j])
    m = crt(primes, tmp_ms)[0]
    msg = long_to_bytes(m)
    if b'cvctf{' in msg:
        flag = msg[msg.index(b'cvctf{'):].decode()
        print(flag)
        break
cvctf{r4b1n_Cryp70_K1nd4_c0mpL1C4t3d?}

French (Reverse)

Ghidraでデコンパイルする。

undefined8 main(void)

{
  undefined8 uVar1;
  long in_FS_OFFSET;
  uint local_84;
  char local_78 [32];
  undefined8 local_58;
  undefined8 local_50;
  undefined4 local_48;
  undefined2 local_44;
  undefined local_42;
  undefined8 local_38;
  undefined8 local_30;
  undefined8 local_28;
  undefined8 local_20;
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  local_38 = 0x49534544204c4547;
  local_30 = 0x544e41544345464e;
  local_28 = 0x454c2052554f5020;
  local_20 = 0x534e49414d2053;
  fread(local_78,1,0x17,stdin);
  local_58 = 0x5ff83441e17900e5;
  local_50 = 0xdf970af589793ad;
  local_48 = 0x494e0309;
  local_44 = 0x92dd;
  local_42 = 0xb7;
  rc4_crypt(&local_58,0x17,&local_38,0x1f);
  local_84 = 0;
  do {
    if (0x16 < local_84) {
      puts("Correct!");
      uVar1 = 0;
LAB_00101735:
      if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
        __stack_chk_fail();
      }
      return uVar1;
    }
    if (*(char *)((long)&local_58 + (long)(int)local_84) != local_78[(int)local_84]) {
      uVar1 = 1;
      goto LAB_00101735;
    }
    local_84 = local_84 + 1;
  } while( true );
}

local_38以降が鍵、local_58以降が暗号データとして、RC4の復号をすればよい。

#!/usr/bin/env python3
from Crypto.Cipher import ARC4

key = (0x49534544204c4547).to_bytes(8, byteorder='little')
key += (0x544e41544345464e).to_bytes(8, byteorder='little')
key += (0x454c2052554f5020).to_bytes(8, byteorder='little')
key += (0x534e49414d2053).to_bytes(7, byteorder='little')

ct = (0x5ff83441e17900e5).to_bytes(8, byteorder='little')
ct += (0xdf970af589793ad).to_bytes(8, byteorder='little')
ct += (0x494e0309).to_bytes(4, byteorder='little')
ct += (0x92dd).to_bytes(2, byteorder='little')
ct += (0xb7).to_bytes(1, byteorder='little')

cipher = ARC4.new(key)
pt = cipher.decrypt(ct).decode()
print(pt)
cvctf{rC4<->3nC0d3d>-<}

Basic Transforms (Reverse)

スクリプトの処理概要は以下の通り。

・以下をチェック
 ・長さは20バイト
 ・"cvctf{"から始まり、"}"で終わる。
・cat: {}の中を鍵"nodejsisfun"でVigenere暗号化し、ASCIIコードでプラス1する。
・catを逆順にしてbase64暗号化すると"QUlgNGoxT2A2empxMQ=="

逆算して、フラグを求める。

#!/usr/bin/env python3
from base64 import *
from string import *

enc = 'QUlgNGoxT2A2empxMQ=='
cat = b64decode(enc)[::-1]
cat = ''.join([chr(c - 1) for c in cat])

key = 'nodejsisfun'

flag = ''
index = 0
for c in cat:
    if c in ascii_lowercase:
        k_index = ascii_lowercase.index(key[index])
        c_index = ascii_lowercase.index(c)
        m_index =(c_index - k_index) % 26
        flag += ascii_lowercase[m_index]
    else:
        flag += c
    index += 1

flag = 'cvctf{%s}' % flag
print(flag)
cvctf{0bfu5_N0d3_H@}

iKUN 1 (Misc)

https://github.com/CryptoverseCTFにアクセスする。cxk-ballのリポジトリを見てみる。そこでcommitの一覧からそれぞれ情報を見てみる。Fixのタイトルでコメント行にフラグが書かれていた。

cvctf{git_reveals_everything}

World Cup Predictions (Reverse)

Ghidraでデコンパイルする。

undefined8 FUN_00101371(void)

{
  int iVar1;
  int iVar2;
  int iVar3;
  int iVar4;
  int iVar5;
  int iVar6;
  int iVar7;
  int iVar8;
  size_t sVar9;
  long in_FS_OFFSET;
  int local_148;
  int local_144;
  int local_140;
  char local_138 [33];
  char cStack279;
  char cStack248;
  char cStack215;
  char cStack184;
  char cStack152;
  char cStack118;
  char cStack88;
  char local_38;
  char local_37;
  char local_36;
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  setvbuf(stdout,(char *)0x0,2,0);
  puts(PTR_s_______.-'___'-.__.'--.`_`.--'._/_00104020);
  puts("Welcome to the World Cup Predictor!");
  puts("[+] Stage 1: Predict the first place in each group.");
  local_148 = 0;
  for (local_144 = 0; local_144 < 8; local_144 = local_144 + 1) {
    printf("Group %c: ",(ulong)(local_144 + 0x41));
    fgets(local_138 + (long)local_144 * 0x20,0x20,stdin);
    iVar8 = FUN_001012fb(local_138 + (long)local_144 * 0x20);
    if (iVar8 == 0) {
      local_148 = local_148 + -1;
    }
  }
  for (local_140 = 0; local_140 < 8; local_140 = local_140 + 1) {
    sVar9 = strlen(local_138 + (long)local_140 * 0x20);
    if (sVar9 < 3) {
      local_148 = local_148 + -1;
    }
    else {
      if ((local_140 == 0) && (local_138[0] == 'N')) {
        iVar8 = 1;
      }
      else {
        iVar8 = 0;
      }
      if ((local_140 == 1) && (cStack279 == 'n')) {
        iVar1 = 1;
      }
      else {
        iVar1 = 0;
      }
      if ((local_140 == 2) && (cStack248 == 'A')) {
        iVar2 = 1;
      }
      else {
        iVar2 = 0;
      }
      if ((local_140 == 3) && (cStack215 == 'e')) {
        iVar3 = 1;
      }
      else {
        iVar3 = 0;
      }
      if ((local_140 == 4) && (cStack184 == 'J')) {
        iVar4 = 1;
      }
      else {
        iVar4 = 0;
      }
      if ((local_140 == 5) && (cStack152 == 'B')) {
        iVar5 = 1;
      }
      else {
        iVar5 = 0;
      }
      if ((local_140 == 6) && (cStack118 == 'a')) {
        iVar6 = 1;
      }
      else {
        iVar6 = 0;
      }
      if ((local_140 == 7) && (cStack88 == 'U')) {
        iVar7 = 1;
      }
      else {
        iVar7 = 0;
      }
      local_148 = local_148 + iVar7 + iVar8 + iVar1 + iVar2 + iVar3 + iVar4 + iVar5 + iVar6;
    }
  }
  if (local_148 < 8) {
    puts("You failed.");
  }
  else {
    puts("[+] Stage 2: Predict the winner!");
    fgets(&local_38,0x20,stdin);
    iVar8 = FUN_001012fb(&local_38);
    if (iVar8 == 0) {
      puts("You failed.");
    }
    else {
      sVar9 = strlen(&local_38);
      if (sVar9 < 3) {
        puts("You failed.");
      }
      else if (((local_38 == 'A') && (local_37 == 'r')) && (local_36 == 'g')) {
        printf("Congrats! Here is your flag: ");
        FUN_00101289();
      }
      else {
        puts("You failed.");
      }
    }
  }
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

undefined8 FUN_001012fb(char *param_1)

{
  int iVar1;
  size_t sVar2;
  int local_c;
  
  sVar2 = strlen(param_1);
  param_1[sVar2 - 1] = '\0';
  local_c = 0;
  while( true ) {
    if (0x1f < local_c) {
      return 0;
    }
    iVar1 = strcmp(param_1,(&PTR_s_Qatar_00104040)[local_c]);
    if (iVar1 == 0) break;
    local_c = local_c + 1;
  }
  return 1;
}

                             PTR_s_Qatar_00104040                            XREF[2]:     FUN_001012fb:0010133b(*), 
                                                                                          FUN_001012fb:00101342(R)  
        00104040 30 21 10        addr       s_Qatar_00102130                                 = "Qatar"
                 00 00 00 
                 00 00
        00104048 36 21 10        addr       s_Ecuador_00102136                               = "Ecuador"
                 00 00 00 
                 00 00
        00104050 3e 21 10        addr       s_Senegal_0010213e                               = "Senegal"
                 00 00 00 
                 00 00
        00104058 46 21 10        addr       s_Netherlands_00102146                           = "Netherlands"
                 00 00 00 
                 00 00
        00104060 52 21 10        addr       s_England_00102152                               = "England"
                 00 00 00 
                 00 00
        00104068 5a 21 10        addr       DAT_0010215a                                     = 49h    I
                 00 00 00 
                 00 00
        00104070 5f 21 10        addr       DAT_0010215f                                     = 55h    U
                 00 00 00 
                 00 00
        00104078 63 21 10        addr       s_Wales_00102163                                 = "Wales"
                 00 00 00 
                 00 00
        00104080 69 21 10        addr       s_Argentina_00102169                             = "Argentina"
                 00 00 00 
                 00 00
        00104088 73 21 10        addr       s_Saudi_Arabia_00102173                          = "Saudi Arabia"
                 00 00 00 
                 00 00
        00104090 80 21 10        addr       s_Mexico_00102180                                = "Mexico"
                 00 00 00 
                 00 00
        00104098 87 21 10        addr       s_Poland_00102187                                = "Poland"
                 00 00 00 
                 00 00
        001040a0 8e 21 10        addr       s_France_0010218e                                = "France"
                 00 00 00 
                 00 00
        001040a8 95 21 10        addr       s_Australia_00102195                             = "Australia"
                 00 00 00 
                 00 00
        001040b0 9f 21 10        addr       s_Denmark_0010219f                               = "Denmark"
                 00 00 00 
                 00 00
        001040b8 a7 21 10        addr       s_Tunisia_001021a7                               = "Tunisia"
                 00 00 00 
                 00 00
        001040c0 af 21 10        addr       s_Spain_001021af                                 = "Spain"
                 00 00 00 
                 00 00
        001040c8 b5 21 10        addr       s_Costa_Rica_001021b5                            = "Costa Rica"
                 00 00 00 
                 00 00
        001040d0 c0 21 10        addr       s_Germany_001021c0                               = "Germany"
                 00 00 00 
                 00 00
        001040d8 c8 21 10        addr       s_Japan_001021c8                                 = "Japan"
                 00 00 00 
                 00 00
        001040e0 ce 21 10        addr       s_Belgium_001021ce                               = "Belgium"
                 00 00 00 
                 00 00
        001040e8 d6 21 10        addr       s_Canada_001021d6                                = "Canada"
                 00 00 00 
                 00 00
        001040f0 dd 21 10        addr       s_Morocco_001021dd                               = "Morocco"
                 00 00 00 
                 00 00
        001040f8 e5 21 10        addr       s_Croatia_001021e5                               = "Croatia"
                 00 00 00 
                 00 00
        00104100 ed 21 10        addr       s_Brazil_001021ed                                = "Brazil"
                 00 00 00 
                 00 00
        00104108 f4 21 10        addr       s_Serbia_001021f4                                = "Serbia"
                 00 00 00 
                 00 00
        00104110 fb 21 10        addr       s_Switzerland_001021fb                           = "Switzerland"
                 00 00 00 
                 00 00
        00104118 07 22 10        addr       s_Cameroon_00102207                              = "Cameroon"
                 00 00 00 
                 00 00
        00104120 10 22 10        addr       s_Portugal_00102210                              = "Portugal"
                 00 00 00 
                 00 00
        00104128 19 22 10        addr       s_Ghana_00102219                                 = "Ghana"
                 00 00 00 
                 00 00
        00104130 1f 22 10        addr       s_Uruguay_0010221f                               = "Uruguay"
                 00 00 00 
                 00 00
        00104138 27 22 10        addr       s_South_Korea_00102227                           = "South Korea"
                 00 00 00 
                 00 00

Stage 1をクリアするためには、local_148を0、iVar1~8を1にする必要がある。Group A~Hに対して、入力したものは&PTR_s_Qatar_00104040以降の文字列のどれかと一致していればよい。
iVar8を1にするためには"N"から始まる文字列にする必要がある。このリストの中では、"Netherlands"
iVar1を1にするためには1(=312-32*1-279)文字目が"n"である必要がある。このリストの中では、"England"
iVar2を1にするためには0(=312-32*2-248)文字目が"A"である必要がある。このリストの中では、"Argentina"
iVar3を1にするためには1(=312-32*3-215)文字目が"e"である必要がある。このリストの中では、"Senegal"
iVar4を1にするためには0(=312-32*4-184)文字目が"J"である必要がある。このリストの中では、"Japan"
iVar5を1にするためには0(=312-32*5-152)文字目が"B"である必要がある。このリストの中では、"Belgium"
iVar6を1にするためには2(=312-32*6-118)文字目が"a"である必要がある。このリストの中では、"Ghana"
iVar7を1にするためには0(=312-32*7-88)文字目が"U"である必要がある。このリストの中では、"Uruguay"
Stage 2では"Arg"から始まる文字列を指定する。このリストの中では、"Argentina"

$ nc 137.184.215.151 22611
          ___          
      _.-'___'-._   
    .'--.`   `.--'.   
   /.'   \   /   `.\   
  | /'-._/```\_.-'\ |   
  |/    |     |    \|   
  | \ .''-._.-''. / |   
   \ |     |     | /   
    '.'._.-'-._.'.'   
      '-:_____;-'   

Welcome to the World Cup Predictor!
[+] Stage 1: Predict the first place in each group.
Group A: Netherlands
Group B: England
Group C: Argentina
Group D: Senegal
Group E: Japan 
Group F: Belgium
Group G: Ghana
Group H: Uruguay
[+] Stage 2: Predict the winner!
Argentina
Congrats! Here is your flag: cvctf{Arg3nt1n4_PLS_W1N_Th3_W0rld_Cup,M3551}
cvctf{Arg3nt1n4_PLS_W1N_Th3_W0rld_Cup,M3551}

Super Guesser (Reverse)

pycをデコンパイルする。

$ decompyle3 guesser.pyc 
# decompyle3 version 3.9.0
# Python bytecode version base 3.8.0 (3413)
# Decompiled from: Python 3.10.4 (main, Jun 29 2022, 12:14:53) [GCC 11.2.0]
# Embedded file name: /home/guesser.py
# Compiled at: 2022-09-12 03:00:05
# Size of source mod 2**32: 682 bytes
import hashlib, re
hashes = [
 'd.0.....f5...5.6.7.1.30.6c.d9..0',
 '1b.8.1.c........09.30.....64aa9.',
 'c.d.1.53..66.4.43bd.......59...8',
 '.d.d.076........eae.3.6.85.a2...']

def main():
    guesses = []
    for i in range(len(hashes)):
        guess = input('Guess: ')
        if len(guess) <= 4 or len(guess) >= 6 or re.match('^[a-z]+$', guess):
            exit('Invalid')
        if not re.match('^' + hashes[i].replace('.', '[0-9a-f]') + '$', hashlib.md5(guess.encode()).hexdigest()):
            exit('Invalid')
        else:
            guesses.append(guess)
    else:
        print(f"Flag: {guesses[0]}" + '{' + ''.join(guesses[1:]) + '}')


if __name__ == '__main__':
    main()
# okay decompiling guesser.pyc

このスクリプトの処理概要は以下の通り。

・hashes: 歯抜けのhash、4つのリスト
・guesses = []
・hashedの長さだけ以下繰り返す(i)
 ・guess: 入力(5バイト英子文字のみ)
 ・hased[i]と形式が合っていることをチェック
 ・合っていたら、guessesにguessを追加
・flagはguess[0]{guess[1]以降の連結}

ブルートフォースで該当するものを探す。

#!/usr/bin/env python3
import itertools
import hashlib, re
import string

hashes = [
 'd.0.....f5...5.6.7.1.30.6c.d9..0',
 '1b.8.1.c........09.30.....64aa9.',
 'c.d.1.53..66.4.43bd.......59...8',
 '.d.d.076........eae.3.6.85.a2...']

guesses = []
for i in range(len(hashes)):
    for c in itertools.product(string.ascii_lowercase, repeat=5):
        guess = ''.join(c)
        if re.match('^' + hashes[i].replace('.', '[0-9a-f]') + '$', hashlib.md5(guess.encode()).hexdigest()):
            guesses.append(guess)
            break

flag = guesses[0] + '{' + ''.join(guesses[1:]) + '}'
print(flag)
cvctf{hashisnotguessy}

ECC Quiz (Crypto)

$ nc 137.184.215.151 22666
Welcome to ECC Quiz! You shall get the flag after answering all 3 questions correctly.
Let's get started!
========================
1. Question 1
2. Question 2
3. Question 3
4. Check Solve Status
5. Get FLAG
6. Exit
========================
Enter your choice: 1
Curve parameters:
p = 9479
a = 575
b = 7016
Point P: (7766, 1290)
Find the point Q = 6149P. The answer is in the form of (x,y):

ECCに関する簡単なクイズが出題される。3つの問題にすべて答えることができたら、フラグが得られるようだ。
Question 1は乗算をするだけなので、sageで簡単に計算できる。
Question 2は2点が表示されるので、a, bを求める必要がある。

y1**2 = x1**3 + a*x1 + b (mod p)
y2**2 = x2**3 + a*x2 + b (mod p)

[x1 1]   [a]   [y1**2 - x1**3]
       *     =
[x2 1]   [b]   [y2**2 - x2**3]

        ↓

[a]           [x1 1]   [y1**2 - x1**3]
    = inverse        * 
[b]           [x2 1]   [y2**2 - x2**3]

これでa, bがわかる。
Question 3は離散対数問題。sageにそのまま解かせてみる。

#!/usr/bin/env sage
import socket
import re

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('137.184.215.151', 22666))

#### Question 1 ####
data = recvuntil(s, b': ')
print(data + '1')
s.sendall(b'1\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)
p = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
a = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
b = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
P = eval(data.split(': ')[1])
data = recvuntil(s, b': ')
print(data, end='')
pattern = 'Q \= (\d+)P'
m = re.search(pattern, data)
mul = int(m.group(1))

F = FiniteField(p)
E = EllipticCurve(F, [a, b])
P = E.point(P)
Q = mul * P
ans = '(%d,%d)' % (Q[0], Q[1])
print(ans)
s.sendall(ans.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)

#### Question 2 ####
data = recvuntil(s, b': ')
print(data + '2')
s.sendall(b'2\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)
p = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
M = eval(data.split(': ')[1])
x1 = M[0]
y1 = M[1]
data = recvuntil(s, b'\n').rstrip()
print(data)
N = eval(data.split(': ')[1])
x2 = N[0]
y2 = N[1]
data = recvuntil(s, b': ')
print(data, end='')

A = matrix(Zmod(p), [[x1, 1], [x2, 1]])
C = matrix(Zmod(p), [[y1**2 - x1**3], [y2**2 - x2**3]])
X = A.inverse() * C
ans = '(%d,%d)' % (X[0][0], X[1][0])
print(ans)
s.sendall(ans.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)

#### Question 3 ####
data = recvuntil(s, b': ')
print(data + '3')
s.sendall(b'3\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)
p = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
a = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
b = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
P = eval(data.split(' = ')[1])
data = recvuntil(s, b'\n').rstrip()
print(data)
Q = eval(data.split(' = ')[-1])
data = recvuntil(s, b': ')
print(data, end='')

F = FiniteField(p)
E = EllipticCurve(F, [a, b])
P = E.point(P)
Q = E.point(Q)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []
for fac in primes:
    t = int(P.order()) // int(fac)
    dlog = discrete_log(t*Q, t*P, operation='+')
    dlogs += [dlog]
ans = crt(dlogs, primes)
print(ans)
s.sendall(str(ans).encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)

#### GET FLAG ####
data = recvuntil(s, b': ')
print(data + '5')
s.sendall(b'5\n')
data = recvuntil(s, b'\n').rstrip()
print(data)

実行結果は以下の通り。

Welcome to ECC Quiz! You shall get the flag after answering all 3 questions correctly.
Let's get started!
========================
1. Question 1
2. Question 2
3. Question 3
4. Check Solve Status
5. Get FLAG
6. Exit
========================
Enter your choice: 1
Curve parameters:
p = 10091
a = 675
b = 4736
Point P: (7608, 6643)
Find the point Q = 6583P. The answer is in the form of (x,y): (8690,8544)
Correct!
========================
1. Question 1
2. Question 2
3. Question 3
4. Check Solve Status
5. Get FLAG
6. Exit
========================
Enter your choice: 2
Curve parameters:
p = 35927826909827010451032405270539923867151462723665087608518140171945610599726754410737409631101219961836765987146807285114651064399967576554517233277285085237527458984842535566458154441023
Point M on the curve: (10294333340606652335263465278917102635046073474250714266160725899559162863009242397869159910341629886077203186834021290949772596768486164945010619810361313277518975711988235747617007361754, 30784564719277754169006087755244651442039328820884574610608512550273887194754573452941559088034475590538059127606638625807728921513193298826087363481358612907234106191446213360008230602299)
Point N on the curve: (19055198188650996221921637413445852243568270293359450701965930516162297778560024704160052033507183380245423048765156643433140985980277266014881260560179034614283602874803826554155352398708, 33077404534492135824159933460311224187197098687278815173880633396353996606155362946730814805792739474988137343375262745757016806954610780378848189909631545699250840119342174211996879440913)
Find the curve parameters a and b. The answer is in the form of (a,b): (35432922908845379643704666898816425046275880587444790766931249117628695468669954111723069282524857248444370433408008980036793344252555002772024804938287461280660835115250394597085465626721,25922552739307824054591395653528362812191753135526396082481091146465833182172602761363337721017632670989226345817827412443467026745160853747808681575911229098870259682149987105191135319696)
Correct!
========================
1. Question 1
2. Question 2
3. Question 3
4. Check Solve Status
5. Get FLAG
6. Exit
========================
Enter your choice: 3
Curve parameters:
p = 1191574194759034684388674581157
a = 463753770494146064372927893251
b = 404025310777323924434557416222
P = (973149161090049679097999482808, 108379228635077153345009768598)
Q = uP = (1144843387379655116394869745634, 1024782742817417295592544711250)
Find the scalar u. The answer is a single integer: 3595
Correct!
========================
1. Question 1
2. Question 2
3. Question 3
4. Check Solve Status
5. Get FLAG
6. Exit
========================
Enter your choice: 5
Congrats! Here's your flag: b'cvctf{ECC_is_411_y0u_n33d_t0_kn0w...And_CryptoHack_15_4w3s0m3!}'
cvctf{ECC_is_411_y0u_n33d_t0_kn0w...And_CryptoHack_15_4w3s0m3!}

CyberMania (Crypto)

以下の順にデコードする。

・base64デコード
・スペース区切りの16進数のデコード
・base85デコード
・base64デコード
・base58デコード
#!/usr/bin:/env python3
from Crypto.Util.number import *
from base64 import *
from base58 import *

with open('secret.txt', 'r') as f:
    enc = f.read()

enc = b64decode(enc)
enc = ''.join([chr(int(c, 16)) for c in enc.split(b' ')])
enc = a85decode(enc)
enc = b64decode(enc)
enc = b58decode(enc)

with open('emoji.txt', 'wb') as f:
    f.write(enc)

すると、以下のような絵文字になる。

🙄😂😒😱🤬😯😦😆🤬🤨😔😶😐😅😤😘😐😰😆😗😳😕😙🤡😃😱😀😙😷😟🤕😠🤮😖🤣😱😢😢🤓🤨🤥😛😑😄😓😵😙🤬😏😡😐🤣😡😒

https://cryptoji.com/で復号する。

cvctf{3m0j1_c4n_L34K_7h1ng5}

RSA 3 (Crypto)

RSA暗号でnは可変で、eが17, 19, 23, 29, 31, 63357のどれかで暗号化される。Hastad's Broadcast Attackを狙い、eが17の情報を17個集めてみる。ただ、cの先頭ビットがダミーの場合があるので、フラグの形式に復号できるまで調整する。ダミービットが付く可能性が低いことから、cがnより大きい場合のみ先頭ビットを外すようにした。

#!/usr/bin/env python3
import socket
import functools
from Crypto.Util.number import *

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

def chinese_remainder(n, a):
    sum = 0
    prod = functools.reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod

def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a // b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

def inv_pow(c, e):
    low = -1
    high = c+1
    while low + 1 < high:
        m = (low + high) // 2
        p = pow(m, e)
        if p < c:
            low = m
        else:
            high = m
    m = high
    assert pow(m, e) == c
    return m

ns = []
cs = []
while True:
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('137.184.215.151', 22629))
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    n = int(data.split(' ')[-1])
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    e = int(data.split(' ')[-1])
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    c = int(data.split(' ')[-1])
    if e == 17:
        if n < c:
            c = int(bin(c)[3:], 2)
        ns.append(n)
        cs.append(c)
    if len(ns) == 17:
        break

a = chinese_remainder(ns, cs)
for n, c in zip(ns, cs):
    assert a % n == c
m = inv_pow(a, e)
flag = long_to_bytes(m).decode()
print(flag)

何回か試したところ、復号できた。実行結果は以下の通り。

        :
n = 19482970449472647996949255790160019536823811589752417040197789538735948234527383791782162975775008738754731098285008440418613529447045872670460110268451401820226012087390289771034680297303142390316615411811682258816497516776137887669470868430337926388914480031091749481453529482321133017258210044932496290651493880771090049040714952219157929756966928260223176461515511221741532997502601962705034663152259651624191144177696990013191360427819162117623636409596742113891434777690046000118995978947349429871654579103961510277435847860729928867562815915298819370228549429954038789132943464034315471555668306212434221484149
e = 19
c = 15633322918528885106037068463083525736491835255915567684792406125054586229367611573734318935590139470714574214563324195426968026517801968691896023516573697740087363463073472022032385915181981652828495216693569748166879146838047409209962719354311907944490470523946341418686730364688459557580110330991189484004223291611151597772559003864083365047879207930308593296339705214653812345777248701345462008417629158376543641116484868106327234530921973090903512268729693102737457497800190592285641128504835270809527829227212496825851963912869575489555243134855877364975861980680374055644970985205401996642200940384181429377468
n = 23783750134837692983880020475871334693840004392932449661317979535097123034976789898789004880255464648561531736460626041425922683750611671060649391630486412467721147318849908313696477104411861358187227601950212024055673953339142506976741564847687343412536044669018339616915996636354197607604701850978696581186475239536559583765670106298861038935063558186973719234066539035793531902906650911715775837207888324727096988123248375948577197848314636645686183060212344859020165499708400642531150263869046482484899567003349554452230220706855881291930204631792152211080716128182526418146579691607829912442781367871407923108671
e = 19
c = 7480299212917778981479839052744008418755942378148134527304599807286893805383369646031920767267319750042706346942480245759966871397726442879693974466544365375648902093609690702515822253264911075291542137931295245816323203713368985834689112588235411996937281210931513990191617196098595707658013426471040296349003728974999742743372387542667576899264503163909588483510674091740967741458919952538339079819929779170236998625837307398691629136226584668536213076185761263293249660089943663720123228013405141905016611392209807163464936324323980356549928503266648279987693518272893809277521001216632584208028338166831626720031
n = 12773619086057910173724885156690762883368513253236437180649023134396660932407976625526582552266923749086290996021761367807342973144553994013443404399738673137266863837983369526022172806852958846593631758321426917129064180598809069482674558138608772862376876089189363040761598398522415131788669926357760020609280506681858829156741961856618689462163480569277029703932528897531464661688932401968375395197838995667757798404097248739176730658827375179105253657857803853403683221880837833698892687536628296066283923449021029586798868473704263538146513509262387211626493261833927361185802759814092820015407318497538367983539
e = 17
c = 6922208356981255935316251518524736914341880539634863089246194411902783112773299948230261774256637952899293970657204855471866342191478880735817912228127299832557838135205469060821643478597214743780108727262611145852911958880412810604703750055401708307772660971338943311457459920747000104050188962869039655806220944079401759335037522027631422637393295451984023707544576960068677748063833053429633089453843033065711356938486742102987517823638615548839719451318559228363678309975631497962380137681122060877705241985887049197886550184511638717371510027653505978239075688791639730776612841000854410243196583101750896586
cvctf{Hastad_with_e=65537_might_be_slow}
cvctf{Hastad_with_e=65537_might_be_slow}