S'=(SD) MOD N=165016813 MOD 47053=3071

Шифры взбивания и стандарт DES.

Стойкость шифра можно ощутимо улучшить, если вместо перестановки использовать линейное преобразование:

S = L * t

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

Доля невырожденных матриц с увеличением их размера стремительно

убывает. Детерминант матрицы L, как и ее элементы, может быть равен либо 0, либо 1. Если det(L)=0, то матрица вырождена. Поскольку известно, что для матрицы, составленной из квадратных подматриц А, В, С и D, имеем:

│ А В│

│ │ = det(A)det(B) - det(C)-det(D)

│ C D│

и, обозначив через Pn вероятность равенства единице детерминанта случайной матрицы размером 2**n, получаем следующее рекуррентное выражение:

P(n+1)=2*Pn*Рn*(1-Pn*Pn).

Так как P1=0. 5, то увеличение n влечет быстрое убывание невырожденных матриц среди случайных.

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

Входной блок данных делится пополам на левую L' и правую R'

части. После этого формируется выходной массив так, что его левая часть L" представлена правой частью R' входного, а правая R" формируется как сумма L' и R' операцией XOR. Далее, выходной массив шифруется перестановкой с заменой. Можно убедиться, что все проведенные операции могут быть обращены и расшифровывание осуществляется за число операций, линейно зависящее от размера блока. В то же самое время, после нескольких таких взбиваний можно считать, что каждый бит выходного блока шифровки может зависеть от каждого бита сообщения.

Система шифрования DES была разработана IBM под именем Lucifer и предложена со своими корректировками Национальным Бюро Стандартов США в 1976 году как стандарт шифрования. В ней применен ключ из 56 би т. Свое развитие DES получил в ГОСТ 28147-89, который увеличил длину ключа до 256 бит и допустил произвольные перестановки.

Шифр DES принят федеральным стандартом США, и хорош в использовании для многих коммерческих приложений. Однако правительства сами никогда не используют шифры, предлагаемые коммерсантам, чтобы закрыть свои данные, так как они недостаточно стойки от атак аналитиков. Например, 16-кратный DES был взломан Шамиром, применявшим дифференциальный криптоанализ, и Матсуи, использовавшим линейный криптоанализ. Наиболее серьезную практическую атаку на DES осуществил Мишель Винер, который разработал и опробовал микросхему, проверяющую в секунду 50 миллионов ключей DES. ЭВМ, стоящая миллион долларов и содержащая несколько десятков тысяч таких микросхем, способна перебрать все ключи DES за 7 часов.

Шифр Энигмы

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

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

Слабость шифра:

1. Пять барабанов могли обеспечить лишь около ста миллионов ключей, что позволяло их за день перебрать на ЭВМ. Если использовать не 25 латинских символов, а 256 кодов ASCII и увеличить число барабанов, то сложность раскалывания шифра существенно возрастет.

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

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

Подсчитаем число ключей такого шифра, реализованного программно. Пусть длина периода программного генератора случайных чисел равна 2**24. Восемь барабанов, генерируемые с помощью этого генератора, дадут вместе 2**192 вариантов ключа, а если учесть еще варианты псевдослучайной последовательности, управляющей движением барабанов, то получится внушительная цифра в 2**216 вариантов ключа. Таким образом, довольно просто получить устойчивый шифр даже при использовании программного генератора случайных чисел с периодом малой для криптографии длины. И хотя несоненно, что криптоаналитики наработали массу " домашних заготовок" для атак на такой шифр, вскрытие шифра Энигмы будет дорого стоить.

Широкое применение нашел похожий на DES алгоритм IDEA ( IDEA - Improved Proposed Encryption Standard - улучшенный стандарт шифрования. ), отличающийся применением ключа длиной 128 бит и смещением операций разных алгебраических групп для блоков длиной 64 бита. Алгоритм IDEA разработан в Цюрихе Джеймсом Мэсси и опубликован в 1990 году. Он выдержал множество атак на него в отличие от алгоритмов FEAL, REDOC-11 и LOKI. IDEA выдержал атаки криптографов многих развитых стран, как Англии, Германии и Израиля. Он считается более стойким, чем традиционный DES, и представляет основу программы шифрования PGP, применяемой пользователями Интернет. Разработчик PGP, Фил Циммерман, сейчас подвергнут в США уголовному преследованию за экспорт криптостойких шифров. Дело " Правительство США против Филиппа Циммермана" приравняло Фила к торговцам оружием и наркотикам.

