Исследование статистических свойств зашифрованного текста

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсовая работа

Исследование статистических свойств зашифрованного текста

Введение

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

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

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

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

? проблему конфиденциальности (секретности), то есть лишение противника возможности извлечь информацию из канала связи;

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

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

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

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

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

Основное же и принципиальное отличие лежит в архитектуре, то есть устройстве самих шифров и реализующих их алгоритмах. Разделение здесь можно провести следующим образом.

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

Блочные же шифры не обладают таким устройством запоминания своего предыдущего состояния. Криптографическое преобразование данных они осуществляют в зависимости от итерационных подключей, которые вырабатываются из главного ключа. И шифрование строится только на основе ключевой последовательности и криптографичеких примитивов. То есть блочный шифр может сгенерировать все необходимые ему для работы подключи сразу, и зависеть они будут только от исходной ключевой последовательности. Хотя здесь опять возникает некоторая неопределенность, если рассматривать существующие блочные шифры, для которых описаны алгоритмы работы в режиме поточного гаммирования, - это, например, ГОСТ 28147-89 и DES. В таком случае, будучи например, использованным в режиме гаммирования с обратной связью, блочный шифр работает как поточный.

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

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

Соответственно чем больше объем алфавита шифротекста - а это не что иное, как объем пространства шифробозначений и объем пространства шифровеличин (если они совпадают), - тем вычислительно сложнее вскрыть шифр общими и некоторыми частными методами криптоанализа.

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

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

1. История создания шифров

шифр конфиденциальность статистический

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

Несмотря на наличие самых разнообразных систем шифрования, все они основаны либо на принципе перестановки письменных знаков, либо на принципе замены одних знаков другими, либо на соединении обоих принципов вместе. И все они были известны задолго до нынешних дней. Самые древние шифрованные записи датируются вторым тысячелетием до нашей эры и найдены в Месопотамии.

Особое развитие шифры получили в древней Греции. Еще за 380 лет до нашей эры полководец Эней изложил систему тайнописи, в которой буквам открытого текста соответствуют буквы, находящиеся в книжном тексте и отмеченные в нем малозаметными проколами под нужными знаками.

А историк Полибий, живший спустя двести лет после Энея, описал шифр, известный ныне как «квадрат Полибия», где буквы алфавита обозначались парой чисел - координатами их в квадратной таблице.

В первом веке до нашей эры знаменитый римский император Юлий Цезарь предложил «шифр Цезаря», представляющий собой замену букв в соответствии с подстановкой, нижняя строка которой - алфавит открытого текста, сдвинутый на три буквы влево. Это было этапное событие - важнейшая ступень в создании так называемых многоалфавитных шифров.

В то время как в Италии и Франции криптография быстро развивалась, во многих государствах Европы она не продвинулась дальше «шифра Цезаря». Это касается и России. Еще в начале XV века царские дипломаты использовали так называемую «Простую литорею» (или же «Тарабарскую грамоту»). Согласные буквы азбуки разбивались на две равные части и писались навстречу друг другу. После чего происходила взаимная замена одной части ключа буквами другой. Гласные буквы вообще не шифровались. Например, слово «Словарь» трансформировалось в «Лсошамь». Сама же эта система берет свое начало с шифров древних евреев. В старинных русских рукописях встречается и способ, где начальные буквы слов, составляющих маскировочный текст, являются закрытым для непосвященных шифром.

В XV веке в некоторых государствах Европы вместо шифров стали широко использоваться так называемые «жаргонные коды», где тем или иным словам соответствовал совершенно другой смысл.

Интенсивным развитием шифровального дела особенно отмечен век XVI-й. В 1518 году в Германии вышла первая печатная книга, посвященная тайнописи. Автор ее - некий аббат Иоганн Третемий. Помимо прочего, он развил в ней идею многоалфавитного шифра. Третемий ввел метод применения при шифровке нескольких азбук, отличающихся друг от друга порядком расположения букв. При этом каждое новое слово или фраза изображались буквами другого алфавита в условленном порядке. Эта идея оказалась очень плодотворной.

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

Основываясь на идеях Цезаря, Третемия, Беллазо, а так же знаменитого ученого итальянца Джованни де ла Порта, свой шифр создал французский посол в Риме Блез де Виженер. Предложенная им в 1585 году система периодической лозунговой замены стала первым великим открытием в криптографии со времен Юлия Цезаря. «Квадратный шифр» Виженера на протяжении 350 лет считался одной из самых надежных систем. Главным преимуществом метода Виженера являлась его простота. Несмотря на широкое распространение шифра Виженера (особенно в XIX веке), автор его был надолго забыт. Таблица Виженера легко восстанавливалась перед самим процессом шифрования, после чего могла быть уничтожена. Однако в эпоху Возрождения ни шифр Виженера, ни другие периодические многоалфавитные системы не получили достойного применения. Они отнимали слишком много времени, а малейшая ошибка при письме была сопряжена с такими искажениями, что получатель сообщения не мог правильно расшифровать его даже при наличии верного ключа. Сотни лет многоалфавитность оставалась редким явлением и сама ее непопулярность служила ей защитой. Если бы многоалфавитностью пользовались чаще, то, возможно, криптоаналитики средневековья давно бы предложили путь к общему решению по ее дешифровке. Но мир стоял на обычных шифрах замены, и мифу о нераскрываемости шифра Виженера была суждена долгая жизнь. Не найдя широкого применения в дипломатической переписке, эта система начала использоваться в военном деле. В эпоху наполеоновских войн она несправедливо получит имя французского императора, в дальнейшем употребляемое иногда и русскими революционерами.

Идеи Виженера нашли развитие в ряде других подобных периодических систем. Например в «шифре Гронсфельда», придуманном в 1734 году бельгийцем Хосе де Бронкхором, графом де Гронсфельд, военным и дипломатом, начальником первого дешифровального отдела в Германии. Взамен буквенного лозунга-ключа он взял числовой, состоящий из нескольких легко запоминающихся цифр. Вместо большой громоздкой квадратной таблицы использовался только один алфавит с правильным расположением литер. Буква шифруемого текста заменялась буквой алфавита, отстоящей от нее вправо или влево на количество знаков, равное соответствующей цифре ключа. Легко убедиться, что система Гронсфельда является частным случаем более общего шифра Виженера. Таким образом, главными центрами развития криптографии в Европе в XV-XVI веках являлись Италия, Франция и Германия.

Исходным пунктом истории развития современных блочных шифров с секретным ключом является криптографическая система «Люцифер», разработанная в исследовательской лаборатории фирмы IBM в конце 60-х - начале 70-х годов XX века под руководством доктора Хорста Файстеля. В дальнейшем в эту систему были внесены определенные изменения, в результате чего возникла общая архитектура блочных шифров с секретным ключом, получившая название «сеть Файстеля» по имени одного из своих создателей. Эта архитектура доминировала в криптографии до середины девяностых годов.

В 1996 году тремя бельгийскими авторами, Йоаном Даэменом (Joan Daemen), Ларсом Кнудсеном (Lars Knudsen) и Винсентом Райменом (Vincent Rijmen), был предложен блочный шифр SQUARE, ставший впоследствии родоначальником новой архитектуры построения блочных шифров с одноименным названием.

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

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

Одной из особенностей шифра являлась его ориентированность на использование в качестве элементарных операндов не битов и не 32- или 16-битовых слов, а 8-битовых байтов.

2. Шифр DES

DES (Data Encryption Standart) это симметричный алгоритм шифрования, т.е. один ключ используется как для зашифровывания, так и для расшифрования сообщений. Разработан фирмой IBM и утвержден правительством США в 1977 как официальный стандарт.

DES имеет блоки по 64 бит и основан на 16 кратной перестановке данных, также для зашифрования использует ключ в 56 бит. Существует несколько режимов DES, например Electronic Code Book (ECB) и Cipher Block Chaining (CBC).

Ключ состоит из 56 бит - это 8 семибитовых ASCII символов, т.е. пароль не может быть больше чем 8 букв. Если вдобавок использовать только буквы и цифры, то количество возможных вариантов будет существенно меньше максимально возможных 2^56.

Алгоритм использует только стандартную арифметику 64-битовых чисел поэтому он легко реализовывался в аппаратуре второй половины 70-х годов. Множество повторений делает его идеальным для исполнения в специализированной микросхеме.

Алгоритм шифра DES. Предварительно входной блок походит так называемую начальную перестановку Таблица 1. Например начальная позиция перемещает бит 58 в битовую позицию 1, бит 50 в битовую позицию 2, бит 42 в битовую позицию 3. Таоке перемещению облегчает побайтную загрузку текста или шифротекста в микросхему

Таблица 1. Начальные перестановки

58	50	42	34	26	18	10	02
60	52	44	36	28	20	12	04
62	54	46	38	30	22	14	06
64	56	48	40	32	24	16	08
57	49	41	33	25	17	09	01
59	51	43	35	27	19	11	03
61	53	45	37	29	21	13	05
63	55	47	39	31	23	15	07

