Текст книги "Шифрованный мир. Азы криптографии и задачи по криптоанализу"

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

Шифровальная машина М-101 Изумруд(в 2 раза уменьшен вес и в 6 раз габариты)

Группа из трёх польских математиков, несмотря на то, что британская и французская разведка не стали браться за эту задачу, сочтя её невыполнимой, вела работы по «борьбе» с «Энигмой» – немецкой роторной шифровальной машины, количество возможных ключей которой составляло более 10 000 000 000 000 000 – и даже умела читать многие сообщения, зашифрованные «Энигмой» до декабря 1938 года. Далее Англия собрала 12 000 специалистов, построила машину, помогавшую в дешифровке и читала все перехваченные и отправленные по телеграфу сообщения Германии, причём немцы так и не узнали об этом вплоть до конца войны (а европейцы ещё несколько лет после войны пользовались трофейными немецкими шифровальными машинами для передачи секретных дипломатических посланий, не зная, что англичане способны их расшифровывать), хотя СССР, состоявший в союзе с Британией имела доступ к переписке Германии и, в частности, благодаря этому смог подготовиться к Курской дуге. Подробнее об этом можно посмотреть в фильме «Игра в имитацию».

Bombe

Bombe – электронно-механическая дешифровальная машина, созданная в годы Второй мировой войны при участии британского математика Алана Тьюринга для расшифровки сообщений, зашифрованных при помощи немецкой машины Enigma.

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

Проникая в мысли противника: легендарный Блетчли-Парк

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

Леонид Черняк. Тайны проекта Ultra

Однако, взломать шифр – это лишь полдела, вторая половина – сделать так чтобы об этом не узнал враг. Чтобы не потерять это немаловажное преимущество и не вызывать лишних подозрений в шифре у немцев, Англии пришлось периодически давать Германии осуществлять её планы, даже уже зная их. Так, например, Черчилль в 1940 году принял решение не эвакуировать и не защищать город, о бомбардировке которого ему было известно заранее. Число повреждённых только зданий, не говоря уже о людях, составило 60 000. Такова цена секрета, о том, что другой секрет известен.

Начиная с 1940 года высшее германское командование начало использовать ещё один метод шифрования.

История криптографии – Википедия

Для него использовалось новое устройство, называемое «машиной Лоренца».

Шифрование основывалось на шифре Вернама (о нём более подробно далее) и при правильном использовании гарантировало абсолютную криптостойкость.

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

Sale, Tony The Lorenz Cipher and how Bletchley Park broke it

Генератор, используемый в машинах «Lorenz SZ 40» оказался слабым.

Трофимов Никита – Разработка программы для шифрования текстовой информации

В том смысле, что зная несколько символов ключа, можно было предсказать следующие.

Однако его взлом всё равно нельзя было осуществить вручную – английским криптоаналитикам из Блетчли-парк потребовалось создать устройство, которое бы перебирало все возможные варианты и избавляло криптоаналитиков от ручного перебора. Таким устройством стала одна из первых программируемых вычислительных машин «Colossus»

Трофимов Никита – Разработка программы для шифрования текстовой информации

,созданная Максом Ньюманом и Томми Флауэрсом при участии Алана Тьюринга в 1943 году. Машина позволила сократить время, требуемое на взлом сообщений, с шести недель до нескольких часов, что дало не только значительное военное преимущество, но и позволила сохранить силы и нервы самих дешифровщиков. Вот что пишет в своих мемуарах один из дешифровщиков из Блетчли-парк:

«… если буква А, которая вчера означала Б, а сегодня может означать В; если перед тобой букв на полстраницы в четыре ряда и по две линии – за ними может стоять как важнейшая военная операция, так и прогноз погоды; если начальство интересуется, почему так медленно движется работа, а счет уже пошел на сотни расшифрованных сообщений в день; если офицер безопасности периодически просит показать ему твои карманы, чтобы убедиться, не припрятал ли ты там шифровку, тебе хочется выбежать из этой хижины, заскочить в автобус или поезд и уехать как можно дальше… где нет шифров, недоверчивого начальства, курьеров, выхватывающих у тебя из-под рук каждое разгаданное слово, чтобы тут же доставить его в Лондон… Но ты делаешь несколько глубоких вдохов, закуриваешь сигару, любуешься свежей зеленью газона, тихой заводью пруда и белым лебедем, который будто позирует художнику, – и через пару минут опять возвращаешься к кодам и шифрам, так как на столе у тебя уже новое сообщение, а через час их собирается целая кипа. И жизнь продолжается… Работа в Блетчли в режиме нон-стоп была на грани человеческих возможностей, а иногда и за гранью: как-то один из шифровальщиков вышел раздетым через окно, нырнул в пруд, поплавал и точно так же вернулся на свое место. В тот же день его отправили в местную больницу, но уже через месяц он снова приступил к привычной работе».

Проникая в мысли противника: легендарный Блетчли-Парк

Ключевой вехой в развитии криптографии является фундаментальный труд Клода Шеннона «Теория связи в секретных системах» – секретный доклад, представленный автором в 1945 году и опубликованный им в 1949 году. В этой работе был впервые показан подход ко всей криптографии как к математической науке. Были сформулированы её теоретические основы и введены понятия, с объяснения которых сегодня начинается изучение криптографии студентами.

История криптографии – Википедия

Также была подана идея итеративных блочных шифров.

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

Баричев С. Г., Гончаров В. В., Серов Р. Е. История криптографии // Основы современной криптографии – М.: Горячая линия – Телеком, 2002. – 175 с. – (Специальность. Для высших учебных заведений) – ISBN 978-5-93517-075-2

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

Для того чтобы зашифровать приказ размером в полторы печатные страницы требовалось 4 – 5 часов, на расшифровку уходило столько же времени.

Сокровищница отечественной криптографии – Habr

В 1973 году Национальный институт стандартов и технологий США объявил конкурс с целью разработать стандарт шифрования данных, победителем которого в 1974 году стал шифр DES.

Блочный шифр – Википедия

В 1977 году он был опубликован, а в 1981 одобрен для использования в гражданском секторе. Однако шифр имел существенный недостаток – маленькую длину ключа (56 бит), что делало его уязвимым для простого перебора. Этот недостаток был специально внедрён АНБ (первоначально шифр мел длину ключа 112 бит), так как с этого времени начинается борьба государств с гражданской криптографией, поскольку гипотетически мощности вычислительной техники персональных компьютеров и публичная теоретическая база подобрались к тому, чтобы кто угодно мог шифровать любые послания так, что даже собственное правительство не в состоянии будет прочитать что там. Если раньше простая перлюстрация (вскрытие и прочтение) писем давала мощную фору государству, то теперь террористы, организованная преступность, бунтари или вражеская разведка этого не боятся. АНБ отказывало в государственных грантах математикам, кто вёл работы по криптографии, не сотрудничая с ними, накладывали гриф секретности на гражданские изобретения, связанные с шифрованием, запрещали публикацию материалов по шифрованию и криптоанализу.

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

История криптографии – Википедия

Против автора бесплатного программного обеспечения с открытым кодом для шифрования и электронной подписи сообщений PGP (криптограф Брюс Шнайер охарактеризовал раннюю версию PGP как «ближайшую к криптосистемам военного уровня»), использующем известные несекретные шифры, Филиппа Циммермана было возбуждено уголовное дело за «экспорт вооружений», так как экспорт криптографических систем с длиной ключа более 40 бит был запрещён. Были многочисленные попытки внедрить в системы шифрования скрытые уязвимости с целью получения при необходимости спецслужбами расшифровки, однако по многим причинам это тогда не удалось. После отказа от технических средств доступа к ключам шифрования правительства обратились-таки к идее законодательного регулирования данного вопроса – когда человек обязан предоставить заранее или будет обязан предоставить по требованию ключ для чтения сообщений. Именно поэтому позже пытались закрыть тогда ещё только мессенджер «Telegram» – Павел Дуров отказался это делать для России, находясь за границей (c 2017 года проживает в Дубае, где и расположена штаб-квартира Telegram. Кроме российского и ОАЭ, имеет также паспорт государств «Сент-Китс и Невис» и Франции), Также он заявил, что во время поездки в США столкнулся с пристальным вниманием со стороны американских спецслужб.

