Протокол аутентификации Фейге-Фиата-Шамира, С/С++, проблемы с реализацией Опции

[*kitty*]

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

[Lapp]

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

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

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

Добавлено через 6 мин.
Еще одна маленькая неясность: из какого диапазона выбирать случайное x? По идее, оно может (и, наверное, должно) быть больше n. Если брать маленькие (порядка n), то, боюсь, это перекособочит весь алгоритм и понизит его прочность. Не знаю, как тут быть.. Чисто интуитивно кажется, что достаточно диапазона порядка n² . А это в свою очередь означает, что нужно уметь обрабатывать числа аж до n⁴..

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

[*kitty*]

k действительно отвечает за криптоскойкость, чем больше будет компонентов в секретном ключе, тем лучше , выбирается, видимо, из своих собственных соображений. Длина простых чисел p и q, с которых начинается алгоритм, должна быть не меньше 256 бит (опять же, чем больше, тем лучше).
Квадратичные вычеты по модулю n, если использовать способ простого перебора, находятся следующим образом: берутся все целые числа, меньшие n, начиная с единицы, возводятся в квадрат по модулю n, получившиеся остатки и есть искомые квадратичные вычеты. Они могут повторятся. Различных значений должно быть ровно (p-1)*(q-1)/4. Но есть одно существенное "НО": для формирования секретного ключа берутся обратные значения по модулю n для квадратичных вычетов, а не для каждого числа существует обратное значение по модулю n, а именно не существует таких обратных значений для чисел, которые не являются взаимно простыми с n. Поэтому нельзя взять произвольно k целых чисел < n, возвести их в квадрат и найти остаток, так как длина ключа может получиться меньше нужной....

Добавлено через 15 мин.
Ой, сначала не так поняла идею про k . Наверное, хорошая идея, искать не всё, а только пока не наберется k квадратичных вычетов, имеющих обратные значения по модулю n.

Сообщение отредактировано: *kitty* - 23.04.2010 23:49

[Lapp]

*kitty*, ты хитрая лиса )), если ты все знала - зачем спрашивала?

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

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

хорошая идея, искать не всё, а только пока не наберется k квадратичных вычетов, имеющих обратные значения по модулю n.

На идею особо не тянет )). Никто не покупает всю картошку в мире, чтоб приготовить себе обед!

[*kitty*]

*kitty*, ты хитрая лиса )), если ты все знала - зачем спрашивала?

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

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

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

На идею особо не тянет )). Никто не покупает всю картошку в мире, чтоб приготовить себе обед!

Точно Ну я вот почему-то до сих пор хотела честно находить все вычеты

[Lapp]

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

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

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

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

Точно Ну я вот почему-то до сих пор хотела честно находить все вычеты

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

[*kitty*]

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

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

И ты испугалась? Именно это я и назвал словами "чуть больше двух".

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

[Lapp]

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

Гм.
Помочь хотят все, думаю. Но писать за тебя.. Может, ты начнешь? Начальных данных уже достаточно, кажется. Или еще нет?

[*kitty*]

Эх, если бы я могла сама написать, не обращалась бы за помощью...

[volvo]

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

Я бы на твоем месте взял готовую реализацию (если надо - прикреплю сюда PDF-файл, описывающий детали реализации, и содержащий сами исходные коды программы, правда, оно всё по-английски. И еще одно: там для работы с длинными числами используется библиотека GMP), и разобрался бы с ней. Поверь, толку будет больше, чем пытаться сделать то же самое с нуля, тыкаться туда, сюда, и ничего в итоге не продвигается... А когда разберешься - можешь уже и написать все с нуля сама, с использованием LIP.H (так сказать, для закрепления материала )

Нужен PDF?

[*kitty*]

Я уже нашла этот pdf (кстати, это единственная реализация этого протокола, который я нашла в сети, а искала долго), но там другая проблема, никак не могу подсоединить эту библиотеку, она написана под Линакс, есть сборки под ХР, но там какае-то сложности подключения все равно... вообщем не получается.
Вы не работали с этой библиотекой? Может у кого-то получилось её подключить и использовать в Билдере Си++?

[volvo]

Получалось... Вот тут: Sources -> gmp-lib and Builder c++ Adil рассказывал что надо делать для подключения GMP к Билдеру. Даже тестовые проекты выкладывались...

[*kitty*]

Спасибо, буду пробовать

[*kitty*]

Написала протокол с использованием библиотеки "lip.h" в консольном режиме, работает. Теперь нужно реализовать это в визуальном режиме. Создала новый проект с формой, перенесла в папку с проектом файлы "lip.c", "lip.h", добавила в проект. В обработчике кнопки попробовала вызвать библиотечные функции, проект компилируется, но линковщик выдает ошибки по всем функциям:

[Linker Error] Unresolved external 'zrandomb(long *, long * *)' referenced from F:\FFS_VLC\MAINUNIT.OBJ
[Linker Error] Unresolved external 'zrandomprime(long, long, long * *, void (*)(long *, long * *))'
referenced from F:\FFS_VLC\MAINUNIT.OBJ
[Linker Error] Unresolved external 'zswrite(char *, long *)' referenced from F:\FFS_VLC\MAINUNIT.OBJ

Подскажите, пожалуйста, как это исправить?

[volvo]

#include <mem.h>
#include <stdio.h>
#include <stdlib.h>

// Указать явно, что LIP написана на чистом С:
extern "C"
{
	#include "lip.h"
}
#include "MainUnit.h"

Тогда программа будет нормально линковаться. На работоспособность не проверял.

[*kitty*]

Спасибо, помогло

[*kitty*]

Здравствуйте, по ходу реализации возникла ещё одна проблема:
из формы Form1 нажатием кнопки вызывается форма Form3->Show(). Далее, при нажатии кнопки на Form3, в Memo1 на Form1 должна выводится некоторая информация. Необходимо чтобы обе форме оставались на экране, было переключение между этими формами, то есть вызывать Form3->ShowModal() нельзя.

Подскажите, пожалуйста, как её разрешить.

[volvo]

вызывать Form3->ShowModal() нельзя.

Вызывай просто Show(), не модально...

[*kitty*]

Вызывай просто Show(), не модально...

Так в том то и дело что выдает ошибку. Когда в обработчике кнопки Form3 пишу

Form1->Memo1->Lines->Add(AnsiString(str) + ";");

проект запускается, но когда нажимаю эту кнопку на стадии выполнения вылетает ошибка

[volvo]

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