44. Шифрование с открытыми ключами: RSA, системы Эль-Гамаля, системы на основе «проблемы рюкзака».

Шифрование с открытыми ключами

Криптосистема состоит из взаимно однозначного шифрующего преобразования f из множества Р всех возможных элементов открытого текста в множество С всех возможных элементов шифртекста.

По определению, криптосистема с открытым ключом обладает тем свойством, что знание шифрующего преобразования не позволяет по ключу шифрования найти ключ дешифрования, избежав чрезвы­чайно длинных вычислений. Другими словами, шифрующая функция f:P->C легко вычисляется, если ключ шифрования .K(/E) известен, но вычислять значения обратной функции f(\-1):C->P очень сложно.

RSA

Работает криптосистема RSA следующим образом.

Каждый пользователь А выбирает два простых числа p(/A), q(/A) а вслед за этим — случайное число e(/A) которое не имеет об­щих множителей с (p(/A)-1)(q(/A)-1) (случайно целое число е(/_a) между 1 и фи(/n))  Далее, А вычисляет n(/A)=p(/A)q(/A), фи(/n(/A))=n(/A)+1-p(/A)-q(/A) и число, обратное относительно умноже­ния к e(/A) по модулю фи(n(/A)):d(/A)=(\def)e(/A)(\-1)(mod фи(n(/A))). Ключ шифро­вания K(/E,A)=(n(/A),e(/A)) делается открытым, а ключ дешифрования K(/D,A)=(n(/A),d(/A)) -  секретным. Шифрующее преобразование — это отображение Z/n(/A)Z в себя по формуле f(P)=(\-)P(\e(/A))(mod n(/A)). Дешифрующее преобразование — это отображение Z/n(/A)Z в себя по формуле f(\-1)(C)=(\-)C(\d(/A))(mod n(/A)) Cогласно выбору d(/A) эти два отображения взаимно обратны. А именно, последо­вательное применение в любом порядке f и f(\-1) приводит к возведению в степень d(/A)e(/A) Поскольку d(/A)e(/A) дает при делении на фи(n(/A)) остаток 1, это эквивалентно возведению в первую степень.

При выборе р и q пользователь А должен по­заботиться о выполнении ряда условий. Самые важные из них следу­ющие: эти простые числа не должны быть слишком близки друг к другу (например, одно должно быть на несколько десятичных разря­дов длиннее другого), числа р—1 и q—1 должны иметь очень маленький наибольший общий делитель и каждое из них должно иметь хотя бы один большой простой делитель.

Системы Эль-Гамаля

Криптосистема   Эль-Гамаля работает следующим образом. Сначала фиксируется достаточно большое конечное поле F(/q) и элемент gEF(/q)(\*) (желательно, хотя и не обязательно, чтобы он был порождающим). Предположим, что исполь­зуются элементы открытого текста с численными эквивалентами Р в F(/q). Каждый пользователь А выбирает случайно целое число a=a(/A) из диапазона 0<a<q-1. Это секретный ключ дешифрования. Открытым ключом шифрования является элемент g(\a)EF(/q).

Чтобы передать сообщение Р пользователю А, выбирается слу­чайно целое число к и А посылается следующая пара элементов из F(/q):

(g(\k),Pg(\ak))

Вычислить g(\ak) можно, не зная а, просто возведя g(\a) в степень к. Теперь А, зная а, может по этой паре раскрыть Р, возве­дя первый элемент g(\k) в а-ю степень и разделив на результат второй элемент (или, что эквивалентно, возведя g(\k) в степень q-1-a и умножив на второй элемент). Другими словами, послание состоит из замаскированного сообщения (Р «несет маску» g(\ak)) и «ключа», а именно,g(\k) которым можно снять маску (но воспользоваться ключом может лишь тот, кто знает а).

Шифрсистемы на основе "проблемы рюкзака"

