Способ изготовления вслепую цифровой rsa-подписи и устройство для его реализации (варианты)

Способ изготовления вслепую цифровой rsa-подписи и устройство для его реализации (варианты)

Реферат

 

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

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

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

В схеме RSA, называемой так по первым буквам имен ее изобретателей (Rivest, Shamir, Adleman), используют представление данных целыми числами из некоторой системы вычетов по модулю целого числа N, называемого RSA-модулем. В качестве системы вычетов обычно используют целые числа от 0 до N-1. Понятия, связанные со схемой RSA ([1], стр. 285, 433; [2], стр. 466-474), могут быть снабжены, для определенности, префиксом RSA, например, RSA-подпись, RSA-шифрование, RSA-ключ, RSA-экспонента и т.п.

Данные S удовлетворяют свойству цифровой RSA-подписи для данных М по отношению к RSA-ключу с модулем N и экспонентой E или, иными словами, являются цифровой RSA-подписью для данных M, если M S^E(modN). При этом под RSA-ключом имеются в виду произвольные данные, определяющие модуль и экспоненту, экспонента представляет собой некоторое целое число, а запись A B (modN) означает, что A и B сравнимы по модулю N, то есть что целое число (A - B) делится нацело на N.

Известен способ изготовления цифровой RSA-подписи [3], в котором цифровую RSA-подпись для данных М изготавливают RSA-шифрованием данных М, при котором в качестве шифровального ключа используют секретный RSA-ключ подписывающей стороны, соответствующий открытому RSA-ключу с модулем N и экспонентой E. При этом под RSA-шифрованием имеется в виду обработка данных X, в результате которой получают данные Y, удовлетворяющие соотношению Y X^C(modN), где С и N, соответственно, экспонента и модуль шифровального RSA-ключа. Под соответствием двух RSA-ключей имеется в виду возможность проверки цифровой RSA-подписи, изготовленной одним RSA-ключом, с помощью другого RSA-ключа или, что то же самое, возможность расшифровки данных, зашифрованных одним ключом, посредством другого ключа. Соответствие RSA-ключей с экспонентами A и B и модулем N обеспечено условием AB 1(mod(N)), где (N) - число вычетов, взаимно простых с N.

Однако изготовление цифровой RSA-подписи для исходных данных М непосредственным RSA-шифрованием исходных данных секретным RSA-ключом подписывающей стороны не обеспечивает приватности подателей, так как предназначенные для подписания исходные данные доступны подписывающей стороне при изготовлении подписи. Это пояснено в [4], где введена концепция изготовления цифровой подписи вслепую, предназначенная для преодоления этого недостатка.

Известен способ изготовления вслепую цифровой RSA-подписи [5], в котором податель, желающий получить цифровую RSA-подпись для исходных данных М, выбирает рандомизированный маскировочный ключ R и создает замаскированные данные М' в соответствии с формулой M R^EM(modN), где E - экспонента, a N - модуль открытого RSA-ключа. Замаскированные данные предоставляются подписывающей стороне, которая возвращает подателю цифровую RSA-подпись S' для замаскированных данных. Податель завершает изготовление цифровой RSA-подписи S для исходных данных демаскировкой полученной цифровой RSA-подписи для замаскированных данных, которую проводит в соответствии с формулой S SR^-1(modN). Известный способ обеспечивает непрослеживаемость, то есть практическую невозможность для подписывающей стороны, получившей впоследствии подписи многих исходных данных, установить соответствие между этими подписями и обработанными замаскированными данными. Однако известный способ не позволяет изготовить вслепую цифровую RSA-подпись без предварительного знания вида подписи, так как экспонента E открытого ключа, определяющая вид подписи, используется при создании замаскированных данных.

Известен способ изготовления вслепую неожидаемой цифровой RSA-подписи [6] , который является наиболее близким аналогом к предлагаемому изобретению и выбран в качестве прототипа. В этом способе используют набор допустимых открытых RSA-экспонент E₁,..., E_k и набор данных (g₁,...,_u), названных генераторами. Для каждого генератора g_j публикуют цифровые RSA-подписи S_ij, соответствующие каждой допустимой открытой RSA-экспоненте E_i. Податель выбирает в качестве рандомизированного маскировочного ключа R набор (k₁,...,k_u) и создает замаскированные данные М' в соответствии с формулой M'=Mg₁^k1... g_u^ku(mod N), где N модуль открытого RSA-ключа. Замаскированные данные M' предоставляют подписывающей стороне, которая выбирает вид подписи, то есть выбирает ту допустимую открытую RSA-экспоненту E_i, которой будет соответствовать изготавливаемая цифровая RSA-подпись. Цифровую RSA-подпись S' для замаскированных данных, соответствующую выбранной открытой RSA-экспоненте E_i, вместе с информацией о выбранной открытой RSA-экспоненте E_i, предоставляют подателю. Податель получает цифровую RSA-подпись S для исходных данных демаскировкой S', которую проводят в соответствии с формулой S SS^-k1_i,1...S^-ku_i,u (modN). Непрослеживаемость в известном способе изготовления вслепую неожидаемой цифровой RSA-подписи определенными свойствами генераторов по отношению к секретным RSA-ключам, в связи с чем используется тестирование пригодности генераторов методом "cut and choose" Подпись в известном способе называется неожидаемой, так как податель, в момент предоставления подписывающей стороне замаскированных данных, не знает вида изготавливаемой подписи, то есть той открытой RSA-экспоненты, которой будет соответствовать изготавливаемая подпись.

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

Известно устройство для изготовления вслепую цифровой RSA-подписи [5]. Однако этого устройства не достаточно для изготовления для изготовления вслепую неожидаемой цифровой RSA-подписи.

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

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

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

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

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

Заявленный способ изготовления вслепую цифровой RSA-подписи предназначен исключительно для аппаратной или компьютерной реализации, так как сама цифровая RSA-подпись реализуется только на аппаратной или компьютерной основе [3].

В описании изобретения используются известные устройства, реализующие основные арифметические функции и основные функции модулярной арифметики. Такие устройства могут работать с данными, представляющими целые числа подходящей разрядности. Для уточнения терминологии далее описана функциональность используемых устройств. Под модулярным умножителем имеется в виду устройство с модульным и двумя аргументными входами, причем если на модульный вход подано целое число N, а на аргументные входы поданы целые числа X, Y, то на выходе появляется целое число Z такое, что Z XY(modN). Под модулярным инвертором имеется в виду устройство с модульным и аргументным входами, причем если на модульный вход подано целое число N, а на аргументный вход подано целое число X, взаимно простое с N, то на выходе появляется целое число Y такое, что XY 1(modN). Под модулярным вычислителем частного имеется в виду устройство с модульным входом и входами делимого и делителя, причем если на модульный вход подано целое число N, на вход делимого подано целое число X, а на вход делителя подано целое число Y, взаимно простое с N, то на выходе появляется целое число Z такое, что ZY X(modN). Под модулярным экспоненциатором имеется в виду устройство с модульным, базовым и экспонентным входами, причем если на модульный вход подано целое число N, на базовый вход подано целое число X, а на экспонентный вход подано целое число E, то на выходе появляется целое число Z такое, что Z X^E(modN). Под тестером взаимной простоты имеется в виду устройство с двумя входами, причем если на входы поданы целые числа A и B, то на выходе появляется логическое значение "Истина", если наибольший общий делитель A и B равен единице, и логическое значение "Ложь" в ином случае.

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

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

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

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

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

В частности, при выборе секретных множителей их отбор производят по наперед заданной вероятности отличия множества всех замаскированных данных, созданных по одним случайно выбранным исходным данным, от аналогичного множества для других случайно выбранных исходных данных.

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

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

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

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

Под модулярным мультипликативным евклидовым преобразователем (ММЕП) имеется в виду устройство, имеющее модульный вход, два базовых входа, два соответствующих экспонентных входа и один выход, причем если на модульный вход ММЕП подано целое положительное число N, на один из базовых входов подано взаимно простое с N целое число X, на соответствующий ему экспонентный вход подано целое число A, на другой базовый вход подано взаимно простое с N целое число Y, а на соответствующий ему экспонентный вход подано целое число B, причем целые числа A и B взаимно просты, то на выходе появляется целое число Z такое, что Z X^CY^D(modN), где С и D - произвольные целые числа, удовлетворяющие соотношению AС + BD = 1. В литературе ([7], стр. 367-368) имеются сведения, достаточные для создания ММЕП специалистами среднего уровня. Для настоящего изобретения существенным является функция, выполняемая ММЕП, а не его конкретная реализация. Тем не менее для подтверждения реализуемости далее в примерах 8 и 10 приведен пример конкретной реализации ММЕП и его работы, а в приведенном ниже примере 1 реализации способа изготовления вслепую цифровой RSA-подписи по первому варианту дано краткое пояснение осуществления демаскировки частным случаем ее реализации с использованием ММЕП.

Сущность способа изготовления вслепую цифровой RSA-подписи по первому варианту состоит в том, что подписывающая сторона выбирает в качестве секретных множителей простые числа P и Q, как и в прототипе, но удовлетворяющие дополнительно условию Н.О.Д.(Р-1, Q- 1) = 2 (сокращение Н.О.Д.(X, Y) используется для обозначения наибольшего общего делителя целых чисел X и Y). Выбор RSA-модуля N, открытой RSA-экспоненты E осуществляют так же, как и прототипе. RSA-модуль N и открытая RSA-экспонента E сообщается заинтересованным сторонам. Кроме того, подписывающая сторона сообщает подателям маскирующий множитель G, который выбирает кратным всем делителям Р-1 и Q-1 в задаваемом диапазоне. Податель, желая создать подпись на исходных данных М, выбирает в качестве рандомизированного маскировочного ключа целое число R, кратное W, и такое, что Н. О. Д (R, E) = 1, и производит маскировку исходных данных М, создавая на их основе замаскированные данные М' в соответствии с формулой M M^R(modN). Ниже в тексте описания термин "рандомизированный маскировочный ключ" может быть для краткости заменен термином "маскировочный ключ" в тех случаях, когда не требуется подчеркнуть происхождение маскировочного ключа. Цифровую RSA-подпись S' для данных М' изготавливают так же, как и прототипе, то есть в соответствии с формулой S (M)^D(modN), где D - секретная RSA-экспонента, соответствующая открытой RSA-экспоненте E. Податель, получив данные S', завершает изготовление цифровой RSA- подписи S для исходных данных M демаскировкой S' в соответствии с формулой S (S)^AM^B(modN), где A и B связаны соотношением AR + BE = 1. В частности, податель может сначала изготовить целые числа A и B, в соответствии с хорошо известным обобщенным алгоритмом Евклида, а затем данные S. Разумеется, податель известными способами может проверить, что изготовленная цифровая RSA-подпись S удовлетворяет свойству подписи для исходных данных М.

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

Указанный выше технический результат при осуществлении способа изготовления цифровой RSA-подписи по первому варианту достигается, в частности, тем, что при выборе секретных множителей верхнюю границу U задаваемого диапазона выбирают по наперед заданной вероятности W отличия множества всех замаскированных данных, созданных по одним случайно выбранным исходным данным, от аналогичного множества для других случайно выбранных исходных данных. Иными словами, речь идет о вероятности такого неудачного выбора подателем исходных данных, который приведет к специфическому виду замаскированных данных и, тем самым, не обеспечит непрослеживаемости. Выбор W = 10^-8 обеспечивает практически полную непрослеживаемость. Для оценки того, какой достаточно взять верхнюю границу U, обеспечивающей необходимую вероятность W, предположим, что P и Q - различные нечетные простые числа, N = PQ, G - маскирующий множитель, кратный всем общим делителям Р-1 и Q-1 и кратный всем делителям каждого из чисел P-1 и Q-1, не превосходящим некоторой границы U. Предположим, что замаскированные данные М' связаны с М соотношением M X^GRmodN, где R - случайно выбранное число. Вероятность W того, что для случайно выбранных данных М множество всех замаскированных данных, созданных на основе М, отличается от множества G-тых степеней по модулю N равна 1 - V. При этом V - вероятность того, что множество всех замаскированных данных, которые могут быть созданы на основе случайных и равномерно распределенных среди обратимых вычетов по модулю N исходных данных М, то есть множество обратимых вычетов вида М^R (mod N), где R пробегает все целые числа, кратные G, совпадает с группой Z всех обратимых вычетов вида C^G (mod N), где С пробегает все обратимые вычеты по модулю N. Вероятность V не меньше, чем произведения чисел (1-L^-1), где L пробегает простые делители (P - 1)(Q - 1), большие U. Тем самым вероятность W меньше, чем Log(N)/[ULog(U + 1)]. Кроме того, оценка W дает и оценку вероятности W₁ того, что для случайных исходных данных X, равномерно распределенных среди обратимых вычетов по модулю N, и случайных независимых данных Y₁ и Y₂, равномерно распределенных среди тех обратимых вычетов по модулю N, которые являются G-тыми степенями по модулю N, вероятность получения Y₁ маскировкой X равна вероятности получения Y₂ маскировкой X. Близость W₁ к 1 также обеспечивает непрослеживаемость и, следовательно, вероятность W₁ определяет уровень маскировки.

