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

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

• Алгоритмы с открытым ключом
• Алгоритмы с секретным ключом
• Блочные методы шифрования
• Криптографические хэш-функции
• Генераторы случайных чисел

Алгоритмы с открытым ключом

• RSA (Rivest-Shamir-Adelman) является наиболее известным алгоритмом с открытым ключом. Может использоваться как для шифрования, так и для создания подписи. Считается, что алгоритм надежен при использовании достаточно длинных ключей (значение 512 бит считается недостаточным, 768 бит - умеренно надежным, 1024 бит - хорошим). Безопасность RSA основана на проблеме факторизации больших целых чисел. Существенные продвижения в способах факторизации больших чисел могут сделать метод RSA уязвимым. В настоящее время RSA является наиболее важным алгоритмом с открытым ключом. Он запатентован в США (патент оканчивается в 2000 году), и бесплатен в остальной части мира.

  В настоящее время, 512-битные ключи считаются слабозащищенными, 1024-битные ключи вероятно подходят для большинства практических целей, 2048-битные ключи будут безопасны для использования в течении десятилетий.

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

  Многие реализации RSA доступны свободно. Смотри, например, RSAREF , RSAEURO, SSLeay, исходные тексты PGP, исходные тексты Ssh и библиотеку Crypto++. См. также ftp.funet.fi:/pub/crypt/cryptography/asymmetric/rsa.

  Дополнительную информацию можно почерпнуть из

  • Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1994.
  • Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to Computer Security. Prentice-Hall, 1989.
  • Man Young Rhee: Cryptography and Secure Data Communications. McGraw-Hill, 1994.
  • R. Rivest, A. Shamir, and L. M. Adleman: Cryptographic Communications System and Method. US Patent 4,405,829, 1983.
  • Hans Riesel: Prime Numbers and Computer Methods for Factorization. Birkhauser, 1994.
  • The RSA Frequently Asked Questions document by RSA Data Security, Inc., 1995.
  • RSA in 3 lines of perl by Adam Back <aba@atlax.ex.ac.uk>, 1995.
  • Страница Шерри Мэйо содержит описание алгоритма RSA.

• Шифр Диффи-Хеллмана (Diffie-Hellman) является известным алгоритмом с открытым ключом, используемый для обмена ключами. Он считается надежным, если используются достаточно длинные ключи и подходящие генераторы. Безопасность шифра Диффи-Хеллмана основана на сложности решения проблемы дискретного логарифма (ее считают равноценной по сложности задаче факторизации больших чисел). Объявлено, что алгоритм Диффи-Хеллмана запатентован в США, однако патент заканчивается 29 апреля 1997 года. Также ходят упорные слухи, что патент на самом деле недействителен (существует свидетельство, что алгоритм был опубликован за год до того, как был выдан патент).

  Алгоритм Диффи-Хеллмана чувствителен к выбору надежного простого числа и генератора. Один из возможных выборов пары простое число/генератор предложен в спецификациях системы Фотурис (Photuris). Размер экспоненты секретного числа также важен для надежности алгоритма. Совет здесь может быть таким: надо выбирать экспоненту длиной по крайней мере в два раза больше, чем используемый ключ сессии.

  Необходимо также принимать во внимание результаты, представленные в статье Brian A. LaMacchia and Andrew M. Odlyzko, Computation of Discrete Logarithms in Prime Fields, Designs, Codes and Cryptography 1 (1991), 47-62. Авторы показали, что путем выполнения предварительных вычислений можно эффективно вычислять дискретный логарифм относительно заранее заданного простого числа. Объем предварительных вычислений примерно равен или немного выше затрат, необходимых для факторизации композитного числа того же размера. На практике сие означает, что если одно и то же простое число используется для нескольких сессий, оно должно быть размером более 512 бит, желательно 1024 бита.

  Имеется также новый метод атаки - атака с использованием таймера с помощью которй можно вскрыть многие реализации шифра Диффи-Хеллмана.

  Многие реализации шифра Диффи-Хеллмана доступны бесплатно. См. например RSAREF, RSAEURO, SSLeay, alodes, или Crypto++.

  Более подробную информацию смотри

  • Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1994.
  • Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to Computer Security. Prentice-Hall, 1989.
  • Man Young Rhee: Cryptography and Secure Data Communications. McGraw-Hill, 1994.
  • M. E. Hellman and R. C. Merkle: Public Key Cryptographic Apparatus and Method. US Patent 4,218,582, 1980.
  • The RSA Frequently Asked Questions document by RSA Data Security, Inc., 1995.

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

  Подробнее смотри, например

  • Bruce Schneier: Applied Cryptography, 2nd edition. John Wiley & Sons, 1995.
  • IEEE P1363 Draft Standard on Elliptic Curve Cryptosystems and Related Methods.
  • Marc Joye's Page about elliptic curves (ссылки и литература).

  Доступны несколько свободных реализаций. См., например пакет eliptic.

