Задача дискретного логарифмирования



страница4/5
Дата22.12.2012
Размер0.51 Mb.
ТипЗадача
1   2   3   4   5

3.71 Замечание (время выполнения Алгоритма 3.68) Для оптимизирования времени выполнения алгоритма вычисления индекса, количество t ключевых элементов факторизации должно выбираться обоснованно. Оптимальный выбор основан на сведениях, касающихся распределения гладких целых чисел в интервале [1, p-1] для группы Z*p , и в случае группы F*2 m, на распределении гладких многочленов (то есть, полиномов, чьи неприводимые делители имеют относительно малые степени) среди полиномов в F2[x] степени меньшей, чем m. С оптимальным выбором t, алгоритм вычисления индекса, как описано выше для Z*p и F*2 m имеет ожидаемое время работы Lq[1/2, c], где q = p или q = 2m , и c >0 константа.
3.72 Замечание (наиболее быстрые известные алгоритмы для дискретных логарифмов в Z*p и F*2 m) На данный момент лучший из известных алгоритм для вычисления логарифмов в F*2 m является разновидностью алгоритма вычисления индекса, называемый алгоритмом Копперсмита (Coppersmiths algorithm), с ожидаемым временем работы L2 m [⅓, c] для констант c <1.587. Лучший известный алгоритм для вычисления логарифмов в Z*p является разновидностью алгоритма вычисления индекса, называемый методом решета числового поля, со средним временем работы Lp [⅓, 1.923]. Последние исследования в этих направлениях описаны в замечаниях раздела (§3.12).
3.73 Замечание (распараллеливание (parallelization) алгоритма вычисления индекса)

(i) При оптимально выбранных параметрах, наиболее трудоемким этапом алгоритма вычисления индекса является генерация соотношений, включающих ключевые элементы факторизации логарифмов (шаг 2 Алгоритма 3.68). Работа на этом этапе легко может быть распределена между несколькими процессорами, объединенными в сеть, предоставив процессорам поиск зависимости отдельно друг от друга. Получаемые соотношения аккумулируются центральным процессором. Когда будет сгенерировано достаточно соотношений, соответствующая система линейных уравнений должна быть решена (шаг 3 Алгоритма3.68) на единственном (возможно параллельном) компьютере.

(ii) Базу данных ключевых элементов факторизации логарифмов достаточно вычислить всего один раз для данного конечного поля. По сравнению с этим вычисление отдельных логарифмов (шаг 4 Алгоритма 3.68) значительно быстрее.
3.6.
6 Задача дискретного логарифмирования в подгруппах Z*p


Задача дискретного логарифмирования в подгруппах Z*p имеет особое значение среди других криптографических методов, потому что ее предполагаемая сложность является основанием защищенности NIST Алгоритма Цифровой Подписи, используемого американским правительством (§11.5.1).

Пусть p простое и q простой делитель p - 1. Пусть G однозначно определенная (unique) циклическая подгруппа Z*p порядка q, и пусть α порождающий элемент G. Тогда задача дискретного логарифмирования в G следующая: дано p, q, α, и β G, найти единственное целое x, 0  x q -1, такое, что x (mod p). Мощные алгоритмы вычисления индекса вряд ли могут быть применены к группе G напрямую. То есть необходимо применить алгоритм вычисления индекса во всей группе Z*p, что бы вычислить логарифмы в меньшей группе G. Следовательно, существует 2 метода, которые можно использовать для вычисления логарифмов в G:

1. Использовать алгоритм “квадратного корня” непосредственно в G, как Rho-алгоритм Полларда (Алгоритм 3.60). Время выполнения при этом подходе O().

2. Пусть  порождающий элемент Z*p, и пусть = (p - 1)/q. Использовать алгоритм вычисления индекса в Z*p для нахождения целых y и z, таких, что  =  y и =  z. Тогда x = log α β = (z/)(y/)-1 mod q. (Так как y и z оба кратны , то y/ и z/ тоже целые.) Время выполнения при этом Lq [⅓, c], если использовать метод решета числового поля.

Какой из двух методов быстрее, зависит от относительного размера и Lp [⅓, c].
3.7 Задача Диффи-Хеллмана

Задача Диффи-Хеллмана тесно связана с хорошо изученной задачей дискретного логарифмирования (DLP) §3.6. Это важно для криптографии с открытым ключом, потому что ее истинная (apparent) сложность обеспечивает надежности, защищенности многих криптографических схем, включая соглашения о ключах Диффи-Хеллмана и его производные (§12.6) и шифрование открытым ключом Эль-Гамаля (§8.4).
3.74 Определение Задача Диффи-Хеллмана (DHP): дано простое p, порождающий элемент  группы Z*p, и элементы a mod p и b mod p, найти abmod p.
3.75 Определение Обобщенная Задача Диффи-Хеллмана (GDHP): дана конечная циклическая группа G, порождающий элемент  группы G, и групповые элементы a и b, найти ab.

Допустим, что задача дискретного логарифмирования в Z*p может быть эффективно решена. Тогда при известных , p, a mod p и b mod p можно сначала найти a из , p, и a mod p решением задачи дискретного логарифмирования, а затем вычислить (b) a = ab mod p. Это устанавливает следующую зависимость между задачей Диффи-Хеллмана и задачей дискретного логарифмирования.
3.76 Утверждение DHP  p DLP. То есть, DHP как минимум в несколько раз меньше DLP. Более того, GDHP  p GDLP.

Остается вопрос, являются ли GDLP и GDHP эквивалентными задачами. Это остается неизвестным; однако, некоторое новое достижение в этом направлении описано в Утверждении 3.77. Напомним, что φ – φ -функция Эйлера (Определение 2.100), и целое число гладкое по отношению к границе B, если все его простые делители sB (Определение 3.13).
3.77 Утверждение (известные эквивалентности между GDHP и GDLP)

(i) Пусть p простое, и известна факторизация p -1. Так же положим, что φ (p-1) гладкое по отношению к границе B, где B = O((ln p)c) для некоторой константы c. Тогда DHP и DLP в Z*p эквивалентные задачи.

(ii) В более общем случае, пусть G конечная циклическая группа порядка n, где известна факторизация n. Положим так же, что φ (n) гладкое по отношению к границе B, где B = O((ln n) c) для некоторой константы c. Тогда GDHP и GDLP в G эквивалентные задачи.

(iii) Пусть G конечная циклическая группа порядка n, где известна факторизация n. Если для каждого простого делителя p числа n либо p –1, либо p +1 является гладким по отношению к границе B, где B = O((ln n) c) для некоторой константы c, тогда GDHP и GDLP в G эквивалентные задачи.
3.8 Сложные модули

Группа множеств Zn, называемая Z*n, была предложена для использования в некоторых криптографических механизмах, включая протоколы соглашения о ключах Якоби (Yacobi) и МакКурлея (McCurley) (см. §12.6 Замечания на стр. 538) и схема идентификации Гиро (Girault) (см. §10.4 Замечания на стр. 423).

Существуют связи криптографического значения между дискретным логарифмом и задачей Диффи-Хеллмана в (циклических подгруппах группы) Z*n, и задача разложения на множители n. Этот раздел обобщает результаты, известные по этой теме.
3.78 Утверждение Пусть n составное целое. Если задача дискретного логарифмирования в Z*n может быть решена за полиномиальное время, тогда n может быть разложено на множители за среднее полиномиальное время.
Другими словами, задача дискретного логарифмирования в Z*n не менее проста, чем задача факторизации n. Утверждение 3.79 частично обратно Утверждению 3.78 и утверждает, что дискретный логарифм в Z*n не сложнее, чем сочетание задач факторизации n и вычисления дискретных логарифмов в Z*p для каждого простого множителя p числа n.
3.79 Утверждение Пусть n составное целое. Задача дискретного логарифмирования в Z*n как минимум в несколько раз меньше комбинации задачи факторизации целых чисел и задачи дискретного логарифмирования в Z*p для каждого простого множителя p числа n.
Утверждение 3.80 говорит о том, что задача Диффи-Хеллмана в Z*n не менее проста, чем задача факторизации n.
3.80 Утверждение Пусть n = pq, где p и q нечетные простые. Если задача Диффи-Хеллмана в Z*n может быть решена за полиномиальное время для значительной доли всех оснований   Z*n, тогда n может быть разложена на множители за ожидаемое полиномиальное время.
3.9 Вычисление отдельных битов

В то время, как задача дискретного логарифмирования в Z*p (§3.6), задача RSA (§3.3) и задача вычисления квадратных корней по модулю составного целого n (§3.5.2) кажутся трудно разрешимыми, правильно подобрав параметры задачи, остается возможным гораздо проще получить некоторую часть информации о решении, например, его младший бит. Оказывается, что, хотя некоторые биты решения этих задач вычислить довольно просто, получить остальные биты так же сложно, как и полное решение. Этот раздел описывает результаты, известные для данного направления. Результаты, могут быть применены для составления схем вероятностного шифрования открытым ключом (§8.7) и псевдослучайных битовых генераторов (§5.5).

Напомним (Определение 1.12), что функция f называется однонаправленной функцией, если f(x) легко вычислима для всех x из области определения, но для большинства y в области значений f, нахождение такого x, что f(x) =y, является трудновычислимым.
Три (кандидата) однонаправленных функций.

