Схема фейге фиата шамира

Обновлено: 07.07.2024

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

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

Схему идентификации с нулевой передачей знаний предложили в 1986 г. У.Фейге, А.Фиат и А.Шамир. Она является наиболее известным доказательством идентичности с нулевой передачей конфиденциальной информации.

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

Но прежде всего определимся с терминологией.

Пусть а, b, d, g О Z (множество целых чисел), n О N (множество натуральных чисел, т.е. положительных целых чисел).

Определение 1. Число а сравнимо с b по модулю n, если а и b при делении на n дают одинаковые остатки, т.е.

a mod n = b mod n.

Определение 2. Число d называют обратным к a по модулю n, если произведение a*d при делении на n дает в остатке 1, т.е.

Примите к сведению, что целое число a -1 ( mod n ) существует тогда и только тогда, когда a является взаимно простым с n, т.е. имеет с модулем n наибольший общий делитель, равный единице.

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

Определение 3. Число g называют квадратным корнем из a по модулю n, если произведение g*g при делении на n дает в остатке a, т.е.

g = sqrt ( a ) ( mod n ) .

Упрощенная схема идентификации с нулевой передачей знаний

сторона A, доказывающая свою подлинность;
сторона B, проверяющая подлинность A.

Для того, чтобы сгенерировать открытый и секретный ключи для стороны A, доверенный арбитр (Центр) выбирает такое число V, что сравнение

х 2 º V ( mod n )
имеет решение. Число V при этом называют квадратичным вычетом по модулю n .

Кроме того должно существовать целое число

Выбранное значение V является открытым ключом для А. Затем вычисляют наименьшее значение S, для которого

S º sqrt (V -1 )( mod n ).

Это значение S является секретным ключом для А.

Теперь можно приступить к выполнению протокола идентификации.

1. Сторона А выбирает некоторое случайное число r, r х = r 2 mod n
и отправляет х стороне В.

2. Сторона В посылает А случайный бит b.

3. Если b = 0, тогда А отправляет r стороне В. Если b = 1, то А отправляет стороне В

4. Если b = 0, сторона В проверяет, что

х = r 2 mod n ,
чтобы убедиться, что А знает sqrt (х). Если b = 1, сторона В проверяет,что

х = у 2 * V mod n ,
чтобы быть уверенной, что А знает sqrt (V -1 ).

Эти шаги образуют один цикл протокола, называемый аккредитацией . Стороны А и В повторяют этот цикл t раз при разных случайных значениях r и b до тех пор, пока В не убедится, что А знает значение S.

Если сторона А не знает значения S, она может выбрать такое значение r, которое позволит ей обмануть сторону В, если В отправит ей b = 0, либо А может выбрать такое r, которое позволит обмануть В, если В отправит ей b = 1. Но этого невозможно сделать в обоих случаях. Вероятность того, что А обманет В в одном цикле, составляет 1/2. Вероятность обмануть В в t циклах равна (1/2) t .

Для того чтобы этот протокол работал, сторона А никогда не должна повторно использовать значение r. Если А поступила бы таким образом, а сторона В отправила бы стороне А на шаге 2 другой случайный бит b, то В имела бы оба ответа А. После этого В может вычислить значение S, и для А все закончено.

Параллельная схема идентификации с нулевой передачей знаний

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

Как и в предыдущем случае, сначала генерируется число n как произведение двух больших чисел. Для того, чтобы сгенерировать открытый и секретный ключи для стороны А, сначала выбирают К различных чисел V 1 , V 2 , . V K , где каждое V i , является квадратичным вычетом по модулю n. Иначе говоря, выбирают значение V, таким, что сравнение

х 2 º V i ( mod n )
имеет решение и существует V i -1 ( mod n ). Полученная строка V 1 , V 2 , . V K является открытым ключом.

Затем вычисляют такие наименьшие значения S i , что

S i = sqrt (V i -1 ) ( mod n ) .

Эта строка S 1 , S 2 , . S K является секретным ключом стороны А.

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

1. Сторона А выбирает некоторое случайное число r, r х = r 2 mod n
и посылает х стороне В.

2. Сторона В отправляет стороне А некоторую случайную двоичную строку из К бит:

