Одноразовая система шифрования

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

Одноразовая система шифрует исходный открытый текст X=(x₀, x₁, …, x_n-1) в шифротекст Y=(y₀, y₁, …, y_n-1) посредством подстановки Цезаря. Y_i=(x_i+k_i) mod m, 0<=i<n. Где k_i это элемент случайной ключевой последовательности. Ключевое пространство k одноразовой системы представляет собой набор дискретных случайных величин из Z_m и содержит mⁿ значений, где n – количество шифруемых сообщений.

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

X_i=(y_i-k_i) mod m, где k_i это i-тый элемент той самой случайной ключевой последовательности. Одноразовая система изобретена в 1917 году американцами Моварном и Вернаном. Для организации этой системы подстановки иногда используют одноразовый блокнот. Этот блокнот состоит из отрывных страниц на каждой из которых напечатана таблица со случайными числами – ключами k_i. Блокнот выполняется в двух экземплярах. Один используется отправителем, а второй получателем. Для каждого символа x_i сообщения используется свой ключ из таблицы только один раз. После того, как таблица использована, она должна быть удалена из блокнота и уничтожена. Шифрование нового сообщения начинается с новой страницы.

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

 

Шифрование метедом гаммирования

Под гаммированием понимают процесс наложения по определенному закону гаммы шифра на открытые данные.

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

 

Метод генерации псевдослучайной последовательностей чисел

При шифровании методом гаммирования в качестве ключа используется случайные строки битов, которые объединяются с открытым текстом, так же представленным в двоичном виде. С помощью побитового сложения по модулю 2 и в результате получается шифрованный текст. Генерирование непредсказуемых двоичных последовательностей большой длины является одной из важных проблем классической криптографии. Для решения этой проблемы широко используются генераторы двоичных псевдослучайных последовательностей. К криптографически-стойкому генератору псевдослучайных последователь системностей предъявляют 3 основных требования:

1. Период гаммы должен быть достаточно большим для шифрования сообщений различной длины

2. Гамма должна быть практически непредсказуемой, что означает невозможность предсказать следующий бит гаммы, даже если известны тип генератора и предшествующий кусок гаммы

3. Генерирование гаммы не должно вызывать больших технических сложностей

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

 

Афинная система подстановок Цезаря

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

E(t) = (at + b) mod m,

где a и b – целые числа, при этом a и b > 0 и < m. M – Размерность алфавита и a и m взаимно простые, то есть НОД (a,m)=1. T – Номер буквы исходного алфавита.

 

Современные симметричные криптосистемы

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

1. Перестановки

2. Блочные – представляют собой семейство обратимых преобразований блоков исходного текста. Фактически блочный шифр это система подстановки на алфавите блоков. В настоящее время блочные шифры наиболее распространены в практике. Российский и американский стандарты шифрования относятся именно к этому классу шифров.

3. Ганирование

Общие сведения о блочных шифрах

Под N-разрядным блоком будем понимать последовательность из нулей и единиц длины N.

X = (x₀,x_1­,...,x_n-1)

Х в этом множестве можно интерпретировать как вектор или как двоичное представление целого числа

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

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

Требования к хорошему блочному шифру формируются следующим образом:

1. Необходимо достаточно большое N (64 или более) для того, чтобы затруднить составление и поддержание каталогов. В стандарте шифрования США от 2000г. N составляло 128

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

3. Необходимы сложные соотношения π{k,x}:xày=π{k,x}

Генерирование блочных шифров

Одним из наиболее распространенных способов задания шифров является использование так называемых сетей Фейстела. Она представляет собой общий метод преобразования произвольной функции обычно называемой F-функцией в перестановку на множестве блоков. Эта конструкция была изобретена Хорстом Фейстелом и было использована в большом количестве шифров, в том числе в шифре DES (1978г) и российским шифром ГОСТ-28147-89.

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

F:Z_2,N/2*Z_2,KàZ_2,N/2

Где N – длина преобразуемого блока текста (должна быть четной), K – длина используемого блока ключевой информации. Пусть X – блок текста и представим его в виде двух подблоков одинаковой длины. Тогда получим X={A,B}. Тогда одна итерация сети Фейстела определяется, как

X_i+1=B_i||(F(B_i,k_i)℗A_i)

Где X_i – A_i, B_i, ℗ - побитовое исключающее «ИЛИ», || - операция конкатенации.

Структуру итерации сетей Фейстела представим в виде следующей схемы:

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

Данная структура шифра обладает рядом достоинств:

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

