Кодирование и шифрование информации в радиоэлектронных системах передачи информации. Часть 2. Шифрование

1.Преобразование исходного текста должно быть необратимым и исключать его восстановление на основе открытого ключа.

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

Алгоритмы шифрования с открытым ключом получили широкое распространение в

современных информационных системах. Их используют в следующих основных

напрвлениях:

1.Как самостоятельные средства защиты передаваемых и хранимых данных.

2.Как средства для распределения криптографических ключей. Алгоритмы асимметричных крипосистем более трудоемки, чем традиционные криптосистемы.

Поэтому часто на практике имеет смысл с помощью асимметричных крипосистем распределять ключи, объем которых незначителен. А потом с помощью менее трудоемких симметричных алгоритмов осуществлять обмен большими информационными потоками.

3.Как средства аутентификации пользователей информационных систем, в том числе для решения проблемы электронной подписи.

4.Как средства для построения сложных криптографических протоколов для решения различных задач защиты инфомации в современных информационных системах.

Алгебраическая обобщенная модель шифра

Ранее мы рассматривали алгебраическую модель шифра К.Шеннона как трехосновную универсальную алгебру А=(М,К,С,Е), где

M - множество открытых текстов,

К - множество ключей,

C - множество криптограмм и

Е – инъективная (взаимно однозначная) функция шифрования:

Еk: МхК С Ek(m)=c, где mM, kK, cC.

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

251

Шифром зашифрования (алгеброй зашифрования) назовем алгебру

Аш=(М, Мс, Кш С, Сс, Е),

где

множество Мс М трактуется как подмножество всех содержательных текстов из множества «открытых текстов» M.

функция шифрования Е осуществляет отображение МхКш на С:

Е: МхКш С, Ек(m)=c,

то есть является сюрьективной, причем k Кш отображение Еk(m) инъективно (образы двух различных элементов различны), а множество Сс состоит из шифрограмм, которые могут быть получены в результате шифрования содержательных текстов: Сс =Е(McхKш), то есть результатов шифрования тех открытых текстов m, для которых определено значение Еk(m) для всех ключей шифра k Кш.

Введение подмножества Мс М как множества содержательных текстов позволяет корректно вводить критерии на содержательные тексты.

Таким образом, шифр зашифрования есть некоторое уточнение модели шифра Шеннона А=(М,Кш,С,Е).

Шифром расшифрования (алгеброй расшифрования) для Аш назовем алгебру Ар=(Мр, Кр, Ср, D), где

CСр и введение множества Cp — шифртекстов «правильных» сообщений (а

точнее, Cp\C — множества искаженных шифртекстов) обеспечивает возможность описания реакции приемной стороны на поступление искаженного шифрованного сообщения cpC;

М Мр, и введение множества Мp\М обеспечивает возможность описания результата расшифрования приемной стороной искаженного шифрованного сообщения cpC;

функция дешифрования D- сюрьективное отображение

D:Cpx Кр Мр, Dk(с)= m,

для которого выполняются следующие условия:

1)существует биекция f: Кш Кр;

2)для любых mM, k Кш из условия Еk(m)=c вытекает

D(c,f (k))=m.

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

252

Отметим, что в определении шифра расшифрования не содержится требований инъективности функции f по переменной k Kp.

Алгебраической обобщенной моделью шифра назовем тройку

( Аш,Ар, f ).

К положительным свойствам этой модели относится возможность моделирования шифров как с симметричным, так и с асимметричным ключом.

При этом учитываются следующие соображения:

ключ kш Кш несекретен, а ключ kр=f (kш)Kp является секретным;

определение значения k связано с решением сложных проблем;

синтез пар ключей (kш , kр) проводится достаточно просто.

Заметим, что здесь проявляется возможность классификации шифров по параметру сложности вычисления значения f (kш) ключа расшифрования, что определяет основной параметр криптографической стойкости шифров с ассиметричным ключом.

Односторонние функции

Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных или односторонних функций. Последнее название было дано по ассоциации с односторонним движением, когда легко проехать в одну сторону и нельзя в другую. При этом в криптографии, как в жизни, «нельзя» не означает «невозможно ни при каких условиях», но говорит о том, что это сопряжено с серьезными трудностями.

Определение. Функция f: Х У называется односторонней (oneway function), если существует эффективный алгоритм для вычисления f(x) x, но не существует эффективного алгоритма для вычисления хотя бы одного элемента прообраза f -1(у).

Никто не знает, существуют ли вообще односторонние функции. Основным критерием отнесения функции f к классу односторонних или необратимых является отсутствие эффективных с вычислительной точки зрения алгоритмов обратного преобразования Y X.

В криптографии под необpатимостью понимается не теоретическая необратимость функции, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства за заданный интервал времени. Таким образом,

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

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

253

1.Разложение больших целых чисел на простые множители.

2.Вычисление логарифма в конечном поле.

3.Вычисление корней алгебраических уравнений.

Факторизация

В качестве первого примера однонаправленной функции рассмотрим целочисленное умножение. Прямая задача — вычисление произведения двух очень больших целых чисел р и q, т.е. нахождение значения n=p·q, является относительно несложной задачей.

Обратная задача, называемая задачей факторизации, - разложение на множители большого целого числа, т.е. нахождение делителей p и q большого целого числа

n = p·q,

является практически неразрешимой задачей при достаточно больших значениях n. По современным оценкам теории чисел при целом n2664 и p q для разложения числа n по-

требуется около 1023 операций, т.е. задача практически неразрешима на современных ЭВМ.

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

р+1 являются «гладкими», т. е. имеют только малые простые делители.

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

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

Дискретный логарифм

Другой пример однонаправленной функции — это модульная экспонента с фиксированными основанием и модулем. Пусть а и n - целые числа, такие, что 1 a n.

Тогда модульная экспонента с основанием a по модулю n представляет собой функцию y = ax mod n,

где х – целое число. Естественно записать х = loga (у).

Задачу обращения этой функции в множестве целых чисел называют задачей нахождения дискретного логарифма.

Определение. Число х называют дискретным логарифмом числа y по основанию a и

модулю n, если для всех а Zn найдется такое целое y, что y = ax mod n.

Вычисление дискретных логарифмов (когда заданы a, y и n) примерно такая же труднорешаемая задача, как и разложение на множители.

254

Определение. Односторонняя функция f: X Y называется односторонней функцией с ловушкой, если f -1(у) можно вычислить за полиномиальное время, имея некоторую дополнительную информацию, т. е. существует функция g(у,t), вычислимая за полиномиальное время и такая, что g(y,t) = f -1(у) для некоторой ловушки t.

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

качестве примера однонаправленной функции с "потайным ходом" можно привести использование функции Эйлера в криптосистеме RSA.

Криптосистема RSA

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

году и получила название в честь ее создателей: Рональда Ривеста (в настоящее вpемя он воз-

главляет компанию RSA Data Security), Ади Шамира и Леонарда Эйдельмана.

В настоящее время RSA является наиболее распространенной криптосистемой с открытым ключом — стандартом де-факто для многих криптографических прложений.

Статус де-факто послужил причиной включения криптосистемы RSA в принятые ранее криптографические стандарты, например в финансовые стандарты США и Франции,

австралийский стандарт управления ключами и многие другие. Криптосистема RSA

применяется в различных протоколах Internet. В криптографические стандарты,

действующие на территории России, RSA не входит, что осложняет ее применение с точки зрения правовых норм. Тем не менее, выбор этой криптосистемы признается оправданным отечественными авторами [8].

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

Надежность алгоритма основывается на трудновычислимых задачах факторизации

(разложения на множители) больших чисел и вычисления дискретных логарифмов.

Определения и теоремы из алгебры, использованные при создании данной криптосистемы рассмотрены в приложении. Приведем здесь только основные утверждения.

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

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

взаимно простых с n.

255

Вычисление функции Эйлера φ(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=n1n2...nk, где все ni попарно взаимно просты, и результат приведения числа x по модулю ni i=1,…,k одинаков, то результатом приведения числа x по модулю n будет то же число. То есть x,a – целых чисел

x a mod n x a mod ni i=1,…,k.

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

xφ(n) 1 mod n.

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

кольце вычетов Zn из сравнения

x-1 xφ(n)-1 mod n.

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

хр-1 1 mod p.

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

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

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

то d-целое, такое, что ed = 1 mod n.

256

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

Алгоpитм RSA

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

операциями сложения и умножения по модулю n образует кольцо.

Модуль n определяется как составное число равное произведению n=p·q двух больших простых чисел p·и q. Модуль n является открытым параметром алгоритма, а чисела p·и q —

секретными параметрами. То есть множители p и q хранят в секрете, а их произведение n

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

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

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

задачей.

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

Открытый ключ Кo = е выбирают случайным образом из множества Z* (n) — чисел меньших (n) и взаимно простых с (n).

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

1<Kо(n), и НОД(Ко, (n))=1,

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

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

Kc · Ко = е · d 1 mod (n). (*)

То есть, секретный ключ d является обратным элементом к открытому ключу е в

множестве Z (n): d = е -1 mod (n). Решение сравнения (*) можно найти с помощью расширенного алгоритма Евклида.

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

При выполнении шифрования и дешифрования вычисления приводятся по модулю n.

Открытый ключ Ко и модуль n сообщают всем, с кем предполагают обмениваться

257

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

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

сообщение m) в соответствии со следующей формулой:

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

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

Обращение функции с = mКо mod n, т.е. определение значения m по известным значениям

с, Кo и n, является задачей дискретного логарифмирования и практически неосуществимо при n2512.

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

m = DKc (с) = сKc mod n.

Докажем, что в результате возведения криптограммы с в степень секретного ключа Кc

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

DKc(EKо(m)) = DKc(me) mod n= (me)d mod n= med mod n.

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

e · d 1 mod (n) (*)

мы можем написать, что k такое что, с учетом свойств (n) : e·d = k ·(n) +1 = k (p-1)(q-1) +1.

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

med m (m (p-1)) k (q-1) = (m(q-1))k (p-1).

По малой теореме Ферма (хр-1 1 mod p, p – простое): med mod p m (1) k (q-1) mod p = m mod p.

Аналогично, заменив p на q, получим: med mod q m (1) k (p-1) mod q = m mod q.

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

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

сKс mod n = m,

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

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

258

Процедуры шифрования и расшифрования в криптосистеме RSA

В реальных системах алгоритм RSA реализуется следующим образом. Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде,

используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В - в роли получателя. Криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В, так как в этом случае не будет необходимости в передаче секретного ключа. Рассмотрим последовательность действий

пользователя В и пользователя А.

Формирование критпосистемы ( на строне получателя информации) состоит в выборе

параметров алгоритма и вычислении пары ключей:

1. Пользователь В выбирает два больших простых числа p и q. Это секретные

параметры алгоритма, они хранятся в секрете на стороне получатателя.

2. Пользователь В вычисляет значение модуля n криптосистемы как результат умножения первых двух чисел:

n = р·q.

Это общедоступный параметр криптосистемы. Иногда его включают в открытый ключ.

3. Пользователь В, зная секретные параметры алгоритма p и q, вычисляет функцию Эйлера:

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

и выбирает случайным образом простое число e как значение открытого ключа Ко с

учетом выполнения условий:

Ко< (n) и НОД(Ко, (n))=1.

4. Пользователь В вычисляет значение секретного ключа Кс = d при решении сравнения

Кс Ко-1 mod (n).

Для вычисления обратного элемента в кольце Z (n) используют частный режим работы расширенного алгоритма Евклида для определения НОД. Это можно осуществить, так как получатель В знает пару простых чисел (p,q) и может легко найти (n). Заметим, что Kc и n

должны быть взаимно простыми.

(В принципе открытый и закрытый ключи можно поменять местами, главное, чтобы выполнялось соотношение e·d 1 mod (n) ).

5. Пользователь В пересылает пользователю А пару чисел {e,n} по незащищенному каналу.

Шифрование информации ( на строне отправителя). Если пользователь А хочет передать пользователю В сообщение m, он выполняет следующие шаги.

259

6.Пользователь А разбивает исходный открытый текст m на блоки mi, i=1,…,N, каждый из которых может быть представлен в виде числа меньшего n

mi {0, 1, 2, ... , n-1}.

7.Пользователь А шифрует текст, представленный в виде последовательности чисел mi с

помощью ключа Ko = е по формуле ci = miе mod n

и отправляет криптограмму c1, … ,ci . пользователю В.

Дешифрование информации (на строне получателя):

8. Пользователь В расшифровывает принятую криптограмму c1, … ,ci, используя секретный ключ Кc=d, по формуле

mi = cid mod n.

В результате будет получена последовательность чисел, которые представляют собой исходное сообщение m.

Таким образом, когда получатель В, который создает криптосистему, он защищает следующие параметры:

1.секретный ключ Кс;

2.пару чисел (p, q);

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

После шифрования сообщение невозможно раскрыть с помощью открытого ключа. Владелец же закрытого ключа без труда может расшифровать принятое сообщение. Противнику же длятого, чтобы определить значение секретного ключа Кc нужно суметь разложить число n

на множители р и q, чтобы узнать бы "потайной ход" и вычислить значение функции Эйлера как (n) = (p-1) (q-1).

Пример. Рассмотрим небольшой пример, иллюстрирующий применение алгоритма

RSA. Зашифруем сообщение "САВ". Для простоты будем использовать маленькие числа

(на практике применяются гораздо большие).

1.Выберем p=3 и q=11.

2.Определим n=3·11=33.

3.Найдем (n) = (p-1)(q-1)= 2·10 = 20.

4.Выберем в качестве секретного ключа d произвольное число взаимно простое с

(n)=20, например, d=3.

5. Выберем открытый ключ е = 7. В качестве такого числа может быть взято

любое число, для которого удовлетворяется соотношение

260