XOR-шифр

В криптографии простой шифр XOR является разновидностью аддитивного шифра . алгоритм шифрования , работающий по принципам:

А $\oplus$ 0 = А,

А $\oplus$ А = 0,

А $\oplus$ Б = Б $\oplus$ А,

(А $\oplus$ Б) $\oplus$ С = А $\oplus$ (Б $\oplus$ С),

(Б $\oplus$ А) $\oplus$ А = Б $\oplus$ 0 = Б,

Например, где $\oplus$ обозначает операцию исключающей дизъюнкции (XOR). Эту операцию иногда называют сложением по модулю 2 (или вычитанием, что идентично). С помощью этой логики текстовую строку можно зашифровать, применив побитовый оператор XOR к каждому символу с использованием заданного ключа. Чтобы расшифровать выходные данные, простое повторное применение функции XOR с ключом удалит шифр.

Пример

Строка «Вики» ( 01010111 01101001 01101011 01101001 в 8-битном ASCII ) можно зашифровать с помощью повторяющегося ключа 11110011 следующим образом:

	01010111 01101001 01101011 01101001
$\oplus$	11110011 11110011 11110011 11110011
=	10100100 10011010 10011000 10011010

И наоборот, для расшифровки:

	10100100 10011010 10011000 10011010
$\oplus$	11110011 11110011 11110011 11110011
=	01010111 01101001 01101011 01101001

Использование и безопасность

Оператор XOR чрезвычайно распространен как компонент более сложных шифров. Сам по себе, используя постоянно повторяющийся ключ, простой шифр XOR можно тривиально взломать с помощью частотного анализа . Если содержание любого сообщения можно угадать или узнать иным образом, то можно раскрыть ключ. Его основное достоинство в том, что его просто реализовать и что операция XOR не требует больших вычислительных затрат. Поэтому простой повторяющийся шифр XOR (т. е. с использованием одного и того же ключа для операции xor для всех данных) иногда используется для сокрытия информации в тех случаях, когда не требуется особой безопасности. Шифр XOR часто используется в компьютерных вредоносных программах , чтобы затруднить обратный инжиниринг.

Если ключ случайный и его длина не меньше длины сообщения, шифр XOR гораздо безопаснее, чем при повторении ключа в сообщении. Когда поток ключей генерируется генератором псевдослучайных чисел , результатом является поточный шифр . Если ключ действительно случайный , в результате получается одноразовый блокнот , который теоретически невозможно взломать .

Оператор XOR в любом из этих шифров уязвим для атаки с использованием известного открытого текста , поскольку открытый текст $\oplus$ зашифрованный текст = ключ . Также тривиально перевернуть произвольные биты в расшифрованном открытом тексте, манипулируя зашифрованным текстом. Это называется податливостью .

Полезность в криптографии

Основная причина, по которой XOR так полезен в криптографии, заключается в том, что он «идеально сбалансирован»; для данного ввода открытого текста 0 или 1 результат зашифрованного текста с равной вероятностью будет либо 0, либо 1 для действительно случайного ключевого бита.

В таблице ниже показаны все четыре возможные пары открытого текста и ключевых битов. Ясно, что если ничего не известно о ключе или открытом тексте, ничего нельзя определить только по зашифрованному тексту.

Таблица трассировки шифрования XOR

Открытый текст	Ключ	Зашифрованный текст
0	0	0
0	1	1
1	0	1
1	1	0

Другие логические операции, такие как И или ИЛИ, не имеют такого сопоставления (например, И дает три 0 и одну 1, поэтому знание того, что данный бит зашифрованного текста равен 0, означает, что существует вероятность 2/3, что исходный открытый текст бит был равен 0, в отличие от идеального шанса 1/2 в случае XOR)

Пример реализации

Пример использования языка программирования Python .

from os import urandom


def genkey(length: int) -> bytes:
    """Generate key."""
    return urandom(length)


def xor_strings(s, t) -> bytes:
    """Concate xor two strings together."""
    if isinstance(s, str):
        # Text strings contain single characters
        return "".join(chr(ord(a) ^ b) for a, b in zip(s, t)).encode('utf8')
    else:
        # Bytes objects contain integer values in the range 0-255
        return bytes([a ^ b for a, b in zip(s, t)])


message = 'This is a secret message'
print('Message:', message)

key = genkey(len(message))
print('Key:', key)

cipherText = xor_strings(message.encode('utf8'), key)
print('cipherText:', cipherText)
print('decrypted:', xor_strings(cipherText, key).decode('utf8'))

# Verify
if xor_strings(cipherText, key).decode('utf8') == message:
    print('Unit test passed')
else:
    print('Unit test failed')

Более короткий пример с использованием языка программирования R , основанный на головоломке , опубликованной в Instagram GCHQ .

secret_key <- c(0xc6, 0xb5, 0xca, 0x01) |> as.raw()

secret_message <- "I <3 Wikipedia" |>
  charToRaw() |>
  xor(secret_key) |>
  base64enc::base64encode()


secret_message_bytes <- secret_message |>
                        base64enc::base64decode()
xor(secret_message_bytes, secret_key) |> rawToChar()

См. также

• Блочный шифр
• Выученный шифр
• Шифр Виженера

Ссылки

Источники

• Будиман, Массачусетс; Тариган, Джей Ти; Вината, А.С. (2020). «Цифровая блокировка на базе Arduino UNO и Android с использованием комбинации шифра Виженера и шифра XOR» . Физический журнал: серия конференций . 1566 (1). Издательство IOP: 012074. Бибкод : 2020JPhCS1566a2074B . дои : 10.1088/1742-6596/1566/1/012074 . ISSN   1742-6588 .
• Черчхаус, Роберт (2002), Коды и шифры: Юлий Цезарь, загадка и Интернет , Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-00890-7
• Гарг, Сатиш Кумар (2017). «Криптография с использованием шифра XOR». Научно-исследовательский журнал науки и технологий . 9 (1). Публикации A и V: 25. doi : 10.5958/2349-2988.2017.00004.3 . ISSN   0975-4393 .
• Гёдель, Курт (декабрь 1931 г.). «О формально неразрешимых теоремах Principia Mathematica и родственных систем I». Ежемесячные журналы по математике и физике (на немецком языке). 38–38 (1): 173–198. дои : 10.1007/BF01700692 . ISSN   0026-9255 . S2CID   197663120 .
• Левин, Майкл (июнь 2012 г.). «Все о XOR» . Перегрузка . 2 ((109): 14–19 . Проверено 29 августа 2021 г.
• Паар, Кристоф; Пельцль, Ян (2009). Понимание криптографии: учебник для студентов и практиков . Спрингер. ISBN  978-3-642-04101-3 . OCLC   567365751 .
• Рихтер, Вольфганг (3 августа 2012 г.), «Невзламываемая криптография за 5 минут» , Crossroads: журнал ACM для студентов , Ассоциация вычислительной техники
• Тутте, WT (19 июня 1998 г.), Фиш и я (PDF) , получено 11 января 2020 г. Стенограмма лекции, прочитанной профессором Тутте в Университете Ватерлоо.