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

[*kitty*]

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

[Lapp]

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

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

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

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

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