Разница между асимметричными и симметричными методами шифрования? Совместное использование симметричных и асимметричных шифров.

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

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

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

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

Есть три состояния безопасности:

• скрытие информации от посторонних;
• предотвращение изменений;
• сохранение целостности информации;
• идентификация отправителя.

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

Бывают два вида шифрования: симметричный и асимметричный.

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

• отправитель шифрует данные;
• получатель расшифровывает.

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

Криптостойкость

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

Существует 2 основных типа криптостойкости системы шифрования.

1. Абсолютно стойкая система не может быть раскрыта, даже при наличии бесконечно больших вычислительных ресурсов. Характеризуется тем, что для каждого сообщения генерируется свой отдельный ключ. Его длина равна или больше длины сообщения.
2. Достаточно стойкие системы применяются в криптографической системе гражданского назначения. Такой алгоритм сложно расшифровать, но при наличии соответствующих ресурсов это становится возможным.

Сравнение криптостойкости некоторых систем шифрования

Максимальный размер ключа RSA - 4096 бит.

Он используется для шифрования и подписи. Криптостойкость можно описать как 2,7.1028 для ключа 1300 Бит. Схема применяется во многих стандартах, принцип шифрования RSA один из первых асимметричных алгоритмов.

Размер ключа схемы Эль-Гамаля равен RSA - 4096 Бит. Он используется и для шифрования, и для цифровой подписи. Криптостойкость этой системы не отличается от RSA при одинаковом размере ключа.

В методе DSA используется значительно меньшей ключ - 1024 бита. Применяется он исключительно для цифровой подписи.

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

Эти два вида шифрования отличаются количеством ключей и уровнем устойчивости к взлому.

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

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

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

Особенности симметричного шифрования

Симметричная система защита имеет следующие достоинства.

К недостаткам относится следующее:

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

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

Особенности асимметричного шифрования

Применение пары открытый-закрытый ключ можно использовать как:

• самостоятельное средство защиты информации;
• средство распределения ключей;
• средства аутентификации пользователей.

Имеет такие преимущества:

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

В таких алгоритмах сложно внести какие-либо изменения. Подобная система имеет длинные ключи. Если симметричный ключ имеет размер 128 Бит, то ключ RSA - 2304 Бит. Из-за этого страдает скорость расшифровывания - она в 2-3 раза медленнее. Для расшифровки требуются большие вычислительные ресурсы.

Существует очень много примеров симметричной и асимметричной систем шифрования.

Симметричное шифрование - как выглядит?

Пример симметричного шифрования и схема реализации ниже.

1. Есть два собеседника, которые планируют обменяться конфиденциальной информацией.
2. Первый собеседник генерирует ключ d, алгоритмы шифрования E и дешифрования D. Затем посылает эту информацию второму собеседнику.
3. Сообщение дешифруется ключом d.

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

Существуют классические методы.

1. Простая и двойная перестановка.
2. Магический квадрат.
3. Одиночная перестановка.

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

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

“Магический квадрат” - более сложная структура, которая представляет собой матрицу. В клетки вписываются натуральные числа таким образом, чтобы сумма чисел по каждому столбцу, строке, диагонали была одинаковой. Каждое число соответствует букве сообщения. Полученный текст выписывается в строку, сопоставляя числа и символы.

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

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

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

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

Существует такие основные методы асинхронного шифрования.

1. Шифр Эль-Гамаля.

RSA

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

Описывается так.

1. Выбирается два простых числа, например, 3 и 7.
2. Вычисляется модуль n - произведение двух чисел. Получается 21.
3. Вычисляется функция Эйлера φ=(p-1)×(q-1)=2×6=12 .
4. Вычисляется любое простое число e меньше φ и простое с φ. Доступные варианты: 5, 7, 11.

Пара чисел e, n (5, 21) - открытый ключ. Теперь вычисляются числа d и n закрытого ключа. Число d удовлетворяет условие (d×е) mod φ=1 и равняется 17. В итоге вторая пара чисел 17 и 21 - закрытый ключ. Шифрование выполняется следующим образом: сообщение возводится в степень e, берется остаток от деления на n, при этом результат должен быть меньше числа n. Получается 10 - это будут закодированные данные. Для раскодировки e возводится в степень d, вычисляется остаток от деления на n.

