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


Содержание

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

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

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

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

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

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

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

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

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

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

Сначала рассмотрим алгоритмы, обладающие обеими характеристиками, а затем перейдем к алгоритмам открытого ключа, которые не обладают вторым свойством.

При описании симметричного шифрования и шифрования с открытым ключом будем использовать следующую терминологию. Ключ, используемый в симметричном шифровании, будем называть секретным ключом. Два ключа, используемые при шифровании с открытым ключом, будем называть открытым ключом (Key Public – KU) и закрытым ключом (Key Private – KR). Закрытый ключ держится в секрете, но называть его будем закрытым ключом, а не секретным, чтобы избежать путаницы с ключом, используемым в симметричном шифровании. Закрытый ключ будем обозначать KR , открытый ключ — KU .

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

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

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

  1. Вычислительно легко создавать пару (открытый ключ KU , закрытый ключ KR ).
  2. Вычислительно легко, имея открытый ключ и незашифрованное сообщение М , создать соответствующее зашифрованное сообщение:

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

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

Y = f (X) – вычислительно легко

X = f -1 (Y) – вычислительно трудно

В данном случае термин «вычислительно легко» означает полиномиальную сложность от длины входа. Таким образом, если алгоритму на вход подается значение длиной n битов, то время вычисления функции пропорционально n a , где а – фиксированная константа. Таким образом, говорят, что алгоритм принадлежит классу полиномиальных алгоритмов Р . Термин «вычислительно трудно» означает более сложное понятие. В общем случае будем считать, что проблему решить невозможно, если усилия для ее решения больше полиномиального времени от величины входа. Например, если длина входа n битов, и время вычисления функции пропорционально 2 n , то это считается вычислительно невозможной задачей. К сожалению, тяжело определить, проявляет ли конкретный алгоритм такую сложность. Более того, традиционные представления о вычислительной сложности фокусируются на поведении алгоритмов в худшем случае или в среднем случае. Это неприемлемо для криптографии, где требуется невозможность инвертировать функцию для всех или почти всех значений входов.

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

Y = fk (X) — легко, если k и Х известны

X = fk-1 (Y) — легко, если k и Y известны

Х = fk-1 (Y) — трудно, если Y известно, но k неизвестно

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

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

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

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

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

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

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

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

Сначала рассмотрим алгоритмы, обладающие обеими характеристиками, а затем перейдем к алгоритмам открытого ключа, которые не обладают вторым свойством.

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

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

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

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

1. Вычислительно легко создавать пару (открытый ключ KU , закрытый ключ KR).

2. Вычислительно легко, имея открытый ключ и незашифрованное сообщение М, создать соответствующее зашифрованное сообщение: С = ЕKU[М]

3. Вычислительно легко дешифровать сообщение, используя закрытый ключ: М = DKR[C] = DKR[EKU[M]]

4. Вычислительно невозможно, зная открытый ключ KU, определить закрытый ключ KR.

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

6. Шифрующие и дешифрующие функции могут применяться в любом порядке:

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

Y = f(X) — легко
X = f -1 (Y) — трудно

Обычно «легко» означает, что проблема может быть решена за полиномиальное время от длины входа. Таким образом, если длина входа имеет n битов, то время вычисления функции пропорционально n a , где а — фиксированная константа. Таким образом, говорят, что алгоритм принадлежит классу полиномиальных алгоритмов Р. Термин «трудно» означает более сложное понятие. В общем случае будем считать, что проблему решить невозможно, если усилия для ее решения больше полиномиального времени от величины входа. Например, если длина входа n битов, и время вычисления функции пропорционально 2 n , то это считается вычислительно невозможной задачей. К сожалению, тяжело определить, проявляет ли конкретный алгоритм такую сложность. Более того, традиционные представления о вычислительной сложности фокусируются на худшем случае или на среднем случае сложности алгоритма. Это неприемлемо для криптографии, где требуется невозможность инвертировать функцию для всех или почти всех значений входов.

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

Y = fk(X) — легко, если k и Х известны
X = fk -1 (Y) — легко, если k и Y известны
Х = fk -1 (Y) — трудно, если Y известно, но k неизвестно

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

Не нашли то, что искали? Воспользуйтесь поиском:

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

Алгоритмы асимметричного шифрования используют два ключа: k1 — ключ зашифрования, или открытый, и k2 — ключ расшифрования, или секретный. Открытый ключ вычисляется из секретного: k1 = f(k2).

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

Схема обмена информацией такова:

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

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

Примером однонаправленной функции может служить умножение двух больших чисел: N = P*Q. Само по себе такое умножение — простая операция. Однако обратная функция (разложение N на два больших множителя), называемая факторизацией, по современным временным оценкам представляет собой достаточно сложную математическую задачу. Например, разложение на множители N размерностью 664 бит при P ? Q потребует выполнения примерно 1023 операций, а для обратного вычисления х для модульной экспоненты y = ax mod p при известных a, p и y (при такой же размерности a и p) нужно выполнить примерно 1026 операций. Последний из приведенных примеров носит название — «Проблема дискретного логарифма» (DLP — Discrete Logarithm Problem), и такого рода функции часто используются в алгоритмах асимметричного шифрования, а также в алгоритмах, используемых для создания электронной цифровой подписи. [18]

Еще один важный класс функций, используемых в асимметричном шифровании, — однонаправленные функции с потайным ходом. Их определение гласит, что функция является однонаправленной с потайным ходом, если она является однонаправленной и существует возможность эффективного вычисления обратной функции x = f-1(y), т. е. если известен «потайной ход» (некое секретное число, в применении к алгоритмам асимметричного шифрования — значение секретного ключа).

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

Все асимметричные криптосистемы являются объектом атак путем прямого перебора ключей, и поэтому в них должны использоваться гораздо более длинные ключи, чем те, которые используются в симметричных криптосистемах, для обеспечения эквивалентного уровня защиты. Это сразу же сказывается на вычислительных ресурсах, требуемых для шифрования, хотя алгоритмы шифрования на эллиптических кривых могут смягчить эту проблему. Брюс Шнейер в книге «Прикладная криптография: протоколы, алгоритмы и исходный текст на C» приводит следующие данные об эквивалентных длинах ключей (таблица 8).

Симметричное и асимметричное шифрование для новичков

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

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

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

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

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

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

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

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

Такие алгоритмы шифрования позволяют свободно распространять пароль (ключ) по сети, так как без второго ключа невозможно получить исходное сообщение. На этом принципе основан протокол SSL, который позволяет легко установить безопасное соединение с пользователями в силу того, что закрытый ключ (пароль) хранится только на стороне сервера. Если замечали, то периодически в браузере появляется сообщение «небезопасное соединение», когда вы открываете сайт с префиксом https. Это означает, что вполне возможно, что закрытый ключ уже давно вскрыт, еще говорят скомпрометирован, и известен злоумышленникам. Поэтому такое безопасное соединение может и не быть безопасным.

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

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

Важные моменты о симметричном и асимметричном шифровании

Самое главное отличие симметричного и асимметричного шифрования заключается в их подходе. Поэтому когда вы слышите или читаете статью про их сравнение вида «этот алгоритм лучше» без упоминания конкретики (определенных условий и задач), то можете смело начинать заниматься другими делами, так как это весьма бесполезное занятие аналогичное спору «Что лучше? Танк или пароход?». Без конкретики, ни то и ни другое. Тем не менее, есть важные моменты, о которых стоит знать:

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

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

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

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

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

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

7. Наличие шифрования не является гарантом безопасности. Его всегда необходимо рассматривать в купе с другими подходами.

Послесловие

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

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

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


9. ШИФРОВАНИЕ С ОТКРЫТЫМ КЛЮЧОМ

9.1. Основы шифрования

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

Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 г. Находясь под влиянием работы Ральфа Меркла (Ralph Merkle) о распространении открытого ключа, они предложили метод получения секретных ключей для симметричного шифрования, используя открытый канал. В 2002 г. Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркла», признавая вклад Меркла в изобретение криптографии с открытым ключом [17].

Хотя работа Диффи-Хеллмана создала большой теоретический задел для открытой криптографии, первой реальной криптосистемой с открытым ключом считают алгоритм RSA (названный по имени авторов — Рон Ривест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman)).

Справедливости ради следует отметить, что в декабре 1997 г. была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал систему, аналогичную RSA, в 1973 г., а несколькими месяцами позже в 1974 г. Малькольм Вильямсон изобрел математический алгоритм, аналогичный алгоритму Диффи – Хеллмана — Меркла.

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

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

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

Алгоритмы шифрования с открытым ключом используют так называемые необратимые или односторонние функции. Эти функции обладают следующим свойством: при заданном значении аргумента х относительно просто вычислить значение функции f(x), однако, если известно значение функции y = f(x), то нет простого пути для вычисления значения аргумента x. Например, функция SIN. Зная x, легко найти значение SIN(x) (например, x = π, тогда SIN(π) = 0). Однако, если SIN(x) = 0, однозначно определить х нельзя, т.к. в этом случае х может быть любым числом, определяемым по формуле i * π, где i – целое число.

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

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

1. Преобразование исходного текста должно быть условно необратимым и исключать его восстановление на основе открытого ключа.

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

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

2. Вычисление дискретного логарифма или дискретное возведение в степень (алгоритм Диффи-Хелмана-Меркла, схема Эль-Гамаля).

4. Вычисление корней алгебраических уравнений.

5. Использование конечных автоматов (автор Тао Ренжи).

6. Использование кодовых конструкций.

9.2. Алгоритм RSA

Стойкость RSA основывается на большой вычислительной сложности известных алгоритмов разложения числа на простые сомножители (делители). Например, легко найти произведение двух простых чисел 7 и 13 даже в уме – 91. Попробуйте в уме найти два простых числа, произведение которых равно 323 (числа 17 и 19). Конечно, для современной вычислительной техники найти два простых числа, произведение которых равно 323, не проблема. Поэтому для надежного шифрования алгоритмом RSA, как правило, выбираются простые числа, количество двоичных разрядов которых равно нескольким сотням.