2. Для построения устройств шифрования можно использовать те же блоки в цепях шифрования и расшифрования

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

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

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

 

Стандарт AES

В конце 1996 года национальным институтом стандартов США был объявлен конкурс на создание нового общенационального стандарта шифрования, который должен был прийти на смену стандарту DES. Второго октября 2000 года было принято окончательное решение в качестве предполагаемого стандарта был выбран алгоритм Rijndael. Этот алгоритм был разработан Уинстоном Рейманом и Йоан Дамен и представляет собой алгоритм, не использующий сети Фейстелла. При описании алгоритма используется поле Галуа: GF(2⁸), построенное, как расширение поля GF(2) по корням неприводимого многочлена m(x)=x⁸+x⁴+x³+x+1. Данный многочлен выбран из соображений эффективности представления элементов поля. Элементарные операции, использующиеся в алгоритме, выполняются в указанном поле. Алгоритм Rijndael представляет собой блочный шифр с переменной длинной блока и переменной длиной ключа. Длины блока и ключа могут быть выбраны независимо равными 128, 192 и 256 битам. Шифр является последовательностью итераций, выполняемых над некоторой промежуточной структурой, называемой состоянием. Состояние может быть представлено виде прямоугольного массива байтов. В массиве 4 строки, а число столбцов обозначается как Nb равное блине блока деленной на 32. Ключ шифрования аналогичным образом представляется в виде прямоугольного байтового массива с четырьмя строками, количество столбцов обозначается Nk, равное длине ключа, деленной на 32. Входные и выходные значения алгоритма представляются в виде одномерных байтовых массивов соответствующей длины. Состояние и ключевой массив заполняется из этих массивов вначале по столбцам, а затем по строкам. Количество итераций обозначается Nr и оно зависит от Nb и Nk в соответствии со следующей таблицей.

Nr	Nb=4	Nb=6	Nb=8
Nk=4
Nk=6
Nk=8

Итерационные преобразования состоит и четырех различных преобразований:

1. Это блок нелинейной обратимой байтовой замены, так называемый S-box, состоящий из двух операций:

a. Операция, каждый байт заменяется на мультипликативные, обратные к нему в поле GF(2⁸).

Замечание: байт со значением ‘00’h отображается сам в себя.

b. Над каждым байтом выполняется аффинное преобразование в поле GF(2).

1 x₀ 1 0 0 0 1 … 1 y₀

1 x₁ 1 1 0 0 0 … 1 y­₁

0 x₂ 1 1 1 0 0 … 1 y₂

0 + x₃ * 1 1 1 1 0 … 1 = y₃

0 x_4­ 1 1 1 1 1 … 0 y₄

1 x_5­­ 0 1 1 1 1 … 0 y₅

1 x₆ 0 0 1 1 1 … 0 y₆

0 x₇ 0 0 0 1 1 … 1 y₇

Это афинное преобразование может быть описано в полиномном виде как:

B(x)=(x⁷+x⁶+x²+x)+a(x)* (x⁷+x⁶+x⁵+x⁴+1)mod(x⁸+1)

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

2. Является циклическим сдвигом влево строк массива состояния на различную величину. Строка ноль не сдвигается, строка 1 сдвигается на C1 позиции, строка 2 сдвигается на C2 позиции, и строка 3 сдвигается на C3 позиции. Величины сдвига представлены в таблице.

Nb	C1	C2	C3

3. В этом преобразовании столбца массива состояния рассматриваются как полиномы над полем GF(2⁸). Преобразование заключается в умножении столбца по модулю x⁴+1 на фиксированный полином.

C(x)=’03h’x³+’01h’x²+’01h’x+’02h’

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

 

Российский стандарт шифрования ГОСТ-28.147-89

Для других организация и частных лиц ГОСТ имеет рекомендационный характер. Данный стандарт формировался с учетом мирового опыта и в частности были приняты во внимание недостатки и нереализованные возможности алгоритма DES, поэтому использование ГОСТ предпочтительнее. Алгоритм шифрования построен с использованием сетей Фейстеля.

В этом алгоритме используется ассоциативная операция конкатенации и используется для неё мультипликативная запись. Кроме того будут использованы следующие операции сложения:

1. Побитовое сложение по модулю 2

2. Сложение по модулю 2³²

3. Сложение по модулю 2³²-1

Алгоритм криптографического преобразования предусматривает несколько режимов работы:

1. Шифрование данных в режиме простой замены

2. Шифрование данных в режиме ганирования

3. Шифрование данных в режиме ганирования с обратной связью

