Сделай Сам Свою Работу на 5

Отечественный стандарт шифрования ГОСТ 28147-89





 

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

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

· L и R - последовательности битов;

· LR - конкатенация последовательностей L и R, в которой биты последовательности R следуют за битами последовательности L;

· (+) - поразрядное сложение по модулю 2 (операция «исключающее ИЛИ»);

· [+] - сложение 32-разрядных чисел по модулю 232;

· {+} - сложение 32-разрядных чисел по модулю 232-1.

Числа суммируются по следующему правилу:

· A [+] B = A + B, если A + B < 232,

· A [+] B = A + B - 232, если A + B >= 232.

· A {+} B = A + B , если A + B < 232 - 1,

· A {+} B = A + B - (232 - 1), если A + B >= 232 - 1.

Алгоритм предусматривает четыре режима работы:

· простая замена;

· гаммирование;

· гаммирование с обратной связью;

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

В любом случае для шифрования данных используется 256-битовый ключ K, который представляется в виде восьми 32-битовых подключей Ki:



K = K7K6K5K4K3K2K1K0.

Расшифрование выполняется по тому же ключу, что и шифрование, но этот процесс является инверсией процесса шифрования данных.

Режим простой замены

Первый и самый простой режим – режим замены. Данные, подлежащие шифрованию, разбивают на 64-битовые блоки. Процедура шифрования блока открытых данных T0 включает 32 цикла (j=1...32).

Блок T0 разделяется на две последовательности по 32 бита: В(0)A(0), где В(0) - левые или старшие биты, A(0) - правые или младшие биты.

Эти последовательности вводят в накопители N1 и N2 перед началом первого цикла шифрования.

Первый цикл (j=1) процедуры шифрования 64-битового блока данных описывается следующими формулами:

{ A(1) = f ( A(0) [+] K0 ) (+) B(0), B(1)=A(0).

Здесь A(1) - заполнение накопителя N1 после 1-го цикла шифрования

{ A(i) = f ( A(i-1) [+] X(j) ) (+) B(i-1), B(i) = A(i-1), если i=25, 26,..., 31; j=32-i
{ A(32) = A(31), B(32) = f ( A(31) [+] X(0) ) (+) B(31),

Здесь i обозначает номер итерации (i = 1, 2,..., 32).

Функция f называется функцией шифрования. Ее аргументом является сумма по модулю 232 числа A(i), полученного на предыдущем шаге итерации, и числа X(j) ключа (размерность каждого из этих чисел равна 32 знакам).



Функция шифрования включает две операции над полученной 32-разрядной суммой. Первая операция называется подстановкой К. Блок подстановки К состоит из 8 узлов замены К(1) ... К(8) с памятью 64 бит каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-х разрядных векторов, каждый из которых преобразуется в 4-х разрядный вектор соответствующим узлом замены, представляющим собой таблицу из 16 целых чисел в диапазоне 0...15.

Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-х разрядные выходные векторы последовательно объединяются в 32-разрядный вектор. Таблицы блока подстановки К содержит ключевые элементы, общие для сети ЭВМ и редко изменяемые.

Вторая операция – циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К.

64-разрядный блок зашифрованных данных Тш представляется в виде Тш=A(32)B(32). Остальные блоки открытых данных в режиме простой замены зашифровываются аналогично.

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

К этим случаям относится выработка ключа и зашифрование его с обеспечением имитозащиты (защиты от навязывания ложных данных) для передачи по каналам связи или хранения в памяти ЭВМ.

Режим гаммирования

Открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m, где m определяется объемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Гш, которая вырабатывается блоками по 64 бит, то есть



Гш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.

Уравнение зашифрования данных в режиме гаммирования может быть представлено в следующем виде:

 

Ш(i) = A (Y(i-1) [+] C2, Z(i-1) {+} C1) (+) T(i) = Г(i) (+) T(i) .


Здесь

· Ш(i) - 64-разрядный блок зашифрованного текста,

· A - функция шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа),

· С1 и С2 - константы, заданные в ГОСТ 28147-89,

· Y(i) и Z(i) - величины, которые определяются итерационно по мере формирования гаммы следующим образом:

· (Y(0), Z(0)) = A(S), где S - 64-разрядная двоичная последовательность (синхропосылка);

· (Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) {+} C1) для i = 1, 2,...,m.

Расшифрование данных возможно только при наличии синхропосылки, которая не является секретным элементом шифра и может храниться в памяти ЭВМ или передаваться по каналам связи вместе с зашифрованными данными.

Режим гаммирования с обратной связью

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как в и режиме гаммирования открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m , где m определяется объемом шифруемых данных), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Гш, которая вырабатывается блоками по 64 бит:

Гш = (Г(1),Г(2),...,Г(i),...,Г(m)).

Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.

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

 

Ш(1) = A(S) (+) T(1) = Г(1) (+) Т(1), Ш(i) = A(Ш(i-1)) (+) T(i) = Г(i) (+) Т(i), для i = 2,3,...,m.

Здесь

· Ш(i) - 64-разрядный блок зашифрованного текста,

· A - функция шифрования в режиме простой замены.

Аргументом функции на первом шаге итеративного алгоритма является 64-разрядная синхропосылка, а на всех последующих - предыдущий блок зашифрованных данных Ш(i-1).

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

 

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

Имитовставка – это блок из р бит (имитовставка Ир), который вырабатывается либо перед шифрованием всего сообщения, либо параллельно с шифрованием по блокам. Первые блоки открытых данных, которые участвуют в выработке имитовставки, могут содержать служебную информацию (например, адресную часть, время, синхропосылку) и не зашифровываться. Значение параметра р (число двоичных разрядов в имитовставке) определяется криптографическими требованиями с учетом того, что вероятность навязывания ложных помех равна 1/2р.

Для получения имитовставки открытые данные представляются в виде 64-разрядных блоков Т(i) (i = 1, 2,..., m , где m определяется объемом шифруемых данных). Первый блок открытых данных Т(1) подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Причем в качестве ключа для выработки имитовставки используется ключ, по которому шифруются данные.

Полученное после 16 циклов работы 64-разрядное число суммируется по модулю 2 со вторым блоком открытых данных Т(2). Результат суммирования снова подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены.

Полученное 64-разрядное число суммируется по модулю 2 с третьим блоком открытых данных Т(3) и т.д. Последний блок Т(m) при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на шаге m-1, после чего зашифровывается в режиме простой замены по первым 16 циклам работы алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р бит.

Имитовставка Ир передается по каналу связи или в память ЭВМ после зашифрованных данных. Поступившие зашифрованные данные расшифровываются. Из полученных блоков открытых данных T(i) вырабатывается имитовставка Ир'. Затем имитовставка сравнивается с имитовставкой Ир, полученной из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок все расшифрованные данные считают ложными.

 

Лекция 9

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

 

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

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

Однонаправленные функции

Вся концепция криптосистем с открытым ключом основана на применении однонаправленных функций (one way functions). Однако точное определение этого класса функций с математической точки зрения дать достаточно сложно. Неформально однонаправленную функцию можно определить следующим образом.

Пусть X и Y - произвольные множества. Функция

f(X) Æ Y,


является однонаправленной, если для всех х, входящих в Х, легко вычислить функцию f(x), и в то же время, для большинства y, входящих в Y, получить любое значение x, входящее в X, такое что f(x) = y достаточно сложно (при этом полагают, что существует, по крайней мере, одно такое значение x).

К сожалению, в настоящее время математика не в состоянии дать нам ответ на вопрос, существуют ли таковые функции вообще или же это только красивая гипотеза. Тем не менее, пытливым умам удалось обнаружить несколько зависимостей, которые могут быть использованы (и используются!) в качестве однонаправленных. Основной критерий причисления функции к классу однонаправленных очень прост – отсутствие эффективных алгоритмов обратного преобразования.

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

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

Но вернемся к теме. Вторым важным классом функций, используемых в практике построения систем с открытым ключом, являются так называемые однонаправленные функции с черным ходом (trap door one way function). Для порядка введем определение.

Функция

f(X) Æ Y,


относится к классу однонаправленных функций с черным ходом в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление инверсной функции, если известен «черный ход» (или, говоря по-русски, секретная строка, число или другая информация, ассоциирующаяся с данной функцией).

 

Система распределения ключей Диффи-Хелмана

 

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

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

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

И если спецслужбы как-то выходят из этой ситуации, то для коммерческих приложений это никуда не годится. И пытливая инженерная мысль нашла выход – была создана система распределения открытых ключей (public-key distribution system), позволяющая своим пользователям обмениваться секретными ключами по незащищенным каналам связи.

