Простое xor

XOR представляет собой операцию "исключающее или": 'Л' в языке С или Q в математической нотации. Это обычная операция над битами:

0 0 = 0

0 1 = 1

1 0 = 1

1 1 = 0

Из это вытекают:

а а = 0 а б б = а

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

/*

Пример алгоритма XOR

Использование: crypto key input_file output_file

*/

#include <stdio.h>

void usage()

{

printf("Usage: crypt key input_file output_file\n");

}

void main(int argc, char* argv[])

{

FILE *file_in, *file_out;

int index = 0;

int c;

if (argc < 4)

{

usage();

return;

}

file_in = fopen(argv[2], "rb");

if (file_in == NULL)

{

usage();

return;

}

file_out = fopen(argv[3], "wb");

if (file_out == NULL)

{

usage();

return;

}

while (1)

{

c = getc(file_in);

if (c == EOF) break;

putc(c ^ argv[1][index], file_out);

index++;

if (argv[1][index] == '\0')

{

index = 0;

}

}

printf("Done!\n");

}

Это симметричный алгоритм. Открытый текст подвергается операции "исключающее или" вместе с ключевым текстом для получения шифротекста. Так как повторное применение операции XOR восстанавливает ори­гинал для шифрования и дешифрирования используется одна и та же программа :

Р К = С С К = Р

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

Предположим, что длина ключа любое небольшое число байт. Ломаем так:

Определим длину ключа с помощью процедуры, известной как подсчет совпадений. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обыч­ный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения, крат­ного длине ключа, к другому и есть длина ключа.

Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шифротекстов. Результатом операции будет удаления ключа и получение открытого текста, подвергнутого операции XOR с самим собой, смещенным на длину ключа. Так как на один байт приходится 1.3 бита действительной информации (в английском языке: для других языков значение может быть другим), существующая значительная избы­точность позволяет определить способ шифрования.

Именно этот алгоритм (с 160-битным повторяющимся "ключом") NSA в конце концов разрешило использовать в цифровых телефонных сотовых сетях для закрытия голоса. XOR может защитить ваши файлы от младшей сестры, но настоящего криптоаналитика задержит лишь на считанные секунды.