Что возможность некоторых алгоритмов шифрования. Алгоритмы шифрования данных

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

На тему:

Алгоритмы шифрования данных

Введение

1. Назначение и структура алгоритмов шифрования

1.1 Обзор криптографических методов

2. Алгоритм симметричного шифрования

2.1 Структура алгоритмов шифрования

3. Применение симметричного алгоритма шифрования

Заключение

Список литературы

Введение

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

Почему проблема использования криптографических методов в информационных системах стала в настоящий момент особо актуальна?

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

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

Что касается расчетов с помощью кредитной карты, то ее недостатки очевидны: необходимо обзаводится картой (а в России еще далеко не все знают, что это такое), есть и опасения, что всем в Интернете станут известны коды вашей кредитки злые люди очистят ваш счет. На самом деле вероятность такого мошенничества не больше той, что при обмене валюты вам подсунут фальшивые деньги. Да и вообще, к электронных денег проблем не больше, чем у обыкновенных. Для проведения расчетов в Сети разработано несколько платежных систем. Которые либо искусно применяют существующие кредитки, либо опираются на чистые электронные деньги, то есть на защищенную систему файлов, в которых хранятся записи о состоянии вашего счета. Таких систем в мире больше десятка, а в России тоже несколько, самая распространенная из которых - CyberPlat.

1. Расчеты в Сети связаны с передачей особой информации, которую нельзя открывать посторонним лицам.

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

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

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

Все это постоянно подталкивает исследователей на создание новых криптосистем и тщательный анализ уже существующих.

Актуальность и важность проблемы обеспечения информационной безопасности обусловлена следующими факторами:

* Современные уровни и темпы развития средств информационной безопасности значительно отстают от уровней и темпов развития информационных технологий.

* Высокие темпы роста парка персональных компьютеров, применяемых в разнообразных сферах человеческой деятельности.

1. Назначение и структура алгоритмов шифрования

Шифрование является наиболее широко используемым криптографическим методом сохранения конфиденциальности информации, он защищает данные от несанкционированного ознакомления с ними. Для начала рассмотрим основные методы криптографической защиты информации. Словом, криптография - наука о защите информации с использованием математических методов. Существует и наука, противоположная криптографии и посвященная методам вскрытия защищенной информации - криптоанализ . Совокупность криптографии и криптоанализа принято называть криптологией . Криптографические методы могут быть классифицированы различным образом, но наиболее часто они подразделяются в зависимости от количества ключей, используемых в соответствующих криптоалгоритмах (см. рис. 1):

1. Бесключевые, в которых не используются какие-либо ключи.

2. Одноключевые - в них используется некий дополнительный ключевой параметр - обычно это секретный ключ.

3. Двухключевые, использующие в своих вычислениях два ключа: секретный и открытый.

Рис. 1. Криптоалгоритмы

1.1 Обзор криптографических методов

Шифрование является основным методом защиты; рассмотрим его подробно далее.

Стоит сказать несколько слов и об остальных криптографических методах:

1. Электронная подпись используется для подтверждения целостности и авторства данных. Целостность данных означает, что данные не были случайно или преднамеренно изменены при их хранении или передаче.

Алгоритмы электронной подписи используют два вида ключей:

o секретный ключ используется для вычисления электронной подписи;

o открытый ключ используется для ее проверки.

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

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

3. Существуют различные методы криптографического контрольного суммирования:

o ключевое и бесключевое хэширование;

o вычисление имитоприставок;

o использование кодов аутентификации сообщений.

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

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

o для подтверждения целостности любых данных в тех случаях, когда использование электронной подписи невозможно (например, из-за большой ресурсоемкости) или является избыточным;

o в самих схемах электронной подписи - "подписывается" обычно хэш данных, а не все данные целиком;

o в различных схемах аутентификации пользователей.

4. Генераторы случайных и псевдослучайных чисел позволяют создавать последовательности случайных чисел, которые широко используются в криптографии, в частности:

o случайные числа необходимы для генерации секретных ключей, которые, в идеале, должны быть абсолютно случайными;

o случайные числа применяются во многих алгоритмах электронной подписи;

o случайные числа используются во многих схемах аутентификации.

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

2 Алгоритм симметричного шифрования

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

Можно представить зашифрование в виде следующей формулы:

С = E k1 (M), где:

M (message) - открытая информация,

С (cipher text) - полученный в результате зашифрования шифртекст,

E (encryption) - функция зашифрования, выполняющая криптографические преобразования над M ,

k1 (key) - параметр функции E , называемый ключом зашифрования.

В стандарте ГОСТ 28147-89 (стандарт определяет отечественный алгоритм симметричного шифрования) понятие ключ определено следующим образом: "Конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразований".

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