Далее входной блок данных делится по 32 бита на левую (L0) и правую (R0) части. После этого выполняется 16 этапов одинаковых действий, называемых функцией f, в которых данные объединяются с ключем Рисунок 1.

На каждом этапе биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных (R0) увеличивается до 48 битов с помощью перестановки с расширением, объединяется операцией XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f. Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 раундов.

Рисунок 1. Алгоритм шифра DES

Предварительный процесс перед расширением ключей - перестановка сжатия, которую называют удалением битов проверки. Он удаляет биты четности (биты 8, 16, 24, 32…, 64) из 64-битового ключа. Остающееся значение на 56 битов - фактический ключ шифра, который используется, чтобы генерировать ключи раунда. Биты удаляются с помощью перестановки. После прямой перестановки ключ разделен на две части по 28 битов Рисунок 2. Каждая часть сдвигается влево (циклический сдвиг) на один или два бита. В раундах 1, 2, 9 и 16 смещение - на один бит, в других раундах - на два бита Таблица 2. Затем эти две части объединяются, чтобы создать часть в 56 бит.

Таблица 2. Число сдвигаемых бит ключа в раундах

Раунд	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Число бит	1	1	2	2	2	2	2	2	2	2	2	2	2	2	2	1

Рисунок 2. Формирование ключа

Перестановка с расширением расширяет правую половину данных, R,-, от 32 до 48 битов Рисунок 3. Так как при этом не просто повторяются определенные биты, но и изменяется их порядок, эта операция называется перестановкой с расширением Таблица 3. У нее две задачи: привести размер правой половины в соответствие с ключом для операции XOR и получить более длинный результат, который можно будет сжать в ходе операции подстановки. Однако главный криптографический смысл совсем в другом. За счет влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Это называется лавинным эффектом. DES спроектирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита открытого текста и каждого бита ключа.

Рисунок 3. Перестановка с расширением

Таблица 3. Таблица блока расширения

32	01	02	03	04	05
04	05	06	07	08	09
08	09	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	31	31	32	01

После объединения сжатого блока с расширенным блоком с помощью XOR над 48-битовым результатом выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки, или S-блоках (от substitution). У каждого S-блока б-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 25б байтов памяти.) 48 битов делятся на восемь 6-битовых подблока Рисунок 4. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - S-блоком 1, второй - S-блоком 2, и так далее Таблица 4.

Рисунок 4. Входы и выходы S-блоков

Таблица 4. Таблица S-блоков

S-блок 1
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	04	13	01	02	15	11	08	03	10	06	12	05	09	00	07
1	00	15	07	04	14	02	13	10	03	06	12	11	09	05	03	08
2	04	01	14	07	13	06	02	11	15	12	09	07	03	10	05	00
3	15	12	08	02	04	09	01	07	05	11	03	14	10	00	06	13
S-блок 2
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	15	01	08	14	06	11	03	04	09	07	02	13	12	00	05	10
1	03	13	04	07	15	02	08	14	12	00	01	10	06	09	11	05
2	00	14	07	11	10	04	13	01	05	08	12	06	09	03	02	15
3	13	08	10	01	03	15	04	02	11	06	07	12	00	05	14	09
S-блок 3
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	10	00	09	14	06	03	15	05	01	13	12	07	11	04	02	08
1	13	07	00	09	03	04	06	10	02	08	05	14	12	11	15	01
2	13	06	04	09	08	15	03	00	11	01	02	12	05	10	14	07
3	01	10	13	00	06	09	08	07	04	15	14	03	11	05	02	12
S-блок 4
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	07	13	14	03	00	06	09	10	01	02	08	05	01	12	04	15
1	13	08	11	05	06	15	00	03	04	07	02	12	01	10	14	09
2	10	06	09	00	12	11	07	13	15	01	03	14	05	02	08	04
3	03	15	00	06	10	01	13	08	09	04	05	11	12	07	02	14
S-блок 5
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	02	12	04	01	07	10	11	06	08	05	03	15	13	00	14	09
1	14	11	02	12	04	07	13	01	05	00	15	10	03	09	08	06
2	04	02	01	11	10	13	07	08	15	09	12	05	06	03	00	14
3	11	08	12	07	01	14	02	13	06	15	00	09	10	04	05	03
S-блок 6
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	12	01	10	15	09	02	06	08	00	13	03	04	14	07	05	11
1	10	15	04	02	07	12	09	05	06	01	13	14	00	11	03	08
2	09	14	15	05	02	08	12	03	07	00	04	10	01	13	11	06
3	04	03	02	12	09	05	15	10	11	14	01	07	10	00	08	13
S-блок 7
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	04	11	02	14	15	00	08	13	03	12	09	07	05	10	06	01
1	13	00	11	07	04	09	01	10	14	03	05	12	02	15	08	06
2	01	04	11	13	12	03	07	14	10	15	06	08	00	05	09	02
3	06	11	13	08	01	04	10	07	09	05	00	15	14	02	03	12
S-блок 8
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	13	02	08	04	06	15	11	01	10	09	03	14	05	00	12	07
1	01	15	13	08	10	03	07	04	12	05	06	11	10	14	09	02
2	07	11	04	01	09	12	14	02	00	06	10	10	15	03	05	08
3	02	01	14	07	04	10	05	13	15	19	09	09	03	05	06	11

