Эволюция криптографии: от математики до физики

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

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

Немного истории

Слова «криптология» и «криптография» в современной литературе часто используются как взаимозаменяемые термины, но между ними есть семантическая разница. У слов различные значения, которые проще всего объяснить так:

• Криптология — учение об искусстве секретности и/или наука о работе криптосистем;
• Криптография — практический способ применения методов проектирования криптосистем, чтобы сделать что-то секретное или скрытое;
• Криптоанализ — поиск уязвимостей, которые позволят восстановить исходное сообщение из шифротекста без знания ключа или алгоритма.

Большая часть статьи посвящена «криптографии», как это принято сегодня, и хотелось бы, чтобы вы знали различия и значения обоих слов.

Само по себе изучение криптологии как науки существует уже много лет. Первый известный случай использования криптографии был обнаружен в надписи, высеченной в 1900 году до нашей эры, в главной гробнице дворянина Хнумхотепа II, в Египте. Писец (да) то тут, то там использовал некоторые странные иероглифы вместо обычных. Целью было скорее не спрятать сообщение, а изменить его форму, чтобы оно выглядело более величавым.

Во время расцвета Римской Империи (100-й год до нашей эры) Юлий Цезарь, как известно, использовал форму шифрования для передачи секретных сообщений своим армейским генералам во время войны. Этот шифр подстановки (шифр Цезаря), вероятно, самый упоминаемый в литературе исторический шифр (шифр — алгоритм, используемый для шифровки или дешифровки сообщений). В шифрах подстановки каждая буква исходного сообщения (исходное сообщение — текст, который будет зашифрован) заменяется на другую букву, находящуюся правее или левее исходной по алфавиту, для получения шифротекста (шифротекст — зашифрованное сообщение). В шифре Цезаря используется сдвиг вправо на 3 позиции, так что «A» становится «D», «B» — «E» и т. д. Алфавит в данном случае будет замкнут и после «X» следует «A».

Во время Второй мировой войны морские пехотинцы США завербовали и обучили людей из племени индейцев навахо, свободно владеющих языком навахо. Это был привлекательный способ использования кодирования, мало людей не из племени знали этот язык, а также не было никаких опубликованных книг на языке навахо. Речевой язык навахо был не очень сложен по криптографическим стандартам и, вероятно, был бы быстро взломан при взаимном сотрудничестве носителя языка и обученных криптографов. У японцев была возможность сделать это, когда в 1942 году на Филлипинах они пленили Джо Кийомию во время Марша смерти в Батаане. После попадания в плен Кийомия, навахо-сержант в армии США, но не носитель кода, получил приказ расшифровать перехваченное радиосообщение. Однако, так как Кийомия не был обучен коду, используемому военными службами США, то слова ему показались ничего не значащими. Когда он доложил, что не может понять перехваченные сообщения, его начали пытать. Японская Имперская Армия и ВМС так и не взломали устный код.

В начале 1970-х компания IBM осознала, что их пользователи требуют какой-нибудь вид шифрования, и сформировала «криптогруппу», возглавляемую Хорстом Фейстелем. Они спроектировали шифр под названием Lucifer. В 1973 году Национальное бюро стандартов США (сейчас NIST — Национальный институт стандартов и технологий США) объявило конкурс на блочный шифр, который должен был стать национальным стандартом. Видимо, они наконец-то осознали, что покупают множество коммерческого ПО без хорошей криптографической поддержки. В конце концов, Lucifer приняли и переименовали в DES (Data Encryption Standard). DES был взломан методом полного перебора в 1997 году. Главной уязвимостью DES была маленькая длина ключа. Когда вычислительная мощность компьютеров увеличилась, то метод полного перебора стал возможен для получения исходного сообщения. И если в 1980-х годах DES был единственным вариантом, то сейчас это изменилось. Сегодня у нас есть широкий выбор более сильных, быстрых и улучшенных алгоритмов. Сейчас проблематично выбрать среди них нужный.

