Как расшифровать rsa файл

Шифрование RSA для первокурсников

Когда я учился программировать, меня всегда раздражало решать на практиках неинтересные задачи. Теперь я преподаю, и мне не хочется, чтобы студенты скучали на моих занятиях.

В этой статье я решаю на языке MIT Scheme задачу шифрования и дешифрования методом RSA [1]. По ряду причин, которые рассматриваются в статье, реализация не может использоваться для криптографической защиты информации.

Генерация ключей — поиск простых чисел

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

Первый этап генерации ключей — случайный выбор двух достаточно больших простых чисел p и q. Натуральное число x называется простым, если у него есть ровно два различных делителя: 1 и x. Все другие делители числа располагаются на отрезке от 2 до квадратного корня из x, однако достаточно проверять на кратность только простые делители, принадлежащие этому отрезку.

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

Генерация ключей — поиск взаимно простого числа

Для вычисления вторых элементов открытого и закрытого ключей используется величина fi, равная функции Эйлера [3], вычисленной на n. Функция Эйлера от x равна количеству натуральных чисел, не больших x и взаимно простых с ним. Для n это количество будет равно произведению p-1 и q-1.

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

Для поиска наибольшего общего делителя можно использовать алгоритм Евклида [4].

Генерация ключей — операции в кольце вычетов

Одним из объектов, изучаемых теорией чисел, является кольцо вычетов [5]. Кольцо вычетов по модулю k — это целые числа от 0 до k-1 и операции сложения и умножения на нём. Сложение в кольце вычетов (a + b mod k) отличается от сложения в группе целых чисел тем, что если результат сложения становится больше k, из него вычитается k, в результате чего этот результат снова оказывается в кольце. Интуитивно, кольцо получается из отрезка соединением его концов.

Как и в группе целых чисел, умножение в кольце вычетов можно задать при помощи сложения, а возведение в степень — при помощи умножения. Как и в группе целых чисел, получившиеся операции сложения и умножения будут обладать ассоциативностью, то есть:
a + (b + c mod k) mod k = (a + b mod k) + c mod k
a * (b * c mod k) mod k = (a * b mod k) * c mod k

Вторым элементом открытого ключа должно быть число d такое, что его произведение с e в кольце вычетов по модулю n является 1, то есть мультипликативно обратный элемент. Привожу алгоритм поиска такого элемента при помощи расширенного алгоритма Евклида [6].

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

При помощи алгоритма RSA можно шифровать сообщения, представленные серией чисел M в диапазоне от 0 до n-1. Шифрование состоит в возведении M в степень e в кольце вычетов по модулю n, дешифрование — в степень d. Благодаря тому, что умножение является ассоциативным, мы можем возводить в степень x за log(x) операций [7].

Контрольный пример

В моём примере открытый ключ представляет собой пару (250483 31), закрытый — пару (250483 32191). Зашифрованное сообщение 123456 равно 133240.

Источник

Хватит использовать RSA

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

По какой-то причине люди до сих пор считают RSA хорошим алгоритмом. Но на самом деле, простор для выстрела в ногу при реализации RSA чрезвычайно огромен. Слабые параметры проверить трудно, если не невозможно. А слабая производительность алгоритма побуждает разработчиков использовать рискованные способы её повысить.

Хуже того, атаки типа padding oracle, которые изобрели более 20 лет назад, актуальны и сегодня.
Даже если в теории и возможно имплементировать RSA корректно, на практике такой «подвиг» совершить почти невозможно. И уязвимости, постоянно возникающие уже на протяжении десятилетий, это только подтверждают.

Пару слов об алгоритме RSA

Если знаете, как работает RSA, эту часть можно пропустить.

RSA — криптосистема с открытым ключом, у которой есть два применения.

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

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

Оба алгоритма отличаются незначительными деталями, поэтому будем их называть просто RSA.

Чтобы начать работать с RSA, Алисе нужно выбрать два простых числа p и q, которые вместе образуют группу чисел по модулю N = pq. Потом Алисе нужно выбрать открытую экспоненту e и секретную d такие, что . По сути, e и d должны быть взаимно просты.

Как только эти параметры будут выбраны, Боб может послать Алисе сообщение M, вычислив . Алиса может затем расшифровать сообщение, вычислив .
Цифровая подпись происходит ровно наоборот. Если Алиса хочет подписать сообщение, она вычисляет подпись , которую Боб может проверить, убедившись, что сообщение

Вот как бы и всё, это основная идея. К Padding oracles мы вернёмся попозже, а пока давайте посмотрим что можно сделать если параметры RSA выбраны неверно.

Начало конца

Для работы RSA требуется выбрать довольно много параметров. К сожалению, невинные на первый взгляд методы их выбора могут навредить безопасности. Давайте пройдемся по каждому из них и посмотрим, какие неприятные сюрпризы вас ждут.

Генерация простых чисел

Безопасность RSA основана на том факте, что имея большое число N, являющееся произведением двух простых чисел p и q, разложение N на простые множители, не зная p и q сделать трудно. Разработчики несут ответственность за выбор простых чисел, составляющих модуль RSA. Этот процесс чрезвычайно медленный по сравнению с генерацией ключей для других криптографических протоколов, где достаточно просто выбрать несколько случайных байтов. Поэтому, вместо того чтобы генерировать действительно случайное простое число, разработчики часто пытаются создавать числа определенной формы. Это почти всегда плохо кончается. Существует много способов выбора простых чисел таким образом, чтобы факторинг N был простым. Например, p и q должны быть глобально уникальными. Если p или q когда-либо повторно используются в других модулях RSA, то оба множителя можно легко вычислить с помощью алгоритма GCD. Плохие генераторы случайных чисел делают этот сценарий довольно вероятным, и исследования показали, что примерно 1% трафика TLS в 2012 году было подвержено такой атаке.

Более того, p и q должны быть выбраны независимо друг от друга. Если p и q совместно используют приблизительно половину своих старших битов, то N может быть вычислено с использованием метода Ферма. На самом деле, даже выбор алгоритма тестирования простоты может иметь последствия для безопасности. Пожалуй, самая широко разрекламированная атака — это уязвимость ROCA в RSALib, которая затронула многие смарт-карты, модули доверенных платформ и даже ключи Yubikey. Здесь при генерации ключей используются только простые числа определенной формы для ускорения вычислений. Простые числа, сгенерированные таким образом, тривиально обнаружить, используя хитрые приемы теории чисел. Как только слабая система была распознана, специальные алгебраические свойства простых чисел позволяют злоумышленнику использовать метод Копперсмита для разложения N.

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

Секретная экспонента d

Поскольку использование закрытого ключа большого размера отрицательно влияет на время расшифровки и подписи, у разработчиков есть стимул выбирать небольшую d, особенно в случаях устройств с низким потреблением энергии, таком как смарт-карты. Тем не менее, злоумышленник может восстановить закрытый ключ, когда d меньше корня 4-й степени из N. Вместо этого разработчикам стоит выбирать большое значение d, так, чтобы для ускорения дешифрования могла бы использоваться Китайская теорема об остатках. Однако сложность этого подхода увеличивает вероятность незначительных ошибок реализации, которые могут привести к восстановлению ключа.

Вы скажете, что обычно при инициализации RSA вы сначала генерируете модуль, используете фиксированную открытую экспоненту, а затем выбираете секретную?
Да, это предотвращает атаки с маленькой секретной экспонентой, если вы всегда используете одну из рекомендуемых открытых экспонент e.
К сожалению, это так же предполагает, что разработчики действительно будут этим заниматься. В реальном мире разработчики часто делают странные вещи, например, сначала выбирают d, а потом считают e.

Открытая экспонента e

Как и в случае c секретной экспонентой, разработчики хотят использовать небольшие открытые экспоненты, чтобы сэкономить на шифровании и проверке подписей. Обычно в этом контексте используются простые числа Ферма, в частности e = 3, 17 и 65537.

Несмотря на то, что криптографы рекомендуют использовать 65537, разработчики часто выбирают e = 3, что приводит к множеству уязвимостей в криптосистеме RSA.

(Тут разработчики использовали e = 1, который на самом деле не шифрует открытый текст вообще.)

Когда e = 3 или схожего размера, многое может пойти не так. Маленькие открытые экспоненты часто сочетаются с другими распространенными ошибками, позволяющими злоумышленнику расшифровать определенные шифротексты или факторизовать N.

Например, атака Франклина-Рейтера позволяет злоумышленнику дешифровать два сообщения, которые связаны известным, фиксированным расстоянием. Другими словами, предположим, что Алиса посылает Бобу только «купить» или «продать». Эти сообщения будут связаны известным значением и позволят злоумышленнику определить, какие из них означают «купить», а какие «продать», не расшифровывая сообщения. Некоторые атаки с маленькой e могут даже привести к восстановлению ключа.

Если открытая экспонента маленькая (не только 3), злоумышленник, который знает несколько бит секретного ключа, может восстановить оставшиеся биты и сломать криптосистему. Хотя многие из этих e = 3-атак на RSA можно пофиксить выравниванием (padding), разработчики, которые сами реализуют RSA, чрезвычайно часто забывают его использовать.

Подписи RSA также уязвимы для маленьких публичных экспонент. В 2006 году Блейхенбахер обнаружил атаку, которая позволяет злоумышленникам подделывать произвольные подписи во многих реализациях RSA, в том числе используемых в Firefox и Chrome. Это означает, что любой сертификат TLS из уязвимой реализации может быть подделан. Эта атака использует тот факт, что многие библиотеки используют небольшую публичную экспоненту и не делают простую проверку выравнивания при обработке подписей RSA. Атака Блейхенбахера на подпись настолько проста, что включена во многие упражнения на курсах криптографии.

Выбор параметров — трудная задача

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

Предполагается, что разработчики сами будут управлять этим сложным процессом отбора, поскольку всё, кроме открытой экспоненты, должно генерироваться при инициализации.
Нет простых способов проверить надежность параметров. Вместо этого разработчикам нужна серьёзная математическая база, наличие которой не следует ожидать от рядовых сотрудников. Хоть использование RSA с выравниванием и может спасти вас при наличии неверных параметров, многие по-прежнему предпочитают этого не делать.

Padding Oracle атаки

Как мы уже выяснили выше, простое использование RSA «из коробки» не совсем работает. Например, схема RSA, изложенная во введении, будет создавать идентичные шифротексты, если один и тот же открытый текст когда-либо шифровался более одного раза. Это проблема, потому что это позволит злоумышленнику узнать содержание сообщения из контекста, не имея возможности расшифровать его. Вот почему нам нужно выравнивать сообщения несколькими случайными байтами. К сожалению, наиболее широко используемая схема выравнивания, PKCS # 1 v1.5, часто уязвима к так называемой атаке padding oracle.

Первоначальная атака на PKCS # 1 v1.5 была обнаружена еще в 1998 году Даниэлем Блейханбахером. Несмотря на то, что ей более 20 лет, сегодня она продолжает быть актуальной для многих систем. Современные версии этой атаки часто включают в себя дополнительный оракул, немного более сложный, чем тот, который первоначально описал Блейханбахер, например, время отклика сервера или выполнение какого-либо понижения версии протокола в TLS. Одним особенно шокирующим примером была атака ROBOT, которая была настолько ужасной, что команда исследователей смогла подписать сообщения секретными ключами Facebook и PayPal. Некоторые могут возразить, что это на самом деле не вина RSA — основная математика в порядке, люди просто испортили важный стандарт несколько десятилетий назад. Дело в том, что у нас уже тогда, с 1998 года была стандартная схема выравнивания с строгим доказательством безопасности, OAEP. Но почти никто не использует ее. Даже когда это происходит, общеизвестно, что OAEP сложно реализовать, и он часто уязвим к атаке Мангера, которая является еще одной атакой оракула, которую можно использовать для восстановления открытого текста.

Фундаментальная проблема здесь заключается в том, что выравнивание необходимо при использовании RSA, и эта дополнительная сложность открывает большой простор для атак на криптосистему. Тот факт, что один бит информации, «правильно ли было выровнено сообщение», может оказать настолько большое влияние на безопасность, что делает разработку защищенных библиотек практически невозможной. TLS 1.3 больше не поддерживает RSA, поэтому мы можем ожидать, что в будущем будет меньше таких атак.

