Какая схема электронной цифровой подписи уязвима к мультипликативной атаке
Определение подлинности информации реализуется путем установки факта, что полученные данные была отправлена подписавшим электронно цифровой подпись, и то что данные не были искажены. На сегодня словосочетание электронная цифровая подпись стало обыденным, а еще не давно считалось что электронный документ проще подделать чем бумажный экземпляр. Письменная подпись под документом используется в качестве доказательства, что человек согласен с содержимым документа. Основные причины доверия к подписи:
- подлинность подписи можно проверить
- подпись которая стоит под одним документом, не может быть использована под другим
- подпись нельзя подделать
- подписанный документ не может быть изменен
- подпись забрать назад нельзя, и поэтому поставив подпись вы не можете потом сказать что не подписывали или не были уведомлены с содержимым документа
В нашем современном криминальном обществе, ни одно из перечисленных свойств на все 100% не реализуются. Можно и подделать подпись, и убрать но это реализуется не просто и быть пойманным есть риск. Существуют также дополнительные вопросы, при отправки документа по почте. Любой документ можно скопировать вместе с подписью. Также можно внести из мнения после подписания документа. Для ликвидации таких угроз используют электронно цифровую подпись. Подделать подпись очень сложно, так как она создается на основе большого объема математических операций. Цифровая подпись может хранится вместе с документом, или быть отдельно от него.
Электронно цифровая подпись — это метод который позволяет на основе реализации криптографических средств определить автора и подлинность документа. Преимущества электронно цифровой подписи:
- большая степень защиты от подделок
- идентификация принадлежности подписи на основе характеристик
- сильная связь с подписываемым документом
Возможные угрозы которые наносят ущерб развитию электронного документооборота показаны на рис.1. Эти угрозы:
- отказ от факта получения документа или авторства
- изменение документа
- замена документа
- замена имени
- повторная рассылка документов
В рамках классической криптографии для аутентификации трудно защитится от всех видом угроз. Эффективно используют схемы подписания, где реализована двухключевая криптография. В этой ситуации каждый пользователь имеет свой секретный ключ. Передающий пользователь несет ответственность за свой секретный ключ. Никто кроме него не может подписать документ именно с такой подписью. К такому ключу можно провести аналогию, как с печаткой. Электронная подпись являет собой длинной число, на основе хеш-функции документа.
Криптостойкость цифровой электронной подписи должна реализовывать надежность к подделкам людьми, которые не имеют секретный ключ. Также должно быть обеспечена защита НСД к месту хранения секретного ключа.
Алгоритм цифровой подписи DSA
DSA — Digital Signature Algorithm — это развитие алгоритмов цифровой подписи Эль Гамаля и К.Шнорра. Получатель и отправитель электронного документа реализуют при вычислении большие целые числа G и P — простые числа, L бит каждое (512 £ L £ 1024), q — простое число длинной 160 бит (делитель числа (P — 1)). Числа P, G, q есть открытыми и могут быть общими для пользователей. Отправитель берет случайное целое число X, 1 < X < q. Число Х — секретный ключ отправителя для создания ЭЦП. Отправитель вычисляет: Y = G X mod P. Число Y — открытый ключ. Что бы подписать документ М, отправитель хэширует его в целое хэш-значение m: m = h(M), 1 < m < q, потом генерирует случайное целое число К, 1 < K < q, и вычисляет: r = (G K mod P) mod q. Также нужно вычислить: s = ((m + r * X)/ K) mod q; Пара чисел S = (r, s) образуют цифровую подпись. Получатель проверяет выполнение условий: 0 < r < q, 0 < s < q. Если условия хоть одно не выполнено, то подпись нужно отвергнуть. Если же выполнены все условия, то получатель вычисляет: w = (l/s) mod q, хэщ-значения m = h(M) и числа u1 = (m * w) mod q, u2 = (r * w) mod q. Затем получатель с помощью открытого ключа Y делает:
v = ((G u1 * Y u2 ) mod P) mod q; Если условие v = r выполняется, тогда подпись S под документом подлинная.
Можно математически доказать, что последнее равенство будет выполнятся тогда, когда подпись S под документом получена с помощью секретного ключа X, из которого был получен открытый ключ Y. Алгоритм DSA имеет преимущества над ЭЦП Эль Гамаля:
- При одинаковом уровне стойкости, длина подписи явно меньше у DSA
- Также меньше время вычисления подписи
В последнее время все больше и больше внедряются в нашу повседневную жизнь информационные технологии, пытаясь захватить в ней все: от важнейших государственных проектов до решения обычных бытовых проблем. Вместе с огромной пользой и, казалось бы, неограниченными возможностями новые технологии приносят и новые проблемы. Одной из них является проблема защиты информации от несанкционированного посягательства теми, кто доступа к этой информации иметь не должен.
Способов защиты информации существует очень много, но каждый из них всегда можно отнести к одному из двух видов: физическое сокрытие информации от противника и шифрование информации.
Данная статья посвящена одной из важнейших задач криптографии – электронной цифровой подписи. Электронная цифровая подпись (ЭЦП) необходима для однозначного установления автора какоголибо документа. ЭЦП служит аналогом обычной подписи, которая устанавливает подлинность какого-либо документа или договора. Электронная цифровая подписьпозволяет осуществить:
- Контроль целостности;
- Защиту от изменений (подделки) документа;
- Невозможность отказа от авторства;
- Доказательное подтверждение авторства документа.
Все эти свойства ЭЦП позволяют использовать её для организации юридически значимого электронного документооборота.
Схемы построения электронной цифровой подписи
Существует несколько схем построения цифровой подписи:
- На основе алгоритмов симметричного шифрования.Данная схема предусматривает наличие в системе третьего лица арбитра, пользующегося довериемобеих сторон. Авторизацией документа является сам факт зашифрования его секретным ключом и передача его арбитру.
- На основе алгоритмов асимметричного шифрования.На данный момент такие схемы ЭЦП наиболее распространены и находят широкое применение.
Кроме этого, существуют другие разновидности цифровых подписей, которые являются модификациями описанных выше схем.
Поскольку подписываемые документы, как правило, достаточно большого объёма, в схемах ЭЦП зачастую подпись ставится не на сам документ, а на его хеш. Хешем называется битовая строка фиксированной длины, полученная путем преобразования входного массива данных произвольной длины.
Использование хеш-функций даёт следующие преимущества:
- уменьшение вычислительной сложности;
- отсутствие проблем с совместимостью;
- возможность проверки целостности данных.
Симметричные схемы ЭЦП менее распространены, чем асимметричные, так как после появления концепции цифровой подписи не удалось реализовать эффективные алгоритмы подписи, основанные на известных в то время симметричных шифрах. Асимметричные схемы цифровой подписи опираются на вычислительно сложные задачи, сложность которых еще не доказана, поэтому невозможно определить, будут ли эти схемы сломаны в ближайшее время. Также для увеличения криптостойкости нужно увеличивать длину ключей, что приводит к необходимости переписывать программы, реализующие асимметричные схемы, и в некоторых случаях перепроектировать аппаратуру. Симметричные схемы основаны на хорошо изученных блочных шифрах.
Асимметричные схемы ЭЦП относятся к криптосистемам с открытым ключом. В схемах цифровой подписи подписывание производится с применением закрытого ключа, а проверка с применением открытого.
Рис 1. Схема подписи и ее проверки с применением хеш-функции
Общепризнанная схема цифровой подписи охватывает три процесса:
- Генерация ключевой пары.При помощи алгоритма генерации ключа выбирается закрытый ключ, далее вычисляется соответствующий ему открытый ключ;
- Формирование подписи.Для заданного электронного документа с помощью закрытого ключа вычисляется подпись;
- Проверка подписи.Для данных документа и подписи с помощью открытого ключа определяется действительность подписи.
Обзор наиболее распространенных алгоритмов ЭЦП
Для генерации пары ключей (секретного и открытого) в алгоритмах ЭЦП используются разные математические схемы, основанные на применении однонаправленных функций. Эти схемы разделяются на две группы. В основе такого разделения лежат известные сложные вычислительные задачи:
- задача факторизации больших целых чисел;
- задача дискретного логарифмирования.
RSA (аббревиатура от фамилий
Rivest, Shamir и Adleman)
Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачусетском технологическом институте США. Надежность алгоритма основывается на трудности факторизации больших чисел.
Алгоритм создания открытого и секретного ключей RSA
подтвержденное цифровой подписью.
Недостатки алгоритма цифровой подписи RSA
- При вычислении модуля n, ключей e и d для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно.Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение.
- Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 1018, необходимо использовать при вычислениях n, d и e целые числа, не менее 2512 каждое, что требует больших вычислительных затрат, превышающих на 2030% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.
- Цифровая подпись RSA уязвима к так называемой мультипликативной атаке.Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа d сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.
Elgamal (схема Эль-Гамаля)
Более надежный и удобный для реализации на персональных компьютерах ЭЦП алгоритм был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем и получил название ElGamalSignatureAlgorithm (EGSA).
Алгоритм создания открытого и секретного ключей Elgamal
Предположим, что стороне A нужно
подтвержденное цифровой подписью.
Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSA:
Однако алгоритм цифровой подписи Эль Гамаля имеет и некоторые недостатки по сравнению со схемой подписи RSA. В частности, длина цифровой подписи получается в 1,5 раза больше, что, в свою очередь, увеличивает время ее вычисления.
DSA (DigitalSignatureAlgorithm) алгоритм цифровой подписи (DSA) предложен в 1991 г. в США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSA является развитием алгоритма ЭЦП EGSA. По сравнению с алгоритмом ЭЦП EGSA, алгоритм DSA имеет ряд преимуществ: сокращен объем памяти и время вычисления подписи. Недостатком же является необходимость при подписывании и проверке подписи выполнять сложные операции деления по модулю большого числа.
Алгоритм создания открытого и секретного ключей DSA
По сравнению с алгоритмом цифровой подписи Эль Гамаля, алгоритм DSA имеет следующие основные преимущества:
Недостатком алгоритма DSA является то, что при подписывании и при проверке подписи приходится выполнять сложные операции деления по модулю q, что не позволяет получать максимальное быстродействие.
Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.
Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа P и Q, затем находит их произведение
и значение функции
Далее отправитель вычисляет число E из условий:
E £ j (N), НОД (E, j (N)) =1
и число D из условий:
Пара чисел (E,N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.
Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис.6.4.
Затем вычисляют цифровую подпись S под электронным документом M, используя хэш-значение m и секретный ключ D:
Пара (M,S) передается партнеру-получателю как электрон-ный документ m, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.
Если соблюдается равенство вычисленных значений, т.е.
то получатель признает пару (M,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу M, а определить секретное число D по открытому числу E не легче, чем разложить модуль N на множители.
Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу E. Поэтому открытый ключ E иногда называют "идентификатором" подписавшего.
Недостатки алгоритма цифровой подписи RSA.
1. При вычислении модуля N, ключей E и D для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.
Рисунок 6.4 – Обобщенная схема цифровой подписи RSA
2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 10 18 , необходимо использовать при вычислениях N, D и E целые числа не менее 2 512 (или около 10 154 ) каждое, что требует больших вычислительных затрат, превышающих на 20…30% вычислительные затраты других алгоритмов циф-ровой подписи при сохранении того же уровня криптостойкости.
3. Цифровая подпись RSA уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа D сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.
Более надежный и удобный для реализации на персональных компьютерах алгоритм цифровой подписи был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем. В 1991 г. НИСТ США обосновал перед комиссией Конгресса США выбор алгоритма цифровой подписи Эль Гамаля в качестве основы для национального стандарта.
Функция h(M) – является хэш-функцией, если она удовлетворяет следующим условиям:
- исходный текст может быть произвольной длины;
- само значение h(M) имеет фиксированную длину;
- значение функции h(M) легко вычисляется для любого аргумента;
- восстановить аргумент по значению с вычислительной точки зрения – практически невозможно;
- функция h(M) – однозначна.
Из определения следует, что для любой хэш-функции есть тексты-близнецы – имеющие одинаковое значение хэш-функции, так как мощность множества аргументов неограниченно больше мощности множества значений. Такой факт получил название «эффект дня рождения».
Наиболее известные из хэш-функций – MD2, MD4, MD5 и SHA.
Алгоритм MD2 предполагает:
- дополнение текста до длины, кратной 128 битам;
- вычисление 16-битной контрольной суммы (старшие разряды отбрасываются);
- добавление контрольной суммы к тексту;
- повторное вычисление контрольной суммы.
Алгоритм MD4 предусматривает:
- дополнение текста до длины, равной 448 бит по модулю 512;
- добавление длины текста в 64-битном представлении;
- использование процедуры Damgard-Merkle с 512-битными блоками (в отличие от хэш-функции этот класс преобразований предполагает вычисление для аргументов фиксированной длины также фиксированных по длине значений), причем каждый блок участвует в трех разных циклах.
В алгоритме MD4 довольно быстро были найдены «дыры», поэтому он был заменен алгоритмом MD5, в котором каждый блок участвует не в трех, а в четырех различных циклах.
Алгоритм SHA (Secure Hash Algorithm) разработан NIST (National Institute of Standard and Technology) и повторяет идеи серии MD. В SHA используются тексты более 264 бит, которые закрываются сигнатурой длиной 160 бит.
При обмене электронными документами по сети связи возникает проблема аутентификации автора документа и самого документа, т. е. установления подлинности автора и отсутствия изменений в полученном документе. В обычной (бумажной) информатике эти проблемы решаются за счет того, что информация в документе и рукописная подпись автора жестко связаны с физическим носителем (бумагой). В электронных документах на машинных носителях такой связи нет.
Электронная цифровая подпись (ЭЦП) используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Функционально она аналогична обычной рукописной подписи и обладает ее основными достоинствами:
- удостоверяет, что подписанный текст исходит от лица, поставившего подпись;
- не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным текстом;
- гарантирует целостность подписанного текста.
При формировании ЭЦП отправитель прежде всего вычисляет хэш-функцию h(M) подписываемого текста M. Вычисленное значение хэш-функции h(M) представляет собой один короткий блок информации m, характеризующий весь текст M в целом.
Затем число m шифруется секретным ключом отправителя. Получаемая при этом пара чисел представляет собой ЭЦП для данного текста M.
Принципиальным моментом в системе ЭЦП является невозможность подделки ЭЦП пользователя без знания его секретного ключа подписывания. В качестве подписываемого документа может быть использован любой файл. Подписанный файл создается из неподписанного путем добавления в него одной или более электронных подписей. Каждая подпись содержит следующую информацию:
- срок окончания действия ключа данной подписи;
- информацию о лице, подписавшем файл (Ф.И.О., должность, краткое наименование фирмы);
- идентификатор подписавшего (имя открытого ключа);
- собственно цифровую подпись.
Технология применения системы ЭЦП предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа. Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и автора подписи. Открытый ключ не позволяет вычислить секретный ключ.
Для генерации пары ключей (секретного и открытого) в алгоритмах ЭЦП, как и в асимметричных системах шифрования, используются разные математические схемы, основанные на применении однонаправленных функций. Эти схемы разделяются на две группы. В основе такого разделения лежат известные сложные вычислительные задачи:
- факторизации (разложения на множители) больших целых чисел;
Алгоритм электронной цифровой подписи RSA. Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA. Согласно этому алгоритму, сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа – P и Q, затем находит их произведение N = PQ и значение функции j(N) = (P – 1)(Q – 1). Далее отправитель вычисляет число E из условий: E £ j(N), НОД[E, j(N)] = 1 и число D из условий: D < N, ED º 1 [mod j(N)]. Пара чисел (E, N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.
Пара (M, S) передается партнеру-получателю как электронный документ M, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.
Если соблюдается равенство вычисленных значений, т. е. SE (mod N) = = h(M), то получатель признает пару (M, S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу M, а определить секретное число D по открытому числу E не легче, чем разложить модуль N на множители. Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу E. Поэтому открытый ключ E иногда называют "идентификатором" подписавшего.
К недостаткам алгоритма электронной цифровой подписи RSA можно отнести следующее:
1 При вычислении модуля N, ключей E и D для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.
2 Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США шифрования информации (алгоритм DES), т. е. 1018, необходимо использовать при вычислениях N, D и E целые числа не менее 2512 (или около 10154) каждое, что требует больших вычислительных затрат, превышающих на 20–30 % вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.
3 Цифровая подпись RSA уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSA позволяет противнику без знания секретного ключа D сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.
Для того чтобы генерировать пару ключей (открытый ключ – секретный ключ), сначала выбирают некоторое большое простое целое число P и большое целое число G, причем G < P. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа P (~10308 или ~21024) и G (~10154 или ~2512), которые не являются секретными.
Пара чисел (a, b) образует цифровую подпись S, проставляемую под документом M. Тройка чисел (M, a, b) передается получателю, в то время как пара чисел (X, K) держится в секрете.
Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSA:
1 При заданном уровне стойкости алгоритма цифровой подписи целые числа, участвующие в вычислениях, имеют запись на 25 % короче, что уменьшает сложность вычислений почти в два раза и позволяет заметно сократить объем используемой памяти.
2 При выборе модуля P достаточно проверить, что это число является простым и что у числа (P – 1) имеется большой простой множитель (т. е. всего два достаточно просто проверяемых условия).
Однако алгоритм цифровой подписи Эль Гамаля имеет и некоторые недостатки по сравнению со схемой подписи RSA. В частности, длина цифровой подписи получается в 1,5 раза больше, что, в свою очередь, увеличивает время ее вычисления.
Российский стандарт электронной цифровой подписи. В российском алгоритме цифровой подписи, определяемом стандартом ГОСТ Р 34.10-94, используются следующие параметры:
p – большое простое число длиной от 509 до 512 либо от 1020 до 1024 бит;
q – простой сомножитель числа (p – 1), имеющий длину от 254 до 256 бит;
a – любое число, меньшее (p – 1), причем такое, что a q mod p = 1;
x – некоторое число, меньшее q;
y = a х mod p.
Кроме того, этот алгоритм использует однонаправленную хэш-функцию h(M). Стандарт ГОСТ Р 34.11-94 определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147-89.
Первые три параметра p, q и a являются открытыми и могут быть общими для всех пользователей сети. Число x является секретным ключом. Число y является открытым ключом.
1 Пользователь A генерирует случайное число k, причем k < q.
2 Пользователь А вычисляет значения r = (a k mod p) mod q, s = x r + k [h(m)]> mod q.
Если h(m) mod q = 0, то значение h(m) mod q принимают равным единице. Если r = 0, то выбирают другое значение k и начинают снова.
Цифровая подпись представляет собой два числа: r mod 2256 и s mod 2256.
Пользователь А отправляет эти числа пользователю В.
3 Пользователь В проверяет полученную подпись, вычисляя последовательно величины v = h(m) q –2 mod q, z1 = (sv) mod q, z2 = ((q – r)v) mod q, u = (mod p) mod q.
Если u = r, то подпись считается верной.
Следует также отметить, что в данном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в значениях параметра q является отражением стремления разработчиков российского стандарта к получению более безопасной подписи.
Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA. Обобщенная схема формирования и проверки цифровой подписи RSA показана на рисунке 6.1.
Криптосистему формирует отправитель (автор) электронных документов. Для этого вычисляет два больших простых числа p и q, затем находит их произведение n=p·q и значение функции Эйлера
j(n)=(p-1)(q-1).
Далее он вычисляет пару ключей (секретный ключ d и открытый ключ e) из условий:
e£j(n), НОД (e, (j(n)) =1 и
Пару чисел (e, n) автор передает партнерам по переписке для проверки его цифровых подписей. Число d сохраняется автором как секретный ключ для подписывания.
Рисунок 6.1. Схема формирования и проверки цифровой подписи RSA
s = m d mod n.
Пара (M, s) передается получателю как электронный документ M, подписанный цифровой подписью s, причем подпись s сформирована обладателем секретного ключа d.
m´= s e mod n.
Кроме того, он находит результат хэширования принятого сообщения M с помощью такой же хэш-функции h(·): m = h(M).
Если соблюдается равенство вычисленных значений, т.е.
s e mod n = h(M),
то получатель признает пару (M,s) подлинной. Доказано, что только обладатель секретного ключа d может сформировать цифровую подпись s по документу M, а определить секретное число d по открытому числу e не легче, чем разложить модуль n на множители.
Можно строго математически доказать, что результат проверки цифровой подписи s будет положительным только в том случае, если при вычислении s был использован секретный ключ d, соответствующий открытому ключу e. Поэтому s называют «идентификатором подписавшего».
Недостатки алгоритма цифровой подписи RSA
1. При вычислении модуля n, ключей e и d для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.
2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США, необходимо использовать при вычислениях n, d и e целые числа не менее 2 512 (или около 10 154 ) каждое, что требует больших вычислительных затрат, превышающих на 20-30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.
3. Цифровая подпись RSA уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа d сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.
Алгоритмы электронной цифровой подписи
Технология реализации системы ЭЦП означает наличие в сети пользователей, которые посылают друг другу подписанные электронные документы. Для каждого пользователя генерируется пара ключей: открытый и секретный. Сектрекный ключ держится абонентом в тайне и реализуется для формирования ЭЦП получателем подписанного электронного документа. Открытый ключ не разрешает вычислить секретный ключ. При генерации пары ключей в алгоритмах ЭЦП, как и в асимметричных системах шифрования, реализованы разные математические схемы, которые основаны на однонаправленых функциях. Эти функции можно разделить на две группы:
- задача факторизации(разложение) больших целых чисел
- задача дискретного логарифмирования
Алгоритм цифровой подписи Эль Гамаля (EGSA)
Основная идея обоснована на практической невозможности фальсификации цифровой подписи. Для этого нужна более сложная вычислительная задача, чем разложение на множители большого целого числа. Также Эль гамалю удалось избежать слабости алгоритма ЭЦП RSA, связанной с подделкой ЭЦП без определения секретного ключа.
К недостаткам можно отнести то, что подпись получается в 1,5 раза больше чем RSA.
Алгоритм цифровой подписи RSA
Первая и самая встречаемая система ЭЦП на основе RSA. Сначала нужно вычислить пару ключей. Отправитель (автор) электронных документов вычисляет два больших простых числа P и Q, затем находит произведение и значение функции:
N = P * Q; φ (N) = (Р-1)(Q-1).
Затем отправитель вычисляет число Е из условий:
Е £ φ (N), НОД (Е, φ (N)) = 1
Пара чисел (E, N) является открытым ключом. Такую пару автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания. Схема показана на рис.1.
Недостатки такой цифровой подписи на основе алгоритма RSA:
- При вычислении модуля N, ключей E, D для цифровой подписи нужно проверять множество дополнительных условий, что на практике трудно. Невыполнение любого из условий делает возможным фальсификации ЭЦП.
- Для достижения криптостойкости подписи RSA к фальсификации по отношению к алгоритмы DES 10 18 , нужно использовать целый числа не менее 2 215 что требует больших вычислительных затрат, а это на 20.. 30% больше чем другие алгоритмы цифровой подписи при той же криптостойкости.
Читайте также: