Главная » Просмотр файлов » А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии

А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 23

Файл №1127102 А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии) 23 страницаА.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102) страница 232019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 23)

Тогда n=φ(19)=18. Поскольку решение будем производить вручную, то не будем пользоваться методом Флойда.

Разбиение G на подмножества произведем следующим образом: если x mod 3=1, то x S1, если x mod 3=2, то x S2, если x mod 3=0, то x S3.

Вычисления будут производиться по формулам:

xi+1=f(xi)=

ui+1= , vi+1=

i

0

1

2

3

4

5

6

7

8

xi

1

8

7

18

17

4

13

9

18

ui

0

0

0

0

1

2

2

2

3

vi

0

1

2

3

3

6

7

8

8

S

S1

S2

S1

S3

S2

S1

S1

S3

S3

x3=x8. Логарифм найдем из сравнения (v3v8)log28≡(u8u3) (mod 18)

-5 log28≡3(mod 18)

13 log28≡3(mod 18)

log28≡3·7(mod 18)

log28≡3(mod 18).

Действительно, 23≡8 (mod 19).

Ответ: log28≡3(mod 18).

3.4. Алгоритм Полига-Хеллмана.

Этот алгоритм использует следующий подход: пусть G – группа порядка n, и n= - каноническое разложение на простые сомножители. Если x=logga mod n, то, вычислив xi=logga mod , для 1 ik, можно восстановить x, используя китайскую теорему об остатках.

Для того чтобы вычислить xi, вычисляют коэффициенты l0, l1,…, в pi-чном представлении числа xi: xi=l0+l1pi+…+ , где 0 ≤ lj pi1.

Представим метол Полига-Хеллмана следующим алгоритмом:

Алгоритм Полига-Хеллмана:

Вход: g – порождающий элемент циклической группы порядка n, a G.

Ш.1. Найти каноническое разложение n= .

Ш.2. Для i от 1 до k выполнить следующие действия:

1. Задать q=pi, α=αi.

2. Задать γ=1, l-1=0.

3. Вычислить .

4. Для j от 1 до α—1 выполнить:

4.1. Вычислить γ=γ ,

4.2. Вычислить li= . (например, используя алгоритм «шаг младенца - шаг великана» или прямой поиск).

5. Вычислить xi=l0+l1q+…+lα1qα—1.

Ш.3. Используя Китайскую теорему об остатках, решить систему сравнений xxi(mod ) .

Выход. x=logga mod n.

Замечание. Все вычисления производятся в группе G кроме случаев, когда оговорено иное.

Замечание. Поскольку порядок элемента (в чем нетрудно убедиться, подставив вместо его выражение из 4.2 и учитывая, что порядок есть q), то li= .

Заметим, что вычисление логарифма прямым поиском на этапе 4.2. происходит сравнительно быстро, так как приходится перебирать не более q значений.

Данный метод эффективен в случаях, когда n является большим числом, а все его простые сомножители – малыми числами.

Сложность данного алгоритма составляет O( ) умножений в группе при условии, что разложение n известно.

Пример.

Пусть G=Z*p, p=61, g=2, a=7.

Ш.1. n=φ(p)=p1=60=22·3·5.

Ш.2.

1. q=2, α=2.

2. γ=1, l-1=0.

3. =230 mod 61=60.

4. j=0 γ=1, =730 mod 61 = 60 l0=log6060 mod 61=1.

j=1 γ=2, =(7·2-1)30mod 61=(7·31)30mod 61=1 l0=log601 mod 61=0.

5. x1=1+0·2=1.

1. q=3, α=1.

2. γ=1, l-1=0.

3. =220 mod 61=47.

4. j=0 γ=1, =720 mod 61 = 47 l0=log4747 mod 61=1.

5. x2=1.

1. q=5, α=1.

2. γ=1, l-1=0.

3. =212 mod 61=9.

4. j=0 γ=1, =712 mod 61 = 34 l0=log934 mod 61=4 (этот логарифм нашли прямым перебором).

5. x3=4.

Ш.3. Составим и решим систему . Решением этой системы будет x≡48 (mod 60).

Проверка: 248mod 61=7.

Ответ: log27 mod 60 = 48.

3.5. Алгоритм исчисления порядка (index-calculus algorithm).

Основные идеи алгоритма исчисления порядка были известны с 20-х годов XX века, но лишь в 1979 году Адлерман указал на этот алгоритм как на средство вычисления дискретного логарифма и исследовал его трудоемкость. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах, в частности, в группе Zp*.

Этот алгоритм в отличие от алгоритмов прямого поиска и ро-метода подходит не для всех циклических групп.

Алгоритм состоит в следующем:

Алгоритм исчисления порядка

Вход: g – порождающий элемент циклической группы порядка n, a G, с≈10 – параметр надежности.

Ш.1. Выбирается факторная база S={p1, p2,…,pt}. (Если G=Zp*, то S состоит из t первых простых чисел.)

Ш.2. Выбрать случайное k: 0k<n и вычислить gk.

Ш.3. Попытаться разложить gk по факторной базе:

, αi0.

Если это не удалось, вернуться на Шаг 2.

Ш.4. Логарифмируя обе части получившегося выражения, получаем

(mod n) *

В этом выражении неизвестными являются логарифмы.

Это сравнение с t неизвестными следует запомнить.

Ш.5. Если сравнений вида (*), полученных на Шаге 4, меньше, чем t+c, то вернуться на Шаг 2.

Ш.6. Решить систему t+c сравнений с t неизвестными вида (*), составленную на Шагах 2-5.

Ш.7. Выбрать случайное k: 0k<n и вычислить agk.

Ш.8. Попытаться разложить agk по факторной базе:

, βi0.

Если это не удалось, вернуться на Шаг 7.

Ш.9. Логарифмируя обе части последнего равенства, получаем

x= ,

где loggpi (1it) вычислены на Шаге 6 как решение системы сравнений.

Выход. x = logga mod n.

В том случае, когда G=Zp*, в качестве факторной базы S берут t первых простых чисел. Такой выбор оправдан следующим наблюдением. Число, наугад выбранное из множества целых чисел, с вероятностью 1/2 делится на 2, с вероятностью 1/3 – на 3, с вероятностью 1/5 – на 5 и т.д. Поэтому можно ожидать, что в промежутке от 1 до p—1 найдется достаточно много чисел, в разложении которых участвуют только маленькие простые делители из множества S. Именно такие числа отыскиваются на шагах 2 и 7.

Параметр c вводится для того, чтобы система сравнений, решаемая на Шаге 6, имела единственное решение. Дело в том, что полученная система может содержать линейно зависимые сравнения. Считается, что при значении с порядка 10 и большом p система сравнений имеет единственное решение с высокой вероятностью.

Пример.

G=Z*71, g=7, a=17, n=φ(71)=70.

S={2, 3, 5, 7} (Шаг 1). (Можем сразу указать log77 mod 70=1).

Теперь будем перебирать k для составления системы сравнений вида * (Шаги 2—5).

k=2, 72 mod 71=49=7·7. (поскольку log77 уже вычислен, это сравнение нам не пригодится).

k=3, 73 mod 71=59.

k=4, 74 mod 71=58=2·29.

k=5, 75 mod 71=51=3·17.

k=6, 76 mod 71=2 6≡log72(mod 70)

k=7, 77 mod 71=14=2·7 7≡log72+log77(mod 70)

k=8, 78 mod 71=27=33 8≡3log73(mod 70)

k=9, 79 mod 71=47.

k=10, 710 mod 71=45=32·5 10≡2log73+log75(mod 70)

Теперь имеем достаточно сравнений для того, чтобы определить логарифмы от элементов факторной базы. Вот эти сравнения:

6≡log72(mod 70)

7≡log72+log77(mod 70)

8≡3log73(mod 70)

10≡2log73+log75(mod 70)

Решая полученную систему, получаем (Шаг 6):

log72≡6(mod 70), log73≡26(mod 70),

log75≡28(mod 70), log77≡1(mod 70).

Перейдем к Шагам 7—9:

k=1, 26·7 mod 71=40=23·5 log726≡3log72+log75—1(mod 70)

log726≡3·6+28—1(mod 70)

log726≡45(mod 70)

Проверка: 745 mod 71 = 26. Верно.

Ответ: log726≡45(mod 70).

Замечание: Для случая G=Zp и для случая G=F2m составляет Lq[1/2,c], где q есть мощность G, с > 0 – константа. Алгоритм, имеющий наилучшую оценку сложности (по времени) для дискретного логарифмирования в Zp есть вариант алгоритма исчисления индексов под названием «метод решета числового поля» (number field sieve), для дискретного логарифмирования в F2m - вариант данного алгоритма под названием «алгоритм Копперсмита» (Coppersmith’s algorithm). Эти алгоритмы слишком сложны, чтобы приводить их здесь.

Задачи и упражнения.

Упражнения к Главе 1.

    1. Вычислить НОД(a,b) при помощи алгоритма Евклида с делением с остатком и бинарного алгоритма Евклида. Сравнить количество итераций.

a) a = 715, b = 195; d) a = 1818, b = 726; g) a = 2448, b = 1632;

Характеристики

Тип файла
Документ
Размер
2,98 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6439
Авторов
на СтудИзбе
306
Средний доход
с одного платного файла
Обучение Подробнее