Недостатки алгоритма цифровой подписи RSA

1. Можно повторно использовать подписанный документ, так как копирование файлов в ЭВМ очень простая задача. Чтобы преодолеть этот недостаток документ должен содержать метку времени (порядковый номер), а проверяющий подпись должен создать базу данных, содержащую метки времени получаемых от отправителя документов. Тогда при повторном предъявлении документа легко обнаружить попытку обмана.

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

3. Стойкость протоколов подписи RSA основана на сложности факторизации большого натурального числа N. В 1978 году, в момент опубликования RSA, считалось, что достаточно взять . В настоящее время выбор уже не обеспечивает защиту от подделки. Таким образом, лицо, подписавшее документ в 1978 году, может сейчас отказаться от своей подписи под этим документом. Или злоумышленник может подделывать подписи под документами, датировав их 1978 годом. Такое свойство электронной цифровой подписи приводит к тому, что будущие историки не будут доверять электронным документам нашего времени.

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

5. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 1018, необходимо использовать при вычислениях N, D и E целые числа не менее 2512 (или около 10154) каждое, что требует больших вычислительных затрат, превышающих на 20-30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.

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

Пример. Допустим, что злоумышленник может сконструировать три сообщения M₁, M₂ и M₃, у которых хэш-значения

m₁ = h(M₁), m₂ = h(M₂), m₃ = h(M₃),

причем m₃ = m₁m₂ (mod N).

Допустим также, что для двух сообщений M₁ и M₂ получены законные подписи

S₁ = m₁^D (mod N) и S₂ = m₂^D (mod N).

Тогда злоумышленник может легко вычислить подпись S₃ для документа M₃, даже не зная секретного ключа D:

S₃ = S₁S₂ (mod N).

Действительно,

S₁S₂ (mod N) = m₁^Dm₂^D (mod N) = (m₁m₂)^D (mod N) = m₃^D (mod N) = S₃.

40.5. Алгоритм цифровой подписи Эль – Гамаля

Алгоритм цифровой подписи Эль – Гамаля основан на сложной вычислительной задаче дискретного логарифмирования. Для его описания напомним сначала необходимые понятия.

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

Конечное поле F(q) с конечным числом q элементов играет важную роль в криптографии. В общем случае число элементов конечного поля имеет вид

q = pⁿ,

где p – некоторое простое число и n ³1. Конечные поля называют полями Галуа и обозначают GF(pⁿ) или GF(p) при n =1. Многие криптосистемы шифров с открытым ключом базируются на полях Галуа GF(p), где p – большое простое число.

Пример. Поле Галуа GF(5) имеет элементы 0, 1, 2, 3, 4 и описывается следующими таблицами сложения и умножения.

+							х

Если p – простое число, то число a Î{1,…,p–1} является взаимно простым с p, и поэтому обратный элемент a^–1 существует. Тем самым однозначно определяется операция деления.

Обозначим через GF*(p) множество всех ненулевых элементов поля GF(p). Некоторый элемент g из GF*(p) называют образующим или порождающим элементом GF*(p), если для всех a из GF*(p) найдется такое целое x, что g^x = a modp. Всего имеется j(p –1) образующих элементов g. Число x называют дискретным логарифмом элемента a по основанию g и модулю p. Вычисление дискретных логарифмов (когда заданы g, a и p) примерно такая же труднорешаемая задача, как и задача разложения целого числа на множители.