Понятие и сущность криптографии

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

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

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

2. Шифрование  с секретным ключом

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

1. Стандарт Data Encryption Stantart (DES).

     В 1997 г. в США Национальным Институтом Стандартов и Технологий (NIST) в качестве стандартного алгоритма шифрования для защиты несекретной информации был принят алгоритм DES. Этот алгоритм вполне уверенно противостоял открытым попыткам взлома вплоть до середины 90-х годов, когда были отмечены попытки взлома с использованием методов дифференциального и линейного криптоанализа. К январю 1999 г. фонду Electronic Frontier Foundation уже удавалось взламывать сообщения, зашифрованные с помощью алгоритма DES, не более чем за сутки.

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

     В алгоритме DES используется 64-х-разрядный  ключ – 8 битов применяются для  исправления ошибок (контроля четности). В результате эффективная длина  ключа составляет 56 бит. Шифрование и расшифровка в алгоритме DES осуществляется блоками по 64 бита (8 байтов), и из 64 битов открытого текста получается 64 бита зашифрованного текста. Алгоритм заключается в не зависящей от ключа перестановке входных данных с последующим шифрованием их с помощью открытого ключа, после чего осуществляется обратная перестановка данных.

2. Методы  шифрования

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

• Метод ECB (Electronic Codebook – Электронная шифровальная книга) – шифрование осуществляется 8-и-байтовыми блоками, причем последующий блок зашифрованного текста не зависит от предыдущих блоков как зашифрованного, так и открытого текста.
• Метод CBC (Cipher Block Changing – Сцепление зашифрованных блоков) – n-ный блок шифруемого текста получается в результате выполнения операции XOR (исключающего или) над (n-1)-м блоком защифрованного текста и n-ным блоком открытого текста.
• Метод CFB (Cipher Feedback – Обратная связь по шифру) – предыдущая порция зашифрованного текста объединяется со следующей порцией открытого текста.
• Метод OFB (Output Feedback – Обратная связь по выходу) – алгоритм DES используется для создания псевдослучайного потока битов, который объединяется с открытым текстом, в результате чего создается поток зашифрованного текста.
• Метод PCBC (Propagating Cipher Block Changing – Сцепление зашифрованных блоков с множественной связью) – Отличается от метода CBC тем, что с n-ным блоком зашифрованного текста объединяется как (n-1)-й блок зашифрованного текста, так и (n-1)-й блок открытого текста.

     Когда требуется зашифровать не 8-и-байтовый, а более короткий блок открытого  текста (например, последние байты  файла или сообщения), он дополняется  до заполнения 64-х-разрядного регистра. В связи с этим возникает проблема – как при расшифровке отличить исходный текст от дополняющих байтов. Для решения этой проблемы компанией RSA Data Encryption, Inc. Был разработан стандарт под названием “Public Key Cryptography Standart #5 padding ” (“Дополнение к стандарту шифрования с открытым ключом #5”). Это дополнение заключается в следующем: “Если n – число байтов, которыми нужно дополнить блок, то значение каждого дополняющего байта устанавливается в n. Если дополнение не требуется, то добавляется один блок, в котором значение каждого байта устанавливается в 8”

     Методы  шифрования и дополнения блоков, используемые с алгоритмом DES, по своей природе, универсальны и могут быть использованы с другими шифрами, такими, например, как DESede или Blowfish

3. Алгоритм DESede

     В связи с популярностью алгоритма DES и его недостатками, выявленными во второй половине 90-х годов, криптографы искали способы повышения его стойкости, при одновременном сохранении его в качестве базового алгоритма шифрования. В алгоритмах DESede выполняется троекратное шифрование по алгоритму DES, что приводит к эффективной длине ключа в 168 разрядов. В одном из вариантов DESede третий ключ равен первому, эффективная длина ключа в таком случае составляет 112 разрядов.

4. Алгоритм Blowfish

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

     Blowfish является 64-х-разрядным блочным шифром, предназначенным для встраиваемой замены алгоритма DES. Он превосходит DES по скорости шифрования и намного – по стойкости. Длина его ключа варьируется от 32-х до 448-и разрядов.

3. Шифрование с открытым ключом

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

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

1. Алгоритм  Ривеста-Шамира-Эдлемана

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

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

     Ниже  кратко описан принцип действия алгоритма RSA:

1. Генерируется два простых числа p и q (100 цифр и более), причем n=pq.
2. В качестве открытого ключа выбирается целое число e, взаимно простое с числом (p-1)(q-1).
3. Закрытый ключ d вычисляется из условия ed mod (p-1)(q-1) = 1.
4. Шифрование открытого числа m (где m < n), осуществляется путем вычисления m^c mod n.
5. Расшифровка зашифрованного числа c осуществляется путем вычисления c^d mod m.

     Основным  недостатком шифра RSA и других алгоритмов с открытым ключом, является их низкая производительность, по сравнению с  алгоритмами с секретным ключом. Алгоритм RSA уступает по скорости  сопоставимым реализациям алгоритма DES в 100, а то и в 1000 раз.

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

2. Алгоритм AlGamal

     Хотя RSA и является одним из самых популярных алгоритмов шифрования с открытым ключом, имеется также множество других алгоритмов. Один из них – алгоритм AlGamal, разработанный в 1984 г. Тэгером Эль-Гамалом. Он не запатентован и может использоваться свободно.

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

1. Выбирается простое число p и два случайных числа, g и x, меньших чем p.
2. Открытый ключ состоит из чисел g, p, и y, где y=g^x mod p. Закрытым ключом является число x.
3. Для шифрования блока сообщения m, выбирается случайное чтило k, такое, что k и (p-1) взаимно простые числа, и вычисляется a=g^k mod p. Зашифрованным блоком являются оба числа – a и b.
4. Для расшифровки a и b вычисляется m=(b/a^x) mod p.

5. Дайджесты сообщений

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

1. Целостность – для обнаружения фактов изменения или подмены сообщения
2. Аутентификация – для проверки того, что сообщение действительно создано лицом или организацией, от имени которой они поступили.
3. Неаннулируемость – для недопущения того, чтобы тот, кто послал сообщение или выполнил некоторую операцию над объектом, мог отрицать тот факт, что именно он сделал это.

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

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

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

     Заметьте, в самой функции дайджеста  сообщений никакого секрета нет  – она общедоступна и не использует ключей. Примерами алгоритма дайджеста  сообщения являются алгоритмы MD5 и SHA-1.

6. Цифровые  подписи и цифровые сертификаты

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

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