Лабораторная работа 1 состоит из четырех частей, каждая из которых выполняется в одном и том же рабочем листе Excel. — КиберПедия 

Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...

Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...

Лабораторная работа 1 состоит из четырех частей, каждая из которых выполняется в одном и том же рабочем листе Excel.

2018-01-29 179
Лабораторная работа 1 состоит из четырех частей, каждая из которых выполняется в одном и том же рабочем листе Excel. 0.00 из 5.00 0 оценок
Заказать работу

  • В первой части следует составить программу на языке Visual Basic для реализации расширенного алгоритма Евклида.
  • Во второй части надо выполнить генерацию параметров метода RSA. Простые числа, необходимые для RSA, надо выбрать случайным образом, генерируя число из диапазона согласно номеру варианта. Проверить выбранные числа на простоту, используя алгоритм, указанный в вариантах работ.
  • В третьей части надо реализовать шифрованию/расшифровку текстов, вводимых с клавиатуры.
  • В заключительной части необходимо реализовать взлом метода RSA, считая известным открытый ключ RSA. Для разложения числа на множители использовать метод Полларда.

ВАРИАНТЫ ЗАДАНИЙ

№ варианта Алгоритм проверки простоты чисел Диапазон выбора простых чисел (для 1-о и 2-о чисел) Открытый ключ (N,E) и шифр сообщения для взлома
  Метод пробных делений [50;100], [75; 125] (N,e)=(78937, 19) M={44389, 31974, 50020, 41406, 29866}
  Метод Ферма [70;120], [90; 140] (N,e)=(55357, 37) M={13389, 33602, 11685, 33602, 40522, 47755, 10459, 15507, 33602}
  Тест Миллера-Рабина [40;90], [80; 130] (N,e)=(41869, 23) M={21618, 16457, 36520, 31771, 22233, 32135 }
  Метод пробных делений [70;120], [60; 110] (N,e)=(111557, 113) M={49096, 63084, 8557, 3743, 4162, 63084, 8557}
  Метод Ферма [30;70], [70; 120] (N,e)=(96091,113) M={61768, 80113, 95437, 80113, 53070, 75177, 82879}
  Тест Миллера-Рабина [60;100], [110; 150] (N,e)=(139331, 113) M={84929, 101535, 89665, 31645, 48847, 48310, 101535, 89665}
  Метод пробных делений [70;120], [60; 110] (N,e)=(85039, 113) M={30454, 11454, 54678, 37720, 28540, 13779, 22807, 63035}
  Метод Ферма [40;80], [70; 120] (N,e)=(150737, 113) M={104318, 143945, 19327, 69783, 112451, 105094}
  Тест Миллера-Рабина [70;110], [120; 150] (N,e)=(94697,113) M={10546, 67178, 84721, 4306, 78944, 1251, 27204}
  Метод пробных делений [75;110], [100; 130] (N,e)=(156031,113) M={29152, 59889, 6814, 115388, 93780, 105567, 31230, 108149}
  Метод Ферма [35;70], [80; 120] (N,e)=(157379, 113) M={113065, 45393, 45393, 77288, 102351, 90053, 4109, 122125}
  Тест Миллера-Рабина [75;100], [120; 160] (N,e)=(65041, 113) M={11965, 10878, 61241, 39494, 43796, 59735, 10878}
  Метод пробных делений [60;90], [90; 140] (N,e)=(95371, 113) M={73636, 91819, 93589, 82293, 75385, 63153, 27478}
  Метод Ферма [70;100], [1200; 150] (N,e)=(103861, 113) M={31152, 63308, 38428, 91454, 4476, 10515, 70086, 63308, 84514, 83370}
  Тест Миллера-Рабина [65;100], [105; 140] (N,e)=(169921, 113) M={39823, 108107, 55814, 75107, 158616, 145959, 18054}

Теоретический материал

Односторонняя (однонаправленная) функция (one way function) - это функция f, осуществляющая отображение X -> Y, где X и Y - произвольные множества, и удовлетворяющая следующим условиям:

  1. Для каждого x из области определения функции легко вычислить . Понятие «легко» обычно означает, что существует алгоритм, вычисляющий функцию f(x) за полиномиальное время от длины аргумента x.
  2. Задача нахождения прообраза для произвольного y, принадлежащего области значений функции , является вычислительно сложной задачей. Последнее означает, что не существует алгоритма, вычисляющего существенно быстрее, чем алгоритм полного перебора.

Задача разложения натурального числа N на простые множители (факторизация N) явлется задачей вычисления односторонней функции: зная сомножители p и q, нетрудно вычислить их произведение N=p • q, но обратная задача нахождения делителей p и q по известному N является сложной задачей, решение которой требует значительных вычислительных ресурсов.

На вычислительной сложности решения этой задачи построен один из самых известных асимметричных методов криптографии – метод RSA. В 1977 году, когда создатели этого метода Ривест, Шамир и Адлеман объявили о новом методе криптографии, основанном на задаче факторизации, наиболее длинные числа, разложимые на множители, имели длину 40 десятичных цифр, что соответствует, примерно, 132-битовому двоичному числу (число 40 надо домножить на ). Создатели RSA предложили широкой публике расшифровать некую фразу английского языка. Для этого предварительно требовалось факторизовать 129-значное десятичное число N (длины 428 в битовом представлении), про которое было известно, что оно представимо в виде произведения двух простых сомножителей p и q, которые имели длину 65 и 64 десятичных знака.

С тех пор был достигнут значительный прогресс в этой области. Число, предложенное создателями RSA, было разложено в 1994 году с помощью нового мощного метода факторизации – метода квадратичного решета (Quadratic Sieve Factoring), разработанного Карлом Померанцем и реализованного Аткинсом, Граффом, Ленстрой и Лейлендом. В работе участвовало около 600 добровольцев, задействовано в сети около 1700 компьютеров, которые работали в течение 7 месяцев.

Параллельно с этим методом Джоном Поллардом, известным специалистом по криптографии и теории алгоритмов, был разработан еще более быстрый метод, получивший название метода решета числового поля (Generalizad Number Field Sieve - GNFS), который является наиболее быстрым методом и на сегодняшний день. Текущий рекорд, установленный немецкими исследователями, на июнь 2008 года, составляет 1000-бит. Это делает небезопасными ключи RSA длины 1024, которые являются на сегодняшний день, самыми распространенными.


Поделиться с друзьями:

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...

История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...

Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.01 с.