Не всегда криптография и криптоанализ так просты, как в примерах из этой главы. Криптоанализ более сложных шифров требует более основательных знаний в области математики и теории передачи данных.
В некоторых алгоритмах шифрования для шифрования и расшифровки используется один и тот же ключ, или дешифровальный ключ может быть вычислен по шифровальному ключу за небольшое время. Такие алгоритмы называются алгоритмами с секретным ключом, алгоритмами с закрытым ключом или симметричными алгоритмами. Ключ используемый в таких алгоритмах должен храниться в тайне. Примером алгоритма с секретным ключом является алгоритм 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 бита зашифрованного текста. Алгоритм заключается в не зависящей от ключа перестановке входных данных с последующим шифрованием их с помощью открытого ключа, после чего осуществляется обратная перестановка данных.
Алгоритм 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
В связи с популярностью алгоритма DES и его недостатками, выявленными во второй половине 90-х годов, криптографы искали способы повышения его стойкости, при одновременном сохранении его в качестве базового алгоритма шифрования. В алгоритмах DESede выполняется троекратное шифрование по алгоритму DES, что приводит к эффективной длине ключа в 168 разрядов. В одном из вариантов DESede третий ключ равен первому, эффективная длина ключа в таком случае составляет 112 разрядов.
Blowfish – это шифр с секретным ключом, разработанный Брюсом Шейнером, ведущим специалистом-криптографом, автором нашумевшей книги Applied Cryptography (Прикладная криптография). Этот алгоритм на запатентован, он бесплатный и беспошлинный, и на его использование не требуется лицензии.
Blowfish является 64-х-разрядным блочным шифром, предназначенным для встраиваемой замены алгоритма DES. Он превосходит DES по скорости шифрования и намного – по стойкости. Длина его ключа варьируется от 32-х до 448-и разрядов.
В предыдущих главах рассматривались методы шифрования с закрытым ключом. Но шифрование с секретным ключом – это не единственный способ шифрования данных. Одним из наиболее значительных прорывов в криптографии двадцатого столетия была разработка шифрования с открытым ключом.
Алгоритмы с открытым ключом, или асимметричные алгоритмы, базируются на использовании отдельных шифровального (открытого – public) и дешифровального (закрытого – private) ключей. В алгоритмах с открытым ключом требуется, чтобы закрытый ключ было невозможно вычислить по открытому ключу. Исходя из этого требования шифровальный ключ может быть доступным кому угодно без какого-либо ущерба безопасности алгоритма шифрования.
Этот алгоритм известен как 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), осуществляется путем вычисления mc mod n.
5.Расшифровка зашифрованного числа c осуществляется путем вычисления cd mod m.
Основным недостатком шифра RSA и других алгоритмов с открытым ключом, является их низкая производительность, по сравнению с алгоритмами с секретным ключом. Алгоритм RSA уступает по скорости сопоставимым реализациям алгоритма DES в 100, а то и в 1000 раз.
Хотя шифр RSA еще никому не удалось раскрыть, прогресс в математике может сделать этот шифр устаревшим. При наличии эффективного способе разложения больших чисел на множители шифр RSA можно легко раскрыть. К тому же алгоритм RSA и другие алгоритмы с открытым ключом не защищены от множества атак, которые определяются способами использования этих алгоритмов.
Хотя RSA и является одним из самых популярных алгоритмов шифрования с открытым ключом, имеется также множество других алгоритмов. Один из них – алгоритм AlGamal, разработанный в 1984 г. Тэгером Эль-Гамалом. Он не запатентован и может использоваться свободно.
Защищенность алгоритма AlGamal базируется на сложности вычисления дискретного логарифма в конечном поле. А заключается алгоритм в следующем:
1.Выбирается простое число p и два случайных числа, g и x, меньших чем p.
2.Открытый ключ состоит из чисел g, p, и y, где y=gx mod p. Закрытым ключом является число x.
3.Для шифрования блока сообщения m, выбирается случайное чтило k, такое, что k и (p-1) взаимно простые числа, и вычисляется a=gk mod p. Зашифрованным блоком являются оба числа – a и b.
4.Для расшифровки a и b вычисляется m=(b/ax) mod p.
Область применения криптографических методов не ограничивается только защитой тайны сообщений. Они также используются в следующих областях:
1. Целостность – для обнаружения фактов изменения или подмены сообщения
2. Аутентификация – для проверки того, что сообщение действительно создано лицом или организацией, от имени которой они поступили.
3. Неаннулируемость – для недопущения того, чтобы тот, кто послал сообщение или выполнил некоторую операцию над объектом, мог отрицать тот факт, что именно он сделал это.
Перечисленные задачи решаются с помощью дайджестов сообщений и цифровых подписей.
Дайджест сообщения – это особый вид функции, носящей название односторонней функции или функции хеширования. Одностороннюю функцию легко вычислить, но сложно обращать. Функции дайджеста сообщения должны обладать следующими свойствами:
· По конкретному значению дайджеста сообщения невозможно численными методами установить сообщение, по которому функция дайджеста сообщения вычислила это значение.
· Невозможно численными методами найти два различных сообщения, по которым функция дайджеста сообщения вычислила совпадающие значения.