DSA

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

1. Выбор криптографической хэш-функции H(x).
2. Битность простого числа q должна равняться значению хэш-функции H(x).
3. Подбор такого простого числа p, чтобы p-1 делился без остатка на q.
4. Вычисление числа g = h (p-1)/q mod p . h должно быть произвольным числом в диапазоне от 1 до p-1.
5. Выбирается случайное число k от 0 до q.
6. Вычисляется r = (g k mod p) mod q .
7. Затем s = k-1(H(m) + xr)) mod q .
8. Если r=0 или s=0, выбирается другое число k.

Схема Эль-Гамаля

Шифрование по схеме Эль-Гамаля используется для цифровых подписей. Является продолжением алгоритма Диффи-Хеллмана.

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

Генерация ключей происходит следующим образом.

1. Выбирается случайное простое число p.
2. Число g должно быть первообразным корнем p.
3. Число x должно быть больше 1 и меньше p-1. Это будет закрытый ключ.
4. Затем вычисляется открытый ключ y по формуле g^x mod p .

При шифровании текста M выбирается системный ключ K. Он больше единицы и меньше p-1. Затем вычисляются числа a и b, которые являются шифротекстом, a = g^k mod p и b = y^k M mod p .

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

Поэтому ниже мы расскажем, что такое симметричное и асимметричное шифрование простыми словами.

Симметричное шифрование простыми словами

Особенностью симметричного шифрования является наличие одного пароля. По другому его еще именуют ключом.

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

Если посмотреть на вышеописанную ситуацию под другим углом, то мы видим, что в случае передачи пароля иному лицу, безопасность системы нарушается.

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

Необходимо отметить, что несмотря на вышеперечисленные нюансы, симметричное шифрование распространено довольно широко, что обусловлено двумя факторами:

• Простота понимания;
• Отсутствие большой технической нагрузки.

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

Ассимитричное шифрование, наоборот, предусматривает использование двух паролей – открытый (публичный ключ) и закрытый (приватный). Открытый, в свою очередь, распространяется между всеми заинтересованными лицами. Закрытый известен только тому, кто принимает информацию и серверу. Таким образом, в некоторой степени, мы наблюдаем равноценность двух ключей.

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

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

Хранить пароли также проще при асимметричном шифровании из-за того, что отсутствует необходимость передачи секретного ключа кому-либо. Его не нужно никому передавать.

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

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

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

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

Асимметричное шифрование позволяет устанавливать безопасное соединения без особых усилий пользователей. Симметричное шифрование, наоборот, требует от пользователя использования пароля для получения данных.

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

Генерировать пароли в симметричном алгоритме на много проще в отличие от ассиметричных алгоритмов.

Выводы

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

• Перевод

Как же все-таки работает HTTPS? Это вопрос, над которым я бился несколько дней в своем рабочем проекте.

Будучи Web-разработчиком, я понимал, что использование HTTPS для защиты пользовательских данных – это очень и очень хорошая идея, но у меня никогда не было кристального понимания, как HTTPS на самом деле устроен.

Как данные защищаются? Как клиент и сервер могут установить безопасное соединение, если кто-то уже прослушивает их канал? Что такое сертификат безопасности и почему я должен кому-то платить, чтобы получить его?

Трубопровод

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

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

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

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

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

Transport Layer Security (TLS)

TLS - наследник SSL - это такой протокол, наиболее часто применяемый для обеспечения безопасного HTTP соединения (так называемого HTTPS). TLS расположен на уровень ниже протокола HTTP в модели OSI . Объясняя на пальцах, это означает, что в процессе выполнения запроса сперва происходят все “вещи”, связанные с TLS-соединением и уже потом, все что связано с HTTP-соединением.

TLS – гибридная криптографическая система. Это означает, что она использует несколько криптографических подходов, которые мы и рассмотрим далее:

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

Криптосистема с открытым ключом

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

Это означает, что если кто-нибудь находится между клиентом и сервером и наблюдает за соединением – он все равно не сможет узнать ни закрытый ключ клиента, ни закрытый ключ сервера, ни секретный ключ сессии.

Как это возможно? Математика!