• DSS (Digital Signature Standard). Метод, используемый только для генерации подписи. Используется правительством США. Детали его реализации пока не опубликованы, но многие уже нашли в нем потенциальные проблемы (например, утечка скрытых в подписи данных; если же вам посчасливится подписать пару разных сообщений с использованием одного и того же случайного числа, это равносильно открытию секретного ключа). Этот алгоритм недавно запатентован американским правительством, и имеется на него еще один патент, который может быть лицензирован в США и Европе за начальный взнос в 25 000 американских долларов плюс отчисления владельцу патента.

  Нет никаких причин использовать DSS для чего бы то ни было (с одним потенциальным исключением - контрактная работа с американским правительством) поскольку более сильные методы доступны бесплатно. Исходные тексты DSS включены в библиотеку Crypto++.

• Криптосистема с открытым ключом ElGamal. Основана на проблеме дискретного алгоритма. См., например, Bruce Schneier: Applied Cryptography, John Wiley and Sons, 1994. Исходные тексты системы Elgamal включены в библиотеку Crypto++.

• LUC - это система с открытым ключом. Краткое описание смотри в luc-algorithm.txt. Вместо возведения в степень система использует функции Люка (Lucas). Изобретатель системы Питер Смит с тех пор реализовал четыре других алгоритма с использованием функций Люка: LUCDIF - метод обмена ключами наподобие Диффи-Хеллмана; LUCELG PK - эквивалент системы шифрования с открытым ключом El Gamal; LUCELG DS - эквивалент системы цифровых подписей El Gamal; и LUCDSA - эквивалент DSS. Компания LUC Encryption Technology Ltd (LUCENT) получила патенты на криптографическое использование функций Люка в США и Новой Зеладии.

  Исходный текст можно найти в ftp.funet.fi:/pub/crypt/cryptography/asymmetric/luc . Они также включены в библиотеку Crypto++.

Алгоритмы с симметричным ключом (симметричные шифры)

• DES был разработан в 1970-х. Он был принят как стандарт американским правительством, и кроме того, принят в некоторых других странах. Он широко используется, и особенно - в финансовой индустрии.

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

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

  Реализации DES могут быть найдены, например, в библиотеках libdes, alodes, SSLeay, Crypto++, descore, chalmers-des и в destoo.

• Blowfish - это алгоритм, разработанный Брюсом Шнейером. Он представляет собой блочный шифр с размером блока в 64 бита и переменной длиной ключа (до 448 бит). Он получил широкое распространение в ряде приложений. Неизвестны успешные атаки на него. (Замечание: Некоторые реализации алгоритма blowfish содержат серьезную ошибку.)

  Blowfish используется в популярных программах, включая Nautilus and PGPfone. Реализация Blowfish может быть найдена в библиотеке Crypto++.

• IDEA (International Data Encryption Algorithm) разработан в ETH, Цюрих, Швейцария. Использует 128-битный ключ и считается очень надежным. В настоящее время этот алгоритм является одним из лучших из известных алгоритмов. Он довольно новый, но уже работает несколько лет и ни одной успешной атаки на него пока не опубликовавно, несмотря на то что неоднократно предпринимались попытки его анализа.

  IDEA запатентован в США и большинстве европейских стран. Владельцем патента является Ascom-Tech. Использование шифра IDEA в некоммерческих целях бесплатно. Для получения коммерческой лицензии необходимо связаться с idea@ascom.ch.

  Свободно доступны несколько реализаций IDEA. Смотри, например, исходные тексты SSLeay, PGP и Ssh, idea86, Crypto++.

• RC4 является шифром, разработанным компанией RSA Data Security, Inc. Он был коммерческой тайной до тех пор пока кто-то не опубликовал в Usenet News исходнеые тексты алгоритма, который был объявлен эквивалентом RC4. Имеется весьма надежное свидетельство того, что опубликованный алгоритм действительно эквивалентен RC4. Алгоритм очень быстр. Степень его безопасности неизвестна, но вскрытие представляется делом нетривиальным. Благодаря его скорости, он может быть использован в некоторых приложениях. Кроме того, алгоритм работает с ключами произвольной длины. По своей сути RC4 представляет собой генератор псевдослучайных чисел, при этом выходные данные генератора используются для операции xor над потоком данных. Поэтому, чрезвычайно важно, чтобы один и тот же ключ RC4 не использовался для шифровки двух различных сообщений.

  Исходные тексты и информацию об RC4 можно найти здесь и во многих криптографических библитотеках, например в исходных текстах SSLeay, Crypto++ и Ssh.

  Американское правительство обычно разрешает к экспорту шифры RC4 с 40-битными ключами. Такие короткие ключи могут быть легко взломаны правительствами, преступниками и даже дилетантами.

  Интересно, что экспортный вариант SSL (Secure Socket Layer корпорации Netscape), где используется шифр RC4-40, был недавно вскрыт по крайней мере двумя независимыми группами. Процесс вскрытия занял порядка восьми дней; в большинстве крупных университетов (или компаний) такой объем вычислительных мощностей доступен любому студенту старших курсов по специальности computer science. Подробнее об инциденте смотри на кракерских страницах SSL Дамиена Долигеза (Damien Doligez).