[44] В августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет». После объяснения принципа системы шифрования с открытым ключом он показал само зашифрованное сообщение и открытый ключ N, используемый в этом шифре:

N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541.

Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число N на простые множители р и q. Более того, Гарднер назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра — Рону Ривесту, Ади Шамиру и Леонарду Адлеману из Лаборатории информации Массачусетского технологического института.

Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более чем 600 человек. Ключами оказались р = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533 и q = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577, а зашифрованная фраза звучала так: «Волшебные слова — это брезгливый ягнятник».

Авторы RSA поддерживали идею её активного распространения. В свою очередь, Агентство национальной безопасности (США), опасаясь использования этого алгоритма в негосударственных структурах, на протяжении нескольких лет безуспешно требовало прекращения распространения системы. Ситуация порой доходила до абсурда. Например, когда программист Адам Бек (Adam Back) описал на языке Perl алгоритм RSA, состоящий из пяти строк, правительство США запретило распространение этой программы за пределами страны. Люди, недовольные подобным ограничением, в знак протеста напечатали текст этой программы на своих футболках [17].

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

Таблица 9.1. Процедура создания ключей

№ п/п Описание операции Пример
1 Выбираются два простых числа 1 p и q. p=7, q=13
2 Вычисляется произведение n = p * q. n=91
3 Вычисляется функция Эйлера 2 φ(n). φ(n) = (7-1)(13-1) = 91-7-13+1 = 72
4 Выбирается открытый ключ e, как произвольное число (0 3 с результатом функции Эйлера (e ⊥ φ(n)). e=5
5 Вычисляется закрытый ключ d, как обратное число 4 к e по модулю φ(n), из соотношения (d*e) mod φ(n) = 1. (d*5) mod 72 = 1, d = 29
6 Публикуются открытый ключ (e, n) в специальном хранилище, где исключается возможность его подмены (общедоступном сертифицированном справочнике).

1) Простое число — натуральное число, большее единицы и не имеющее других натуральных делителей, кроме самого себя и единицы.

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

Таблица 9.2. Способы расчета функции Эйлера

Расчетный случай Формула Пример
(число / расчетная формула /
список взаимно простых чисел)
n
простое число
φ(n) = n — 1 n = 7
φ(7) = 7 – 1 = 6
n = p q
произведение двух простых чисел
φ(n) = φ(p) φ(q) =
= (p — 1) (q — 1) = n – p – q + 1
(за исключением случая p = q = 2)
n = 15 = 3 * 5
φ(15) = φ(3) φ(5) = (3 — 1) (5 — 1) = 15 — 3 — 5 + 1 = 8
n = p q
простое число в степени
φ(n) = p q – p q-1 n = 9 = 3 2
φ(9) = 3 2 — 3 2-1 = 9 — 3 = 6
n = p1 q1 p2 q1 … pk qk
разложение числа согласно
основной теоремы арифметики
(общий случай)
n = 84 = 2 2 3 1 7 1

3) Взаимно простые числа – числа, не имеющие общих делителей, кроме 1, т.е. наибольший общий делитель которых равен 1.

4) Обратными числами по модулю m называются такие числа n и n -1 , для которых справедливо выражение (n * n -1 ) mod m = 1. Для вычисления обратных чисел по модулю обычно используется расширенный алгоритм Евклида. В безмодульной математике обратное число n -1 (обратное значение, обратная величина) — число, на которое надо умножить данное число n, чтобы получить единицу (n * n -1 = 1). Пара чисел, произведение которых равно единице, называются взаимно обратными. Например: 5 и 1/5, -6/7 и -7/6.

Процедуры шифрования и дешифрования выполняются по следующим формулам

C = Т e mod n, (9.1)

Т = C d mod n. (9.2)

где Т, C — числовые эквиваленты символов открытого и шифрованного сообщения.

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

Таблица 9.3. Пример шифрования по алгоритму RSA

Открытое сообщение, Т Символ А Б Р А М О В
Код 1 2 18 1 14 16 3
Шифрограмма, С = Т 5 mod 91 1 32 44 1 14 74 61
Открытое сообщение, Т = С 29 mod 91 1 2 18 1 14 16 3

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

[44] Алгоритм RSA требует много машинного времени и очень мощных процессоров. До 1980-х гг. только правительства, армия и крупные предприятия имели достаточно мощные компьютеры для работы с RSA. В результате у них была фактически монополия на эффективное шифрование. Летом 1991 г. Филипп Циммерман, американский физик и борец за сохранение конфиденциальности, предложил бесплатную систему шифрования PGP (англ. Pretty Good Privacy — «достаточно хорошая степень конфиденциальности»), алгоритм которой мог работать на домашних компьютерах. PGP использует классическое симметричное шифрование, что и обеспечивает ей большую скорость на домашних компьютерах, но она шифрует ключи по асимметричному алгоритму RSA.

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

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

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

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

PGP дает людям возможность самим защищать свою конфиденциальность. Сегодня существует растущая социальная потребность в этом. Вот почему я написал PGP.

В заключении следует отметить стойкость данного алгоритма. В 2003 г. Ади Шамир и Эран Тромер разработали схему устройства TWIRL, которое при стоимости $ 10 000 может дешифровать 512-битный ключ за 10 минут, а при стоимости $ 10 000 000 – 1024-битный ключ меньше, чем за год. В настоящее время Лаборатория RSA рекомендует использовать ключи (параметр n) размером 2048 битов.

9.3. Алгоритм на основе задачи об укладке ранца

В 1978 г. Меркл и Хеллман предложили использовать задачу об укладке ранца (рюкзака) для асимметричного шифрования [8]. Она относится к классу NP-полных задач и формулируется следующим образом. Дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений M1, M2, . Мn и суммарное значение S; требуется вычислить значения bi такие что

где n – количество предметов;
bi — бинарный множитель. Значение bi = 1 означает, что предмет i кладут в рюкзак, bi = 0 — не кладут.

Например, веса предметов имеют значения 1, 5, 6, 11, 14, 20, 32 и 43. При этом можно упаковать рюкзак так, чтобы его вес стал равен 22, использовав предметы весом 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его вес стал равен 24.

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

Таблица 9.4. Пример шифрования на основе задачи об укладке ранца

Открытый текст 1 1 1 1 1 1 1 1
Рюкзак (ключ) 1 5 6 11 14 20 32 43 1 5 6 11 14 20 32 43 1 5 6 11 14 20 32 43
Шифрограмма 32 (1+5+6+20) 73 (5+11+14+43)

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

В качестве закрытого ключа (легкого для укладки ранца) используется сверхвозрастающая последовательность. Сверхвозрастающей называется последовательность, в которой каждый последующий член больше суммы всех предыдущих. Например, последовательность <2, 3, 6, 13, 27, 52, 105, 210>является сверхвозрастающей, а <1, 3, 4, 9, 15, 25, 48, 76>— нет.

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

Например, пусть полный вес рюкзака равен 270, а последовательность весов предметов равна <2, 3, 6, 13, 27, 52, 105, 210>. Самый большой вес – 210. Он меньше 270, поэтому предмет весом 210 кладут в рюкзак. Вычитают 210 из 270 и получают 60. Следующий наибольший вес последовательности равен 105. Он больше 60, поэтому предмет весом 105 в рюкзак не кладут. Следующий самый тяжелый предмет имеет вес 52. Он меньше 60, поэтому предмет весом 52 также кладут в рюкзак. Аналогично проходят процедуру укладки в рюкзак предметы весом 6 и 2. В результате полный вес уменьшится до 0. Если бы этот рюкзак был бы использован для дешифрования, то открытый текст, полученный из значения шифртекста 270, был бы равен 10100101.

Открытый ключ представляет собой не сверхвозрастающую (нормальную) последовательность. Он формируется на основе закрытого ключа и, как принято считать, не позволяет легко решить задачу об укладке ранца. Для его получения все значения закрытого ключа умножаются на число n по модулю m. Значение модуля m должно быть больше суммы всех чисел последовательности, например, 420 (2+3+6+13+27+52+105+210=418). Множитель n должен быть взаимно простым числом с модулем m, например, 31. Результат построения нормальной последовательности (открытого ключа) представлен в следующей таблице.

Таблица 9.5. Пример получения открытого ключа

Закрытый ключ, ki 2 3 6 13 27 52 105 210
Открытый ключ,
(ki*n) mod m = (ki*31) mod 420
62 93 186 403 417 352 315 210

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

В качестве примера возьмем открытое сообщение «АБРАМОВ», символы которого представим в бинарном виде в соответствии с таблицей кодов символов Windows 1251. Результат шифрования с помощью открытого ключа <62, 93, 186, 403, 417, 352, 315, 210>представлен в следующей таблице.

Таблица 9.6. Пример шифрования

Открытое сообщение Сумма весов Шифрограмма
(рюкзак), ci
Символ Bin-код
А 1100 0000 62+93 155
Б 1100 0001 62+93+210 365
Р 1101 0000 62+93+403 558
А 1100 0000 62+93 155
М 1100 1100 62+93+417+352 924
О 1100 1110 62+93+417+352+315 1239
В 1100 0010 62+93+315 470

Для расшифрования сообщения получатель должен сначала определить обратное число n -1 , такое что (n * n -1 ) mod m = 1. После определения обратного числа каждое значение шифрограммы умножается на n -1 по модулю m и с помощью закрытого ключа определяются биты открытого текста.

В нашем примере сверхвозрастающая последовательность равна <2, 3, 6, 13, 27, 52, 105, 210>, m = 420, n = 31. Значение n -1 равно 271 (31*271 mod 420 = 1).

Таблица 9.7. Пример расшифрования

