Перестановочные шифры
В перестановочном шифре меняется не открытый текст, а порядок символов. В простом столбцовом перестановочном шифре открытый текст пишется горизонтально на разграфленном листе бумаги фиксированной ширины, а шифротекст считывается по вертикали. Дешифрирование представляет собой запись шифротекста вертикально на листе разграфленной бумаги фиксированной ширины и затем считывание открытого текста горизонтально.
Так как символы шифротекста те же, что и в открытом тексте, частотный анализ шифротекста покажет, что каждая буква встречается приблизительно с той же частотой, что и обычно. Это даст криптоаналитику возможность применить различные методы, определяя правильный порядок символов для получения открытого текста. Применение к шифротексту второго перестановочного фильтра значительно повысит безопасность. Существуют и еще более сложные перестановочные фильтры, но компьютеры могут раскрыть почти все из них.
Немецкий шифр ADFCVX, использованный в ходе Первой мировой войны, представлял собой перестановочный фильтр в сочетании с простой подстановкой. Этот для своего времени очень сложный алгоритм был раскрыт Жоржем Пенвэном (Georges Painvin), французским криптоаналитиком.
Хотя многие современные алгоритмы используют перестановку, с этим связана проблема использования большого объема памяти, а также иногда требуется работа с сообщениями определенного размера. Подстановка более обычна.
Простое 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 может защитить ваши файлы от младшей сестры, но настоящего криптоаналитика задержит лишь на считанные секунды.