Аналогичным образом можно представить и расшифрование:

M" = D k2 (C), где:

M" - сообщение, полученное в результате расшифрования,

D (decryption) - функция расшифрования; так же, как и функция зашифрования, выполняет криптографические преобразования над шифртекстом,

k2 - ключ расшифрования.

Для получения в результате расшифрования корректного открытого текста (то есть того самого, который был ранее зашифрован: M" = M), необходимо одновременное выполнение следующих условий:

1. Функция расшифрования должна соответствовать функции зашифрования.

2. Ключ расшифрования должен соответствовать ключу зашифрования.

При отсутствии верного ключа k2 получить исходное сообщение M" = M с помощью правильной функции D невозможно. Под словом "невозможно" в данном случае обычно понимается невозможность вычисления за реальное время при существующих вычислительных ресурсах.

Алгоритмы шифрования можно разделить на две категории (см. рис. 1):

1. Алгоритмы симметричного шифрования.

2. Алгоритмы асимметричного шифрования.

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

В асимметричном шифровании ключ зашифрования k1 легко вычисляется из ключа k2 таким образом, что обратное вычисление невозможно. Например, соотношение ключей может быть таким:

k1 = a k2 mod p,

где a и p - параметры алгоритма шифрования, имеющие достаточно большую размерность.

Такое соотношение ключей используется и в алгоритмах электронной подписи.

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

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

Симметричное шифрование бывает двух видов:

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

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

Рассмотрим, как выглядят изнутри алгоритмы блочного симметричного шифрования.

2.1 Структура алгоритмов шифрования

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

1. Алгоритмы на основе сети Фейстеля.

Сеть Фейстеля подразумевает разбиение обрабатываемого блока данных на несколько субблоков (чаще всего - на два), один из которых обрабатывается некоей функцией f() и накладывается на один или несколько остальных субблоков. На рис. 2 приведена наиболее часто встречающаяся структура алгоритмов на основе сети Фейстеля.

Рис. 2. Структура алгоритмов на основе сети Фейстеля.

Дополнительный аргумент функции f() , обозначенный на рис. 2 как Ki , называется ключом раунда . Ключ раунда является результатом обработки ключа шифрования процедурой расширения ключа, задача которой - получение необходимого количества ключей Ki из исходного ключа шифрования относительно небольшого размера (в настоящее время достаточным для ключа симметричного шифрования считается размер 128 бит). В простейших случаях процедура расширения ключа просто разбивает ключ на несколько фрагментов, которые поочередно используются в раундах шифрования; существенно чаще процедура расширения ключа является достаточно сложной, а ключи Ki зависят от значений большинства бит исходного ключа шифрования.

Наложение обработанного субблока на необработанный чаще всего выполняется с помощью логической операции "исключающее или" - XOR (как показано на рис. 2). Достаточно часто вместо XOR здесь используется сложение по модулю 2 n , где n - размер субблока в битах. После наложения субблоки меняются местами, то есть в следующем раунде алгоритма обрабатывается уже другой субблок данных.

Такая структура алгоритмов шифрования получила свое название по имени Хорста Фейстеля (Horst Feistel) - одного из разработчиков алгоритма шифрования Lucifer и разработанного на его основе алгоритма DES (Data Encryption Standard) - бывшего (но до сих пор широко используемого) стандарта шифрования США. Оба этих алгоритма имеют структуру, аналогичную показанной на рис. 2. Среди других алгоритмов, основанных на сети Фейстеля, можно привести в пример отечественный стандарт шифрования ГОСТ 28147-89, а также другие весьма известные алгоритмы: RC5, Blowfish, TEA, CAST-128 и т.д.

На сети Фейстеля основано большинство современных алгоритмов шифрования - благодаря множеству преимуществ подобной структуры, среди которых стоит отметить следующие:

o Алгоритмы на основе сети Фейстеля могут быть сконструированы таким образом, что для зашифрования и расшифрования могут использоваться один и тот же код алгоритма - разница между этими операциями может состоять лишь в порядке применения ключей Ki; такое свойство алгоритма наиболее полезно при его аппаратной реализации или на платформах с ограниченными ресурсами; в качестве примера такого алгоритма можно привести ГОСТ 28147-89.

o Алгоритмы на основе сети Фейстеля являются наиболее изученными - таким алгоритмам посвящено огромное количество криптоаналитических исследований, что является несомненным преимуществом как при разработке алгоритма, так и при его анализе.

Существует и более сложная структура сети Фейстеля, пример которой приведен на рис. 3.

Рис. 3. Структура сети Фейстеля.

Такая структура называется обобщенной или расширенной сетью Фейстеля и используется существенно реже традиционной сети Фейстеля. Примером такой сети Фейстеля может служить алгоритм RC6.

2. Алгоритмы на основе подстановочно-перестановочных сетей (SP-сеть - Substitution-permutation network).

В отличие от сети Фейстеля, SP-сети обрабатывают за один раунд целиком шифруемый блок. Обработка данных сводится, в основном, к заменам (когда, например, фрагмент входного значения заменяется другим фрагментом в соответствии с таблицей замен, которая может зависеть от значения ключа Ki ) и перестановкам, зависящим от ключа Ki (упрощенная схема показана на рис. 4).

Рис. 4. Подстановочно-перестановочная сеть.

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

SP-сети распространены существенно реже, чем сети Фейстеля; в качестве примера SP-сетей можно привести алгоритмы Serpent или SAFER+.

3. Алгоритмы со структурой "квадрат" (Square).

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

Структура алгоритма получила свое название от алгоритма Square, который был разработан в 1996 году Винсентом Риджменом (Vincent Rijmen) и Джоан Деймен (Joan Daemen) - будущими авторами алгоритма Rijndael, ставшего новым стандартом шифрования США AES после победы на открытом конкурсе. Алгоритм Rijndael также имеет Square-подобную структуру; также в качестве примера можно привести алгоритмы Shark (более ранняя разработка Риджмена и Деймен) и Crypton. Недостатком алгоритмов со структурой "квадрат" является их недостаточная изученность, что не помешало алгоритму Rijndael стать новым стандартом США.

Рис. 5. Алгоритм Rijndael.

На рис. 5 приведен пример операции над блоком данных, выполняемой алгоритмом Rijndael.

4. Алгоритмы с нестандартной структурой, то есть те алгоритмы, которые невозможно причислить ни к одному из перечисленных типов. Ясно, что изобретательность может быть безгранична, поэтому классифицировать все возможные варианты алгоритмов шифрования представляется сложным. В качестве примера алгоритма с нестандартной структурой можно привести уникальный по своей структуре алгоритм FROG, в каждом раунде которого по достаточно сложным правилам выполняется модификация двух байт шифруемых данных (см. рис. 6).

Рис. 6. Модификация двух байт шифруемых данных.

Строгие границы между описанными выше структурами не определены, поэтому достаточно часто встречаются алгоритмы, причисляемые различными экспертами к разным типам структур. Например, алгоритм CAST-256 относится его автором к SP-сети, а многими экспертами называется расширенной сетью Фейстеля. Другой пример - алгоритм HPC, называемый его автором сетью Фейстеля, но относимый экспертами к алгоритмам с нестандартной структурой.

3. Применение сим метричного алгоритма шифрования

криптография алгоритм симметричный шифрование

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

Схема работы с применением симметричного алгоритма шифрования состоит из следующих этапов:

стороны устанавливают на своих компьютерах программное обеспечение, обеспечивающее шифрование и расшифровку данных и первичную генерацию секретных ключей;

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

отправитель шифрует информацию при помощи установленного программного обеспечения, реализующего симметричный алгоритм шифрования;

зашифрованная информация передается получателю по каналам связи;

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

Ниже приведен обзор некоторых алгоритмов симметричного шифрования:

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

Triple DES. Это усовершенствованный вариант DES, применяющий для шифрования алгоритм DES три раза с разными ключами. Он значительно устойчивее к взлому, чем DES;

Rijndael. Алгоритм разработан в Бельгии. Работает с ключами длиной 128, 192 и 256 бит. На данный момент к нему нет претензий у специалистов по криптографии;

Skipjack. Алгоритм создан и используется Агентством национальной безопасности США. Длина ключа 80 бит. Шифрование и дешифрование информации производится циклически (32 цикла);

IDEA. Алгоритм запатентован в США и ряде европейских стран. Держатель патента компания Ascom-Tech. Алгоритм использует циклическую обработку информации (8 циклов) путем применения к ней ряда математических операций;

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

В соответствии с законодательством США (соглашение International Traffic in Arms Peguiation), криптографические устройства, включая программное обеспечение, относится к системам вооружения.

Поэтому при экспорте программной продукции, в которой используется криптография, требуется разрешение Госдепартамента. Фактически экспорт криптографической продукции контролирует NSA (National Security Agency). правительство США очень неохотно выдаёт подобные лицензии, поскольку это может нанести ущерб национальной безопасности США. Вместе с тем совсем недавно компании Hewlett-Packard выдано разрешение на экспорт её криптографического комплекса Ver Secure в Великобританию, Германию, Францию, Данию и Австралию. Теперь НР может эксплуатировать в эти страны системы, использующие 128-битный криптостандарт Triple DES ,который считается абсолютно надёжным.

ЗАКЛЮЧЕНИЕ

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

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

Однако, этот критерий не учитывает других важных требований к криптосистемам:

* невозможность раскрытия или осмысленной модификации информации на основе анализа ее структуры,

* совершенство используемых протоколов защиты,

* минимальный объем используемой ключевой информации,

* минимальная сложность реализации (в количестве машинных операций), ее стоимость,

* высокая оперативность.

Желательно конечно использование некоторых интегральных показателей, учитывающих указанные факторы.

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

Часто более эффективным при выборе и оценке криптографической системы является использование экспертных оценок и имитационное моделирование.

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

Эллиптические функции также относятся к симметричным методам шифрования.

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

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

Список литературы

1) Чмора А.Л. Современная прикладная криптография. 2-е изд., стер. - М.: Гелиос АРВ, 2004. - 256с.: ил.