3. Сторона А вычисляет

у = r * (S 1 b 1 * S 2 b 2 * . * S K b K ) mod n .
Перемножаются только те значения S i , для которых b i = 1. Например, если b 1 = 1, то сомножитель S 1 входит в произведение, если же b 1 = 0, то S 1 не входит в произведение, и т.д. Вычисленное значение у отправляется стороне В.

4. Сторона В проверяет, что

х = у 2 * (V 1 b 1 * V 2 b 2 * . * V K b K ) mod n .

Фактически сторона В перемножает только те значения V i , для которых b i = 1. Стороны А и В повторяют этот протокол t раз, пока В не убедится, что А знает S 1 , S 2 , . S K .

Вероятность того, что А может обмануть В, равна (1/2) Kt . Авторы рекомендуют в качестве контрольного значения брать вероятность обмана В равной (1/2) 20 при К = 5 и t = 4.

Заметим, что 14, 15, 21, 25 и 30 не имеют обратных значений по модулю 35, потому что они не являются взаимно простыми с 35.

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

VV -1 S = sqrt (V -1 ) 111 49 * 3 942 11164 16119 ** 29298 Пояснения:
* (4 * 9) mod 35 = 1; ** (9 * 9) mod 35 = 11

Итак, сторона А получает открытый ключ, состоящий из К = 4 значений V:

Соответствующий секретный ключ, состоящий из К = 4 значений S:

Рассмотрим один цикл протокола.

1. Сторона А выбирает некоторое случайное число r = 16, вычисляет

х = 16 2 mod 35 = 11
и посылает это значение х стороне В.

2. Сторона В отправляет стороне А некоторую случайную двоичную строку

3. Сторона А вычисляет значение

у = r * (S 1 b 1 * S 2 b 2 * . * S K b K ) mod n = 16 * (3 1 * 4 1 * 9 0 * 8 1 ) mod 35 = 31
и отправляет это значение у стороне В.

4. Сторона В проверяет, что

х = y 2 * (V 1 b 1 * V 2 b 2 * . * V K b K ) mod n = 31 2 * (4 1 * 11 1 * 16 0 * 29 1 ) mod 35 = 11 .

Стороны А и В повторяют этот протокол t раз, каждый раз с разным случайным числом r, пока сторона В не будет удовлетворена.

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

В этот протокол можно включить идентификационную информацию.

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

Далее используют одностороннюю функцию f(·) для вычисления f(I, j), где j - некоторое двоичное число, сцепляемое со строкой I. Вычисляют значения

V j = f(I, j)
для небольших значений j, отбирают К разных значений j, для которых V j являются квадратичными вычетами по модулю n. Затем для отобранных квадратичных вычетов V j вычисляют наименьшие квадратные корни из V j -1 (mod n). Совокупность из К значений V j образует открытый ключ, а совокупность из К значений S j - секретный ключ пользователя А.

Схема идентификации Гиллоу - Куискуотера

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

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

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

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

I * G V º 1 (mod n) .

Сторона А отправляет стороне В свои идентификационные данные I. Далее ей нужно доказать стороне В, что эти идентификационные данные принадлежат именно ей. Чтобы добиться этого, сторона А должна убедить сторону В, что ей известно значение G.

Вот протокол доказательства подлинности А без передачи стороне В значения G:

1. Сторона А выбирает случайное целое r, такое, что 1 £ n - 1. Она вычисляет

Т = r V mod n
и отправляет это значение стороне В.

2. Сторона В выбирает случайное целое d, такое, что 1 £ n - 1, и отправляет это значение d стороне А.

3. Сторона А вычисляет

D = r * G d mod n
и отправляет это значение стороне В.

4. Сторона В вычисляет значение

T' = D V I d mod n .
Если Т º Т' (mod n), то проверка подлинности успешно завершена.

Математические выкладки, использованные в этом протоколе не очень сложны:

T' = D V * I d = (r * G d ) V * I d = r V * G dV * I d = r V * (I * G V ) d = r V º T (mod n) .
поскольку G вычислялось таким образом, чтобы выполнялось соотношение

Протокол Фейга-Фиата-Шамира (Feige-Fiat-Shamir) — это один из протоколов идентификации с нулевым разглашением. Основывается на сложности вычисления квадратного корня числа по модулю большого числа с неизвестным разложением на простые множители. Был предложен в 1986 г. У.Фейге, А.Фиатом и А.Шамиром.

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

Описание алгоритма

Доказывающая сторона (Алиса) выбирает секретное число s (которое становится ее секретным ключом), взаимно простое с n, далее вычисляет значение v ≡ s² mod n и публикует значение, объявляя его своим открытым ключом.

Далее следует выполнение протокола идентификации:

1. Алиса выбирает некоторое случайное число z, 1 b mod n.

Если b = 0, то y = z, y² = z², xv b = x, и проверка означает, что выражение x ≡ z² mod n верно. Аналогично, если b = 1, то y ≡ zs mod n, y² ≡ z²s² mod n, xv b = xv ≡ xs² mod n. И проверка также означает, что выражение z²s² ≡ xs² mod n

Эти шаги образуют один цикл протокола, называемый аккредитацией. Алиса и боб повторяют этот цикл t раз при разных случайных значениях z и b до тех пор, пока Боб не убедится, что Алиса знает значение s.

Выводы

Если Алисе неизвестно значение s, она может выбрать такое значение z, которое позволит ей обмануть Боба, либо если он перешлет ей b = 0, либо если он перешлет ей b = 1. Но обмануть Боба в обоих случаях одновременно ей не удастся. Вероятность того, что Алиса обманет Боба в одном цикле, составляет 1/2. Вероятность же обмануть Боба в t циклах равна (1/2) t .

Для того чтобы этот протокол корректно выполнялся, Алиса никогда не должна повторно использовать значение z. Если бы Алиса поступила таким образом, а Боб во время другого цикла отправил бы Алисе на шаге 2 другой случайный бит b, то Боб бы имел оба ответа Алисы. После этого Боб может вычислить значение s, и ему будет известен секретный ключ Алисы.

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

Выбрать случайное число r, 1 2 mod N.

Вычислить H(M, u) = S = (S₁,S₂. S_m).

Подписью для M положить пару (S, T).

Алгоритм проверки подписи состоит в выполнении следующих действий:

По открытому ключу B₁,B₂. B_m mod N и значению T вычислить

Вычислить H(M, W) = S’.

Проверить равенство S = S’.

Пример. Если p = 5, q = 7, N = 35, то возможными квадратичными вычетами являются:

1: x 2  1 (mod 35) имеет решения: x = 1, 6, 29, 34.

4: x 2  1 (mod 35) имеет решения: x = 2, 12, 23, 33.

9: x 2  1 (mod 35) имеет решения: x = 3, 17, 18, 32.

11: x 2  1 (mod 35) имеет решения: x = 9, 16, 19, 26.

14: x 2  1 (mod 35) имеет решения: x = 7, 28.

15: x 2  1 (mod 35) имеет решения: x = 15, 20.

16: x 2  1 (mod 35) имеет решения: x = 4, 11, 24, 31.

21: x 2  1 (mod 35) имеет решения: x = 14, 21.

25: x 2  1 (mod 35) имеет решения: x = 5, 30.

29: x 2  1 (mod 35) имеет решения: x = 8, 13, 22, 27.

30: x 2  1 (mod 35) имеет решения: x = 10, 25.

Обратными значениями (mod 35) и их квадратными корнями являются

B_i

(B_i) -1 = a_i 2

Репутация: 1

