Информационная безопасность / Общий_лекция

	131
k	Объем ансамбля
5	6
6	8
7	18
8	16
9	48
10	60
16	2048

Очевидно, что такие объемы ансамблей последовательности неприемлемы. Поэтому на практике часто используют последовательности Голда, образующиеся суммированием нескольких М-последовательностей. Объем ансамблей этих последовательностей на несколько порядков превосходят объемы ансамблей порождающих М-последовательностей. Так при k=10 ансамбль увеличивается от 1023 (М-последовательности) до 388000.

Также перспективными представляются нелинейные датчики ПСП (например сдвиговые регистры с элементом И в цепи обратной связи), однако их свойства еще недостаточно изучены.

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

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

5. Блочные шифры

Характерной особенностью блочных криптоалгоритмов является тот факт, что в ходе своей работы они производят преобразование блока входной информации фиксированной длины и получают результирующий блок того же объема, но недоступный для прочтения сторонним лицам, не владеющим ключом. Таким образом, схему работы блочного шифра можно описать функциями Z=EnCrypt(X,Key) и X=DeCrypt(Z,Key)

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

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

132

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

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

Название алгоритма	Автор	Размер блока		Длина ключа
IDEA	Xuejia Lia and James Massey	64	бита	128 бит
CAST128		64	бита	128 бит
BlowFish	Bruce Schneier	64	бита	128 – 448 бит
ГОСТ	КГБ СССР	64	бита	256 бит
TwoFish	Bruce Schneier	128 бит		128 – 256 бит
MARS	Корпорация IBM	128 бит		128 – 1048 бит

Криптоалгоритм именуется идеально стойким, если прочесть зашифрованный блок данных можно только перебрав все возможные ключи, до тех пор, пока сообщение не окажется осмысленным. Так как по теории вероятности искомый ключ будет найден с вероятностью 1/2 после перебора половины всех ключей, то на взлом идеально стойкого криптоалгоритма с ключом длины N потребуется в среднем 2N-1 проверок. Таким образом, в общем случае стойкость блочного шифра зависит только от длины ключа и возрастает экспоненциально с ее ростом. Даже предположив, что перебор ключей производится на специально созданной многопроцессорной системе, в которой благодаря диагональному параллелизму на проверку 1 ключа уходит только 1 такт, то на взлом 128 битного ключа современной технике потребуется не менее 1021 лет. Естественно, все сказанное относится только к идеально стойким шифрам, которыми, например, с большой долей уверенности являются приведенные в таблице выше алгоритмы.

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

133

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

Таким образом, на функцию стойкого блочного шифра Z=EnCrypt(X,Key) накладываются следующие условия:

1.Функция EnCrypt должна быть обратимой.

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

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

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

Все действия, производимые над данными блочным криптоалгоритмом, основаны на том факте, что преобразуемый блок может быть представлен в виде целого неотрицательного числа из диапазона, соответствующего его разрядности. Так, например, 32-битный блок данных можно интерпретировать как число из диапазона 0..4'294'967'295. Кроме того, блок, разрядность которого обычно является "степенью двойки", можно трактовать как несколько независимых неотрицательных чисел из меньшего диапазона (рассмотренный выше 32-битный блок можно также представить в виде 2 независимых чисел из диапазона 0..65535 или в виде 4 независимых чисел из диапазона 0..255).

Над этими числами блочным криптоалгоритмом и производятся по определенной схеме следующие действия (слева даны условные обозначения этих операций на графических схемах алгоритмов):

Биективные (обратимые) математические функции

	Сложение	X'=X+V

	Исключающее ИЛИ	X'=X XOR V
	Умножение по модулю 2N+1	X'=(X*V) mod (2N+1)

134

	Умножение по модулю 2N	X'=(X*V) mod (2N)
Битовые сдвиги
	Арифметический сдвиг влево	X'=X SHL V
	Арифметический сдвиг вправо	X'=X SHR V
	Циклический сдвиг влево	X'=X ROL V
	Циклический сдвиг вправо	X'=X ROR V
Табличные подстановки
	S-box (англ. substitute)	X'=Table[X,V]

В качестве параметра V для любого из этих преобразований может использоваться:

