Занятие 5 Теоретико-числовые алгоритмы в криптографии



Скачать 21.95 Kb.
Дата07.07.2013
Размер21.95 Kb.
ТипДокументы
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 5
Теоретико-числовые алгоритмы в криптографии

Цель. Изучение применяемых в криптографии базовых алгоритмов работы с большими числами.
Порядок выполнения работы.

  1. Выбрать одну из предложенных тем работ.

  2. Познакомиться с алгоритмами решения задач в рамках выбранной темы.

  3. Объяснить, при решении каких задач криптографии они применяются.

  4. Изложить суть алгоритмов, их свойства, оценки вычислительной сложности, провести сравнительный анализ, описать подходы к программной реализации.

  5. Выполнить программную реализацию одного или нескольких алгоритмов (по согласованию с преподавателем)

  6. Подготовить отчет о работе (5-7 страниц)

  7. На основе отчета подготовить обзорное сообщение по теме на 15 минут (включая демонстрацию программы)



Темы.


  1. Арифметика вычетов. Операции с большими числами по модулю p. Возведение числа в степень по модулю р. Алгоритм Евклида. Нахождение обратных чисел по модулю р. Нахождение квадратичных вычетов. [2, 3, 7]

  2. Модульное представление чисел и Китайская теорема об остатках. [2,3,7]

  3. Проверка большого числа на простоту (тест на основе малой теоремы Ферма, тест Соловея-Штрассена, тест Рабина-Миллера и др.) [1,2,3,]

  4. Построение больших простых чисел (Критерий Люка, на основе теоремы Диемитко, метод Мауэра, на основе чисел Мерсена и др.) [1,2,3]

  5. Алгоритмы факторизации целых чисел (алгоритм Полларда, алгоритм Полларда-Штрассена, Факторизация Ферма, Алгоритм Диксона, квадратичное решето и др.) [1,2,3,5]

  6. Дискретное логарифмирование (Алгоритм перебора, алгоритм Сильвера- Поллига-Хеллмана (алгоритм согласования) и др.) [1,3,5,7]

  7. Операции на эллиптических кривых. Дискретное логарифмирование на эллиптических кривых.[4,8]

  8. Построение псевдослучайных последовательностей.[3,5]


Примечание: одна тема может выполняться совместно двумя студентами.

время на подготовку 1-2 недели
Литература.

  1. В.В.Ященко Введение в криптографию. – М.:МЦНМО, 1998 (второе издание – в изд. «Питер» в 2001 или 2002 году). Полнотекстовый вариант есть на www.cryptography.ru

  2. А.В.Черемушкин. Вычисления в алгебре и теории чисел. Полнотекстовый вариант есть на www.cryptography.ru и в локальной сети.

  3. Б. Шнайер. Прикладная криптография (http://www.ssl.stu.neva.ru/psw/crypto.html)

  4. Рябко Б.Я., Фионов А.А. Основы современной криптографии. – М.: Научный мир, 2004 (была заказана для библиотеки НГУ и должны были приобрести).

  5. Нечаев В.И. Элементы криптографии. Основы защиты информации. – М.: ВШ.,1999.

  6. Д.
    Кнут. Искусство программирования. Т. 2.

  7. Ахо, Ульман, Хопкрофт. Построение и анализ вычислительных алгоритмов.

  8. Болотов А.А. Алгоритмические основы эллиптических кривых (есть в локальной сети)

Похожие:

Занятие 5 Теоретико-числовые алгоритмы в криптографии iconТеоретико-числовые методы в криптографии
Автор: к ф м н., доцент, доцент кафедры алгебры и математической логики С. И. Яблокова
Занятие 5 Теоретико-числовые алгоритмы в криптографии iconПрограмма курса лекций «теория чисел»
В настоящее время теоретико-числовые методы криптографии активно проникают в сферу экономики и финансов. Этому во многом способствует...
Занятие 5 Теоретико-числовые алгоритмы в криптографии iconРабочая программа по дисциплине «Теоретико-числовые методы в криптографии» для студентов специальности «Компьютерная безопасность»
Дисциплин как алгебра, теория чисел, теория сложности. Студентам, изучающим криптографию всерьез, необходимо знание ее математических...
Занятие 5 Теоретико-числовые алгоритмы в криптографии iconТеоретико-числовые алгоритмы
Арифметическая сложность алгоритмов. Алгоритм Евклида, оценка его сложности (теорема Ламе). Квадратичные сравнения. Малая теорема...
Занятие 5 Теоретико-числовые алгоритмы в криптографии iconЗанятие I тема. Разветвляющиеся алгоритмы. Оператор условия If
До сих пор Вы использовали линейные алгоритмы, т е алгоритмы, в которых все этапы решения задачи выполняются строго последовательно....
Занятие 5 Теоретико-числовые алгоритмы в криптографии iconПрограмма по дисциплине «Теоретико-числовые основы защиты информации» для специальности
Рабочая программа составлена на основании
Занятие 5 Теоретико-числовые алгоритмы в криптографии iconТеоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация
Специальность 05. 13. 18 – математическое моделирование, численные методы и комплексы программ
Занятие 5 Теоретико-числовые алгоритмы в криптографии iconМодели вычислений
Под эффективными алгоритмами всюду ниже, согласно тезису Эдмондса, мы будем понимать полиномиальные алгоритмы. Последние, в соответствии...
Занятие 5 Теоретико-числовые алгоритмы в криптографии iconЗанятие №1 Теоретико-методологические проблемы современного востоковедения
Актуальность востоковедческой проблематики. Перспективы истории в концепциях Ф. Фукуямы и С. Хантигтона
Занятие 5 Теоретико-числовые алгоритмы в криптографии icon§ теоретико-числовые свойства чисел фибоначчи
Если существует хотя бы одно число Фибоначчи un делящееся на m, то таких делящихся на m чисел Фибоначчи можно найти сколь угодно...
Разместите кнопку на своём сайте:
ru.convdocs.org


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