Асимметричное шифрование

Асимметричное шифрование

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

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

Открытый ключ вычисляется из секретного: kl = f(k2). Асимметричные алгоритмы шифрования основаны на применении однонаправленных функций. Согласно определению функция y = f(x) является однонаправленной, если ее можно легко вычислить для всех возможных вариантов x, а для большинства возможных значений y достаточно сложно вычислить такое значение x, при котором y = f(x) .

Примером однонаправленной функции может служить умножение двух больших чисел: N = S х G. Само по себе, с точки зрения математики, такое умножение представляет собой простую операцию. Однако обратная операция (разложение N на два больших множителя), называемая также факторизацией, по современным временным оценкам представляет собой достаточно сложную математическую задачу.

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

Алгоритм Диффи—Хеллмана. В 1976 году Уитфилд Диффи (Whitfield Diffie) и Мартин Хеллман (Martin Hellman) разработали свою систему шифрования с открытым ключом. Система Диффи—Хеллмана разрабатывалась для решения проблемы распространения ключей при использовании систем шифрования с секретными ключами. Идея заключалась в том, чтобы применять безопасный метод согласования секретного ключа без передачи ключа каким-либо другим способом. Следовательно, необходимо было найти безопасный способ получения секретного ключа с помощью того же метода связи, для которого разрабатывалась защита. Суть алгоритма Диффи—Хеллмана заключается в следующем. Предположим, что двум точкам (S1 и S2) требуется установить между собой безопасное соединение, для которого необходимо согласовать ключ шифрования.

? S1 и S2 принимают к использованию два больших целых числа a и b, причем 1 < a < b.

? S1 выбирает случайное число i и вычисляет I = ai ? mod b. S1 передает I абоненту S2.

? S2 выбирает случайное число j и вычисляет J = aj ? mod b. S2 передает J абоненту S1 .

? S1 вычисляет k1 = Ji ? mod b.

? S2 вычисляет k2 = Ij ? mod b.

Имеем k1 = k2 = ai ? j х mod b, следовательно, k1 и k2 являются секретными ключами, предназначенными для использования при передаче других данных.

Даже если допустить, что злоумышленнику каким-то образом удастся прослушать передаваемый трафик, то ему будут известны a, b, I и J. Тем не менее остаются в секрете i и j. Уровень безопасности системы зависит от сложности нахождения i при известном I = ai ? mod b. Эта задача называется задачей дискретного логарифмирования и считается очень сложной (то есть с помощью современного вычислительного оборудования ее решить практически невозможно), если числа очень велики. Следовательно, a и b необходимо выбирать очень тщательно. Например, оба числа b и (b – 1)/2 должны быть простыми и иметь длину не менее 512 бит. Рекомендуемая длина чисел составляет 1024 бита.

Алгоритм RSA был разработан в 1978 году тремя соавторами и получил свое название по первым буквам фамилий разработчиков (Rivest, Shamir, Adleman). В основе стойкости алгоритма стоит сложность факторизации больших чисел и вычисления дискретных логарифмов. Основной параметр алгоритма RSA – модуль системы N, по которому проводятся все вычисления в системе, а N = R х S (R и S – секретные случайные простые большие числа, обычно одинаковой размерности).

Секретный ключ k2 выбирается случайным образом и должен соответствовать следующим условиям: 1 < k2 < F(N) и НОД (k2, F(N))= 1, где НОД – наибольший общий делитель. Иными словами, k1 должен быть взаимно простым со значением функции Эйлера F(N) , причем последнее равно количеству положительных целых чисел в диапазоне от 1 до N, взаимно простых с N, и вычисляется как F(N) = (R – 1) ? (S – 1) .

Открытый ключ kl вычисляется из соотношения (k2 х kl) = 1 ? mod F(N). Для этого используется обобщенный алгоритм Евклида (алгоритм вычисления наибольшего общего делителя). Зашифровка блока данных M по алгоритму RSA выполняется следующим образом: C = Mkl ? mod N. Поскольку в реальной криптосистеме с использованием RSA число k1 весьма велико (в настоящее время его размерность может доходить до 2048 бит), прямое вычисление Mk1 нереально. Для его получения применяется комбинация многократного возведения M в квадрат с перемножением результатов. Обращение данной функции при больших размерностях неосуществимо; иными словами, невозможно найти M по известным C, N и kl. Однако, имея секретный ключ k2, при помощи несложных преобразований можно вычислить M = Ck2 ?  mod N. Очевидно, что, помимо собственно секретного ключа, необходимо обеспечивать секретность параметров R и S. Если злоумышленник добудет их значения, то сможет вычислить и секретный ключ k2.

В настоящее время криптосистема RSA применяется в самых различных продуктах, на различных платформах и во многих отраслях. Достаточно вспомнить ее использование в операционных системах Microsoft, Apple, Sun и Novell, чтобы представить всю "грандиозность" RSA. В аппаратной составляющей алгоритм RSA широко используется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, в криптографическом оборудовании Zaxus (Racal). Ко всему прочему, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Интернет, в том числе S/MIME, SSL и S/WAN, а также используется во многих правительственных учреждениях, государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.