Подстановка в каждом блоке следует по заранее определенным правилам, основанным на таблице из 4-х строк и 16-ти столбцов. Комбинация битов 1 и 6 на входе определяет одну из четырех строк; комбинация битов от 2-го до 5-го определяет один из шестнадцати столбцов, как показано на Рисунке 5.

Рисунок 5. Правила подстановки в S-блоках

Последняя операция в функции DES - прямая перестановка с 32 битами на входе и 32 битами на выходе. Отношения «вход-выход» для этой операции показаны в Таблица 5. Они следуют тем же самым общим правилам, как и предыдущие таблицы перестановки. Например, седьмой бит входа становится вторым битом выхода.

Таблица 5. Таблица прямой перестановки

16	07	20	21	29	12	28	17
01	15	23	26	05	18	31	10
02	08	24	14	32	27	03	09
19	13	30	06	22	11	04	25

DES позволяет использовать для шифрования или дешифрирования блока одну и ту же функцию. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке. То есть, если на этапах шифрования использовались ключи K_l, K₂, K₃, … K₁₆, то ключами дешифрирования будут K₁₆, K_l5, K_l4,… K_l. Алгоритм, который создает ключ для каждого этапа, также цикличен. Ключ сдвигается направо, а число позиций сдвига равно 0, і, 2, 2, 2, 2, 2, 2, і, 2, 2, 2, 2, 2, 2, і.

3. Шифр ГОСТ №28147-89

Алгоритм как бы состоит из трех уровней. Основной шаг криптопреобразования - самый нижний уровень, на его основе строятся все более высокие части алгоритма. Отталкиваясь от основных шагов строятся базовые циклы: цикл шифрования (32-З), цикл расшифровки (32-Р) и цикл выработки имитовставки (16-З). На самой верхней ступени стоят собственно реальные алгоритмы или циклы (на самом деле стандарт ГОСТ 28147-89 содержит не один, а несколько алгоритмов шифрования), которые строятся на основе базовых циклов.

Данные с которыми работает алгоритм представляются как 32-битовые беззнаковые числа. Перед тем, как предоставить алгоритму данные, их необходимо преобразовать в 32-битные числа. Здесь может возникнуть проблема с тем, что данных не хватит, чтобы заполнить последнее 32-битное число и последний блок данных будет неполным, но эта проблема легко решается с помощью гаммирования. Реальные алгоритмы шифрования и сфера их применения будут рассмотрены далее в этой статье.

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

Ключом в данном алгоритме служит массив из восьми 32-битных чисел. Таким образом, длина ключа составляет 256 бит. Ключ можно представить как таблицу, в которой 8 строк и 32 столбца. Такая конфигурация ключа необходима для работы алгоритма, что будет видно далее.

На входе основного шага определяется 64-битный блок данных N = (N1, N2), где N1 - младшая 32-битовая часть, а N2 - старшая 32-битовая часть. Обе части рассматриваются как отдельные 32-битовые числа. На вход основного шага также поступает один из восьми элементов ключа (какой именно, будет рассказано далее). 32-битовый элемент ключа обозначается за X. Далее производятся следующие действия Рисунок 6.



Рисунок 6. Алгоритм шифра ГОСТ

1.S = N1 + X (mod 232).

2. Число S разбивается на 8 частей: S0, S1, S2, S3, S4, S5, S6, S7 по 4 бита каждая, где S0 - младшая, а S7 - старшая части числа S.

3. Для всех i от 0 до 7: Si = T (i, Si), где T (a, b) означает ячейку таблицы замен с номером строки a и номером столбца b (счет с нуля).

4. Новое число S, полученное на предыдущем шаге циклически сдвигается в сторону старших разрядов на 11 бит.

5.S = S xor N2, где xor - операция исключающего или.

6.N2 = N1.

7.N1 = S.

Таблица 5. Данный набор S-блоков используется в криптографических приложениях ЦБ РФ

Номер S-блока	Значение
1	4	10	9	2	13	8	0	14	6	11	1	12	7	15	5	3
2	14	11	4	12	6	13	15	10	2	3	8	1	0	7	5	9
3	5	8	1	13	10	3	4	2	14	15	12	7	6	0	9	11
4	7	13	10	1	0	8	9	15	14	4	6	12	11	2	5	3
5	6	12	7	1	5	15	13	8	4	10	9	14	0	3	11	2
6	4	11	10	0	7	2	1	13	3	6	8	5	9	12	15	14
7	13	11	4	1	3	15	5	9	0	10	14	7	6	8	2	12
8	1	15	13	0	5	7	10	4	9	2	3	14	6	11	8	12

Как результат основного шага криптопреобразования возвращается блок данных N = (N1, N2), где N2 равно исходному N1, а N1 - результат преобразований основного шага.

Базовые циклы ГОСТ 28147-89 строятся из основных шагов криптопреобразования путем многократного их повторения с различными элементами ключа. Блок данных, с которым работает базовый цикл поступает на его вход один раз в начале работы, а результатом базового цикла является преобразованный блок данных. Как и в основном шаге 64-битный блок данных обозначим через N = (N1, N2), а элементы ключа через X с индексом, означающим номер элемента в ключевом массиве.

Итак, берем блок данных N и вызываем последовательно процедуру основного шага криптопреобразования со следующими ключами:

*Для цикла шифрования (32-З Рисунок 7): X0, X1, X2, X3, X4, X5, X6, X7, X0, X1, X2, X3, X4, X5, X6, X7, X0, X1, X2, X3, X4, X5, X6, X7, X7, X6, X5, X4, X3, X2, X1, X0

*Для цикла расшифровки (32-Р Рисунок 8): X0, X1, X2, X3, X4, X5, X6, X7X7, X6, X5, X4, X3, X2, X1, X0X7, X6, X5, X4, X3, X2, X1, X0X7, X6, X5, X4, X3, X2, X1, X0.

*Для цикла выработки имитовставки (16-З Рисунок 9): X0, X1, X2, X3, X4, X5, X6, X7, X0, X1, X2, X3, X4, X5, X6, X7.

Рисунок 7. Цикл шифрования

Рисунок 8 Цикл расшифровки



Рисунок 9. Имитовставка

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

ГОСТ 28147-89 определяет три основных режима шифрования: простая замена, гаммирование и гаммирование с обратной связью и один дополнительный режим выработки имитовставки.

Рисунок 10 Шифрование простой заменой

Алгоритм шифрования простой заменой следующий. Для каждого блока данных производится однократный вызов базового цикла. При зашифровке используется цикл шифрования Рисунок 10, при расшифровке - цикл расшифровки Рисунок 11. После того, как блок был преобразован базовым циклом, результат цикла заменяет исходный блок данных. Так как данные шифруются блоками по 64-бита и исходный текст постепенно заменяется шифрованным текстом начиная от начала массива данных к концу массива данных.

Рисунок 11 Расшифровка простой замены

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



Рисунок 12. Гаммирование

Для выработки случайных 64-битных чисел в ГОСТ 28147-89 определен специальный математический генератор, называемый рекуррентный генератор последовательности чисел (РГПЧ). РГПЧ используется при шифровании гаммированием. На каждом шаге он выдает 64-битное число, которое по сути состоит из двух 32-битных чисел. Фактически существуют два РГПЧ для старшей и младшей частей. Числа, которые выдает РГПЧ обозначим через Q = (A, B), где A - младшая, а B - старшая части числа. Индекс числа Q обозначает номер шага на котором числа получены, так индекс i - 1 означает предыдущий шаг. Q0 - синхропосылка или начальный заполнитель. Выработка происходит следующим образом:

*Ai = Ai - 1 + C1 (mod 232), где C1 = 101010116.

*Bi = Bi - 1 + C2 (mod 232 - 1), где C2 = 101010416.

*Если Bi = 0, то Bi = 232 - 1.

Число B не может получиться нулевым. Константы C1 и C2 даны в шестнадцатеричной системе счисления.

