Шифрование методом Вернама
Система шифрования Вернама является в сущности частным случаем системы шифрования Вижинера при значении модуля m = 2. Конкретная версия этого шифра, предложенная в 1926 г. Гилбертом Вернамом, сотрудником фирмы AT&T США, использует двоичное представление символов исходного текста.
Каждый символ исходного открытого текста из английского алфавита <А, В, С, D, . Z>, расширенного шестью вспомогательными символами (пробел, возврат каретки и т.п.), сначала кодировался в 5-битовый блок (b0, b1, …, b4) телеграфного кода Бодо.
Случайная последовательность двоичных ключей k0,k1,k2. заранее записывалась на бумажной ленте.
Схема передачи сообщений с использованием шифрования методом Вернама показана на рис.13. Шифрование исходного текста, предварительно преобразованного в последовательность двоичных символов x, осуществлялось путем сложения по модулю 2 символов x с последовательностью двоичных ключей k.
Рис. 13. Схема шифрования и расшифрования сообщений по методу Вернама
Расшифрование состоит в сложении по модулю 2 символов у шифртекста с той же последовательностью ключей k:
y Е k = x Е k Е k = x. (14)
При этом последовательности ключей, использованные при шифровании и расшифровании, компенсируют друг друга (при сложении по модулю 2), и в результате восстанавливаются символы x исходного текста.
При разработке своей системы Вернам проверял ее с помощью закольцованных лент, установленных на передатчике и приемнике для того, чтобы использовалась одна и та же последовательность ключей.
Следует отметить, что метод Вернама не зависит от длины последовательности ключей и, кроме того, он позволяет использовать случайную последовательность ключей. Однако при реализации метода Вернама возникают серьезные проблемы, связанные с необходимостью доставки получателю такой же последовательности ключей, как у отправителя, либо с необходимостью безопасного хранения идентичных последовательностей ключей у отправителя и получателя. Эти недостатки системы шифрования Вернама преодолены при шифровании методом гаммирования.
Роторные машины
В 20-х годах XX века были изобретены электромеханические устройства шифрования, автоматизирующие процесс шифрования. Принцип работы таких машин основан на многоалфавитной замене символов исходного текста по длинному ключу согласно версии шифра Вижинера. Большинство из них — американская машина SIGABA (М-134), английская TYPEX, немецкая ENIGMA, японская PURPLE были роторными машинами.
Главной деталью роторной машины является ротор (или колесо) с проволочными перемычками внутри. Ротор имеет форму диска (размером с хоккейную шайбу). На каждой стороне диска расположены равномерно по окружности m электрических контактов, где m — число знаков алфавита (в случае латинского алфавита m = 26). Каждый контакт на передней стороне диска соединен с одним из контактов на задней стороне, как показано на рис.14. В результате электрический сигнал, представляющий знак, будет переставлен в соответствии с тем, как он проходит через ротор от передней стороны к задней. Например, ротор можно закоммутировать проволочными перемычками для подстановки G вместо A, U вместо В, L вместо С и т.д.
Рис. 14. Банк роторов
При повороте ротора из одного положения в другое подстановка, которую он осуществляет в приходящем сигнале, будет изменяться. В общем случае эту подстановку можно записать в виде
T = C j p C -j , (15)
где p — подстановка, реализуемая ротором в его начальном положении; С — циклический сдвиг на одну позицию; C j — циклический сдвиг на j позиций.
Например, если начальная подстановка ротора p(А) = G и ротор сдвигается на три позиции (j = 3) (рис.15), то открытый текст D будет против того контакта ротора, который используется
Рис. 15. Схема формирования подстановки при сдвиге ротора (j =3)
для представления открытого текста А, а шифрованный текст J окажется против того контакта ротора, который используется для представления шифрованного текста G , и результирующая подстановка Т(D) = G при j = 3. Алгебраически это записывается в виде
Т (D) = С 3 pС -3 (D) = С 3 p (А) = С 3 (G) = J.
Роторы можно объединить в банк роторов таким образом, чтобы выходные контакты одного ротора касались входных контактов следующего ротора. При этом электрический импульс от нажатой клавиши с буквой исходного текста, входящий с одного конца банка роторов, будет переставляться каждым из роторов, до тех пор, пока не покинет банк (рис. 14).
Математически работу банка роторов можно описать в виде
Такой банк может реализовывать большое число подстановок, соответствующих различным комбинациям положений роторов. Для получения сильной криптографической системы расположение роторов должно меняться при переходе от знака к знаку сообщения.
Роторная машина состоит из банка роторов и механизма для изменения положения роторов с каждым зашифрованным знаком, объединенного с устройствами ввода и вывода, такими как устройство считывания с перфоленты и печатающее устройство.
Простейшее из возможных движений ротора — это движение по принципу одометра; оно использовалось в немецкой машине Enigma во время второй мировой войны. При шифровании одного знака правое крайнее колесо поворачивается на одну позицию. Когда это (и любое другое) колесо переместится на m позиций и совершит полный оборот, колесо, расположенное слева от него, передвинется на одну позицию, и процесс будет повторяться. Этот процесс проведет банк роторов сквозь все его возможные положения, прежде чем цикл повторится. Поскольку все роторы перемещаются с разными скоростями, период n-роторной машины составляет 26 n (при m = 26).
Для закона движения ротора желательны следующие характеристики:
• период должен быть большим;
• после шифрования каждого знака все роторы или большая их часть должны повернуться друг относительно друга.
Движение по принципу одометра оптимально в смысле первого требования, но совершенно неудовлетворительно в отношении второго требования. Улучшение движения по принципу одометра можно получить, если поворачивать каждый ротор более чем на одну позицию. Если смещения каждого ротора не имеют общих множителей с объемом алфавита m, то период останется максимальным.
Другое решение заключается в ограничении числа допустимых остановочных мест для каждого ротора за счет введения внешнего фиксирующего кольца, на котором определенным способом зафиксированы места остановок. При использовании латинского алфавита можно заставить машины поворачиваться и останавливаться следующим образом. Первому колесу разрешается останавливаться в каждой из 26 позиций, второму колесу — только в 25 позициях, третьему колесу — только в 23 позициях, и так далее до шестого колеса, которому разрешается останавливаться только в 17 позициях. Период такой роторной машины теперь составляет 101 млн, а не 26 6 »309 млн, как в случае движения по принципу одометра. Потеря в длине периода с успехом окупается полученной сложностью движения роторов. Теперь второе требование удовлетворяется довольно хорошо, поскольку каждое из колес перемещается после шифрования каждого знака и многие колеса могут двигаться друг относительно друга.
Роторная машина может быть настроена по ключу изменением любых ее переменных:
•порядка расположения роторов;
•числа мест остановки на колесо;
•характера движения и т.д.
Поскольку перекоммутировать роторы трудно, то обычно на практике машины обеспечивали комплектом роторов, в котором находилось больше роторов, чем можно одновременно поместить в машину. Первичная настройка по ключу производилась выбором роторов, составляющих комплект. Вторичная настройка по ключу производилась выбором порядка расположения роторов в машине и установкой параметров, управляющих движением машины. С целью затруднения расшифрования шифртекстов противником роторы ежедневно переставляли местами или заменяли. Большая часть ключа определяла начальные положения роторов (2б 3 =17576 возможных установок) и конкретные перестановки на коммутационной доске, с помощью которой осуществлялась начальная перестановка исходного текста до его шифрования (26!= 4·10 26 возможностей).
Роторные машины были самыми важными криптографическими устройствами во время второй мировой войны и доминировали по крайней мере до конца 50-х годов.
Невзламываемый шифр
Невзламываемый шифр (шифр Вернама) – в криптографии целый класс систем с абсолютной криптографической стойкостью, широко известных под названием «одноразовые блокноты/вкладыши». [1] .
Содержание
История создания
Соответствующий принцип был впервые отчетливо сформулирован американским ученым Гилбертом Вернамом примерно в 1917. Вернам занимался разработкой криптографических методов для использования в телетайпных машинах. В этой связи он предложил комбинировать открытый текст, представленный в виде отверстий в бумажной перфоленте, с данными, нанесенными на другую перфоленту и являющимися ключом к шифру. Ключ должен был состоять из отверстий, перфорированных в ленте случайным образом. Комбинация этих двух лент и составляла шифротекст. [2]
Описание
В оригинале, для получения шифротекста открытый текст объединяется операцией «исключающее ИЛИ» с ключом (называемым одноразовым блокнотом или шифроблокнотом). При этом ключ должен обладать тремя критически важными свойствами:
- быть истинно случайным;
- совпадать по размеру с заданным открытым текстом;
- применяться только один раз.
Возможно объединять не только биты сообщения с битами ключа, но и, например, буквы. Идею Вернама можно проиллюстрировать с привлечением шифра Виженера. Ключ для этого шифра, по мысли Вернама, должен был представлять собой случайную последовательность букв.
| Ключ | EVTIQWXQVVOPMCXREPYZ |
| Открытый текст | ALLSWELLTHATENDSWELL |
| Шифротекст | EGEAMAIBOCOIQPAJATJK |
| Шифрограмма | EGEAM AIBOC OIQPA JATJK |
Без знания ключа такое сообщение не поддается анализу. Даже если бы можно было перепробовать все ключи, в качестве результата мы получили бы все возможные сообщения данной длины плюс колоссальное количество бессмысленных дешифровок, выглядящих как беспорядочное нагромождение букв. Но и среди осмысленных дешифровок не было бы никакой возможности выбрать искомую. Когда случайная последовательность (ключ) сочетается с неслучайной (открытым текстом), результат этого (шифротекст) оказывается совершенно случайным и, следовательно, лишённым тех статистических особенностей, которые могли бы быть использованы для анализа шифра. [1]
Область применения
На практике можно один раз физически передать носитель информации с длинным истинно случайным ключом, а потом по мере необходимости пересылать сообщения. На этом основана идея шифроблокнотов: шифровальщик при личной встрече снабжается блокнотом, каждая страница которого содержит ключ. Такой же блокнот есть и у принимающей стороны. Использованные страницы уничтожаются.
Кроме того, если есть два независимых канала, в каждом из которых вероятность перехвата низка, но отлична от нуля, шифр Вернама также полезен: по одному каналу можно передать зашифрованное сообщение, по другому — ключ. Для того чтобы расшифровать сообщение, перехватчик должен прослушивать оба канала.
Шифр Вернама может применяться, если есть односторонний защищённый канал: ключ передаётся в одну сторону под защитой канала, сообщения в другую сторону защищаются ключом.
Не является шифром Вернама, но близка к нему схема одноразовых кодов: например, кодовое слово «Альфа» означает «Возвращаюсь».
Достоинства метода
В 1949 году Клод Шеннон опубликовал работу, в которой доказал абсолютную стойкость шифра Вернама. Это по сути означает, что шифр Вернама является самой безопасной криптосистемой из всех возможных. При этом требования к реализации подобной схемы достаточно нетривиальны, поскольку необходимо обеспечить наложение уникальной гаммы, равной длине сообщения, с последующим её гарантированным уничтожением. В связи с этим коммерческое применение шифра Вернама не так распространено в отличие от схем с открытым ключом и он используется, в основном, для передачи сообщений особой важности государственными структурами.
Другое преимущество состоит в том, что ключ может быть распространён заранее, а также по более медленным и надёжным каналам связи, после чего шифрограмму можно совершенно безбоязненно пересылать по обычным каналам. В результате появления микропроцессоров и дискет для хранения и распространения компьютерных данных практическая значимость «одноразовых» шифров возросла, потому что порождение и сверка относительно большого числа ключей может теперь производиться автоматически. [3]
Недостатки метода
Получение «случайного» ключа – процесс весьма непростой. С помощью математических алгоритмов можно получать последовательности, обладающие многими свойствами, которые присущи «случайности»; однако эти последовательности не являются истинно случайными. Ещё одной проблемой, связанной с использованием шифров «одноразового вкладыша», является то, что под рукой всегда необходимо иметь достаточное количество ключей, которые могут понадобиться в дальнейшем для шифрования больших объёмов открытого текста. Реальный же объём текста зачастую трудно оценить заранее, в особенности это касается дипломатической и военной сферы, где ситуация способна меняться быстро и непредсказуемо. Это может приводить к нехватке ключей, что может заставить шифровальщика либо использовать ключ(и) повторно, либо полностью прервать шифрованную связь. [3]
- Для работы шифра Вернама необходима истинно случайная последовательность нулей и единиц (ключ). По определению, последовательность, полученная с использованием любого алгоритма, является не истинно случайной, а псевдослучайной. То есть, нужно получить случайную последовательность неалгоритмически (например, используя распад ядер, создаваемый электронным генератором белый шум или другие достаточно случайные события).
- Проблемой является тайная передача последовательности и сохранение её в тайне. Если существует надёжно защищённый от перехвата канал передачи сообщений, шифры вообще не нужны: секретные сообщения можно передавать по этому каналу.
- Возможны проблемы с надёжным уничтожением использованной страницы. Этому подвержены как бумажные страницы блокнота, так и современные электронные реализации с использованием компакт-дисков или флэш-памяти.
- Если третья сторона каким-нибудь образом узнает сообщение, она легко восстановит ключ и сможет подменить послание на другое такой же длины.
- Шифр Вернама чувствителен к любому нарушению процедуры шифрования.
Применимость метода
Лёгкость порождения ключа – решающий фактор в том, что касается практической применимости шифров типа «одноразовых вкладышей». Ведь ключ должен быть точно такой же длины, что и шифруемое сообщение. Более того, никакой ключ нельзя использовать повторно, потому что данный факт часто может быть обнаружен с помощью статистических тестов и тогда те куски сообщения (или сообщений), в которых был использован тот же самый ключ, будут расшифрованы. То обстоятельство, что ключ может быть использован только один раз, и определяет «одноразовость» таких шифров. Прежде чем пересылать невзламываемую шифрограмму, необходимо передать получателю копию ключа. Поскольку ключ имеет ту же длину, что и открытый текст, одна проблема (надёжно засекреченная передача сообщения) оказывается просто замененной на другую такую же (надёжно засекреченное распространение ключа). [4]
Элементарные шифры на понятном языке
Все мы довольно часто слышим такие слова и словосочетания, как «шифрование данных», «секретные шифры», «криптозащита», «шифрование», но далеко не все понимают, о чем конкретно идет речь. В этом посте разберемся, что из себя представляет шифрование и рассмотрим элементарные шифры с тем расчетом, чтобы даже далекие от IT люди поняли суть этого явления.
Прежде всего, разберемся в терминологии.
Шифрование – это такое преобразование исходного сообщения, которое не позволит всяким нехорошим людям прочитать данные, если они это сообщение перехватят. Делается это преобразование по специальным математическим и логическим алгоритмам, некоторые из которых мы рассмотрим ниже.
Исходное сообщение – это, собственно, то, что мы хотим зашифровать. Классический пример — текст.
Шифрованное сообщение – это сообщение, прошедшее процесс шифрования.
Шифр — это сам алгоритм, по которому мы преобразовываем сообщение.
Ключ — это компонент, на основе которого можно произвести шифрование или дешифрование.
Алфавит – это перечень всех возможных символов в исходном и зашифрованном сообщении. Включая цифры, знаки препинания, пробелы, отдельно строчные и заглавные буквы и т.д.
Шифр Атбаша
Например, есть у нас алфавит, который полностью соответствует обычной латинице.
Для реализации шифра Атбаша просто инвертируем его. «А» станет «Z», «B» превратится в «Y» и наоборот. На выходе получим такую картину:
И теперь пишем нужное сообшение на исходном алфавите и алфавите шифра
Исходное сообщение: I love habr
Зашифрованное: r olev szyi
Шифр Цезаря
Опять же, для наглядности, возьмем латиницу
И теперь сместим вправо или влево каждую букву на ключевое число значений.
Например, ключ у нас будет 4 и смещение вправо.
Исходный алфавит: a b c d e f g h i j k l m n o p q r s t u v w x y z
Зашифрованный: w x y z a b c d e f g h i j k l m n o p q r s t u v
Пробуем написать сообщение:
Шифруем его и получаем следующий несвязный текст:
Шифр Вернама (XOR-шифр)
Исходный алфавит — все та же латиница.
Сообщение разбиваем на отдельные символы и каждый символ представляем в бинарном виде.
Классики криптографии предлагают пятизначный код бодо для каждой буквы. Мы же попробуем изменить этот шифр для кодирования в 8 бит/символ на примере ASCII-таблицы. Каждую букву представим в виде бинарного кода.
Теперь вспомним курс электроники и элемент «Исключающее ИЛИ», также известный как XOR.
XOR принимает сигналы (0 или 1 каждый), проводит над ними логическую операцию и выдает один сигнал, исходя из входных значений.
Если все сигналы равны между собой (0-0 или 1-1 или 0-0-0 и т.д.), то на выходе получаем 0.
Если сигналы не равны (0-1 или 1-0 или 1-0-0 и т.д.), то на выходе получаем 1.
Теперь для шифровки сообщения, введем сам текст для шифровки и ключ такой же длины. Переведем каждую букву в ее бинарный код и выполним формулу сообщение XOR ключ
сообщение: LONDON
ключ: SYSTEM
Переведем их в бинарный код и выполним XOR:
В данном конкретном примере на месте результирующих символов мы увидим только пустое место, ведь все символы попали в первые 32 служебных символа. Однако, если перевести полученный результат в числа, то получим следующую картину:
С виду — совершенно несвязный набор чисел, но мы-то знаем.
Шифр кодового слова
Например, возьмем для разнообразия, кириллический алфавит.
Придумаем кодовое слово. Например, «Лукоморье». Выдернем из него все повторяющиеся символы. На выходе получаем слово «Лукомрье».
Теперь вписываем данное слово в начале алфавита, а остальные символы оставляем без изменений.
И теперь запишем любое сообщение и зашифруем его.
Получим в итоге следующий нечитаемый бред:
Шифр Плейфера
Пусть кодовое слово у нас будет «HELLO».
Сначала поступаем как с предыдущим шифром, т.е. уберем повторы и запишем слово в начале алфавита.
Теперь возьмем любое сообщение. Например, «I LOVE HABR AND GITHUB».
Разобьем его на биграммы, т.е. на пары символов, не учитывая пробелы.
Если бы сообщение было из нечетного количества символов, или в биграмме были бы два одинаковых символа (LL, например), то на место недостающего или повторившегося символа ставится символ X.
Шифрование выполняется по нескольким несложным правилам:
1) Если символы биграммы находятся в матрице на одной строке — смещаем их вправо на одну позицию. Если символ был крайним в ряду — он становится первым.
Например, EH становится LE.
2) Если символы биграммы находятся в одном столбце, то они смещаются на одну позицию вниз. Если символ находился в самом низу столбца, то он принимает значение самого верхнего.
Например, если бы у нас была биграмма LX, то она стала бы DL.
3) Если символы не находятся ни на одной строке, ни на одном столбце, то строим прямоугольник, где наши символы — края диагонали. И меняем углы местами.
Например, биграмма RA.
По этим правилам, шифруем все сообщение.
Если убрать пробелы, то получим следующее зашифрованное сообщение:
Поздравляю. После прочтения этой статьи вы хотя бы примерно понимаете, что такое шифрование и знаете как использовать некоторые примитивные шифры и можете приступать к изучению несколько более сложных образцов шифров, о которых мы поговорим позднее.
Шифр Вернама и протокол Диффи — Хеллмана — Меркла как квантово-устойчивая система шифрования
Чайко, В. И. Шифр Вернама и протокол Диффи — Хеллмана — Меркла как квантово-устойчивая система шифрования / В. И. Чайко. — Текст : непосредственный // Исследования молодых ученых : материалы LII Междунар. науч. конф. (г. Казань, январь 2023 г.). — Казань : Молодой ученый, 2023. — С. 1-6. — URL: https://moluch.ru/conf/stud/archive/474/17723/ (дата обращения: 11.03.2023).
В статье автор предлагает систему шифрования, основанную на шифре Вернама и протоколе Диффи — Хеллмана — Меркла, как квантово-устойчивою систему шифрования. Также автор приводит реальный пример использования данной системы на практике и практическую попытку взлома данной системы.
Ключевые слова: шифр Вернама, протокол Диффи — Хеллмана — Меркла, шифрование, квантово-стойкий, RSA.
23 декабря 2022 года была опубликована статья «Факторинг целых чисел с сублинейными ресурсами на сверхпроводящем квантовом процессоре». [1] Согласно данной статье взлом шифра RSA с длинной ключа 2048 бит возможен уже сегодня. Такое положение дел фактически подрывает информационную безопасность во всем мире. Однако стоит отметить, что взлом шифра RSA, с длинной ключа 2048 бит, на практике, они так и не осуществили, поэтому данная статья — только теоретическая. [2] [3]
Тем не менее, эра квантовых суперкомпьютеров все ближе, что делает проблему информационной безопасности актуальнее с каждым годом. Квантовые суперкомпьютеры работают на совершенно иных принципах, нежели наши привычные офисные и домашние ПК. Именно благодаря этому они способны взламывать современные шифры, в том числе AES, Twolfish и Serpent, что несет огромную угрозу информационной безопасности, в том числе в телекоммуникационном, банковском и военном секторах. [4]
Ученые со всего мира уже давно ведут исследования и разработки в области криптографии, пытаясь разработать такую систему шифрования, которая могла быть использована простым компьютером и не поддавалась взлому при помощи квантового суперкомпьютера. Стоит отметить, что уже сегодня существует большое количество наработок в этой области, однако они, в большинстве своем, только теоретические. Эффективность этих шифров против взлома квантовым суперкомпьютером не была доказана на практике. [5] Именно поэтому сегодня существует потребность в создании квантово-устойчивого шифра на практике.
В качестве такого шифра я предлагаю систему шифрования, основанную на шифре Вернама [6] и протоколе Диффи — Хеллмана — Меркла [7].
Гилберт Вернам, в 1917 году, изобрел шифр, который стал называться его именем — «шифром Вернама». Позже, в 1930-х годах, невзламываемость данного шифра была доказана математиком Клодом Шенноном. Данный шифр реализуется при помощи побитного сложения по модулю 2 (побитного «XOR») текста сообщения и его ключа. Получающаяся в результате шифрования последовательность битов не поддается какому-либо анализу и взлому. [8] Такое положение дел сохраняется и сегодня — данный шифр невозможно взломать на компьютере любой мощности, в том числе и квантовом суперкомпьютере. [9]
Несмотря на надежность, от использования данного шифра отказались по целому ряду причин. Наиболее важные из них — это величина ключа, уровень его (ключа) случайности, и необходимость его передачи собеседнику по защищенному каналу («проблема распределения ключей»). Эти три требования сделали его, в начале, неудобным, а впоследствии, и непригодным к применению в современное время. Взамен этого шифра было решено использовать симметричные шифры и шифр RSA (в сетях передачи данных). [6]
Сегодня шифр Вернама — единственный тип шифра, который может противостоять квантовому суперкомпьютеру на практике, и возможен для реализации на обычных компьютерах. Именно поэтому в основу предлагаемой мной системы лег именно этот шифр.
В 1976 году два математика Диффи и Хеллман опубликовали метод безопасного создания общего ключа шифрования при помощи обмена открытыми числами. [7] Этот метод стал называться протоколом Диффи-Хеллмана, но позже, в 2002 году, по просьбе Хеллмана, данный протокол стали называть Диффи — Хеллмана — Меркла. Используя данный протокол модифицированной версии, предлагаемая система шифрования лишена «проблемы распределения ключей».
Чтобы понять суть модификации, необходимо разобрать сам процесс взлома протокола Диффи — Хеллмана — Меркла:
Алиса и Боб договариваются о двух простых числах p=23, g=5. Алиса выбирает в качестве секретного числа a=6, а Боб b=15. Алиса вычисляет число A по формуле
, и передает его Бобу. Боб вычисляет число B по формуле
и передает Алисе. Алиса вычисляет ключ k по формуле
. Боб вычисляет ключ k по формуле
. У Алисы и Боба есть общий ключ k=2, которым они могут шифровать свои сообщения. Ева, которая хочет узнать общий ключ k, знает только числа p=23, g=5, A=8, B=19. Чтобы найти ключ k она должна решить уравнение
, подбирая значения x и y методом перебора. После того, как такое совпадение будет найдено, Ева вычисляет значение любой из частей уравнения и получает ответ. Далее она пробует расшифровать передаваемое сообщение, используя ответ в качестве ключа, до тех пор, пока он не подойдет. Учитывая, что шифрование осуществляется современным блочным шифром, рано или поздно сообщение будет расшифровано единственно верным способом. Наглядно перебор Евы возможных значений, для данного примера, представлен в таблице 1.