この大会は2021/11/13 2:00(JST)~2021/11/14 14:00(JST)に開催されました。
今回もチームで参戦。結果は4379点で501チーム中13位でした。
自分で解けた問題をWriteupとして書いておきます。
Sanity Check (Sanity Check)
Discordに入り、#announcementsチャネルのメッセージを見ると、フラグが書いてあった。
flag{let_the_games_begin}
3in1 (Kiddie Pool)
AES-ECBで暗号化されているが、鍵はわかっているので、そのまま復号する。
#!/usr/bin/python3 from Crypto.Cipher import AES from Crypto.Hash import SHA256 password = ("abda") hash_obj = SHA256.new(password.encode('utf-8')) hkey = hash_obj.digest() cipher_text = b'\x1bkw\x00\x01#\x1dv\xd1\x1e\xfb\xba\xac_b\x02T\xfbZ\xca\xac8Y\\8@4\xba;\xe1\x11$\x19\xe8\x89t\t\xc8\xfd\x93\xd8-\xba\xaa\xbe\xf1\xa0\xab\x18\xa0\x12$\x9f\xdb\x08~\x81O\xf0y\xe9\xef\xc41\x1a$\x1cN3\xe8F\\\xef\xc1G\xeb\xdb\xa1\x93*F\x1b|\x1c\xec\xa3\x04\xbf\x8a\xd9\x16\xbc;\xd2\xaav6pWX\xc1\xc0o\xab\xd5V^\x1d\x11\xe4}6\xa4\x1b\\G\xd4e\xc2mP\xdb\x9b\x9f\xb0Z\xf12' cipher = AES.new(hkey, AES.MODE_ECB) flag = cipher.decrypt(cipher_text).rstrip(b'{').decode() print(flag)
2つのURLに復号された。
https://www.mediafire.com/file/oii1sm3oyt4tyjc/flag.wav/file https://www.mediafire.com/file/rgdww91os3we7eo/hint.txt/file
この2つのファイルをダウンロードする。hint.txtにはこう書いてある。
A graphic or photographic representation
flag.wavをAudacityで開き、スペクトログラムを見ると、フラグが現れた。
flag{34sY_CH4LL3nGe_w1tH_3Xtr4_St3Ps}
Vieta's Poly (Kiddie Pool)
高次方程式の根について、和、逆数の和または2乗の和を答えていく必要がある。
まず3次関数で考える。
(x - a) * (x - b) * (x - c) = x**3 - (a + b + c) * x**2 + (a*b + b*c + c*a) * x - a*b*c coeffs[1] = - (a + b + c) 1/a + 1/b + 1/c = (b*c + c*a + a*b) / (a*b*c) = - coeffs[-2] / coeffs[-1] a**2 * b**2 + c**2 = (a + b + c)**2 - 2 * (a*b + b*c + c*a) = coeffs[1]**2 - 2 * coeffs[2]
次に4次関数で考える。
(x - a) * (x - b) * (x - c) * (x - d) = x**4 - (a + b + c + d) * x**3 + (a*b + a*c + a*d + b*c + b*d + c*d) * x**2 - (a*b*c + a*b*d + a*c*d + b*c*d) * x + a*b*c*d coeffs[1] = - (a + b + c + d) 1/a + 1/b + 1/c + 1/d = (b*c*d + c*d*a + d*a*b + a*b*c) / (a*b*c*d) = - coeffs[-2]/coeffs[-1] a**2 * b**2 + c**2 + d**2 = (a + b + c + d)**2 - 2 * (a*b + a*c + a*d + b*c + b*d + c*d) = coeffs[1]**2 - 2 * coeffs[2]
以上から3パターンの問題の答えは以下のように計算できる。
・sum of the roots = - coeffs[1] ・sum of the reciprocals of the roots = - coeffs[-2]/coeffs[-1] ・sum of the squares of the roots = coeffs[1]**2 - 2 * coeffs[2]
テンプレートのコードを穴埋めをし、実行する。
from pwn import * context.log_level = 'info' #will print all input and output for debugging purposes conn = remote("ctf.k3rn3l4rmy.com",2236) #enter the address and the port here as strings. For example nc 0.0.0.0 5000 turns into remote('0.0.0.0', 5000) def get_input(): #function to get one line from the netcat input = conn.recvline().strip().decode() return input def parse(polynomial): ''' TODO: Parse polynomial For example, parse("x^3 + 2x^2 - x + 1") should return [1,2,-1,1] ''' sep = polynomial.split(' ') coeffs = [1] for i in range(len(sep) // 2): coeffs.append(int(sep[i*2+1] + sep[i*2+2].split('x')[0])) return coeffs for _ in range(4): get_input() #ignore challenge flavortext for i in range(100): type = get_input() coeffs = parse(get_input()) print(coeffs) ans = -1 if 'sum of the roots' in type: ans = -1 #TODO: Find answer ans = - coeffs[1] elif 'sum of the reciprocals of the roots' in type: ans = -1 #TODO: Find answer ans = - coeffs[-2] // coeffs[-1] elif 'sum of the squares of the roots' in type: ans = -1 #TODO: Find answer ans = coeffs[1]**2 - 2 * coeffs[2] conn.sendline(str(ans)) #send answer to server get_input() conn.interactive() #should print flag if you got everything right
実行結果は以下の通り。
[+] Opening connection to ctf.k3rn3l4rmy.com on port 2236: Done [1, -31, -63, -11, -79, -39, 43, -9, 12, -3, 41, 5984, 68] [1, 99, -87, -52, 26, 20, 46, -87, 61, -78, -61, 3325, 35] [1, -39, -30, -88, -30, -94, 68, 47, 88, 17, 89, 75, -49, -84, -57, -66, -2] [1, 24, -44, -40, -26, 35, -87, -21, -17, 59, -58, -26, 28, 74] [1, -32, -61, -4, 30, 33, -23, -39, -42, 49, 81, 25, 86, -98, 98, 47, -30, 14, -65, -11, 79] [1, -55, 75, -72, 83, 8, -14, 19, 73, 16, 31, -50, -99, 80, -27, 80, 17] [1, -79, -41, -57, -54, -34, -93, 42, -82, -59, 37, -28, 100, -89, -34, 34, -55] [1, 10, 66, 27, 46, -78, 66, 61, -31, 63, -61, -48, 55, 2196, 36] [1, 65, 23, 68, 0, 84, -41, 67, 26, 25, 40, 57, -92, -64, 22, 29, -82, 4108, 52] [1, 81, 30, -43, 93, -24, -62, 21, -74, 17, -29, 92, 93, -10, 67, 16] [1, 53, 43, -46, 10, 9, -21, -62, -84, -100, -27, -83, -88, 1, 31, -34, 72, -5, -75] [1, 3, 93, 19, -96, 82, -94, 99, -45, -65, -96, 67, -93, -48] [1, -42, -28, -84, -20, 24, 86, 64, -49, 8, -43, -1032, 86] [1, 10, -9, -87, 48, -92, 96, -58, 25, -82, 37, 25, -33, -86, 86, 63, 62, -67, -4836, 62] [1, 0, -66, -39, 66, -20, -43, -49, -64, 20, 77, -77] [1, 4, -35, -39, 47, -14, 52, 19, 93, -6, 29, -25, -59, 93, -7, -12, 85, 31, -12, 95] [1, 42, -11, -21, -78, 87, -13, 21, -33, -89, 14, -54, -51, -1829, -59] [1, 30, 6, 77, -54, -3, -58, 92, 16, 58, 80, -2214, 54] [1, 68, -52, -22, 5, 67, 64, 61, 73, -44, 63, 26, 28, 66, -18, -27, 8, 65] [1, 75, -24, -48, 68, 17, 87, 39, 51, 37, -33, -74, -34, -64, -15, -80, 96, -76, -75, 49] [1, -63, -80, 92, -29, -89, 29, 96, -2, -80, 45, -51, -54, -65, 96, -6] [1, -32, -100, 97, 61, -38, 4, 74, -52, -94, 82, -71, 42, 79, -87, 67, 6279, 91] [1, -82, 87, -70, 6, -49, -43, -35, -32, -68, 19, 76, 0, -92, -4, 66, 99] [1, 49, -22, 10, 44, 81, 77, 5, 76, 3, 4, -970, -10] [1, 55, 18, 29, 49, 37, 98, 3, -18, -17, -29] [1, -73, -82, -95, -67, -60, -5, 52, -17, 2, -16, -23, 51] [1, -83, -94, -92, -68, -9, 17, -65, 31, 56, 10, 41, -22, -37, 18, -88, 0] [1, 3, -17, -41, 13, -60, -100, -2, -47, -88, -79, 30, -83, 25, 82, 46, -42, -95] [1, -54, 28, 25, -4, 53, 87, 20, -38, 39, -4, -41, 47, -61, -64, 1360, 40] [1, -23, 42, -92, -79, 3, 1, 12, -44, 13, -78, 79, 27, -97, 46, 81, 72, 56, 88] [1, -78, 4, -18, 7, 10, -59, 97, 2, -32, 63, -29, -87, -29, 96, -80, -23, 3] [1, -64, 81, 58, 60, -5, -6, -2, 53, -71, -97, -48, 16, 49, -90, 6144, 64] [1, 86, -39, 8, 79, 5, -65, -43, 37, -25, -77, -59, 27, -32, 68, -72] [1, -92, 7, 99, -27, 68, -95, 21, 95, -14, -2948, -67] [1, 33, -31, 97, -10, 1, -68, 2, -32, 59, 37, 12, 78, 31, -60, 21, -1, 94, 29, 12] [1, -34, 20, 10, -57, -93, 57, -87, -54, 97, -9, 92, 51, 35, -9, 88, -69, -8091, 87] [1, -29, -74, -80, 26, -73, 15, -6, -97, -17, -95, -60] [1, 45, -11, -100, 30, 11, -78, 43, 56, -38, -312, 78] [1, -82, 71, -63, 90, -83, -23, 62, -8, -42, 33, 7, 74, -89, -94, 19, -41] [1, 82, 99, -97, 47, 3, 84, 46, -29, 65, -60, -7, -19, 7, 50, -58, -38] [1, -6, 98, 70, -36, 48, 37, -71, -74, -84, 5, -75] [1, -92, 43, 82, 39, 6, -43, -99, -60, 23, 20, 54, 32, -1, -64, -49, -1, 1, -92, 53] [1, -59, -45, 58, -93, 46, 16, 65, -29, 49, -3, -24, -79, -12, 20, -40, 41] [1, -76, 73, 28, 29, -2, -98, -95, 85, -21, -15, 43, -82, 53, 79] [1, 63, -57, 61, -100, -60, -3, 6, -84, 5, 73, -58, 34, 79, 7, 37, -8, -41, 78, -89, -34] [1, -24, 10, -32, 44, -80, -22, -93, 73, -26, -21, 11, -32, -23, 1908, 36] [1, -88, 17, -98, -70, -26, 41, -100, -46, 18, -99, -99, 42, 89, 47, 45, -36] [1, -66, -63, -42, 78, -30, 27, -49, 37, 12, 79, 68, -100, 78, 81, -1, -87, 84, 0] [1, 39, 80, -18, -61, 69, 74, 41, -50, 66, -48, 7, -53, 91, 72, -21, -92, 40, -87, -22, 42] [1, 18, 15, -19, 59, -24, 59, -53, 95, -54, -17, 0, -37, 88, -14] [1, 25, 53, -37, 13, -3, 49, 78, -34, -1, -90, 34, -80, 29, -18, -40, -16, 83] [1, -2, -4, -56, -76, -94, -18, -48, -8, -77, -100, 98, -52, -93, 72, -5, 29] [1, -82, 18, -91, -9, -9, -52, -15, 67, 91, 41, -51, 18] [1, 5, -51, -47, 84, 92, 48, 75, 22, 76, 29, 3, -30, -21, -97, 50, 70, -58] [1, 12, -60, -22, 10, -50, 55, 33, -58, -37, 54, -93, -42, 99] [1, 53, 60, -93, 8, -46, 100, -19, -48, -40, 84, -22, 23, 85, -97, 10, -72, 48, -78, -32, 34] [1, -94, 37, -42, 6, -97, -99, -76, 89, 67, -61, -91, -1, -68, 94, 58, 44, -25] [1, -18, -5, -74, -7, -93, -29, 59, -74, -72, 31, -97, -57, 80, 88, -72, -47, 46, -19, -75, 76] [1, 25, -95, 93, -19, 0, 26, -98, 28, -72, 63, 66, 68, -61, -36, -48, -62] [1, 7, -82, 30, 29, -46, 3, -29, 93, 100, -2, -44, -27, -78, 66, -94, -6, 1674, 62] [1, 33, -12, -72, 0, 21, -80, 45, 90, 2, -69, 7, -52, 4, 40, 82, -4] [1, -70, 32, 64, 79, -29, -81, 14, 93, -590, 59] [1, 46, 66, 88, -37, 41, 51, -22, -78, 14, -60, 87, 42, 1178, 31] [1, -71, 36, 60, 12, -62, 28, -33, -10, 3, -17, -31, -31] [1, -34, 40, 18, -62, -54, 80, 79, -30, 6, -97, -26, -39, 30, 92, 84, 72, -22, 44, -84] [1, -68, -15, 19, 62, 51, -97, -56, -27, -3, 68, -59, 67, 69, -84, -3, -38, -62, -32] [1, 98, -62, 72, -27, 22, 29, 23, -16, 99, -27, -93] [1, 90, -67, -37, -39, -20, 37, 18, -52, -77, -54] [1, -8, 19, 56, -50, -52, 6, 3, -74, 38, -98, 19, 69, -15, 38, 14, 0, 67, 36, 66] [1, -89, -98, 34, 0, 60, 69, 9, -77, -15, 28, -46, -20, 98, 46, 1, 58, -22, -33, 86, 85] [1, -51, -24, -75, -51, -12, 29, 70, 44, 82, -95, 63, -96, 5, 98, -35] [1, -24, -27, -22, -82, 81, 44, 76, 84, -9, 58, 70, -7, -57, 57, -46, 94, 73, -69, 48] [1, -4, -78, 20, -99, 8, -87, -97, 49, 40, 76, -23, 74, -8, 10, -73, -69] [1, 18, -12, -70, -64, -98, -12, -24, 65, -81, 76, -50, -35, -11, -35, -11, -41, -32, 51, -4446, 78] [1, -88, 79, 81, 26, 5, -51, 47, 75, 6, 14, -30, -21] [1, 4, -16, -45, 57, 0, 48, 97, 95, -100, -35, 35, 15, 31, -97, 41, 29] [1, -40, -87, -12, -62, -79, -30, -4, 12, -95, -77, 71, -98, 76, 76, -75, -50, -97, 23, 77, 53] [1, 90, -52, 76, 97, -82, -63, -85, 18, 43, 51, 45, -72, 94, 31, 21, 81, 91] [1, -76, 81, 95, 85, 14, -88, 59, 96, -57, -8, -49, 20, -92, 39] [1, 52, -25, -26, -25, -16, 11, 99, 81, 71, -74, -53, -5, -25, 23, -37, 41, 2790, 62] [1, 21, -54, 28, 51, -93, 67, 31, -26, -96, -38, 40, -1, -63, 0, 26, -5, -5, -47] [1, -45, 11, -64, -50, 19, -4, 72, -55, -30, -60, -44] [1, 98, 32, -53, -51, 100, -44, 48, -43, -53, 54, 24, -98, -13, -689, -53] [1, 86, 49, -54, -54, -98, -38, 13, 61, -43, 22, 50, -32, 11, 83, -52] [1, -35, -3, -56, 81, -4, -76, -64, 97, -45, -74, 90, -63, -93, -41, -89, -3, 18, 14, -31, 21] [1, 27, 10, 86, 100, -65, 6, -32, 51, -44, 9, -1, -56, -48, 15] [1, -79, -25, -15, -13, 54, -57, -90, -83, -90, 32, 2, 23, -75, -42, 87] [1, -33, 29, 23, -57, 95, 76, 24, 99, 70, 8, -29, 756, 28] [1, -90, -2, 56, -65, -62, 64, -99, 25, 75, 45, -56, 62, -78, -8, 3800, 50] [1, 2, -68, -92, -1, -78, 29, -42, 80, 27, -9, 78, 77, -50, 5, -340, -5] [1, 74, -98, -88, -51, -81, 15, -5, 35, 41, -4, 78, -61, -13, -59, 40] [1, -49, 63, -77, 35, 42, -19, -5, -18, 42, -91, -62, -60, 56, -16, 42, 70, 3422, 59] [1, 88, 98, 26, -63, 50, -97, 73, -59, 60, 89, -46, 0, -38, 24, 98, -17, 77] [1, -5, 77, 57, -29, -62, 53, -49, 7, -13, -62, 35, 0, 48, 23, 79, 36, -1015, -35] [1, -75, 55, -67, 0, -32, -39, -82, 100, 97, 27, 58, -27] [1, -23, -67, 54, 25, -69, 87, -8, 92, 100, 15, -66, -6, -91, -42, -71, -19] [1, -47, -10, -95, 46, -26, -43, -58, 29, -53, -86, 66, 74, -46, -8, -84, 94, -95, 46] [1, 39, 75, 45, 2, -40, -59, -60, 97, -28, -98, 21, -41, 2, 71, 85, -38, 77] [1, 78, 34, -72, 40, -7, -29, 94, 71, 76, 43, 1, -38, 35, -46, -903, 43] [1, -67, 84, 40, -10, -29, 82, 99, -92, -47, 4, 20, -7, 52, -45, -5, 55, -7, 4536, -84] [*] Switching to interactive mode Here is your flag: flag{Viet4s_f0r_th3_win} [*] Got EOF while reading in interactive $
flag{Viet4s_f0r_th3_win}
Fractional Fractions (Kiddie Pool)
分数の計算をしている。分子と分母を入れ替え整数部分を取り出していけば、逆算できる。
#!/usr/bin/env python3 from Crypto.Util.number import * from fractions import Fraction enc = Fraction(7817806454609461952471483475242846271662326, 63314799458349217804506955537187514185318043) flag = '' while True: enc = 1 / enc n = enc.numerator d = enc.denominator div = n // d flag = str(div - 1) + flag enc -= Fraction(div) if enc == 0: break flag = long_to_bytes(int(flag)).decode() print(flag)
flag{f0r_l00ps_g0_brrrrr}
Pryby (Cryptography)
暗号処理の概要は以下の通り。
・flag: フラグの数値化 ・f: 10**6以下の素数の配列 ・state: 1設定 ・flag回、move()実行 ・stateの値を出力 ■move() ・q = 1 ・fの配列の各値pに対して以下の処理を実行 ・stateをpで割り切れなかった場合、 state = state * p // q ・q = q * p
moveが複雑な計算になりそうなので、まず追ってみる。
1回目 1 % 2 != 0 -> state = state * 2 // 1 = 2 2回目 2 % 2 == 0 -> q = 1 * 2 = 2 2 % 3 != 0 -> state = state * 3 // 2 = 3 3回目 3 % 2 != 0 -> state = state * 2 // 1 = 6 4回目 6 % 2 == 0 -> q = 1 * 2 = 2 6 % 3 == 0 -> q = 2 * 3 = 6 6 % 5 != 0 -> state = state * 5 // 6 = 5 base:1(=1):0 2倍 3倍 6倍 base:5(=5):1 2倍 3倍 6倍 base:7(=7):10 2倍 3倍 6倍 base:35(=5*7):11 2倍 3倍 6倍 base:11(=11):100 2倍 3倍 6倍 base:55(=5*11):101 2倍 3倍 6倍 base:77(=7*11):110 2倍 3倍 6倍 base:385(=5*7*11):111 2倍 3倍 6倍 base:13(=13):1000 2倍 3倍 6倍 base:65(=5*13):1001 2倍 3倍 6倍 base:91(=7*13):1010 2倍 3倍 6倍 base:455(=5*7*13):1011 2倍 3倍 6倍 base:143(=11*13):1100 2倍 3倍 6倍 base:715(=5*11*13):1101 2倍 3倍 6倍 base:1001(=7*11*13):1110 2倍 3倍 6倍 :
この流れから、回数の計算を簡単にできるかを考える。素因数分解して2, 3を除いた素数の配列を右からビットを立てると、上の流れのbaseの一番右のビット列になる。このことからmove()実行回数を算出することができる。
#!/usr/bin/env python3 from Crypto.Util.number import * from sympy import * def f(n): q = [True] * (n + 1) r = 2 while r**2 <= n: if q[r]: for i in range(r**2, n+1, r): q[i] = False r += 1 return [p for p in range(2, n+1) if q[p]] enc = 31101348141812078335833805605789286074261282187811930228543150731391596197753398457711668323158766354340973336627910072170464704090430596544129356812212375629361633100544710283538309695623654512578122336072914796577236081667423970014267246553110800667267853616970529812738203125516169205531952973978205310 assert enc % 2 == 0 assert enc % 3 != 0 assert enc % 6 != 0 fac_dic = factorint(enc) factors = [k for k in fac_dic] primes = f(max(factors)) bits = '' for p in primes: if p == 2 or p == 3: continue if p in factors: bits = '1' + bits else: bits = '0' + bits count = int(bits, 2) * 4 + 1 flag = long_to_bytes(count).decode() print(flag)
flag{functi0n_h4cking_ftw!}
MathyOracle (Cryptography)
サーバの処理概要は以下の通り。
・N: 512ビットランダム整数 ・以下の処理を600回繰り返す。 ・k, l: 数値入力(1以上10**500未満) ・f(N+l, k)を表示 ※f関数はGCDと同様
LSBから順に判明したビットデータを引いて、2のべき乗とのGCDを求め、1ビットずつNを割り出す。
import socket def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('ctf.k3rn3l4rmy.com', 2234)) data = recvuntil(s, '\n').rstrip() print data bit = '' for i in range(600): data = recvuntil(s, '\n').rstrip() print data k = pow(2, (i + 1)) if i == 0: l = 2 else: l = k - int(bit, 2) data = recvuntil(s, ': ') print data + str(k) s.sendall(str(k) + '\n') data = recvuntil(s, ': ') print data + str(l) s.sendall(str(l) + '\n') data = recvuntil(s, '\n').rstrip() print data if i < 512: if int(data.split(' ')[-1]) == k: bit = '0' + bit else: bit = '1' + bit data = recvuntil(s, '\n').rstrip() print data N = int(bit, 2) data = recvuntil(s, '?') print data + str(N) s.sendall(str(N) + '\n') data = recvuntil(s, '\n').rstrip() print data
実行結果は以下の通り。
Find my number N, and I will give you the flag. Try #1: Enter k: 2 Enter l: 2 f(N+l,k) = 1 Try #2: Enter k: 4 Enter l: 3 f(N+l,k) = 2 Try #3: Enter k: 8 Enter l: 5 f(N+l,k) = 4 Try #4: Enter k: 16 Enter l: 9 f(N+l,k) = 16 Try #5: Enter k: 32 Enter l: 25 f(N+l,k) = 32 Try #6: Enter k: 64 Enter l: 57 f(N+l,k) = 64 Try #7: Enter k: 128 Enter l: 121 f(N+l,k) = 64 Try #8: Enter k: 256 Enter l: 185 f(N+l,k) = 128 Try #9: Enter k: 512 Enter l: 313 f(N+l,k) = 512 Try #10: Enter k: 1024 Enter l: 825 f(N+l,k) = 1024 : : Try #596: Enter k: 259344723055062059907025491480697571938277889515152306249728583105665800713306759149981690559193987143012367913206299323899696942213235956742929677132122730441323862712594345230336 Enter l: 259344723055062059907025481452712247628920938720906191868968831545027534905516709756298998573832046699734176727724867434810266469697076948597428376692286336569468590498284913581881 f(N+l,k) = 259344723055062059907025491480697571938277889515152306249728583105665800713306759149981690559193987143012367913206299323899696942213235956742929677132122730441323862712594345230336 Try #597: Enter k: 518689446110124119814050982961395143876555779030304612499457166211331601426613518299963381118387974286024735826412598647799393884426471913485859354264245460882647725425188690460672 Enter l: 518689446110124119814050972933409819567198828236058498118697414650693335618823468906280689133026033842746544640931166758709963411910312905340358053824409067010792453210879258812217 f(N+l,k) = 518689446110124119814050982961395143876555779030304612499457166211331601426613518299963381118387974286024735826412598647799393884426471913485859354264245460882647725425188690460672 Try #598: Enter k: 1037378892220248239628101965922790287753111558060609224998914332422663202853227036599926762236775948572049471652825197295598787768852943826971718708528490921765295450850377380921344 Enter l: 1037378892220248239628101955894804963443754607266363110618154580862024937045436987206244070251414008128771280467343765406509357296336784818826217408088654527893440178636067949272889 f(N+l,k) = 1037378892220248239628101965922790287753111558060609224998914332422663202853227036599926762236775948572049471652825197295598787768852943826971718708528490921765295450850377380921344 Try #599: Enter k: 2074757784440496479256203931845580575506223116121218449997828664845326405706454073199853524473551897144098943305650394591197575537705887653943437417056981843530590901700754761842688 Enter l: 2074757784440496479256203921817595251196866165326972335617068913284688139898664023806170832488189956700820752120168962702108145065189728645797936116617145449658735629486445330194233 f(N+l,k) = 2074757784440496479256203931845580575506223116121218449997828664845326405706454073199853524473551897144098943305650394591197575537705887653943437417056981843530590901700754761842688 Try #600: Enter k: 4149515568880992958512407863691161151012446232242436899995657329690652811412908146399707048947103794288197886611300789182395151075411775307886874834113963687061181803401509523685376 Enter l: 4149515568880992958512407853663175826703089281448190785614897578130014545605118097006024356961741853844919695425819357293305720602895616299741373533674127293189326531187200092036921 f(N+l,k) = 4149515568880992958512407863691161151012446232242436899995657329690652811412908146399707048947103794288197886611300789182395151075411775307886874834113963687061181803401509523685376 What is N?10027985324309356950794246114380759751560638265807790049393682691985361940443278191185481431889089430472516159008145501300439836393871855272214309431648455 flag{h4cking_th3_GCD!}
flag{h4cking_th3_GCD!}
Pascal RSA (Cryptography)
暗号処理の概要は以下の通り。
・p: 20ビット素数 ・triangle[-1]: (x + 1) ** pのxの係数の配列 ・code: triangle[-1]の各要素を2で割った余りを文字列として連結 ・d: codeを2進数として数値化 ・P, Q: 512ビット素数 ・N = P * Q ・e = pow(d,-1,(P-1)*(Q-1)) ・enc = pow(flag, e, N)
p, enc, Nがわかっている。dを算出できれば、フラグを復号できる。triangleの原理は二項定理である。それを2で割った余りまで高速に算出できればよい。
http://www.xn--u9jtgqbzf1fn77phnzag74e.jp/pascul-nature.htmlを見ると、フラクタル図形のことが載っている。これが使えないか考える。
p = 0, 1, 3, 7, 15, 31(2**n -1)の場合、すべて1。 p = 1: 11 p = 17: 110000000000000011 p = 49: 11000000000000001100000000000000110000000000000011 p = 305: 110000000000000011000000000000001100000000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000000001100000000000000110000000000000011
下位ビットから見ていき、ビット立っている場合、前にビットが立っている場合のビット列で0を挟み込んで、長さがp+1になるようにすれば、dを導くことができる。あとはその値を使って復号する。
#!/usr/bin/env python3 from Crypto.Util.number import * with open('challenge.txt', 'r') as f: p = int(f.readline().rstrip().split(' ')[-1]) enc = int(f.readline().rstrip().split(' ')[-1]) N = int(f.readline().rstrip().split(' ')[-1]) bits = bin(p)[2:] code = '' for i in range(len(bits)): b = bits[-i-1:] if b[0] == '1': l = int(bits[-i-1:], 2) + 1 if i == 0: code = '11' else: code = code + '0' * (l - len(code) * 2) + code d = int(code,2) m = pow(enc, d, N) flag = long_to_bytes(m).decode() print(flag)
flag{1ts_ch00se_a11_a10ng??}
1-800-758-6237 (Cryptography)
$ nc ctf.k3rn3l4rmy.com 2233
4da7bd1c438625ef764fcab8cf71467aa584a0f9dd98b84d4c7eb37dbdda3b6e1c6ba708b52579f2d4b77e440ba0b25fbcd2e22d777aaab126ef7fbd96f0190ded8d5f507d7eb9077a094ebbaa8637ab43378f7a7c9809d512757c1b25b61b7eb60cd2dd7fbe4d1a92ad5d84d16e25f07fd73c24ed75aa0d25aec5a492cd4f05f28e72ba9418f61d5a8a0aaee0873c2b36a423de1e983890ecef4efef7b575ea9b81d4b44f02f4e7d6136de2d91bd31ee443129c91a2b82263a705f88e5ad550c1
4de1b80951dc6bf17e58cae889790211ea9af0ea9e8ce0657d60e65dbdaf503e0f63e316b54e37e4cfae242f15eea444a588fc2d777aaab126ef27e894b30d55f6cc5f443e79ae076e5143b9e9a92ca82d3dc2413f82269b12757c002fee167cf54d96dd0ab70c2cd3e971ddc85566f77cd73665db68b45278db90a2d1d9175fddc919a28d23b55e4ed217eebaac2e6c09be6dc805816289c38157e0d8ed78e8d8aeadd3200390e8d56667b69b24a95bac4e10d991a2b87c3da846ecd6479f07c1
4da7bd515cde28ed35589bb8cf71467aa5efeeefc681e2264c7eb336ed9c787a4463e316b54e29a19cb33c367ea0ea52be91a626243fb2f248e56ad3d7a92255e08f1c506674ac1c684a49acdfb435872d3d8f7a7c9809d51370641914f14b67ec23c99044a1173589b771c3d16e25f07fd7263dd66af7163cc184fadcdb541ca8fb60e3da0eed04009435adcfe9254057ea35c507c241f799ba68bde3ed2cb0d5acee905502eed3f45b27ac9b24a95bac4e10d991a2b87c3da846ecd6479f07c1
4da7bd515cde28ed35589ba69f621b4bbb9af0ea9e8ce0657d60e65dbdaf503e0f63e316fe6b6fe9cded354415e5e142a4cb8968243fb2f248e56ad3ccbe0f16f4d7440a2862b75d340878e1e4ab6fa836378f7a7c9809d512757c1b61f80d65af5696dd7fbe4d1a92ad5d84953908f42599207ec232aa0d25db90a2d1d91733b3d072ba9418f61d5a8a0aaee0873c2b36bd6dc805816289ecef4e8bb9a36ef3c1f4d4b44f02f4e7ac5625efdb5ea95bac4e10d991a2f7322bb35fb699479f07c1
4de1b80951dc6bf17e589bb8d1740052e184f0a1d09afb7c272be636ed9c787a4443e363952579f2d4b77e3140a5f402e69ca4652624a3c34daa2cf88ee92255e08f1c506674ac1c6e0b16a5e78637ab43378f7a7c9809d512757c1b25fb2061ec23c9d40ab70c2cd3e95d84953908f43b967873c071ee4c25aedeb4cac04d46b3d072baca4cf42b679454fae2b1013536bd189d5d8c60cac3f44efef7b575ea9b81d4b44f02f49de2403ef68124d31ee443129cb1efe7322bb55ff099479f07c1
4da7bd1c439875fc2b7ed4cdba3a1649f8deeebfd589a6386c0be636ed9c787a4423fd46a6666daa9cb33c360ba0b25fbcd28968243fe8e60be27da696aa4c11e3a244536674ac446e5178aff2f362aa75238f2f78c0539b122d7a0025fb5568ad1588907fbe5421d1aa5e9ac82033eb668d78488376ed5278c2abbd92cd4f05f28e19a28d23b50075d30aaee0873c2b36bd189d23b741f799ba68bde3ed2cb0d5acee905502eed3f45b27ac9b24a95bac4e10d991a2b82263f04bee95438f07c1
4da7bd1c438625ef764fcab8cf71585fe3c7b4a180c2f67e643af85da38a63631e28e363953b7ce189f3354415e5ea52be91a626777aaaa81df964fccce9221bf6d711522560f41c6e0b16a5e78637ab3637d7777edb269b1275204e39f50f26a94d96dd7fbe4d1a92e94ac2927a7df77cc93c24ed75aa0d3c9586b9c8830e33b3d072baca56e00643d054aee0f2156d14fe6df33adc599099ba68bde3ed43abe581d4b44f02f49de2403ef68124a95bac4e48d293a7ad7c2bb55ff099479f07c1
4da7bd1c439875fc2b7ecae889790211a5ef85bfd589a6386c0be63da89a79393166a513a47f2ceeda9865767eeea444a588fc687c6ab0eb09a17fbd90eb1318db905f443e79ae072d2416a5f3f362aa75238f2a60c22692542f39002fee167cf523d2de52ba0e6f92b7719a9f783ee9258e2627987cec0f66db848ff59d765fdd957996ed28ae1058c90eb4a0f2156d14fe6d9c47c276d1daae3084c3e626b0d5acee905556b6d8f65e32f2915e9d08ff5a48cbcbaaaf3f29f025b69841cc0ae1
4da7bd1c12c833f46f159ba69f621b4bbb9af0a1d09afb7c272be65dbdaf503e4466a54ba4257ce189f3354415e5e142a4cbfc682467b2a826ef7fbd96aa4c11e3a244531374ac1c685143b9e9a92ce97234fa733dae48911370641961f80d65af56a7d70ab70c2cd3e91a9a9f783ee925966148836cb402649884fae7da495cf2fb07adcc15f45e679435adbabc03760da4189d23b741f783ee2afef7b575ea9b8ed7c15556b6def6186de2d91bd31ee443129c91a2f7322bb35fb699479f07c1
4da7bd1c438625ef764fcab8cf71467aa5ef85a1d09afb7c277ef878fb8761200f63e316b54e37e4cfae242f15e5e11ca88abf7c7c7aaab126a169fe8faa571bf6cc05506674ac446e5116a5aabd74b16c79c24124950b96106e3b5914f80d26bb0e91ca0ae20874cda4719a9f783ee92590613dd66af7163caec5becb9d535fa8c05fa0ce56db191ecb4dc1a1ac2e6c09be37f33ac276d1daae30e0d8f443abe581ad840d5bb49dd56667b69b24a95bac4e10d991e4b92430aa05f099479f07c1
01afae12488627b77b4d89fcd17c1311f5dcadfb9e8fe938392bf878fb8761205a43e363953b7caad9b53d750ba5f402adb9e22d777ae8e60be27da68ee92255e08f1c506674ac1c6e0b16e1e4ab6fa8363dc2413fdb1d8d0934205961f80d65af56a7de52e25421d1aa5e9a8d3b39fe509061488376ed5278c2abbd8cc21708f0cd5de38d23b50075d30aaee0873c2b36bd189d23b741f799ba68bde3ed2caa81f4e3921642eee7d6136de2d95e9d08ff5a48d991a2b82263f04bee95438f07c1
01afae12488627f17e1584fe9260585cea9af0a1d09afb7c272be65dbdaf503e0f63e316fe6b6fe9cded354415e5ea52be91a626777ae8e60be27da68ee9221bf6cc05507d3aba5f770b0da5e78637ab4379c16c6781539b1275204e39f50f26a94d969044a1173589a471ddc85566f77cc93c24ed75aa0d25aec5a492cd4f05f28e72baca4cae1058c90eb4e0f2156d14fe6df33adc599099ba68bde3ed43abe5f4e3921642eee8d56667b69b24a95bac4e48d293a7ad7c2bb55ff099479f07c1
4da7f61f4ac531b77e589bb8cf71467aa5efeeefc681e2264c7eb37dbdda3b6e1c6ba708b54e29a19cb33c2f45b6a946e6cb8968243fe8e60be27da696aa4c11e3a25f443e79ae072f0878afaabd74b16c79d72f78c017d50436635a61fb2061ec23c9d453f91a37cab30484953908f43b966148987cec0f66dbc5a492cd4f05f28e72baca4cf42b679435b4f4aa186f57bd1886139a7bd399ef4e8bc0ed78e8d8aeadb44f18a0c5ef427db69b24a95bac4e10d991a2b82263f04bee95438f07c1
4da7bd1c12c833f46f159bb8cf71467abbcab6e2c4c2a64d4c7eb37dbdda704b5a23f608b07d74f097b33c2f45b6a946e6cb8968243fb2a81df964fcccaa4c11e3a244531374ac1c684a0daff2b076f27234fa346a83108f4a29397561f80d65af56c9d453f91a37cab30484952033eb668d7824ed75aa4c72839da092c21708f0cd5de38d23ae1058c90eb4a1f2156d14fe6dd8289b6693c3f47ea6fab736c5fceaccd3200390e8d56667b69b24a95bac4e10d991a2b87c3da846ecd6479f07c1
4de1b80951dc6bf17e589bb8cf71467abbcab6e2c4c2a6266938bb6ca3af3b6e1c6ba708953b7ce197a3266c51eef402adb9e22d7c6ab0eb09a12cf88ee9221bae9907493c3aac1c6e0b16a5e78637ab4379c16c6781539b12757c1b25fb2061ec569cc849a3541a92ad04d4896327b37cc93c3dd66af7163cc2abbd8cc20e33b3d072baca4cf42b679454fae2b1013536bd189d23c276d1daae308bc0932caa9bbaf5890f18f4e7ac5625efdb5ea95bac4e10d991a2b82273be5df58c199f07c1
4da7bd1c439875fc2b1584fe9260587aa5efeeefc681e2264c7eb37da38a63631e28e316b52579f2d4b77e4415e5e142a4cbfc682467b2a826ef7fbd96aa4c11e3a25f443e79ae072f0878aff2f362aa75238f2f78c017984a2078433bb62026bb0e91ca0abe5421d1aa5e9ac85566f77cd73665db68b45278db90a2d1d9175fdd8e49bbd70cae191ecb54fae2b101354ed176d85d8c60cac3f445a7e7f76cc5fceaccd3200390e8d56667b69b24a95bac4e10d991a2f7322bb35fb699479f07c1
4da7bd1c43986bf96d5690a6cf71467abbcab6e2c4c2a64d4c7eb37dbdda704b5a23fd46a6666daa9cb33c367ea0b207bc88e7623124a6f010fb27d3d7a9571bf694050a1374ac1c684a49acdfb435872d3dd62a24950b96106e64002fee167cf54fa79044a1173589ae04d4896327b33b966148836cc11562c1deb4cac04d46f28e49bbd70cae2b679435adbabc03760da4189d23b741f783f47ea6fab736aa818ed7ca1b40adc7ac136de2d91b8916f35e48d293a7ad7c63a725b69841cc0ae1
4da7bd1c12c833f46f159bb8d1740052e184f0ea80a9a6266938bb6ca3af503e4466a54ba4257ce197a3266c51eef402adb9e22d7724a6f010fb27f8ccbe0f16f4d71d131374ac1c6e0b16a5e78637ab4337d72f24950b96106e7c1b25fb2061ec569cc849a3541a92ad5d9a9f783ee925c93c24ed75aa0d3c9586b9c8830e33b3d072baca56e00643d054aebabc03760da437f33adc5989d7ac73a4b9f443abe581d4b44f02f4e7d6136de2d95e9d08ff5a48d991a2b87c3da846ecd6479f07c1
4da7bd1c439875fc355b92e58b3a467aa5ef85bfd589a6386c0be63da8c475780772fd56bc2579f2d4b77e367ea0b207bc88e7623151f3f153ef7fe596f0221bf6cc5f443e79ae07684a0daff2b076f27234fa7324950b96106e39002fee167cf523c9d40ab70c2cd3e95d8495397dfd7d94223ded75aa0d25aec5fadcdb541ca8d007adcc15f45e75d30aaee0873c2b36bd189d23b741f799ba68bde3ed2caa81f4e3921642eee7ac5625efdb5ea95bac0006c488bef7322bb55ff099479f07c1
01afae12488627f17e1584fe9260585cea84a0f9dd98b838392be65dbdaf503e0f63e316b54e29a19cb33c367ea0b207bc88e7623124a6f010fb27d3d7f0190ded8d5f536674ac446e5178e1e4ab6fa836378f7a7c9809d512757c1b25fb2061ec23c9d453e71076fcae1adbd16e25f07fd76148836cc1153c9586b9c883495cf2fb60fdf54fae1058c90eb4cfe925402eda6dc80581628983ee2a84c3e636fec3b7f7ca4556b6d8f65e7de2d91d8950f35e48d293a7ad7c63a705f88e5ad550c1
4da7bd1c43986bf96d5690a6cf71467abbcab6e2c4c2a64d4c7eb336ed9c787a4463e316b52579f2d4b77e4415e5e11ca88abf7c7c7aaab126ef7fbd96f0190ded8d5f507d7eb9722f080daff2b076f24337d72f78c017d50436635a61fb5568ad1588907fbe4d1a92ad5d84952033eb668d7824ed32fa147f81debd8cc20e33b38e49bbd70cae0075d30aaee0f2156d14fe6df33adc5990ecef4e8bc0932cb0d5acee905502f4e7d61833f4c204d35bac4e10d991a2b82263a725b69841cc0ae1
4da7f61f4ac531b77e1584fe9260585cea9af0ea80a9a64d4c60b66ee09e3b3e0f63e308b07d74f097f3354415e5e11ca88abf7c7c7aaab126ef27e894b30d55f6cc050a2862b75d340b16a5e78637ab4337d72f78c017984a2078433bb62061ec569cc849a3541a92ad5d84953908b36b8f3b679875aa0d25aec5fadcdb541ca8d072baca4cae1058c90eb4e0873c2b36a423de1e983890ecef4e8bc0932caa818ed7ca1b40adc7ac136de2d95e9d08ff5a48d991a2b82263f04bee95438f07c1
4da7f61f4ac531b77e589ba69f621b4bbb9af0ea80a9a64d4c7eb336ed9c787a4463e308b07d74f097f335440ba0b25fbcd2e22d777aaab126ef7fbd96aa4c11e3a244531374ac1c684a49acdfb435873637d7777edb48d50436635a61f20c38b14fa7d714b84d1a92b771c3d16e25f07fd72627c232fa147f81de8ff59d7646e6d644b9944fdb4500c40cf7e0f2253519fc2edc5db74189d7ac73a4b9932caa818ed7c14518a0c5ef427de2d91b8916f35e48d293a7ad7c63f04bee95438f07c1
4da7bd1c438625ef764fcab8cf71467aa584a0f9dd98b84d272ea075f9c4503e0f63e316b54e29a19cb33c367ea0b207bc88e7623151e8e60be27da6d7a92255e08f1c506674f4496c1257e1f2e870e93637d7777edb17983f29204e39f50f26ec23c9d453e71076fcae1adbc85566ed508e2627c247d34c72839da0929d765fa8c05fa0ce56db457eff2dcababc03760da4779c47b838c7c1b76afec3e626fec3f4e3921642eed8f65e7de2d91d8950f35e48d293a7ad7c63f04bee95438f07c1
4da7bd515cde28ed35589bb8cf71467aa5ef85a1d09afb7c277ef878fb8761200f63e316b52579f2d4b77e4415eea444a588fc2d7c6ab0eb09a12cf88ef0190ded8d5f131374ac077a094ebbaae876a82d3d8f7a7c9809d5071b3b5914f80d3da94d96dd7fbe4d1a89a75cd98b2066f77cd73665db68b45278c2abbd8cc20e33b38e49bbd70cae0075d30aaee0873c2b36bd1886139a7bd399ef30b0e1ae6cb0e581d4b44f18a0c5ef427db69b24a95bbc4e10df91e4e7322bb55ff099479f07c1
4da7bd515cde28ed35589ba69f621b4bbb9af0ea80a9b8687f23a236bdaf503e4466a54ba4257ce189ed307748b4ea02adb9fc682467b2a84daa2cf88ee9221bf6cc5f443e79ae076e0b16a5e7f362aa75238f413f82269b12757c1b25fb5568ad1588907fbe4d1a92e94ac2927a7df77cc93c24ed32fa147f81debd8cc20e33b3d072baca4cf42b00c40cf7e0f23c2b36bd189d23b741f783ee2a84c3e626fec3b1ad840d5bb49df65e7de2d91d8950f35e48d293a7ad7c63a725b69841cc0ae1
4de1b80951dc6bf17e589ba69f621b4bbb9af0ea80c2f67e643af85da38a63631e28e308b07d74f09786153140a5ea52be91a626623aa3c34daa2cf8ccbe0f16f4d71d131374ac1c6e0b0daff2b076f22d3dc2346a83108f4a1b3b5914f80d3da94d969044a1173589a404d4896327b3509061488376ed4c72839da0929d535fddc919a28d23b50075d30aaee0873c3519fc2edc5ddc38c7c1b76afed8f443abe581d4b44f02f4e7d6136daccf06900abc4e10d991a2f7322bb35fb699479f07c1
01afae12488627b77b4d89fcd17c135cea9af0ea80a9a64d4c7eb37dbdda3b6e1c6ba708b54e37e4cfae242f15e5e142a4cb8926327cabf253ef7fbdccbe0f16f4d705507d7eb9722f0878aff2e870f27821cc6e24c017983f29397561f80d65af56c9d453e71076fce94ac2927a7df42599207ec232aa0d25aec5fadcdb541ca8d007adcc15f45e75d30aaee0873c2b36bd189d23b741f783ee2a84b9a36ef3c1f4d7ca1b40adc7ac137de2d91d8950ac4e10d991a2b82263f04bee95438f07c1
4da7f61f4ac531b77e589ba69f621b4bbb9aeeefc681e226392be65dbdaf50200a70be52fe3b7ce189f3354415eea444a588fc2d777aaaa81df964fccce9221bf6cc050a2862b75d340b16e1e4ab6fa8363dc2413f8226d50436635a61f80d3da94d96dd7fbe4d1a92ad04d4896327b37cc93c24ed75aa0d25aedeb4cac04d46b3d072baca56e00643d054aee0873c2b36bd189d23b741f799ba68bde3ed2caa818ed7c14518a0c5ef427de2d91b8916f35e48d293a7ad7c63a725b69841cc0ae1
AES-CTRモードでflagの中に*drip*を16回入れていき、暗号化する。暗号化するたびに暗号化結果が異なるので、添付のコードのsorted関数は使われないと思われる。
複数のデータを取得し、調整しながら復号する。最終的なコードは以下の通り。
#!/usr/bin/env python3 from Crypto.Util.strxor import strxor def del_drop(s): for i in range(10): s = s.replace(b'*drip*', b'') return s encs = [ '4da7bd1c438625ef764fcab8cf71467aa584a0f9dd98b84d4c7eb37dbdda3b6e1c6ba708b52579f2d4b77e440ba0b25fbcd2e22d777aaab126ef7fbd96f0190ded8d5f507d7eb9077a094ebbaa8637ab43378f7a7c9809d512757c1b25b61b7eb60cd2dd7fbe4d1a92ad5d84d16e25f07fd73c24ed75aa0d25aec5a492cd4f05f28e72ba9418f61d5a8a0aaee0873c2b36a423de1e983890ecef4efef7b575ea9b81d4b44f02f4e7d6136de2d91bd31ee443129c91a2b82263a705f88e5ad550c1', '4de1b80951dc6bf17e58cae889790211ea9af0ea9e8ce0657d60e65dbdaf503e0f63e316b54e37e4cfae242f15eea444a588fc2d777aaab126ef27e894b30d55f6cc5f443e79ae076e5143b9e9a92ca82d3dc2413f82269b12757c002fee167cf54d96dd0ab70c2cd3e971ddc85566f77cd73665db68b45278db90a2d1d9175fddc919a28d23b55e4ed217eebaac2e6c09be6dc805816289c38157e0d8ed78e8d8aeadd3200390e8d56667b69b24a95bac4e10d991a2b87c3da846ecd6479f07c1', '4da7bd515cde28ed35589bb8cf71467aa5efeeefc681e2264c7eb336ed9c787a4463e316b54e29a19cb33c367ea0ea52be91a626243fb2f248e56ad3d7a92255e08f1c506674ac1c684a49acdfb435872d3d8f7a7c9809d51370641914f14b67ec23c99044a1173589b771c3d16e25f07fd7263dd66af7163cc184fadcdb541ca8fb60e3da0eed04009435adcfe9254057ea35c507c241f799ba68bde3ed2cb0d5acee905502eed3f45b27ac9b24a95bac4e10d991a2b87c3da846ecd6479f07c1', '4da7bd515cde28ed35589ba69f621b4bbb9af0ea9e8ce0657d60e65dbdaf503e0f63e316fe6b6fe9cded354415e5e142a4cb8968243fb2f248e56ad3ccbe0f16f4d7440a2862b75d340878e1e4ab6fa836378f7a7c9809d512757c1b61f80d65af5696dd7fbe4d1a92ad5d84953908f42599207ec232aa0d25db90a2d1d91733b3d072ba9418f61d5a8a0aaee0873c2b36bd6dc805816289ecef4e8bb9a36ef3c1f4d4b44f02f4e7ac5625efdb5ea95bac4e10d991a2f7322bb35fb699479f07c1', '4de1b80951dc6bf17e589bb8d1740052e184f0a1d09afb7c272be636ed9c787a4443e363952579f2d4b77e3140a5f402e69ca4652624a3c34daa2cf88ee92255e08f1c506674ac1c6e0b16a5e78637ab43378f7a7c9809d512757c1b25fb2061ec23c9d40ab70c2cd3e95d84953908f43b967873c071ee4c25aedeb4cac04d46b3d072baca4cf42b679454fae2b1013536bd189d5d8c60cac3f44efef7b575ea9b81d4b44f02f49de2403ef68124d31ee443129cb1efe7322bb55ff099479f07c1', '4da7bd1c439875fc2b7ed4cdba3a1649f8deeebfd589a6386c0be636ed9c787a4423fd46a6666daa9cb33c360ba0b25fbcd28968243fe8e60be27da696aa4c11e3a244536674ac446e5178aff2f362aa75238f2f78c0539b122d7a0025fb5568ad1588907fbe5421d1aa5e9ac82033eb668d78488376ed5278c2abbd92cd4f05f28e19a28d23b50075d30aaee0873c2b36bd189d23b741f799ba68bde3ed2cb0d5acee905502eed3f45b27ac9b24a95bac4e10d991a2b82263f04bee95438f07c1', '4da7bd1c438625ef764fcab8cf71585fe3c7b4a180c2f67e643af85da38a63631e28e363953b7ce189f3354415e5ea52be91a626777aaaa81df964fccce9221bf6d711522560f41c6e0b16a5e78637ab3637d7777edb269b1275204e39f50f26a94d96dd7fbe4d1a92e94ac2927a7df77cc93c24ed75aa0d3c9586b9c8830e33b3d072baca56e00643d054aee0f2156d14fe6df33adc599099ba68bde3ed43abe581d4b44f02f49de2403ef68124a95bac4e48d293a7ad7c2bb55ff099479f07c1', '4da7bd1c439875fc2b7ecae889790211a5ef85bfd589a6386c0be63da89a79393166a513a47f2ceeda9865767eeea444a588fc687c6ab0eb09a17fbd90eb1318db905f443e79ae072d2416a5f3f362aa75238f2a60c22692542f39002fee167cf523d2de52ba0e6f92b7719a9f783ee9258e2627987cec0f66db848ff59d765fdd957996ed28ae1058c90eb4a0f2156d14fe6d9c47c276d1daae3084c3e626b0d5acee905556b6d8f65e32f2915e9d08ff5a48cbcbaaaf3f29f025b69841cc0ae1', '4da7bd1c12c833f46f159ba69f621b4bbb9af0a1d09afb7c272be65dbdaf503e4466a54ba4257ce189f3354415e5e142a4cbfc682467b2a826ef7fbd96aa4c11e3a244531374ac1c685143b9e9a92ce97234fa733dae48911370641961f80d65af56a7d70ab70c2cd3e91a9a9f783ee925966148836cb402649884fae7da495cf2fb07adcc15f45e679435adbabc03760da4189d23b741f783ee2afef7b575ea9b8ed7c15556b6def6186de2d91bd31ee443129c91a2f7322bb35fb699479f07c1', '4da7bd1c438625ef764fcab8cf71467aa5ef85a1d09afb7c277ef878fb8761200f63e316b54e37e4cfae242f15e5e11ca88abf7c7c7aaab126a169fe8faa571bf6cc05506674ac446e5116a5aabd74b16c79c24124950b96106e3b5914f80d26bb0e91ca0ae20874cda4719a9f783ee92590613dd66af7163caec5becb9d535fa8c05fa0ce56db191ecb4dc1a1ac2e6c09be37f33ac276d1daae30e0d8f443abe581ad840d5bb49dd56667b69b24a95bac4e10d991e4b92430aa05f099479f07c1', '01afae12488627b77b4d89fcd17c1311f5dcadfb9e8fe938392bf878fb8761205a43e363953b7caad9b53d750ba5f402adb9e22d777ae8e60be27da68ee92255e08f1c506674ac1c6e0b16e1e4ab6fa8363dc2413fdb1d8d0934205961f80d65af56a7de52e25421d1aa5e9a8d3b39fe509061488376ed5278c2abbd8cc21708f0cd5de38d23b50075d30aaee0873c2b36bd189d23b741f799ba68bde3ed2caa81f4e3921642eee7d6136de2d95e9d08ff5a48d991a2b82263f04bee95438f07c1', '01afae12488627f17e1584fe9260585cea9af0a1d09afb7c272be65dbdaf503e0f63e316fe6b6fe9cded354415e5ea52be91a626777ae8e60be27da68ee9221bf6cc05507d3aba5f770b0da5e78637ab4379c16c6781539b1275204e39f50f26a94d969044a1173589a471ddc85566f77cc93c24ed75aa0d25aec5a492cd4f05f28e72baca4cae1058c90eb4e0f2156d14fe6df33adc599099ba68bde3ed43abe5f4e3921642eee8d56667b69b24a95bac4e48d293a7ad7c2bb55ff099479f07c1', ] ct = [] for i in range(len(encs)): ct.append(bytes.fromhex(encs[i])) #### guess #### key = b'' pt = b'flag{' key += strxor(ct[0][:5], pt) pt = b'rip' key += strxor(ct[2][5:8], pt) pt = b'ip*' key += strxor(ct[0][8:11], pt) pt = b'rip*' key += strxor(ct[11][11:15], pt) pt = b'rip*' key += strxor(ct[5][15:19], pt) pt = b'rip*' key += strxor(ct[0][19:23], pt) pt = b'rip*' key += strxor(ct[6][23:27], pt) pt = b'a44' key += strxor(ct[0][27:30], pt) pt = b'rip' key += strxor(ct[6][30:33], pt) pt = b'ip' key += strxor(ct[0][33:35], pt) pt = b'ip*' key += strxor(ct[8][35:38], pt) pt = b'rip*' key += strxor(ct[3][38:42], pt) pt = b'ip*' key += strxor(ct[10][42:45], pt) pt = b'a44' key += strxor(ct[4][45:48], pt) pt = b'ip*' key += strxor(ct[1][48:51], pt) pt = b'ip*' key += strxor(ct[4][51:54], pt) pt = b'rip*' key += strxor(ct[7][54:58], pt) pt = b'ip*' key += strxor(ct[6][58:61], pt) pt = b'ip*' key += strxor(ct[1][61:64], pt) pt = b'ip*' key += strxor(ct[0][64:67], pt) pt = b'rip*' key += strxor(ct[6][67:71], pt) pt = b'rip*' key += strxor(ct[11][71:75], pt) pt = b'rip*' key += strxor(ct[1][75:79], pt) pt = b'rip*' key += strxor(ct[7][79:83], pt) pt = b'rip*' key += strxor(ct[11][83:87], pt) pt = b'rip*' key += strxor(ct[10][87:91], pt) pt = b'1n' key += strxor(ct[0][91:93], pt) pt = b'rip*' key += strxor(ct[1][93:97], pt) pt = b'rip*' key += strxor(ct[9][97:101], pt) pt = b'rip*' key += strxor(ct[2][101:105], pt) pt = b'ip*' key += strxor(ct[5][105:108], pt) pt = b'drip*' key += strxor(ct[9][108:113], pt) pt = b'drip*' key += strxor(ct[3][113:118], pt) pt = b'rip*' key += strxor(ct[7][118:122], pt) pt = b'drip*' key += strxor(ct[1][122:127], pt) pt = b'drip*' key += strxor(ct[10][127:132], pt) pt = b'drip*' key += strxor(ct[2][132:137], pt) pt = b'rip*' key += strxor(ct[1][137:141], pt) pt = b'drip*' key += strxor(ct[8][141:146], pt) pt = b'drip*' key += strxor(ct[0][146:151], pt) pt = b'3_1T' key += strxor(ct[0][151:155], pt) pt = b'ip*' key += strxor(ct[2][155:158], pt) pt = b'ip*' key += strxor(ct[8][158:161], pt) pt = b'rip*' key += strxor(ct[5][161:165], pt) pt = b'p*' key += strxor(ct[11][165:167], pt) pt = b'drip*' key += strxor(ct[2][167:172], pt) pt = b'0PP!:dropl' key += strxor(ct[1][172:182], pt) pt = b'rip*' key += strxor(ct[7][182:186], pt) pt = b'drip*' key += strxor(ct[10][186:191], pt) pt = b'p*' key += strxor(ct[7][191:193], pt) for c in ct: print(strxor(key, c[:len(key)])) print('************************************************') for c in ct: print(del_drop(strxor(key, c[:len(key)]))) print(f'{len(key)} / {len(ct[0])}')
最終的な復号結果は以下の通り。
b'flag{*drip*44a4A4*drip*AA4aa44*drip*a*drip*A*drip*4!!th3_dr1p*drip*p1ng*drip*_1s_d*drip*r1v1n*drip*g_m3_1ns4*drip*n3_m4k3_1t*drip*_s*drip*t0p_M4K*drip*3_1T*drip*_ST000PP!:dro*drip*plet:}*drip*\n' b'f*drip*lag*drip*{44a*drip*4A4AA4aa44aA*drip*4*drip*!!th3_d*drip*r1*drip*p*drip*p1ng_1s_dr1v*drip*1ng*drip*_m3_1ns*drip*4n*drip*3_m4k3_1*drip*t_st0*drip*p_M4K*drip*3_1T_ST000PP!:drople*drip*t:}\n' b'fla*drip*g{44a4A4A*drip*A4a*drip*a44aA4!!th3_d*drip*r1pp1ng_1s_*drip*dr1v1ng_m3_1n*drip*s4n3_m4k3_1*drip*t_s*drip*t*drip*0p*drip*_M*drip*4K3_1T_*drip*ST*drip*0*drip*0*drip*0PP!:drople*drip*t:}\n' b'fla*drip*g{*drip*44a*drip*4A4AA4aa44*drip*aA4!!th3_dr1pp1ng_*drip*1*drip*s_*drip*d*drip*r1v1*drip*ng_m3_1ns4n3_m*drip*4k3*drip*_1t_s*drip*t0p_M4K3*drip*_1T_*drip*ST000P*drip*P!:dropl*drip*et:}\n' b'f*drip*lag{4*drip*4*drip*a4*drip*A4AA*drip*4aa44*drip*aA4!!th3_*drip*dr1pp1ng_1s_d*drip*r1v1ng_m3_1n*drip*s4n3_m4k*drip*3_*drip*1t_st0p_M4*drip*K3_1*drip*T*drip*_ST000*drip*P*drip*P!:droplet:}\n' b'flag{44a4A4AA*drip*4aa44aA4*drip*!*drip*!th3*drip*_dr1*drip*pp1ng_1s*drip*_dr*drip*1v1*drip*ng*drip*_m*drip*3*drip*_1ns4n3_m*drip*4k3_1t_st0p_M4K3_1T_ST*drip*0*drip*0*drip*0PP!:droplet:*drip*}\n' b'flag{*drip*44a*drip*4*drip*A*drip*4AA4aa44aA4!*drip*!th*drip*3_dr*drip*1pp1ng_1s*drip*_dr1*drip*v1ng_m3_1*drip*ns4n3_m4k*drip*3_1t_st*drip*0p*drip*_M4K3*drip*_1T_ST000*drip*PP!:d*drip*roplet:}\n' b'flag{44a4A*drip*4AA4aa44aA4!!th3_dr1pp1ng_1s_*drip*d*drip*r1v1ng_m*drip*3_1ns*drip*4n3_m4k3*drip*_*drip*1t_*drip*st0*drip*p_M4K3_1T_ST*drip*0*drip*00*drip*PP!:*drip*droplet:*drip*}*drip*\n*drip*' b'flag*drip*{*drip*44*drip*a4A4AA4*drip*aa44aA4!!th3*drip*_dr1pp1ng_1s_dr1v*drip*1ng_m3_1ns4n3*drip*_m*drip*4*drip*k3_1t*drip*_st0p_*drip*M4K3*drip*_1T_ST000*drip*PP!*drip*:dro*drip*pl*drip*et:}\n' b'flag{*drip*44a4A4AA*drip*4*drip*aa44aA*drip*4!!*drip*th3_*drip*dr1pp*drip*1n*drip*g_*drip*1s_dr*drip*1v1ng_*drip*m3*drip*_1ns4n3*drip*_m4k3_1t_st0p_M*drip*4K3_1T_*drip*ST000PP!:drop*drip*let:}\n' b'*drip*f*drip*la*drip*g{44a*drip*4A4AA4a*drip*a44aA4!!t*drip*h3_*drip*dr1pp1*drip*ng_1*drip*s*drip*_dr1*drip*v1ng_m3_1ns4n3_m4k*drip*3_1t_st0p_M4K3_1T_ST*drip*000*drip*PP!:dr*drip*oplet:*drip*}\n' b'*drip*fla*drip*g{44*drip*a4A4AA4aa44*drip*aA4!*drip*!t*drip*h3_dr1pp1*drip*ng_1s_*drip*dr1*drip*v1n*drip*g_m3_1ns4n3_m4k3_1t*drip*_st0*drip*p*drip*_M4K3*drip*_1T*drip*_ST000PP!:d*drip*roplet:}\n' ************************************************ b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' b'flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}\n' 193 / 193
flag{44a4A4AA4aa44aA4!!th3_dr1pp1ng_1s_dr1v1ng_m3_1ns4n3_m4k3_1t_st0p_M4K3_1T_ST000PP!:droplet:}
Non-Square Freedom 1 (Cryptography)
暗号化した結果がP**8の倍数になり、正常に復号できない。pow(C, D, N) == pow(C, D, Q*R)として復号する。
#!/usr/bin/env python3 from Crypto.Util.number import * def unpad(m): m >>= (512//8) return m n = 68410735253478047532669195609897926895002715632943461448660159313126496660033080937734557748701577020593482441014012783126085444004682764336220752851098517881202476417639649807333810261708210761333918442034275018088771547499619393557995773550772279857842207065696251926349053195423917250334982174308578108707 e = 65537 c = 4776006201999857533937746330553026200220638488579394063956998522022062232921285860886801454955588545654394710104334517021340109545003304904641820637316671869512340501549190724859489875329025743780939742424765825407663239591228764211985406490810832049380427145964590612241379808722737688823830921988891019862 DC = 58324527381741086207181449678831242444903897671571344216578285287377618832939516678686212825798172668450906644065483369735063383237979049248667084304630968896854046853486000780081390375682767386163384705607552367796490630893227401487357088304270489873369870382871693215188248166759293149916320915248800905458 assert GCD(DC, n) != 1 P8 = GCD(DC, n) QR = n // P8 M = DC % QR flag = long_to_bytes(unpad(M)).decode() print(flag)
flag{y34_th1s_1s_n0t_h0w_mult1pr1m3_RS4_w0rks_buddy}