Шифрограмма
(рюкзак), ci
(ci*n -1 ) mod m =
(ci*271) mod 420
Сумма весов Открытое сообщение
Символ Bin-код
155 5 2+3 1100 0000 А
365 215 2+3+210 1100 0001 Б
558 18 2+3+13 1101 0000 Р
155 5 2+3 1100 0000 А
924 84 2+3+27+52 1100 1100 М
1239 189 2+3+27+52+105 1100 1110 О
470 110 2+3+105 1100 0010 В

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

9.4. Вероятностное шифрование

Вероятностное шифрование является разновидностью криптосистем с открытым ключом (авторы — Шафи Гольдвассер (Shafi Goldwasser) и Сильвио Микали (Silvio Micali)). Данный вид шифрования относят к допускающим неоднозначное вскрытие. Основной целью вероятностного шифрования является устранение утечки информации в криптографии с открытым ключом. Поскольку криптоаналитик всегда может зашифровать случайные сообщения открытым ключом, он может получить некоторую информацию. При условии, что у него есть шифртекст С (С = Еk1(T)) и он пытается получить открытый текст T, он может выбрать случайное сообщение T’ и зашифровать: С’ = Еk1(T’). Если С’ = С, то он угадал правильный открытый текст. В противном случае он делает следующую попытку.

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

В результате, даже если у криптоаналитика имеется шифртекст Ci и он угадает T, то в результате операции шифрования получиться Сj = Еk1(T). Вероятность того, что Ci = Сj крайне низка. Таким образом, криптоаналитик даже не узнает, была ли правильной его догадка относительно T или нет.

Ниже рассматриваются два алгоритма вероятностного шифрования:

9.5. Алгоритм шифрования Эль-Гамаля

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

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

g x mod p = y. (9.6)

Требуется по известным g, y и p найти целое неотрицательное число x (дискретный логарифм).

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

Таблица 9.8. Процедура создания ключей

№ п/п Описание операции Пример
1 Выбирается простое число p. p = 37
2 Выбирается число g, являющееся первообразным корнем по модулю p и меньшее р. g = 2
3 Выбираются произвольное число x, меньшее p. x = 5
4 Вычисляется y = g x mod p y = 2 5 mod 37 = 32 mod 37 = 32
5 Открытый ключ — y, g и p. Причем g и p можно сделать общими для группы пользователей.
Закрытый ключ — x.

Примечание. Первообразный (примитивный) корень по модулю p – наименьшее положительное число g такое, что

g i mod p ≠ 1, для 1 ≤ i 36 mod 37 = 1;
2 1 mod 37 = 2 (≠ 1);
2 2 mod 37 = 4 (≠ 1);
2 3 mod 37 = 8 (≠ 1);
2 4 mod 37 = 16 (≠ 1);
. ;
2 34 mod 37 = 28 (≠ 1);
2 35 mod 37 = 19 (≠ 1).

Для шифрования каждого отдельного блока исходного сообщения должно выбираться случайное число k (1 k mod p, (9.7)


b = (y k Т) mod p, (9.8)

где Т – исходное сообщение;
(a, b) – зашифрованное сообщение.

Дешифрование сообщения выполняется по следующей формуле

T = (b (a x ) -1 ) mod p (9.9)

T = (b a p-1-x ) mod p, (9.10)

где (a x ) -1 – обратное значение числа a x по модулю p.

Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k = 7 приведен в таблице, хотя для шифрования каждого блока (в нашем случае буквы) исходного сообщения надо использовать свое случайное число k.

Первая часть шифрованного сообщения – a = 2 7 mod 37 = 17.

a x = 17 5 = 1419857, (a x ) -1 = 2 (1419857 * 2 mod 37 = 1) или a p-1-x = 17 37-1-5 ≈ 1.3928892 * 10 38 .

Таблица 9.9. Пример шифрования по алгоритму Эль-Гамаля (при k = const)

Открытое сообщение, Т Символ А Б Р А М О В
Код 1 2 18 1 14 16 3
Шифрование Случайное число k 7 7 7 7 7 7 7
Первая часть шифрограммы, a = 2 k mod 37 17 17 17 17 17 17 17
Вторая часть шифрограммы, b = (32 a * T) mod 37 19 1 9 19 7 8 20
Расшифрование Обратное значение числа a x по модулю p, (a x ) -1 2 2 2 2 2 2 2
Открытое сообщение, T = (b * (a x ) -1 ) mod 37 1 2 18 1 14 16 3

Ввиду того, что число k является произвольным, то такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, т.к. у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение Т и ключ не определяют шифртекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений Т и Т’. Если использовать одинаковые k, то для соответствующих шифртекстов (a, b) и (a’, b’) выполняется соотношение b (b’) -1 = Т (Т’) -1 (mod p). Из этого выражения можно легко вычислить Т, если известно Т’.

Пример. Предположим злоумышленник перехватил зашифрованное сообщение С = ((a1, b1), (a2, b2), …, (an, bn)), для которого использовалось одно и тоже случайное число k. Он знает один из блоков Ti = Ek1(Ci) или при известном открытом ключе (y, g, p) ему удалось подобрать k’, которое совпало с используемым при шифровании k. Например по второму варианту, для шифрования символа Х (Т’ = 22) злоумышленник использовал k’ = 7 (равное k). Тогда, b(X) = b’ = (32 7 * 22) mod 37 = 11, (b’) -1 = 27, (Т’) -1 = 32. Расшифрование перехваченного сообщения приведено в следующей таблице.

Таблица 9.10. Пример расшифрования перехваченного сообщения

Вторая часть перехваченной шифрограммы, b 19 1 9 19 7 8 20
L = (b * (b’) -1 ) mod p = (b * 27) mod 37 32 27 21 32 4 31 22
Вскрытое
открытое
сообщение,
Т
Код, определяемый по уравнению
(T * (T’) -1 ) mod p = L
(Т * 32) mod 37 = L
1 2 18 1 14 16 3
Символ А Б Р А М О В

9.6. Алгоритм на основе эллиптических кривых

Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем (Neal Koblitz) и Виктором Миллером (Victor Miller) в 1985 г. [8, 17]. При использовании алгоритмов на эллиптических кривых полагается, что не существует быстрых алгоритмов для решения задачи дискретного логарифмирования в группах их точек. В настоящий момент известны лишь экспоненциальные алгоритмы вычисления обратных функций для эллиптических кривых. По сравнению с субэкспоненциальными алгоритмами разложения числа на простые сомножители (см. криптосистему RSA), это позволяет при одинаковом уровне стойкости уменьшить размерность ключа в несколько раз, а, следовательно, упростить программную и аппаратную реализацию криптосистем.

Эллиптической кривой E называется множество точек (x, y), удовлетворяющих однородному уравнению Вейерштрасса:

где ai — коэффициенты уравнения.

а) y 2 = x 3 – x б) y 2 = x 3 – 3x + 2 в) y 2 = x 3 – x + 1

Рис.9.1. Примеры эллиптических кривых

В криптографии эллиптические кривые рассматриваются над двумя типами конечных полей: простыми полями нечётной характеристики ( ℤ n, где n > 3 — простое число) и полями характеристики 2 (GF(2 m )).

Эллиптические кривые над полями нечётной характеристики ℤ n можно привести к виду, называемому эллиптической кривой в короткой форме Вейерштрасса:

y 2 = x 3 + Ax + B (mod n), (9.12)

где A, B ℤ n — коэффициенты эллиптической кривой, удовлетворяющие 4 A 3 + 27 B 2 ≠ 0 (mod n).

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

x 3 + Ax + B = 0. (9.13)

Это можно сделать с помощью известных формул Кардано. Дискриминант этого уравнения

Если ∆ > 0, то уравнение имеет три различных действительных корня (см. рис. 9.1а – x1, x2 и x3). Если ∆ = 0, то уравнение имеет три действительных корня, по крайней мере, два из которых равны (см. рис. 9.1б – x1 и x2). Если ∆ ℤ n у каждого ненулевого элемента есть либо два квадратных корня, либо нет ни одного, поэтому точки эллиптической кривой разбиваются на пары вида P = (x, y) и -P = (x, -y). Например, эллиптическая кривая y 2 = x 3 + 3x + 2 при x = 1 и n = 5 имеет две точки в качестве решения: P = (1, 1) и -P = (1, -1), т.к. 1 2 ≡ 1 3 + 3 * 1 + 2 (mod 5) и (-1) 2 ≡ 1 3 + 3 * 1 + 2 (mod 5).

Введем две операции, которые можно выполнять над точками кривой.

а) y 2 = x 3 – x б) y 2 = x 3 – x + 1

Рис.9.2. Сложение точек

В формулах 9.15 и 9.16 λ — угловой коэффициент прямой, проходящей через точки P1 и P2. Если P1 = P2, то λ равен значению производной в точке P1.

а) y 2 = x 3 – x б) y 2 = x 3 – x + 1

Рис.9.3. Удвоение точки

А) вариант 1 – выполнить сложение точки P k раз

B) вариант 2 – с использование двоичного представления числа k = (bL, …, b2, b1) и операции удвоения точки. Например, k = 11010 = 11011102, тогда Pk = 64P + 32P + 8P + 4P + 2P.

Алгоритм, вычисления Pk может выглядеть следующим образом.

3. Цикл. Для i := 1 до L

то Если Pk = null

3.2. Q = 2 * Q // ≈ Q = Q + Q

Для k = 110 вместо 109 сложений будет 1 присваивание, 4 сложения и 6 удвоений (сложений).

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

Таблица 9.11. Процедура создания ключей

№ п/п Описание операции Пример
1 Выбирается модуль эллиптической кривой — простое число n (n > 2 255 — ГОСТ). n = 41
2 Выбираются коэффициенты эллиптической кривой A и B.
Должно соблюдаться условие (4 A 3 + 27 B 2 ) mod n ≠ 0, в противном случае меняются параметры эллиптической кривой n, A или B.
A = 3, B = 7

