Field Rules - volgaCTF-2025 - Crypto

Alexander Myasnikov

2025-04-05 2025-04-14 1580 слов 7 минут

Содержание

1 Исходные данные

Описание
Field is the goat, but what about…

Файлы
field-rules.zip

2 Анализ файла chall.py

Посмотрим на файл chall.py:

from functools import reduce
from operator import mul
from os import urandom

from Crypto.Util.number import getPrime

from secret import flag

ROUNDS, m, k = 512, 20, 78
key = int.from_bytes(flag)
target_bl = len(flag) * 8
prime_base = [getPrime(m) for _ in range(-(-target_bl // m) + 1)]
n = reduce(mul, prime_base, 1)
e_len = -(-n.bit_length() // 8)

assert key < n


def encrypt(m: bytes, key: int) -> bytes:
    e = int.from_bytes(m)
    for _ in range(ROUNDS - 1):
        e += key
        e = pow(e, k, n)
    e = (e + key) % n
    return e.to_bytes(e_len, "big")


msgs, encs = [], []
for i in range(10):
    m = urandom(len(flag))
    msgs.append(m)
    encs.append(encrypt(m, key))

with open("output.py", "wt") as f:
    f.write(f"{msgs, encs, n =}")

Можем заметить, что n это произведение ~10-20 простых чисел. Значит можно попробовать факторизовать n.

target_bl = len(flag) * 8
prime_base = [getPrime(m) for _ in range(-(-target_bl // m) + 1)]
n = reduce(mul, prime_base, 1)

def encrypt(m: bytes, key: int) -> bytes:
    e = int.from_bytes(m)
    for _ in range(ROUNDS - 1):
        e += key
        e = pow(e, k, n)
    e = (e + key) % n
    return e.to_bytes(e_len, "big")

msgs, encs = [], []
for i in range(10):
    m = urandom(len(flag))
    msgs.append(m)
    encs.append(encrypt(m, key))

Каждое сообщение зашифровывается функцией encrypt и выглядит так:
$enc_j = (…((msg_j + key)^k + key)^k + … + key) \mod n$

Т.к. N это произведение простых чисел, т.е. $N \equiv \prod_{i} p_{i}$, то
$enc_j = (…((msg_j + key)^k + key)^k + … + key) \mod p_i$
для всех множителей числа N.

Можем выполнить переход к
$enc_j’ = (…((msg_j’ + key’)^k + key’)^k + … + key’) \mod p_i$
где
$enc_j’ \equiv enc_j \mod p_i$
$msg_j’ \equiv msg_j \mod p_i$
$key_j’ \equiv key_j \mod p_i$

$enc_j’$, $msg_j’$, $p_i’$ легко вычисляются.
Нужно найти остатки по модулю $key_j$. Их нужно будет найти перебором. Но так как $p_i$ не такие большие, то это не займет много времени.

После нахождения всех $key_j$ получим систему уравнений:
$\begin{cases} x \equiv key_0' \mod p_0 \\ x \equiv key_1' \mod p_1 \\ x \equiv key_2' \mod p_2 \\ x \equiv key_3' \mod p_3 \\ ... \\ x \equiv key_r' \mod p_r \\ \end{cases}$
где x это флаг, он же key

Для решения таких систем применяется китайская теорема об остатках.

Остается только реализовать все алгоритмы и получить флаг.

3 Решение

3.1 Факторизация

Перебором находим все делители числа n. Никаких оптимизаций не делаем. На текущем примере работает очень быстро.
Реализация:

func factorize(n *big.Int) []*big.Int {
	num := new(big.Int).Set(n)
	divisor := big.NewInt(2)
	remainder := new(big.Int)
	tmp := new(big.Int)

	primes := make([]*big.Int, 0)

	for {
		tmp.QuoRem(num, divisor, remainder)

		if remainder.BitLen() == 0 {
			primes = append(primes, divisor)
			num.Div(num, divisor)
			divisor = big.NewInt(2)

			if num.Cmp(big.NewInt(1)) == 0 {
				break
			}
		}

		divisor.Add(divisor, big.NewInt(1))
	}

	return primes
}

3.2 Поиск остатков от деления

Перебором чисел от 0 до p находим такое число, которое после вызова функции encrypt даст такой же остаток от деления enc на p.
Если искать остатки от деления только для одного сообщения, то могут попадаться числа, которые подходят только для этого сообщения, но не подходят для остальных.
Поэтому нужно проверять все сообщения (или хотя бы два).
Реализация:

func encrypt(m, key, k, n *big.Int) *big.Int {
	e := new(big.Int).Set(m)
	for range ROUNDS - 1 {
		e.Add(e, key)
		e.Exp(e, k, n)
	}
	e.Add(e, key)
	e.Mod(e, n)
	return e
}

func findKeyModP(msgs, encs []*big.Int, p *big.Int) (*big.Int, error) {
	msgsMod := make([]*big.Int, len(msgs))
	encsMod := make([]*big.Int, len(encs))

	for i := range msgs {
		msgsMod[i] = new(big.Int).Mod(msgs[i], p)
		encsMod[i] = new(big.Int).Mod(encs[i], p)
	}

	for candidate := big.NewInt(0); candidate.Cmp(p) < 0; candidate.Add(candidate, big.NewInt(1)) {
		found := true
		for i := range msgsMod {
			e := encrypt(msgsMod[i], candidate, KEXP, p)

			if e.Cmp(encsMod[i]) != 0 {
				found = false
				if i > 0 {
					log.Printf("skip %v - %v", i, candidate)
				}
				break
			}
		}
		if found {
			return candidate, nil
		}
	}

	return nil, fmt.Errorf("no key mod p found")
}

3.3 Китайская теорема об остатках

Реализация по алгоритму, который чаще всего упоминается и наиболее простой.

Вычисляем общий модуль $N=\prod_{i} p_{i}$
Вычисляем впомогательные модули $N_i=\frac{N}{p_i}$
Вычисляем обратные элементы $N_i^{-1} \equiv \frac{1}{N_i} {\bmod {p_i}}$
Вычисляем искомое значение $x = \sum_{i}r_{i}N_{i}N_{i}^{-1} \mod N$

Реализация:

func crt(p, k []*big.Int) (*big.Int, error) {
	N := new(big.Int).SetInt64(1)
	for _, v := range p {
		N.Mul(N, v)
	}

	x := new(big.Int)
	for i := range p {
		Ni := new(big.Int).Div(N, p[i])
		inv := new(big.Int)
		if inv.ModInverse(Ni, p[i]) == nil {
			return nil, fmt.Errorf("no inverse for %v mod %v", Ni, p[i])
		}
		x.Add(x, new(big.Int).Mul(k[i], new(big.Int).Mul(Ni, inv)))
	}

	return x.Mod(x, N), nil
}

Основная часть:

type ResKey struct {
	Index int
	Key   *big.Int
}

func main() {
	log.SetFlags(log.Lmicroseconds)

	primes := factorize(N)
	log.Printf("primes: %v -> %v", N, primes)

	ch := make(chan ResKey)

	for i := range primes {
		go func(i int) {
			prime := primes[i]
			key, err := findKeyModP(msgs, encs, prime)
			log.Printf("key mod: %v - %v - %v", err, prime, key)
			ch <- ResKey{Index: i, Key: key}
		}(i)
	}

	keyMods := make([]*big.Int, len(primes))
	for range primes {
		res := <-ch
		keyMods[res.Index] = res.Key
	}

	log.Printf("primes: %v", primes)
	log.Printf("keyMods: %v", keyMods)

	key, err := crt(primes, keyMods)
	log.Printf("crt: %v - %v - %s", err, key, key.Bytes())
}

Чтобы повысить производительность добавлены корутины. Позволяет сократить поиск всех остатков от деления в несколько раз.

Программа целиком:

package main

import (
	"fmt"
	"log"
	"math/big"
)

var (
	msgs = []*big.Int{
		new(big.Int).SetBytes([]byte("\xee0\xc6Ax7M\xea\xb7\xe0^\xaf.\xb1u0\xf3\x83\x13\x9eX\xe0+\xdaeN\xc3<\xb2\x03\x18\xf3\xfd\x0c\xd3J\xea\xb0K")),
		new(big.Int).SetBytes([]byte("\t\xcaF\x8b\xec\xc6\x10e\x97\xfc`\xd1\tYHw\xde\x1d\x19=\xbb\xe5\x9a\x1f\xa9<\xf3a4\xc3\x7f8\xe7o6\xa0vI\x81")),
		new(big.Int).SetBytes([]byte("\xf4&\xcf-O\x8d\xe7\x03\xa4\xf8l@\xf9\xae\xd8\x91R\xe5Z\x01J\xee\xfb\xb2\xa3\xcf\x9cQ\x9f\x8d\xf6t>0\xff\xe2-h\xbc")),
		new(big.Int).SetBytes([]byte("&U\xcb\xf0)r\xfcz\n\x91\xb7$5\x0bO\xff\xba\xf6h\xd3\xb3\xe1d4\xbb\xb6\"\xc6\x87\x83EAA\xf0N\xb5O\x9f\x90")),
		new(big.Int).SetBytes([]byte("e&\xad\x19\x97n\xdf$\xc5\t4u\xf5\xdd/\xd6\x9f\xec\x14\xb6\xed\xb9\xb2)=\xef\xec\xbcv\xf3\x04\x1a\xa3\xb5{\x15{\xaa\xf8")),
		new(big.Int).SetBytes([]byte("\x98mX\xbfH\x93\x14\x80_h\x01\xb0]tA\xaf\xf6*\xec\x8b\x7f\x93\x0c>6\x9e\x9bJ\xb5\xe7\x92m\xda\x91{\x94%\xdc\x16")),
		new(big.Int).SetBytes([]byte("\xbb\xf2e\x9f\xa32\xae\xeda\xcd\xa7\xa0\r\x8e1\xb2\x93\xf5\x82/\xd6\xb3\x07r\x92\xe4\x870\xe0\xbes\xb5\xa4\x12\x87\xf23=\xcd")),
		new(big.Int).SetBytes([]byte("(\xc3\x95(\x04 \x89g\t\x86\x1d\xbb\xc3t\xe7\xcf(\x90]\xabNw\x18X+V\xe7\x1c\xdf\xdd\xe8\x1a\x12\x07\xe1|\x15\xf6\xbc")),
		new(big.Int).SetBytes([]byte("\xecS&\xe6\xf5\xbb\xf5\x13\xab\x93\x01\xc2Z\xb1\xc8J@\xe2}\x08\x14\xf1k\xc1'\x07\x0b\xea\x96&\xa3\x81\xeaY\x01\xd4\xe4\xb7\xaf")),
		new(big.Int).SetBytes([]byte("\xc1b1\x8dz\x10\xcf\xb5\xb9bB5E\x1a\xe9\xcc\xa6\x1c\x01\xbf\n\xe7\xa1Zm$\x88r\x9c\x93\x12\x87\xfa{\x17+\xe7c\xf7")),
	}

	encs = []*big.Int{
		new(big.Int).SetBytes([]byte("\x05\xc2\xbe\x97_o\xc4\x03CiW\x884t\xf7\xde\xf0\xe1T\r2\x1e\xc135\x1aX\xfa\x01\xd4p3\xb4\xb6{ \x1c/\xb49\n\xc8")),
		new(big.Int).SetBytes([]byte("\x00\xe2\x106\x92\xcfJU\xf6@\x80)\xd8\x1eStQ\x11\x00\xa9(\x8a\xe6wt\xa5@\xa1H\xf1\xc3\xcb\xb5\x9b\x97\x10\x8f\xc8\xdbul\xc2")),
		new(big.Int).SetBytes([]byte("\x0f\xd7]%\n\xa8\x0e\x18a\x99\x9b\xfc\xbd\xdbqr\x0f\xad\xf1\x87\xf7\xc5(\x11*;\x11\xb1\xec\x06nC\xe1\xb1B%\xbf\xc4\x8c@\xa2\xd1")),
		new(big.Int).SetBytes([]byte("\x0c\x0cmG\xaf\xb3_\xf3~\xea\x16-P\x1d\x90f\x19\xc4\x8a\xf2&/vm\x87\xe2\xf4\xa9\xc4\x8f\xd4\n\xb6\xd7\xad\xed(\n\xc1\xd6x\xf3")),
		new(big.Int).SetBytes([]byte("\x11\xa4?\xcch\xd0\x19f\xfb\t}q\xb2`\xd6\xe1\xb1\xf6~\x95\xa0{\x88\xfb$\xccUHg\xd9\xa0H\\\xf8\xa4>\xf52\xf7\xaa%*")),
		new(big.Int).SetBytes([]byte("\x18\xa5\x8c\x83^\x90\xbb\x08O-n\xc3-\x8f3\x81%vpx?4\x9e\xbcNw\x84\n\x97&C!@\x8aa\xfae\x1eU\x9f\xac\xf6")),
		new(big.Int).SetBytes([]byte("\x0e\xee\x0c\xa0\xb1\xca\xbe\x98'_\xf9\xddi\xb9W\xd1\x1c\x84@4P\xcd\x89\xafB\xca\xc0\xb3\xe3\xa7\x85J\xb2\xea\xb2\x84\x93qN\xe5\xb3\xbe")),
		new(big.Int).SetBytes([]byte("\x06\x82\x13C\x88\xa1\xcaMM+\x00_\xce\xcd\xdc\xfb\xd5#^\xff\xe5\x05\x07\xd1OM\xae\x14\xcf\x9aDx\x04\xd8]\xee\xbb\xddc\xe5\x1f\xb2")),
		new(big.Int).SetBytes([]byte("\x02\xd4C\x99\x9d\xce\x02l\xee\x8f\x1b\xfa \xddd\x02MkW\xea\xee'\xef\xb5\xc6\xfd\x94Gs>\xfb|\x96\x0eS\xb5\x89a5\xc9\xac\xb2")),
		new(big.Int).SetBytes([]byte("\x0eQ0\x82J\xc9X\x98M]\xa6\xcf\x86\x90\x9cC\xc0S\x16\xb2\xd2\x0b\xcdX\x1f\x9f\x8a\xf4t\x1dyy\xeb\x1csm\xf6\xf6\xef/\x93\x06")),
	}

	N, _ = new(big.Int).SetString("13581753459672963723370610555805601592569224906006184329377532633106785380857166524817321353558156357", 10)

	ROUNDS = 512
	KEXP   = big.NewInt(78)
)

func factorize(n *big.Int) []*big.Int {
	num := new(big.Int).Set(n)
	divisor := big.NewInt(2)
	remainder := new(big.Int)
	tmp := new(big.Int)

	primes := make([]*big.Int, 0)

	for {
		tmp.QuoRem(num, divisor, remainder)

		if remainder.BitLen() == 0 {
			primes = append(primes, divisor)
			num.Div(num, divisor)
			divisor = big.NewInt(2)

			if num.Cmp(big.NewInt(1)) == 0 {
				break
			}
		}

		divisor.Add(divisor, big.NewInt(1))
	}

	return primes
}

func encrypt(m, key, k, n *big.Int) *big.Int {
	e := new(big.Int).Set(m)
	for range ROUNDS - 1 {
		e.Add(e, key)
		e.Exp(e, k, n)
	}
	e.Add(e, key)
	e.Mod(e, n)
	return e
}

func findKeyModP(msgs, encs []*big.Int, p *big.Int) (*big.Int, error) {
	msgsMod := make([]*big.Int, len(msgs))
	encsMod := make([]*big.Int, len(encs))

	for i := range msgs {
		msgsMod[i] = new(big.Int).Mod(msgs[i], p)
		encsMod[i] = new(big.Int).Mod(encs[i], p)
	}

	for candidate := big.NewInt(0); candidate.Cmp(p) < 0; candidate.Add(candidate, big.NewInt(1)) {
		found := true
		for i := range msgsMod {
			e := encrypt(msgsMod[i], candidate, KEXP, p)

			if e.Cmp(encsMod[i]) != 0 {
				found = false
				if i > 0 {
					log.Printf("skip %v - %v", i, candidate)
				}
				break
			}
		}
		if found {
			return candidate, nil
		}
	}

	return nil, fmt.Errorf("no key mod p found")
}

func crt(p, k []*big.Int) (*big.Int, error) {
	N := new(big.Int).SetInt64(1)
	for _, v := range p {
		N.Mul(N, v)
	}

	x := new(big.Int)
	for i := range p {
		Ni := new(big.Int).Div(N, p[i])
		inv := new(big.Int)
		if inv.ModInverse(Ni, p[i]) == nil {
			return nil, fmt.Errorf("no inverse for %v mod %v", Ni, p[i])
		}
		x.Add(x, new(big.Int).Mul(k[i], new(big.Int).Mul(Ni, inv)))
	}

	return x.Mod(x, N), nil
}

type ResKey struct {
	Index int
	Key   *big.Int
}

func main() {
	log.SetFlags(log.Lmicroseconds)

	primes := factorize(N)
	log.Printf("primes: %v -> %v", N, primes)

	ch := make(chan ResKey)

	for i := range primes {
		go func(i int) {
			prime := primes[i]
			key, err := findKeyModP(msgs, encs, prime)
			log.Printf("key mod: %v - %v - %v", err, prime, key)
			ch <- ResKey{Index: i, Key: key}
		}(i)
	}

	keyMods := make([]*big.Int, len(primes))
	for range primes {
		res := <-ch
		keyMods[res.Index] = res.Key
	}

	log.Printf("primes: %v", primes)
	log.Printf("keyMods: %v", keyMods)

	key, err := crt(primes, keyMods)
	log.Printf("crt: %v - %v - %s", err, key, key.Bytes())
}

4 Получение флага

Запускаем программу:

❯ go run ./main.go
15:14:22.236665 primes: 13581753459672963723370610555805601592569224906006184329377532633106785380857166524817321353558156357 -> [552583 594271 616211 645097 664369 684569 709231 770587 787547 794473 871177 909599 910099 964309 982063 982147 997357]
15:15:02.350547 key mod: <nil> - 594271 - 47740
15:15:02.859370 key mod: <nil> - 871177 - 50886
15:15:18.484793 key mod: <nil> - 645097 - 72977
15:16:58.607391 skip 1 - 196903
15:17:10.595183 key mod: <nil> - 997357 - 215578
15:17:18.066492 key mod: <nil> - 910099 - 228601
15:17:26.286467 skip 1 - 242248
15:17:31.263406 key mod: <nil> - 552583 - 243969
15:17:40.039452 skip 1 - 258027
15:18:45.667231 skip 1 - 381318
15:18:48.578592 key mod: <nil> - 909599 - 380110
15:19:16.496272 key mod: <nil> - 982063 - 437765
15:19:22.285306 skip 1 - 462800
15:19:23.646157 key mod: <nil> - 770587 - 464139
15:19:25.827930 skip 1 - 458256
15:19:53.239150 key mod: <nil> - 664369 - 546460
15:20:01.543940 key mod: <nil> - 616211 - 560253
15:20:02.920172 key mod: <nil> - 964309 - 569223
15:20:16.827676 key mod: <nil> - 684569 - 646230
15:20:20.038924 key mod: <nil> - 709231 - 663540
15:20:21.396375 skip 1 - 667336
15:20:23.234507 key mod: <nil> - 794473 - 679225
15:20:35.595988 key mod: <nil> - 787547 - 755126
15:20:48.656943 key mod: <nil> - 982147 - 858254
15:20:48.656967 primes: [552583 594271 616211 645097 664369 684569 709231 770587 787547 794473 871177 909599 910099 964309 982063 982147 997357]
15:20:48.656995 keyMods: [243969 47740 560253 72977 546460 646230 663540 464139 755126 679225 50886 380110 228601 569223 437765 858254 215578]
15:20:48.657015 crt: <nil> - 2817147352264586717411216279640959057352746518352237653949439230620683712537493173958559872381 - VolgaCTF{bru73_f0rc3_m3_l0v3_50m371m35}

Получили флаг VolgaCTF{bru73_f0rc3_m3_l0v3_50m371m35}

Программа работает примерно 5 минут.
Факторизация числа N происходит очень быстро, менее 1 секунды требуется.
Самое трудоемкое - поиск остатков от деления. Требуется перебирать много вариантов.