Занимательная криптография(обзорная статья)

[brainstorm 0]

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

Вот все твердят, криптография, криптография... Так что же это, в сущности, такое?

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

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

Если секретность информации обусловлена секретностью алгоритма, то это т. наз. ограниченный алгоритм, как правило он недостаточно безопасен. У хорошего же криптоалгоритма секретность информации защищена не секретностью алгоритма, а секретностью самого ключа. Ключ – это сердце криптоалгоритма, его квинтэссенция, некий уникальный файл(массив битов), так же “запирающий-отпирающий” шифротекст, как его железный сородич делает это с замком. Множество всех возможных для данного алгоритма ключей называют ключевым пространством.

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

Также симметричные криптоалгоритмы делятся на потоковые, когда информация обрабатывается побитово, и блочные, когда информация обрабатывается массивами из 64 или кратного 64 бит числа.

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

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

До появления компьютерной техники криптография осуществлялась на символьной основе при помощи смещений и подстановок. Таким был, к примеру, знаменитый шифр Юлия Цезаря, заключавшийся в смещении каждого символа на 3 позиции вправо по модулю 26(число букв лат. алфавита), D вместо A, E вместо B, …. , A вместо X, B вместо Y... Да ещё этот текст наносили несмываемой тушью на выбритую налысо голову гонца, которая потом по дороге обрастала волосами, а чтобы прочитать шифровку, голову опять брили. Такого рода шифры весьма наивны, поскольку не маскируют частоту использования символов и для их вскрытия необходимо знать только сам латинский алфавит! Немного похитрее полиалфавитные шифры, в которых каждая следующая буква шифруется собственным ключом с некоторым циклическим периодом – такими шифрами пользовались американцы времён Гражданской войны; сейчас подобные ухищрения вскрываются программно за секунды. Именно такого рода – известные шифры Бофора и Вигенера. С изобретением машин для такого шифрования стали использоваться роторные механизмы, подобные тому, который применялся в немецкой шифровальной машинке Энигма времён 2МВ.

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

С изобретением компьютеров основой шифрования стала побитовая логическая операция XOR - исключающее или( 0 XOR 0 = 0 ; 1 XOR 0 = 1 ; 0 XOR 1 = 1 ; 1 XOR 1 = 0 ). По сути, это сложение по модулю 2, в отличие от mod 26 при посимвольном шифровании. Оно примечательно тем, что повторный XOR данного битового массива с одним и тем же ключом даёт возвращение исходного текста! Самые распространённые криптографические алгоритмы на сегодняшний день – это симметричные DES и AES/Rijndael и асимметричные RSA, Diffy-Hellman и Fiat-Shamir.

Надёжность шифрования.

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

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

Что же до длины ключа, то для ключа длиной 8 бит надо будет перебрать 2 в 8-ой степени; для ключа в 56 бит – 2 в 56-ой степени. Если компьютер взломщика способен перебирать миллион ключей в секунду, взлом ключа займёт 2285 лет. Если длина ключа равна 128 битам, то брутфорс с данной скоростью займёт 10 в 25-ой степени лет, что превышает возраст вселенной(ок. 10 в 10-ой всего лишь!)

Майкл Винер сконструировал машину со множеством независимых процессоров стоимостью порядка 1 млд.долл., которая 56-битный ключ DES может взломать за 3,5 – 7 часов в среднем. В настоящее время такие ресурсы доступны крупным коммерческим структурам и криминальным организациям. 64-битный ключ могут взломать брутфорсом спецслужбы свехдержав и их военные структуры. 80 — битный ключ уже не кажется столь безопасным, учитывая прогресс компьютерной техники. Но 128 битный ключ делает мысль о брутфорсе невозможной – даже если бросить на него все существующие на планете миллиарды процессоров, его время всё равно будет в миллионы раз выше времени жизни вселенной!

Безопасность алгоритма RSA(Ривеста-Шамира-Аделсона) основана на трудности разложения на множители больших чисел. Открытый и закрытый ключи являются функциями двух больших(100-200 и больше разрядов) чисел. Восстановление открытого текста по шифротексту и открытому ключу аналогично разложению на множители больших чисел. Открытый ключ RSA длиной 2048 бит аналогичен по безопасности приблизительно 128-битному ключу симметричного криптоалгоритма.

[orange 0]

До сих пор пользуюсь Энигмой, проблем не возникало

[LemonSorbet 1]

где-то я уже это видела