Современные криптографические методы

Министерство образования Российской Федерации

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

Кафедра прикладной математики и информатики

К У Р С О В А Я   Р А Б О Т А

Современные криптографические методы

Студент IV-ИЭ-8                   Альперт В. В.

Научный руководитель         Пономарев В. П.

С а м а р а

2000

С О Д Е Р Ж А Н И Е

Стр.

 TOC o "1-3" Введение в криптографию______________________________________________ h 3

Симметричные криптосистемы___________________________________________ h 5

Стандарт шифрования данных ГОСТ 28147-89_____________________________ h 6

Международный алгоритм шифрования данных IDEA_______________________ h 10

Алгоритм RSA_______________________________________________________ h 12

Оценка надежности криптосистем_______________________________________ h 14

ЗАКЛЮЧЕНИЕ_______________________________________________________ h 19

ЛИТЕРАТУРА________________________________________________________ h 20

Введение в криптографию

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

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

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

Про­бле­мой защиты информации путем ее преобразования за­ни­ма­ет­ся крип­то­ло­гия (kryptos - тай­ный, logos - нау­ка). Криптология раз­де­ля­ет­ся на два на­прав­ле­ния - крип­то­гра­фию и крип­тоа­на­лиз. Це­ли этих на­прав­ле­ний прямо про­ти­во­по­лож­ны.

Крип­то­гра­фия за­ни­ма­ет­ся по­ис­ком и ис­сле­до­ва­ни­ем ма­те­ма­ти­че­ских ме­то­дов пре­об­ра­зо­ва­ния ин­фор­ма­ции.

Сфе­ра ин­те­ре­сов криптоанализа -  ис­сле­до­ва­ние воз­мож­но­сти рас­шиф­ро­вы­ва­ния ин­фор­ма­ции без зна­ния клю­чей.

Шиф­ро­ва­ние - пре­об­ра­зо­ва­тель­ный про­цесс: ис­ход­ный текст, ко­то­рый но­сит так­же на­зва­ние от­кры­то­го тек­ста, за­ме­ня­ет­ся шиф­ро­ван­ным тек­стом.

исходный

текст

шифрованный

текст

Криптографическая система

КЛЮЧ

Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

шифрованный

текст

исходный

текст

Криптографическая система

КЛЮЧ

Ключ - ин­фор­ма­ция, не­об­хо­ди­мая для бес­пре­пят­ст­вен­но­го шиф­ро­ва­ния и де­шиф­ро­ва­ния тек­стов.

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

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

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

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

·    

·    

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

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

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

Симметричные

криптосистемы

Гаммирование

Подстановки

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

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

Мо­но- и поли­ал­фа­вит­ные под­ста­нов­ки.

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

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

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

Гам­ми­ро­ва­ние.

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

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

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

Стан­дарт шиф­ро­ва­ния дан­ных ГОСТ 28147-89

Российский стан­дарт шифрования является блочным, т. е. преобразование ведется по блокам. Он включает в себя режим замены и два режима гаммирования. Стан­дарт ГОСТ 28147-89 фор­ми­ро­вал­ся с уче­том ми­ро­во­го опы­та, и в ча­ст­но­сти, бы­ли при­ня­ты во вни­ма­ние не­дос­тат­ки и не­реа­ли­зо­ван­ные воз­мож­но­сти ал­го­рит­ма DES, по­это­му ис­поль­зо­ва­ние стан­дар­та ГОСТ пред­поч­ти­тель­нее. Эффективность данного стан­дар­та достаточно высока. Системы, основанные на ГОСТ 28147-89, позволяют зашифровать в секунду до нескольких десятков Кбайт данных. В него заложен метод, с помощью которого можно зафиксировать необнаруженную случайную или умышленную модификацию зашифрованной информации.

Вве­дем ас­со­циа­тив­ную опе­ра­цию кон­ка­те­на­ции. Если L и R – последовательность бит, то LR обозначает кон­ка­те­на­цию последовательностей, то есть LR - последовательность бит с размерностью равной сумме размерностей L и R, причем биты R следуют за битами L. Кро­ме то­го, бу­дем ис­поль­зо­вать сле­дую­щие опе­ра­ции сло­же­ния:

·      

если A+B=>2, то A^B=А+B-2

если A+B<2 , то A^B=А+B, где A и B 1-битные числа.

·       32;

если A+B=>232, то A[+]B=A+B-232

если A+B<232 , то A[+]B=A+В, где A и B 32-битные числа.

·       32-1;

если A+B=>232-1, то A{+}B=A+B-232+1

если A+B<232-1 , то A{+}B=A+B, где A и B 32-битные числа.

Алгоритм криптографического преобразования предусматривает три режима работы. В стандарте ГОСТ используется ключ W длиной 256 бит, представляемый в виде восьми 32-разрядных чисел x(i).

W=X(7)X(6)X(5)X(4)X(3)X(2)X(1)X(0)

Самый простой из возможных режимов - замена.

Пусть открытые блоки разбиты на блоки по 64 бит в каждом, которые обозначим как T(j).

Очередная последовательность бит T(j) разделяется на две последовательности B(0) и A(0) по 32 бита (правый и левый блоки). Далее выполняется итеративный процесс шифрования, описываемый следующими формулами, вид который зависит от i.

·      

A(i) = f(A(i-1) [+] X(j)) ^ B(i-1)

B(i) = A(i-1)

·      

A(i) = f(A(i-1) [+] X(j)) ^ B(i-1)

B(i) = A(i-1)

·      

A(32) = A(31)

B(32) = f(A(31) [+] X(0)) ^ B(31).

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

·      

A(31) = A(32)

B(31) = f(A(32) [+] X(0)) ^ B(32).

·      

A(i-1) = B(i)

B(i-1) = f(B(i) [+] X(j)) ^ A(i)

·      

A(i-1) = B(i)

B(i-1) = f(B(i) [+] X(j)) ^ A(i)

Полученные A(0), B(0) – расшифрованный текст.

Здесь i обозначает номер итерации. Функция f – функция шифрования.

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

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

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

Другой режим шифрования называется режимом гаммирования.

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

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

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

Ш(i) = (f(Y(i) , f(Z(i)) ^ T(i)=Г(i) ^ T(i)

В этом уравнении Ш(i) обозначает 64-разрядный блок зашифрованного текста, f - функцию шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа). C1 и C2 - константы, заданные в ГОСТ 28147-89. Величины Y(i) и Z(i) определяются итерационно по мере формирования гаммы следующим образом:

(Z(0), Y(0)) = f(S), где S - 64-разрядная двоичная последовательность

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

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

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

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

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

Ш(1) = f(S) ^ T(1) = Г(1) ^ T(1),

Ш(i) = f(Ш(i-1)) ^ T(i) = Г(i)^T(i),  i=2, 3, ..., m.

В ГОСТ 28147-89 определяется процесс выработки имито­вставки, который единообразен для всех режимов шифрования. Имитовставка - это блок из р бит (имитовставка Ир), который вырабатывается либо перед шифрованием всего сообщения либо параллельно с шифрованием по блокам. Параметр р выбирается в соответствии с необходимым уровнем имитозащищенности.

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

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

КОНСТАНТЫ C1=1538417 341, C2=2591989193

СИНХРОПОСЫЛКА S=134987665736005221

ТАБЛИЦА ПОДСТАНОВОК Kij

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

K(1)

1

0

0

1

5

9

8

4

6

5

2

3

13

12

7

4

K(2)

0

3

8

1

11

13

6

10

2

15

7

4

14

5

12

9

K(3)

4

7

13

5

0

3

12

1

9

8

10

14

6

2

11

15

K(4)

10

15

2

12

9

14

7

6

8

4

0

13

3

11

5

1

K(5)

6

1

4

10

2

12

0

15

8

13

3

11

5

9

14

7

K(6)

8

11

7

14

15

5

12

2

0

9

10

1

6

13

3

4

K(7)

11

5

9

4

3

1

15

8

7

2

14

0

13

12

10

6

K(8)

4

13

15

5

0

3

12

7

10

11

8

9

6

1

14

2

Международный алгоритм шиф­ро­ва­ния дан­ных IDEA

Шифр IDEA (International Data Encryption Algorithm) был разработан Лэй  и Мэсси  из ETH в Цюрихе. Этот шифр, наряду с RSA, применяется в популярной компьютерной криптосистеме PGP (Pretty Good Privacy).

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

Графическая схема алгоритма IDEA

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

·      

если A+B=>2, то A^B=А+B-2

если A+B<2 , то A^B<А+B, где A и B 1-битные числа.

·       16;

если A+B=>216, то A(+)B=A+B-216

если A+B<216 , то A(+)B=A+В, где A и B 16-битные числа.

·       16+1;

если A* B=>216+1, то A(*)B=A*B-216-1

если A* B<216+1 , то A(*)B=A*B, где A и B 16-битные числа.

Процесс шифрования представляет собой цикл из восьми шагов:

На первом шаге:

p1 (*) s1 --> d1             p2 (+) s2 --> d2           p3 (+) s3 --> d3           p4 (*) s4 --> d4

d1 ^ d3 --> d5               d2 ^ d4 --> d6

d5 (*) s5 --> d7             d6 (+) d7 --> d8          d8 (*) s6 --> d9           d7 (+) d9 --> d10

d1 ^ d9  --> d11                        d3 ^ d9  --> d12          d2 ^ d10 --> d13         d4 ^ d10 --> d14

p1, p2, p3, p4 – четыре 16 битных блока, на которые разбиваются один блок исходного текста

s1, s2, s3, s4, s5, s6 – шесть 16 битных подключей.

На следующем шаге в качестве p1, p2, p3, p4 используют d11, d13, d12, d14 и новые шесть подключей. Полученные четыре последние 16 битных блока и есть зашифрованный текст. Процесс дешифрования осуществляется аналогично.

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

Подключи для дешифрования определяются таблицей:

1 шаг                                                   s49*  s50#  s51#  s52*  s47  s48

2 шаг                                                   s43*  s45#  s44#  s46*  s41  s42

3 шаг                                                   s37*  s39#  s38#  s39*  s35  s36

4 шаг                                                   s31*  s33#  s32#  s34*  s29  s30

5 шаг                                                   s25*  s27#  s26#  s28*  s23  s24

6 шаг                                                   s19*  s21#  s20#  s22*  s17  s18

7 шаг                                                   s13*  s15#  s14#  s16*  s11  s12

8 шаг                                                   s7*   s9#   s8#   s10*  s5   s6

Последнее преобразование              s1*   s2#   s3#   s4*

sXX* = мультипликативная инверсия sXX по  модулю 216+1

sXX# = аддитивная инверсия sXX по  модулю 216

Алгоритм RSA

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

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

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

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

исходный

текст

Система

с открытым ключом

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

исходный

текст

Система

с открытым ключом

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

Шифрованный текст

Отправитель

Адресат

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

Ал­го­рит­мы шиф­ро­ва­ния с от­кры­тым клю­чом по­лу­чи­ли ши­ро­кое рас­про­стра­не­ние в со­вре­мен­ных ин­фор­ма­ци­он­ных сис­те­мах. Так, ал­го­ритм RSA стал ми­ро­вым стан­дар­том де-фак­то для от­кры­тых сис­тем.

Ал­го­рит­мы криптосистем с открытым ключом мож­но ис­поль­зо­вать в 3 на­зна­че­ни­ях.

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

2. Как сред­ст­ва для рас­пре­де­ле­ния клю­чей.

3. Сред­ст­ва ау­тен­ти­фи­ка­ции поль­зо­ва­те­лей.

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

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

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

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

Пусть n=p*q, где p и q - различные простые числа, и e и d удовлетворяют уравнению

e*d (mod  (p-1)*(q-1))= 1

Если p и q - достаточно большие простые числа, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA.

{e,n} образует открытый ключ, а {d,n} - закрытый (можно взять и наоборот).

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

Шифрование осуществляется по формуле: Sшифр = Se  mod N

Шифрование осуществляется по формуле: S = Sdшифр  mod N

Где S – исходный текст, Sшифр – преобразованный текст, при этом S < N

Оценка надежности криптосистем

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

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

1)         использования достижений научно-технического прогресса и применения технологических новинок для увеличения производительности отдельного устройства;

2)                  увеличения количества таких устройств в системе.

C физической точки зрения тот тип транзистора, который является основой современной интегральной схемы, может быть уменьшен еще примерно в 10 раз, до размера 0,03 мк. За этой гранью процесс включения/выключения микроскопических переключателей станет практически невозможным. Таким образом максимальное быстродействие составит - 1016 операций/секунду, а предел роста наступит приблизительно в 2030 г.

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

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

с мощностью порядка 1012 FLOPS 3 экз.;

с мощностью порядка 1011 FLOPS 54 экз.;

с мощностью порядка 1010 FLOPS 428 экз.;

с мощностью порядка 109 FLOPS 251 экз.

Десять самых мощных суперкомпьютеров в мире по состоянию на июль 1999 г.