1.фиксированное число (например, X'=X+125)

2.число, получаемое из ключа (например, X'=X+F(Key))

3.число, получаемое из независимой части блока (например, X2'=X2+F(X1))

Последний вариант используется в схеме, названной по имени ее создателя сетью Файстеля (нем. Feistel).

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

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

135

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

Поскольку операция зашифровки или расшифровки отдельного блока в процессе кодирования пакета информации выполняется многократно (иногда до сотен тысяч раз), а значение ключа и, следовательно, функций Vi(Key) остается неизменным, то иногда становится целесообразно заранее однократно вычислить данные значения и хранить их в оперативной памяти совместно с ключом. Поскольку эти значения зависят только от ключа, то они в криптографии называются материалом ключа. Необходимо отметить, что данная операция никоим образом не изменяет ни длину ключа, ни криптостойкость алгоритма в целом. Здесь происходит лишь оптимизация скорости вычислений путем кеширования (англ. caching) промежуточных результатов. Описанные действия встречаются практически во многих блочных криптоалгоритмах и носят название расширение ключа (англ. key scheduling).

Тема 2.3. Ассиметричные методы криптографии.

1.Асимметричная (открытая) методология

2.Методика шифрования с помощью открытого ключа.

3.Электронная цифровая подпись.

1. Асимметричная (открытая) методология

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

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

136

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

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

тым ключом.

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

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

Криптографические системы с открытым ключом используют так называемые необратимые или односторонние функции, которые обладают следующим свойством: при заданном значении x относительно просто вычислить значение f(x), однако если y=f(x), то нет простого пути для вычисления значения x.

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

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

137

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

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

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

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

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

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

Виды асимметричных алгоритмов

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

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

Тип		Описание

RSA

ECC

(криптосистема на основе эллиптических кривых)

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

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

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

Современные его реализации показывают, что эта система гораздо более эффективна, чем другие системы с открытыми ключами. Его производительность приблизительно на порядок выше, чем производительность RSA, Диффи-Хеллмана и DSA.

Эль-Гамаль. Вариант Диффи-Хеллмана, который может быть использован как для шифрования, так и для электронной подписи.

138

2. Методика шифрования с помощью открытого ключа.

Несмотря на довольно большое число различных асимметричных криптографических систем, наиболее популярна - криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.

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

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

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HHTP, S-MIME, S/WAN, STT и PCT.

Описание криптосистемы с открытым ключом, на примере алгоритма, используемого в системе RSA

Пусть абоненты А и В решили наладить между собой секретную переписку с открытым ключом. Тогда каждый из них, независимо от другого, выбирает два больших простых числа p1 и q1 , находит их произведение rА , которое

для заданного алфавита должно удовлетворять условию

rA M

(M –

количество используемых знаков алфавита), функцию Эйлера от этого

произведения

(rА )

и выбирает случайное число

a

меньшее этого

вычисленного значения функции Эйлера и взаимно простое с ним. Взаимно простыми числами называются такие числа, у которых общий делитель равен «1», математическая запись, означающая, что числах а и b взаимно простые записывается: (a, b) 1, пример взаимно простых чисел: (3, 7) 1, (6,17) 1.

Таким образом:

A: B :

p	, q	, r
1	1	A

p2 , q2 , rB



p q	, (r	) (
1 1	A

p2q2 , (rB )

p
1

( p2

1)(q
1

1)(q2

1), (a, (r	))
A

1), (b, (rB

1,	0
))	1, 0

a (rA ) ;

b (rB ).

Функция Эйлера при известных простых числах p1 и q1 вычисляется легко(rА ) ( p1 1)(q1 1) , а в случае, если известно только их произведение

	139
rА p1q1 , эта функция вычисляется путем перебора всех простых чисел не
превышающих rА .
Затем печатается телефонная книга, доступная всем
желающим, которая имеет вид (табл. 2). В данной книге rА –			Таблица 2
произведение двух простых	чисел, известных	только	A : r	, a
			A
корреспонденту А, а - открытый ключ, доступный каждому,			B : r	, b
кто хочет передать секретное	сообщение абоненту	А, rB -	B

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

Каждый из абонентов находит свой секретный ключ из сравнений:

а 1(mod (r	))
A

и

b

1(mod (rB

))

,

при этом значения

этих ключей

и	должны удовлетворять условиям:

0 (r	)
A

и

0

(rB

)

.

Сравнение: делиться на

(rA ) 32,

1, 2, 3...

а 1(mod (rA )) означает, что произведение чисел a должно
(rA )	по mod (rA ) с остатком, равным «1». Например: a 11,
путем	перебора	произведений	a	при различных значениях
и т.д.	находим,	что при 3	отношение делится с остатком

равным «1»:

	a			33
	(r	)		32
	A

1 1 (остаток

)

.

Таких чисел может быть

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

	i (r	) 1		значений i 1, , при которых данное отношение
	A		, для тех
	a
делится без остатка по				mod(а) . В приятой математической символике это

можно записать: а 0(mod( (rA ) 1)) .

Таким образом формируется полный комплект открытых и закрытых ключей для корреспондентов А и В (табл. 3):

Таблица 3

Абонент

А

В

Открытый ключ

rA , a

r	,b
B

Закрытый ключ

Процесс шифрования и расшифровывания передаваемых сообщений

140

Пусть абонент B решает послать сообщение m абоненту A:
B : m A при этом для передачи сообщения требуется, чтобы			0 m rA .
Абонент B шифрует сообщение т открытым ключом абонента А, который
есть в телефонной книге, и находит
m1 m	a	(mod rA ) , 0 m1 rA .

Абонент А расшифровывает это сообщение своим секретным ключом:

m2

m1

(mod r	)
A

,

0 m	r
2	A

и получает

m2

m

.

Доказательство:

m		a	m	a	(mod
	m	(m )
2	1
m2	m(mod rA ) .		Но так как

r		)
A
	0

и так

m rA

как и 0

a m1

1(mod (r		))
A
rA , то	m2

, следовательно,

m .

Пример. Пусть p1 7 и q1	23 – простые числа выбранные абонентом A
(пример простых чисел показан в табл. П.6, приложения);					p2 11 и q2 17 –
простые числа абонента В;	rA 161 и		rB 187 – произведения этих чисел
соответственно, (161) 132 ,		(187 ) 160 , выберем		значения открытого
ключа из условий: (132, а) 1,		0 а 132: а = 7 и (160,		b) 1, 0 b 160: b

= 9 – случайные числа для абонентов А и В соответственно, и наконец, пусть телефонная книга, доступная всем желающим, имеет вид:

1)А: 161, 7.

2)В: 187, 9.

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

7 1(mod132) ,

9 1(mod160) ,

0 0

132

160

;

.

Таким образом,	они находят собственные секретные ключи 19 и 89
соответственно.	Пусть теперь абонент B	решает послать секретное

сообщение: «МИР» абоненту А. По таблице соответствия букв русского алфавита (см. табл. П.1, приложения) преобразуем сообщение в цифровой код: m 12, 9,16 .