4. Выработка имитовставки

Во всех режимах используется ключ W длиной 256 бит, представленный в виде восьми тридцати двух разрядных чисел x_i, то есть W=x₇*x₆*…*x₀. Для расшифрования используется тот же ключ, но этот процесс является инверсным по отношению к исходному. Базовым режимом работы алгоритма является режим простой замены.

Рассмотрим этот режим более подробно.

Пусть открытый текст разбит на блоки по 64 бита в каждом, который обозначим T₀. Последовательность битов T₀ разделяется на две последовательности – B₀ и A₀ по 32 бита. Далее выполняется итерационный процесс шифрования, который опишем следующими формулами:

Для i=1…24:

A(i)=RK(A(i-1)[+]X_(i-1)(mod8))℗B(i-1) }

B(i)=A(i-1) }

Для i=25…31:

A(i)=RK(A(i-1)[+]X_32-1)℗B(i-1) }

B(i)=A(i-1) }

Для i=32:

A(32)=A(31) }

B(32)=RK(A(31)[+]X₀℗B(31) }

 

I – номер итерации.

Функция шифрования включает 2 операции над 32-разрядным аргументом K и R. Первая операция является подстановкой. Блок подстановки K состоит из 8 узлов замен, то есть K(1)…K(8) с памятью по 64 бита каждый. Поступающий на блок подстановки 32-разрядный вектор разбивают на 8 последовательно идущих 4-разрядных векторов, каждый из которых преобразуется в 4-разрядный вектор соответствующим узлом замены, представляющий из себя таблицу из 16 целых чисел от 0 до 15. Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем полученные 4-разрядные векторы вновь последовательно объединяются 32-разрядный выходной. ГОСТ-28147-89 в явном виде не указывает таблицы подстановок. Вторая операция это циклический сдвиг 32-разрядного вектора, полученного в результате подстановки K на 11 шагов влево. 64-разрялный блок зашифрованных данных T_ш представляется в виде =A(32)B(32).

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

Схема режима простой замены ГОСТ 28147-89

 

Ассиметричные криптосистемы

Концепция криптосистем с открытым ключом

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

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

E_B – шифровка сообщения

D_B – расшифровка сообщения

K_B – открытый ключ

K_B – закрытый ключ

Примечания: генератор ключей целесообразно располагать на стороне получателя B, чтобы не пересылать секретный ключ k_b по незащищенному каналу.

Раскрытие секретного ключа k_b по известному K_b должно быть вычислительно неразрешимой задачей. Характерные особенности ассиметричных криптосистем:

1. Открытый ключ K_b и криптограмма С могут быть отправлены по незащищенному каналу

2. Алгоритм шифрования и расшифрования всем известен

Можно описать его следующим образом:

E_B:MàC

D_B:CàM

Дифи и Хэлман сформулировали требования, выполнение которых обеспечит безопасность ассиметричной криптосистемы:

1. Вычисление пары ключей K_B и k_B получателем B на основе начального условия должно быть простым

2. Отправитель A зная открытый ключ K_b и сообщение M может легко вычислить криптограмму

С=E_KB(M)=E_B(M)

3. Получатель B используя секретный ключ k _B и криптограмму C может легко восстановить исходное сообщение: M=D_kB(C)=D_B(C)=D_B(E_B(M))

4. Противник, зная открытый ключ K_B при попытке вычислить секретный ключ k­_B наталкивается на непреодолимую вычислительную проблему

5. Противник зная пару K­ _B и C при попытке вычислить исходное сообщение M наталкивается на непреодолимую вычислительную проблему

 

Криптосистема шифрования данных RSA (РША)

Алгоритм РША предложен в 1978 году тремя авторами – Райвест, Шамир, Адлеман. Алгоритм получил свое название по первым буквам фамилий её авторов. Этот алгоритм стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронно-цифровой подписи. Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов.

В криптосистеме РША открытый ключ K_B секретный ключ k_B, сообщение M и криптограмма C принадлежат множеству целых чисел:

Z_N={0,1,2,…,N-1}, где N – модуль. N=P*Q, здесь P и Q случайные большие простые числа. Для обеспечения максимальной безопасности выбирают P и Q равной длины и хранят в секрете. Множество Z_N с операциями умножения и сложения по модулю N образуют арифметику по модулю N. Открытый ключ K_B выбирают случайным образом так, чтобы выполнялись условия:

1. =>K_B>1

2. НОД(K_B, )=1

3. =(P-1)(Q-1)

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

Второе из указанных выше условий означает, что открытый ключ K_B и должны быть взаимнопростыми. Далее, используя расширенный алгоритм Евклида вычисляется секретный ключ k_B следующим образом: k_B*K_BΞ1(mod ) или k_B=K_B^-1(mod(P-1)(Q-1)). Это можно осуществить так, как получатель B знает пару простых чисел P и Q и может легко найти функцию . Заметим, k_B и N должны быть взаимнопростыми. Преобразование шифрования определяет криптограмма C через пару K_B и M в соответствии со следующей формулой:

C=E_KB(M)=E_B(M)=M^KB(mod N)

В качестве алгоритма быстрого вычисления значения C используют ряд последовательных возведений в квадрат целого M и умножения на M с привидением по модулю N. Обращение функции С=M^KB(mod N), то есть определение значения M по известным значениям C, K_B и M практически неосуществимо при N приблизительно равному 2⁵¹². Однако, обратную задачу, то есть задачу расшифрования криптограммы C можно решить используя пару k_B и C по следующей формуле:

M=D_kB(C)=С^kB(mod N)

D_B(E_B(M))=M

(M^KB)^kB=M (mod N) или M^KBkB=M(mod N)

 

Величина играет важную роль в теореме Эйлера, в которой утверждает, что, если НОД(x,N)=1, то x^ =1 (mod N). Или в некотором более общем виде: x

Таким образом, если криптограмму возвести в степень k_B, то в результате восстанавливается исходный текст M.

В итоге получатель B, который создает криптосистему, защищает 2 параметра:

1. Секретный ключ k _B

2. Пару чисел P, Q, произведение которых дает модуль N

С другой стороны получатель B отбивает значения модуля B и открытый ключ K_B

 

Процедура шифрования и расшифрования в криптосистеме РША

Предположим, что пользователь A хочет передать пользователю B сообщение в зашифрованном виде, используя криптосистему РША. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь B – получатель. Как отмечалось выше, криптосистему РША должен сформировать получатель сообщения, то есть пользователь B. Сейчас рассмотрим последовательность действий пользователя B и пользователя A:

1. Пользователь B выбирает 2 произвольных и больших числа P и Q

2. Пользователь B вычисляет значение модуля, то есть находит произведение N=P*Q

3. Пользователь B вычисляет функцию Эйлера =(P-1)(Q-1) и выбирает случайным образом значение открытого ключа K _B с учетом выполнения условий: =>K_B>1, НОД(K_B, )=1

4. Пользователь B вычисляет значение секретного ключа k_B используя алгоритм Евклида

5. Пользователь B пересылает пользователю A пару чисел N, K_B по незащищенному каналу связи

Если пользователь A хочет передать пользователю B сообщение M, он выполняет следующие шаги:

6. Пользователь A разбивает исходный открытый текст M на блоки, каждый из которых можно представить в виде числа M_i=0,1,2,…,N-1.

7. Пользователь A шифрует текст, представленный виде последовательности чисел M_i по формуле: C_i=M_i^KB(mod N) и отправляет криптограмму C₁,C₂,C₃ и так далее

8. Пользователь B расшифровывает принятую криптограмму используя секретный ключ k_B по формуле: M_i=C_i^kB(mod N)

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

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

Пример: зашифруем сообщение CAB. Для простоты будем использовать небольшие простые числа.

1. P=3 Q=11

2. N=P*Q=33

3. =2*10=20 K_B=7

4. k_B=7^-1(mod 20) =3

5.

6. Пусть буква А представлено как число 1, В =2, С=3 Тогда сообщение САВ можно представить как последовательность чисел 312, то есть M1=3, M2=1, M3=2.

7. С₁=M₁⁷(mod 33)=3⁷(mod 33)=2187 mod 33=9

C₂=1⁷mod 33=1

C₃=2⁷mod 33=29

8. M₁=C₁³(mod 33)=9³mod 33=3

M₂=1³mod 33=1

M₃=29³mod 33=2

 

Схема шифрования Эль-Гамаля

 

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

С=P^E(mod n), P - исходное сообщение, C – криптограмма, Е – ключ для шифровки, N – модуль. Расшифрование можно записать следующей формулой:

P=C^D(mod n), D – ключ для дешифровки.

При этом E*D=1 mod n. При этом n не определяется через два больших простых числа, а является некоторым составным числом. Не зная значения ключей шифрования и дешифрования, противник должен будет вычислять значения одного из ключей по следующей формуле:

E=log_P^C(mod n) что является труднорешимой задачей.