Основные определения и теоремы

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

1. Криптографические системы являются стойкими, если опреде­лен­ные их параметры являются простыми числами. Число а называется простым, если оно не имеет целых делителей, кроме единицы. Числа а и b называются взаимно простыми, если их наибольший общий делитель НОД(а, b)=1.

2. Функцией Эйлера φ (n)называется число положительных целых чисел меньших n и взаимно простых с n.

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

- φ (p) = p - 1 " p – простого числа.

- φ (a, b) = φ (а) φ (b) для любых натуральных взаимно простых а и b,

которые позволяют легко вычислить значение функции Эйлера φ (n) с помощью трех арифметических действий, если известно разложение числа n на простые сомножители p и q:

φ (n) = (p-1)(q-1).

3. В RSA используется теорема, которая носит название китайской теоремы об остатках, так как этот результат был известен еще в древнем Китае, где теорема была предложена китайским матема­ти­ком первого века Сун Це. Она утверждает, что любое неотрицательное целое число, не превосходящее произведе­ния модулей, можно однозначно восстановить, если известны его вычеты по этим модулям, и названа так потому, что результатом приведения числа а по модулю n является остаток от деления а на n.

Фактически в RSA используется следствие из этой теоремы, утверж­дающее, что если известно разложение числа n на простые множители n=n₁n₂...n_k, где все n_i попарно взаимно просты, и результат приведения чис­ла x по модулю n_i " i=1,…,k одинаков, то результатом приведения числа x по модулю n будет то же число. То есть " x,a – целых чисел

xº a mod n Û x º a mod n_i " i=1,…,k.

4. Теорема Эйлера. Если n >1, то " х Î Z_n * (х взаимно простого с n), выполняется сравнение

x ^{φ( n )} º 1 mod n.

Следствие. " х < n и взаимно простого с n можно легко вычислить обратный элемент x ^-1 в кольце вычетов Z_n из сравнения

x ^-1 º x ^{φ( n )-1} mod n.

Малая теорема Ферма. " x Î GF(p), х ¹ 0, выполняется сравнение

х^{р- 1} º 1mod p.

Малая теорема Ферма является следствием из теоремы Эйлера, хотя исторически она была доказана раньше, затем Эйлер её обобщил.

Следствие 1: Если p — простое число, то " х, взаимно простого с p:

x^p = х mod p.

Следствие 2:если НОД(е,φ(n))=1 (е - простое относительно φ(n))

 то $ d -целое, такое, что

ed = 1 mod n.

На этих математических фактах основан алгоритм RSA.

 

Алгоpитм RSA

В криптосистеме RSA сообщение m, криптограмма c, открытый ключ K_о, и секретный ключ К_с, принадлежат множеству целых чисел Z_n ={0, 1, 2,..., n -1}. Множество Z_n с операциями сложения и умножения по модулю n образует кольцо.

Модуль n определяется как составное число равное произведению n=p · q двух больших простых чисел p ·и q. Модуль n является открытым параметром алгоритма, а чисела p ·и q — секретными параметрами. То есть множители p и q хранят в секрете, а их произведение n известно всем, кто пользуется данной криптосистемой. Здесь используется односторонняя функция с ловушкой. Зная секретные параметры алгоритма p и q можно легко вычислить функцию Эйлера j (n) по формуле

j (n)=(p -l)(q -1),

тогда как вычисле­ние j (n) только по большому числу n является трудновычислимой задачей.

Функция Эйлера используется в RSA при вычислении ключей.

Открытый ключ К_o = е выбирают случайным образом из множества

Z^* _{j (n)} — чисел меньших j (n) и  взаимно простых с  j (n).

Иначе условие е ÎZ^* _{j (n)} раносильно выполнению двух условий

1< K_о £ j (n), и НОД(К_о, j (n))=1,

которым должено удовлетворять случайно выбранное число К_o = е, чтобы оно могло служить открытым ключом в RSA.

Секретный ключ K_c = d вычисляют так, чтобы выполнялось условие

K_c · К_о = е · d º 1 mod j (n).       (*)

То есть, секретный ключ d является обратным элементом к открытому ключу е в множестве Z_{j (n)}:   d = е ^-1 mod j (n). Решение сравнения (*) мо­жно найти с помощью расширенного алгоритма Евклида.

Заметим, что d и n также взаимно простые числа. Вычисление сек­ретного ключа по открытому является трудновы­числимой задачей, если неизвестны секретные параметры алгоритма p и q, так как при этом трудно вычислить значение функции Эйлера, то есть модуля, по которому приво­дятся результаты операций при вычислении ключей.

При выполнении шифрования и дешифрования вычисления приво­дятся по модулю n. Открытый ключ К_о и модуль n сообщают всем, с кем предполагают обмениваться сообщениями и используют для шифрования данных, а секретный ключ К_с хранят в секрете на стороне получателя и используют для дешифрования.

Преобразование шифрования определяет криптограм­му c через пару (открытый ключ К_о, сообщение m) в соответствии со сле­дующей формулой:

с =Е _Ко (m) = m^Ко mod n.

В качестве алгоритма быстрого вычисления значения c используют ряд последовательных возведений в квадрат целого m и умножений на m с приведением по модулю n.

Обращение функции с = m^Ко mod n, т.е. определение значения m по известным значениям с, К_o и n, является задачей дискретного логарифми­рования и практически неосуществимо при n»2⁵¹².

Однако задачу расшифрования криптограммы с, можно легко решить, используя секретный ключ К_c, по следующей формуле:

m = D _Kc (с) = с^Kc mod n.

Докажем, что в результате возведения криптограммы с в степень секрет­ного ключа К_c получается исходный текст m. Процесс расшифрова­ния можно записать так:

D _Kc (E _Kо (m)) = D _Kc (m ^e) mod n = (m ^e) ^d mod n = m^ed mod n.

По условию выбора ключей

e · d   º1 mod j (n)                      (*)

мы можем написать, что $ k такое что, с учетом свойств j (n):

e · d = k · j (n) +1 = k (p- 1)(q- 1) +1.

Подставим это выражение в показатель степени:

m^ed   º m (m ^{(p- 1)}) ^{k (q- 1)} = (m ^{(q- 1)}) ^{k (p- 1)}.

По малой теореме Ферма (х^р-1 º1 mod p, p – простое):

m^ed mod p º m (1) ^{k (q- 1)} mod p = m mod p.

Аналогично, заменив p на q, получим:

m^ed mod q º m (1) ^{k (p- 1)}  mod q = m mod q.

Далее, по следствию из китайской теоремы об остатках так как n=pq:

m^ed mod n = m mod n,       ч.т.д.

Таким образом, если криптограмму с возвести в степень К_с:

с^Kс mod n = m,

то в результате восстанавливается исходный открытый текст m.

Именно поэтому для вычисления секретного ключа К_c используют соотношение (*).