У этого и следующего режимов есть интересная особенность: т.к. генератор псевдослучайных чисел необходимо инициализировать начальным 64-битным значением, в качестве которого очень часто используется текущее время зашифровки. В качестве синхропосылки или начального заполнителя ГОСТ 28147-89 определяет не само число, полученное из какого-либо источника, а результат зашифровки этого числа по алгоритму шифрования. Используя текущее время или что-то иное в качестве начального заполнителя необходимо это число предварительно зашифровать, а затем уже инициализировать им генератор. Итак, чтобы зашифровать массив данных необходимо выработать синхропосылку и зашифровать ее циклом шифрования. При этом получится начальный заполнитель генератора чисел. Затем, для каждого 64-битного блока данных из массива данных, необходимо выработать очередное число с помощью генератора чисел, зашифровать это число циклом шифрования и наложить полученное число на блок данных при помощи операции исключающего или. При зашифровке последнего неполного блока данных допускается накладывать не все число, а только его часть, равную длине данных в последнем неполном блоке.

Гаммирование с обратной связью позволяет зацепить блоки один за другой и любое изменение хотя бы одного бита в каком-либо месте шифротекста повлечет за собой при расшифровке повреждение информации во всех последующих блоках, что легко заметить Рисунок 13.

Имитовставка - это контрольная комбинация, зависящая от открытых данных и секретной ключевой информации. Целью использования имитовставки является обнаружение всех случайных или преднамеренных изменений в массиве данных. Для потенциального злоумышленника две следующие задачи практически неразрешимы, если он не владеет ключевой информацией: вычисление имитовставки для заданного открытого массива данных; подбор открытых данных под заданную имитовставку. Алгоритм выработки имитовставки:



Рисунок 13. Гаммирование с обратной связью

*S = 0

*Для каждого 64-битного блока данных из массива данных: S = F (S xor Ti), где Ti - блок данных, F - базовый цикл выработки имитовставки (16-З), xor - операция исключающего или.

*S - полученная имитовставка.

В качестве имитовставки можно использовать лишь часть полученного числа S, но следует помнить, что вероятность успешного навязывания ложных данных равна величине 2-L, где L - длина используемой части числа в битах. Обычно используются младшие 32 бита числа S Рисунок 14.

Рисунок 14. Иммитовставка

4. Сравнение шифров

Основные характеристики шифров DES и ГОСТ приведены в Таблице 6.

Таблица 6. Основные характеристики

Параметр	ГОСТ	DES
1. Размер блока шифрования	64 бита	64 бита
2. Длина ключа	256 бит	56 бит
3. Число раундов	32	16
4. Узлы замен (S-блоки)	не фиксированы	фиксированы
5. Длина ключа для одного раунда	32 бита	48 бит
6. Схема выработки раундового ключа	простая	сложная
7. Начальная и конечная перестановки битов	нет	есть

Из других отличий ГОСТа от DES'а надо отметить следующее:

На каждом раунде шифрования используется «раундовый ключ», в DES'е он 48-битовый и вырабатывается по относительно сложному алгоритму, включающему битовые перестановки и замены по таблице, в ГОСТе он берется как фрагмент ключа шифрования. Длина ключа шифрования в ГОСТе равна 256 битам, длина раундового ключа - 32 битам, итого получаем, что ключ шифрования ГОСТа содержит 256/32=8 раундовых ключей. В ГОСТе 32 раунда, следовательно, каждый раундовый ключ используется 4 раза, порядок использования раундовых ключей установлен в ГОСТе и различен для различных режимов.

Таблица замен в ГОСТе - аналог S-блоков DES'а - представляет собой таблицу (матрицу) размером 8x16, содержащую число от 0 до 15. В каждой строке каждое из 16-ти чисел должно встретиться ровно 1 раз. В отличие от DES'а, таблица замен в ГОСТе одна и та же для всех раундов и не зафиксирована в стандарте, а является сменяемым секретным ключевым элементом. От качества этой таблицы зависит качество шифра. При «сильной» таблице замен стойкость шифра не опускается ниже некоторого допустимого предела даже в случае ее разглашения. И наоборот, использование «слабой» таблицы может уменьшить стойкость шифра до недопустимо низкого предела. Никакой информации по качеству таблицы замен в открытой печати России не публиковалось, однако существование «слабых» таблиц не вызывает сомнения - примером может служить «тривиальная» таблица замен, по которой каждое значение заменяется на него самого. Это делает ненужным для компетентных органов России ограничивать длину ключа - можно просто поставить недостаточно «сильную» таблицу замен. В ГОСТе, в отличие от DES'а, нет начальной и конечной битовых перестановок шифруемого блока, которые, по мнению ряда специалистов, не влияют существенно на стойкость шифра, хотя влияют (в сторону уменьшения) на эффективность его реализации.