Кроме того, в качестве секретных множителей подписывающая сторона может взять простые числа вида 2L + 1, где L также простое число.

Ниже приведен пример конкретной реализации способа изготовления вслепую цифровой RSA-подписи по первому варианту.

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

При выборе первого секретного множителя подписывающая сторона получает посредством датчика случайных чисел начальные пробные данные P и тестирует следующие их свойства: (а) нечетность; (б) несравнимость с 1 по модулю 4 и всех простых нечетных чисел, не превосходящих 10; (в) простоту. Если пробные данные не проходят хотя бы один из этих тестов, то они бракуются и начинается тестирование очередных пробных данных, полученных например, добавлением 1 к предыдущим пробным данным. Эта процедура продолжается до тех пор, пока очередные пробные данные не пройдут всех тестов и будут приняты, в этом случае, в качестве первого секретного множителя. Допустим, что в качестве начальных пробных данных выбраны данные P = 414. Они не выдерживают теста на нечетность и бракуются. Очередные пробные данные P = 415 не выдерживают теста на несравнимость с единицей по модулю 3 и также бракуются. Пробные данные 416 и 418 будут забракованы тестом на нечетность, пробные данные 417 будут забракованы тестом на несравнимость с 1 по модулю 4, а очередные пробные данные P = 419 выдержат все тесты и будут приняты в качестве первого секретного множителя. После этого подписывающая сторона выбирает аналогичным образом второй секретный множитель. Для этого подписывающая сторона выбирает посредством датчика случайных чисел начальные пробные данные Q и тестирует их свойства (а), (б), (в), указанные выше, а если пробные данные выдерживают все эти тесты, то осуществляют дополнительное попарное тестирование секретных множителей на одновременную сравнимость с единицей по модулю произвольных нечетных делителей, где термин "попарно" означает, что такое тестирование осуществляют для каждой пары секретных множителей. В частности, такое тестирование может быть осуществлено сравнением значения наибольшего общего делителя уменьшенных на единицу секретных множителей с целым числом, равным двум. Так как в этом примере имеется всего одна пара секретных множителей (P, Q), то для этой пары тестируется следующее свойство (г) Н.О.Д. (Р-1, Q-1) = 2. Если очередные пробные данные выдерживают и этот тест, то их принимают в качестве второго секретного множителя и на этом заканчивают выбор секретных множителей. Допустим, что в качестве начальных пробных данных выбраны данные Q = 857. Начальные пробные данные 857 бракуются тестом на несравнимость с 1 по модулю 4, очередные пробные данные 858 бракуются тестом на нечетность. Следующие пробные данные 859 бракуются тестом (б), и начинается тестирование очередных пробных данных 860. Пробные данные 860 и 862 бракуются тестом на четность, а пробные данные 861 бракуются тестом на несравнимость с 1 по модулю 4. В итоге пробные данные Q = 863 пройдут все тесты и будут приняты в качестве второго секретного множителя.

После этого подписывающая сторона создает RSA-модуль N, например, посредством умножителя подходящей разрядности, как произведение секретных множителей. В этом примере N = PQ = 419863 = 361597. В качестве открытой RSA-экспоненты E подписывающая сторона выбирает произвольное число, взаимно простое с P-1 и Q-1, например E = 3. После этого RSA-модуль 361597 и открытая RSA-экспонента E = 3 сообщаются всем заинтересованным потенциальным подателям.

Предположим, что податель желает изготовить вслепую для подписывающей стороны цифровую RSA-подпись некоторых исходных данных M в диапазоне от 0 до N-1. Для определенности рассмотрим М = 123456. Податель посредством датчика случайных чисел выбирает маскировочный ключ R, размер которого сопоставим с размером RSA-модуля. Например, пусть R= 901. Проверив четность маскировочного ключа R и взаимную простоту R относительно открытой RSA-экспоненты E = 3, податель приступает к созданию замаскированных данных М'. A именно, в качестве замаскированных данных принимают результат RSA-шифрования RSA-ключом (N, R) = (361597, 901) исходных данных М = 123456. Это RSA-шифрование можно произвести модулярным экспоненциатором, на модульный вход которого подают RSA-модуль, N = 361597, на базовый вход которого подают исходные данные М = 123456, на экспонентный вход которого подают маскировочный ключ R = 901, а выходные данные которого принимают в качестве замаскированных данных М'. На выходе модулярного экспоненциатора получим цифровые данные M^R(modN) (123456)⁹⁰¹(mod361597) = 237367. Итак, M'= 237367.

Подписывающая сторона до создания цифровой RSA-подписи S для замаскированных данных М' создает секретный ключ (N, D), где экспонента D секретного RSA-ключа D создается посредством модулярного инвертора, на модульным вход которого подается (N) = (P-1)(Q-1) = 418862 = 360316, на аргументный вход которого подается выбранная открытая RSA-экcпoнентa E = 3, а на выходе которого появляется D E^-1(modN) = 3^-1(mod360316) = 240211. Далее подписывающая сторона так же, как и прототипе, создает цифровую RSA-подпись S' для замаскированных данных М'. Это может быть сделано посредством модулярного экспоненциатора, на модульный вход которого подают RSA-модуль N = 361597, на базовый вход которого подают замаскированные данные М' = 237367, на экспонентный вход которого подают экспоненту секретного RSA-ключа D = 240211, а выходные данные которого принимают в качестве цифровой RSA-подписи S' для замаскированных данных М'. Тем самым Получив цифровую RSA-подпись S' для замаскированных данных М податель осуществляет демаскировку данных S' и, тем самым, создает цифровую RSA-подписи S для исходных данных М. Для этого податель подает данные S' = 88275 на первый базовый вход модулярного мультипликативного евклидова преобразователя (ММЕП), а исходные данные М = 123456 на второй базовый вход ММЕП, маскировочный ключ R = 901 на первый экспонентный вход ММЕП, открытую экспоненту E = 3 на второй экспонентный вход ММЕП, а RSA- модуль N = 361597 на модульный вход ММЕП. На выходе появляются данные S = 88275278670 (mod 361597) = 150340, которые и являются цифровой RSA-подписью для исходных данных М = 123456.

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

Кроме того, то, что податели могут убедиться в том, наибольший общий делитель уменьшенных на единицу секретных множителей равен двум, а также в том, что сообщенный подписывающей стороной маскирующий множитель G действительно кратен всем делителям уменьшенных на единицу секретных множителей в указанном ей диапазоне без раскрытия подписывающей стороной секретных множителей с помощью известного метода "cut and choose". А именно, подписывающая сторона выбирает первоначально большое количество наборов RSA-модулей и маскирующих множителей и опубликовывает их. Представитель подателей выбирает все наборы, кроме одного, после чего подписывающая сторона раскрывает для каждого выбранного представителем подателей набора соответствующие секретные множители. Имея секретные множители, представитель подателей убеждается в правильности выбора секретных и маскирующих множителей в выбранных им наборах. Тем самым, представитель подателей косвенным образом убеждается и в правильности выбора секретных множителей и маскирующего множителя в невыбранном им наборе, а подписывающая сторона использует этот оставшийся набор при изготовлении подписи.

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

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

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