(4 * 3 3 + 27 * 7 2 ) mod 41 = 37 3 Определяется точка эллиптической кривой P(xp, yp) и порядок циклической подгруппы группы точек эллиптической кривой q *) .
Принимается произвольное xp (0 t mod q ≠ 1, для всех целых t = 1, 2, …, T, где T ≤ 31;
— 2 254 256 (ГОСТ)
в противном случае меняются либо параметры эллиптической кривой n, A или B либо выбирается другая точка P. xp = 7 ((7 3 +3*7+7) mod 41 = 2),
yp = 17 (17 2 mod 41 = 2)

q = 47 4 Выбирается закрытый ключ d (0 2 = x 3 + Ax + B (mod n) > y 2 = x 3 + 3x + 7 (mod 41).

Примем x1 = 7, тогда y1 2 mod 41 = (7 3 + 3 * 7 + 7) mod 41 = 2, откуда y1 = 17.

2) Находим координаты второй точки. Для этого вначале вычисляется коэффициент λ

Решая последнее уравнение, получаем λ = 2 (34 * 2 mod 41 = 27).

Координаты второй точки получаем путем удваивания первой из выражений

x2 = (λ 2 – 2x1) mod n = (2 2 – 2 * 7) mod 41 = -10 mod 41 = 31,

y2 = (λ(x1 – x2) – y1) mod n = (2 (7 – 31) – 17) mod 41 = -65 mod 41 = 17.

3) Каждую следующую точку рассчитываем по формулам, пока в знаменателе первой формулы не будет получен 0:

К полученному числу точек добавляем точку О, в результате чего q = 46 + 1 = 47. Эта точка есть результат сложения любых двух точек P(xi, yi) и -P(xi, -yi) и представляет собой бесконечно удаленную точку, в которой гипотетически сходятся все вертикальные кривые.

Процедура шифрования отдельного блока выполняется следующим образом [25].

Таблица 9.12. Процедура шифрования отдельного блока (буквы)

№ п/п Описание операции Пример
1 Определяется десятичное представление буквы t. Буква «K»
t = 12
2 Выбирается случайное число k (0 -1 ) mod n,
где xd -1 – обратное число к xd по модулю n.
xd -1 = 14 [(3 * 14) mod 41 = 1]
t = (36 * 14) mod 41 = 12
3 Определяется исходное сообщение по ее десятичному представлению. Буква «K»

Приведенный выше способ шифрования является вариацией шифрования Эль-Гамаля. Если стойкость алгоритма шифрования Эль-Гамаля базируется на сложности решения задачи дискретного логарифмирования, то стойкость шифрования с помощью эллиптических кривых базируется на сложности нахождения множителя k точки P по их произведению. Т.е. если Q = k P, то зная P и k довольно легко вычислить Q. Эффективное решение обратной задачи (найти k при известных P и Q) на текущий момент пока не опубликовано.

Информационная безопасность

Практика информационной безопасности

Страницы

суббота, 28 августа 2010 г.

ISSP \ Домен 06. Криптография. Часть 2

Симметричные шифры делятся на два основных типа: подстановки (substitution) и перестановки (transposition, permutation). Шифры подстановки заменяют биты, символы или блоки на другие биты, символы или блоки. Шифры перестановки не меняют исходный текст, вместо этого они перемещают исходные значения внутри исходного текста – они переставляют биты, символы или блоки символов для скрытия первоначального смысла.

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

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

В шифре перестановки значение перемешивается (scrambled) или ставится в другом порядке. Ключ определяет позицию, на которую следует переместить значение, как показано на Рисунке 6-6.

Это простейший пример шифра перестановки, он показывает только способ выполнения перестановки. Если применяются сложные математические функции, перестановка может стать достаточно сложной для взлома. Современные симметричные алгоритмы используют одновременно и длинные последовательности сложных подстановок и перестановок символов шифруемого сообщения. Алгоритм содержит возможные способы для процессов подстановки и перестановки (представленные в математических формулах). Ключ является инструкциями для алгоритма, точно указывая, как должна происходить обработка и в какой последовательности. Чтобы понять связь между алгоритмом и ключом, взгляните на Рисунок 6-7. Образно говоря, алгоритм создает различные ящики, каждый из которых имеет свой (отличный от других) набор математических формул, указывающих шаги подстановки и перестановки, которые должны быть совершены над попадающими в этот ящик битами. Для шифрования сообщения, значение каждого бита должно пройти через различные ящики. Однако если каждое наше сообщение будет проходить через один и тот же набор ящиков в одинаковой последовательности, злоумышленник легко сможет провести обратный инжиниринг этого процесса, взломать шифр и получить открытый текст нашего сообщения.

Чтобы помешать злоумышленнику, используется ключ, представляющий из себя набор значений, которые указывают, какие ящики должны использоваться, в какой последовательности и с какими значениями. Так, если сообщение А шифруется ключом 1, ключ требует, чтобы сообщение прошло через ящики 1, 6, 4 и 5. Когда нам нужно зашифровать сообщение В, мы используем ключ 2, который требует, чтобы сообщение прошло через ящики 8, 3, 2 и 9. Ключ добавляет случайность и секретность в процесс шифрования.

Простые шифры подстановки и перестановки уязвимы к атакам, выполняющим частотный анализ (frequency analysis). В каждом языке некоторые слова и шаблоны используются чаще, чем другие. Например, в тексте на английском языке обычно чаще используется буква «е». При выполнении частотного анализа сообщения, взломщик ищет самые часто повторяющиеся шабоны из 8 бит (составляющих символ). Если в коротком сообщении он нашел, например, 12 восьмибитных шаблонов, он может сделать вывод, что это вероятнее всего буква «е» — самая часто используемая буква в языке. Теперь взломщик может заменить эти биты на букву «е». Это даст ему опору в процессе, который позволит ему провести обратный инжиниринг и восстановить исходное сообщение.

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

Функции генерации ключей. Для генерации сложных ключей обычно сначала создается мастер-ключ, на основе которого затем генерируются симметричные ключи. Например, если приложение отвечает за создание сеансового ключа для каждого обратившегося к нему субъекта, оно не должно просто раздавать экземпляры одного и того же ключа. Различным субъектам при каждом соединении нужны различные симметричные ключи, чтобы минимизировать продолжительность времени их использования. Даже если атакующий перехватит трафик и взломает ключ, он сможет ознакомиться с переданной информацией только в пределах соответствующего сеанса. В новом сеансе будет использоваться другой ключ. Если два или более ключей формируются на основе мастер-ключа, они называются субключами (subkey).

Функции генерации ключей (KDF – key derivation function) используется для генерации ключей, состоящих из случайных значений. Различные значения могут использоваться независимо или совместно в качестве случайного ключевого материала. Созданы алгоритмы, использующие определенные хэши, пароли и/или «соль», которые много раз проходят через математические функции, указанные алгоритмом. Чем больше раз этот ключевой материал пройдет через указанные функции, тем больший уровень уверенности и безопасности сможет обеспечить криптосистема в целом.

ПРИМЕЧАНИЕ. Помните, что алгоритм остается статичным. Случайность процессов криптографии обеспечивается в основном за счет ключевого материала.

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

Криптографические алгоритмы делятся на симметричные алгоритмы, которые используют симметричные ключи (также называемые секретными ключами (secret key)), и асимметричные алгоритмы, которые используют асимметричные ключи (называемые также открытыми (public key) и закрытыми ключами (private key)).

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

Каждой паре пользователей, для защищенного с помощью симметричной криптографии обмена данными, требуется два экземпляра одного и того же ключа. Например, если Дену и Ирине нужно обмениваться данными, им обоим нужно получить копию одного ключа. Если Ден хочет также с использованием симметричной криптографии взаимодействовать с Нормом и Дейвом, ему нужно иметь три отдельных ключа – по одному на каждого друга. Это не является большой проблемой, пока Дену не потребуется взаимодействовать с сотней других людей за несколько месяцев и сохранять историю переписки. Ведь это потребует использования соответствующего ключа для переписки с каждым конкретным получателем. В таком случае это может стать сложнейшей задачей. Если десяти людям необходимо безопасно обмениваться данными друг с другом с использованием симметричной криптографии, им потребуется 45 ключей. Если же взаимодействовать нужно ста людям, им потребуется 4950 ключей. Формула для расчета необходимого количества симметричных ключей выглядит следующим образом:

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

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

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

Следующий список описывает сильные и слабые стороны криптосистем с симметричными ключами:

Сильные стороны:

  • Гораздо быстрее асимметричных систем
  • При использовании длинного ключа сложно взломать

Слабые стороны:

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

Ниже приведены некоторые примеры симметричных алгоритмов, которые будут подробно рассмотрены позднее в разделе «Блочные и поточные шифры».

  • Data Encryption Standard (DES)
  • Triple-DES (3DES)
  • Blowfish
  • IDEA
  • RC4, RC5 и RC6
  • Advanced Encryption Standard (AES)

Ссылки по теме:

  • Security in Open Systems, Node 208, “Symmetric Key Cryptography,” by Paul Markovitz, NIST Special Publication 800-7 (July 1994)
  • Understanding the Public Key Cryptography

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

В системах с открытыми ключами, создается пара ключей, один из которых является закрытым, другой – открытым. Открытый ключ (public key) может быть известен всем, а закрытый ключ (private key) должен знать только его владелец. Часто открытые ключи хранятся в каталогах и базах данных адресов электронной почты, общедоступных всем желающим использовать эти ключи для зашифрования и расшифрования данных при взаимодействии с отдельными людьми. Рисунок 6-9 иллюстрирует использование отличающихся асимметричных ключей.
Открытый и закрытый ключи асимметричной криптосистемы математически связаны, однако наличие у кого-то открытого ключа другого человека не позволяет узнать соответствующий ему закрытый ключ. Таким образом, если злоумышленник получит копию открытого ключа Боба, это вовсе не значит, что он с помощью какого-то математического волшебства сможет получить соответствующий ему закрытый ключ Боба. Однако, если кто-то получит закрытый ключ Боба, возникнет большая проблема. Поэтому никто кроме владельца не должен иметь доступа к закрытому ключу.

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


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