Многие алгоритмы, включая DES и ГОСТ, построены по одному и тому же принципу: Процесс шифрования состоит из набора раундов-шагов, на каждом шаге выполняются следующие действия.

Входной блок делится пополам на старшую (L) и младшую (R) части. Вычисляется значение функции шифрования от младшей части (R) и раундового ключа (k) X=f (R, k).Используемая на данном шаге функция и называется фукцией шифрования ракдов. Она может быть одна для всех раундов, или индивидуальна для каждого раунда. В последнем случае функции шифрования различных раундов одного шифра отличаются, как правило, лишь в деталях. Формируется выходной блок, его старшая часть равна младшей части входного блока L'=R, а младшая часть это результат выполнения операции побитового исключающего или (обозначим его (+)) для старшая части входного блока и результата вычисления функции шифрования R'=L(+) f (R, k).

Функция шифрования ГОСТа очень проста. Младшая часть блока R и раундовый ключ складываются по модулю 2^32. Полученное значение преобразуется по таблице замен - оно делится на 8 4-битовых групп, и каждая группа заменяется на новое значение с использованием соответствующего узла замен. Полученное значение циклически сдвигается на 11 бит влево. В отличие от DES'а очень простая и легко реализуемая функция шифрования. И последнее: ГОСТ не запатентован, поэтому его может свободно использовать любое юридическое и физическое лицо, если, конечно, это не противоречит законодательству страны где находятся это лицо. Со стороны авторов ГОСТа претензий нет и быть не может, так как юридические права на алгоритм ни за кем не закреплены.

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

Исчерпывающий ответ на вопрос о критериях качества ключей и таблиц замен ГОСТа если и можно вообще где-либо получить, то только у разработчиков алгоритма. Соответствующие данные не были опубликованы в открытой печати. Однако согласно установленному порядку, для шифрования информации, имеющей гриф, должны быть использованы ключевые данные, полученные от уполномоченной организации. Косвенным образом это может свидетельствовать о наличии методик проверки ключевых данных на «вшивость». Если наличие слабых ключей в ГОСТе - дискуссионный вопрос, то наличие слабых узлов замены не вызывает сомнения. Очевидно, что «тривиальная» таблица замен, по которой любое значение заменяется им же самим, является настолько слабой, что при ее использовании шифр взламывается элементарно, каков бы ни был ключ.

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

Ключ должен являться массивом статистически независимых битов, принимающих с равной вероятностью значения 0 и 1. Нельзя полностью исключить при этом, что некоторые конкретные значения ключа могут оказаться «слабыми», то есть шифр может не обеспечивать заданный уровень стойкости в случае их использования. Однако, предположительно, доля таких значений в общей массе всех возможных ключей ничтожно мала. По крайней мере, интенсивные исследования шифра до сих пор не выявили ни одного такого ключа ни для одной из известных (т.е. предложенных ФАПСИ) таблиц замен. Поэтому ключи, выработанные с помощью некоторого датчика истинно случайных чисел, будут качественными с вероятностью, отличающейся от единицы на ничтожно малую величину. Если же ключи вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше статистические характеристики, и, кроме того, обладать высокой криптостойкостью, - не меньшей, чем у самого ГОСТа. Иными словами, задача определения отсутствующих членов вырабатываемой генератором последовательности элементов не должна быть проще, чем задача вскрытия шифра. Кроме того, для отбраковки ключей с плохими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев, - для проверки равновероятного распределения битов ключа между значениями 0 и 1 обычно используется критерий Пирсона («хи квадрат»), а для проверки независимости битов ключа - критерий серий. Об упомянутых критериях можно прочитать в учебниках или справочниках по математической статистике.

Наилучшим подходом для выработки ключей было бы использование аппаратных датчиков СЧ, однако это не всегда приемлемо по экономическим соображениям. При генерации небольшого по объему массива ключевой информации разумной альтернативой использованию такого датчика является и широко используется на практике метод «электронной рулетки», когда очередная вырабатываемая порция случайных битов зависит от момента времени нажатия оператором некоторой клавиши на клавиатуре компьютера. В этой схеме источником случайных данных является пользователь компьютера, точнее - временные характеристики его реакции. За одно нажатие клавиши при этом может быть выработано всего несколько битов случайных данных, поэтому общая скорость выработки ключевой информации при этом невелика - до нескольких бит в секунду. Очевидно, данный подход не годится для получения больших массивов ключей. [2]