В 1997 году NIST объявил конкурс на новый блочный шифр и получил 50 заявок. В 2000 году был принят Rijndael и назван AES (Advanced Encryption Standard).

Основы

Шифрование — это процесс изменения данных таким образом, чтобы они стали неузнаваемыми и бесполезными для несанкционированного лица. А дешифрование — процесс превращения данных в их первоначальный вид. Наиболее безопасные виды шифрования используют математические алгоритмы и переменную — «ключ». Выбранный ключ (зачастую любая случайная последовательность) вводится при шифровании и является неотъемлемой частью изменения данных. Тот же самый ключ необходим для дешифровки сообщения.

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

Основные причины, по которым требуется криптография:

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

Шифры

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

Чтобы лучше понять эти шифры, рассмотрим простенький пример.

Квадрат Полибия

Квадрат Полибия — шифр простой замены. В данном примере будет использоваться двумерная матрица 6х6, содержащая заглавные буквы алфавита и цифры от 0 до 9.

Матрица будет выглядеть следующим образом:

С матрицей 6х6 (36 буквенно-цифровых знаков) мы можем начать замену. Например, буква «А» имеет адрес 1х1 или x=1, y=1. Эту запись можно упростить до 11. Другой пример: адрес буквы «N» будет 2х3 или x=2, y=3 или 23.

Давайте зашифруем простое сообщение:

Сообщение: ENCRYPT ME 2 DAY

Шифротекст: 51–23–31–63–15–43–24 13–51 55 41–11–15

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

Шифр Цезаря

Шифр Цезаря, названный в честь его создателя — Юлия Цезаря, считается самым первым шифром, изобрётенным человечеством. Цезарь использовал его для кодирования сообщений своим генералам, чтобы враги из Римской Империи не смогли прочитать приказы при перехвате. Шифр Цезаря имеет элементарную форму шифрования, и его очень легко взломать. По этой причине сейчас он не используется для шифрования каких-либо серьёзных данных.

Шифр Цезаря просто сдвигает алфавит вправо или влево. Разные значения сдвига приводят к разным результатам шифровки. Число сдвига — это число букв, на которое происходит смещение в одну из сторон, для создания шифротекста. Пример использования шифра со сдвигом влево на 3:

Сообщение: ENCRYPT ME

Шифротекст: HQFUBSW PH

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

Прим. пер. Существует более простой способ взлома шифра Цезаря — частотный анализ, о котором автор не упоминает. Он заключается в подсчёте частоты встреч каждого символа в любом обычном тексте и в шифротексте. Потом символы с похожими частотами заменяются. Например, если в шифротексте чаще всего встречается буква «T», то она заменяется на букву «Е» для английского алфавита. Этот способ действует только для текстов свыше 300 символов.

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

Квадрат Виженера

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

Полиморфизм

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

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

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

Распространённые алгоритмы

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

В 1949 году Клод Шеннон из Bell Laboratories опубликовал фундаментальную теорию, положившую начало симметричному шифрованию, а десятилетия эволюции принесли примеры высокого качества. Однако только в 1975 году мощный алгоритм с закрытым ключом DES стал доступен для общего пользования.

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

Стойкость шифровального алгоритма зависит от трёх важных факторов:

• Инфраструктура — Если криптография встроена в ПО, то самым слабым звеном будет среда выполнения этого ПО. Если вы пытаетесь сохранить сообщение в секрете, то хакеру будет проще всего взломать компьютер и украсть сообщение ещё до того, как оно будет зашифровано. Пробраться в систему или заразить её вирусом всегда будет легче, чем подобрать закрытый ключ неизвестной длины. В большинстве случаев самый лёгкий способ раскрытия секретного ключа — подслушать пользователя и перехватить ключ.
• Длина ключа — В криптографии длина ключа имеет большое значение. Если злоумышленник не сможет установить кейлогер, то лучшим способом взломать шифротекст будет ключ, подобранный путём проб и ошибок, т.е. методом полного перебора. Практичный шифр должен использовать такую длину ключа, при которой полный перебор будет нецелесообразным. Однако, так как аппаратные мощности с каждым годом увеличиваются, то длина «безопасного» ключа продолжает расти. Эксперты признают, что ключи длиной 64 бита и меньше, включая ключи DES, стали уязвимы для определённого вида атак. В 1999 Фонд Электронных Рубежей (англ. Electronic Frontier Foundation, EFF) профинансировал разработку устройства под названием Deep Crack, которое смогло подобрать ключ шифрования DES за три дня и меньше. Длина современных ключей шифрования всегда начинается от 100 бит.
• Качество алгоритма — О качестве алгоритма довольно сложно судить. И если создать рабочий шифр на основе существующего алгоритма легко, то это не спасёт от возможного наличия мелких недостатков. Они могут привести к быстрому взлому, если эксперты внимательно изучат этот шифр. Ошибки шифрования могут ускорить процесс взлома для злоумышленников.

Пример из жизни: популярный файловый архиватор PKZIP обычно применял встроенный алгоритм шифрования, который использовал 64-битный ключ. В теории для проверки всех ключей понадобилось бы 2^64 попытки. Но на практике оказалось, что в шифровании есть недостаток, который позволил сократить количество попыток взлома шифротекста до 2^27.
Единственный способ найти такие недостатки — попытаться взломать алгоритм шифрования на практике, используя трюки, сработавшие на других алгоритмах. О качестве алгоритма можно судить после того, как алгоритм подвергли тщательному анализу и попытались взломать. Но даже это не спасает от возможности того, что позже кто-то другой найдёт недостатки в алгоритме шифрования.

Виды алгоритмов

DES выдержал испытание временем, потому что качество шифрования доказывалось на протяжении многих лет опубликованных исследований. После четверти века исследований учёным удалось найти несколько спекулятивных атак, которые в конечном итоге не были столь эффективными, как метод полного перебора. Единственная реальная слабость DES-шифра — его критически маленькая длина ключа в 56 бит.

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

AES (Advanced Encryption Standard или Rijndael) поддерживает три длины ключа 128, 192 и 256 бит и использует 128-битный размер блоков. В настоящее время он считается достаточно стойким и используется по всему миру.

Алгоритм шифрования Rijndael

Так как DES был специально разработан для аппаратного обеспечения, то не было предусмотрено, чтобы он эффективно работал в ПО. NIST протестировал работу алгоритма AES в программной среде и разработал требования к хранению криптоматериала, чтобы гарантировать, что AES будет эффективно работать на C и Java, которые используются на рабочих станциях, а также в более ограниченных средах встроенный процессоров ARM и смарт-карт.

Архитектура AES основана на принципе, известном как замена и перестановка, и быстро работает как в программном, так и на аппаратном уровнях. В отличие от своего предшественника — DES, AES не использует сеть Фейстеля (прим. пер. — один из методов построения блочных шифров). AES — это вариант Rijndael с фиксированной длиной блоков в 128 бит и критическим размером 128, 192 и 256 бит. Напротив, спецификации Rijndael задаются длиной блоков и ключей, которые могут быть кратными 32 в диапазоне от 128 до 256 бит.

AES работает с матрицей порядка 4х4 столбцов с байтами, называемой состоянием, хотя некоторые версии Rijndael имеют больший размер блоков и дополнительные столбцы. Большинство расчётов AES выполняются в определённом конечном поле.

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

• 10 циклов повторения для 128-битных ключей;
• 12 циклов повторения для 192-битных ключей;
• 14 циклов повторения для 256-битных ключей.

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

Смотрите также: 10 популярных кодов и шифров

Квантовая криптография

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

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

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

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

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

Источник: tproger.ru

Комментарии: