Системи шифрування з відкритим ключем

АССИМЕТРИЧНЫЕ ШИФРЫ

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

Системи шифрування з відкритим ключем

Розподіл ключів при традиційному шифруванні вимагає, щоб обидві сторони, що беруть участь в обміні даними, або вже мали загальний ключ, або використовували послуги деякого центра розподілу ключів. Одні з винахідників методу шифрування з відкритим ключем, Діффі та Хеллман, вважали, що друга з цих вимог суперечить самій сутності криптографії – можливості забезпечити повну таємність кореспонденції. Як помітив Діффі: "Який зміст має розробка неприступної криптосистеми, якщо її користувачі повинні застосовувати свої таємні ключі разом з деяким центром розподілу ключів, що може бути скомпрометований або зломщиком, або судовим рішенням?".

Іншою проблемою, що сформулював Діффі і яка, мабуть, не пов'язана з першої, є проблема "цифрових підписів". Якщо використання криптографії одержало дуже широке поширення, і не тільки в області військової справи, але й в області комерції і приватних комунікацій, то електронні повідомлення і документи мають потребу в еквівалентах підписів, використовуваних у паперових документах. Іншими словами, чи можна розробити метод, за допомогою якого обидві сторони могли б переконатися в тім, що цифрове повідомлення було відправлено даною конкретною особою?

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

Алгоритми шифрування з відкритим ключем залежать від одного ключа для шифрування та другого, зв'язаного з першим, ключа для дешифрування. Ці алгоритми мають наступну важливу особливість: з погляду обчислень нереально визначити ключ дешифрування, знаючи тільки використовуваний криптографічний алгоритм і ключ шифрування. Крім того, кожний з цих двох зв'язаних ключів може служити для шифрування, а інший – для дешифрування.

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

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

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

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

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

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

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

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

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

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

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

Пусть есть некоторое источник сообщений А, который создает сообщения X в виде открытого текста. Сообщение адресовано получателю В, который генерирует связанную пару ключей: открытый KBв и личный ключ KBо. Ключ KBо остается известным только пользователю В. Имея сообщение X и ключ шифрования KBв в качестве входных данных, отправитель А формирует шифрованный текст Y.

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

Схема, показанная на рис. 4.1, обеспечивает конфиденциальность.

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

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

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

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

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

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

Применение криптосистем с открытым ключом

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

- Шифрование / дешифрование (открытый ключ получателя);

- Цифровая подпись (личный ключ отправителя);

- Обмен ключами. (Личные ключи одной или обеих сторон).

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

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

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

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

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

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

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

К этим требованиям можно добавить еще одно:

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

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

4.3. Односторонние функции, функции-ловушки и некоторые определения теории чисел

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

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

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

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

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

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

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

Криптографические системы с открытым ключом основаны на мощном математическом аппарате теории чисел. Рассмотрим некоторые ее определения.

Конгруэнтность и взятие числа по модулю. Операция взятия числа a по модулю числа n означает, что число b является остатком от деления числа a на число n: a mod n = b.

Операция взятия числа по модулю имеет 3 основных свойства:

- Аддитивности (a + b) mod n = ((a mod n) + (b mod n)) mod n;

- Мультипликативности (a * b) mod n = ((a mod n)*(b mod n)) mod n;

-Сохранения степени a^k mod n = (a mod n) ^k mod n.

Утверждение, что числа a и b конгруэнтные по модулю означает, что остатки от деления чисел a и b на n равны между собой.

Наибольший общий делитель (НЗД) чисел a и b - это наибольшее из чисел, на которое оба числа делятся без остатка: НЗД (56, 98) = 14.

Простое число - это такое число, что не делится без остатка ни на какое другое число, кроме 1 и самого себя. Взаимно простые числа - это такие числа a и b, что возможно и не являются простыми, но не имеют общего делителя, на который они оба делятся без остатка (кроме числа 1).

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

В общем случае предположим, что нужно найти значение a^m, где a и m являются положительными целыми числами. Если представить m в виде бинарного числа b_kb_{k – 1}… b ₀, то

поэтому

Дата добавления: 2015-08-10