ШИФРЫ С ОТКРЫТЫМ КЛЮЧОМ

Этапы развития криптографии в XX веке:

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

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

3. Началом третьего периода развития криптоло гии обычно считают 1976 год, когда американские математики Диффи и Хеллма н предложили принципиально новый вид организации засекреченной связи без предварительного снабжения абонентов секретны миключами, такназываемое шифрование с открытым ключом. В результате стали появляться криптографические системы, основанные на подходе, сформулированном еще в сороковых годах Шенноном. Он предложил строить шифр таким способом, чтобы его раскрытие было эквивалентно решению математической задачи, требующей выполнения объемов вычислений, превосходящих возможности современных ЭВМ. Новый период развития криптографии характеризуется появлением полностью автоматизированных систем шифрованной связи, в которых каждый пользователь имеет свой индивидуальный пароль для подтверждения подлинности, хранит его, к примеру, на карте, и предъявляет при входе в систему, а весь остальной процесс проведения секретной связи происходит автоматически.

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

При шифровании с открытым ключом для шифрования и дешифрования используются разные клю чи, и знание одного из них не дает практической возможности определить второй. Поэтому ключ для шифрования может быть сделан общедоступным без потери стойкости шифра, если ключ для дешифрования сохраняется в секрете, например, генерируется и хранится только получателем информации. Сейчас два метода шифрования с открытым ключом получили признание и закреплены в стандартах. Национальный институт стандартов и технологий США NIST (бывший ANSI) принял стандарт MD 20899, основанный на алгоритме ЭльГамаля, а на основе алгоритма RSA приняты стандарты ISO/IEC/DIS 9594-8 международной организацией по стандартизации и Х. 509 международным комитетом по связи.

Шифр Ривеста-Шамира-Алдемана (RSA)

Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году так называемая система RSA. Ее название происходит от первых букв фамилий авторов R ivest, S hamir и A ldeman, которые придумали ее во время совместных исследований в М ассачусетском Технологическом И нституте в 1977 году. Она основана на трудности разложения очень больших целых чисел на простыесомножители. Международная сеть электронного перечисления платежей SWIFT уже требует от банковских учреждений, пользующихся ее услугами, применения именно этой криптографической системы.

Алгоритм ее работает так:

1. Отправитель выбирает два очень больших простых числа P и Q и вычисляет два произведения N=PQ и M=(P-1)(Q-1).

2. Затем он выбирает случайное целое число D, взаимно простое с М, и вычисляет Е, удовлетворяющее условию DE = 1 MOD М.

3. После этого он публикует D и N как свой открытый ключ шифрования, сохраняя Е как закрытый ключ.

4. Если S - сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале (1, N), то оно превращается в шифровку возведением в степень D по модулю N и отправляется получателю S'=(S**D) MOD N.

5. Получатель сообщения расшифровывает его, возводя в степень E по модулю N, так как S = (S'**E) MOD N = (S**(D*E)) MOD N.

Таким образом, открытым ключом служит пара чисел N и D, а секретным ключом число Е. Смысл этой системы шифрования становится прозрачным, если упомянуть про малую теорему Ферма, которая утверждает, что при простом числе Р и любом целом числе К, которое меньше Р, справедливо тождество К**(P-1)=1 MOD Р. Эта теорема позволяет определять, является ли какое-либо число

простым или же составным.

Пример на малых простых числах P=211 и Q=223. В этом случае N=47053 и М=46620. Выберем открытый ключ шифрования D=16813 и вычислим секретный ключ расшифровывания Е=19837. Теперь, взяв за сообщение название метода RSA, переведем

его в число. Для этого будем считать букву R равной 18, S равной 19, А равной 1 по порядковому номеру их положения в английском алфавите. На представление каждой буквы отведем по 5 бит числа, представляющего открытый текст. В этом случае слову RSA соответствует следующее число: S=((1*32)+19)*32+18=1650.

С помощью открытого ключа получаем шифровку:

S'=(S**D) MOD N=1650**16813 MOD 47053=3071

Получатель расшифровывает ее с помощью секретного ключа: