Comments 25
а теперь давайте усложним:
В цифровой подписи, публичный ключ предназначен для шифрования или расшифрования?
Я потратил несколько часов чтобы вникнуть в азы математики (сам не ожидал, что так сильно всё забыл и плюс мне надо прям досконально представлять и понимать суть вещей).
И вот что я хочу спросить. Получается, что описанные шифры не "не расшифровываемые". Их можно расшифровать, но сроки их расшифровки уходят сильно дальше разумного времени при текущем уровне технологий.
А есть ли шифры, которые нельзя математически нельзя расшифровать без закрытого ключа или иной секретной информации?
Книжный шифр, например. При использовании случайного закрытого текста и без переиспользования слов, получается весьма стойкий шифр.
Всё всегда будет упираться во время.
Даже если условно каждой букве будет назначен случайный символ (книжный шифр/Виженера), то частотным анализом можно будет взломать.
Т.е. просто имея что-то зашифрованное - рано или поздно при достаточном датасете оно "взломается".
Поэтому единственный вариант - чтобы ничего не было известно посторонним.
Но тогда легче просто лично шепнуть на ухо без шифровки, нежели полагаться на доставку пакетов.
Даже если условно каждой букве будет назначен случайный символ (книжный шифр/Виженера), то частотным анализом можно будет взломать.
Если действительно случайный символ, то частотный анализ не сработает.
С чего бы?)
Частотный анализ как раз и применяется когда у нас есть зашифрованный текст, где мы не знаем на что были заменены изначальные символы.
Чтобы применить частотный анализ, Вам нужны закономерности, перекошенная статистика в шифротексте.
Для шифра Цезаря очевидно статистика совпадает со статистикой открытого текста — просто дешифруется. Для шифра Виженера с ключевой фразой длины K можно рассмотреть статистику на каждом K-ом символе шифротекста и открытого текста — они, очевидно, совпадают.
В одноразовом блокноте у нас шифротекст распределен равномерно. Ну можно рассматривать его как шифр Виженера с бесконечным периодом. Каждый символ шифруется независимо от других, по независимому ключу. А по одному символу шифротекста статистику тяжело построить.
Или с другой стороны: нет даже способа проверить, что задданный ключ можно использовать для расшифрования — при расшифровке мы можем получить абсолютно любой текст заданной длины.
Поэтому нет, одноразовый блокнот не поддаётся статистическому анализу (если он действительно одноразовый и если он истинно случайный (чего само по себе сложно добиться)).
Любопытно, а если взять одноразовый блокнот где открытый текст и ключ представляют собой текст на одном языке. Ключ условно - случайная страница из Войны и Мир.
Остальное все по правилам: содержимое открытого текста не знаем даже примерно, размер ключа > открытого текста, ключ больше нигде не использовался.
Такая шифровка поддается частотному анализу или все еще обладает стойкостью?
И как это противоречит моему изначальному комментарию, что нужно иметь достаточный датасет?
Если будет достаточно зашифрованных сообщений, то его можно будет расшифровать, что вы и подтвердили в своем комментарии, идя от обратного, что если не использовать достаточно много шифрованный сообщений (каждый раз менять ключ), то его сложно расшифровать частотным.
Шифр Вернама хорош как раз из-за того, что один и тот же ключ не переиспользуется, но если мы будем иметь N сообщений зашифрованных одним ключом, то его с лёгкостью удасться взломать.
Так что ваш коммент никак не противоречит моему изначальному комменту, а только его подтверждает.
Что сколь угодно случайный ключ можно будет расшифровать при достаточном кол-ве зашифрованных данных...
И тут главная фишка вообще не в случайном ключе, а в том, что этот ключ одноразовый.
Ну, вообще, по-хорошему, любой ключ должен быть одноразовым. Если мы хотите зашифровать несколько сообщений один ключом, то мы мысленно дописываем одно сообщение после другого и всё равно шифруем только один раз.
В этом смысле, размер "датасета", как Вы выразились — это просто длина шифруемого сообщения. И важным параметрам для шифра является именно "какой длины сообщение можно им зашифровать без риска для взлома".
Переиспользование ключей для нескольких разных сообщений в лучшем случае является сомнительной практикой, а в худшем просто напросто влечёт к прямому взлому. Поэтому нет особого смысла об этом говорить(если мы о хороших практиках, разумеется).
Поэтому в классической постановке, без нарушений условий эксплуатации одноразовый блокнот не поддаётся частотный анализу. А если же мы допускаем нарушения условий эксплуатации, то гораздо более эффективно воспользоваться человеческим фактором...
Поэтому нет особого смысла об этом говорить(если мы о хороших практиках, разумеется).
Почему нет смысла говорить, если доставка ключа это тоже важно?
Один из факторов популярности асимметричных как раз в том, что публичный ключ можно передавать по незащищенному каналу.
И я бы не сказал, что использование асимметричных это плохая практика.
Всё упирается в нужды, чем мы готовы пожертвовать ради чего-то другого, что получим.
А есть ли шифры, которые нельзя математически нельзя расшифровать без закрытого ключа или иной секретной информации?
Ассиметрический шифр всегда можно взломать, если потратить достаточно много времени.
Для этого достаточно перебрать все возможные сообщения, все возможные закрытые ключи и все возможные значения источников случайности. Таким образом, рано или поздно, мы найдём а) наш шифротекст б) закрытый ключ (или несколько) который расшифровывает все сообщения (которые мы перебрали). (Разумеется сообщений для перебора бесконечно много, но мы можем перебрать все сообщения шифротексты которых подходят по длине искомого шифротекста — это можно сделать за конечное время).
Мы зашифровали наше сообщение — и знаем последовательность [1060, 1089, 1292, 1698, 709, 532, 178, 1271] и шаги шифрования, но расшифровать наше сообщение не представляется возможным. Зная только открытый ключ, подобрать исходные биты сложно. Попробуйте подобрать для числа 3420 комбинацию, какие биты были единицами, а какие нулями.
А это и не требуется в данном случае. Достаточно зашифровать открытым ключом каждый из 256 различных байтов, чтобы получить полный словарь.
Вы правы, в данном примере таблица из 256 предвычисленных значений позволит расшифровать символ по шифротексту, зная открытый ключ. Думаю мы оба с Вами понимаем, что пример учебный, но на мой взгляд, предложенный метод больше относится к атаке/взлому шифра, чем к расшифровке.
Спасибо за интересный комментарий и благодарю за внимательное прочтение.
Да, абсолютно, спасибо. Именно поэтому нельзя использовать RSA в чистом виде для шифрования коротких сообщений, например, ПИН-кодов карт.
Начинающим разбираться в асимметричных алгоритмах шифрования будет ещё полезно рассказать, что оно работает в обе стороны - зашифрованное открытым ключом можно расшифровать только закрытым, а зашифрованное закрытым - соответствующим ему закрытым. Так, если взять сообщение, вычислить его хэш и зашифровать этот хэш своим закрытым ключом, то получим примитивную цифровую подпись. Любой желающий расшифровав открытым ключом подписанный хэш и сравнить его с вычисленным хэшем исходного сообщения и удостоверится, что во-первых, оно не было изменено, а во-вторых, его авторство принадлежит владельцу закрытого ключа.
Так мы плавно приходим к сертификатам, которые удостоверяют принадлежность закрытых ключей владельцам сертификатов.
Спасибо большое за статью! Поясните, пожалуйста, в алгоритме RSA при шифровании вы добавляете 13, а при расшифровке отнимаете. Откуда оно вообще берётся, и как тот кто шифрует открытым ключем и тот, кто расшифровывает закрытым его узнаёт?
Спасибо за комментарий! На самом деле, в настоящем RSA нет никакого «плюс 13» 😄 Это мое небольшое упрощение для учебного примера. Я добавил это, чтобы все зашифрованные буквы стали двухзначными числами.
Это нужно, чтобы избежать неоднозначности. Иначе разным буквам и сочетаниям будут соответствовать одинаковые числа. Например, код 2 (Б) и 1(А) будет означать и сочетание БА, и букву М (21)
«Почему расшифровать сообщение можно только закрытым ключом?»
Но ведь может же быть и наоборот, что закрытым шифруется, а открытым расшифровывается.
Спасибо. Жду новых постов с толь интересным и простым описанием.
Криптография для котиков или почему открытый ключ не может расшифровать сообщение