PRIVATEРейтинг

Наименование машины

Страна-обладатель

Фирма-производитель

Количество процессоров

Мощность (GFLOPS)

1

Intel ASCI Red

США

Intel (США)

9125

1333

2

Hitachi/Tsukuba

CP-PACS

Япония

Hitachi/Tsukuba (Япония)

2048

368

3

SGI/Cray T3E

Великобритания

Cray (США)

696

265

4

Fujitsu Numerical Wind Tunnel

Япония

Fujitsu (Япония)

167

230

5

Hitachi SR2201

Япония

Hitachi (Япония)

1024

220

6

SGI/Cray T3E

Германия

Cray (США)

512

176

7

SGI/Cray T3E

США

Cray (США)

512

176

8

SGI/Cray T3E

Германия

Cray (США)

512

176

9

SGI/Cray T3E

США

Cray (США)

512

176

10

SGI/Cray T3E

США

Cray (США)

512

176

Первое место в мире по количеству суперкомпьютеров занимают США 254 (51%). За ними следуют Япония 87 (17,5%), Германия 45 (9%), Великобритания 24 (4,8%), Франция 18 (3,6%), Корея 8 (1,6%), Канада 7 (1,4%), Швеция, Швейцария и Норвегия по 6 (1,2%). Россия упомянута в этом списке лишь один раз: на 156-ом месте находится компьютер HPC Ultra 10000 (пиковая производительность 16600 MFLOPS), произведенный фирмой SUN и установленный в Национальном Резервном Банке России. Интересная деталь: в США отсутствуют компьютеры иностранного производства американцы работают только на отечественных машинах и к тому же снабжают ими весь остальной мир.

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

1999 786 установок

1998 638 установок

1997 207 установок

1996 168 установок

1995 52 установки

1994 45 установок

1993 16 установок

1992 10 установок

Допустим, что рассматриваемые нами алгоритмы шифрования идеальны, то есть оптимальным методом их взлома будет прямой перебор всех возможных ключей данного алгоритма. Очевидно, что в этом случае стойкость криптосистем будет определяться длиной ключа. При проведении данного исследования предполагалось, что криптоаналитик противной стороны обладает всей информацией относительно алгоритма шифрования, за исключением данных о секретном ключе, и ему доступен для анализа шифрованный текст сообщения. По определению предполагается, что идеальный алгоритм лишен каких-либо недостатков, снижающих его криптостойкость. Для шифров ГОСТ-28147-89 и IDEA существенных недостатков в настоящее время не выявленно.

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

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

PRIVATEНаименование

машины

Мощность (FLOPS)

56 бит

7.2*Е16

64 бита

1.8*E19

70 бит

1.18*Е21

75 бит

3.78*Е22

128 бит

3.4*E38

256 бит

1.15*Е77

Intel ASCI Red

1.333*Е12

14 часов

5 мес.

28 лет

899 года

8.09*Е18

2.72*Е57

Hitachi/Tsukuba CP-PACS

3.68*Е11

52 часа

18 мес.

102 года

3257 лет

2.93*Е19

9.9*Е57

SGI/Cray T3E

2.65*Е11

69 часов

51 мес.

141 года

4523 года

4.07*Е19

1.37*Е58

Fujitsu Numerical Wind Tunnel

2.3*Е11

171 час

60 мес.

162 года

5211 года

4.69*Е19

1.58*Е58

Hitachi SR2201

2.2*Е11

178 часов

61 мес.

170 лет

5448 лет

4.9*Е19

1.66*Е58

Таким образом с помощью указанной рабочей модели можно оценивать надежность проектируемых и эксплуатируемых систем шифрования. Алгоритм ГОСТ 28147-89 использует таблицу подстановок размером 512 бит. Общее число возможных таблиц составляет 1.33*Е36 и полное время перебора составляет 3.162*Е16 лет. Для алгоритма IDEA длина ключа составляет 128 бит и полное время перебора составляет 8.09*Е18 лет. Даже если будет использован суперкомпьютер состоящий из ста тысяч процессоров с максимально возможной скоростью в 1016 операций/секунду для расшифровки ГОСТа понадобится 4.21*Е7 лет, а для IDEA - 1.08*Е10 лет. Очевидно, что даже применение нескольких сотен суперкомпьютеров Intel ASCI Red, стоимостью по 55 миллионов долларов каждый, не в стоянии кардинально улучшить ситуацию.

алгоритм RSA

Оцен­ки тру­до­ем­ко­сти раз­ло­же­ния про­стых чи­сел (1994 год)

N

Число операций

Длина

Примечания

E50

1.4*1010

166 бит

Раскрываем на суперкомпьютерах

E100

2.3*1015

332 бит

На пределе современных технологий

E200

1.2*1023

664 бит

За пре­де­ла­ми со­вре­мен­ных тех­но­ло­гий

E300

2.7*1034

996 бит

Тре­бу­ет су­ще­ст­вен­ных из­ме­не­ний в тех­но­ло­гии

E500

1.3*1051

1660 бит

Не раскрываем

Оцен­ки тру­до­ем­ко­сти раз­ло­же­ния про­стых чи­сел (2000 год)

N

Число операций

Длина

Максимальное время дешифровки на суперкомпьютере Intel ASCI Red

E50

1.4*1010

166 бит

0.01 сек.

E100

2.3*1015

332 бит

29 сек.

E200

1.2*1023

664 бит

2854 года

E300

2.7*1034

996 бит

6.425*Е14 лет

E500

1.3*1051

1660 бит

3.092*Е31 лет

В кон­це 1995 го­да уда­лось прак­ти­че­ски реа­ли­зо­вать рас­кры­тие шиф­ра RSA для 500-знач­но­го клю­ча. Для это­го с по­мо­щью се­ти Ин­тер­нет бы­ло за­дей­ст­во­ва­но 1600 ком­пь­ю­те­ров. Сами авторы RSA рекомендуют использовать следующие размеры модуля  N:

·    

·    

·    

Немаловажный аспект реализации RSA - вычислительный. Ведь приходится использовать аппарат длинной арифметики. Если используется ключ длиной k бит, то для операций по открытому ключу требуется О(k2) операций, по закрытому ключу - О(k3) операций, а для генерации новых ключей требуется О(k4) операций. В связи с развитием вычислительной технике оценки, данные Шроппелем, устарели, так шифр RSA длиной 100 знаков дешифровывается в течение нескольких секунд на суперкомпьютере Intel ASCI Red. В отличие от симметричных криптосистем, надежность которых с увеличением длина ключа возрастает экспоненциально, для метода RSA надежность возрастает лишь логарифмически. Преобразование информации по методу RSA осуществляется значительно медленнее. Недавно разработан новый тип атак, основанный на последовательном измерении времен, затрачиваемых на выполнение операции возведения в степень по модулю целого числа. Ей подвержены по крайней мере следующие шифры: RSA, Диффи-Хеллман (вычисление дискретного логарифма) и метод эллиптических кривых. Также RSA подвержен атаке с заданным текстом (Для известного  текста, зашифрованного известным открытым ключом, подбираются закрытые ключи).

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

Предположим, что размер процессора равен размеру атома. Тогда в наших обозначениях быстродействие гипотетического процессора выразится формулой F = Vc/Ra = 3 * 1018 операций в секунду, где Vc = 3 * 10 8 м/с скорость света в вакууме, а Ra = 10-10 м - размеры атомов. Столько раз за 1 секунду свет пройдет размеры атома. Поскольку период обращения Земли вокруг Солнца составляет 365,2564 суток или 31 558 153 секунд, то за один год такой процессор выполнит 94 674 459 * 1018 » 1026 операций.

Этому процессору понадобится 1.15*Е51 лет для перебора 256 битного ключа. Более быстрый процессор в нашей вселенной невозможен в принципе, поэтому более быстро производить дешифрование методом тотального перебора ключей принципиально невозможно. Таким образом, прогноз будущего силовой атаки на основе распределенных вычислений неутешителен. Cиловая атака на криптосистемы бесперспективна. Однако, недостатки алгоритмов могут существенно сократить число вариантов перебора. Использование в качестве ключей осмысленных слов позволяет применять атаку по словарю. Следовательно, в дальнейшее развитие криптографии будет происходить в области криптоанализа.

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

1.    Баричев С. Криптография без секретов. М., 1998

2.    Брассар Дж. Современная криптология. 1988

3.    Жельников В. Криптография от папируса до компьютера. М., 1996

4.    Йолнен Тату. Введение в криптографию. 1999

5.    Спесивцев А. В. Защита информации в персональных ЭВМ. М., 1992

6.        Шнайер Брюс. Прикладная криптография. 1994