Урок 4. XOR и однобайтовый ключ

До сих пор мы только снимали открытые кодировки — никакого секрета там не было. Теперь появляется первый настоящий элемент шифрования, и это XOR. С него начинается огромная часть олимпиадных задач: от простых «расшифруй строку» до целых цепочек, где XOR спрятан под слоями кодировок. Хорошая новость в том, что XOR — операция дружелюбная: если понять одно её свойство, ломать однобайтовый XOR становится делом нескольких строк.

Что такое XOR

XOR (исключающее «или», в Python — оператор ^) работает над битами по простому правилу: бит результата равен 1, если биты-аргументы разные, и 0, если одинаковые.

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

Над байтами XOR применяется поразрядно: 0x76 ^ 0x2a ксорит каждый из восьми битов. В Python это просто:

print(0x76 ^ 0x2a)    # 92

Главное свойство: обратимость

Из таблицы вытекают два факта, на которых держится всё остальное:

• $a \oplus a = 0$ — любое число, ксоренное само с собой, даёт ноль (биты попарно одинаковы);
• $a \oplus 0 = a$ — XOR с нулём ничего не меняет.

А теперь соберём из них главное. Пусть мы зашифровали байт открытого текста $m$ ключом $k$:

$$c = m \oplus k$$

Что будет, если применить XOR с тем же ключом ещё раз, уже к шифртексту?

$$c \oplus k = (m \oplus k) \oplus k = m \oplus (k \oplus k) = m \oplus 0 = m$$

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

XOR по байтам

В реальной задаче ксорят не один байт, а всю строку. Если ключ — один байт, им ксорят каждый байт данных:

b = bytes.fromhex(open("task.txt").read().strip())

k = 0x2a
m = bytes([x ^ k for x in b])
print(m)

Это и есть однобайтовый XOR — самый частый начальный случай. Весь текст зашифрован одним-единственным байтом ключа. И вот здесь кроется его слабость.

Взлом однобайтового XOR: перебор

Однобайтовый ключ — это число от 0 до 255. Всего 256 вариантов. Перебрать 256 вариантов на компьютере — мгновение. Значит, мы можем просто попробовать все ключи и посмотреть, при каком получается осмысленный результат:

b = bytes.fromhex(open("task.txt").read().strip())

for k in range(256):
    m = bytes([x ^ k for x in b])
    print(k, m)

Запустите — и глазами найдите строку, где вылезает vsosh{. Это уже рабочий способ: 256 строк можно просмотреть. Но глазами долго и не масштабируется, поэтому научимся выбирать правильный вариант автоматически.

Как отличить правильный вариант: две стратегии

Стратегия 1: печатаемость. Осмысленный текст состоит из печатаемых ASCII-символов (диапазон 0x20–0x7e). Значит, можно для каждого ключа посчитать долю печатаемых байт и взять вариант с наибольшей долей:

def score(m):
    good = sum(0x20 <= c <= 0x7e for c in m)
    return good / len(m)

best_k, best = 0, -1
for k in range(256):
    m = bytes([x ^ k for x in b])
    s = score(m)
    if s > best:
        best, best_k = s, k
print(best_k)

Логично? Да. Но здесь спрятана ловушка, о которой обязательно нужно знать.

Ловушка печатаемости. XOR печатаемого текста с некоторыми ключами даёт снова печатаемый текст. Простой пример: буквы обычно лежат в диапазоне 0x40–0x7a; заксорьте их подходящим ключом — и получите другие буквы, тоже печатаемые. Тогда сразу несколько ключей (включая, например, ключ 0, то есть сам шифртекст) наберут высокую «печатаемость», и ваш скоринг выберет не тот вариант. Это не выдумка — на этом спотыкаются и люди, и автопроверки.

Стратегия 2: якорь vsosh{. А вот теперь вспомните урок 1. Мы же знаем, что открытый текст — это флаг, и он начинается с vsosh{. Значит, правильный ключ — тот, при котором расшифровка начинается ровно с этих шести символов. И такой ключ ровно один (одному байту ключа приходится одновременно превратить первый байт в v, второй в s, третий в o и так далее — это жёсткое условие, случайно оно не выполняется). Поэтому:

b = bytes.fromhex(open("task.txt").read().strip())

for k in range(256):
    m = bytes([x ^ k for x in b])
    if m.startswith(b"vsosh{"):
        print(k, m)

Этот способ надёжнее скоринга по печатаемости, потому что он не «на глазок», а по точному признаку. Когда вы знаете формат флага (а вы его знаете всегда), фильтруйте по нему, а не по печатаемости. Печатаемость оставьте на случай, когда известного префикса нет. Ровно этот однобайтовый XOR под слоями кодировок был внутренним ядром уже знакомой вам задачи «Снежный ком» · муниципальный этап, 2025–2026: сняв base64 и base32, участники упирались в один байт ключа и брали его перебором с фильтром по vsosh{.

Запомните это различие — оно повторится не раз: точная зацепка всегда лучше эвристики. Мы вернёмся к этой мысли в уроке 5, где vsosh{ из «фильтра» превратится в способ вычислить ключ вообще без перебора.

Важная деталь: возвращайте ключ, а не текст

Когда задача (или автопроверка) просит «восстановить ключ» — верните именно ключ (число), а не расшифрованный текст. Это самая частая ошибка в задачах на XOR: человек находит ключ, но возвращает m вместо k. Читайте условие: просят ключ — верните ключ; просят флаг — верните флаг. В задаче J4 требуется именно ключ.

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

• J3 «однобайтовый XOR» (тренажёр кода). По hex-строке и ключу вернуть результат XOR (список байт). Закрепляет саму операцию.
• J4 «найти ключ» (тренажёр кода). По hex-строке шифртекста вернуть однобайтовый ключ. Открытый текст — флаг, начинается с vsosh{. Здесь как раз проверяется, что вы фильтруете по якорю, а не по печатаемости, и что возвращаете ключ, а не текст.
• C5 «Одинокий байт». В файле — флаг, зашифрованный однобайтовым XOR (в hex). Найдите ключ и сдайте флаг.

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

• Возвращают текст вместо ключа (или наоборот). Смотрите, что именно просят.
• Фильтруют только по печатаемости и выбирают неверный ключ, потому что шифртекст тоже оказался печатаемым. Есть известный префикс — фильтруйте по нему.
• Ксорят строку вместо байтов. XOR — операция над числами; держите данные в bytes.
• Путают ^ и **. ^ — это XOR, ** — возведение в степень. Разные вещи.
• Считают печатаемость с делением на ноль на пустых данных. Мелочь, но ломает автопроверку.

Что дальше

Мы перебирали 256 вариантов. Но если известно начало открытого текста, ключ можно вычислить напрямую, без всякого перебора — и это работает не только для одного байта, но и для длинных повторяющихся ключей. Именно этому посвящён урок 5: known plaintext и repeating-key XOR.