2) А.Г. Ростовцев, Н.В. Михайлова Методы криптоанализа классических шифров.

3) А. Саломаа Криптография с открытым ключом.

4) Герасименко В.А. Защита информации в автоматизированных системах обработки данных кн. 1.-М.: Энергоатомиздат. -2004.-400с.

5) Грегори С. Смит. Программы шифрования данных // Мир ПК -2007. -№3.

6) Ростовцев А. Г., Михайлова Н. В. Методы криптоанализа классических шифров. -М.: Наука, 2005. -208 с.

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

Подобные документы

    История появления симметричных алгоритмов шифрования. Роль симметричного ключа в обеспечении степени секретности сообщения. Диффузия и конфузия как способы преобразования бит данных. Алгоритмы шифрования DES и IDEA, их основные достоинства и недостатки.

    лабораторная работа , добавлен 18.03.2013

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

    курсовая работа , добавлен 09.05.2012

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

    курсовая работа , добавлен 20.01.2010

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

    курсовая работа , добавлен 18.09.2016

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

    реферат , добавлен 31.05.2013

    Криптография и шифрование. Симметричные и асимметричные криптосистемы. Основные современные методы шифрования. Алгоритмы шифрования: замены (подстановки), перестановки, гаммирования. Комбинированные методы шифрования. Программные шифраторы.

    реферат , добавлен 24.05.2005

    Автоматизация процесса шифрования на базе современных информационных технологий. Криптографические средства защиты. Управление криптографическими ключами. Сравнение симметричных и асимметричных алгоритмов шифрования. Программы шифрования информации.

    курсовая работа , добавлен 02.12.2014

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

    краткое изложение , добавлен 12.06.2013

    Основные методы криптографической защиты информации. Система шифрования Цезаря числовым ключом. Алгоритмы двойных перестановок и магические квадраты. Схема шифрования Эль Гамаля. Метод одиночной перестановки по ключу. Криптосистема шифрования данных RSA.

    лабораторная работа , добавлен 20.02.2014

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

Государственным стандартом шифрования в России является алгоритм, зарегистрированный как ГОСТ 28147-89. Он является блочным шифром, то есть шифрует не отдельные символы, а 64-битные блоки. В алгоритме предусмотрено 32 цикла преобразования данных с 256-битным ключом, за счет этого он очень надежен (обладает высокой криптостойкостью). На современных компьютерах раскрытие этого шифра путем перебора ключей (“методом грубой силы”) займет не менее сотен лет, что делает такую атаку бес­смысленной. В США используется аналогичный блочный шифр AES .

В Интернете популярен алгоритм RSA, названный так по начальным буквам фамилий его авторов - Р.Райвеста (R.Rivest), А.Шамира (A.Shamir) и ЛАдлемана (L.Adleman). Это алгоритм с открытым ключом, стойкость которого основана на использовании свойств простых чисел. Для его взлома нужно разложить очень большое число на простые сомножители. Эту задачу сейчас умеют решать только перебором вариантов. Поскольку количество вариантов огромно, для раскрытия шифра требуется много лет работы со­временных компьютеров.

Для применения алгоритма RSA требуется построить открытый и секретный ключи следующим образом.

1. Выбрать два больших простых числа, р и q.
2. Найти их произведение n = p * q и значение f = (р - 1) (q - 1)
3. Выбрать число e (1 < e < k), которое не имеет общих делителей с f.
4. Найти число d, которое удовлетворяет условию d e = k f + 1 для некоторого целого k
5. Пара значений (e, n) - это открытый ключ RSA (его можно свободно публиковать), а пара (d, n) - это секретный ключ .

Передаваемое сообщение нужно сначала представить в виде последовательности чисел в интервале от 0 до n - 1. Для шифрования используют формулу y = х e mod n, где х - число исходного сообщения, (e, n) - открытый ключ, y - число закодированного сообщения, а запись х e mod n обозначает остаток от деления х на n. Расшифровка сообщения выполняется по формуле х = y d mod n.
Это значит, что зашифровать сообщение может каждый (открытый ключ общеизвестен), а прочитать его - только тот, кто знает секретный показатель степени d.
Для лучшего понимания мы покажем работу алгоритма RSA на простом примере.
ПРИМЕР: Возьмем р = 3 и q = 7, тогда находим n = р q = 21 и f = (р - 1) (q - 1) = 12. Выберем e = 5, тогда равенство d e = к f + 1 выполняется, например, при d = 17 (и к = 7). Таким образом, мы получили открытый ключ (5, 21) и секретный ключ (17, 21).

Зашифруем сообщение “123” с помощью открытого ключа (5,21). Получаем

1 1 5 mod 21 = 1 ,
2 2 5 mod 21 = 11 ,

3 → 3 5 mod 21 = 12,
то есть зашифрованное сообщение состоит из чисел 1 ,11и 12. Зная секретный ключ (17, 21), можно его расшифровать:

1 → 1 17 mod 21 = 1 ,

11 → 11 17 mod 21 = 2 ,
12 → 12 17 mod 21 = 3 .

Мы получили исходное сообщение.

Конечно, вы заметили, что при шифровании и расшифровке приходится вычислять остаток от деления очень больших чисел (например, 12 17) на n. Оказывается, само число 12 17 в этом случае находить не нужно. Достаточно записать в обычную целочисленную пере­менную, например х, единицу, а потом 17 раз выпол­нить преобразование х = 12*х mod 21. После этого в переменной х будет значение 12 17 mod 21 = 3. Попро­буйте доказать правильность этого алгоритма.
Для того чтобы расшифровать сообщение, нужно знать секретный показатель степени d. А для этого, в свою очередь, нужно найти сомножители р и q, такие что n = р q. Если n велико, это очень сложная задача, ее решение перебором вариантов на современном ком­пьютере займет сотни лет. В 2009 году группа ученых из разных стран в результате многомесячных расчетов на сотнях компьютеров смогла расшифровать сообще­ние, зашифрованное алгоритмом RSA с 768-битным ключом. Поэтому сейчас надежными считаются ключи с длиной 1024 бита и более. Если будет построен рабо­тающий квантовый компьютер, взлом алгоритма RSA будет возможен за очень небольшое время.
При использовании симметричных шифров всегда возникает проблема: как передать ключ, если канал связи ненадежный? Ведь, получив ключ, противник сможет расшифровать все дальнейшие сообщения. Для алгоритма RSA этой проблемы нет, сторонам достаточно обменяться открытыми ключами, которые можно показывать всем желающим.
У алгоритма RSA есть еще одно достоинство: его можно использовать для цифровой подписи сообщений. Она служит для доказательства авторства документов, защиты сообщений от подделки и умышленных изменений.

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

Отправитель может передать вместе с исходным сообщением такое же сообщение, зашифрованное с помощью своего секретного ключа (это и есть цифровая подпись). Получатель расшифровывает цифровую подпись с помощью открытого ключа. Если она совпа­ла с незашифрованным сообщением, можно быть уве­ренным, что его отправил тот человек, который знает секретный код. Если сообщение было изменено при передаче, оно не совпадет с расшифрованной цифровой подписью. Так как сообщение может быть очень длинным, для сокращения объема передаваемых дан­ных чаще всего шифруется не все сообщение, а только его хэш-код.
Во многих современных программах есть возможность шифровать данные с паролем. Например, офисные пакеты OpenOffice.org и Microsoft Office позволяют шифровать все создаваемые документы (для их просмотра и/или изменения нужно ввести пароль). При создании архива (например, в архиваторах 7Zip,WinRAR, WinZip ) также можно установить пароль, без которого извлечь файлы невозможно.
В простейших задачах для шифрования файлов можно использовать бесплатную программу Шифро­вальщик (http://www.familytree.ru/ru/cipher.htm), версии которой существуют для Linux и Windows . Програм­мы TnieCrypt (http://www.truecrypt.org/), BestCrypt (www. jetico.com) и FreeOTFE (freeotfe.org) создают логические диски-контейнеры, информация на которых шифруется. Свободно распространяемая программа DiskCrypto r (diskcryptor.net) позволяет шифровать разделы жестких дисков и даже создавать шифрованные флэш-диски и CD/DVD-диски.
Программа GnuPG (gnupg.org) также относится к свободному программному обеспечению. В ней под­держиваются симметричные и несимметричные шиф­ры, а также различные алгоритмы электронной циф­ровой подписи.

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

Видео YouTube

При передаче сообщений можно не только применять шифрование, но и скрывать сам факт передачи сообщения.


Стеганография - это наука о скрытой передаче информации путем скрытия самого факта передачи информации.

Древнегреческий историк Геродот описывал, например, такой метод: на бритую голову раба записывалось сообщение, а когда его волосы отрастали, он отправлялся к получателю, который брил его голову и читал сообщение.
Классический метод стеганографии - симпатические (невидимые) чернила, которые проявляются только при определенных условиях (нагрев, освещение, хиический проявитель). Например, текст, написанный молоком, можно прочитать при нагреве.
Сейчас стеганография занимается скрытием информации в текстовых, графических, звуковых и видеофайлах с помощью программного “внедрения” в них нужных сообщений.
Простейший способ - заменять младшие биты файла, в котором закодировано изображение. Причем это нужно сделать так, чтобы разница между исходным и полученным рисунками была неощутима для человека. Например, если в черно-белом рисунке (256 оттенков серого) яркость каждого пикселя кодируется 8 битами. Если поменять 1-2 младших бита этого кода, ““встроив” туда текстовое сообщение, фотография, в которой нет четких границ, почти не изменится. При замене 1 бита каждый байт исходного текстового сообщения хранится в млад­ших битах кодов 8 пикселей. Например, пусть первые 8 пикселей рисунка имеют такие коды:

10101101

10010100

00101010

01010010

10101010

10101010

10101011

10101111

Чтобы закодировать в них код буквы “И” (110010002), нужно изменить младшие биты кодов:

1010110 1

1001010 1

0010101 0

0101001 0

1010101 1

1010101 0

1010101 0

1010111 0

Получателю нужно взять эти младшие биты и “собрать” их вместе в один байт.
Для звуков используются другие методы стеганографии, основанные на добавлении в запись коротких условных сигналов, которые обозначают 1 и 0 и не воспри
нимаются

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


Контрольные вопросы:
  1. Какой алгоритм шифрования принят в России в качестве государственного стандарта?
  2. Что такое блочный алгоритм шифрования?
  3. К какому типу относится алгоритм RSA? На чем основана его криптостойкость?
  4. Что такое цифровая подпись?
  5. Как можно использовать алгоритм RSA для цифровой подписи?
  6. Что такое стеганография?
  7. Какие методы стеганографии существовали до изобретения компьютеров?
  8. Как можно добавить текст в закодированное изображение?
  9. На чем основаны методы стеганографии для звуковых и видеоданных?
  10. Что такое цифровые водяные знаки? Зачем они используются?

Задание:

1.Просмотреть материал лекции и ответить на контрольные вопросы.
2. Пройдитесь по ссылкам и познакомьтесь с программами для шифрования файлов.
3. Зашифруйте любой документ в любом из офисных пакетов OpenOffice.org или Microsoft Office и пришлите мне.

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

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

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

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

Симметричный алгоритм шифрования.

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

Для блочных шифров единицей шифрования является блок из нескольких байтов. Результат шифрования зависит от всех исходных байтов этого блока. Блочное шифрование применяется при пакетной передаче информации и кодировании файлов. Блочные шифры шифруют целые блоки информации (от 4 до 32 байт) как единое целое – это значительно увеличивает стойкость преобразований к атаке полным перебором и позволяет использовать различные математические и алгоритмические преобразования.

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

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

Функция

С = ЕК (М),
М = DK (C),
где М – исходный (открытый) блок данных;
С – зашифрованный блок данных.

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

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

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

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

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

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

Примечание

Рассеивание представляет собой распространение влияния одного знака открытого текста на много знаков шифротекста, что позволяет скрыть статистические свойства открытого текста…

Примечание

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

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

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

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

Все действия, производимые блочным криптоалгоритмом над данными, основаны на том факте, что преобразуемый блок может быть представлен в виде целого неотрицательного числа из диапазона, соответствующего его разрядности. Например, 32-битовый блок данных можно интерпретировать как число из диапазона 0 – 4294967295. Кроме того, блок, разрядность которого представляет собой «степень двойки», можно трактовать как сцепление нескольких независимых неотрицательных чисел из меньшего диапазона (указанный выше 32-битовый блок можно также представить в виде сцепления двух независимых 16-битовых чисел из диапазона 0 – 65535 или в виде сцепления четырех независимых 8-битовых чисел из диапазона 0 – 255).

Над этими числами блочный криптоалгоритм производит по определенной схеме следующие действия:

1. Математические функции:
– сложение X’ = X + V;
– «исключающее ИЛИ» X’ = X xor V;
– умножение по модулю 2N + 1 X’ = (X*V) mod (2N + 1);
– умножение по модулю 2N X’ = (X*V) mod 2N.
2. Битовые сдвиги:
– арифметический сдвиг влево X’ = X shl V;
– арифметический сдвиг вправо X’ = X shr V;
– циклический сдвиг влево X’ = X rol V;
– циклический сдвиг вправо X’ = X ror V.
3. Табличные подстановки:
– S-box (англ. substitute) X’ = Table .

В качестве параметра V для любого из этих преобразований может использоваться:

  • фиксированное число (например, X’ = X + 125).
  • число, получаемое из ключа (например, X’ = X + F(K)).
  • число, получаемое из независимой части блока (например, X2’ = X2 + F(X1)).

Примечание

Последний вариант используется в схеме, называемой сетью Фейстеля (по имени ее создателя)…

Сеть Фейстеля.

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

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

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

На основе сети Фейстеля построены американский стандарт шифрования данных DES и наш ГОСТ 28147-89.

09.07.2003

Что такое шифрование?

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

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

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

Основные современные методы шифрования

Среди разнообразнейших способов шифровании можно выделить следующие основные методы:

  • Алгоритмы замены или подстановки - символы исходного текста заменяются на символы другого (или того же) алфавита в соответствии с заранее определенной схемой, которая и будет ключом данного шифра. Отдельно этот метод в современных криптосистемах практически не используется из-за чрезвычайно низкой криптостойкости.
  • Алгоритмы перестановки - символы оригинального текста меняются местами по определенному принципу, являющемуся секретным ключом. Алгоритм перестановки сам по себе обладает низкой криптостойкостью, но входит в качестве элемента в очень многие современные криптосистемы.
  • Алгоритмы гаммирования - символы исходного текста складываются с символами некой случайной последовательности. Самым распространенным примером считается шифрование файлов "имя пользователя.pwl", в которых операционная система Microsoft Windows 95 хранит пароли к сетевым ресурсам данного пользователя (пароли на вход в NT-серверы, пароли для DialUp-доступа в Интернет и т.д.).

Когда пользователь вводит свой пароль при входе в Windows 95, из него по алгоритму шифрования RC4 генерируется гамма (всегда одна и та же), применяемая для шифрования сетевых паролей. Простота подбора пароля обусловливается в данном случае тем, что Windows всегда предпочитает одну и ту же гамму.

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

Симметричные и асимметричные криптосистемы

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

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

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

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

Алгоритм RSA

Алгоритм RSA (по первым буквам фамилий его создателей Rivest-Shamir-Adleman) основан на свойствах простых чисел (причем очень больших). Простыми называются такие числа, которые не имеют делителей, кроме самих себя и единицы. А взаимно простыми называются числа, не имеющие общих делителей, кроме 1.

Для начала выберем два очень больших простых числа (большие исходные числа нужны для построения больших криптостойких ключей. Например, Unix-программа ssh-keygen по умолчанию генерирует ключи длиной 1024 бита).

Определим параметр n как результат перемножения p и q . Выберем большое случайное число и назовем его d , причем оно должно быть взаимно простым с результатом умножения (p -1)*(q -1) .

Отыщем такое число e, для которого верно соотношение

(e*d) mod ((p -1)*(q -1)) = 1

(mod - остаток от деления, т. е. если e, умноженное на d, поделить на ((p -1)*(q -1)) , то в остатке получим 1).

Открытым ключом является пара чисел e и n , а закрытым - d и n .

При шифровании исходный текст рассматривается как числовой ряд, и над каждым его числом мы совершаем операцию

C(i)= (M(i) e) mod n.

В результате получается последовательность C(i) , которая и составит криптотекст. Декодирование информации происходит по формуле

M(i) = (C(i) d) mod n.

Как видите, расшифровка предполагает знание секретного ключа.

Давайте попробуем на маленьких числах.

Установим p=3, q=7 . Тогда n=p*q=21. Выбираем d как 5. Из формулы (e*5) mod 12=1 вычисляем e=17 . Открытый ключ 17, 21 , секретный - 5, 21 .

Зашифруем последовательность «12345»:

C(1)= 1 17 mod 21= 1

C(2)= 2 17 mod 21 =11

C(3)= 3 17 mod 21= 12

C(4)= 4 17 mod 21= 16

C(5)= 5 17 mod 21= 17

Криптотекст - 1 11 12 16 17.

Проверим расшифровкой:

M(1)= 1 5 mod 21= 1

M(2)= 11 5 mod 21= 2

M(3)= 12 5 mod 21= 3

M(4)= 16 5 mod 21= 4

M(5)= 17 5 mod 21= 5

Как видим, результат совпал.

Криптосистема RSA широко применяется в Интернете. Когда вы подсоединяетесь к защищенному серверу по протоколу SSL, устанавливаете на свой ПК сертификат WebMoney либо подключаетесь к удаленному серверу с помощью Open SSH или SecureShell, то все эти программы применяют шифрование открытым ключом с использованием идей алгоритма RSA. Действительно ли эта система так надежна?

Конкурсы по взлому RSA

С момента своего создания RSA постоянно подвергалась атакам типа Brute-force attack (атака методом грубой силы, т. е. перебором). В 1978 г. авторы алгоритма опубликовали статью, где привели строку, зашифрованную только что изобретенным ими методом. Первому, кто расшифрует сообщение, было назначено вознаграждение в размере 100 долл., но для этого требовалось разложить на два сомножителя 129-значное число. Это был первый конкурс на взлом RSA. Задачу решили только через 17 лет после публикации статьи.

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

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

Один из самых распространенных в России почтовых клиентов, программа The Bat!, обладает встроенными возможностями добавлять цифровые подписи к письмам (обратите внимание на пункт меню Privacy при редактировании письма). Подробнее об этой методике читайте в статье (см. «Мир ПК», № 3/02).

Рис. 3

Криптография

Криптография - наука о принципах, средствах и методах преобразования информации для защиты ее от несанкционированного доступа и искажения. В последнее время она развивается очень и очень бурно. Это бесконечная увлекательная гонка, требующая много времени и сил: криптоаналитики взламывают алгоритмы, которые еще недавно были стандартами и повсеместно использовались. Кстати, недавно математики Дэн Голдстон (США) и Кем Илдирим (Турция) доказали первую закономерность в распределении простых чисел (до сих пор таких закономерностей не замечали). Простые числа располагаются на числовой оси некоторыми скоплениями, что несколько облегчает их поиск.

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

Олег Бунин - специалист по разработке ПО для крупных Интернет-проектов, сотрудник компании «Рамблер», [email protected] .

Литература
  1. Лукашов И. В. Криптография? Железно! // Мир ПК. 2003. № 3 (
  2. Носов В. А. Краткий исторический очерк развития криптографии // Материалы конференции "Московский университет и развитие криптографии в России", МГУ, 17-18 октября 2002 г.
  3. Саломаа А. Криптография с открытым ключом. М., 1996 .
  4. Циммерман Ф. PGP - кодирование с открытым ключом для всех.

Система шифрования Цезаря

Пример алгоритма замены - система шифрования Цезаря. Этот метод основан на замене каждой буквы сообщения на другую путем смещения от исходной на фиксированное количество символов. Попробуйте расшифровать четверостишие Омара Хайяма (время выполнения - 10 минут).

РЛЗЬ ЁМЭЙЗ АВБЖУ ИЙЗАВЛУ, БЖЩЛУ ЖЩЭЗЬЖЗ ЖЮЁЩЕЗ, ЭЫЩ ЫЩАЖФО ИЙЩЫВЕЩ БЩИЗЁЖВ ЭЕШ ЖЩРЩЕЩ: ЛФ ЕМРСЮ ЪЗЕЗЭЩГ, РЮЁ РЛЗ ИЗИЩЕЗ ЮКЛУ, В ЕМРСЮ ЬМЭУ ЗЭВЖ, РЮЁ ЫЁЮКЛЮ К ДЮЁ ИЗИЩЕЗ.

Успели? Привожу «отгадку»:

Чтоб мудро жизнь прожить, знать надобно немало,

Два важных правила запомни для начала:

Ты лучше голодай, чем что попало есть,

И лучше будь один, чем вместе с кем попало.

Ключ для расшифровки: сдвигаем на семь символов (берем седьмой) влево по алфавиту. Алфавит закольцован. Регистр символов не учитывается.

Windows и пароли

Как Windows шифрует пароли?

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

Конкурс AES (Advanced Encryption Standard)

В 80-х гг. в США приняли стандарт симметричного шифрования для внутреннего применения - DES ((Data Encryption Standard, подобный стандарт есть и в России). Но в 1997 г., когда стало понятно, что 56-битового ключа DES недостаточно для надежной криптосистемы, Американский институт стандартизации объявил конкурс на новый стандартный алгоритм. Из 15 вариантов был выбран лучший: бельгийский алгоритм Rijndael (его название составлено из фамилий авторов - Rijmen и Daemen, читается как «Рэйндал». Этот алгоритм уже встроен в различные криптографические средства, поставляемые на рынок). Другими финалистами конкурса стали MARS, RC6, Serpent, TwoFish. Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа.

Криптографические хэш-функции

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

  • два разных набора данных с одинаковым результатом преобразования (стойкость к коллизиям); например, количество арифметических операций, необходимых для того, чтобы найти блок данных, также имеющий краткое сообщение для хэш-функции MD5, составляет приблизительно 2 64;
  • входное значение по известному результату хэширования (необратимость); для MD5 предполагаемое количество операций, необходимых для вычисления исходного сообщения, равно 2 128.

Занимательное шифрование