Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M) , и только адресату известно, как выполнить операцию f-1. Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n = pq и число d, c (d, p – 1) = (d, q – 1) = 1 (один из возможных способов выполнить это условие – выбрать d больше, чем p/2 и q/2). Шифрование производится по формуле: f(M) = Md х mod n, где M и f(M) оба < n – 1 . Оно может быть вычислено за разумное время, даже если M, d и n содержат весьма большое количество знаков. Адресат вычисляет M на основе Md, используя свое знание p и q. Если dc ? (p_1) 1, тогда (Md)e ? p1.
Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M)) e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.
Аналогично (Md)e ? qM, если dc ? (q_1)1. е удовлетворяет этим двум условиям, если cd ? (p_1) (q_1)1. Мы можем позволить е = x, когда x является решением уравнения dx + (p – 1)(q – 1)y = 1.
Так как (Md)e – M делимо на p и q, оно делимо и на pq. Следовательно, мы можем определить M, зная Md, вычислив его значение в степени е и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, нельзя было вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором приблизительно 1050 комбинаций. Данная проблема изучается уже около 100 лет.
Теоретически можно предположить, что возможно выполнение операции f-l без вычисления p и q. Но в любом случае задача эта непроста, и разработчики считают ее трудно факторизуемой.
Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M и хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно – надо знать все возможные значения Mi.
Проясним использование алгоритма RSA на конкретном примере. Выберем два простых числа p = 7; q = l7 (на практике эти числа во много раз длиннее). В этом случае n = pq будет равно ll9. Теперь необходимо выбрать е. Выберем е = 5. Следующий шаг связан с формированием числа d, так чтобы de = 1 х mod [(p – 1)(q – 1)]. d = 77 (использован расширенный алгоритм Евклида). d – секретный ключ, а е и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать, представляется M = 19. С = Me х mod n. Получаем зашифрованный текст C = 66. Этот 'текст' может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М = Cd х mod n и C = 66. В результате получается M = 19.
На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату.
Возможно ли взломать ЭЦП?
Взлом ЭЦП фактически сводится к взлому алгоритма шифрования. В данном случае возможные варианты взлома мы рассмотрим на примере алгоритма RSA.
Существует несколько способов взлома RSA. Наиболее эффективная атака – найти секретный ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом, и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель) нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n. Безопасность RSA зависит от разложения на сомножители (факторинга), что является трудной задачей, не имеющей эффективных способов решения.
Фактически, задача восстановления секретного ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот: можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.
Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = Me х mod n, то корнем степени e из mod n является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделать подписи, даже не зная секретный ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.
Существуют и другие типы атак, позволяющие, однако, расшифровать только одно сообщение и не позволяющие нападающему вскрыть прочие сообщения, зашифрованные тем же ключом. Кроме того, изучалась возможность расшифровывания части зашифрованного сообщения.
Самое простое нападение на отдельное сообщение – атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст (например, 'Штирлиц – Плей-шнеру'). Затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака на единственное сообщение применяется в том случае, если отправитель посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападающий может перехватить эти сообщения и расшифровать сообщение M.
Такую атаку также можно предотвратить, вводя перед каждым шифрованием в сообщение несколько случайных битов. Кроме того, существуют несколько видов атак по зашифрованному тексту (или атаки отдельных сообщений с целью подделки подписи), при которых нападающий создает некоторый зашифрованный текст и получает соответствующий открытый текст, например, заставляя обманным путем зарегистрированного пользователя расшифровать поддельное сообщение. Разумеется, существуют и атаки, нацеленные не на криптосистему непосредственно, а на уязвимые места всей системы коммуникаций в целом. Такие атаки не могут рассматриваться как взлом RSA, так как говорят не о слабости алгоритма, а скорее об уязвимости конкретной реализации. Например, нападающий может завладеть секретным ключом, если тот хранится без должной предосторожности. Необходимо подчеркнуть, что для полной защиты недостаточно защитить выполнение алгоритма RSA и принять меры математической безопасности, то есть использовать ключ достаточной длины, так как на практике наибольший успех имеют атаки на незащищенные этапы управления ключами системы RSA.
2.3. Современные технологии аутентификации. Смарт-карты
Смарт-карты, подобно Memory-картам, представляют собой пластиковые карты со встроенной микросхемой (ICC, integrated circuit card – карта с интегрированными электронными схемами). Однако смарт-карты представляют собой более сложное устройство, содержащее микропроцессор и операционную систему, контролирующую устройство и доступ к объектам в его памяти. Кроме того, смарт- карты, как правило, обладают возможностью проводить криптографические вычисления.
Назначение смарт-карт – одно-и двухфакторная аутентификация пользователя, хранение информации и проведение криптографических операций в доверенной среде.
Напомню нашим читателям, что двухфакторная аутентификация подразумевает под собой использование двух атрибутов, удостоверяющих личность, например: пароль и отпечаток пальцев, смарт- карта и сетчатка глаза и т. д.
Смарт-карты находят все более широкое применение в различных областях – от систем накопительных скидок до кредитных и дебетовых карт, студенческих билетов и телефонов стандарта GSM.
В зависимости от встроенной микросхемы все смарт-карты делятся на несколько основных типов, кардинально различающихся по выполняемым функциям:
¦ карты памяти;
¦ микропроцессорные карты;