В случае же, когда необходимо выработать большой по объему массив ключевой информации, возможно и очень широко распространено использование различных программных датчиков псевдослучайных чисел. Поскольку от подобного датчика требуются высокие показатели криптостойкости, естественным является использование в качестве него генератора гаммы самого шифра - просто «нарезаем» вырабатываемую шифром гамму на «куски» нужного размера, для ГОСТа - по 32 байта. Конечно, для такого подхода нам потребуется «мастер-ключ», который мы можем получить описанным выше методом электронной рулетки, а с его помощью, используя шифр в режиме генератора гаммы, получаем массив ключевой информации нужного нам объема. Так эти два способа выработки ключей, - «ручной» и «алгоритмический», - работают в тандеме, дополняя друг друга. Схемы генерации ключей в «малобюджетных» системах криптозащиты информации практически всегда построены по такому принципу.

В силу намного большей длины ключа ГОСТ гораздо устойчивей DES'а к вскрытию «грубой силой» - путем полного перебора по множеству возможных значений ключа. Функция шифрования ГОСТа гораздо проще функции шифрования DES'а, она не содержит операций битовых перестановок, коими изобилует DES и которые крайне неэффективно реализуются на современных универсальных процессорах (хотя очень просто аппаратно - путем разводки проводников в кристалле или на плате). В силу сказанного, при вдвое большем количестве раундов (32 против 16) программная реализация ГОСТа на процессорах Intel x86 более чем в 2 раза превосходит по быстродействию реализацию DES'а.

Что касается устойчивости шифра к взлому «экстенсивными» методами, то есть к «переборной» атаке, тот тут все более или менее ясно: ключ размером 64 бита находится где-то на грани доступности этому виду атаки, шифр с ключом 96 бит и выше (помните, что ключ должен содержать целое число 32-битовых элементов) вполне устойчив против него. Действительно, несколько лет назад прежний стандарт шифрования США, DES, был неоднократно взломан переборным путем, - сначала его взломала вычислительная сеть, организованная на базе глобальной сети Интернет, а затем - специализированная, т.е. сконструированная специально для этого вычислительная машина. Примем, что стандартный вариант ГОСТа при программной реализации на современных процессорах работает вчетверо быстрее DES. Тогда 8-раундовый «редуцированный ГОСТ» будет работать в 16 раз быстрее DES. Примем также, что за прошедшее с момента взлома DES время производительность вычислительной техники согласно закону Мура возросла вчетверо. Получаем в итоге, что сейчас проверка одного 64-битового ключа для «редуцированного ГОСТа» с восемью циклами осуществляется в 64 раза быстрее, чем в свое время выполнялась проверка одного ключа DES. Таким образом, преимущество такого варианта ГОСТа перед DES по трудоемкости переборной атаки сокращается с 2^64-56 = 2⁸ = 256 до 256/64 = 4 раз. Согласитесь, это весьма иллюзорное различие, почти что ничего.

Гораздо сложнее оценить устойчивость ослабленных модификаций ГОСТа к «интенсивным» способам криптоанализа. Однако общую закономерность можно проследить и здесь. Дело в том, что «профильные» характеристики многих наиболее сильных на сегодняшний момент видов криптоанализа зависят экспоненциально от числа раундов шифрования. Так, для линейного криптоанализа (ЛКА) это будет характеристика линейности L:

где C и - константы, R - число раундов. Аналогичная зависимость существует и для дифференциального криптоанализа. По своему «физическому смыслу» все характеристики такого рода - вероятности. Обычно объем необходимых для криптоанализа исходных данных и его трудоемкость обратно пропорциональны подобным характеристикам. Отсюда следует, что эти показатели трудоемкости растут экспоненциально с ростом числа основных шагов шифрования. Поэтому при снижении числа раундов в несколько раз трудоемкость наиболее известных видов анализа изменится как, - очень приблизительно и грубо, - корень этой степени из первоначального количества. Это очень большое падение стойкости.[2]

С другой стороны, ГОСТ проектировался с большим запасом прочности и на сегодняшний день устойчив ко всем известным видам криптоанализа, включая дифференциальный и линейный. Применительно к ЛКА это означает, что для его успешного проведения требуется больше пар «открытый блок - зашифрованный блок», чем «существует в природе», то есть более 2⁶⁴. С учетом сказанного выше это означает, что для успешного ЛКА 16-раундового ГОСТа потребуется не менее блоков или 2³⁵ байтов или 32 Гбайта данных, а для 8-раундового - не менее блоков или 2¹⁹ байтов или 0.5 Мбайт.

Заключение

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

Список использованной литературы

1. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.

2. Винокуров А. Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86.

3. www.enlight.ru Винокуров А. «Энциклопедия блочных шифров».

Размещено на Allbest.ru