IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Протокол аутентификации Фейге-Фиата-Шамира, С/С++, проблемы с реализацией
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


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

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

Сообщение отредактировано: *kitty* -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


*kitty*, ты хитрая лиса )), если ты все знала - зачем спрашивала? smile.gif
Цитата(*kitty* @ 23.04.2010 20:37) *
Но есть одно существенное "НО": для формирования секретного ключа берутся обратные значения по модулю n для квадратичных вычетов, а не для каждого числа существует обратное значение по модулю n, а именно не существует таких обратных значений для чисел, которые не являются взаимно простыми с n. Поэтому нельзя взять произвольно k целых чисел < n, возвести их в квадрат и найти остаток, так как длина ключа может получиться меньше нужной....
Легко быть взаимно простым с числом, являющимся произведением двух простых. Иначе говоря, НЕ взаимно простых есть только чуть больше двух )).

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


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


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

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

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

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

Точно smile.gif Ну я вот почему-то до сих пор хотела честно находить все вычеты blush.gif laugh.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

Цитата
Точно smile.gif Ну я вот почему-то до сих пор хотела честно находить все вычеты blush.gif laugh.gif
Эээ.. так ты рискуешь умереть с голоду, так и не пообедав, восседая на картофельном Эвересте.. wacko.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


Цитата(Lapp @ 24.04.2010 3:37) *
Кстати, какой у тя компилятор и какая среда? И вообще, Си - это требование или ты просто так дорожишь той найденной библиотекой?

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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(*kitty* @ 24.04.2010 16:42) *
я подумала, вдруг кто-нибудь захочет немного помочь и написать небольшой кусочек кода
Гм.
Помочь хотят все, думаю. Но писать за тебя.. Может, ты начнешь? Начальных данных уже достаточно, кажется. Или еще нет?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


Эх, если бы я могла сама написать, не обращалась бы за помощью... unsure.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






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

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

Нужен PDF?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


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


Гость






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


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


Спасибо, буду пробовать smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


Написала протокол с использованием библиотеки "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


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


Прикрепленные файлы
Прикрепленный файл  FFS_vlc.rar ( 500.87 килобайт ) Кол-во скачиваний: 125
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гость






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

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


Тогда программа будет нормально линковаться. На работоспособность не проверял.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


Спасибо, помогло smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


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

Подскажите, пожалуйста, как её разрешить.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Гость






Цитата
вызывать Form3->ShowModal() нельзя.
Вызывай просто Show(), не модально...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Женский

Репутация: -  1  +


Цитата(volvo @ 5.05.2010 11:33) *

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

Так в том то и дело что выдает ошибку. Когда в обработчике кнопки Form3 пишу
Form1->Memo1->Lines->Add(AnsiString(str) + ";");

проект запускается, но когда нажимаю эту кнопку на стадии выполнения вылетает ошибкаПрикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Гость






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

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 27.10.2020 21:58
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name