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



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

3.9.1 Задача дискретного логарифмирования в Z*p — отдельные биты (individual bits - Ok)

Пусть p нечетное простое и  порождающий элемент группы Z*p. Допустим, что задача дискретного логарифмирования в Z*p труднообрабатываемая (intractable). Пусть Z*p и пусть x = log α β. Напомним из Утверждения 2.135, что - квадратичный вычет по модулю p тогда и только тогда, когда x четное (is even). Следовательно, младший бит x равен (1- ( /p))/2, где символ Лежандра (Legendre symbol) ( /p) может быть эффективно вычислен (Алгоритм 2.149). В более общем случае действительно следующее.
3.83 Утверждение Пусть p нечетное простое, и пусть  порождающий элемент группы Z*p. Предположим, что p - 1 = 2s t, где t нечетное. Тогда существует эффективный алгоритм, который при заданном Z*p, вычисляет s младших битов числа x = log α β.
3.84 Утверждение Пусть p простое и  порождающий элемент группы Z*p. Определим предикат B: Z*p → {0, 1}, как

B(x) =

Тогда B является сложным предикатом для функции возведения в степень по модулю p. Другими словами, при известных p, , и , вычислить один бит B(x) дискретного логарифма x = log α β так же сложно, как вычислить полностью дискретный логарифм.
3.85 Утверждение Пусть p простое и  порождающий элемент группы Z*p. Пусть k = O(lg lg p) целое. Пусть интервал [1, p-1] поделен на 2k интервалов I0, I1,…, I2k -1 приблизительно одной длины. Определим k-битовый предикат B (k): Z*p → {0, 1}k, как B(k) (x) = j, если xIj .Тогда B(k) сложный k-битовый предикат для функции возведения в степень по модулю p.
3.9.2 The RSA problem — отдельные биты

Пусть n произведение двух различных нечетных простых p и q, и пусть e целое, такое, что НОД(e, (p - 1)(q - 1)) = 1.
Для известных n, e, и c = xe mod n (для некоторых xZn), легко получить некоторую информацию о x. Например, так как e нечетное целое,



и, следовательно, отдельный бит информации (x/n) может быть просто определен путем вычисления символа Якоби (Jacobi) (c/n) (Алгоритм 2.149). Однако остаются другие биты информации о x, которые сложно вычислить, как показали следующие два результата.
3.86 Утверждение Определим предикат B: Zn → {0, 1}, как B(x) = x mod 2; то есть B(x) младший бит числа x. Тогда B сложный предикат для функции RSA (см. стр. 115).
3.87 Утверждение Пусть k = O(lg lg n) целое. Определим k-битовый предикат B(k): Zn → {0, 1}k, как B(k)(x) = x mod 2k. То есть B(k)(x) состоит из k младших битов числа x. Тогда B(k) сложный k-битовый предикат для функции RSA.
Таким образом, в функции RSA есть lg lg n одновременно защищенных битов.
3.9.3 Задача Рабина — отдельные биты

Пусть n = pq, где p и q различные простые, и оба сравнимы с 3 по модулю 4.
3.88 Утверждение Определим предикат B: Qn → {0, 1}, как B(x) = x mod 2; то есть B(x) младший бит квадратичного вычета x. Тогда B сложный предикат для функции Рабина (см. стр. 115).
3.89 Утверждение Пусть k = O(lg lg n) целое. Определим k-битовый предикат B(k): Qn → {0, 1}k, как B(k)(x) = x mod 2k . То есть B(k)(x) состоит из k младших битов квадратичного вычета x. Тогда B(k) сложный k-битовый предикат для функции Рабина.
Таким образом, в функции Рабина есть lg lg n одновременно защищенных битов.
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