Асимметричная система шифрования RSA

Криптографическая асимметричная система RSA [8,11,12], получившая название в честь ее авторов (Rivest, Shamir, Adleman) была предложена в 1978 г.

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

Все арифметические функции, выполняемые над натуральными числами, равным образом применимы и к их дополнениям по некоторому модулю р, являющемуся простым числом. Рассматриваемые числа составляют конечное множество 0, 1,…, р-1. Их можно получить сложением, вычитанием и умножением с использованием обычных правил арифметики и приведением результата по mod p. Преимущество использования mod p состоит в том, что деление всегда возможно и дает результат в конечном поле размерности GF(p). В операциях по mod p в уравнении а·х = 1 решение для х является обратной (единственной) величиной от а.

Например, в арифметических действиях по модулю 7 найдем число, об-ратное 3, семь чисел, кратных 3, это 3, 6, 2, 5, 1, 4, 0. Они все различны и одно из них должно быть 1. Единица является пятой в этой последовательности, и, следовательно, числом, обратным 3, является 5. Это один из эффективных и простых алгоритмов нахождения обратного значения.

Теперь опишем систему в упрощенной форме, которая, однако, не обес-печивает достаточной степени защиты. Шифрование и дешифрование выполняются с использованием операций по mod p, и, следовательно, как закрытый, так и открытый тексты состоят из чисел в области 0 ¸ р-1. Модуль р должен быть большим, чтобы зашифрованные блоки имели большой размер, если требуется обеспечить свойство необратимости. Обозначим открытое сообщение через М, а шифрованный текст этого сообщения - через С. Модуль р является частью ключа общего пользования (КОП). Дешифрование может выражаться соотношением С=М^S, в котором показатель степени s также является частью КОП.

Сделаем анализ этого преобразования на соответствие трем требованиям. Первое состоит в том, что для каждого значения М генерируется свое значение С. При использовании модуля, являющегося простым числом, это требование всегда выполняется, поэтому применение указанного преобразования в качестве шифрования приемлемо. Вторым требованием является относительная простота преобразования, с тем чтобы оно не требовало большого объема вычислений. Здесь основную сложность составляют многократные операции с длинными словами, поскольку р является по необходимости большим числом, следовательно, каждое умножение требует большого количества машинных операций. Возведение М в степень s не представляет очень больших трудностей. Мы можем сформировать М², М⁴, М⁸ и т.д. повторением возведения в квадрат с последующим перемножением требуемых степеней, выбирая их с помощью просмотра двоичного представления числа s. Третьим требованием является то, что функция должна быть необратимой, даже когда задано значение s. Простая система не выдерживает этого требования.

Обратная функция, или дешифрование, представлена в форме , где показатель t должен выбираться таким образом, что для всех значений М. Согласно теореме Ферма . Следовательно, величина t является решением уравнения s·t=1 по модулю (р-1). Эта упрощенная схема не может функционировать, как система с КОП, поскольку t простым образом выводится из s, но она может функционировать как криптографическая система традиционного типа, в которой s и t держатся в секрете. Таким образом, мы получаем систему с секретным ключом, но еще не систему с КОП.

Метод, применяемый в системе RSA для более высокой степени защиты, состоит в том, что вместо простого числа в качестве модуля используется произведение двух больших простых чисел, т. е. в этом случае модуль представлен как n = p×q, где p, q – большие простые числа. Метод основан на сложности вычисления множителей p и q по известному n. Число n входит в КОП, т. к. действия выполняются по этому модулю, однако приемник сообщений не раскрывает значений p и q, которые он использует, чтобы получить это сообщение. Простые числа выбираются таким образом, чтобы p-1 и q-1 имели большие множители, чтобы защитить систему от обратного преобразования показательной функции (Например, p-1=2 p^’ , q-1=2 q^’ , где p^’и q^’- простые числа).

Шифрование и дешифрование в системе RSA имеют такую же форму, которая описана, а именно используют возведение открытого текста в степень S при шифровании и возведение шифрованного текста в степень t при дешифровании. Однако вычисление t теперь практически невыполнимо, если неизвестны p и q.

В теории чисел широкое применение находит функция Эйлера, которая обозначается символом f (n) и представляет собой число целых положительных значений, которые меньше n и являются взаимно простыми с n.

Для простого p f (p)= p-1, что следует из теоремы Ферма. В алгоритме шифрования RSA n = p×q, для которого функция Эйлера:

.

Согласно теореме Эйлера для любых взаимно простых чисел a и n

Отсюда, поскольку ,

НОД(s, p-1) и НОД(s, q-1) =1.

Для шифрования нужно выбрать s <f (n) и удовлетворяющее условию НОД(s,(p-1) ·( q-1)) =1 и найти t такое, что

s× t mod(x)=1, где x = (p-1) ·( q-1).

В качестве a возьмем открытый текст M, удовлетворяющий условию M<n, тогда шифрование запишется в виде C=M^s mod n, а дешифрование в виде M=
C ^t mod n = (M^s)^t mod n.

Таким образом, первое возведение в степень s открытого текста M по модулю n обеспечивает шифрование, а повторное возведение результата (С) в степень t по модулю n дает открытый текст M.

Модуль n является частью ключа общего пользования (КОП). Шифрование может выражаться соотношением С=M^s, в котором показатель степени s также является частью КОП.

Для нахождения числа t, которое является секретным ключом функции дешифрования, нам необходимо знать p и q. Тогда оно вычисляется просто. Вначале мы находим x, которое является произведением p-1 и q-1, а затем находим t по алгоритму Евклида. В общем виде он выглядит так

, где a и t – числа, вычисляемые по алгоритму Евклида. Поскольку x и s взаимно простые числа, то . Поэтому , т.е. .

Эффективный и простой алгоритм нахождения мультипликативного обратного описан в работе [9] и выглядит так:

1. (х₁, х₂, х₃): = (1, 0, х); (y₁, y₂, y₃): = (1, 0, х);

2. If y₃=0 return х₃:= НОД (s, x) – нет обратного;

3. If y₃=1 return y₃:= НОД (s, x); y₂= s ^-1 mod(x);

4. ;

5. (T₁, T₂, T₃):= (х₁ - Q× y₁, х₂ - Q× y₂, х₃ - Q× y₃,);

6. (х₁, х₂, х₃): = (y₁, y₂, y₃);

7. (y₁, y₂, y₃): = (T₁, T₂, T₃);

8. Возврат на п. 2.

Пример. Число возможных сообщений возьмём равным М = 2000. Дальнейшие вычисления должны осуществляться по модулю числа, равного произведению двух простых чисел, причем модуль этого числа должен превышать количество возможных сообщений, т.е. 2000. Выберем числа 43 и 47. Данные числа являются простыми, их произведение равно 2021, что больше 2000.

Список простых чисел, не превышающих 6000 приведён в приложении 1.
Чтобы гарантировать однозначность процесса дешифрования, нужно открытый ключ s выбирать таким образом, НОД(s, p-1) и НОД(s, q-1) =1. Выберем открытый ключ s = 41. Действительно, числа 42 и 41, 46 и 41 являются взаимнопростыми.

Для получения закрытого ключа t сначала находим число x изуравнения

x = (p-1) ·( q-1) =42×46 =1932. По алгоритму Евклида получаем НОД(1932, 41) =

1932 = 41×47 + 5,

41 = 5 × 8 + 1.

Согласно обобщённому алгоритму Евклида

1 = 41 - 5 × 8 = 41 - 8×(1932 - 41×47) = 377 × 41 - 1932 × 8.

Отсюда величина t = 377.

Осуществим шифрование и дешифрование сообщения с помощью полученных ключей.

Для шифрования возьмем открытый текст M=12. Закрытый текст С=M⁴¹=12⁴¹ mod 2021. Для вычисления данного выражения представим 41 в двочном коде: 101001= 2⁵+2³+2⁰, что даёт следующий ряд остатков: 12, 1820, 361. Теперь вычислим C:

С=(12*1820*361) mod 2021=7884240 mod 2021=319.

Теперь выполним дешифрование сообщения. Возьмем C=319. Открытый текст равен M=C³⁷⁷ mod 2021=319³⁷⁷ mod 2021. Для вычисления данного выражения представим 377 в двоичном коде: 101111001= 2⁸+2⁶+2⁵+ 2⁴+2³+2⁰, что даёт следующий ряд остатков: 319, 685, 353, 1328, 1272, 1303. Теперь вычислим M:

M=(319*685*353*1328*1272*1303)mod 2021= 12.

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