- •Часть 1 Шифрование с помощью таблицы Виженера
- •Часть 2 Расшифровать криптограмму с использованием открытого ключа методом rsa
- •Часть 3 Сформировать электронную подпись с использованием открытого ключа методом rsa
- •Методика шифрования с помощью таблицы виженера
- •Методика шифрования с помощью открытого ключа. Разъяснения алгоритма шифрования rsa
- •Описание криптосистемы с открытым ключом, на примере алгоритма, используемого в системе rsa
- •Электронная цифровая подпись с использованием открытого ключа
- •Свойства и вычисление функции Эйлера
Методика шифрования с помощью открытого ключа. Разъяснения алгоритма шифрования rsa
В 1976 году американцы Уитфилд Диффи и Мартин Хеллман (Diffi W., Hellman М.) – два инженера-электрика из Станфордского университета, а также Рольф Меркль, бывшие в то время студенты Калифорнийского университета, совершили замечательный прорыв в построении криптосистем. Их работа частично финансировалась Национальным научным фондом, и ее результаты были опубликованы Диффи и Хеллманом в статье «Новые направления в криптографии». В этой статье был предложен новый принцип и строения криптосистем, не требующий не только передачи ключа, принимающему сообщение, но даже сохранения в тайне метода шифрования. Эти шифры позволяют легко зашифровывать и дешифровать текст и их можно использовать многократно.
Описание криптосистемы с открытым ключом, на примере алгоритма, используемого в системе rsa
Пусть абоненты А и В решили наладить между собой секретную переписку с открытым ключом. Тогда каждый из них, независимо от другого, выбирает два больших простых числа и , находит их произведение , которое для заданного алфавита должно удовлетворять условию (M – количество используемых знаков алфавита), функцию Эйлера от этого произведения и выбирает случайное число меньшее этого вычисленного значения функции Эйлера и взаимно простое с ним. Взаимно простыми числами называются такие числа, у которых общий делитель равен «1», математическая запись, означающая, что числах а и b взаимно простые записывается: , пример взаимно простых чисел: , .
Таким образом:
;
Функция Эйлера при известных простых числах и вычисляется легко , а в случае, если известно только их произведение , эта функция вычисляется путем перебора всех простых чисел не превышающих . Подробнее о функции Эйлера изложено в следующем параграфе.
З атем печатается телефонная книга, доступная всем желающим, которая имеет вид (табл. 2). В данной книге – произведение двух простых чисел, известных только корреспонденту А, а - открытый ключ, доступный каждому, кто хочет передать секретное сообщение абоненту А, - произведение двух простых чисел, известных только абоненту В, b - открытый ключ, доступный каждому, кто хочет передать сообщение абоненту B.
Каждый из абонентов находит свой секретный ключ из сравнений:
и ,
при этом значения этих ключей и должны удовлетворять условиям:
и .
Сравнение: означает, что произведение чисел должно делиться на по с остатком, равным «1». Например: , , путем перебора произведений при различных значениях и т.д. находим, что при отношение делится с остатком равным «1»: . Таких чисел может быть бесконечное множество и их можно вычислить, пользуясь выражением , для тех значений , при которых данное отношение делится без остатка по . В приятой математической символике это можно записать: .
Таким образом формируется полный комплект открытых и закрытых ключей для корреспондентов А и В (табл. 3):
Таблица 3
Абонент |
Открытый ключ |
Закрытый ключ |
А |
|
|
В |
|
|
Процесс шифрования и расшифровывания передаваемых сообщений
Пусть абонент B решает послать сообщение m абоненту A:
при этом для передачи сообщения требуется, чтобы .
Абонент B шифрует сообщение т открытым ключом абонента А, который есть в телефонной книге, и находит
, .
Абонент А расшифровывает это сообщение своим секретным ключом:
, и получает .
Доказательство:
и так как , следовательно, . Но так как и , то .
Пример. Пусть и – простые числа выбранные абонентом A (пример простых чисел показан в табл. П.4, приложения); и – простые числа абонента В; и – произведения этих чисел соответственно, , , выберем значения открытого ключа из условий: , : а = 7 и , : b = 9 – случайные числа для абонентов А и В соответственно, и наконец, пусть телефонная книга, доступная всем желающим, имеет вид:
А: 161, 7.
В: 187, 9.
В этой книге первое число – произведение двух простых, известных только одному абоненту, второе число – открытый ключ, доступный каждому, кто хочет передать секретное сообщение этому абоненту. Каждый из абонентов находит свой секретный ключ из сравнений:
, ;
, .
Таким образом, они находят собственные секретные ключи и соответственно. Пусть теперь абонент B решает послать секретное сообщение: «МИР» абоненту А. По таблице соответствия букв русского алфавита (см. табл. П.1, приложения) преобразуем сообщение в цифровой код: .
Стоит задача передать это сообщение абоненту А, .
Тогда абонент B шифрует это сообщение (числа соответствующих букв) открытым ключом абонента A :
; ; .
Таким образом, . Получив зашифрованное сообщение абонент А расшифровывает это сообщение своим секретным ключом – : ; ; , следовательно, , после чего по таблице соответствия букв русского алфавита (см. табл. П.2) получим переданный открытый текст: «МИР».
В данном примере использовалась операция возвышения числа в степень по модулю другого числа . Данная операция выполняется следующим образом: производиться обычное возведение в степень , полученное число делят на модуль и выделяется остаток, которому и равно данное возвышение в степень по модулю с.
Рассмотрим пример: . Пусть , и . Возведем , далее разделим полученное число на 60: , следовательно, . Применение такого метода вычисления возможно при малых значениях и . В случае больших чисел, даже двухзначных, обычное возведение в степень затруднено в силу ограниченности вычислительных возможностей калькуляторов или персональных компьютеров. В этих ситуациях следует производить вычисление поэтапно как показано ниже, например: можно вычислить: ; ; , , откуда окончательно получим .