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

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

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

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

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

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

Е _k: МхК ® С  E _k ( m )= c, где m ÎM, k ÎK, c ÎC.

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

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

А_ш=(М, М_с, К_ш С, С_с, Е), где

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

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

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

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

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

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

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

А_р=(М_р, К_р, С_р, D), где

Ø CÍС_р и введение множества C _p — шифртекстов «правильных» сообщений (а точнее, C _p \C — множества искаженных шифртекстов) обеспечивает возможность описания реакции приемной стороны на поступление искаженного шифрованного сообщения c _p ÏC;

Ø МÍМ_р, и введение множества М _p \М обеспечивает возможность описания результата расшифрования приемной стороной искаженного шифрованного сообщения c _p ÏC;

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

D: C_px К_р® М_р, D _k ( с )= m,

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

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

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

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

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

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

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

(А_ш,А_р, f).

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

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

Ø ключ k _шÎК_ш  несекретен, а ключ k _р= f (k _ш)ÎK _p является секрет­ным;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

n = p · q,

является практически неразрешимой задачей при достаточно больших значениях n. По современным оценкам теории чисел при целом n»2⁶⁶⁴ и p»q для разложения числа n по­требуется около 10²³ операций, т.е. задача практически неразрешима на современных ЭВМ.

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

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

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

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

y = a^x mod n,

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

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

Определение. Число х называют дискретным логарифмом числа y по основанию a и модулю n, если для всех а Î Z_n найдется такое целое y, что

y = a^x mod n.

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

Определение. Односторонняя функция 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 не входит, что осложняет ее при­менение с точки зрения правовых норм. Тем не менее, выбор этой крипто­системы признается оправданным отечественными авторами [7].