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

[*kitty*]

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

[*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 19:49

[Lapp]

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

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

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

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

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