19. Перевірка чисел на взаємну простоту (розширений алгоритм Евкліда)

Отметим, что значение a_i может быть вычислено как MOD(a_i-2, a_i-1), но достоинство приведенного выше выражения заключается в том, что a_i вычисляется аналогично вычислению коэффициентов x_i и y_i. Этот факт используется в следующем алгоритме.

20. Знаходження секретного ключа (рівняння Діофанта)

Диофа́нтово уравнение или уравнение в целых числах — это уравнение с неизвестными, которые могут принимать только целые значения. Общий вид: ax + by + ... + cz = d.

В литературе под диофантовыми уравнениями понимаются также уравнения более частного вида (с двумя неизвестными): ax + by = c (1), которые достаточно хорошо изучены. Рассмотрим такие уравнения более подробно. Если (то есть c не делится нацело на НОД(a,b)), то уравнение (1) не разрешимо в целых числах. В самом деле, в этом случае , но тогда число, стоящее слева в (1) делится на (a,b), а стоящее справа — нет. Если в уравнении ax + by = 1 (a,b) = 1, то оно разрешимо в целых числах.

Пусть (x₀,y₀) — решение уравнения ax + by = c. Тогда все его решения находятся по следующим формулам: x = x₀ - bn, y = y₀ + an, .

21. Шифрування методом rsa (дискретне піднесення до степеня)

В настоящее время лучшим криптографическим алгоритмом с открытым ключем считается RSA. Перед изложением метода RSA определим некоторые термины.

Под простым числом будем понимать такое число, которое делится только на 1 и на само себя.

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

Под результатом операции i mod j будем понимать остаток от целочисленного деления i на j.

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

1. Случайным образом выбираются два секретных простых числа, p и q, pq.

2. Вычисляется r=pq.

3. Вычисляется =(p-1)(q-1).

4. Выбираются открытый (Ко) и секретный (Кс) ключи, которые являются взаимно простыми с  и удовлетворяют условию (КоКс) mod  = 1.

Чтобы зашифровать данные открытым ключем Ко, необходимо:

1) разбить исходный текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0, 1, ..., n-1;

2) зашифровать последовательность чисел M(i) по формуле

C(i)=(M(i)^Ко) mod n,

где последовательность чисел C(i) представляет шифротекст.

Чтобы расшифровать эти данные секретным ключем Кс, необходимо выполнить следующие вычисления:

M(i)=(C(i)^Кс) mod n.

В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

22. Розшифрування криптограм rsa.

RSA – криптографическая система открытого ключа, обеспечивающая такие механизмы защиты как шифрование и цифровая подпись (аутентификация – установление подлинности). Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков Ronald Rivest, Adi Shamir и Leonard Adleman.

Алгоритм RSA работает следующим образом: берутся два достаточно больших простых числа p и q и вычисляется их произведение n = p*q; n называется модулем.

Затем выбирается число e, удовлетворяющее условию 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом (p - 1)*(q - 1).

Затем вычисляется число d таким образом, что (e*d - 1) делится на (p - 1)*(q – 1).

• e – открытый (public) показатель

• d – частный (private) показатель.

• (n; e) – открытый (public) ключ

• (n; d). – частный (private) ключ.

Делители (факторы) p и q можно либо уничтожить либо сохранить вместе с частным (private) ключом.

Если бы существовали эффективные методы разложения на сомножители (факторинга), то, разложив n на сомножители (факторы) p и q, можно было бы получить частный (private) ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой – практически неразрешимой – задаче разложения n на сомножители (то есть на невозможности факторинга n) так как в настоящее время эффективного способа поиска сомножителей не существует.

Предположим, Алиса хочет послать Бобу сообщение M. Алиса создает зашифрованный текст С, возводя сообщение M в степень e и умножая на модуль n: C = M^**e* (mod n), где e и n – открытый (public) ключ Боба. Затем Алиса посылает С (зашифрованный текст) Бобу. Чтобы расшифровать полученный текст, Боб возводит полученный зашифрованный текст C в степень d и умножает на модуль n: M = c**^d*(mod n); зависимость между e и d гарантирует, что Боб вычислит M верно. Так как только Боб знает d, то только он имеет возможность расшифровать полученное сообщение.

Существует несколько способов взлома RSA. Наиболее эффективная атака — найти секретный ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом, и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n — p и q. На основании p, q и e (общий показатель) нападающий может легко вычислить частный показатель d. Основная сложность в поиске главных сомножителей (факторинг) n. Безопасность RSA зависит от разложения на сомножители (факторинга), что является трудной задачей, не имеющей эффективных способов решения.

Фактически, задача восстановления секретного ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот, можно использовать n для поиска d (см. подпп. 2.3.4 и 2.3.5 о факторинге). Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы (см. подп. 2.3.5).

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = M^e mod n, то корнем степени e из mod n является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки — единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

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

Самое простое нападение на отдельное сообщение — атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст, затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака на единственное сообщение применяется в том случае, если отправитель посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападающий может перехватить эти сообщения и расшифровать сообщение M.

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