Хотя не известно ни одного доказательства существования однонаправленной функции, принято считать, что однонаправленные функции существуют (см. Замечание 9.12). Далее приведены кандидаты на однонаправленные функции (фактически, необратимые перестановки), так как они легко вычислимы, но их инверсия требует решения задачи дискретного логарифмирования в Z*p, задачи RSA, или задачи вычисления квадратных корней по модулю n, соответственно:

1. Модульное возведение в степень с модулем p. Пусть p простое и пусть  порождающий элемент группы Z*p. Функция f: Z*pZ*p определяется, как f(x) = x mod p.

2. RSA функция. Пусть p и q различные нечетные простые, n = pq, и пусть e целое, такое, что НОД(e, (p - 1)(q - 1)) = 1. Функция f: ZnZn определяется, как f(x) = xe mod n.

3.Функция Рабина. Пусть n = pq, где p и q различные простые и оба сравнимы с 3 по модулю 4. Функция f: Qn Qn определяется, как f(x) = x2 mod n. (Напомним из Утверждения 2.160, что f перестановка, и из Утверждения 3.46, что инвертирование f, т.е. вычисление арифметического значения квадратных корней, является трудно разрешимой задачей, в предположении, что факторизация целых чисел неприменима.)
Следующие определения используются в § 3.9.1, 3.9.2, и 3.9.3.
3.81 Определение Пусть f: SS однонаправленная функция, где S конечное множество. Говорят, что булев предикат B: S → {0, 1}k является сложным предикатом (hard predicate) для f, если:

(i) B(x) легко вычислить для данного xS; и

(ii) правило, по которому функция B(x) вычисляется правильно со значительным преимуществом 6 при наличии только функции f(x) (где x S), может быть использовано для легкого инвертирования f.

Другими словами, B является сложным предикатом для однонаправленной функции f, если определение одного бита B(x) информации о x при единственном значении f(x), так же сложно, как инвертирование всей f.
6 В Определениях 3.81 и 3.82 все значения xS равновероятны, а правило вычисления функции выбирается по случайному закону.
3.82 Определение Пусть f: SS однонаправленная функция, где S конечное множество. Говорят, что k-битовый предикат B (k): S → {0, 1}k называется сложным k-битовым предикатом (hard k-bit predicate) для f, если:

(i) B(k) (x) легко вычислить для данного xS; и

(ii) для каждого булевого предиката B: {0, 1}k → {0, 1} правило, по которому функция B(B(k)(x)) вычисляется правильно со значительным преимуществом при единственном значении f(x) (где xS), может быть использовано для легкого инвертирования f.

Если такое B(k) существует, то говорят, что f скрывает k-битов (hide k bits), или что k битов одновременно защищенные биты.

Другими словами, B(k) сложный k-битовый предикат для однонаправленной функции f, если определение какой бы то ни было части информации о B(k)(x) при единственном значении f(x), имеет такую же сложность, как инвертирование всей f.
1   2   3   4   5

Похожие:

Задача дискретного логарифмирования iconМетоды факторизации и дискретного логарифмирования
Учебный курс предназначен для студентов специальности 1-31 03 01-01 «математика (научно-производственная деятельность)». Для понимания...
Задача дискретного логарифмирования iconЛекции 50 часов Экзамен 8 семестр практические занятия 50 часов Диф зачет нет самостоятельная работа 20 часов
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Задача дискретного логарифмирования iconЛекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Задача дискретного логарифмирования iconЛабораторная работа №2 Транспортная задача
Транспортная задача (Задача Монжа — Канторовича) — задача об оптимальном плане перевозок продуктов из пунктов отправления в пункты...
Задача дискретного логарифмирования iconЗадача 1 Задача 2 Медицина. Задача 3 Основные понятия моделирования
Модель — это некоторое упрощенное подобие реального объекта, явления или процесса
Задача дискретного логарифмирования iconЭкзаменационные вопросы Понятие математической модели. Инструментальные переменные и параметры математической модели. Критерий оптимизации и целевая функция
Математические модели простейших экономических задач: задача использования сырья, задача о диете; задача планирования товарооборота;...
Задача дискретного логарифмирования iconКомплексный анализ
Автор: д-р физ мат наук, профессор, зав кафедрой дискретного анализа Бондаренко В. А
Задача дискретного логарифмирования iconЗадача на границах периодической системы 3 Задача кот шредингера и химия 4
Задача 22. Необычные пути окисления жирных кислот: омега- и (омега-1)-окисление 42
Задача дискретного логарифмирования iconЗадача №1. Вычислить определитель четвертого порядка Задача №2. Даны матрицы А, В, с и числа  и 
Задача № Для данной матрицы найти обратную и убедиться, что обратная матрица найдена правильно
Задача дискретного логарифмирования iconЗадача №1: получение данных 6 Задача №2 модели и программное обеспечение управления добычей 7
Задача №3 Переход к технологиям облачных вычислений в задачах связанных с «интеллектуальным месторождением». Высокопроизводительные...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org