Алгоритм Эль-Гамаля. Эль-Гамаль (Taher Elgamal) разработал вариант системы Диффи—Хеллмана. Он усовершенствовал этот алгоритм и получил один алгоритм для шифрования и один для обеспечения аутентификации. Алгоритм Эль-Гамаля не был запатентован (в отличие от RSA) и таким образом стал более дешевой альтернативой, так как не требовалась уплата лицензионных взносов. Поскольку этот алгоритм базируется на системе Диффи—Хеллмана, то его стойкость обеспечивается сложностью решения все той же задачи дискретного логарифмирования.

Алгоритм цифровой подписи (Digital Signature Algorithm). Алгоритм DSA был разработан правительством США как стандартный алгоритм для цифровых подписей (см. разд. 2.3). Данный алгоритм базируется на системе Эль-Гамаля, но позволяет осуществлять только аутентификацию. Конфиденциальность этим алгоритмом не обеспечивается.

Шифрование с использованием эллиптических кривых. Эллиптические кривые были предложены для использования в системах шифрования в 1985 году. Системы шифрования с использованием эллиптических кривых (ECC) основываются на отличной от факторизации или дискретного логарифмирования математической задаче. Данная задача заключается в следующем: имея две точки A и B на эллиптической кривой, такие что A = kB, очень трудно определить целое число k. Несмотря на некоторую «экзотичность», использование ECC перед алгоритмом RSA или Диффи—Хеллмана в ряде случаев дает существенное преимущество. Самым большим из таких преимуществ является то, что ключи могут иметь существенно меньшую длину (по причине сложности задачи). И это без потери стойкости! Как результат, вычисления производятся быстрее с сохранением того же уровня безопасности. Так, безопасность, обеспечиваемая 160-битным ключом ECC, может быть приравнена к 1024-битному ключу RSA.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Симметричное шифрование

Из книги Защити свой компьютер на 100% от вирусов и хакеров автора Бойцев Олег Михайлович

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


Асимметричное мультипроцессирование

Из книги Основы AS/400 автора Солтис Фрэнк

Асимметричное мультипроцессирование Давайте, хотя бы кратко, затронем системы асимметричного мультипроцессирова-ния (ASMP). В системе ASMP части одной или даже разных ОС выполняются на выделенных процессорах. Структура задач AS/400 поддерживает и такую модель


3.8.6 Комбинированное шифрование

Из книги TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) автора Фейт Сидни М

3.8.6 Комбинированное шифрование Комбинированное шифрование реализуется следующим образом:? Выбирается случайный симметричный ключ.? По этому ключу шифруются данные.? Случайный ключ шифруется с помощью общедоступного ключа шифрования получателя и включается в


Шифрование данных

Из книги 500 лучших программ для Windows автора Уваров Сергей Сергеевич

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


2.26. Шифрование строк

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

2.26. Шифрование строк Иногда нежелательно, чтобы строки можно было легко распознать. Например, пароли не следует хранить в открытом виде, какими бы ограничительными ни были права доступа к файлу.В стандартном методе crypt применяется стандартная функция с тем же именем для


Подписание и шифрование.

Из книги PGP: Кодирование и шифрование информации с открытым ключом. автора Левин Максим

Подписание и шифрование. Для подписания текстового файла вашим секретным ключом и последующей его зашифровки открытым ключом адресата, наберите:pgp –es textfile her_userid [-u your_userid]Обратите внимание, что скобки [ ] просто обозначают необязательное поле, не вводите сами скобки.В


Глава 12 Шифрование

Из книги Delphi. Трюки и эффекты автора Чиртик Александр Анатольевич

Глава 12 Шифрование • Основы криптографии• Шифр простой подстановки• Транспозиция• Шифр Виженера и его варианты• Шифр с автоключом• ВзломПо той или иной причине часто бывает необходимо сообщить определенную информацию конкретному кругу людей так, чтобы она


7.4. Шифрование

Из книги Windows Vista. Для профессионалов автора Клименко Роман Александрович

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


Шифрование пароля

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен

Шифрование пароля Интерфейс gsec шифрует пароли, используя скромный метод, основанный на алгоритме хэширования DES (Data Encryption Standard, стандарт шифрования данных). По причине восьмисимвольного ограничения идентификация пользователя в Firebird на сегодняшний день не может


5.2. Шифрование

Из книги Linux глазами хакера автора Флёнов Михаил Евгеньевич

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


5.2.3. Шифрование файлов

Из книги IT-безопасность: стоит ли рисковать корпорацией? автора Маккарти Линда

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


Использовать шифрование!

Из книги Анонимность и безопасность в Интернете. От «чайника» к пользователю автора Колисниченко Денис Николаевич

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


3.1.3. Шифрование информации в I2P

Из книги автора

3.1.3. Шифрование информации в I2P Весь трафик в сети I2P, в отличие от Tor, шифруется от отправителя к получателю. В общей сложности используются четыре уровня шифрования (сквозное, "чесночное", туннельное и шифрование транспортного уровня). Перед шифрованием I2P добавляет в


10.4. Шифрование в Windows 7

Из книги автора

10.4. Шифрование в Windows 7 Самые дорогие выпуски Windows 7: Профессиональная (Professional), Корпоративная (Enterprise) и Максимальная (Ultimate) – поддерживают функцию шифрования файлов и каталогов (система EFS). Зашифрованные файлы нельзя просмотреть на другом компьютере – в случае, если,