Небезопасный столп кибербезопасности
4 ноября 2022 г.История гласит, что Цезарь, чтобы обмениваться секретными сообщениями со своими генералами в полевых условиях, брил своих посланников налысо и писал сообщение на их скальпах. Затем он ждал несколько месяцев, пока их волосы отрастут, и отправлял их по назначению. Только его доверенные генералы знали об этом методе обмена сообщениями, таким образом безопасно доставляя его приказы (хотя и с опозданием на несколько месяцев).
n Этот непрактичный и довольно глупый пример описывает суть криптологии. Криптология — это наука о защите связи. Термин происходит от греческих слов kryptós («скрытый, тайный») и lógos («слово»). По сути, речь идет о «сокрытии слов». Это всего лишь один из столпов науки о кибербезопасности, но очень важный. В основе этого столпа лежат разделы криптологии: криптография и криптоанализ. Их можно почти рассматривать как взаимодополняющие. В то время как криптография – это практика преобразования сообщений в форму, недоступную для прослушивания, криптоанализ – это попытка расшифровать эти преобразованные сообщения непреднамеренным получателем.
n И именно здесь, у основания этой опоры, одно доказательство проблемы может привести к краху кибербезопасности.
n Итак, войдите в Пантеон, этот храм кибербезопасности, если хотите, и позвольте мне показать вам, где начинают появляться трещины в коринфских колоннах.
n n Существует множество различных алгоритмов, предназначенных для обеспечения безопасности сообщений. Я собираюсь немного рассказать вам о некоторых из этих систем, чтобы стала понятна основа этих алгоритмов.
n Если вы читали что-нибудь о криптографии, скорее всего, вы сталкивались с концепцией под названием "шифр Цезаря". Это еще один пример метода, используемого для защиты сообщений. Его также приписывают Цезарю, хотя в нем не используются замки посыльного (каламбур), чтобы сохранить сообщение в безопасности. Вместо этого этот шифр вводит важную концепцию, на которой основана значительная часть криптографических алгоритмов: модульная арифметика.
n 
n Знаю, знаю. Звучит страшно, правда? Что, если я скажу вам, что это настолько просто, что вы используете его каждый день? Видите ли, ваши часы тоже основаны на модульной арифметике. Когда вы пытаетесь вычислить, сколько вы будете спать, если вам придется вставать в 06:00, поскольку вы заканчиваете этот срок в 23:00, вы знаете, что после 24:00 считать нельзя. . Результат всегда будет меньше 24:00. По сути, вы вычисляете по модулю 24. Это модульная арифметика, и она широко используется в криптографии. Однако даже при всей своей простоте модульная арифметика хранит много секретов, которые не сразу бросаются в глаза. Многие криптографические алгоритмы используют эти секреты.
n Шифр Цезаря является симметричным шифром. Это означает, что обе стороны используют один и тот же ключ. Допустим, ключ равен 3. Отправитель сдвинет каждую букву своего сообщения на 3. Это называется шифрованием. Получатель должен знать ключ, а затем сдвинет каждую букву назад на 3, получив исходное сообщение. Это называется расшифровкой. Сравните это с методом лысого посыльного. Шифрование позволяет мессенджеру расти над сообщением, а дешифрование — брить мессенджера налысо.
n Итак, насколько надежен шифр Цезаря? Ну не совсем. Любой может легко попробовать все разные ключи, которых всего 26, и найти правильный, чтобы разгадать сообщение. Это называется атакой грубой силы. Хотя шифр не очень безопасен, он придерживается важного принципа, которого не придерживаются лысые посланники Цезаря. Принцип Керкхоффа гласит:
<цитата>n "Шифр не должен требовать секретности, и не должно быть проблем, если он попадет в руки врага".
n Другими словами, принцип гласит, что секретным должен оставаться только ключ. Метод можно сделать общедоступным, но без ключа сообщение должно оставаться в безопасности.
n Если ранее лысый посланник Цезаря будет перехвачен врагом, и перехватчик знает о методе, использованном Цезарем, бедный посланник будет снова обрит налысо в кратчайшие сроки, обнажая сообщение на его скальпе. Однако с шифром Цезаря, даже если перехватчик знает метод шифрования, ему все равно придется попробовать 26 различных ключей, чтобы раскрыть сообщение. п
n Шифр Цезаря — один из самых простых существующих шифров, но его простота прекрасно демонстрирует аспекты модульной арифметики. Другими распространенными симметричными криптосистемами являются DES, 3DES и AES. По сути, они делают то же самое, что и шифр Цезаря, но намного сложнее и труднее взломать методом грубой силы. Если вы хотите узнать больше об этих системах, я настоятельно рекомендую прочитать комикс AES< /а>.
n Введем еще одно важное понятие. Асимметричная криптография (или криптография с открытым ключом). Разница в том, что у двух сторон не один и тот же ключ, а собственные открытый и секретный ключи.
n Прежде чем мы углубимся в RSA, вот вам интересная информация об этом. Когда RSA был изобретен Роном Ривестом, Ади Шамиром и Леонардом Адлеманом, для них было незаконным экспортировать алгоритм или даже его описание в рамках контроля над боеприпасами в США. RSA считалась настолько могущественной, что должна была храниться в военной тайне. В знак протеста против свободы слова они носили футболки с напечатанным на них алгоритмом на съездах и переговорах.
n RSA — самая популярная криптосистема с открытым ключом. Это очень крутая система, которая прекрасно иллюстрирует то, на чем основана большая часть современной криптографии. Мы собираемся немного углубиться в технические подробности, но потерпите меня.
n Основная теорема арифметики утверждает, что любое положительное число можно представить ровно одним способом в виде произведения одного или нескольких простых чисел. Например, число 77 можно представить путем умножения 7 (простое число) и 11 (простое число). Нет другого способа представить число 77 в виде простых чисел, кроме изменения порядка простых чисел. Помните об этом, пока я буду объяснять RSA.
n Перед отправкой сообщения нам необходимо выполнить некоторые настройки. Скажем, Боб хочет послать сообщение Алисе, а есть какой-то подслушиватель по имени Ева. Алиса, как получатель, выбирает два больших простых числа. Она умножает эти два числа, чтобы получить результат m, модуль. В нашем примере мы сохраним его простым и небольшим. Алиса выбирает 7 и 11 в качестве простых чисел, в результате чего получается модуль 77. Она публикует модуль 77 и некоторый выбранный показатель степени шифрования e. Комбинация модуля 77 и показателя шифрования e называется ее открытым ключом.
n С помощью открытого ключа Алисы Боб может зашифровать сообщение, которое он хочет отправить. В этом случае сообщение представляет собой число x. Шифрование в RSA выполняется путем взятия x^e mod m. Это приводит к зашифрованному тексту y и отправляет его Алисе.
n Теперь Алиса может поколдовать с простыми множителями 7 и 11, в результате чего получится часть информации, называемая d (для расшифровки). Это секретный ключ Алисы. Все, что теперь нужно сделать Алисе, — это взять y^d, что приведет к исходному сообщению Боба x.
n Уф, это было много, но самое сложное уже позади! Теперь обратите внимание, что только Алиса знает простые делители 7 и 11. Это означает, что только Алиса может проделать этот фокус, чтобы получить информацию d. Но если вы проницательны, вы не согласитесь со мной здесь. Вы бы сказали: «Поскольку 77 опубликовано и каждый имеет к нему доступ, Ева может легко вычислить, что 77 = 7*11, и проделать магический трюк, чтобы получить d, с помощью которого она может получить исходное сообщение x». Я бы согласился с вами здесь. Тогда я бы сказал вам: «Каковы простые числа числа 30142741». Скорее всего, вы не сможете сказать мне ответ. Я могу очень легко дать вам ответ, поскольку все, что я сделал, это взял два простых числа и умножил их, чтобы получить 30142741. И если бы я сказал вам эти два числа, вы могли бы так же легко убедиться, что произведение равно 30142741. Так что действительно, RSA полагается на то, что Ева (или вы) не сможете найти эти два простых числа. В данном случае это простые числа 6037 и 4993. Видите, как сложно разложить простые числа на множители, но как легко проверить правильность простых чисел?
n Вот оно! Наконец мы у основания столба. Видишь трещины? Возможно нет. Поясню.
n Таким образом, преобразования, которые мы применяем к сообщению (шифрование), должны быть обратимыми, чтобы получатель мог его расшифровать. Получатель может инвертировать сообщение, потому что он владеет некоторой дополнительной информацией. Между тем любой перехватчик, не владеющий этой информацией, не сможет расшифровать сообщение. В RSA, например, перехватчику нужно будет найти два простых множителя модуля. Найти два простых множителя небольшого числа, такого как 77, конечно, несложно, но разложение на простые множители становится намного сложнее, когда выбирается большое число. Проверить, что два простых числа являются множителями модуля, всегда относительно легко, поскольку вы просто выполняете умножение.
n Если бы факторизация простых чисел была простой или если бы существовал алгоритм, способный решить проблему относительно быстро, то RSA устарела бы. Он основан на простой факторизации, которую трудно решить, но легко проверить. Мы можем провести различие между двумя наборами проблем. Есть задачи, для которых мы знаем, как быстро найти ответ, например, умножение или возведение в квадрат. Этот набор называется «класс P». Другой класс, «NP», представляет собой набор задач, для которых нет известных способов быстрого поиска ответа, но когда у вас есть некоторая информация, ответ легко проверить. Первичная факторизация принадлежит к этому классу.
n Но что, если есть способ легко решить проблему простой факторизации? Это означало бы, что первичная факторизация принадлежит классу P. На самом деле, возможно, мы могли бы доказать, что все NP-задачи на самом деле являются P-задачами. Можно сделать вывод, что P = NP.
n Этот вывод имел бы катастрофические последствия для криптографии. Как мы видели, RSA полагается на сложность решения простой факторизации. Но RSA — это только один из многих алгоритмов, основанных на задачах NP, а простая факторизация — только один пример проблемы NP. Другие симметричные и асимметричные шифры, используемые для ваших финансовых транзакций, общения по электронной почте и т. д., станут устаревшими.
n Биткойн и другие криптовалюты также пострадают от серьезных последствий, поскольку Биткойн использует криптографическое хеширование, в частности, алгоритм хеширования SHA-256. Чтобы новый блок был принят в цепочке блоков, этот новый блок должен содержать доказательство работы. Короче говоря, доказательство легко проверить любому узлу в сети, но сгенерировать правильное число чрезвычайно сложно.
n 
Доказательство P = NP может быть с другой стороны, имеют положительные последствия для других областей. Многие математические задачи остаются трудноразрешимыми. Только представьте, какое влияние это может оказать на математику!
n Доказательство того, что P ≠ NP, будет означать, что наши криптографические алгоритмы безопасны и что название этой статьи просто наживка. Но, по крайней мере, я предложил тебе шанс выиграть миллион долларов! Это награда, которую Математический институт Клэя присудит тому, кто первым решит задачу "P vs NP".
n Итак, попробуйте! Может быть, вы могли бы взломать современную криптографию и вернуть нас к использованию голых мессенджеров для нашего повседневного общения. п
Также опубликовано здесь n
Оригинал