Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.7.1 Общетеоретические обоснования Вверх: 13. Методы построения больших простых чисел Назад: 13.6 Полиномиальные алгоритмы доказательства простоты n с помощью известного полного разложения n-1 на простые множители   Содержание   Предметный указатель


13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма"

В указанном Стандарте предлагается алгоритм построения простых чисел $ p$ длины $ t_p$ битов, $ 1021\leqslant t_p\leqslant 1024$, с простым делителем $ q$ длины $ t_q$ битов, $ 255\leqslant t_q\leqslant 256$, числа $ p-1$. При этом частное $ (p-1)/q$ также имеет большой простой делитель $ Q$ длины 512 битов. Наличие достаточно больших простых делителей у числа $ p-1$ вызвано требованиями предлагаемого Стандартом алгоритма электронной цифровой подписи. Алгоритм построения чисел $ p$ с указанными свойствами предлагается в двух модификациях (Процедуры В и В$ '$), ориентированных соответственно на 16- и 32-битовые вычислительные машины. Модификации отличаются лишь размерами случайных чисел, вырабатываемых случайными датчиками, основанными на линейном конгруэнтном методе и указанными в Стандарте. В Процедуре В такой датчик имеет вид

$\displaystyle x_n=(19381x_{n-1}+c)\bmod 2^{16}, $

а в процедуре В$ '$

$\displaystyle x_n=(97781173x_{n-1}+c)\bmod 2^{32}. $

Основу указанных процедур составляют соответственно Процедуры А и А$ '$, позволяющие строить при каждом целом $ t>17$ простые числа $ p$ длины $ t$ битов с простым делителем $ q\mid(p-1)$ длины $ [t/2]$ битов (здесь $ [\,.\,]$ -- целая часть числа). Процедуры А и А$ '$ также отличаются лишь размерами используемых случайных чисел. Мы опишем в п. 13.7.2 и затем проанализируем алгоритм, лежащий в основе этих процедур, на примере процедуры А. Использование этого алгоритма в процедурах В и В$ '$ не имеет принципиальных отличий.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.7.1 Общетеоретические обоснования Вверх: 13. Методы построения больших простых чисел Назад: 13.6 Полиномиальные алгоритмы доказательства простоты n с помощью известного полного разложения n-1 на простые множители   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100