Урок 5. Known plaintext и повторяющийся XOR

В прошлом уроке мы перебирали 256 ключей и фильтровали результат по началу vsosh{. Это работало, но, честно говоря, перебор — это грубая сила. Сейчас вы увидите приём поизящнее, который не перебирает ничего, а вычисляет ключ напрямую. Он называется known plaintext — «известный открытый текст» — и это, пожалуй, самый важный сквозной приём всего курса. Он же дальше сработает в задачах на affine, на линейные генераторы и на многое другое. Поэтому давайте разберём его по-настоящему.

Идея known plaintext

Вернёмся к формуле XOR-шифрования одного байта:

$$c = m \oplus k$$

Раньше мы знали $c$ (шифртекст) и искали $k$ (ключ). Но у нас есть третья величина — $m$, открытый текст. И мы кое-что о нём знаем: он начинается с vsosh{. То есть первые шесть байт $m$ нам известны заранее.

А раз известны $c$ и $m$, то $k$ достаётся из той же формулы одним движением. XOR обратим, поэтому:

$$k = c \oplus m$$

Проверьте: $c \oplus m = (m \oplus k) \oplus m = k$. Всё, ключ вычислен, без перебора. Нам не пришлось пробовать 256 вариантов — мы просто заксорили шифртекст с известным куском текста.

На практике это выглядит так. Пусть ключ однобайтовый; тогда достаточно одного известного символа, но давайте возьмём весь известный префикс и посмотрим:

ct = bytes.fromhex(open("task.txt").read().strip())
known = b"vsosh{"

key = []
for i in range(len(known)):
    key.append(ct[i] ^ known[i])

print(key)

Если ключ действительно однобайтовый, все шесть чисел в key окажутся одинаковыми — потому что один и тот же байт ключа ксорил все позиции. Это, кстати, отличная проверка гипотезы: посмотрели на key, все элементы равны — значит ключ из одного байта, берём любой и расшифровываем весь текст.

k = key[0]
m = bytes([x ^ k for x in ct])
print(m.decode())

Обратите внимание, насколько это быстрее перебора. Никаких 256 итераций, никакого скоринга — только одно наблюдение «текст начинается с vsosh{» и одна операция XOR.

Когда known plaintext даёт ключ, а когда нет

Важно понимать границы приёма. Known plaintext мгновенно даёт ключ, потому что XOR — линейная, обратимая по ключу операция: зная вход и выход, легко найти параметр. Это же свойство есть у affine-шифров и линейных генераторов, которые ждут вас в четвёртом модуле, — там vsosh{ тоже станет ключом к решению.

А вот для стойких шифров (например AES с неизвестным ключом) known plaintext ключа не даёт: связь входа и выхода там нарочно сделана «нелинейной и запутанной». Так что запомните правило: known plaintext ломает линейные конструкции. XOR — самая простая из них, и на ней вы отрабатываете приём, который потом масштабируется.

Этим приёмом решались реальные задачи. В олимпиадной классике «Анализ трафика» · региональный этап, 2022–2023 ключ XOR восстанавливали именно по известному куску открытого текста, вытащенному из перехваченного трафика. А в задаче «Тайна заброшенной шахты» · региональный этап, 2025–2026 зацепкой служил всё тот же префикс vsosh{, по которому раскручивали линейный keystream.

Повторяющийся ключ (repeating-key XOR)

Однобайтовый ключ слаб, поэтому задачи усложняют: ключ делают длиной в несколько байт, и он повторяется по кругу вдоль всего текста. Это называется repeating-key XOR (по духу — байтовый шифр Виженера).

Формально, если ключ $k$ имеет длину $L$, то

$$c_i = m_i \oplus k_{i \bmod L}$$

То есть первый байт текста ксорится с $k_0$, второй с $k_1$, ..., $L$-й снова с $k_0$, и так по кругу. В коде повторяющийся XOR пишется так:

def rk(data, key):
    out = []
    for i in range(len(data)):
        out.append(data[i] ^ key[i % len(key)])
    return bytes(out)

Ключевая деталь — индекс i % len(key): он «зацикливает» ключ. Если перепутать здесь индексацию, получится каша, поэтому проговорите про себя: «i по модулю длины ключа».

Взлом repeating-key через known plaintext

И вот здесь known plaintext раскрывается во всю силу. Пусть мы не знаем ни ключ, ни даже его длину. Но мы знаем начало текста — vsosh{, а часто и больше (например, формат условия подсказывает продолжение). Если известный префикс не короче длины ключа, мы восстанавливаем весь ключ тем же приёмом «ксорим шифртекст с известным текстом»:

$$k_i = c_i \oplus m_i, \quad i = 0, 1, \dots, L-1$$

ct = bytes.fromhex(open("task.txt").read().strip())
known = b"vsosh{"                       # известный префикс

key = bytes(ct[i] ^ known[i] for i in range(len(known)))
print(key)

Что мы получим в key? Если ключ короче префикса, ключ начнёт повторяться внутри key. Например, для ключа длины 4 в первых шести байтах вы увидите что-то вроде k0 k1 k2 k3 k0 k1, то есть период 4 виден невооружённым глазом. Это и есть определение длины ключа: находим наименьший период, при котором key повторяется.

Дальше — восстанавливаем весь текст найденным ключом:

period = 4                              # увидели период глазами или проверили кодом
key = key[:period]
m = bytes(ct[i] ^ key[i % period] for i in range(len(ct)))
print(m.decode())

Проверка гипотезы простая: если после расшифровки получился читаемый текст с vsosh{...} и правильно закрывающей скобкой — период угадан верно. Если каша — попробуйте другой период (обычно кандидаты видны прямо в key).

Небольшой, но важный момент про «минимальный период». Иногда известный префикс даёт ключ, который сам является повторением более короткого (например, kekey вместо key). Правильный ответ — наименьший период. В задаче J6 как раз проверяется, что вы сворачиваете ключ к минимальной длине, а не возвращаете его удвоенную копию.

Практика урока

• J5 «ключ по префиксу» (тренажёр кода). По hex-шифртексту и известному началу текста вернуть байты ключа (для длины префикса). Прямое применение $k = c \oplus m$.
• J6 «повторяющийся ключ» (тренажёр кода). По hex-шифртексту и известному префиксу вернуть повторяющийся ключ как текст, свёрнутый к минимальному периоду.
• C6 «Якорь». Флаг зашифрован однобайтовым XOR; решите его через known plaintext (по vsosh{), а не перебором. Почувствуйте разницу с уроком 4.
• C7 «Повтор». Флаг зашифрован повторяющимся XOR. Восстановите ключ по известному префиксу и расшифруйте.

Приём «ключ спрятан в одном месте, а применяется в другом» — из арсенала заключительного этапа. В задаче «Скрытый канал в пингах» · заключительный этап, 2025–2026 ключ XOR сначала находили в HTTP-трафике, а потом им расшифровывали данные, спрятанные в ICMP-пакетах.

Типичные ошибки

• Берут known как строку, а не байты. XOR — над байтами; пишите b"vsosh{", а не "vsosh{".
• Не проверяют, что ключ постоянный/периодичный. Восстановили key, а он «скачет» — значит либо префикс не тот, либо ключ длиннее известного куска.
• Путают индексацию i % len(key) и получают мусор.
• Возвращают неминимальный период в repeating-key (например, kekey вместо key).
• Берут известный префикс короче длины ключа и восстанавливают только часть ключа, а потом удивляются, почему хвост текста не расшифровался.

Что дальше

Вы освоили все кирпичи: представление данных, кодировки, инструмент, XOR, known plaintext. В уроке 6 мы соберём их в одну задачу — такую, как встречается на реальных этапах ВСОШ: несколько слоёв кодировок, под ними числа, под числами XOR, а зацепка — всё тот же vsosh{. Вы решите её целиком и увидите, что уже умеете доводить настоящую задачу до флага.