Но пока разработчики будут продолжать использовать RSA в своих собственных приложениях, Padding Oracle атаки будут продолжать происходить.

Что делать?

Люди часто предпочитают использовать RSA, потому что они считают, что это концептуально проще, чем запутанный протокол DSA или криптография с эллиптической кривой (ECC). Но хотя RSA интуитивно понятнее, ему очень не хватает защиты от дурака.

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

Во-вторых, любое согласование ключей на основе алгоритма Диффи-Хеллмана или схема подписи (включая варианты эллиптической кривой) не требуют выравнивания и, следовательно, полностью устойчивы к атакам Padding Oracle. Это серьезная победа, учитывая, что у RSA очень длинный послужной список попыток избежать этого класса уязвимостей.

Мы рекомендуем использовать Curve25519 для обмена ключами и ed25519 для цифровых подписей. Шифрование должно выполняться с использованием протокола ECIES, который сочетает в себе обмен ключами ECC с алгоритмом симметричного шифрования. Curve25519 была разработана чтобы полностью предотвратить классы атак, которые могут случиться с другими кривыми, а еще она очень быстрая. Более того, она реализована во множестве библиотек, например libsodium, который снабжен легкой для чтения документацией и доступен для большинства языков.

Хватит использовать RSA. Серьезно.

(Twilio до сих пор использует RSA ключи)

(Travis CI до сих пор использует 1024 битные ключи и не даёт их заменить)

RSA был важной вехой в развитии безопасных коммуникаций, но последние два десятилетия криптографических исследований сделали его устаревшим. Алгоритмы на эллиптических кривых как для обмена ключами, так и для цифровых подписей были стандартизированы еще в 2005 году и с тех пор были интегрированы в интуитивно понятные и устойчивые к неправильному использованию библиотеки, такие как libsodium. Тот факт, что RSA все еще широко используется в наши дни, указывает как на ошибку со стороны криптографов из-за неадекватного описания рисков, присущих RSA, так и со стороны разработчиков, переоценивающих свои способности успешно развертывать его. Security сообщество должно начать думать об этом как о стадной проблеме — хоть некоторые из нас и могут быть в состоянии ориентироваться в чрезвычайно опасном процессе настройки или реализации RSA, исключения дают понять разработчикам, что в некотором роде RSA еще актуален. Несмотря на множество предостережений и предупреждений на StackExchange и GitHub README, очень немногие люди верят, что именно они испортят RSA, и поэтому они продолжают поступать безрассудно. В конечном счете ваши пользователи будут платить за это. Вот почему мы все должны согласиться с тем, что использование RSA в 2019 году совершенно неприемлемо. Без исключений.

Оригинал статьи на английском.

VirgilSecurity, Inc. разрабатывает open source developer friendly SDK и сервисы для защиты данных. Мы позволяем разработчикам использовать существующие алгоритмы с минимальным риском для безопасности.

Источник

Выбор параметров шифра RSA и возможные последствия

Под катом описаны примеры выбора «плохих» параметров шифра RSA.

Процитируем авторов учебного пособия «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001г., на странице 316:

«Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля RSA (числа n) для каждого из корреспондентов сети. В связи с этим можно сказать следующее. Читатель может самостоятельно убедиться в том, что зная одну из трех величин p, q или φ(n), можно легко найти секретный ключ RSA…».

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

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

Вначале приведем сам пример со стр. 313-315 из названного пособия.

Пример

Шифрование короткого исходного текстового сообщения: RSA.
Получатель устанавливает шифр с характеристиками n=pq=527, где р=17, q=31 и φ(n)=(р –1)(q – 1)=480. В качестве открытого ключа е выбрано число, взаимно простое с φ(n), е=7. Для этого числа с помощью расширенного алгоритма Евклида найдены целые числа u и v, удовлетворяющие соотношению е∙u+φ(n)∙v=1:

Поскольку –137≡343(mod480), то d=343.

Текстовое сообщение представляется в виде последовательности чисел, содержащихся в интервале [0, 526]. Для этого буквы R, S и A кодируются пятиразрядными двоичными числами. Используются порядковые номера этих букв в английском алфавите при их двоичном представлении:

Тогда RSA=(100101001100001)₂. Разбиение текста на блоки ограниченной длины дает представление из двух блоков: RSA=(100101001), (100001)=(М₁=297, М₂=33).

Здесь воспользовались тем, что:

Шифрованный текст, как и исходный, получаем в виде двух блоков: у₁=474; у₂=407.

Расшифрование представляется последовательностью действий D_k(y_i )=(y_i ) d =(y_i ) 343 (mod 527), i=1,2.

Вычисления возведения в степень d более удобно проводить, предварительно представляя показатель степени суммой степеней числа 2, а именно: 343=256+64+16+4+2+1.

Используя это представление показателя степени d=343, получаем:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
и окончательно 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Аналогично вычисляется значение 407 343 (mod527)=33.

Переход к буквенному представлению расшифрованного сообщения дает: RSA.

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

Атака на шифр RSA

Рассмотрим пример атаки на шифр RSA. Воспользуемся данными примера, приведенного на странице 313-315 в учебном пособии «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001.

Неудачность (недопустимость) выбранных параметров системы в этом примере легко показывается вычислениями, реализующими атаку бесключевого чтения исходного текста. Сущность такой атаки состоит в следующем. Заданы открытый ключ шифра RSA (е=7, n=527) и шифрованный текст. В примере шифрованный текст представлен двумя блоками
у=(у₁=474, у₂=407).

Каждый шифрованный блок атакуется индивидуально, вначале атакуем у₁=474, после его дешифрования, атакуем другой блок у₂=407.

Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений у_i, у₁=у имеющийся шифрованный текст.

В алгоритме атаки на шифрованный текст определяется такой номер шага j, для которого y_i e j (mod n)=(y_i e j–1 (mod n)) e (mod n)=y_i, i>1. Из последнего соотношения видим, что при возведении в степень е значения (y_i e j–1 (mod n)) получается начальный шифoртекст y_i = у₁.

Но это и означает, что на этом шаге шифровался открытый текст. Непосредственными вычислениями (их оказывается совсем немного) с использованием экранного калькулятора находим то значение j, при котором цикл шифрования завершается значением y₁, с которого цикл и был начат.

Атака на первый блок у₁=474 шифртекста.
Шаг 1: &nbsp 474 7 (mod527)=382;
Шаг 2: &nbsp 382 7 (mod527)=423;
Шаг 3: &nbsp 423 7 (mod527)=297;
Шаг 4: &nbsp на этом шаге шифруется уже найденный исходный текст, но его необходимо выполнить, так как атакующий исходного текста не знает. Признаком завершения атаки является совпадение начального значения шифртекста (474) и результата 4-го шага зашифрования. Именно такое совпадение и имеет место.

297 7 (mod527)=474 получили начальный (первый) блок шифртекста. Атака на первый блок завершена успешно у₁=474. Предшествующий результат шага 3 равен открытому тексту М₁=297.

По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=297 по модулю n=527. Это записывается так y_i=у₁=297. Формируем степенные вычеты
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Вновь на третьем шаге получен блок исходного текста (М₂=33), но атакующему это неизвестно, и он выполняет следующий (четвертый шаг), результат которого (407) совпадает с начальным шифртекстом у₂=407.

По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=33 по модулю n=527. Это записывается так y_i=у₂=33.
Формируем степенные вычеты ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Результат атаки (исходный текст М₁=297, М₂=33) получен трехкратным шифрованием заданного шифртекста. Больший успех для атакующего шифртекст трудно представить.

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

Ни на одном из заданных е не удается зашифровать исходные тексты, представляемые числами
187, 341, 154 и 373.

Пример (невозможность шифрования значений некоторых исходных текстов)

Пусть исходные тексты представлены четырьмя блоками y=(y₁=154, y₂=187, y₃=341, y₄=373). Экспонента е открытого ключа шифра может быть любым взаимно простым числом с функцией Эйлера φ(n)=φ(527)=480. Впрочем, для рассматриваемого случая открытый ключ е может быть задан произвольно. Действительно, пусть е=2, 4, 7, 9, 17, 111 тогда:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

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

Источник