По его словам, сотрудников «Telegram» пытались подкупить, а ФБР пыталось оказать на него давление, американские спецслужбы дважды предлагали взятку работающим на него сотрудникам.

При этом, подчеркивает Дуров, это произошло «всего за одну неделю». «Было бы наивно полагать, что в США возможно развивать независимый или защищенный криптосервис», – заявил Дуров.

Дуров заявил о попытке подкупа разработчиков Telegram – РБК / Битва за Telegram

Позже команда мессенджера всё же начала сотрудничество с Россией по проблемам борьбы с наркотиками и терроризмом.

Минкомсвязь назвала две причины разблокировки Telegram – РБК / Битва за Telegram

В России тут же официально разблокировали «Telegram», однако, в Пакистане и Омане он также полностью заблокирован, видимо, нет нужды сотрудничать с ними.

«Сегодня Иран официально выбыл из числа стран, которые я могу посещать, – прокурор Тегерана завел там на меня уголовное дело. Телеграмом в Иране пользуется более 40 миллионов человек, и за все годы работы мы не заблокировали ни один политический канал и не выдали властям ни байта личных данных… Отсутствие возможности изредка посещать Россию для меня более болезненно, чем невъезд в Иран» – Дуров.

ФСБ потребовала от Telegram расшифровать переписку пользователей – Ведомости

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

Вот такие пироги…

это что ещё за шифр?)

Итак, далее в 1976 году ещё успели опубликоваться Уитфилд Диффи и Мартин Хеллман с работой «Новые направления в криптографии».

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

История криптографии – Википедия

Сам алгоритм будет приведён в этой книге позже. Аналогичный алгоритм изобрёл Вильямсон тремя годами ранее для британской разведки, однако работа была рассекречена только после публикации работы Диффи и Хеллмана. В 1977 году в открытом доступе появляется алгоритм RSA (по первым буквам фамилий создателей – информатиков Rivest и Shamir, математика Adleman) (его разберём позже), пригодный и для шифрования и для цифровой подписи. Аналогичный алгоритм был изобретён и известен британской разведке (создатель – математик Кокс) ещё четырьмя годами ранее, но не использовался тогда из-за недостаточных мощностей ЭВМ в то время. Однако для криптостойкости в современном мире алгоритму RSA (2022 год) необходим ключ от 2048 бит, из-за чего у него до сих пор имеется недостаток – низкая скорость шифрования.

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

RSA – Википедия

Полностью RSA применяется для создания электронного ключа (устройство, похожее на флешку) и при создании/проверке цифровой подписи. В России для электронной цифровой подписи принят стандарт ГОСТ Р 34.10—2001, использующий криптографию на эллиптических кривых, который позволяет получить ту же криптостойкость, что у RSA при использовании ключей в десять раз меньше.

Отсутствие достойной защиты от атак шифра DES породило в 1997 году, когда США уже пришло к идее законодательного регулирования, AES, также являющийся результатом конкурса Национального института стандартов и технологий США (с ключом 128 – 256 бит и сложными математическими конструкциями, такими как вычисления в поле Галуа), который много где используется и по сей день при передаче данных между обычными пользователями.

Победитель – алгоритм Rijndael – был объявлен в 2000 году.

AES (конкурс) – Википедия

Через год алгоритм был стандартизирован и опубликована его спецификация. В июне 2003 года Агентство национальной безопасности США постановило, что шифр AES является достаточно надёжным, чтобы использовать его для защиты всех сведений, составляющих государственную тайну – просто для разных грифов секретности – своя длина ключа (128 – 256 бит).

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

Кодирование и шифрование

А вот ответьте теперь на такой вопрос – чем кодирование отличается от шифрования?

Что такое код и кодирование? Под кодом может подразумеваться множество понятий будь то код от сейфа или программный код, а вот кодирование – это преобразование представления информации. Так, например, различные кодировки интернет-страниц не шифруют информацию, а просто подразумевают определенное представление преобразования двоичной информации в символьную (например, два байта на символ или один).

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

Приложение CryptoApp

CryptoApp – это приложение для Android, открывающее большие возможности автоматизированной работы при изучении шифров.

Приложение CryptoApp работает с шифрами простой замены (шифр Цезаря, Атбаш, пляшущие человечки) и полиалфавитными шифрами (Виженера, Бофора)

Скачать его можно по ссылке https://disk.yandex.ru/d/vU4jH-sJFG0ngw

При необходимости в настройках устройства разрешите установку из неизвестных источников.

Также приложение CryptoApp может «расшифровывать» текст, набранный в неправильной раскладке, так как это частный случай простой замены.

Виды шифров

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

Симметричный и асимМетричный

От самых первых шифров вплоть до 1977 года все из них являлись симметричными шифрами. Отличительная черта симметричных шифров – это то, что ключ расшифрования и ключ зашифрования одинаковы. Алгоритмы расшифрования и зашифрования – либо идентичны, либо полностью противоположны друг другу. Функция у таких видов шифрования лишь одна – обеспечение конфиденциальности/секретности информации от несанкционированных лиц. Примерами таких шифров могут служить такие шифры, как Вижинера, Плейфера, Цезаря, Вернама, книжный, афинный, Хилла, Атбаш, пляшущих человечков и Бэкона. Смотрите далее задачи по всем этим и нижеперечисленным примерам шифров.

И только недавно (1973 г.) было изобретено асимметричное шифрование. При этом один из ключей может быть разглашен и не сохраняться в тайне, в таком случае шифрование в некотором смысле получается односторонним – кто угодно может зашифровать информацию (к примеру, текст документа), но расшифровать может только узкий круг лиц, или же наоборот расшифровать – кто угодно, но зашифровать только одно лицо (используется для создания электронной подписи и проверки подлинности документа). Функциональность данного вида шифров чрезвычайно широка – от конфиденциальности до цифровой подписи и подтверждения аутентичности информации (свойство, гарантирующее, что субъект или ресурс идентичны заявленным). Примерами ассиметричного шифрования могут служить такие шифры, сертификаты и протоколы, как RSA, SSL, HTTPS и SSH

Эллиптическая криптография

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

Эллиптическая криптография – Википедия

Использование эллиптических кривых для создания криптосистем было независимо друг от друга предложено Нилом Коблицем и Виктором Миллером в 1985 году.

Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An introduction to mathematical cryptography. – Springer, 2008. – 524 с. – (Undergraduate Texts in Mathematics). – ISBN 9780387779942.

Считается, что для достижения такого же уровня криптостойкости, как и в RSA, требуются группы меньших порядков, что уменьшает затраты на хранение и передачу информации. Например, на конференции RSA 2005 Агентство национальной безопасности объявило о создании «Suite B», в котором используются исключительно алгоритмы эллиптической криптографии, причём для защиты информации, классифицируемой до «Top Secret», используются всего лишь 384-битные ключи.

Эллиптическая криптография – Википедия

Это ускоряет обработку информации и облегчает xранение и передачу ключей по сравнению со стандартными ассиметричными шифрами.

Длина ключа

Так например, в РФ используется

«ГОСТ 34.10—2018. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» – действующий межгосударственный криптографический стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи, реализуемой с использованием операций в группе точек эллиптической кривой, определенной над конечным простым полем.

ГОСТ 34.10—2018 – Википедия

Блочный и потоковый

Отличительная особенность блочного вида шифров состоит в том, что они обрабатывают за одну итерацию сразу несколько символов (от биграмм – двух символов до всех символов, содержащихся в сообщении/ключе) открытой информации – например, шифры Хилла, книжный, RSA и Плейфера, в отличие от потокового вида шифров, который обрабатывает по 1 байту/символу – например, шифры Вижинера, Цезаря, Афинный, Атбаш, Вернама (вплоть до 1 бита), пляшущих человечков и Бэкона.