Первой системой такого рода стала система Диффи-Хелмана, разработанная в 1976 году, построенная на задаче о дискретном логарифмировании.

Предположим, что два пользователя, «А» и «Б», применяющие симметричную криптосистему, желают связаться друг с другом. Это означает, что они должны прийти к соглашению относительно ключа K, которым будут шифроваться сообщения. Давайте посмотрим, как система Диффи-Хелмана позволит обменяться ключом.

Пусть N - некоторое большое целое число, а G - другое целое, такое что

1 <= G <= N-1.

Рассмотрим процедуру обмена ключами по шагам.

1. Вначале «А» и «Б» достигают соглашения о значениях N и G (как правило, эти значения являются стандартными для всех пользователей системы).

Затем «А» выбирает некоторое большое целое число X и вычисляет XX = G^X MOD N.

Аналогичным образом «Б» выбирает число Y и вычисляет
YY = G^Y MOD N.

После этого «А» и «Б» обмениваются значениями XX и YY. (Мы считаем, что все данные, которые передаются по каналу связи, могут быть перехвачены злоумышленником).

Числа X и Y «А» и «Б» хранят в секрете.

Получив от «Б» число YY, «А» вычисляет K(1) = YY^X MOD N,

а «Б» - K(2) = XX^Y MOD N.

Но (!) YY^X MOD N = G^(X*Y) MOD N = XX^Y MOD N,

следовательно, K(1) = K(2) = K.

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

Злоумышленник, перехвативший G, N, XX и YY, тоже должен определить значение ключа K. Очевидный путь для решения задачи состоит в вычислении значения X по G, N, XX или, по крайней мере, некоторого X', такого что

G^X' MOD N = X,


поскольку в этом случае

YY^X' MOD N = K.

Однако это и есть задача дискретного логарифмирования в чистом виде, которая считается неразрешимой.

Система Диффи-Хелмана позволяет двум пользователям прийти к соглашению относительно общего секретного ключа. Однако система никак не влияет на то, как потом будет шифроваться сама информация. И если «А» хочет передать «Б» секретное сообщение M, то после установления ключа по Диффи-Хеллману может быть использована любая система шифрования.

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

Пользователь «А» имеет в своем распоряжении два алгоритма: E для шифрования и D для расшифровки сообщений. При этом алгоритм E делается общедоступным, например, через использование каталога ключей, а алгоритм D хранится «А» в секрете. Если «Б» или даже злоумышленник хочет послать «А»у сообщение, он ищет в каталоге ключей алгоритм E и использует его для шифрования передаваемой информации. А вот расшифровать сообщение сможет только «А», поскольку алгоритм D есть только у него. Очевидно, что E и D должны удовлетворять условию:

 

D(E(M)) = M,


для любого сообщения M.

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

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

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

Система RSA

 

В настоящее время наиболее развитым методом криптографической защиты информации с известным ключом является RSA, названный так по начальным буквам фамилий его изобретателей (Rivest, Shamir и Adleman).

Перед тем как приступить к изложению концепции метода RSA, дадим определение некоторых терминов.

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

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

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

2. Определим n как результат умножения p на q ( n = p*q ).

3. Выберем большое случайное число, которое назовем d. Это число должно быть взаимно простым с результатом умножения (p-1) * (q-1).

4. пределим такое число е, для которого является истинным следующее соотношение: (e * d) mod ((p-1) * (q-1)) = 1.

5. Назовем открытым ключем числа е и n, а секретным ключем числа d и n.

Теперь, чтобы зашифровать данные по известному ключу {e,n}, необходимо сделать следующее:

разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i) = 0, 1,..., n-1;

зашифровать текст, рассматриваемый как последовательность чисел M(i), по формуле: С(i) = (M(i)^e) mod n.

Чтобы расшифровать эти данные используя секретный ключ {d,n}, необходимо выполнить следующие вычисления: M(i) = (C(i)^d) mod n. В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

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

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

Более того, сам вопрос существования эффективных алгоритмов решения NP – полных задач является до настоящего времени открытым. В связи с этим для чисел, состоящих из 200 цифр (а именно такие числа рекомендуется использовать), традиционные методы требуют выполнения огромного числа операций (около 1023).

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

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

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