• SAFER - это алгоритм, разработанный J. L. Massey (одним из авторов IDEA). Как заявляется, алгоритм способен производить надежную шифровку даже на 8-битных процессорах (при эффективной программной реализации). Имеется два варианта. Один - для работы с 64-битными ключами, и другой - для 128-битных ключей. Реализацию можно найти в ftp.funet.fi:/pub/crypt/cryptography/symmetric/safer.

  Анализ шифра SAFER-K64 был представлен на конференции Crypto'95 и опубликован в ее трудах.

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

  Примером шифра, основанного на хэш-функции, является MDC/SHA; исходные тексты можно найти, например, в библиотеке Crypto++ .

• Enigma - это шифр, который использовали немцы во Вторую Мировую Войну. Его тривиально можно вскрыть с помощью современного компьютера; смотри программу Crypt Breaker's Workbench. Этот шифр используется в программе UNIX crypt(1), которой, следовательно, не следует пользоваться.

• Vigenere является исторически важным способом шифровки. Он упоминается во многих учебниках. Его легко вскрыть. Необходимое программное обеспечение свободно доступно.

• Некотрорые другие классические шифры описаны в http://rschp2.anu.edu.au:8080/cipher.html. Такие шифры не следует использовать, поскольку они не являются надежными.

Эти и некоторые другие шифры доступны на ftp.funet.fi:/pub/crypt/cryptography/symmetric .

Моды блочной шифровки

Если один и тот же блок шифруется дважды одним и тем же числом, то в обоих случаях результат будет одинаков (такой метод шифровки называют Электронной Книгой Кодов, Electronic Code Book mode, или ECB). Эта информация может быть полезна для атакующего.

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

• Метод CFB: Блок шифрованного текста получается так: шифруется предыдущий шифрованный блок, результат затем используется для осуществления операции xor над нашим блоком текста.
• Метод CBC: Сначала делают операцию xor предыдущего шифрованного блока с нашим блоком текста; получившийся результат зашифровывается.

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

Дополнительную информацию о блочных методах шифровки можно найти в Bruce Schneier: Applied Cryptography, John Wiley & Sons, 1994.

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

• MD5 (Message Digest Algorithm 5) представляет собой надежный алгоритм хэширования, разработанный компанией RSA Data Security, Inc. Он может использоваться для хэширования строки байт произвольной длины в 128-битное значение. MD5 широко используется и считается достаточно надежным.

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

  MD5 можно получить на ftp.funet.fi:/pub/crypt/hash/mds/md5 . Также этот алгоритм включен в исходные тексты PGP, SSLeay, RSAREF, Crypto++ и Ssh. Описание MD5 можно найти в книге Bruce Schneier: Applied Cryptography, John Wiley & Sons, 1994.

• MD2, MD4: Эти алгоритмы являются более ранними версиями алгоритма хэширования от RSA Data Security. Известно, что они имеют слабые стороны и их не рекомендуется использовать. Исходный текст MD2 включен по крайней мере в SSLeay и RSAREF, которые описаны на странице программного обеспечения. Также их можно найти в архиве ftp.funet.fi:/pub/crypt/hash/mds .

• SHA (Secure Hash Algorithm) (также известен как SHS, Secure Hash Standard): хэширующий криптографический алгоритм, опубликованный американским правительством. Он выдает 160-битное хэш-значение по строке произвольной длины. Многие считают его очень хорошим. Он является довольно новым алгоритмом.

  SHA можно найти в архиве ftp.funet.fi:/pub/crypt/hash/sha, и он включен во многие криптографические библиотеки, такие как Crypto++.

• Tiger представляет собой новый хэширующий алгоритм, разработанный Anderson and Biham. Его можно получить с ftp.funet.fi:/pub/crypt/hash/tiger.

• Наиболее свежий алгоритм хэширования - это RIPEMD-160, который создан на смену MD4 и MD5. Он производит дайджест длиной в 20 байт, и, как объявлено, работает со скоростью в 40 Mb/s на 90 MHz Pentium. Его разработчики поместили его в public domain.

Генераторы случайных чисел

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

Примеры криптографических генераторов случайных чисел можно найти, например, в исходных текстах PGP, Noiz и Ssh.

Disclaimer: Любые мнения и выводы, представленные здесь являются субъективными и автор не может нести ответственность за их правильность.