Файл: MethodFull.doc

Стеганография

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

Ближе к сегодняшнему дню люди начали прятать секреты в графических изображениях, заменяя младший значащий бит изображения битом сообщения. Графическое изображение при этом менялось совсем незаметно – большинство графических стандартов определяют больше цветовых градаций, чем способен различить человеческий глаз – и сообщение извлекалось на противоположном конце. Так в черно-белой картинке 1024x1024 пик­села можно спрятать можно спрятать сообщение в 64 Кбайт. Многие общедоступные программы могут проделывать подобный фокус.

Имитационные функции Питера Уэйнера (Peter Wayner) маскируют сообщения. Эти функции изменяют сообщение так, что его статистический профиль становится похожим на что-нибудь еще: раздел The New York Times, пьесу Шекспира или телеконференцию в Internet. Этот тип стеганографии не одурачит че­ловека, но может обмануть большой компьютер, ищущий нужную информацию в Internet.

Подстановочные и перестановочные шифры

До появления компьютеров криптография состояла из алгоритмов на символьной основе. Различные крипто­графические алгоритмы либо заменяли одни символы другими, либо переставляли символы. Лучшие алгоритмы делали и то, и другое, и по много раз.

Сегодня все значительно сложнее, но философия остается прежней. Первое изменение заключается в том, что алгоритмы стали работать с битами, а не символами. Это важно хотя бы с точки зрения размера алфавита – с 26 элементов до двух. Большинство хороших криптографических алгоритмов до сих пор комбинирует подстановки и перестановки.

Подстановочные шифры

Подстановочным шифром называется шифр, который каждый символ открытого текста в шифротексте заменяет другим символом. Получатель инвертирует подстановку шифротекста, восстанавливая открытый текст. В классической криптографии существует четыре типа подстановочных шифров:

• Простой подстановочный шифр или моноалфавитный шифр– это шифр, который каждый символоткрытого текста заменяет соответствующим символом шифротекста. Простыми подстановочными шифрами являются криптограммы в газетах.

• Однозвучный подстановочный шифрпохож на простую подстановочную криптосистему за исключением того, что один символ открытого текста отображается на несколько символов шифротекста. Напри­мер, "А" может соответствовать 5, 13, 25 или 56, "В" - 7, 19, 31 или 42 и так далее.

• Полиграмный подстановочный шифр– это шифр, который блоки символов шифрует по группам. На­пример, "ABA" может соответствовать "RTQ", "ABB" может соответствовать "SLL" и так далее.

• Полиалфавитный подстановочный шифрсостоит из нескольких простых подстановочных шифров. Например, могут быть использованы пять различных простых подстановочных фильтров; каждый сим­вол открытого текста заменяется с использованием одного конкретного шифра.

Знаменитый шифр Цезаря, в котором каждый символ открытого текста заменяется символом, находящегося тремя символами правее по модулю 26 ("А" заменяется на "D," "В" - на "Е", ... "W" - на " Z ", "X" - на "А", "Y" - на "В", "Z" - на "С"), представляет собой простой подстановочный фильтр. Он действительно очень прост, так как алфавит шифротекста представляет собой смещенный, а не случайно распределенный алфавит открытого текста.

ROT13 - это простая шифровальная программа, обычно поставляемая с системами UNIX. Она также являет­ся простым подстановочным шифром. В этом шифре "А" заменяется на "N," "В" - на "О" и так далее. Каждая буква смещается на 13 мест. Шифрование файла программой ROTI3 дважды восстанавливает первоначальный файл.

P = ROT13(ROT13(P))

ROTI3 не используется для безопасности, она часто применяется в почте, закрывая потенциально неприятный текст, решение головоломки и тому подобное.

Простые подстановочные шифры легко раскрываются, так как шифр не прячет частоты использования различных символов в открытом тексте. Чтобы восстановить открытый текст, хорошему криптоаналитику требуется только знать 33 символа русского алфавита.

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

Полиграмные подстановочные шифры – это шифры, которые кодируют сразу группы символов . Шифр Play-fair ("Честная игра"), изобретенный в 1854 году, использовался англичанами в Первой мировой войне. Он шифрует пары символов. Другим примером полиграмного подстановочного шифра является шифр Хилла (Hill). Иногда можно видеть как вместо шифра использует­ся кодирование по Хаффману (Huffman), это небезопасный полиграмный подстановочный шифр.

Полиалфавитные подстановочные шифры были изобретены Лином Баттистой (Lean Battista) в 1568 году. Они использовались армией Соединенных Штатов в ходе Гражданской войны в Америке. Несмотря на то, что они легко могут быть взломаны (особенно с помощью компьютеров), многие ком­мерческие продукты компьютерной безопасности используют такие шифры. Шифр Вигенера (Vigenere), впервые опубликованный в 1586 году, и шифр Бофора (Beaufort) также являются примерами полиалфавитных подстановочных шифров.

У полиалфавитных подстановочных шифров множественные однобуквенные ключи, каждый из которых используется для шифрования одного символа открытого текста. Первым ключом шифруется первый символ открытого текста, вторым ключом – второй символ, и так далее. После использования всех ключей они повторяются циклически. Если применяется 20 однобуквенных ключей, то каждая двадцатая буква шифруется тем же ключом. Этот параметр называется периодом шифра. В классической криптографии шифры с длинным перио­дом было труднее раскрыть, чем шифры с коротким периодом. Использование компьютеров позволяет легко раскрыть подстановочные шифры с очень длинным периодом.

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

Перестановочные шифры

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

Так как символы шифротекста те же, что и в откры­том тексте, частотный анализ шифротекста покажет, что каждая буква встречается приблизительно с той же частотой, что и обычно. Это даст криптоаналитику возможность применить различные методы, определяя правильный порядок символов для получения открытого текста. Применение к шифротексту второго перестановочного фильтра значительно повысит безопасность. Существуют и еще более сложные перестановочные фильтры, но компьютеры могут раскрыть почти все из них.

Немецкий шифр 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 может защитить ваши файлы от младшей сестры, но настоящего криптоаналитика задержит лишь на считанные секунды.