Алгоритм Ди́ффи - Хе́ллмана

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

Немного математики…

Пусть Алиса и Боб – две стороны, осуществляющие обмен ключами по DH-алгоритму. Сперва они договариваются о некотором основании root (обычно маленьком числе, таком как 2,3 или 5) и об очень большом простом числе prime (больше чем 300 цифр). Оба значения пересылаются в открытом виде по каналу связи, без угрозы компрометировать соединение.

Напомним, что и у Алисы, и у Боба есть собственные закрытые ключи (из более чем 100 цифр), которые никогда не передаются по каналам связи.

По каналу связи же передается смесь mixture , полученная из закрытых ключей, а также значений prime и root .

Таким образом:
Alice’s mixture = (root ^ Alice’s Secret) % prime
Bob’s mixture = (root ^ Bob’s Secret) % prime
где % - остаток от деления

Таким образом, Алиса создает свою смесь mixture на основе утвержденных значений констант (root и prime ), Боб делает то же самое. Как только они получили значения mixture друг друга, они производят дополнительные математические операции для получения закрытого ключа сессии. А именно:

Вычисления Алисы
(Bob’s mixture ^ Alice’s Secret) % prime

Вычисления Боба
(Alice’s mixture ^ Bob’s Secret) % prime

Результатом этих операций является одно и то же число, как для Алисы, так и для Боба, и это число и становится закрытым ключом на данную сессию. Обратите внимание, что ни одна из сторон не должна была пересылать свой закрытый ключ по каналу связи, и полученный секретный ключ так же не передавался по открытому соединению. Великолепно!

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

Обратите внимание как начальный цвет (желтый) в итоге превращается в один и тот же “смешанный” цвет и у Боба, и у Алисы. Единственное, что передается по открытому каналу связи так это наполовину смешанные цвета, на самом деле бессмысленные для любого прослушивающего канал связи.

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

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

Аутентификация

Что если я позвоню своему приятелю, мы осуществим DH-обмен ключами, но вдруг окажется, что мой звонок был перехвачен и на самом деле я общался с кем-то другим?! Я по прежнему смогу безопасно общаться с этим человеком – никто больше не сможет нас прослушать – но это будет совсем не тот, с кем я думаю, что общаюсь. Это не слишком безопасно!

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

Но, на самом деле, что это за сертификат, и как он предоставляет нам безопасность?

Сертификаты

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

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

Чтобы сертификату доверял любой веб-браузер, он должен быть подписан аккредитованным удостоверяющим центром (центром сертификации, Certificate Authority, CA). CA – это компании, выполняющие ручную проверку, того что лицо, пытающееся получить сертификат, удовлетворяет следующим двум условиям:

1. является реально существующим;
2. имеет доступ к домену, сертификат для которого оно пытается получить.

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

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

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

Прочие вещи которые нужно знать о сертификатах

Расширенная валидация

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

Обслуживание множества веб-сайтов на одном сервере

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

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

Хэш-функции

В рассмотренных в разделе 2.4 алгоритмах формирования ЭЦП длина подписи получается равной или даже большей, чем длина самого сообщения. Очевидно, что удостоверять подобным образом большой документ неудобно. Поэтому подписывается, как правило, не само сообщение, а его «дайджест» – значение фиксированной длины, зависящее от подписываемого сообщения. Для формирования дайджеста используется хэш-функция (от англ. «hash function») – односторонняя функция, преобразующая строку произвольной длины в строку фиксированной длины. В криптографии используются хэш-функции 2 классов:

Хэш-функции без ключа;

Хэш-функции с ключом.

Хэш-функции без ключа

Хэш-функции без ключа делятся на слабые и сильные. Слабой хэш-функцией H(x) ,удовлетворяющая следующим условиям:

1) аргумент может быть строкой бит произвольной длины;

2) значение функции H(x) должно быть строкой бит фиксированной длины;

3) значение H(x) легко вычислить;

4) для любого фиксированного аргумента x вычислительно невозможно найти другой x’ x , такой что H(x’)=H(x) .

Пара значений x’ x : H(x’)=H(x) называется коллизией хэш-функции.

Сильной хэш-функцией называется односторонняя функция H(x) ,удовлетворяющая условиям 1) – 3) и последнему условию в следую-щей формулировке:

5) вычислительно невозможно любую пару значений x’ x , таких

что H(x’)=H(x) .

Любая сильная хэш-функция соответствует и требованиям для слабой, обратное в общем случае неверно. Для иллюстрации различия в сложности поиска коллизий слабой и сильной хэш-функции рассмотрим атаку с использованием «парадокса дней рождения» 1 . Зафиксируем значение аргумента x , и будем перебирать случайным образом x’ x в поисках ситуации, когда H(x’)=H(x). Если предположить, что значения хэш-функции равномерно распределены, а число возможных значений H(x) равно N , то потребуется в среднем перебор N / 2вариантов.Если же мы захотим найти какую-либо коллизию вообще, то задача оказывается проще: с вероятностью 0,63 для определения нужной пары значений потребуется опробовать N вариантов.

Чтобы минимизировать стоимость создания криптографических хэш-функций, разработчики часто используют один из существующих алгоритмов шифрования. Пусть E(m,k) обозначает шифрование сообщения m на ключе k , а v 0 – стартовый вектор. Представим кэшируемое сообщение M в виде последовательности блоков m 1 , …, m t и будем их использовать в качестве раундовых ключей. Тогда H(m) вычисляется следующим образом:

Алгоритм SHA-1

Алгоритм SHA (Secure Hash Algorithm) разработан в США как часть стандарта SHS (Secure Hash Standard), опубликованного в 1993 году. Но в нем были обнаружены уязвимости, которые привели к необходимости модифицировать алгоритм. Через два года была опубликована новая версия – SHA-1, получившая на сегодняшний день широкое распространение.

Получая на входе сообщение произвольной длины менее 2 64 бит, SHA-1 формирует 160-битное выходное сообщение (дайджест). Вначале преобразуемое сообщение M дополняется до длины, кратной 512 битам. Заполнитель формируется следующим образом: в конец пре-образуемого сообщения добавляется 1, потом – столько нулей, сколь-ко необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, после чего добавляют 64-битное представление длины исходного сообщения. Например, если сообщение длиной 800 бит, то 801-й бит =1, потом добавляем нули до 960 бит, после чего – в оставшихся 64-разрядах записывается число «800», в итоге хэшируем 1024-битное сообщение. Общая схема преобразования представлена на Рисунок 2.18. Перед началом преобразований инициализируется пять 32-битных переменных:

A =0x67452301; B =0xEFCDAB89; C =0x98BADCFE; D =0x10325476; E =0xC3D2E1F0.

Эти значения присваиваются также переменным a 0 , b 0 , c 0 , d 0 , e 0 . Преобразование производится над блоком сообщения размером 512 бит в 80 раундов. В процессе преобразования используются следующие нелинейные функции f t:

f t (X,Y,Z)=(X Y) ((X) Z) для t =0…19;

f t (X,Y,Z)=X Y Z для t =20…39 и t =60…79;

f t (X,Y,Z)=(X Y) (X Z) (Y Z) для t =40…59.

Рисунок 2.18 - Схема раунда алгоритма SHA-1

В процессе преобразования используются четыре константы:

K t =0x5A827999 для t =0…19;

K t =0x6ED9EBA1 для t =20…39;

K t =0x8F1BBCDC для t =40…59;

K t =0xCA62C1D6 для t =60…79.

Обозначение «<<< X» – циклический сдвиг влево на X разрядов, «+» – сложение по модулю 2 32 .

После преобразования очередного 512-битного блока, полученные значения a ,b ,c ,d ,e складываются со значениями A ,B ,C ,D ,E соответственно, и начинается обработка следующего блока (или полученное значение в виде сцепления a ,b ,c ,d ,e подается на выход, если обработанный блок был последним).

Таким образом, на выходе получаем 160-битный дайджест исходного сообщения.

Хэш-функции с ключом

Хэш-функцией с ключом называется односторонняя функция H(k,x) со следующими свойствами:

Аргумент x функции H(k,x) может быть строкой бит произвольной длины;

Значение функции должно быть строкой бит фиксированной длины;

При любых данных k и x легко вычислить H(k,x) ;

Для любого x должно быть практически невозможно вычислить

H(k,x) ,не зная k ;

Должно быть практически невозможно определить k , даже при большом числе известных пар {x, H(k,x)} или вычислить по этой информации H(k,x’) для x’ x .

Часто такие функции также называются кодами аутентифика

ции сообщений (англ. «Message Authentication Code»,сокр.MAC).В

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

открытый ключ K: используется для шифрования информации, вычисляется из секретного ключа k;

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

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

Асимметричные системы называют еще двухключевыми криптографическими системами или криптосистемами с открытым ключом.

Обобщенная схема асимметричной криптосистемы шифрования

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

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

Процесс шифрования и передачи сообщения

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

1.Подготовительный этап.

Абонент В генерирует пару ключей: секретный ключ k B и открытый ключ К в . Открытый ключ К в посылается абоненту А и остальным абонентам (или делается доступным, например, на разделяемом ресурсе).

2.Использование - обмен информацией между абонентами А и В.

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

Односторонние функции

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

Функция F:X→Y называется односторонней, если выполняются следующие два условия:

существует эффективный алгоритм, вычисляющий F(x) для любого x ∈ X ;

не существует эффективного алгоритма инвертирования функции F , т.е. алгоритма, позволяющего определить значение x по значению F(x) .

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

Не любая односторонняя функция не может быть использована для шифрования. Действительно, если преобразовать открытый текст t с помощью односторонней функции: c = F(t) , то расшифровать полученный текст, то есть по c восстановить t , не сможет уже никто, в том числе и законный получатель. Для использования в криптографии необходимо, чтобы задача инвертирования шифрующего преобразования (т.е. вычисления t по F(t) ) была разрешима за приемлемое время, но сделать это мог только тот, кто знает секретный ключ. Такие функции называются односторонними функциями с секретом

Односторонняя функция с секретом - это функция F k : X → Y , зависящая от параметра k ∈ K (этот параметр называется секретом), для которой выполняются следующие условия:

при любом k ∈ K существует эффективный алгоритм, вычисляющий F k (x ) для любого x ∈ X ;

при неизвестном k не существует эффективного алгоритма инвертирования функции F k ;

при известном k существует эффективный алгоритм инвертирования функции F k .

Алгоритм RSA

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

Взаимно простыми числами называются такие числа, которые не имеют ни одного общего делителя, кроме 1.

Функция Эйлера  (p ) от натурального p есть количество чисел, меньших p и взаимно простых с n (число 1 взаимно просто с любым числом).

Если p - простое число, то  (p ) = p - 1.

Если p - простое, a - натуральное число, то  (p a ) = p a - p a -1 .

Если p и q взаимно простые, то  (pq ) =  (p )  (q )

Генерация ключей выполняется по следующему алгоритму:

1. Выбираются два больших простых числа p, q (на сегодняшний день обычно выбирают числа, содержащие от 200 до 400 знаков)

2. вычисляется их произведение n , которое не может быть разложено на множители за разумное время. Данное произведение называется модулем

3 . Вычисляется значение функции Эйлера

φ(n) = φ(pq ) = (p − 1)(q − 1).

4. Выбирается целое число e (1< e <  (n )) , взаимно простое со значением  (n ) . Обычно в качестве e берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537. Число e называется открытой экспонентой

5. Вычисляется число d , удовлетворяющее условию:

de 1(mod (n ))

или в другом виде:

de=1+k (n )

Число d называется секретной экспонентой

6. Пара P = (e , n ) публикуется в качестве открытого ключа системы RSA.

7. Пара S = (d , n ) называется секретным ключом RSA и держится в тайне.

1. Шифрование сообщения

Чтобы зашифровать данные по известному ключу P = (e,n) необходимо разбить шифруемый текст на боки, каждый из которых может быть представлен в виде числа M(i) = 0, 1, … , n-1. Далее текст шифруется как последовательность чисел M(i), преобразованных по следующей формуле:

C(i) = M(i)emod(n)

2. Расшифровка сообщения

Чтобы расшифровать сообщение используя секретный ключ P=(d,n) необходимо каждое число из последовательности в зашифрованном сообщении преобразовать по формуле:

M(i) = C(i)dmod(n)

В результате будет получено множество чисел M(i), которое представляет собой исходный текст.