Схема Шнорра
Схема Шнорра (англ. schnorr scheme) — одна из наиболее эффективных и теоретически обоснованных схем аутентификации. Безопасность схемы основывается на трудности вычисления дискретных логарифмов. Предложенная Клаусом Шнорром схема является модификацией схем Эль-Гамаля (1985) и Фиата-Шамира (1986), но имеет меньший размер подписи. Схема Шнорра лежит в основе стандарта Республики Беларусь СТБ 1176.2-99 и южнокорейских стандартов KCDSA и EC-KCDSA. Она была покрыта патентом США 4999082, который истек в феврале 2008 года. ВведениеСхемы аутентификации и электронной подписи — одни из наиболее важных и распространенных типов криптографических протоколов, которые обеспечивают целостность информации. Понять назначение протоколов аутентификации можно легко на следующем примере. Предположим, что у нас есть информационная система, в которой необходимо разграничить доступ к различным данным. Также в данной системе присутствует администратор, который хранит все идентификаторы пользователей с сопоставленным набором прав, с помощью которого происходит разграничение доступа к ресурсам. Одному пользователю может быть одновременно разрешено читать один файл, изменять второй и в то же время закрыт доступ к другому. В данном примере под обеспечением целостности информации понимается предотвращение доступа к системе лиц, не являющихся её пользователями, а также предотвращение доступа пользователей к тем ресурсам, на которые у них нет полномочий. Наиболее распространенный метод разграничения доступа, парольная защита, имеет массу недостатков, поэтому перейдем к криптографической постановке задачи. В протоколе имеются два участника — Алиса, которая хочет подтвердить свой идентификатор, и Боб, который должен проверить это подтверждение. У Алисы имеется два ключа — K 1 {displaystyle mathrm {K} _{1}} , открытый (общедоступный), и K 2 {displaystyle mathrm {K} _{2}} — закрытый (приватный) ключ, известный только Алисе. Фактически, Боб должен проверить, что Алиса знает свой закрытый ключ K 2 {displaystyle mathrm {K} _{2}} , используя только K 1 {displaystyle mathrm {K} _{1}} . Схема Шнорра — одна из наиболее эффективных среди практических протоколов аутентификации, реализующая данную задачу. Она минимизирует зависимость вычислений, необходимых для создания подписи, от сообщения. В этой схеме основные вычисления могут быть сделаны во время простоя процессора, что позволяет увеличить скорость подписания. Как и DSA, схема Шнорра использует подгруппу порядка q {displaystyle q} в Z p ∗ {displaystyle mathbb {Z} _{p}^{*}} . Также данный метод использует хеш-функцию h : { 0 , 1 } ∗ → Z p {displaystyle h:{0,1}^{*} o mathbb {Z} _{p}} . Генерация ключейГенерация ключей для схемы подписи Шнорра происходит так же, как и генерация ключей для DSA, кроме того, что не существует никаких ограничений по размерам. Заметим также, что модуль p {displaystyle p} может быть вычислен автономно. Протокол проверки подлинностиАлгоритм работы протоколаБезопасность алгоритма зависит от параметра t. Сложность вскрытия алгоритма примерно равна 2 t {displaystyle 2^{t}} . Шнорр советует использовать t около 72 битов, для p ≥ 2 512 {displaystyle pgeq 2^{512}} и q ≥ 2 140 {displaystyle qgeq 2^{140}} . Для решения задачи дискретного логарифма, в этом случае, требуется по крайней мере 2 72 {displaystyle 2^{72}} шагов известных алгоритмов. ПримерГенерация ключей:
Проверка подлинности:
Атаки на СхемуПассивный противникЕсли в схеме Шнорра предположить, что Алиса является противником, то на шаге 1 она может выбрать x {displaystyle x} случайным, но эффективным способом. Пусть x {displaystyle x} — это переданное Алисой число. Предположим, что можно найти два случайных числа e 1 {displaystyle e_{1}} и e 2 {displaystyle e_{2}} такие, что e 1 ≠ e 2 {displaystyle e_{1} eq e_{2}} и для каждого из них Алиса может найти соответствующие s 1 {displaystyle s_{1}} и s 2 {displaystyle s_{2}} , для которых подтверждение даст положительный результат. Получаем: x = g s 1 y e 1 mod p {displaystyle x=g^{s_{1}}y^{e_{1}}{mod {p}}} x = g s 2 y e 2 mod p {displaystyle x=g^{s_{2}}y^{e_{2}}{mod {p}}} .Отсюда g s 1 y e 1 = g s 2 y e 2 ( mod p ) {displaystyle g^{s_{1}}y^{e_{1}}=g^{s_{2}}y^{e_{2}}{pmod {p}}} или же y e 1 − e 2 = g s 2 − s 1 ( mod p ) {displaystyle y^{e_{1}-e_{2}}=g^{s_{2}-s_{1}}{pmod {p}}} . Так как e 1 ≠ e 2 {displaystyle e_{1} eq e_{2}} , то существует ( e 2 − e 1 ) − 1 mod q {displaystyle (e_{2}-e_{1})^{-1}{mod {q}}} и, следовательно, ( s 1 − s 2 ) ( e 2 − e 1 ) − 1 = w mod q {displaystyle (s_{1}-s_{2})(e_{2}-e_{1})^{-1}=w{mod {q}}} , то есть дискретный логарифм y {displaystyle y} . Таким образом, либо e 1 , e 2 , e 1 ≠ e 2 {displaystyle e_{1},e_{2},e_{1} eq e_{2}} такие, что Алиса может ответить надлежащим образом на оба из них (при одном и том же x {displaystyle x} ) на шаге 3 протокола, встречаются редко, что означает, что атака Алисы успешна лишь с пренебрежимо малой вероятностью. Либо такие значения попадаются часто, и тогда тот алгоритм, который применяет Алиса, можно использовать для вычисления дискретных логарифмов. Иными словами, доказано, что в предположении трудности задачи дискретного логарифмирования схема аутентификации Шнорра является стойкой против пассивного противника, то есть корректной. Активный противникАктивный противник может провести некоторое количество сеансов выполнения протокола в качестве проверяющего с честным доказывающим (или подслушать такие выполнения) и после этого попытаться атаковать схему аутентификации. Для стойкости против активного противника достаточно, чтобы протокол аутентификации был доказательством с нулевым разглашением. Однако свойство нулевого разглашения для схемы Шнорра до сих пор никому доказать не удалось. Протокол цифровой подписиАлгоритм Шнорра также можно использовать и в качестве протокола цифровой подписи сообщения M {displaystyle M} . Пара ключей используется та же самая, но добавляется однонаправленная хеш-функция H ( M ) {displaystyle H(M)} . Генерация подписиПроверка подписиЭффективностьОсновные вычисления для генерации подписи производятся на этапе предварительной обработки и на этапе вычисления w S 1 mod q {displaystyle wS_{1}{mod {q}}} , где числа w {displaystyle w} и S 1 {displaystyle S_{1}} имеют порядок 140 {displaystyle 140} битов, а параметр r {displaystyle r} — 72 {displaystyle 72} бита. Последнее умножение ничтожно мало по сравнению с модульным умножением в схеме RSA. Проверка подписи состоит в основном из расчета X = g S 2 y S 1 {displaystyle X=g^{S_{2}}y^{S_{1}}} , который может быть сделан в среднем за 1.5 l + 0.25 t {displaystyle 1.5l+0.25t} вычислений по модулю p {displaystyle p} , где l = [ l o g 2 q ] {displaystyle l=[log_{2}q]} есть длина q {displaystyle q} в битах. Более короткая подпись позволяет сократить количество операций для генерации подписи и верификации: в схеме Шнорра O ( log 2 q log 2 2 p ) {displaystyle O(log _{2}qlog _{2}^{2}p)} , а в схеме Эль-Гамаля O ( log 3 p ) {displaystyle O(log ^{3}p)} . ПримерГенерация ключей: Подпись сообщения: ПатентыСхема Шнорра имеет патенты в ряде стран. Например, в США № 4,995,082 от 19 февраля 1991 года (истёк 19 февраля 2008 года). В 1993 году Public Key Partners (PKP) из Саннивейла (Sunnyvale) приобрела мировые права на данный патент. Кроме США, данная схема запатентована также и в нескольких других странах. Модификации схемыМодификация схемы, которая была выполнена Эрни Брикеллом (Brickell) и Кевином МакКерли (McCurley) в 1992 году, значительно повысила безопасность данной схемы. В их методе используется число p {displaystyle p} , которое так же, как и p − 1 {displaystyle p-1} , сложно разложить, простой делитель q {displaystyle q} числа p − 1 {displaystyle p-1} и элемент α {displaystyle alpha } порядка q {displaystyle q} в Z p ∗ {displaystyle mathbb {Z} _{p}^{*}} , которые впоследствии применяются в подписи. В отличие от схемы Шнорра подпись в их методе вычисляется уравнением s = e α + k mod ( p − 1 ) {displaystyle s=ealpha +k{mod {(}}p-1)} .ПреимуществаВ то время, как в вычислительном плане модификация Брикелл и МакКерли менее эффективна, чем схема Шнорра, данный метод имеет преимущество, так как основывается на трудности двух сложных задач:
|