Здравствуйте! Очень нужна помощь в написании небольшой программы с большими числами. Необходимо реализовать протокол аутентификации Фейге-Фиата-Шамира, используя длинные ключи. Нашла в инете реализацию цифровой подписи на основе данного протокола с использованием библиотеки ‘lip.h’ (работа с длинными числами, модулярная арифметика), обрадовалась, увидя процедуру генерации ключей, но, начав разбираться в коде поняла, что для цифровой подписи протокол несколько иной…
В протоколе аутентификации ФФШ секретный ключ формируется следующим образом: ищутся квадратичные вычеты по модулю n (n=p*q, где p и q – большие простые числа), далее находят их обратные значения опять же по модулю n, затем из получившегося множества выбирают k значений, из каждого значения извлекается квадратный корень по модулю n – получившийся вектор из k чисел и будет секретным ключом. В цифровой же подписи секретный ключ формируется иным образом. Вот и попала я в тупиковую ситуацию: на Си/Си++ ранее писать не приходилось, работала только на Делфи, поэтому каждый шаг дается пока с трудом, а тут такая головоломка… Не представляю даже каким образом можно реализовать генерацию секретного ключа, а именно нахождение квадратичных вычетов по модулю для длинного числа: осуществлять это перебором? наверное, займет много времени; как хранить найденное множество значений? ведь их будет очень много…
Библиотека, на первый взгляд, приличная, все функции снабжены кратким описанием, присутсвуют все необходимые операции модулярной арифметики: умножение, вычисление обратного значения, квадратного корня и т.д. Сама понимаю, что не справлюсь, поэтому буду очень рада помощи.
Прикрепляю проект с присоединенной библиотекой, ничего не выбрасывала из кода, хотя хэш-функция мне не нужна, а для начала только процедура FFS_gen_keys. Так же выкладываю описание самого алгоритма.
ffs.rar ( 408.75 килобайт ) Кол-во скачиваний: 454

Репутация: 159

Не представляю даже каким образом можно реализовать генерацию секретного ключа, а именно нахождение квадратичных вычетов по модулю для длинного числа: осуществлять это перебором? наверное, займет много времени; как хранить найденное множество значений? ведь их будет очень много…

Непонятен такой момент: сколько тебе нужно вычетов? То есть чему равно то число k?
Собственно поиск вычетов, мне кажется, не так уж и долог. Это не совсем перебор. Смотри.
Берем некторое x (случайно), возводим его в квадрат и находим его остаток (a) по модулю n - это и есть вычет. Так? Вроде, так. Повторяем эту операцию, отсеивая повторы (по a), пока не наберем нужное количество k. Если k не очень велико, то повторов много не будет. Вычетов же довольно много. Если бы n было простым, их было бы порядка n/2. Не знаю, как оценить в случае произведения двух простых, но вряд ли разлчичие составляет много порядков.. )) Так что особой задержки тут ожидать не следует.
Вопрос о хранении тоже сопряжен с их количеством. Чем определяется k?

Ааа.. Ясно: k напрямую связана с криптостойкостью (я все-таки дочитал тот док до конца)). Так что ты выбираешь k, исходя из желаемой прочности. Если устраивает, скажем, 128 бит (при однократной попытке), то k=128. Я прав?

Реализаций длинных чисел, к слову сказать, на Форуме проскакивало несколько. Одна из них, кажется, в FAQе.. Какой конкретно диапазон тебе нужен?

Репутация: 1

Репутация: 159

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

Репутация: 1

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

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

Вот это не поняла что-то, там в примере 143=11*13, обратных значений нет у 11 чисел, так как они не являются взаимно простыми с числом 143.

Репутация: 159

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

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

И ты испугалась? Именно это я и назвал словами "чуть больше двух". Каждое из p и q порождает свою линию "невзаимнопростыхсn" чисел: i*p и j*q. Их количество естественным образом зависит от величины p и q. Всего их p+q, грубо говоря (в примере 13+11=24). Но вычетами являются всего несколько меньше половины - вот и получили 11, что в процентном отношении от 143 довольно много. Но если мы возьмем p и q порядка 10 10 , то их произведение (n) будет порядка 10 20 , а сумма 2*10 10 . И процентное отношение легко превращается в микропроцентное )). Еще раз: именно это я и называю "чуть бльше двух" . То есть вероятность того, что твой вычет не будет иметь обратного значения стремится к нулю с возрастанием размеров чисел.
Примеры - они хороши безусловно, но нужно понимать, что они не всегда прямо масштабируются.

Репутация: 1

Кстати, какой у тя компилятор и какая среда? И вообще, Си - это требование или ты просто так дорожишь той найденной библиотекой?

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

Ну да, я поняла это буквально. Для меня "чуть больше двух" - это три, ну максимум четыре

Читайте также: