Алгоритм криптографической системы RSA (Райвест-Шамир-Адлеман)

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

К_О – открытый ключ;

К_З – закрытый (секретный) ключ;

P и Q – случайные большие простые числа;

N – модуль системы вычислений;

φ(N) – функция Эйлера.

Закрытыми (секретными) параметрами в криптографической системе RSA являются параметры К_З; Р; Q; φ(N), значения этих параметров хранятся персональных компьютеров абонентов в секрете (при необходимости как правило на съемных носителях) и никогда никому не передаются.

Открытыми параметрами системы RSA являются К_О; N, которые передаются всем абонентам корпоративной системы в открытом виде и по открытым каналам теледоступа. Открытая комбинация {K_O; N} служит для формирования криптограммы открытого текста (шифрования) абонента-отправителя, закрытый ключ-К_З и значение модуля N служат для распознавания принятой криптограммы и восстановления переданного сообщения.

Условно примем, что абонент А является отправителем зашифрованного по алгоритму RSA электронного сообщения для абонента-получателя В. Рассмотрим процесс алгоритмизации и организации криптографической системы обмена зашифрованными сообщениями на простом примере, когда параметры P и Q будут являться простыми числами двузначными по размеру. В практически применяемых криптографических системах значения этих параметров составляют более 100 десятичных знаков. Функциональное построение криптографической системы (Рис.1) и алгоритм ее функционирования изначально целесообразно рассмотреть со стороны абонента-получателя, т.е. абонента В. При инсталляции криптографической системы c использованием алгоритма RSA многие процессы выполняются автоматически и незаметны для участников сеанса обмена закриптографированными электронными сообщениями. Однако, для пояснения процессов шифрования открытых исходных сообщений (формирования криптограмм) и дешифрования принимаемых закриптографированных сообщений приведем полное описание всех процессов алгоритмизации.

Действия абонента В – абонента получателя закриптгорафированного (зашифрованного) сообщения.

1. Абонент В на своем компьютере задает два простых числа P и Q (для примера рассматриваются простые двузначные числа, на практике эти числа имеют разрядность более 100 десятичных знаков):

примем Р = 41; Q =37.

2. Вычисляет значение модуля N = P * Q = 41 * 37 = 1517.

3. Вычисляет значение функции Эйлера для полученного значения модуля N; функция Эйлера для двух простых чисел, в частности для выбранных значений P и Q определяется как: φ(N) = (P - 1)*(Q – 1) = 40 * 36 = 1440.

Функция Эйлера указывает, сколько во множестве чисел от 1 до N есть чисел взаимно простых с N, т.е. НОД (К_О, φ(N)) = 1. Это определение необходимо для случайного выбора значения открытого ключа К_ОВ из подмножества, определяемого численным значением функции Эйлера.

4. После вычисления значения функции Эйлера φ(N) случайным образом из полученного подмножества от 1 до φ(N) в качестве открытого ключа К_ОВ выбирается число, удовлетворяющее условиям:

1 ≤ К_ОВ ≤ φ(N); НОД (К_ОВ; φ(N)) = 1, т.е. это значение выбирается из указанного множества и в то же время должно быть взаимно простым с численным значением функции Эйлера. Для примера примем К_ОВ = 379.

5. После случайного выбора значения открытого ключа производится вычисление закрытого (секретного) ключа К_ЗВ для абонента В по заданному значению открытого ключа К_ОВ = 379, применяя для этого расширенный алгоритм Евклида при решении сравнения К_ЗВ = К_ОВ^-1 (mod φ(N)), т.е. значение закрытого ключа К_ЗВ в алгоритме RSA является обратной величиной К_ОВ в модулярной алгебре, а т.к. число К_ОВ и численное значение функции Эйлера взаимнопросты, то инверсия значения открытого ключа определяется из следующего соотношения К_ЗВ =К_ОВ^{(φ(N) – 1)} mod φ(N). В рассматриваемом примере это значение закрытого (секретного) ключа определяется как:

К_ЗВ =К_ОВ^{(φ(N) – 1)} mod φ(N) = 379¹⁴³⁹ mod 1440 = 19 mod 1440 ≡ 19.

Таким образом, со стороны абонента В была сформирована система криптографической защиты информации по алгоритму RSA, сформированы закрытые компоненты этой системы, которые хранятся в секрете у абонента В (К_ЗВ; Р; Q; φ(N)), а открытые компоненты (N; К_ОВ), которые являются ключом шифрования открытых сообщений абонент В по открытому каналу пересылает абоненту А для шифрования открытых сообщений для абонента В.

Действия абонента А по формированию криптограмм открытых сообщений для абонента В.

1. Свое открытое сообщение, предназначенное для криптографической защиты (шифрования) и передачи криптограммы по открытым каналам теледоступа от абонента А для абонента В, абонент А представляет в виде целых чисел в соответствии с таблицей перевода (например Windows-кодировка). Для примера произведено шифрование слова «Криптон»:

К→171; р→209; и→201; п→208; т →211; о→207; н→206.

Таким образом, слово «Криптон» в цифровой форме по основанию десять в соответствии с выбранной таблицей кодировки будет иметь следующее отображение:

Криптон → 171; 209; 201; 208; 211; 207; 206.

Здесь необходимо дать определение понятию «Кодирование сообщения». В соответствии с терминологией сборника рекомендуемых терминов «Теория передачи информации» Академии наук СССР под кодированием понимается «Преобразование дискретного сообщения в дискретный сигнал, осуществляемое по определенному правилу» или, в соответствии со словарем терминов и определений в области информационной безопасности под кодированием понимается: «Установление соответствия между элементом данных и совокупностью символов, называемой кодовой комбинацией, словом кода». В этом случае под дискретным сообщением понимается множество букв исходного открытого текста, а под дискретным сигналом отображение каждой буквы естественного алфавита в виде соответствующего кода (в рассматриваемом примере отображение символа алфавита в цифру десятичной системы счисления). Следовательно, сообщение М представляется как М = {M_i} = {M₁; М₂; М₃; … М_i}, где: M₁=171; М₂=209; М₃=201; М₄=208; М₅=211; М₆=207; М₇=206}.

2. После преобразования элементов семантического алфавита в цифровое десятичное отображение абонент А производит формирование его криптограммы (шифрование), используя для этого открытый ключ К_ОВ=379 и значение модуля N=1517, полученные в открытом виде по открытым каналам теледоступа от абонента В, в соответствии со следующей зависимостью:

С_i = mod N = M_i³⁷⁹ mod1517.

После выполнения операции возведения числа М_i в степень по модулю получают криптографические значения элементов открытого сообщения для абонента В:

C₁ = M₁³⁷⁹ mod 1517 = 171³⁷⁹ mod 1517 = 199 mod 1517 → 199;

C₂ = M₂³⁷⁹ mod 1517 = 209³⁷⁹ mod 1517 = 605 mod 1517 → 605;

C₃ = M₃³⁷⁹ mod 1517 = 201³⁷⁹ mod 1517 = 830 mod 1517 → 830;

C₄ = M₄³⁷⁹ mod 1517 = 208³⁷⁹ mod 1517 = 273 mod 1517 → 273;

C₅ = M₅³⁷⁹ mod 1517 = 211³⁷⁹ mod 1517 = 1469 mod 1517 → 1469;

C₆ = M₆³⁷⁹ mod 1517 = 207³⁷⁹ mod 1517 = 718 mod 1517 → 718;

C₇ = M₇³⁷⁹ mod 1517 = 206³⁷⁹ mod 1517 = 206 mod 1517 → 206.

После реализации операции возведения чисел в степень по модулю составляется криптограмма сообщения М, предназначенная для передачи от абонента А к абоненту В. Эта криптограмма может быть расшифрована только с помощью соответствующего закрытого (секретного) ключа К_ЗВ, который хранится в секрете у абонента-получателя зашифрованного сообщения В, и эта криптограмма недоступна для распознавания всеми другими абонентами и несанкционированными пользователями, имеющими доступ к корпоративной телекоммуникационной системе.

C={C_i}={C₁; С₂; С₃; С₄; С₅; С₆; С₇}={199; 605; 830; 273; 1469; 718; 206}→

→ ж; j; S; P; n; М; н.

Действия абонента В по приему и расшифровки криптограммы «С», полученной от абонента А.

3. Абонент В по сетевым каналам телекоммуникаций принимает криптограмму «С», зашифрованную его открытым ключом К_ОВ, от абонента А. В этом случае абонент В является санкционированным пользователем, который имеет специальный закрытый (секретный) ключ К_ЗВ, непосредственно связанный с открытым ключом шифрования К_ОВ. С помощью закрытого ключа К_ЗВ абонент В расшифровывает принятую криптограмму «С», полученную от абонента А, следующим образом:

M_i = mod N = C_i¹⁹ mod 1517,

где: M_i – элемент расшифрованного текста;

C_i – криптограмма элемента открытого текста.

В соответствии с формулой вычисления элемента открытого текста из элемента криптограммы с помощью закрытого (секретного) К_ЗВ ключа абонента В дешифрование производится путем возведения в степень числа по модулю:

М₁ = C₁¹⁹ mod 1517 = 199¹⁹ mod 1517 = 171 mod 1517 → 171 → К

M₂ = C₂¹⁹ mod 1517 = 605¹⁹ mod 1517 = 209 mod 1517 → 209 → р

M₃ = C₃¹⁹ mod 1517 = 830¹⁹ mod 1517 = 201 mod 1517 → 201 → и

M₄ = C₄¹⁹ mod 1517 = 273¹⁹ mod 1517 = 208 mod 1517 → 208 → п

M₅ = C₅¹⁹ mod 1517 = 1469¹⁹ mod 1517 = 211 mod 1517 → 211 → т

M₆ = C₆¹⁹ mod 1517 = 718¹⁹ mod 1517 = 207 mod 1517 → 207 → о

M₇ = C₇¹⁹ mod 1517 = 206¹⁹ mod 1517 = 206 mod 1517 → 209 → н

Таким образом, на стороне абонента В восстанавливается открытый текст из принятой криптограммы от абонента А:

М = М₁ M₂ M₃ M₄ M₅ M₆ M₇ → 171;209;201;208;211;207;206 →

→ К р и п т о н.

Поиск по сайту: