Расширенный алгоритм евклида excel

Обновлено: 07.07.2024

Цель. Ознакомиться с аппаратом программирования на языке Visual Basic for Applications, примерами программ для решения простых задач. Разработать и написать в среде Excel программу выработки пар «открытый/закрытый» ключ по методу RSA. Выполнить шифрование конфиденциальных данных.

Программно-аппаратные средства. Компьютерная лаборатория, пакет Microsoft Office.

Задание на лабораторную работу

1. Изучить теоретический материал по данной лабораторной работе.

2. Ознакомиться с указаниями по программированию в на языке VBA в среде Excel.

3. Разработать программный комплекс в среде Excel генерации параметров метода RSA, шифрования/расшифровки данных.

4. Выполнить пробное шифрование/расшифровку данных, передаваемых по сети в рамках компьютерного класса. Вставить в отчет полученные данные, описать методику выполнения задания.

5. Ответить на контрольные вопросы в конце задания.

Указания к выполнению лабораторной работе.

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

¨ В первой части следует составить программу на языке Visual Basic для реализации расширенного алгоритма Евклида.

¨ Во второй части надо выполнить генерацию параметров метода RSA. Простые числа, необходимые для RSA, надо выбрать случайным образом, генерируя число из диапазона согласно номеру варианта. Проверить выбранные числа на простоту, используя алгоритм, указанный в вариантах работ.

¨ В третьей части надо реализовать шифрованию/расшифровку текстов, вводимых с клавиатуры.

¨ В заключительной части необходимо реализовать взлом метода RSA, считая известным открытый ключ RSA. Для разложения числа на множители использовать метод Полларда.

простоты чисел

Метод пробных делений