Если отправителю в большей степени важна конфиденциальность передаваемой информации, ему следует зашифровать свое сообщение на открытом ключе получателя. Это называют безопасным форматом сообщения (secure message format), поскольку только человек, имеющий соответствующий закрытый ключ, сможет расшифровать это сообщение.

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

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

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

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

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

ПРИМЕЧАНИЕ. Криптография с открытым ключом – это асимметричная криптография. Эти термины взаимозаменяемы.

Ниже указаны сильные и слабые стороны алгоритмов с асимметричными ключами:

Сильные стороны

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

Слабые стороны

  • Работают гораздо медленнее симметричных систем
  • Выполняют сложные математические преобразования

Ниже приведены примеры алгоритмов с асимметричными ключами.

  • RSA
  • Криптосистема на основе эллиптических кривых (ECC – Elliptic curve cryptosystem)
  • Алгоритм Диффи-Хеллмана Diffie-Hellman
  • Эль Гамаль (El Gamal)
  • Алгоритм цифровой подписи (DSA – Digital Signature Algorithm)
  • Knapsack

Эти алгоритмы мы рассмотрим далее в этом Домене, в разделе «Типы асимметричных систем».

В Таблице 6-1 приведено краткое резюме основных отличий между симметричными и асимметричными системами.

ПРИМЕЧАНИЕ. Цифровые подписи будут рассмотрены позднее в разделе «Цифровые подписи».

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

Если для зашифрования и расшифрования данных используется блочный шифр, сообщение делится на блоки битов. Затем эти блоки передаются на обработку математическим функциям, по одному блоку за раз. Представьте, что вам нужно зашифровать сообщение для мамы с помощью блочного шифра, который работает с блоками по 64 бита. Длина вашего сообщения составляет 640 бит, поэтому оно делится на 10 отдельных блоков по 64 бита. Каждый блок последовательно передается на вход математической функции. Этот процесс продолжается до тех пор, пока каждый блок не будет преобразован в шифротекст. После этого вы отправляете зашифрованное сообщение вашей маме. Она использует такой же блочный шифр и тот же ключ. Эти 10 блоков шифротекста последовательно передаются в алгоритм в обратной последовательности до тех пор, пока не будет получен исходный открытый текст.

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

В алгоритмах рассеивание может происходить как на уровне отдельных битов в блоках, так и на уровне самих блоков. Перемешивание выполняется с помощью сложных функций подстановки, чтобы злоумышленник не мог понять, каким образом заменялись исходные значения и получить оригинальный открытый текст. Представьте, что у меня есть 500 деревянных блоков, на каждый их которых нанесена буква. Я выстраиваю их в линию, чтобы составить из них сообщение (открытый текст). Затем я заменяю 300 из этих блоков блоками из другого набора (перемешивание путем подстановки). Затем я переставляю все эти блоки (рассеивание посредством перемешивания) и оставляю эту кучу. Чтобы вы смогли восстановить мое исходное предложение, вам нужно заменить блоки правильными и расставить их в правильной последовательности. Удачи!

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

Рассеивание, с другой стороны, означает, что один бит открытого текста оказывает влияние на несколько бит шифротекста. Замена значения в открытом тексте должна приводить к замене нескольких значений в шифротексте, а не одного. Фактически, в действительно стойком блочном шифре, при замене одного бита в открытом тексте, должны изменяться около 50% битов в шифротексте. Т.е. при изменении всего одного бита в открытом тексте, изменится около половины шифротекста.

Блочные шифры в своих методах работы используют и перемешивание, и рассеивание. На Рисунке 6-10 показан концептуальный пример простого блочного шифра. Ему передано для обработки четыре блока длиной по четыре бита каждый. Рассматриваемый блочный алгоритм имеет два уровня четырехбитных боксов замещения, называемых S-боксами. Каждый S-бокс содержит таблицы подстановки, используемые алгоритмом в качестве инструкций по шифрованию битов.

Ключ указывает (см. Рисунок 6-10), какие должны использоваться S-боксы в процесе перемешивания исходного сообщения из читаемого открытого текста в нечитаемый шифротекст. Каждый S-бокс содержит различные методы подстановки и перестановки, которые могут быть выполнены над каждым блоком. Это очень простой пример. В реальности большинство блочных шифров работает с блоками размером по 32, 64 или 128 бит и может использовать гораздо больше S-боксов.

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

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

ПРИМЕЧАНИЕ. Этот процесс очень похож на использование одноразовых шифровальных блокнотов, описанных ранее. Отдельные биты в одноразовом блокноте используются для шифрования отдельных битов сообщения с помощью операции XOR, а в поточном алгоритме отдельные биты создаются генератором ключевого потока, также используемым для шифрования битов сообщения с использованием операции XOR.

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

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

Векторы инициализации (IV – Initialization vectors) – это случайные значения, которые используются алгоритмом для обеспечения отсутствия шаблонов в процессе шифрования. Они используются совместно с ключами и их не нужно шифровать при отправке получателю. Если вектор инициализации не используется, два одинаковых открытых текста, зашифрованные на одном и том же ключе, дадут в результате один и тот же шифротекст. Такой шаблон существенно упростит задачу атакующего по взлому метода шифрования и вскрытию ключа. Если в вашем сообщении есть повторяющаяся часть (фраза или слово), вам нужно убедиться, что при шифровании каждой повторяющейся части открытого текста сообщения, создается различный шифротекст, т.е. не будет создаваться шаблон. Именно для обеспечения большей случайности в процессе шифрования и используется вектор инициализации совместно с ключом.

Стойкие и эффективные поточные шифры имеют следующие характеристики:

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

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

ПРИМЕЧАНИЕ. Конечно, существуют и блочные шифры, реализованные на аппаратном уровне, и поточные шифры, работающие на программном уровне. Указанное выше утверждение просто является «лучшей практикой», рекомендациями по разработке и внедрению.

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

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

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

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

Симметричный ключ используется для шифрования отправляемых вами сообщений. Когда ваш друг получает зашифрованное вами сообщение, ему нужно расшифровать его, для чего ему требуется симметричный ключ, на котором зашифровано ваше сообщение. Но вы не хотите отправлять этот ключ незащищенным образом, т.к. сообщение может быть перехвачено и незащищенный ключ может быть извлечен из него злоумышленником для последующего использования в целях расшифрования и ознакомления с вашими сообщениями. Не следует использовать для шифрования сообщений симметричный ключ, если для него не обеспечена надлежащая защита. Для обеспечения защиты симметричного ключа можно использовать асимметричный алгоритм, с помощью которого он может быть зашифрован (см. Рисунок 6-13). Но зачем нам использовать симметричный ключ для шифрования сообщений, а асимметричный ключ для шифрования симметричного ключа? Как было сказано ранее, асимметричный алгоритм работает медленно, т.к. он использует более сложную математику. А поскольку ваше сообщение, скорее всего, будет длиннее ключа, для его шифрования разумнее использовать более быстрый алгоритм (симметричный), а для шифрования ключа подойдет медленный (асимметричный), но обеспечивающий дополнительные сервисы безопасности.

Как это работает в реальности? Предположим, что Билл отправляет Полу сообщение и хочет, чтобы только Пол мог прочитать его. Билл зашифровывает сообщение на секретом ключе, теперь он имеет шифротекст и симметричный ключ. Ключ должен быть защищен, поэтому Билл зашифровывает симметричный ключ на асимметричном ключе. Асимметричные алгоритмы используют закрытый и открытый ключи, поэтому Билл зашифровывает симметричный ключ на открытом ключе Пола. Теперь у Билла есть шифротекст сообщения и шифротекст симметричного ключа. Почему Билл зашифровал симметричный ключ на открытом ключе Пола, а не на своем закрытом ключе? Если бы Билл зашифровал его на собственном закрытом ключе, кто угодно мог бы расшифровать его на открытом ключе Билла и получить симметричный ключ. Однако Биллу не нужно, чтобы любой, имеющий его открытый ключ, мог читать его сообщения Полу. Биллу нужно, чтобы такая возможность была только у Пола. Итак, Билл зашифровал симметричный ключ на открытом ключе Пола. Если Пол хорошо защищал свой закрытый ключ, только он один сможет прочитать сообщение Билла.

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

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

Здесь все достаточно просто, вам нужно запомнить следующие аспекты:

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

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

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

Если у Тани есть симметричный ключ, который она постоянно использует для шифрования сообщений между ней и Лансом, этот симметричный ключ не нужно перегенерировать или изменять. Они просто используют один и тот же ключ каждый раз при взаимодействии с использованием шифрования. Однако длительное повторное использование одного и того же ключа повышает вероятность его перехвата и компрометации безопаных коммуникаций. Чтобы избежать этого, следует генерировать новый симметричный ключ каждый раз, когда Тане и Лансу нужно взаимодействовать, и использовать его лишь на протяжении одного сеанса связи, а затем уничтожать (см. Рисунок 6-14). Даже если им потребуется снова взаимодействовать всего через час, будет сгенерирован новый сеансовый ключ.

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

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

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

ПРИМЕЧАНИЕ. Закрытые и симметричные ключи не должны храниться и/или передаваться в виде открытого текста. Хотя это кажется очевидным, уже множество программных продуктов было скомпрометировано именно по этой причине.

Проблемы беспроводной безопасности. Мы рассматривали различные стандарты 802.11 и протокол WEP в Домене 05. Среди обширного списка проблем WEP, есть проблема, связанная с шифрованием данных. Если для шифрования беспроводного трафика используется только WEP, в таком случае в большинстве реализаций используется только один статистический симметричный ключ для шифрования пакетов. Одним из изменений и преимуществ стандарта 802.11i является то, что он обеспечивает шифрование каждого пакета уникальным сеансовым ключом.

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

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

Основная идея асимметричных криптоалгоритмов состоит в том, что для шифрования сообщения используется один ключ, а при дешифровании — другой. Кроме того, процедура шифрования выбрана так, что она необратима даже по известному ключу шифрования — это второе необходимое условие асимметричной криптографии. То есть, зная ключ шифрования и зашифрованный текст, невозможно восстановить исходное сообщение — прочесть его можно только с помощью второго ключа — ключа дешифрования. А раз так, то ключ шифрования для отправки писем какому-либо лицу можно вообще не скрывать — зная его все равно невозможно прочесть зашифрованное сообщение. Поэтому, ключ шифрования называют в асимметричных системах «открытым ключом», а вот ключ дешифрования получателю сообщений необходимо держать в секрете — он называется «закрытым ключом».

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

Напрашивается вопрос: «Почему, зная открытый ключ, нельзя вычислить закрытый ключ ?» — это третье необходимое условие асимметричной криптографии — алгоритмы шифрования и дешифрования создаются так, чтобы зная открытый ключ, невозможно вычислить закрытый ключ.

В целом система переписки при использовании асимметричного шифрования выглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя пара ключей: «открытый» Ej и «закрытый» Dj, где j — номер абонента. Все открытые ключи известны всем пользователям сети, каждый закрытый ключ, наоборот, хранится только у того абонента, которому он принадлежит. Если абонент, скажем под номером 7, собирается передать информацию абоненту под номером 9, он шифрует данные ключом шифрования E9 и отправляет ее абоненту 9. Несмотря на то, что все пользователи сети знают ключ E9 и, возможно, имеют доступ к каналу, по которому идет зашифрованное послание, они не могут прочесть исходный текст, так как процедура шифрования необратима по открытому ключу. И только абонент №9, получив послание, производит над ним преобразование с помощью известного только ему ключа D9 и восстанавливает текст послания. Заметьте, что если сообщение нужно отправить в противоположном направлении (от абонента 9 к абоненту 7), то нужно будет использовать уже другую пару ключей (для шифрования ключ E7, а для дешифрования — ключ D7).

Как мы видим, во-первых, в асимметричных системах количество существующих ключей связано с количеством абонентов линейно (в системе из N пользователей используются 2*N ключей), а не квадратично, как в симметричных системах. Во-вторых, при нарушении конфиденциальности k-ой рабочей станции злоумышленник узнает только ключ Dk: это позволяет ему читать все сообщения, приходящие абоненту k, но не позволяет вывадавать себя за него при отправке писем.

Технология применения систем ЭЦП рассчитана на сеть абонентов, посылающих друг другу электронные документы, например платежные поручения. Абонентами могут быть клиенты банка и сам банк в системах клиент банк или банки при обмене документами в межбанковской сети. Некоторые из этих абонентов могут только проверять подписанные другими сообщения, другие (назовем их абонентами с правом подписи) могут как проверять, так и подписывать сообщения. Кроме того, могут быть случаи, когда кто-либо может ставить свою ЭЦП только в качестве второй подписи после подписи определенного абонента-начальника (например, директор бухгалтер); это не меняет существа дела.

Далее, возможны две ситуации: либо в этой сети есть центр (абонент, наделенный особыми полномочиями), либо все абоненты с правом подписи равноправны. Не исключен, однако, и вариант, при котором функции центра рассредоточены по нескольким «локальным центрам». В сетях с центрами могут быть заложены разные степени «доверия» центра к абонентам. Образно говоря, сети могут быть «тоталитарными» и «демократическими», т.е. центры в сетях могут (потенциально) либо полностью контролировать абонента, либо выполнять чисто формальные функции администрирования, скажем, по приему в сеть новых абонентов.

Архитектура алгоритмов ЭЦП

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

В случае программной реализации необходимо проверить, нет ли в системе «криптовирусов», которые могут нанести существенный вред. Например, в момент подписания «криптовирусы» могут перехватить секретные ключи (и скопировать их в нужное место). Кроме того, при проверке подписи они могут заставить систему «сказать», что подпись верна, хотя она на самом деле неверна. Можно представить себе «криптовирус», который, попав в систему лишь один-единственный раз в момент генерации ключей, «поможет» системе сгенерировать слабые ключи. Например, если ключи генерируются на основе датчика случайных чисел, который использует встроенный таймер, вирус может изменить показания таймера, а потом восстановить «статус кво». Впоследствии эти ключи могут быть легко вскрыты злоумышленником. Далее этот вирус уже не нужен, он сделал свое дело. Против таких «криптовирусов» имеется только одна защита — загрузка с «чистой» системной дискеты, и использование «чистого», «родного» программного продукта.

Чтобы поставить ЭЦП под конкретным документом, необходимо проделать довольно большой объем вычислительной работы. Эти вычисления разбиваются на два этапа.

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

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

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

Далее, к полученному значению хеш-функции применяют то или иное математическое преобразование (в зависимости от выбранного алгоритма ЭЦП), и получают собственно подпись документа.

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

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

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

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

Стандарты и сертификаты

Система ЭЦП должна решать задачу предотвращения подделки подписи. Не так давно (после долгих споров, продвинувших науку вперед) в США был принят стандарт на электронную подпись. Для чего он нужен? Во-первых, для получения уверенности в том, что сделанное в соответствии со стандартом средство реализации ЭЦП является криптостойким. Во-вторых, стандарт обеспечивает патентную чистоту. В частности, алгоритм RSA запатентован в США.

Некоторые банки используют в качестве основы своей системы ЭЦП известный пакет программ Pretty Good Privacy (PGP), созданный под руководством Филипа Циммермaннa (Philip Zimmermann). Хотя он свободно рaспрострaняется по сетям, это не означает, что его можно безнаказанно использовать существует патентное законодательство. Кроме того, в банках обнаружено несколько закладок (в частности против систем, построенных на основе пакета программ PGP), при помощи которых были подделаны электронные документы (см. статью А.Щербакова, упомянутую выше).

Попросту говоря, стандарт это достаточно подробное описание алгоритмов, по которым вычисляется и проверяется подпись.

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

В России приняты стандарты: ГОСТ Р 34.10-94 «Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма» и ГОСТ Р 34.11-94 «Функция хеширования». В основу ГОСТ Р 34.10-94 положена однонаправленная функция, основанная на дискретном возведении в степень.

Можно быть вполне уверенным, что алгоритм из стандарта ГОСТ Р 34.10-94 обладает высокой криптографической стойкостью. Однако пользователя мало интересуют премудрости криптографии. Он должен быть убежден, что его подпись никто подделать не сможет и если программа определила, что такое-то сообщение подписал А. Б. Иванов, то его на самом деле подписал именно А. Б. Иванов и он не сможет от этого отпереться.

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

Гарантией надежности может служить сертификация продукта Федеральным агентством правительственной связи и информации (ФАПСИ). Сертификация — это процесс, в результате которого подтверждается соответствие требованиям стандарта. Однако в данном случае имеется тонкость, состоящая в том, что стандарт определяет процедуру выработки и проверки электронной цифровой подписи, а сертифицируется средство, реализующее эту процедуру. При сертификации необходимо проверять соответствие сертифицируемого средства требованиям не только стандарта, но и целому ряду других требований (по надежности, отсутствию закладок, качеству протоколов и т.д.). Ясно, что работа по сертификации требуют высочайшей квалификации, весьма ответственна и трудоемка, а поэтому и длительна. В США, например, процесс сертификации занимает более года. Здесь банкам надо выбирать между надежными сертифицированными средствами реализации функции ЭЦП и средствами, может быть, более современными, но не прошедшими еще сертификации, а значит и менее надежными).В связи с этим может возникнуть ситуация, когда выбор на рынке средств, реализующих процедуру выработки и проверки ЭЦП, окажется небольшим, что поставит банки перед необходимостью покупать не очень удобное средство или платить непомерно высокую цену. Будем надеяться, что подготавливаемые нормативные акты по реализации законодательных положений, регулирующих применение средств обеспечения подлинности информации учтут требования антимонопольного законодательства.

Стойкость большинства схем ЭЦП зависит от стойкости асимметричных алгоритмов шифрования и хэш-функций.

Существует следующая классификация атак на схемы ЭЦП:

— атака с известным открытым ключом.

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

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

— Направленная атака с выбором сообщения

— Адаптивная атака с выбором сообщения.

Каждая атака преследует определенную цель, которые можно разделить на несколько классов:

— полное раскрытие. Противник находит секретный ключ пользователя

— универсальная подделка. Противник находит алгоритм, функционально аналогичный алгоритму генерации ЭЦП

— селективная подделка. Подделка подписи под выбранным сообщением.


— экзистенциальная подделка. Подделка подписи хотя бы для одного случайно выбранного сообщения.

На практике применение ЭЦП позволяет выявить или предотвратить следующие действия нарушителя:

— Отказ одного из участников авторства документа.

— Модификация принятого электронного документа.

— Навязывание сообщений в процессе передачи — противник перехватывает обмен сообщениями и модифицирует их.

— Имитация передачи сообщения.

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

Некоторые средства работы с ЭЦП

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

Наиболее известный — это пакет PGP (Pretty Good Privacy) — (www.pgpi.org), без сомнений являющийся на сегодня самым распространенным программным продуктом, позволяющим использовать современные надежные криптографические алгоритмы для защиты информации в персональных компьютерах.

К основным преимуществам данного пакета, выделяющим его среди других аналогичных продуктов следует отнести следующие:

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

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

3. Бесплатность. Готовые базовые продукты PGP (равно как и исходные тексты программ) доступны в Интернете в частности на официальном сайте PGP Inc.

4. Поддержка как централизованной (через серверы ключей) так и децентрализованной (через «сеть доверия») модели распределения открытых ключей.

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

Текущая версия — 7.0.3 для платформ Windows 9x/NT/2000, MacOS.

GNU Privacy Guard (GnuPG)

GnuPG (www.gnupg.org) — полная и свободно распространяемая замена для пакета PGP. Этот пакет не использует патентованный алгоритм IDEA, и поэтому может быть использован без каких-нибудь ограничений. GnuPG соответствует стандарту RFC2440 (OpenPGP).

Текущая версия — 1.0.4, платформы — Unices, Windows 9x/NT

Пакет программ КРИПТОН®Подпись (http://www.ancud.ru/crypto/crpodpis.htm) предназначен для использования электронной цифровой подписи (ЭЦП) электронных документов.

Программы пакета КРИПТОН®Подпись функционируют на компьютере, удовлетворяющем следующим требованиям:

· наличие операционной системы Windows-98 или Windows NT 4.0;

· наличие УКЗД серии КРИПТОН с соответствующим драйвером для Windows-98/NT или его программного драйвера-эмулятора для Windows — Crypton Emulator версии 1.3 или выше.

· наличие Crypton API для Windows версии 2.2 или выше (входит в поставку УКЗД серии КРИПТОН и содержит также драйвер поставляемого УКЗД);

· наличие манипулятора «мышь».

В стандартной поставке для хранения файлов открытых ключей используются дискеты. Помимо дискет, пакет КРИПТОН®Подпись дает возможность использования всех типов ключевых носителей (смарт-карт, электронных таблеток Touch Memory и др.), поддерживаемых текущей версией интерфейса SCApi, входящего в поставку Crypton API v2.2 и выше

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

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

0дной из главных сфер применения схемы шифрования с открытым ключом является решение проблемы распределения ключей. Имеется две совершенно различные области использования шифрования с открытым ключом в этой сфере:

– распределение открытых ключей;

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

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

Распределение открытых ключей

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

– публично доступный каталог;

– авторитетный источник открытых ключей;

– сертификаты открытых ключей.

Публичное объявление открытых ключей

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

Рисунок 1.2 — Неконтролируемое распределение открытых ключей

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

Рисунок 1.3 — Публикация открытых ключей

Публично доступный каталог

Более высокую степень защиты можно обеспечить с помощью создания и обслуживания некоторого публично доступного динамичного каталога открытых ключей. За сопровождение и распространение публичного каталога должен отвечать некоторый надежный центр или надежная организация (рис. 1.3). Такая схема должна включать следующие элементы.

Уполномоченный объект поддерживает каталог с записями вида <имя, открытый ключ>для каждого из участников.

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

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

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

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

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

Авторитетный источник открытых ключей

Лучшая защита распределения открытых ключей может быть достигнута путем более строгого контроля за распределением открытых ключей из каталога. Типичный сценарий представлен схемой (рис. 1.3), в основу которого положен один из рисунков из [РОРЕ79]. Как и прежде, сценарий предполагает наличие некоторого центрального объекта, уполномоченного поддерживать динамический каталог открытых ключей всех участников обмена данными. Кроме того, каждому из участников достоверно известен открытый ключ центра, но только центр знает соответствующий личный ключ. При этом выполняются следующие действия (их номера согласованы с номерами на рис. 1.3).

Инициатор А посылает сообщение с меткой даты/времени авторитетному источнику открытых ключей с запросом о текущем открытом ключе участника В.

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

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

— оригинальный запрос, чтобы сторона А имела возможность сопоставить ответ с ранее отправленным запросом и убедиться, что запрос не был изменен на пути к авторитетному источнику;

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

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

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

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

Респондент В посылает сообщение инициатору А, шифрованное с помощью KU. и содержащее оказию отправителя А (N1), а также новую оказию, сгенерированную участником В (N2). Ввиду того что только он и мог де шифровать сообщение (3), присутствие N1 в сообщении (6) убеждает участника А в том, что отправителем полученного сообщения был В.

Рисунок 1.4 — Сценарий распределения открытых ключей

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

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

Сертификаты открытых ключей

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

Альтернативный подход, который предложил Конфельдер (Kohnfelder) [KOHN78], основан на сертификатах, которые могут использоваться участниками для обмена ключами без контакта с авторитетным источником открытых ключей и должны обеспечивать способ обмена, такой же надежный, как способ получения ключей непосредственно от авторитетного источника открытых ключей. Каждый сертификат содержит открытый ключ и другую информацию, создается авторитетным источником сертификатов и выдается участнику вместе с соответствующим личным ключом. Один участник передает информацию о своем ключе другом; с помощью передачи своего сертификата. Другие участники мо гут проверить, что сертификат был создан авторитетным источником. Можно сформулировать следующие требования к этой схеме:

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

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

Только авторитетный источник сертификатов должен иметь возможность создавать и изменять сертификаты.

Все эти требования удовлетворялись первоначальной схемой из [KOHN78]. Деннинг (Denning) добавил к ним следующее дополнительное требование [DENN83].

4. Любой участник должен иметь возможность проверить срок действия сертификата.

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

CA=EKRauth[T, IDA, KUa],

где KR.auth обозначает личный ключ, используемый авторитетным источником. Теперь участник А может переслать этот сертификат любому другому участнику, который прочитывает и проверяет сертификат:

D KUauth [CA] = DKUauth[EKRauth[T, >

Получатель использует открытый ключ авторитетного источника сертификатов KUauth , чтобы дешифровать сертификат. Ввиду того, что сертификат можно прочитать только с помощью открытого ключа авторитетного источника сертификатов это дает гарантию того, что сертификат пришел именно от авторитетного источника сертификатов. Элементы IDA и KUa сообщают получателю имя и открытый ключ владельца сертификата. Наконец, метка даты/времени Т определяет срок действия сертификата. Метка даты/времени должна быть защищена от следующей последовательности действий. Противник узнает личный ключ А. По этой причине А генерирует новую пару ключей (личный и открытый) и обращается к авторитетному источнику сертификатов за новым сертификатом. Тем временем противник воспроизводит сообщение со старым сертификатом и отсылает его В. Если В будет шифровать сообщения, используя старый скомпрометированный открытый ключ, противник сможет прочитать эти сообщения.

Рисунок 1.5- Обмен сертификатами открытых ключей

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

Распределение секретных ключей с помощью системы с открытым ключом

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

Простое распределение секретных ключей

Исключительно простую схему предложил Меркл (Merkle) [MERK79], рис. 1.6. Если инициатор А намерен обменяться данными с пользователем В, для этого предполагается следующая процедура.

Рисунок 1.6 — Простое использование шифрования с открытым ключом при выборе сеансового ключа

Сторона А генерирует пару открытый/личный ключи и передает сообщение стороне В, содержащее KUа и идентификатор отправителя A, IDA .

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

Пользователь А вычисляет DKRа[EKUa[Ka]], чтобы восстановить секретный ключ. Поскольку только пользователь А может дешифровать это сообщение, только участника обмена данными А и В будут знать значение Кa.

Участник А выбрасывает ключ KRa , а участник В — выбрасывает ключ KUa.

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


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

Участник А генерирует пару открытый/личный ключи и передает сообщение адресату В, содержащее KUa и идентификатор участника А IDА.

Противник Е перехватывает сообщение, создает собственную пару открытый/личный ключи и передает сообщение адресату В, содержащее KUe || IDA .

В генерирует секретный ключ Кa и передает ЕKUe[Кa].

Противник Е перехватывает это сообщение и узнает Кa , вычисляя DKRe [EKUe [Ka]] .

Противник Е передает участнику А сообщение ЕKUa[Кa].

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

Распределение секретных ключей с обеспечением конфиденциальности и аутентификации

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

Рисунок 1.7 — Распределение секретных ключей с помощью шифрования с открытым ключом

Сторона А использует открытый ключ стороны В, чтобы переслать стороне В шифрованное сообщение, содержащее идентификатор участника A (IDA) и оказию (N1), используемую для идентификации данной конкретной транзакции.

Пользователь В посылает сообщение пользователю А, зашифрованное с помощью KUa и содержащее полученную от него оказию (N1) и новую оказию (N2), сгенерированную пользователем В. Ввиду того что только участник В мог дешифровать сообщение (1), присутствие N1 в сообщении (2) убеждает участника А в том, что респондентом является сторона В.

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

Участник А выбирает секретный ключ Кa посылает участнику В сообщение М = EKUb[EKRa[Ka]]. Шифрование этого сообщения открытым ключом стороны В гарантирует, что только участник В сможет прочитать его, а шифрование личным ключом участника А — что только участник А мог послать его.

Сторона В вычисляет DKUa [EKRb [M]], чтобы восстановить секретный ключ.

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

Еще одна схема использования шифрования с открытым ключом при распределении секретных ключей представляет гибридный подход, применяемый на мэйнфреймах IBM [LE93]. Эта схема предполагает участие центра распределения ключей (ЦРК), с которым каждый пользователь использует свой главный секретный ключ, и распределение секретных сеансовых ключей, шифруемых главным ключом. Схема шифрования с открытым ключом служит для распределения главных ключей. В основе такого трехуровневого подхода лежит следующая логика.

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

2. Обратная совместимость. Гибридную схему можно легко реализовать в виде расширения уже имеющейся схемы, предполагающей использование ЦРК, с минимальными изменениями предусмотренной процедуры и программного обеспечения.

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

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

Постановка задачи

Таким образом, в работе необходимо разработать программное приложение, осуществляющее:

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

создание закрытых и открытых ключей электронных цифровых подписей.

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

Для разработки программного приложения будем использовать программную среду Delphi 7.0.

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

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

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

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

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

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

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

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

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

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

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

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

– абонент В генерирует пару ключей: секретный ключ kB и открытый ключ КB;

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

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

– абонент А зашифровывает сообщение с помощью открытого ключа КB абонента В и отправляет шифртекст абоненту B;

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

Асимметричные криптосистемы обладают следующими характерными особенностями:

1. Открытый ключ КB и криптограмма С могут быть отправлены по незащищенным каналам, то есть противнику известны КB и С.

2. Алгоритмы шифрования и расшифрования ЕB: М ® С, DB: С ® М являются открытыми.

Безопасность асимметричной криптосистемы обеспечивает выполнение следующих требований:

1. Вычисление пары ключей (КB, kB) получателем В на основе начального условия должно быть простым.

2. Отправитель А, зная открытый ключ КB и сообщение М, может легко вычислить криптограмму

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

4. Противник, зная открытый ключ КB, при попытке вычислить секретный ключ kB наталкивается на непреодолимую вычислительную проблему.

5. Противник, зная пару (КB, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую вычислительную проблему.

Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим об разом. Пусть X и Y – некоторые произвольные множества. Функция f: X ® Y является однонаправленной, если для всех х Î X можно легко вычислить функцию , где у Î Y. В то же время для большинства у Î Y достаточно сложно получить значение х Î X, такое, что (при этом полагают, что существует по крайней мере одно такое значение х).

Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования Y ® X.

Примером однонаправленной функции является целочисленное умножение. Прямая задача – вычисление произведения двух очень больших целых чисел Р и Q, то есть нахождение значения N = Р ´ Q является относительно несложной задачей для компьютера.

Обратная задача – факторизация, или разложение на множители большого целого числа, то есть нахождение делителей Р и Q большого целого числа N = Р ´ Q, – является практически неразрешимой при достаточно больших значениях N. По современным оценкам теории чисел, при целом и Р = Q для разложение числа N потребуется около 10 23 операций, то есть задача практически неразрешима для современных компьютеров.

Вторым важным классом функций, используемых при построении криптосистем с открытым ключом, являются однонаправленные функции с секретом. Функция f: X ® Y относится к классу однонаправленных функций с секретом в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен секрет (секретное число, строка или другая информация, ассоциирующаяся с данной функцией). В качестве примера однонаправленной функции с секретом можно указать используемую в криптосистеме RSA модульную экспоненту с фиксированными модулем и показателем степени. Переменное основание модульной экспоненты используется для представления числового значения сообщения М либо криптограммы С.

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

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

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

¨ исчезает квадратическая зависимость числа ключей от числа пользователей; в асимметричной криптосистеме количество используемых ключей связано с количеством абонентов линейной зависимостью (в системе из N пользователей используются 2´N ключей), а не квадратичной, как в симметричных системах;

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

Асимметричные криптосистемы имеют следующие недостатки:

¨ на настоящий момент нет математического доказательства необратимости используемых в асимметричных алгоритмах функций;

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

¨ необходимо защищать открытые ключи от подмены.

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

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

Криптоалгоритм RSA был разработан в 1978 году тремя авторами: Р. Райвестом (Rivest), A. Шамиром (Shamir) и Л. Эйдельманом (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

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

В алгоритме RSA открытый ключ КB, секретный ключ kB, сообщение М и криптограмма С принадлежат множеству целых чисел

Здесь Р и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят их в секрете.

Множество с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ КB выбирают случайным образом так, чтобы выполнялись условия

где – функция Эйлера.

Функция Эйлера указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N.

Условие (4.13) означает, что открытый ключ КB и функция Эйлера должны быть взаимно простыми.

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ kB, такой, что

Это можно осуществить, так как получатель В знает пару простых чисел (Р, Q) и может легко найти . Заметим, что kB и N должны быть взаимно простыми.

Открытый ключ КB используют для шифрования данных, а секретный ключ kB – для расшифрования.

Процедура шифрования определяет криптограмму С через пару (открытый ключ КB, сообщение М) в соответствии со следующей формулой:

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

Расшифрование криптограммы С выполняют, используя пару (секретный ключ kB, криптограмма С) по следующей формуле:

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

Пользователи В и А должны выполнить следующие действия:

1. Пользователь В выбирает два произвольных больших простых числа Р и Q.

2. Пользователь В вычисляет значение модуля .

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


и выбирает случайным образом значение открытого ключа КB с учетом выполнения условий

4. Пользователь В вычисляет значение секретного ключа kB, используя расширенный алгоритм Евклида при решении сравнения

5. Пользователь В пересылает пользователю А пару чисел (N, КB) по незащищенному каналу.

Если пользователь А хочет передать пользователю В сообщение М, он выполнить следующие действия:

6. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в виде числа

7. Пользователь А шифрует текст, представленный в виде последовательности чисел , по формуле

и отправляет криптограмму

8. Пользователь В расшифровывает принятую криптограмму

используя секретный ключ kB, по формуле

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

Пример: Шифрование сообщения CAB. Для простоты вычислений будут использоваться небольшие числа. На практике применяются очень большие числа (длиной 250÷300 десятичных разрядов).

Действия пользователя В:

1. Выбирает Р = 3 и Q = 11.

2. Вычисляет модуль .

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

Выбирает в качестве открытого ключа КB произвольное число с учетом выполнения условий

т.е. ключ должен быть взаимно простым с (целым числом, которое не имеет общих делителей с – 3, 7, 9 и т.д.). Пусть .

4. Вычисляет значение секретного ключа kB, используя расширенный алгоритм Евклида при решении сравнения

5. Пересылает пользователю А пару чисел (N = 33, КB = 7).

Действия пользователя А:

6. Представляет шифруемое сообщение как последовательность целых чисел в диапазоне 0. 32. Пусть буква А представляется как число 1, буква В – как число 2, буква С – как число 3. Тогда сообщение CAB можно представить как последовательность чисел 312, то есть М1 = 3, М2 = 1, М3 = 2.

7. Шифрует текст, представленный в виде последовательности чисел М1, М2 и М3 используя ключ КB = 7 и N = 33, по формуле

Отправляет пользователю В криптограмму

Действия пользователя В:

8. Расшифровывает принятую криптограмму С1, С2, С3 используя секретный ключ kB = 3, по формуле

Таким образом, восстановлено исходное сообщение: CAB

Криптоалгоритм RSA всесторонне исследован и признан стойким при достаточной длине ключей. В настоящее время длина ключа 1024 бит считается приемлемым вариантом. Некоторые авторы утверждают, что с ростом мощности процессоров криптоалгоритм RSA потеряет стойкость к атаке полного перебора. Однако увеличение мощности процессоров позволит применить более длинные ключи, что повышает стойкость RSА. Следует отметить, что алгоритм RSА можно применять как для шифрования сообщений, так и для электронной цифровой подписи.

Нетрудно видеть, что в асимметричной криптосистеме RSA количество ис­пользуемых ключей связано с количеством абонентов линейной зависимостью (в системе из N пользователей используются 2 ´ N ключей), а не квадратичной, как в симметричных системах.

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

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

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

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

Поэтому мы можем представить их следующим образом:

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

Цифровые подписи (может как включать, так и не включать шифрование)

Эта статья будет сфокусирована на симметричных и асимметричных алгоритмах шифрования.

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

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

Взаимосвязанность ключей

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

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

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

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

Длина ключей

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

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

Преимущества и недостатки

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

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

Варианты применения

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

Благодаря своей скорости, симметричное шифрование широко используется для защиты информации во многих современных компьютерных системах. Например, Advanced Encryption Standard (AES) используется правительством США для шифрования секретной информации. AES заменил ранее принятый стандарт шифрования данных (DES), который был разработан в 1970-х годах в качестве стандарта симметричного шифрования.

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

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

Гибридные системы

Во многих приложениях, симметричное и асимметричное шифрование используются вместе. Хорошим примером таких гибридных систем являются криптографические протоколы Security Sockets Layer (SSL) и Transport Layer Security (TLS), которые были разработаны для обеспечения безопасной связи в интернете. Протоколы SSL на данный момент считаются небезопасными и ими не рекомендуют пользоваться. В свою очередь, протоколы TLS считаются безопасными и широко используются всеми современными веб-браузерами.

Использование шифрования криптовалютами

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

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

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

Заключение

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

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

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

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

Обобщенная схема асимметричной криптосистемы с открытым ключом показана на рисунке 42.

В этой криптосистеме применяют два различных ключа: КА — открытый ключ отправителя А; КВ — секретный ключ получателя В. Генератор ключа целесообразно располагать на стороне получателя В (чтобы не пересылать секретный ключ Кв по незащищенному каналу). Значения ключей КА, КВ – зависят от начального состояния генератора ключей.

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

Характерные особенности асимметричных криптосистем:

1. Открытый ключ Кв и криптограмма С могут быть отправлены по незащищенному каналу, т.е. могут быть известны противнику;

Рис. 42. Обобщенная схема асимметричной криптосистемы с открытым ключом

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

Ев: М С, являются открытыми. Защита информации в асимметричной криптосистеме основана на секретности ключа КВ.

У. Диффи и М. Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы:

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

— Отправитель А, зная открытый ключ КА и сообщение М, может легко зашифровать М:

С=ЕКА(М). (36)

3. Получатель В, используя секретный ключ КВ и шифрограмму С, может легко восстановить М:

М=ДКВ(С). (37)

4. Противник, зная открытый ключ КА, при попытке вычислить секретный ключ КВ наталкивается на непреодолимую вычислительную проблему.

5. Противник, зная пару (КА, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую вычислительную проблему.

Криптосистема RSA

Алгоритм RSA предложен в 1978 г. тремя авторами: Райвестом (Rivest), Шамиром (Shamir) и Адлеманом (Adleman). Это первый полноценный алгоритм с открытым ключом, который может работать в режиме шифрования и ЭЦП. Алгоритм использует две однонаправленные функции: произведение больших простых чисел и модульную экспоненту.

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

Задача факторизации является трудно разрешимой задачей для больших значений модуля N.

Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые числа Р и Q случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, Р. Райвест, полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Однако этот прогноз не оправдался из-за сравнительно быстрого прогресса компьютеров и их вычислительной мощности, а также улучшения алгоритмов факторизации.

Криптосистемы RSA реализуются как аппаратным, так и программным путем.

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

Программная реализация RSA примерно в 100 раз медленнее программной реализации DES. С развитием технологии эти оценки могут несколько изменяться, но асимметричная криптосистема RSA никогда не достигнет быстродействия симметричных криптосистем.

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

Дата добавления: 2020-04-19 ; просмотров: 959 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Илон Маск рекомендует:  Сервисы для автоматизации продвижения в соцсетях
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL