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

[*kitty*]

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

[*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. Если честно, то библиотека конкретно эта понравилась: простая, охватывает основные необходимые моменты и самый большой плюс - снабжена понятными, доступными описаниями всех функций, примерами. Для Делфи подобного не нашла, если и есть библиотеки, то либо без описания, либо настолько это какими-то непонятными обрывками... Самостоятельно разбираться в библиотеках (что, где и как там делается) времени не хватает, потому что засяду с этим надолго. А к этой целая книжечка в качестве документации идет . Вот я подумала, вдруг кто-нибудь захочет немного помочь и написать небольшой кусочек кода

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

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