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

принадлежит классу полиномиальных алгоритмов .

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

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

-легко, если  и известны

-легко, если  и известны

-легко, если  известно, но неизвестно

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

 

 

 

1.2. Криптоанализ алгоритмов с открытым ключом

 

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

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

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

 

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

 

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

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

 

Рис. 1.2.  Шифрование с открытым ключом

 

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

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

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

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

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

     Создание и проверка подписи состоит из следующих шагов:

 

Рис. 1.3.  Создание и проверка подписи

 

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

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

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

4. Когда получает подписанное сообщение, он проверяет подпись , используя

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.4. Схема идентификации FIAT-SHAMIR

 

Схема цифровой подписи  и проверки подлинности, разработанная Амосом Фиатом (Amos Fiat) и Ади Шамиром (Adi Shamir). Уриель Фейге (Uriel Feige), Фиат и Шамир модифицировали алгоритм, превратив его в доказательство подлинности с нулевым знанием. Это лучшее доказательство подлинности с нулевым знанием.

9 июля 1986 года три автора  подали заявку на получение  патента США. Из-за возможного  военного применения заявка была рассмотрена военными. Время от времени результатом работы Патентное бюро является не выдача патента, а нечто, называемое секретным распоряжением . 6 января 1987 года, за три дня до истечения шестимесячного периода, по просьбе армии Патентное бюро издало такое распоряжение . Заявило, что " . . . раскрытие или публикация предмета заявки . . . может причинить ущерб национальной безопасности ..." Авторам было приказано уведомить всех граждан США, которые по тем или иным причинам узнали о проводимых исследованиях, что несанкционированное раскрытие информации может закончиться двумя годами тюремного заключения, штрафом $10,000 или тем и другим одновременно. Более того, авторы должны были сообщить Уполномоченному по патентам и торговым знакам обо всех иностранных гражданах, которые получили доступ к этой информации.

Это было нелепо. В течение  второй половины 1986 года авторы представляли свою работу на конференциях в Израиле, Европе и Соединенных Штатах. Они даже не были американским гражданами, и вся работа была выполнена в Институте Вейцмана (Weizmann) в Израиле.

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

Упрощенная схема идентификации Feige-Fiat-Shamir

Перед выдачей любых закрытых ключей арбитр выбирает случайный модуль , n,  который является произведением двух больших простых чисел. В реальной жизни длина п должна быть не меньше 512 битов и лучше как можно ближе к 1024 битам, п может общим для группы контролеров. (Использование чисел Блюма (Blum) облегчит вычисления, но не является обязательным для безопасности.)

Для генерации  открытого и закрытого ключей Пегги доверенный арбитр выбирает число v, являющееся квадратичным остатком mod п. Другими словами выбирается v так, чтобы уравнение х² = v (mod n) имело решение, и существовало v^-1 mod п. Это v и будет открытым ключом Пегги. Затем вычисляется наименьшее s, для которого s ≡ sqrt (v^-1) (mod n). Это будет закрытый ключ Пегги. Используется следующий протокол идентификации.

1. Пегги выбирает случайное r, меньшее п. Затем она вычисляет х =-r² mod n и посылает х Виктору.
2. Виктор посылает Пегги случайный бит b.
3. Если b = 0, то Пегги посылает Виктору r. Если b= 1, то Пегги посылает Виктору у = r*s mod n.
4. Если b = 0, Виктор проверяет, что х = -r² mod п, убеждаясь, что Пегги знает значение sqrt(v^-1). Если b = 1, 
   Виктор проверяет, что х =y²*v mod n, убеждаясь, что Пегги знает значение sqrt(v^-1).

Это один этап протокола, называемый аккредитацией. Пегги и Виктор повторяют этот протокол t раз, пока Виктор не убедится, что Пегги знает s. Это протокол "разрезать и выбрать". Если Пегги не знает s, она может подобрать r  так, что она сможет обмануть Виктора, если он пошлет ей 0, или она может подобрать r  так, что она сможет обмануть Виктора, если он пошлет ей 1. Она не может сделать одновременно и то, и другое. Вероятность, что ей удастся обмануть Виктора один раз, равна 50 процентам . Вероятность, что ей удастся обмануть его t раз, равна 1/2^t.

Виктор может попробовать  вскрыть протокол, выдавая себя за Пегги . Он может начать выполнение протокола с другим контролером, Валерией. На шаге (1) вместо выбора случайного r ему останется просто использовать значение r, которое Пегги использовала в прошлый раз. Однако, вероятность того, что Валерия на шаге (2) выберет то же значение b, которое Виктор использовал в протоколе с Пегги, равна 1/2 . Следовательно, вероятность, что он обманет Валерию, равна 50 процентам. Вероятность, что ему удастся обмануть ее t раз, равна 1/2^t.

Чтобы этот протокол работал, Пегги никогда не должна использовать r повторно. В противном случае, если Виктор на шаге (2) пошлет Пегги другой случайный бит, то он получит оба ответа Пегги. Тогда даже по одному из них он сможет вычислить s, и для Пегги все закончится.

Схема идентификации Feige-Fiat-Shamir

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

Сначала, как  и в предыдущем примере, генерируется п, произведение двух больших простых чисел. Для генерации открытого и закрытого ключей Пегги сначала выбирается k различных чисел: v₁, v₂,...v_k, где каждое v_i, является квадратичным остатком mod п. Иными словами, v_i выбираются так, чтобы х² ≡ v_i (mod n) имело решение, и существовало v_i^-1 mod п. Строка, v₁, v₂, … v_k , служит открытым ключом. Затем вычисляются наименьшие s_i, для которых s_i = sqrt (v_i^-1) (mod n). Строка s₁, s₂, … s_k, служит закрытым ключом.

Выполняется следующий протокол:

1. Пегги выбирает случайное r, меньшее п. Затем она вычисляет х =-r² mod n и посылает х Виктору.
2. Виктор посылает Пегги строку из k случайных битов: b₁, b₂, … b_k.
3. Пегги вычисляет у = r *(s_l^b1 * s₂^b2 *...*s_k^bk )mod n. (Она перемножает вместе значения s_i, соответствующие 
   bi=1. Если первым битом Виктора будет 1, то s_l войдет в произведение, а если первым битом будет 0, то 
   нет, и т.д.) Она посылает у Виктору.
4. Виктор проверяет, что х = у²*( v₁^b1 * v₂^b2  * ...*v_k^bk) mod n. (Он перемножает вместе значения v_i, основываясь 
   на случайной двоичной строке. Если его первым битом является 1, то Vi войдет в произведение, а если 
   первым битом будет 0, то нет, и т.д.)