"Проблема рюкзака" (или "ранца") может быть сформу­лирована следующим образом. Пусть задано множество нату­ральных чисел A- {α₁,α₂,...,α_η} и натуральное число S. Требуется установить, имеется ли такое подмножество мно­жества А , сумма элементов которого была бы равна S . Эк­вивалентной является следующая формулировка: существует ли   такой   набор   чисел  x(/i)E{0,1}, i<=n  для   которого

SUM(/i=1)(\n)a(/i)x(/i)=S

[Данная проблема получила свое название в связи с тем, что поставленная задача может быть переформулирована также в следующем виде. Имеется набор предметов с извест­ными весами и рюкзак, который может выдержать вес, не превышающий заданной величины. Можно ли выбрать набор предметов для погрузки в рюкзак так, чтобы они в точности имели максимально возможный вес.

"Проблема рюкзака" является весьма сложной, ее реше­ние с полиномиальной сложностью в настоящее время не из­вестно.]

Идея построения системы шифрования на основе про­блемы рюкзака заключается в выделении некоторого под­класса задач об укладке рюкзака, решаемых сравнительно легко, и "маскировки" задач этого класса (с помощью некото­рого преобразования параметров) под общий случай. Пара­метры подкласса определяют секретный ключ, а параметры модифицированной задачи — открытый ключ. В качестве легко решаемой задачи Р.Меркль и М. Хеллман в 1978 г. предложили задачу об укладке "супервозрастающе-го" рюкзака.

Назовем супервозрастающей последовательность нату­ральных чисел (b(/1),b(/2),...,b(/n)), обладающую свойством

b(/i)>SUM(/j=1)(\i-1)b(/j), 2<i<n

Проблема рюкзака для су­первозрастающей последовательности может быть решена с помощью процедуры, состоящей в выполнении следующих шагов:

1.   Положить i = n ;

2.   Если i > 1, то положить х(/_i)  равным 1 и S  равным S –b(/_i), если S>b(/_i), и положить х(/_i), равным 0 в противном случае;

3.   Положить i равным  i — 1 и возвратиться к шагу 2.

В системе, основанной на проблеме рюкзака, величина n является параметром системы.

Для вычисления открытого и соответствующего секрет­ного ключа каждый из абонентов системы осуществляет сле­дующую последовательность действий.

1.   Выбирает   супервозрастающую    последовательность

(b(/₁₎,b(/₂₎,...,b(/_n))  и модуль т такой, что m>SUM(/i=1)(\n)b(/i)

2.   Выбирает случайное число W, 1<W<m-1, такое, что НОД(W,m) = 1.

3.   Выбирает    случайную     перестановку     пи     чисел {1,2,...,n}.

4.   Вычисляет a(/i)=W*b(/пи(i)) mod m для i=(1,n)(\-)

Открытым ключом является набор (a(/₁₎,a(/₂₎,...,a(/_п)), секрет­ным ключом — набор (пи,m,W,(b(/₁₎,..,b(/_n))).

Чтобы зашифровать сообщение М, предназначенное для абонента А , абонент В осуществляет следующие шаги с по­мощью открытого ключа (a(/₁₎,a(/₂₎,...,a(/_η)) абонента А :

1.  Представляет Μ в виде бинарной последовательности

Μ = М(/₁₎М(/₂₎...М(/_n) длины n ;

2.  Вычисляет C=SUM(/i=1)(\n)*a(/i) и направляет его к А .

Абонент А . получив С, вычисляет Η = W(\^-1) С mod m, а затем, решая проблему рюкзака для супервозрастающей по­следовательности, находит числа z(/i)E{0,1} такие, что

H=SUM(/i=1)(\n)z(/i)*b(/i)

Биты последовательности M_i, вычисляются по формуле:

M(/i)=z(/пи(i)), i=(1,n)(\-)

Корректность  проведенной  процедуры   расшифрования вытекает из следующих рассуждений. Поскольку

0<H<m, то H=SUM(/i=1)(\n)M(/i)*b(/пи(i)) и, следовательно, алгоритм

решения проблемы рюкзака действительно находит биты от­крытого текста, переставленные в соответствии с перестанов­кой пи.