Односторонняя (однонаправленная) функция (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, которые являются на сегодняшний день, самыми распространенными.

Генерация пар «открытый/закрытый ключ» метода RSA.

1. Выбираются два простых числа p и q. Для нашего примера числа p и q должны находится в интервале от 100 до 200. В этом случае их произведение N=p • q будет иметь длину 10 – 12 бит. В реальных задача длина N выбирается равной 512, 768 или 1024 бита (иногда 2048 для самых ответственных задач).

2. Вычисляем их произведение N=p • q.

3. Вычисляем функцию Эйлера . Значение равно числу натуральных чисел, меньших N, взаимно простых с (т.е. числу всех k < N таких, что наибольший общий делитель НОД(N; k)=1).

4. Выбираем параметр e, входящий в открытый ключ RSA, равным произвольному числу, меньшему N, но взаимно простому с . При реальном шифровании длина e выбирается приблизительно равной L/3, где L – длина N. Можно взять e равным произвольному простому числу, меньшему N и отличному от p и q, проверив при этом условие того, что не делится на е ().

5. Находим параметр d, являющийся секретным параметром метода RSA, из условия . Для вычисления d необходимо воспользоваться расширенным алгоритмом Евклида , который описан ниже. Расширенный алгоритм Евклида по входным натуральным числам A и B находит их наибольший общий делитель C=НОД(А,В), а также числа x и y такие, что выполнено равенство . Для нахождения параметра d подставим в расширенный алгоритм Евклида входные числа и е. Их наибольший общий делитель C=НОД(,е) равен 1. Если это не так, то параметр е выбран неверно. Выполнив вычисления по алгоритму Евклиду мы найдем числа x и y такие, что . Применив операцию к обеим частям последнего равенства, получим . Значит, можно взять значение параметра d равным коэффициенту y из метода Евклида. Однако, коэффициент y может принимать как положительные, так и отрицательные значения, а параметр d обязательно должен положительным, поэтому в случае если y < 0, следует взять

Генерация параметров RSA завершена. Пара (N, e) объявляется открытым ключом, а параметры и d закрытыми параметрами (d – закрытый ключ).

Текст, который следует зашифровать, разбивается на отдельные символы (или на блоки по k бит в реальных задачах, где , L – длина N в битовом представлении). Для шифрования числа с , служащего кодом символа, выполняется операция возведения в степень по формуле

где числа N, e взяты из открытого ключа RSA.

Обратная расшифровка выполняется возведение шифра r в степень d, где d – секретный параметр RSA.

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

Расширенный алгоритм Евклида.

Алгоритм Евклида используются для нахождения по заданным целым числам A и B их наибольшего общего делителя С=НОД(А; B). Расширенный алгоритм Евклида используется также для нахождения целых чисел x, y таких, что выполняется условие . Используется во многих криптографических конструкциях, в том числе в методе RSA.

Основным равенством, используемым для вычисления НОД чисел А и В, является условие

НОД(А, В) = НОД( В, A mod B) (3)

где A mod B – остаток от целочисленного деления А на В. Применяя последовательно формулу (3), мы будем уменьшать числа А и В в этом алгоритме, пока A mod B не станет равным 0, тогда последнее значение аргумента В даст искомый НОД (А, В). Полное описание расширенного алгоритма мы объясним на примере. Пусть числа А и В равны 172 и 38 соответственно. Откроем рабочий лист Excel и разметим в первых строчках заголовки столбцов, а под заголовками А и В поместим числа 172 и 38, как указано на рисунке.

Рис.1. Примерный вид рабочего листа Excel для реализации расширенного алгоритма Евклида.

В столбце Amod B напишем формулу вычисления остатка от целочисленного деления А на В: =ОСТАТ(A3;B3), а в столбце A div B впишем формулу =ЦЕЛОЕ(A3/B3), обозначающую операцию нахождения целой части от деления A на В.

В следующей строке в столбах А и В поместим значения 38 и 20, взятые из двух ячеек, находящихся выше и правее (применение формулы (3)). Значения ячеек под заголовками Amod B и A div B надо вычислить как в предыдущей строке. В Excel для этого достаточно просто скопировать и вставить вышележащие клетки на строку ниже.

Повторяем эти операция несколько раз, пока не получим в столбце Amod B значение 0. Значение В в этой строке будет равно НОД(А,В) (в нашем примере он равен 2).

Далее заполняем столбцы x и y в обратном порядке снизу вверх. Поместим в столбцы x и y в последней полученной строке значения 0 и 1. Далее в каждой следующей (вышележащей) строке i поместим значения x_i и y_i , вычисленные по формулам:

где обозначает значение из столбца A div B, взятое из той же строки, где вычисляются значения x и y. Используя эти формулы, заполним столбцы x и y. В верхней строке получим значения x и y, которые нам нужны.

Алгоритм возведения в степень по модулю натурального числа.

Для выполнения шифрования по методу RSA приходится выполнять возведение в большую степень различных чисел, а результат приводить по модулю числа N, являющегося параметром метода и имеющего длину 512 и более бит. Уже для небольших a и e вычислить значение

выполняя сначала возведение в степень, а потом вычисляя остаток от деления на N, становится невозможным. Между тем, если применить алгоритм, описанный в этом разделе, можно вычислять выражения (1), для достаточно больших чисел a, e, N, оставаясь в рамках обычных операций с целыми числами, заложенных в компьютере.

Алгоритм быстрого возведения в степень основывается на идее замены прямого вычисления возведения в степень последовательными операциями умножения на a и возведения в квадрат. Для этого представим степень e число в двоичном исчислении

где любое t_i для принадлежит , . Зная вектор разрядов , можно вычислить число e , применяя последовательные вычисления:

Например, если e = 13, то в двоичном представлении e = 1101₂ , и 13 можно представить как результат вычисления , .

Последнее число и есть e .

Используя формулы (3), можно процедуру возведения в степень по модулю натурального числа N, записать в виде последовательности итераций:

где . Множитель в зависимости от принимает либо значение a, если , либо 1, если . Результат вычислений можно свести в таблицу

Алгоритм Евклида для многочленов. Алгоритм Евклида позволяет найти наибольший общий делитель двух многочленов, т.е. многочлен наибольшей степени, на который делятся без остатка оба данных многочлена.
Алгоритм основан на том факте, что для любых двух многочленов от одного переменного, f(x) и g(x), существуют такие многочлены q(x) и , называемые соответственно частное и остаток, что

при этом степень остатка меньше степени делителя, многочлена g(x), и, кроме того, по данным многочленам f(x) и g(x) частное и остаток находятся однозначно. Если в равенстве (*) остаток r(x) равен нулевому многочлену (нулю), то говорят, что многочлен f(x) делится на g(x) без остатка.
Алгоритм состоит из последовательного деления с остатком сначала первого данного многочлена, f(x), на второй, g(x):

затем, если r₃(x) ≠ 0, – второго остатка на третий:

и т.д. Поскольку на каждом этапе степень очередного остатка уменьшается, процесс не может продолжаться бесконечно, так что на некотором этапе мы обязательно придем к ситуации, когда очередной, n + 1-й остаток r_{n + 1} равен нулю:

r_n–2(x) = r_n–1(x)∙ q_n(x) + r_n(x),	(n)
r_n–1(x) = r_n(x)∙ q_n+1(x) + r_n+1(x),	(n+1)
r_n+1(x) = 0.	(n+2)

Тогда последний не равный нулю остаток r_n и будет наибольшим общим делителем исходной пары многочленов f(x) и g(x).
Действительно, если в силу равенства (n + 2) подставить 0 вместо в равенство (n + 1), затем – полученное равенство r_{n – 1}(x) = вместо r_{n – 1}(x) – в равенство (n), получится, что r_{n – 2}(x) = r_n(x)∙q_{n + 1}(x) q_n(x) + r_n(x), т.е. r_{n – 2}(x) = r_n(x)( q_{n + 1}(x) q_n(x) + 1), и т.д. В равенстве (2) после подстановки получим, что g(x) = r_n(x)∙Q(x), и, наконец, из равенства (1) – что f(x) = r_n(x)∙S(x), где Q и S – некоторые многочлены. Таким образом, r_n(x) – общий делитель двух исходных многочленов, а то, что он наибольший (т.е. наибольшей возможной степени), следует из процедуры алгоритма.
Если наибольший общий делитель двух многочленов не содержит переменную (т.е. является числом), исходные многочлены f(x) и g(x) называются взаимно-простыми.

Основным равенством, используемым для вычисления НОД чисел А и В, является условие

НОД(А, В) = НОД( В, A mod B) (3)

Рис.1. Примерный вид рабочего листа Excel для реализации расширенного алгоритма Евклида.

Алгоритм возведения в степень по модулю натурального числа.

где любое t_i для принадлежит , . Зная вектор разрядов , можно вычислить число e, применяя последовательные вычисления:

Например, если e = 13, то в двоичном представлении e = 1101₂ , и 13 можно представить как результат вычисления , .

Последнее число и есть e.

Рассмотренный выше метод отыскания двух чисел основывается на использовании представления этих чисел в виде произведения простых множителей. Однако на практике такой метод мало применим, так как разложение числа, как правило, неизвестно, и его отыскание (как будет показано в дальнейшем) является сложной математической задачей.

Другим, наиболее известным способом отыскания наибольшего общего делителя двух чисел является алгоритм, впервые изложенный в трудах древнегреческого математика Евклида (IV-III вв. до н.э.

Алгоритм Евклида заключается в следующем.

Пусть , гдеи мы хотим найти. Разделимнас остатком,. Если, то разделимна:,и т.д. Получим последовательность равенств с убывающими остатками:

где

Если — последний ненулевой остаток, то. , в этом случае.

Пример 5. Найти .

Таким образом.

Для практического использования приведенного алгоритма важнейшим является вопрос о времени его выполнения.

Теорема 1. При алгоритм Евклида позволяет вычислитьза время порядка.

Схема доказательства. Для доказательства данной теоремы достаточно показать, что за каждые два шага алгоритма остаток уменьшается, по крайней мере, вдвое [9]. Таким образом результат работы алгоритма достигается не позднее чем через делений чисел разрядностью, не превосходящихкаждое.

Теорема 2. Наибольший общий делитель двух чисели, где, можно представить в виде линейной комбинации этих чиселс целыми коэффициентами, за время порядка.

Схема доказательства. Для доказательства теоремы достаточно показать [8,9], что представление числа может быть найдено путем последовательного выражениячерез все более ранние остатки в алгоритме Евклида, на что будет затрачено одно умножение и одно сложение или вычитание. Поскольку количество операций реализующих сложение есть величина более низкого порядка, то получаем искомую оценку времени.

Определение 9. Два целых числа иназываются взаимно простыми, если, т.е. если они не имеют общих делителей больших 1.

Определение 10. Для любого целого положительного числа функция Эйлераопределяется как число неотрицательных целых, меньшихи взаимно простых с:

Из определения следуют следующие свойства функции Эйлера:

1. .

2. Для любого простого

Несложно показать 3, что для любого простого и некоторого

1.1.3 Расширенный метод Евклида

Рассмотрим теперь расширенный алгоритм Евклида, позволяющий наряду с наибольшим общим делителем чисел инаходить натуральные числаи, удовлетворяющие равенству. От обычного алгоритма Евклида он отличается тем, что наряду с последовательностью остатковвычисляются ещё две вспомогательные последовательностии. Расширенный алгоритм Евклида заключается в следующем. Пусть,нам необходимо найти натуральные числа и, удовлетворяющие равенству. На первом шаге положим, что.Далее будем выполнять следующую последовательность действий, до тех пор пока :

Значения и, при которых, и будут искомыми в силу следующего утверждения:

Лемма. При всех , выполнимо равенство

Доказательство. Применим индукцию по . Приравенство очевидно. Если равенства доказаны для всех значений индексов меньших, то для, пользуясь индуктивным предположением, получим

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

Расширенный метод Евклида может применяться для нахождения корней частного случая диофантовых уравнений .

В криптографии расширенный метод очень часто применяется для нахождения обратного значения по модулю, подробнее будет рассмотрено в разделе 2.

Упражнения для самоконтроля

Определить, сколько делителей имеет заданное число 945.

Найти степени чисел 2, 3, 4, 5 точно делящие число 23455.

Найти значение двумя способами: через разложение на простые множители и используя алгоритм Евклида.

При помощи алгоритма Евклида найти наибольший общий делитель и представить его в виде линейной комбинации с целыми коэффициентами.

Найти ииз уравнения.

Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.

Читайте также: