Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Криптография с открытым ключом
Криптография с открытым ключом
Изучение основных методов и алгоритмов криптографии с открытым ключом и их практического использования. Анализ и практическое применение алгоритмов криптографии с открытым ключом: шифрование данных, конфиденциальность, генерация и управление ключами.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 20.06.2011 |
| Размер файла | 1,2 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Пример СТЕП 1. Рассмотрим степени числа 5 по модулю 19:
Поэтому в нашем примере, любые две степени числа 5, показатели которых отличаются на 9 (или на число, кратное 9), сравнимы по модулю 19. Иначе, последовательность является периодической с периодом, равным наименьшему положительному показателю m, при котором 5m = 1 mod 19.
В общем случае можно сказать, что наивысшим из показателей, которому может принадлежать число a по модулю n, является (n). Числа, принадлежащие показателю (n), называются первообразными корнями по модулю n.
В таблице (табл. 2.1), в продолжение примера, приводятся степени целых чисел по модулю 19 (первая выделенная строка соответствует степеням; затемненные части строк соответствуют конкретным периодам).
Как видно, все последовательности заканчиваются числом 1.
В нашем примере длина последовательности является делителем (19) = 18. Некоторые последовательности для a 19 будут иметь длину 18. В таком случае говорят, что целое число a генерирует (своими степенями) множество всех ненулевых вычетов по модулю 19.
Любое из этих чисел называют первообразным корнем по модулю 19.
Важность этого понятия подтверждается тем, что если a является первообразным корнем n, его степени a1, a2,…,a(n) оказываются различными по модулю n и взаимно простыми с n.
В частности, для простого числа p, если a является первообразным корнем p, то a1, a2,…,ap-1 оказываются различными по модулю n и взаимно простыми с n.
Как видно из таблицы, для простого числа 19 его первообразными корнями являются числа 2, 3, 10, 13, 14 и 15.
Не все целые числа имеют первообразные корни. Этими числами могут быть числа 2, 4, pa и 2pa, где p любое нечетное простое число.
Таблица 2.1 Степени целых чисел по модулю 19
2.1.2 Алгоритм определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней
На рисунке 2.1, слайд 2.3 приводится общая блок-схема алгоритма определения степеней целых чисел (am) по конкретно заданному модулю p и одновременно его первообразных корней.
Рис. 2.1. Блок-схема алгоритма вычисления степеней целого числа am
по модулю p и целых чисел, принадлежащих показателю (p)
2.1.3 Инструкция по выполнению задания 1
Проанализировать приведенный пример СТЕП 1 совместно с данными таблицы 2.1.
С использованием «ПРОГРАММЫ 1 алгоритм Евклида нахождения наибольшего общего делителя», подобрать два взаимно простых числа a50, p40 (должно быть gcd (a, p) = 1).
С использованием «ПРОГРАММЫ 2 расширенный алгоритм Евклида для вычисления мультипликативного обратного», проверить подобранные числа действительно ли они являются взаимно простыми? Если они взаимно простые, то имеется мультипликативное обратное.
2.1.4 Алгоритм выполнения задания 1. Вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю (p)
(первообразных корней по модулю p)
В соответствии с подобранными взаимно простыми числами a и p необходимо вручную (или с использованием составленной студентом программы) вычислить для всех положительных целых ap степени по модулю p. В результате получим последовательности (см. таблицу 2.1) Необходимо из них выделить последовательности с длиной (p) = p-1. В таком случае говорят, что каждое целое число a гененрирует (своими степенями) множество всех ненулевых вычетов по модулю p. Эти соответствующие целые a и являются первообразными корнями по модулю p. Таблицу можно построить, используя возможности программы. Так, введя значение целого числа а в одноименное поле ввода, степени числа а по модулю p можно вычислить, нажав соответствующую кнопку. При этом, если при данном значении числа а число итераций на единицу меньше модуля р, то данное простое число а - первообразный корень, иначе - нет.
Ввести полученные результаты (первообразные корни) и исходные данные в программу (ПРОГРАММА 4 вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю (p), первообразных корней по модулю p).
Если Ваши результаты совпадут с результатами программы, то они будут зачтены. Иначе все задание 1 необходимо будет выполнить повторно с подбором новых исходных данных. Далее приводится более подробное описание действий.
Подобранные значения исходных данных вводятся в поля ввода с соответствующими названиями «Целое число (а)» и «Взаимно простой с a модуль (p)». Найти все степени числа a по модулю p и выделить первообразные корни. Полученные ответы ввести в большое поле «Первообразные корни по модулю p». Каждое число необходимо записать на новой строке. Начинать следует с первой строки. Если на следующей строке после пустой строки введены какие-либо значения, то это будет расценено программой как ошибка вводящего. Для проверки программой расчетов студента необходимо нажать кнопку с надписью «Проверка корректности». В ходе проверки программой верности расчетов студента все верные расчеты будут выведены в большом текстовом поле, находящимся в левой части экрана. Если студент ввел хотя бы один неверный ответ, то ему придется выполнить задание с новыми входными данными.
В случае верного решения студентом поставленной задачи информация об этом будет выведена в большом текстовом поле, и студенту станут, доступны для ввода поля ввода задания 2 данной лабораторной работы. При выполнении данной работы, при необходимости, рекомендуется использовать доступные возможности программ из предыдущих лабораторных работ.
Ответы и исходные данные фиксируются в соответствующем МАССИВЕ РЕЗУЛЬТАТОВ.
2.2 Задание 2. Генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети
2.2.1 Теория
Эффективность алгоритма Диффи-Хеллмана опирается на трудностях вычисления дискрет-ных логарифмов. В общем виде
y gx mod p,
вычисление y при заданных g, x и p является относительно простой задачей даже при очень больших значениях x (имеются соответствующие эффективные алгоритмы). Однако если заданы y, g и p, то вычисление x (дискретное логорифмирование) является, вообще говоря, очень непростой задачей. Согласно [1], до недавного времени сложность асимптотически наиболее быстрого из известных алгоритмов вычисления дискретных логарифмов по модулю простого числа оценивалась величиной порядка
ez, где z = ((ln p)1/3ln (ln p))2/3.
Теперь рассмотрим схему Диффи-Хеллмана по обмену ключами [1, 2] (рис. 2.2, слайд 2.4).
Рис. 2.2. Обмен ключами по схеме Диффи-Хеллмана
Глобальные открытые элементы:
простое число p;
первообразный корень простого числа p a, где a p.
Вычисление ключа пользователем А:
Пользователь А выбирает случайное целое число XA p и вычисляет YA = aXA mod p.
XA p секретная величина (закрытый ключ пользователя А);
YA открытая величина (открытый ключ пользователя А).
Вычисление ключа пользователем В:
Пользователь В выбирает случайное целое число XВ p и вычисляет YВ = a XВ mod p.
XВ p секретная величина (закрытый ключ пользователя В);
YВ открытая величина (открытый ключ пользователя B).
Производится обмен открытыми ключами.
Пользователь А вычисляет общий секретный сеансовый ключ
K = (YB) XA mod p.
Пользователь B вычисляет общий секретный сеансовый ключ
K = (YA) XB mod p.
Эти последние формулы дают одинаковые результаты:
K = (YB )XA mod p = (a XВ mod p) XA mod p = (a XВ) XA mod p = a XВ XA mod p = (aXA) XB mod p = (aXA mod p) XB mod p = (YA) XB mod p.
Злоумышленнику могут быть известны величины p, a, YA и YB.
Злоумышленнику для определения секретного ключа пользователя В необходимо вычислить
XВ = Inda, p (YB), иначе YВ = a XВ mod p.
Только после этого он может определить общий секретный ключ K. Вычисление XВ из последнего соотношения (дискретного логарифма) является, вообще говоря, очень непростой задачей.
Взаимный обмен сообщениями с использованием метода обмена ключами Диффи-Хеллмана при определенных условиях (использовании централизованного каталога хранения параметров) обеспечивает как конфиденциальность, так и определенную степень аутентификацию.
Пример ДХ 1: Произвести обмен ключами между двумя пользователями А и В и сгенерировать общий сеансовый секретный ключ по схеме Диффи-Хеллмана.
Примечание. Описание примера дается для процесса информационного обмена между двумя абонентами. Однако интерфейс задания 2 данной лабораторной работы приводится общий (смотри далее). Это сделано для удобства выполнения лабораторной работы автономно одним студентом на одном рабочем месте.
1. Определение общих открытых элементов (в начале данный пункт задания выполняется пользователем А (условно) и полученные результаты в открытом виде передаются (условно) пользователю В). Для экономии времени одновременно пользователь В аналогичную работу выполняет с другими значениями p и a.
Это простое число p и его первообразный корень a.
Простое число выбирается из приведенной в приложении таблицы (таблица 1). Рекомендуется в качестве p выбрать двухразрядное число, равное или меньшее по значению 97. Для рассматриваемого примера, ради обеспечения простоты, мы выберем p=19.
Первообразный корень для выбранного p может быть определен двояко.
В первом случае (именно рекомендуется пойти по этому пути) первообразный корень выбирается из множества первообразных корней, полученных в результате выполнения расчетов по ПРОГРАММЕ 4 «Вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю (p), первообразных корней по модулю p». При этом значение p берется из предыдущей программы, где определялись первообразные корни.
Во втором случае первообразный корень для выбранного p подбирается из условия, что целыми числами с первообразными корнями могут быть только числа 2, 4, n и 2n (где n любое нечетное простое число). Естественно, выбранный в данном случае первообразный корень a p.
В заключение отметим, что для лабораторной работы рекомендуется выбрать простое число из таблицы, вычислить множество соответствующих первообразных корней путем выполнения расчетов по предложенному алгоритму и одновременно проверить выше приведенное условие выбора чисел, которые могут выступать в качестве первообразных корней для выбранного p.
Для нашего примера p=19 и a=10 (см. таблица 2.1., примера СТЕП 1).
2. Выбор секретных ключей пользователей А и В (соответственно XA и XB).
В соответствии с выбранным значением p определяются секретные ключи по условиям XA p и XB p. Выбираем XA=5 и XB=7.
3. Вычисление в соответствии с найденным a и выбранному p открытых ключей YA и YB (соответственно пользователями А и В) для пользователей А и В на основе XA и XB (при этом используется ниже указанная программа)
YA = aXA mod p = 105 mod 19.
YB = aXB mod p = 107 mod 19.
В действительности целые числа, используемые в приведенных соотношениях очень большие и выполнить данные расчеты не так легко. Поэтому необходимо эти расчеты производить в соответствии с ПРОГАММОЙ 3 «Быстрое возведение в степень для ab mod n при больших значениях b» (см. лабораторную работу 1 «Алогритм быстрого возведения в степень для ab mod n при больших значениях b», примеры БВОЗ 1 и БВОЗ 2, и задание 3, не путать p с n; в алгоритме n выбранное простое число).
В нашем примере YA = aXA mod p = 105 mod 19 = 3, то есть . YA = 3.
YB = aXB mod p = 107 mod 19 = 15, то есть, YB = 15.
4. Выполнение процесса обмена открытыми ключами (условно).
Пользователь А получает в свое распоряжение открытый ключ пользователя В YB.
Пользователь B получает в свое распоряжение открытый ключ пользователя A YA.
5. Вычисление каждой стороной значения своего сеансового ключа (эти ключи K будут одинаковыми и используются пользователями как общий сеансовый ключ) на базе полученных открытых ключей противоположных сторон.
Пользователь A вычисляет свой сеансовый секретный ключ K Ї
K = (YB)XA mod p.
Пользователь B вычисляет свой сеансовый секретный ключ K Ї
K = (YA)XB mod p.
При этом обе стороны используют ПРОГАММУ 3 «Быстрое возведение в степень для ab mod n при больших значениях b».
Для нашего примера
Пользователь A: K = (YB)XA mod p = 155mod19 = 2; K= 2.
Пользователь B: K = (YA)XB mod p = 37mod19 = 2; K= 2.
6. Посылка (условно) определенного сообщения пользователем A пользователю B.
При зашифровании секретный сеансовый ключ используется как гамма (зашифрование методом гаммирования), то есть ключ последовательно повторяется столько раз, пока не будет накрыто все передаваемое сообщение. Зашифрование производится с применением поразрядной операции сложения по модулю два.
Сообщение (А) ....З В Е З Д А
Шестнадцатиричный (таблица 2 приложения)
код 866 (A).…... 87 82 85 87 84 80
Двоичный код.1000 0111 1000 0010 1000 0101 1000 0111 1000 0100 1000 0000
Гамма K (A).…1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010
mod 2………0010 1101 0010 1000 0010 1111 0010 1101 0010 1110 0010 1010
Гамма К (B).....1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010
Двоичный код 1000 0111 1000 0010 1000 0101 1000 0111 1000 0100 1000 0000
Шестнадцатиричный
код 866 (B)…..……87 82 85 87 84 80
Сообщение (B) .... З В Е З Д А
7. С целью проверки совместной работы пользователей необходимо расшифрованное пользователем В сообщение переслать (условно) в открытом виде пользователю А.
8. Необходимо такую же работу, одновременно с пользователем А, произвести и пользователю В (условно) согласно п. 1 для передачи другого слова пользователем В пользователю А.
2.2.2 Инструкция по выполнению задания 2
Проанализировать процесс выполнения примера ДХ 1 по приведенному алгоритму. Задание 2 выполняется двумя пользователями взаимосвязанно (условно их, как и в примере, назовем соответственно, пользователями A и B). Задание выполняется поэтапно так, как показано в примере 2.
1. Выбор из таблицы 1 приложения простого числа p. С использованием ПРОГРАММЫ 4 «Вычисление степеней целого числа am по модулю p и целых чисел, принадлежащих показателю (p), первообразных корней по модулю p» определить соответствующий конкретный первообразный корень a (где ap).
2. В соответствии с выбранным значением p определить секретные ключи по условиям XA p и X B p.
3. Вычислить в соответствии с найденным a и конкретным p открытые ключи YA и YB для пользователей А и В на основе их секретных ключей XA и XB. При этом используется ПРОГАММА 3 «Быстрое возведение в степень для ab mod n при больших значениях b»..
4. Выполнение процесса обмена открытыми ключами пользователей по открытой сети (условно).
5. Вычисление каждой стороной значения своего секретного сеансового ключа (эти ключи K будут одинаковыми и используются пользователями как общий сеансовый ключ) на базе полученных открытых ключей противоположных сторон. При этом опять используется ПРОГАММА 3 «Быстрое возведение в степень для ab mod n при больших значениях b».
6. Посылка (условно) определенного короткого однословного сообщения пользователем A пользователю B и, наоборот. При этом необходимо пользоваться соответствующей кодовой таблицей (например, таблица 2 приложения или таблица, применяемая в соответствующем Windows-е).
Если после расшифровки, полученные сообщения будут совподать, то выполненные пользователями работы будут автоматически зачтены.
2.2.3 Общее положение по выполнению задания 2 генерация и обмен секретными ключами по схеме Диффи-Хеллмана между пользователями сети
Как видно, в данной работе значения первообразного корня (а), простого числа (р) и секретных ключей (XА и XВ) соответствующим образом выбираются и вводятся в соответствующие поля ввода окна задания 2. Все, что требуется от студента - рассчитать открытые ключи(YА и YВ) и общий секретный сеансовый ключ К, значения которых затем нужно ввести в соответствующие поля. Для проверки программой расчетов студента необходимо нажать кнопку с надписью «Контроль расчета К». В ходе проверки все верные расчеты будут выведены в большом текстовом поле, которое находится в нижней части экрана.
Если студент ввел неверный ответ, то не будут выполняться преобразования, ему придется ввести новые входные данные.
В случае правильного решения студентом поставленной задачи информация о верности решения будет выведена в большом текстовом поле. В зависимости от того, желает ли студент зашифровывать открытое слово (открытый текст) или расшифровывать зашифрованный текст, он заполняет поля ввода "Слово для зашифрования" или "Зашифрованное слово (текст) для расшифровывания". Далее необходимо нажать кнопку "зашифрование/расшифрование", после чего в текстовом поле "Ход расчетов программы" появятся все действия программы по зашифрованию/расшифрованию. Далее студент может сохранить все расчеты в специиальном файле, нажав кнопку "Сохранить в файле". Студенты могут обмениваться кодами посредством, например, электронной почты, и расшифровывать сообщения друг друга, зная общий секретный сеансовый ключ.
Необходимо все исходные данные и результаты зашифрования и расшифрования сохранить в файле РЕЗУЛЬТАТОВ.
ГЛОССАРИЙ
1. Алгоритм Диффи-Хеллмана. Алгоритм Диффи-Хеллмана основывается на трудностях вычисления дискретных логарифмов. Злоумышленнику могут быть известны величины Q (простое число), (первообразный корень простого числа Q), YA и YB (открытые ключи, соответственно абонентов А и В). Злоумышленнику для определения, например, секретного ключа пользователя В необходимо вычислить XВ = Ind, Q (YB), иначе YВ = XВ mod Q.
2. Асимметричная криптографическая система (система с двумя ключами, схема шифрования с открытым ключом). Отправитель и получатель используют разные ключи. Здесь ключи зашифрования и расшифрования различны и секретность сообщения основана на сложности вычисления ключа по некоторой производной от него информации, которая в открытом виде передается по каналу связи.
3. Закрытый ключ. Это закрытая (секретная) половина криптографической пары, используемая при шифровании с применением открытых ключей. Закрытые ключи обычно используются при расшифровке симметричных ключей сеансов, создании цифровых подписей и расшифровке данных, зашифрованных соответствующим открытым ключом.
4. Индекс b по основанию a, рассматриваемому по модулю p (иначе дискретный логарифм). Ind a,p (b) или показатель степени i, при котором b = aimod p, где 0 i (p-1).
3. Лабораторная работа 3. КриптографиЯ с открытым ключом.
Метод зашифрования с открытым ключом RSA
В этой лабораторной работе определяются параметры преобразования, необходимые для выполнения алгоритма RSA (выбирается соответствующим образом открытый ключ e, вычисляется соответствующий закрытый ключ d как мультипликативное обратное к e). Далее с использованием этих параметров производятся зашифрование открытого текста (конкретного двухразрядного десятичного числа) и расшифрование этого зашифрованного текста.
Работа состоит из трех заданий.
Задание 1. RSA-0 подготовка к выполнению алгоритма зашифрования открытого сообщения открытым ключом RSA-1.
Задание 2. RSA-1 выполнение алгоритма зашифрования открытого сообщения открытым ключом RSA-1.
Задание 3. RSA-2 выполнение алгоритма расшифрования зашифрованного сообщения секретным ключом RSA-1.
3.1 Теория, криптография с открытым ключом. Метод зашифрования с открытым ключом RSA
Алгоритмы шифрования с открытым ключом зависят от двух ключей: одного ключа для зашифрования и другого ключа, связанного с первым, для расшифрования (слайд 3.2). С точки зрения вычислений, нереально определить ключ расшифрования, зная только используемый крипто-графический алгоритм и ключ зашифрования. В некоторых алгоритмах любой из этих ключей может применяться для зашифрования, а другой для расшифрования.
Криптографические системы с открытым ключом зависят от некоторой обратимой математической функции со специальными свойствами. Сложность вычисления такого рода функций может зависеть не линейно от числа битов в ключе, а расти более быстро. Поэтому длина ключа должна быть достаточно большой. Однако чем длиннее ключи, тем больше времени требуется для выполнения процессов зашифрования/расшифрования. Поэтому алгоритмы криптографии с открытым ключом в настоящее время, в основном, применяются в управлении ключами и приложениями цифровой подписи. Однако схема Райвеста-Шамира-Адлемана (RSA) стала единственной получившей широкое признание и практически применяемой схемой шифрования с открытым ключом [1]. Эта схема представляет собой блочный шифр, в котором и открытый текст, и шифрованный текст представляются целыми числами из диапазона от 0 до (n-1) для некоторого n.
В данной лабораторной работе мы изучим этот метод шифрования и алгоритмы вычислений, применяемых при реализации этого метода.
Операции зашифрования открытого текста и расшифрования закрытого текста в RSA состоят из операций возведения большого целого числа в большую целую степень по модулю n.
Обобщенная блок-схема генерации ключей, необходимых для алгоритма RSA приводится на рис. 3.1 (слайд 3.3).
Рис. 3.1. Генерация ключей для RSA
На рис. 3.2 (слайд 3.4) приводится блок-схема алгоритмов зашифрования и расшифрования для RSA.
Рис. 3.2. Блок-схема алгоритмов зашифровки и расшифровки для RSA
3.2 Алгоритм RSA
Далее приводятся два примера, поясняющие работу алгоритма RSA.
Пример RSA-0. Выбор целого e, взаимно простого с (n) и меньшего, чем (n). А также определение такого d, что de = 1 mod (n) и d (n).
Это подготовительный этап для выполнения алгоритма RSA.
Из таблицы 1 приложения выбираем два простых числа p = 7 и q = 17.
Вычисляем n = p q = 7 17 = 119.
Вычисляем (n) = (p-1) (q-1) = 6 16 = 96.
Выбираем e по условию, что gcd (e, (n)) = 1 и 1e(n) Для этого будем пользоваться расширенным алгоритмом Евклида для нахождения наибольшего общего делителя двух чисел, который при определении и уточнении, что таким делителем является 1, выдает и мультипликативное обратное для e по модулю (n).
gcd (d, f) = gcd (e =5, (n) = 96) = 1.
Выполняем алгоритм:
X1 = 1, X2 = 0, X3 = 96.
Y1 = 0, Y2 = 1, Y3 = 5.
Y3 0,
Y3 1.
Q = X3/Y3 = 96/5 = 19.
T1 = X1 - Q Y1 = 1 - 19 0 = 1,
T2 = X2 - Q Y2 = 0 - 19 1 = -19,
T3 = X3 - Q Y3 = 96 - 19 5 = 1.
X1 = Y1 = 0,
X2 = Y2 = 1,
X3 = Y3 = 5.
Y1 = T1 = 1,
Y2 = T2 = -19,
Y3 = T3 = 1.
Соотношения:
f T1 + d T2 = 96 1 + 5 (-19) = 1 = T3,
f X1 + d X2 = 96 0 + 5 1 = 5 = X3,
f Y1 + d Y2 = 96 1 + 5 (-19) = 1 = Y3.
Так как Y3 = 1, то Y3 gcd (5, 96) = 1 наибольший общий делитель.
Тогда Y2 = d-1 mod 96 = -19. Так как Y2 отрицательное целое, то мультипликативное обратное будет 96-19 = 77.
Таким образом, для нашего примера e = 5 и d = 77.
Пример RSA-1: Вычислить ab mod n (см. раздел 1.4. «Алгоритм быстрого возведения в степень для ab mod n при больших значениях b», рис. 1.5. и слайд 7), где a = M = 19, b = e = 5 (открытый ключ) и n = (p q) = 119, С зашифрованный текст.
Иначе
195 mod 119 = C ?
b = 510 = 101, k = 2, c = 0, d = 1, a = 19, n = 119.
1. k 0, k = 2;
c = 2 c = 2 0 = 0;
d = (d d) mod n = (1 1) mod 119 = 1 mod 119 = 1;
bk = b2 = 1;
c = c + 1 = 0 + 1 = 1;
d = (d a) mod n = (1 19) mod 119 = 19 mod 119 = 19 - 19 / 119 119 = 19 - 0 119 = 19.
k = k - 1 = 2 - 1 = 1.
2. k 0, k = 1;
c = 2 c = 2 1 = 2;
d = (d d) mod n = (19 19) mod 119 = 361 mod 119 = 361 - 361 / 119 119 = 361 - 3 119 = = 361 - 357 = 4;
bk = b1 = 0;
k = k - 1 = 1 - 1 = 0.
3. k 0, k = 0;
c = 2 c = 2 2 = 4;
d = (d d) mod n = (4 4) mod 119 = 16 mod 119 = 16 - 16 / 119 119 = 16 - 0 119 = 16;
bk = b0= 1;
c = c + 1 = 4 + 1 = 5;
d = (d a) mod n = (16 19) mod 119 = 304 mod 119 = 304 - 304 / 119 119 = 304 - 2 119 = 66.
k = k - 1 = 0 - 1 = -1.
Ответ: C = 195 mod 119 = 66.
Далее рассмотрим пример для обратного преобразования
Пример RSA-2: Вычислить ab mod n, где a = C = 66, b = d = 77 (закрытый ключ) и n = 119.
Иначе
M = 6677 mod 119 = ?
b = 7710 = 10011012, k = 6, c = 0, d = 1, a = 66, n = 119.
1. k 0, k = 6;
c = 2 c = 2 0 = 0;
d = (d d) mod n = (1 1) mod 119 = 1 mod 119 = 1;
bk = b6 = 1;
c = c + 1 = 0 + 1 = 1;
d = (d a) mod n = (1 66) mod 119 = 66 mod 119 = 66 - 66 / 119 119 = 66 - 0 119 = 66.
k = k - 1 = 6 - 1 = 5.
2. k 0, k = 5; b5 = 0;
c = 2 c = 2 1 = 2;
d = (d d) mod n = (66 66) mod 119 = 4356 mod 119 = 4356 - 4356 /119 119 = 4356 - (36 119) = 4356 - 4284 = 72;
k = k - 1 = 4
bk = b4 = 0;
c = c 1 = 2 2 = 4;
d = (d d) mod n = (72 72) mod 119 = 5184 mod 119 = 5184 - 5184 / 119 119 = 5184 - (43 119) = 5184 - 5117 = 67.
k = k - 1 = 4 - 1 = 3.
3. k 0, k = 3; b3 = 1;
c = 2 c = 2 4 = 8;
d = (d d) mod n = (67 67) mod 119 = 4489 mod 119 = 4489 - 4489 /119 119 = 4489 - (37 119) = 4489 - 4403 = 86;
c = c + 1 = 8 + 1 = 9;
d = (d a) mod n = (86 66) mod 119 = 5676 mod 119 = 5676 - 5676 / 119 119 = 5676 - (47 119) = =5676 - 5593 = 83.
k = k - 1 = 3 - 1 = 2; b2 = 1.
4. k 0, k = 2; b2 = 1;
c = 2 c = 2 9 = 18;
d = (d d) mod n = (83 83) mod 119 = 6889 mod 119 = 6889 - 6889 /119 119 = 6889 - (57 119) = 6889 - 6783 = 106;
c = c + 1 = 18 + 1 = 19;
d = (d a) mod n = (106 66) mod 119 = 6996 mod 119 = 6996 - 6996 / 119 119 = 6996 - (58 119) = 6996 - 6902 = 94.
k = k - 1 = 2 - 1 = 1; b1 = 0.
5. k 0, k = 1; b1 = 0;
c = 2 c = 2 19 = 38;
d = (d d) mod n = (94 94) mod 119 = 8836 mod 119 = 8836 - 8836 /119 119 = 8836 - (74 119) = 8836 - 8806 = 30;
b1 = 0;
6. k 0, k = 0; b0 = 1; c = 2 c = 2 38 = 76;
d = (d d) mod n = (30 30) mod 119 = 900 mod 119 = 900 - 900 /119 119 = 900 - (7 119) = = 900 - 833 = 67;
c = c + 1 = 76 + 1 = 77;
d = (d a) mod n = (67 66) mod 119 = 4422 mod 119 = 4422 - 4422 / 119 119 = 4422 - (37 119) = 4422 - 4403 = 19.
k = k - 1 = 0 - 1 = -1.
Так как k 0, то получен следующий ответ.
Ответ: M = 6677 mod 119 = 19.
3.3 Общее положение по выполнению лабораторной работы. Метод зашифрования RSA
Необходимо выбрать из таблицы 1 приложения новые значения простых чисел p и q, и выполнить все примеры аналогично RSA-0, RSA-1 и RSA-2.
С целью облегчения выполнения заданий вручную (для освоения соответствующих алгоритмов) p и q выбираются двухразрядными. В качестве открытого исходного сообщения берется также двухразрядное десятичное число. Его необходимо зашифровать. В программе предусматривается автоматический контроль правильности.
3.3.1 Задание 1 RSA-0 подготовка для выполнения алгоритма зашифрования открытого сообщения открытым ключом RSA-1
1. Выбираем из таблицы 1 приложения два взаимно простых числа p и q. 2. С использованием вкладки «Лабораторная работа 1, задание 1» испытываем выбранные числа на взаимную простату. Вводим эти числа в поля «Число 1 (d)» и «Число 2 (f)». В качестве ответа должны получить значение наибольшего общего делителя 1. 3. Вводим выбранные числа в поля «Простое число 1 (p)» и «Простое число 2 (q), взаимно простое с числом p» окна RSA-0 данной лабораторной работы. 4. Рассчитываем значение n = p q. Нажав кнопку «Расчет (n)» вычислим (n) = (p-1) (q-1).
5. Для подбора соответствующего значения открытого ключа e (взаимно простого с (n)) используем вкладку «Лабораторная работа 1, задание 1». В окне этой вкладки в поле «Число 1 (d)» вводим выбранное значение e (где 1e(n)), а в поле «Число 2 (f)» вводим значение (n). Так как эти поля уже доступны студенту, то подбор производится относительно легко (подбирается значение e). Подобранное значение e вводится в поле «Значение открытого ключа e, взаимно простое с (n)» окна RSA-0 данной лабораторной работы.
6. Подбираем значение закрытого ключа d, мультипликативного обратного для e по модулю (n) в поле «Значение закрытого ключа d, мультипликативного обратного для e по модулю (n)» в поле RSA-0 данной лабораторной работы. При заполненных полях этого окна в большом среднем поле отражается правильный процесс вычисления и полученный верный ответ (используется кнопка «Проверка корректности»). Правильный ответ получается в результате коррекции ответа (если это необходимо) в процессе подбора. Этим подготовительная работа завершается.
3.3.2 Задание 2 RSA-1 - выполнение алгоритма зашифрования открытого сообщения открытым ключом RSA-1
По результатам RSA-0 заполняются поля «Открытое сообщение (a)», «Открытый ключ (b = e)», «Значение n (n = p q)».
Вычисляется ab mod n и в результате получается соответствующий зашифрованный текст. При этом используется вкладка «Задание 3 лабораторной работы 1». Правильный процесс расчетов отображается в большом поле окна задания RSA-1 данной лабораторной работы.
3.3.3 Задание 3 RSA-2 - выполнение алгоритма расшифрования зашифрованного сообщения секретным ключом RSA-1
Обратный процесс можно проследить в окне RSA-2 данной лабораторной работы. Этот процесс выполняется аналогично процессу RSA-1. Соответствующие ответы и исходные данные фиксируются в МАССИВЕ РЕЗУЛЬТАТОВ.
3.4. Общий алгоритм выполнения лабораторной работы 3
по криптографическим системам с открытым ключом
Рис. 3.3. Общий алгоритм выполнения лабораторной работы
ГЛОССАРИЙ
1. Алгоритм RSA. Алгоритм RSA основан на выражениях со степенями. Эта система основана на трудностях разложения очень больших целых чисел по степеням простых чисел.
2. Канал связи. Естественный или искусственный материальный объект (среда), обеспечивающий передачу сигнала от передатчика к приемнику. Основными каналами распространения информации в настоящее время являются, в первую очередь, Интернет, а также другие специализированные системы государственного и межгосударственного уровня.
В перспективе на эту роль претендуют цифровые информационно-телекоммуникационные сети интегрального обслуживания.
3. Ключ. Это конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования данных, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразований; последовательность символов, управляющая операциями шифрования и дешифрования.
Список утверждений
1. Алгоритмы шифрования с открытым ключом зависят от двух ключей: одного ключа для зашифрования и другого ключа, связанного с первым, для расшифрования. С точки зрения вычислений, нереально определить ключ расшифрования, зная только используемый криптографический алгоритм и ключ зашифрования.
2. c, отличное от нуля, делит a, если a = m c для некоторого m, где c, a и m являются целыми числами. c делит a, если деление выполняется без остатка. Это пишется так: ca. c называют делителем a.
3. Целое число p1 называется простым, если его делителями являются только числа 1 и p.
4. Положительное целое число c является наибольшим общим делителем чисел a и b (НОД, запись gcd (a, b)), если: c является делителем a и b; любой делитель a и b является делителем c. gcd (a, b) = max [k таких, что ka и kb].
5. Числа a и b являются взаимно простыми, если gcd (a, b) = 1.
6. Если a является целым, а z положительным целым, то a mod z определяется как остаток от деления a на z.
7. Два целых числа a и b являются сравнимыми по модулю n, если (a mod n) = (b mod n). Это записывается так: a b mod n.
8. Если gcd (d, f) = 1, то d имеет мультипликативное обратное по модулю f. То есть, для положительного целого числа d f существует такое d -1 f, что d d -1= 1 mod f.
9. [(a1 mod n) (a2 mod n)] mod n = (a1 a2) mod n.
10. Число положительных целых значений, которые меньше n и являются взаимно простыми с n, обозначается через (n) и называется функцией Эйлера. Для простого числа p это будет (p) = = p - 1.
11. Теорема Эйлера утверждает, что для любых взаимно простых чисел a и n
a(n) 1 mod n.
12. Если a и n являются взаимно простыми, то существует, по крайней мере, одно целое число m, удовлетворяющее соотношению am 1 mod n, где m = (n). Для наименьшего из положительных m, при которых выполняется указанное условие, используются названия или порядок числа a по модулю n, или показатель, которому принадлежит a по модулю n, или длина периода последовательности, генерируемой степенями a.
13. Числа, принадлежащие показателю (n), называются первообразными корнями по модулю n.
Заключение
Из всего изложенного следует, что надежная криптографическая система должна удовлетворять таким требованиям:
процедуры зашифровывания и расшифровывания должны быть "прозрачны" для пользователя;
дешифрование закрытой информации должно быть максимально затруднено;
содержание передаваемой информации не должно сказываться на эффективности криптографического алгоритма;
надежность криптозащиты не должна зависеть от содержания в секрете самого алгоритма шифрования (примерами этого являются как алгоритм DES, так и алгоритм ГОСТ 28147-89).
Литература
Подобные документы
Краткие сведения о истории криптографии. Симметричные криптосистемы (системы с секретным ключом) и системы с открытым ключом. Аутентификация и идентификация, электронная цифровая подпись. Управление ключами, их архивирование, хранение и восстановление.
доклад [458,9 K], добавлен 08.11.2013Появление шифров, история эволюции криптографии. Способ приложения знаний особенностей естественного текста для нужд шифрования. Критерии определения естественности. Способ построения алгоритмов симметричного шифрования. Криптосистема с открытым ключом.
реферат [452,2 K], добавлен 31.05.2013Разновидности защиты компьютерной информации. Особенности алгоритмов и шрифтов, применяемых в криптографии. Специфика использования криптосистем с открытым ключом. Структура вредоносного программного обеспечения. Обеспечение безопасности баз данных.
презентация [393,2 K], добавлен 05.04.2012Понятие и история изобретения криптосистемы с открытым ключом. Свойства односторонней функции и сложность раскрытия шифра. Описание алгоритма RSA: шифрование и дешифрование. Возможные атаки, способы взлома, обоснование и практическая реализация RSA.
курсовая работа [45,9 K], добавлен 24.12.2011Принципы криптографии, история ее развития. Шифры с секретным и с открытым ключом. Криптография как оружие, угрозы данным, их раскрытие. Ужесточчение мер в отношении использования криптоалгоритмов. Раскрытие криптосистемы и стойкость системы к раскрытию.
доклад [35,8 K], добавлен 09.11.2009Изучение, освоение на примере симметричных шифров элементы практической криптографии. Использование расширенного алгоритма Евклида для нахождения обратного по модулю числа. Ознакомление с демо-версией программы симметричного шифрования с секретным ключом.
лабораторная работа [97,5 K], добавлен 18.04.2015Особенности шифрования данных, предназначение шифрования. Понятие криптографии как науки, основные задачи. Анализ метода гаммирования, подстановки и метода перестановки. Симметрические методы шифрования с закрытым ключом: достоинства и недостатки.
курсовая работа [564,3 K], добавлен 09.05.2012Актуальность и предыстория проблемы построения систем связи с открытым ключом. Алгоритм кодирования, перевода из десятичного числа в двоичное, быстрого возведения числа в степень, поиска взаимно простых чисел. Дешифрование сообщения по криптоалгоритму.
курсовая работа [140,3 K], добавлен 20.06.2017Обмен информации, защищенной от фальсификаций и незаконных пользователей. Распределение секретных ключей с помощью системы с открытым ключом. Разработка модулей системы генерации ключей и обмена конфиденциальной информацией для группы пользователей.
курсовая работа [2,0 M], добавлен 17.11.2011Основные программы стеганографии. Программно-аппаратные средства криптографической защиты информации с закрытым ключом. Требования к используемым криптографическим средствам за рубежом и в России. Отечественные системы шифрования с открытым ключом.
отчет по практике [64,6 K], добавлен 18.09.2013