Само сообщение шифруется с использованием этого временного сеансового ключа. Затем этот сеансовый ключ шифруется с помощью открытого асимметричного ключа получателя и асимметричного алгоритма шифрования.

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

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

Если используется короткий сеансовый ключ (например, DES), то не имеет значения, насколько велики асимметричные ключи. Хакеры будут атаковать не их, а сеансовые ключи.

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

Pretty Good Privacy (PGP)

 

Одной из реализаций асимметричных криптосистем является разработанная Филиппом Циммерманном программа PGP (Довольно Хорошая Секретность). Эта программа отличается превосходно продуманным и чрезвычайно мощным механизмом обработки ключей. Популярность и бесплатное распространение сделали PGP фактически стандартом для электронной переписки во всем мире.

Программа PGP широко доступна в сети. В связи с ограничениями на экспорт криптографической продукции версия 5.0 запрещена к экспорту, но по старой доброй традиции была немедленно проэкспортирована из США.

 

Электронная подпись в системах с открытым ключом

 

Пусть пользователь N1 должен передать сообщение m пользователю N2 так, чтобы пользователь N2 в случае надобности мог доказать, что сообщение послано пользователем N1.

Для этого пользователь N1 разрабатывает систему шифрации

E1(D1(X)) = X


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

Получив от пользователя N2 общий ключ шифрования E2 открытой системы

E2(D2(X)) = X,


пользователь N1 вычисляет сигнатуру сообщения

S = D1(m),


затем шифрует ее открытым ключом E2

C = E2(S)


и передает его пользователю N2, который расшифровывает сообщение процедурой

S = D2(C)
m* = E1(S).

Теперь при возникновении спорной ситуации пользователь N1 должен представить арбитру свой личный ключ подписи D1, удовлетворяющий соотношению

E1(D1(X)) = X.

Арбитру необходимо лишь проверить, что

D1(m*) = S,


и следовательно, сообщение мог послать только пользователь N1. Кроме того и пользователь N2 не может исказить сообщение m, т.к. для доказательства в суде ему необходимо изменить и сигнатуру S, а для этого ему нужно знать личный ключ подписи пользователя N1, а его то и нет!

О «двуличии» в алгоритмах цифровой подписи

 

Анализируя ту или иную схему ЭЦП, обычно ставят вопрос так: «Можно ли быстро подобрать два различных (осмысленных) сообщения, которые будут иметь одинаковые ЭЦП». Ответ здесь обычно отрицательный – трудно это сделать. Поставим вопрос по другому, а именно: «Можно ли, имея два сообщения, подобрать секретные ключи так, чтобы подписи совпадали?». Оказывается, что сделать это чрезвычайно просто!

Вот пример действий злоумышленника.

Он может:

Подготовить две платежки: на 10000000 руб. (m1) и на 3 руб. (m2).

Выбрать секретный ключ X1 и рассчитать ключ X2.

Зарегистрировать открытые ключи, соответствующие секретным ключам.

Отправить в банк требование m1 с подписью на X1 (m1c1).

Дождаться выполнения банком поручения.

Предъявить банку претензию, состоящую в том, что он якобы посылал требование о переводе 3-х рублей (m2c2), а не 10000000 (m1c1), а то, что кто-то подобрал текст сообщения, не изменяющий ЭЦП - дело не его. Пусть платит банк, удостоверяющий центр, страховая компания - кто угодно, только верните мои деньги!

И главное, что придется вернуть!

В чем же источник успеха такой атаки? Дело в том, что Федеральный Закон «Об электронной цифровой подписи» допускает множественность ЭЦП для одного лица (статья 4, п.2). Именно поэтому злоумышленник получает реальную возможность подбирать не сообщение, а ключ! Более того – не исключен вариант сговора двух лиц – т. е. ЭЦП оказывается уязвимой, если секретный ключ известен хоть кому-нибудь! А если сговорятся два центра по сертификации подписей? Тем не менее, не все так страшно.

Приведенный пример никак не дискредитирует собственно криптостойкость ЭЦП. Он показывает возможную уязвимость при неправильном применении механизмов ЭЦП. В этой связи особое внимание должно быть уделено способам построения защищенного документооборота на базе ЭЦП. Из всего сказанного вытекают следствия:

В Интернете не должно быть анонимности.

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

Вопросы применения ЭЦП в документообороте должны быть нормативно закреплены в ФЗ «Об электронном документообороте».

 

Лекция 10

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.