XVIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Разработка программы для реализации методов шифрования и криптоанализа (одноразовый шифроблокнот с использованием языка программирования Python)
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Одноразовый шифроблокнот (Шифр Вернама)- это шифр Виженера, который приобретает абсолютную криптографическую стойкость, если ключ удовлетворяет следующим критериям:
длина ключа совпадает с длиной открытого сообщения;
символы ключа выбираются абсолютно случайным образом;
ключ используется всего один раз и больше не применяется ни к каким другим сообщениям.
Придерживаясь этих трех правил, можно сделать зашифрованное сообщение неуязвимым для любых видов криптоанализа. Такой ключ невозможно взломать, даже располагая неограниченными вычислительными ресурсами. Свое название шифр получил благодаря тому, что обычно его ключи записывали в блокноте. После использования ключа верхний лист блокнота отрывали, чтобы перейти к следующему ключу. Как правило, в блокноте сразу записывали большое количество ключей, помечая ключи конкретными датами, а сам блокнот передавали из рук в руки. Например, если зашифрованное сообщение было получено 25 апреля, то следовало пролистать блокнот и найти ключ, соответствующий этой дате.
Выравнивание длины слова по размеру сообщения
Чтобы понять, почему шифротекст, зашифрованный с помощью одноразового шифроблокнота, невозможно взломать, что делает обычный шифр Виженера уязвимым для атак. В основе программы взлома шифра Виженера лежит частотный анализ. Но если размер ключа равен размеру сообщения, то подключ каждой буквы открытого текста является уникальным в том смысле, что каждая такая буква может быть зашифрована в любую букву шифротекста с равной вероятностью.
Например, чтобы зашифровать сообщение "IF YOU WANT ТО SURVIVE OUT HERE, YOU'VE GOT ТО KNOW WHERE YOUR TOWEL IS", удаляем из него пробелы и знаки препинания, получая в результате сообщение длиной 55 букв. Для применения одноразового шифроблокнота необходимо получить ключ, длина которого тоже составляет 55 букв. Выбрав в качестве примера ключ: KCQYZHEPXAUTIQEКXEJMORETZHZTRWWQDYLBTТVEJMEDBSANYВPXQIK, получим шифротекст: "SHOMTDECQTILCHZSSIXGHYIKDFNNMACEWRZLGHRAQQVHZGUERPLBBQC" .
(см. рис.1)
Допустим, криптоаналитик завладел шифротекстом ("SHOMTDEC ... ") . Как взломать такой шифр? Полный перебор ключей методом грубой силы не сработает, так как это чересчур много даже для компьютера. Количество ключей будет равно 26 в степени, равной числу букв в сообщении. Если длина сообщения - 55 букв, как в нашем примере, то общее число возможных ключей составит 2655, или 666 09 1 878 43 1 395 624 1 53 823 182 526 730 590 376 250 379 528 249 805 353 030 484 209 594 192 101 376. Но, даже располагая компьютером, достаточно мощным для того, чтобы испытать все ключи, криптоаналитик все равно не сможет взломать одноразовый шифроблокнот, поскольку для любого шифротекста все возможные варианты открытых текстов одинаково вероятны. Шифротекст "SHOMTDEC ... " может оказаться результатом шифрования совершенно иного сообщения с тем же количеством букв, например текста "ТНE MYTHOF OSIRISWASOFIMPORTANCEINANCIENTEGYPTIANRELIGION", зашифрованного с помощью ключа ZAКAVКXOLFQDLZHWSQJBZMТWМMNAКWURWEXDCUYWКSGORGHNNEDVТCP (см. рис.2).
Причина, по которой возможно взломать какой-либо шифр, заключается в том, что обычно существует лишь один ключ, применение которого для дешифрования сообщения позволяет получить осмысленный текст на английском языке. Но, как только что было показано на конкретном примере, один и тот же шифротекст может быть получен для двух совершенно разных сообщений. В случае одноразового шифроблокнота у криптоаналитика нет возможности определить, какое из них является истинным. По сути, любое сообщение на английском языке, насчитывающее ровно 55 букв, может с равной вероятностью оказаться истинным. Одного лишь факта получения осмысленного текста на английском языке недостаточно для определения исходного ключа шифрования. Поскольку для получения шифротекста с равной вероятностью мог быть использован любой текст на английском языке, сообщение, зашифрованное с помощью одноразового шифроблокнота, не поддается взлому.
Создание истинно случайного ключа
Встроенный модуль random не позволяет получать истинно случайные числа. Применяемый алгоритм генерирует так называемые псевдослучайные числа, которые лишь кажутся случайными, чего вполне достаточно в большинстве задач. Однако в случае одноразового шифроблокнота ключ должен быть истинно случайным числом, в противном случае шифр теряет свою абсолютную криптографическую стойкость. В Python версии 3.6 и выше имеется модуль secrets, который в качестве источника истинно случайных чисел использует операционную систему (чаще всего таким источником служат случайные события, например промежуток времени между последовательными нажатиями клавиш). Функция secrets.randbelow () возвращает истинно случайное число в диапазоне от 0 до значения, определяемого аргументом (не включая его самого).
>>> import secrets
>>> secrets.randbelow (10)
2
>>>secrets.randbelow (10)
0
>>>secrets.randbelow (10)
6
Функции модуля secrets работают медленнее по сравнению с функциями модуля random, поэтому последние предпочтительнее в ситуациях, когда истинная случайность не нужна. Можно также воспользоваться функцией secrets .choice (), которая возвращает случайно выбранный элемент из переданной ей строки или списка.
>>> import secrets
>>> secrets.choice ( ' AВCDEFGHIJКLМNOPQRSТUWXYZ ' )
'R'
>>> secrets . choice ( [ ' cat ' , ' dog ' , 'mouse '] )
' dog '
Для создания истинно случайного одноразового шифроблокнота размером 55 символов можно использовать следующий код.
>>> import secrets
>>> otp = ''
>>> for i in range (55) :
... otp += secrets.choice ( 'AВCDEFGHIJRLМNOPQRSТUVWXYZ ' )
...
>>> otp
' МVOVAAYDPELIRNRUZNNQHDNSOUWWNWPJUPIUAIMKFKNHQAN I I YCHHDC '
Кроме того, существует еще одно обстоятельство, о котором никогда нельзя забывать при работе с одноразовым шифроблокнотом. Рассмотрим, почему следует избегать повторного использования одноразовых шифроблокнотов.
Двухразовые шифроблокноты
Под двухразовым шифроблокнотом понимают использование одного и того же ключа одноразового шифроблокнота для шифрования двух разных сообщений. Это создает критическую уязвимость. Результатом расшифровки сообщения, зашифрованного с помощью одноразового шифроблокнота, представляет собой осмысленный текст на английском языке, еще не означает, что найден правильный ключ. Но если используется один и тот же ключ для шифрования двух разных сообщений, то тем самым взломщик получает информацию. В этом случае взломщик, получив осмысленный текст в результате дешифрования первого шифротекста с помощью найденного ключа и увидев, что применение этого же ключа ко второму шифротексту дает случайный набор букв, сразу же поймет, что ключ не подходит. Если в распоряжении взломщика имеется только одно из двух сообщений, то расшифровать его по-прежнему невозможно. Но всегда надо исходить из того, что все зашифрованные сообщения могут перехватываться злоумышленниками.
Эквивалентность двух разового шифроблокнота шифру Виженера
Чтобы понять, почему двухразовый шифроблокнот уязвим подобно шифру Виженера, рассмотрим работу шифра Виженера в том случае, когда размер сообщения превышает длину ключа. Исчерпав буквы ключа, мы возвращаемся к его первой букве и продолжаем процесс шифрования. Например, чтобы зашифровать сообщение "BLUE IODINE INBOUND САТ" длиной 20 букв с помощью ключа YZNMPZXYXY длиной 10 букв, мы шифруем первые 10 букв ("BLUE IODINE") ключом YZNMPZXYXY, после чего тем же ключом шифруем следующие 10 букв ("INBOUND САТ"). Эффект завертывания проиллюстрирован на рис. 3
Предположим, что шифрование 10-буквенного сообщения "BLUE IODINE" осуществляется с использованием одноразового шифроблокнота и ключа YZNMPZXYXY. Тогда криптограф, шифрующий второе 10-буквенное сообщение "INBOUND САТ" с помощью того же ключа YZNMPZXYXY, совершает серьезную ошибку (рис. 4)
Если сравнить шифротекст, полученный с помощью шифра Виженера ("ZKHQXNAGKCGMOAJMAAXR" на рис. 3) , с шифротекстами, полученными с помощью одноразового шифроблокнота ("ZКНQXNAGKC" и "GMOAJМAAXR" на рис. 4), то увидим, что они в точности совпадают. Таким образом, двухразовый шифроблокнот обладает теми же свойствами, что и шифр Виженера, а значит, его можно взломать теми же самыми способами!
Криптоанализ
Для работы шифра Вернама необходима истинно случайная последовательность нулей и единиц (ключ). По определению, последовательность, полученная с использованием любого алгоритма, является не истинно случайной, а псевдослучайной. То есть, нужно получить случайную последовательность неалгоритмически (например, используя распад ядер, создаваемый электронным генератором, белый шум или другие достаточно случайные события). Чтобы сделать распределение предельно близким к равномерному, случайная последовательность обычно прогоняется через хэш-функцию наподобие MD5.
Проблемой является тайная передача последовательности и сохранение её в тайне. Если существует надёжно защищённый от перехвата канал передачи сообщений, шифры вообще не нужны: секретные сообщения можно передавать по этому каналу. Если же передавать ключ системы Вернама с помощью другого шифра (например, DES), то полученный шифр окажется защищённым ровно настолько, насколько защищён DES. При этом, поскольку длина ключа та же, что и длина сообщения, передать его не проще, чем сообщение. Шифроблокнот на физическом носителе можно украсть или скопировать.
Возможны проблемы с надёжным уничтожением использованной страницы. Этому подвержены как бумажные страницы блокнота, так и современные электронные реализации с использованием компакт-дисков или флэш-памяти.
Если третья сторона каким-нибудь образом узнает сообщение, она легко восстановит ключ и сможет подменить послание на другое такой же длины.
Шифр Вернама чувствителен к любому нарушению процедуры шифрования. Бывали случаи, когда одна и та же страница блокнота по различным причинам применялась дважды. Например, среди всего объёма советской шифрованной переписки, перехваченной АНБ США в период 40-х годов прошлого века, были обнаружены сообщения, закрытые дважды использованной гаммой. Период этот длился не очень долго, потому что уже после первых успехов американских криптоаналитиков в конце 1940-х годов в спецслужбах СССР узнали о серьёзных проблемах с надёжностью своей шифрпереписки. Такие сообщения были расшифрованы в течение 40 последующих лет в рамках секретного проекта «Venona», документы которого были не так давно рассекречены и выложены на сайте АНБ.
Тем не менее, схема одноразового блокнота является единственной схемой с абсолютной стойкостью, доказанной теоретически. Вышеперечисленные недостатки можно попытаться устранить применением новых схем распределения ключей, например таких, как квантовая криптография, в частности, протокол BB84 для генерации и передачи одноразовых блокнотов. Также существуют другие перспективные методы распределения ключей, например использование возможностей нейрокриптографии.
Вывод
Одноразовый шифроблокнот - это методика, позволяющая сделать шифр Виженера неуязвимым для взлома. Для этого необходимо, чтобы длина ключа совпадала с размером сообщения, а сам ключ был истинно случайным и использовался строго один раз. Соблюдение всех трех условий полностью исключает возможность взлома сообщения, зашифрованного с помощью одноразового шифроблокнота. Однако применять такую методику для регулярного шифрования сообщений не очень удобно. Обычно одноразовые шифроблокноты со списком ключей передаются из рук в руки. При этом вы должны быть уверены в том, что список не попадет в чужие руки!
Список литературы:
Peter, H. Gregory Blocking Spam For Business For Dummies® (For Dummies (Computers)) / Peter H. Gregory. - Москва: ИЛ, 2016. - 636 c.
Шумский, А.А. Системный анализ в защите информации / А.А. Шумский. - Москва: СПб. [и др.] : Питер, 2013. - 224 c.
Бабаш, А. В. История криптографии. Часть I / А.В. Бабаш, Г.П. Шанкин. - М.: Гелиос АРВ, 2016. - 240 c.
Горев, А И; Симаков А А Обеспечение Информационной Безопасности / А Горев А И; Симаков А. - Москва: ИЛ, 2016. - 494 c.
Криптография: скоростные шифры / А. Молдовян и др. - М.: БХВ-Петербург, 2014. - 496 c.
Свейгарт, Эл. Криптография и взлом шифров на Python.: Пер. с англ. - Спб.: ООО «Диалектика», 2020. - 512 с.