КУРЖЕЕВСКИЙ И.В., ТОЛМАЧЁВА Ю.С., ШУМКОВА А.А. ИСПОЛЬЗОВАНИЕ ДОПОЛНИТЕЛЬНЫХ ПАРАМЕТРОВ ДЛЯ ПОВЫШЕНИЯ КРИПТОСТОЙКОСТИ СХЕМ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ НА ОСНОВЕ ЗАДАЧИ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ

Ключевые слова: , , , ,


КУРЖЕЕВСКИЙ И.В., ТОЛМАЧЁВА Ю.С., ШУМКОВА А.А. ИСПОЛЬЗОВАНИЕ ДОПОЛНИТЕЛЬНЫХ ПАРАМЕТРОВ ДЛЯ ПОВЫШЕНИЯ КРИПТОСТОЙКОСТИ СХЕМ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ НА ОСНОВЕ ЗАДАЧИ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ


Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
// Современные научные исследования и инновации. 2013. № 1 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2013/01/19939 (дата обращения: 02.06.2017).

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

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

Криптостойкость большинства систем ЭЦП основывается на отсутствии эффективных алгоритмов для решения за приемлемое время следующих двух задач:

- разложение числа на простые множители (факторизация);

- решение задачи дискретного логарифмирования.

Алгоритм ЭЦП Эль-Гамаля с составным модулем  основан на сложности решения задачи факторизации. Факторизацией натурального числа называется его разложение в произведение  простых множителей. Умножение двух больших простых чисел является не сложной задачей, при этом обратная задача – разложение на сомножители – чрезвычайно трудоемкая.

Дискретным логарифмированием называется задача обращения функции  g^{x} в некоторой конечной мультипликативной группе G. Для заданных g и a решение x уравнения g^{x}=a  по заданному модулю pназывается дискретным логарифмом элемента a по основанию g. Криптостойкость схем ЭЦП на основе задачи дискретного логарифмирования базируется на высокой вычислительной сложности обращения показательной функции [5]. Пусть наибольший общий делитель (НОД) чисел a и n равен единице. Наименьшее из чисел gamma, для которого выполняется сравнение a^{r}equiv 1modn, называется показателем, которому число a принадлежит по модулю n. Числа, принадлежащие показателю varphi (n), где  varphi (n)– функция Эйлера, называются первообразными корнями по модулю n [5].

Рассмотрим некоторые атаки на ЭЦП, основанные на алгоритмах дискретного логарифмирования.

Под слабыми системами ЭЦП будем понимать те из них, которые допускают подделку подписи. Последнее означает формирование подписи к некоторому заданному сообщению без знания секретного ключа. Многие системы ЭЦП, рассматриваемые как стойкие, допускают возможность формирования без знания секретного ключа случайных значений h и (r,S), которые удовлетворяют уравнению проверки подписи. Рассмотрим пример: пусть уравнение подписи имеет вид: r=y^{k}a^{rS}modp.  Осуществим подделку подписи без знания секретного ключа. Имеется некоторый документ, значение хеш-функции от которого равно h. Далее действуем по следующему алгоритму [4].

1. Выбираем некоторое значение z.

2. Вычисляем r=a^{S}y^{h}modp.

3. Если НОД (r, p-1)>1, то повторяем шаги 1 и 2, пока не выполнится условие НОД(r, p-1)=1.

4. Вычисляем   S=z/rmod(p-1),  т.е. получаем z=Srmod(p-1).

5. Предъявляем в качестве подписи к хеш-функции h пару чисел (r, S).

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

Применение в схемах ЭЦП, подобных системе Эль-Гамаля, составного модуля вместо простого связано с тем, что большое число таких схем не обеспечивает стойкости к атакам, основанным на вычислении подписи путем подбора параметра  r  в виде:                                                                                                                                    

r=alpha ^{t}y^{u}mod p                                                                                              (1)

При создании ЭЦП параметр k  должен быть одноразовым, поскольку при формировании подписей  r и  S к двум различным сообщениям возникают предпосылки для вычисления varphi (n) и секретного ключа x. При наличии двух подписей имеется следующая система из двух уравнений с неизвестными x и varphi (n), которую злоумышленник может решить:

                   h(m)=xrmodvarphi (n)                                                                             (2)

              h(m)=xSmodvarphi (n)                                                                            (3)

Параметр r задает в уравнении генерации подписи неизвестную k, которая изменяется с каждой процедурой генерации подписи. Это предотвращает атаки, связанные с попыткой вычисления секретного ключа из уравнения формирования подписи [4].

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

Постановка задачи. Для повышения криптостойкости схем ЭЦП на основе задачи дискретного логарифмирования в данной работе авторы предлагают в качестве дополнительных параметров  использовать  рандомизатор k, генерируемый по алгоритму  Нидхема-Шредера [6] и параметр H', представляющий собой хеш-значение от общего секретного ключа пользователей K, сформированного по алгоритму Диффи-Хеллмана [2] и параметров ЭЦП  r и S.

Основной материал исследования. Широкое практическое применение получили схемы ЭЦП Эль-Гамаля с простым модулем p, которые, по мнению многих специалистов, не обеспечивают в некоторых случаях необходимой криптостойкости. Поэтому целесообразно использовать схемы ЭЦП Эль-Гамаля с составным модулем [4].

Ряд возможных схем реализации электронной цифровой подписи с составным модулем, однаразовым сеансовым ключом k и дополнительным параметром  H' представлен в таблице 1.

Таблица 1  –  Варианты ЭЦП с составным модулем и дополнительным параметром .

Безымянный3

Где  n– составной модуль, представляющий собой произведение больших простых чисел p и q ; H – хеш-значение документа;  x– секретный ключ;  y – открытый ключ;   q' – сгенерированное большое простое число размером 160-256 бит, являющееся делителем больших простых чисел p-1 и q-1;  alpha – наименьшее число, такое, что alpha^{q'}modn=1 ; параметр ЭЦП  r вычисляется по формуле: r=alpha ^{k}modn  [4]; K – общий секретный ключ, сформированный по алгоритму Диффи-Хеллмана;  H' - хеш-значение конкатенации чисел K ,  r и S ; совокупность чисел (r,S,H') представляет собой ЭЦП документа. Рассмотрим подробно алгоритм формирования и проверки ЭЦП на примере схемы 1, представленной в таблице 1.

Владелец секретного ключа выбирает два больших простых числа p и q,  перемножает их, получая модуль:

n=pq                                                                                                        (4)

Значения простых множителей p и q держатся в секрете или уничтожаются после вычисления функции Эйлера:

varphi (n)=(p-q)(q-1)  .                                                                                 (5)

Абонент А выбирает в качестве секретного ключа x, принадлежащее множеству xin (1,...,q'-1).  Для обеспечения невозможности вычисления секретного ключа  x на основе известной подписи используется открытый ключ y:

    y=alpha ^{x}mod n  .                                                                                             (6)

Открытой информацией абонента А являются числа (y,n,alpha ).

Длина числа  alpha  может быть выбрана сравнительно небольшой (меньше размера используемых значений p и q, такое, что:

alpha ^{q^{'}}mod n=1                                                                                               (7)

Для потенциального нарушителя в уравнении генерации подписи присутствуют две неизвестные величины: x  и k. Поэтому он не имеет возможности с большой вероятностью вычислить секретный ключ x. В качестве случайного значения k  при вычислении параметра  r  использовать значения сеансовых ключей генерируемых по алгоритму Нидхема-Шредера.

Для каждого сеанса связи, согласно алгоритму Нидхема-Шредера [6], абоненты А и В вычисляют значение сеансового ключа по следующей схеме. Пусть в течение некоторого времени абоненты А и В договорились об m-сеансах связи; А и В генерируют m-сеансовых ключей последовательно хешируя m-раз общую для них произвольную информацию (М) h1=H(M), h2=H(h1),…, hm-1=H(hm-2), hm=H(hm-1), а в качестве сеансовых ключей при передачи сообщений будут применять эти вычисленные значения в обратном порядке. В схемах ЭЦП на основе задачи факторизации авторы предлагают в качестве рандомизатора  k  использовать текущее значение сеансового ключа вычисленное по алгоритму Нидхема-Шредера, что позволит осуществить дополнительную проверку подлинности абонентов А и В.

По уравнению формирования подписи из схемы 1 абонентом  А  вычисляется параметр r:

r=alpha ^{k}modn                                                                                               (8)

Для повышения криптостойкости схемы электронной цифровой подписи с составным модулем применим также алгоритм Диффи-Хеллмана.

Общий секретный ключ  K для абонентов A и B формируется следующим образом. Абонентам известны некоторые два числа  g и p', которые не являются секретными и могут быть известны также другим заинтересованным лицам ( p'  является случайным простым числом, g –  первообразный корень по модулю p'). Для того чтобы создать, неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа:  абонент A – число a, абонент B – число b. Затем абонент A вычисляет значение:

A'=g^{a}modp'                                                                                             (9)

и пересылает его абоненту B , который вычисляет:

                                               B'=g^{b}modp'                                                                                           (10)

и передаёт абоненту A. На втором этапе первый абонент на основе имеющегося у него  a и полученного по сети  B' вычисляет значение:

B'^{a}modp'=g^{ab}modp' ,                                                                               (11)

а второй абонент на основе имеющегося у него числа b  и полученного числа  H'  вычисляет значение:

A'^{b}modp'=g^{ab}modp'                                                                               (12)

Таким образом, абоненты A и B сформировывают общий секретный ключ K по формуле:

K=g^{ab}modp'.                                                                                         (13)

Злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления (11) или (12) по перехваченным g^{a}modp'  и g^{b}modp', если числа p' , a и b выбраны достаточно большими [2]. В практических реализациях, для и  используются числа порядка 10100 и   порядка 10300.

По уравнению формирования подписи из схемы 1 (см. таблица 1) вычисляется S:

                                     kH=xr+Smodq'                                                                                  (14)

К общему секретному ключу K  добавляются значения параметров ЭЦП r и  S и эта совокупность чисел хешируется. Полученное хеш-значение  H' является дополнительным параметром электронной цифровой подписи, использование которого, по мнению авторов, повышает криптостойкость схемы ЭЦП Эль-Гамаля с составным модулем. Подписью под электронным документом в этом случае есть совокупность значений (r,S,H').

Процедура проверки подлинности электронного документа, подписанного с помощью электронной цифровой подписи с составным модулем и дополнительным параметром H', происходит следующим образом. У получателя есть переданный электронный документ с ЭЦП (r,S,H'). Абоненту B известно значение  открытого ключа y, число  alpha и составной модуль n, а также сформированный общий секретный ключ K.

Уравнение  проверки ЭЦП, по схеме 1 (см. таблица 1) имеет вид:

            r^{H}=y^{r}alpha ^{S}modn                                                                                    (15)

Вычисляются по отдельности левая  lch и правая  pch части уравнения:

                                       lch=r^{H}  ,                                                                                           (16)

                                                pch=y^{r}alpha ^{S}mod n .                                                                                 (17)

Получатель электронного документа осуществляет конкатенацию сформированного ранее общего секретного ключа  K и параметров r  и S:

                   M=Kleft | r right |S                                                                                        (18)

и вычисляет хеш-значение H_{1}:

H_{1}=h(M)  .                                                                                       (19)

Если обе части уравнения проверки равны и H'=H_{1} (т.е. абонент В может быть уверен в том¸ что абонент А знает общий секретный ключ K), то электронная цифровая подпись соответствует документу и его можно считать подлинным. Если же результаты отличаются, то подпись поддельная. В качестве дополнительной проверки  подписи абонента А абонент В вычисляет значение параметра r  по формуле r=alpha ^{k}modp, используя в качестве k текущее значение сеансового ключа вычисленного по алгоритму Нидхема-Шредера.

Рассмотрим также алгоритмы ЭЦП на основе задачи дискретного логарифмирования с простым модулем p и с использованием одноразового сеансового ключа k, формируемого по алгоритму Нидхема-Шредера и дополнительного параметра H', вычисленного с помощью алгоритма Диффи-Хеллмана. Выбирается большое простое число p и соответствующий ему первообразный корень a<p. Для обеспечения стойкости системы ЭЦП на число p накладывается следующее условия: разложение числа  p-1 на множители должно содержать, по крайней мере, один большой простой множитель; размер числа p должен быть не менее 1024 бит. Каждый абонент выбирает свой секретный ключ x и вычисляет соответствующий ему открытый ключ y по формуле y=alpha ^{x}modp . Согласно алгоритму Нидхема-Шредера [6], приведенного ранее, для каждого сеанса связи абоненты А и В вычисляют значение сеансового ключа k. В схемах ЭЦП на основе задачи дискретного логарифмирования авторы предлагают в качестве рандомизатора k использовать текущее значение сеансового ключа, вычисленное по алгоритму Нидхема-Шредера, что позволит осуществить дополнительную проверку подлинности абонентов А и В.

На языке Java были реализованы следующие алгоритмы  ЭЦП на основе задачи дискретного логарифмирования с  использованием сеансовых ключей Нидхема-Шредера, представленные уравнениями проверки подлинности ЭЦП и уравнениями формирования ЭЦП [4]:

a^{h}=y^{S}r^{r}modp ,  и   S=frac{(h-kr)}{x}mod(p-1)                                              (20)

a^{h}=y^{r}r^{S}modp,  и   S=frac{(h-kr)}{k}mod(p-1)                                                (21)

a^{S}=y^{r}r^{h}modp,   и    S=xr+khmod(p-1)                                                (22)

a^{r}=y^{h}r^{S}modp,  и    S=frac{(r-xh)}{k}mod(p-1)                                              (23)

a^{r}=y^{S}r^{h}modp ,  и    S=frac{(r-kh)}{x}mod(p-1)                                             (24)

Пример реализации  схемы №1 на языке Java с использованием в качестве рандомизатора k сеансового ключа, сгенерированного по алгоритму Нидхема-Шредера и дополнительного параметра H' , сформированного на основе алгоритма Диффи-Хеллмана, представлен ниже.

Язык Java обладает такими достоинствами как многозадачность, поддержка протоколов Internet и многоплатформенность [3]. Среда программирования IDE NetBeans 7.0.1. представляет собой модульную интегрированную среду разработки (IDE), написанную на языке программирования Java. Она позволяет выполнять целочисленные операции с большой разрядностью. При реализации алгоритмов ЭЦП использовался класс BigInteger, хранящийся в библиотеке Java.math и представленные ниже методы этого класса:

add(x) – операция this  “+” x;

mod(x) – остаток от деления объекта this  на аргумент метода х;

modInverse(x) – остаток от деления числа, обратного объекту this , на аргумент x;

modPow(n,m) – остаток от деления объекта this , возведенного в степень n, на m;

multiply(x) – операция this “*” x;

subtract(x) – операция this “–“ x.

В процессе реализации на языке Java алгоритмов ЭЦП на основе задачи дискретного логарифмирования  с использованием формирования сеансовых ключей Нидхема-Шредера и дополнительного параметра H', были получены следующие результаты, на примере схемы ЭЦП описанной уравнением (1).

На подготовительном этапе абонент А генерирует большое простое число p размером 1024 бита:

p=1056924599668519511464493397803051926487935381821830624572348806583057872899888773409

8146395794291438050841854039640291876914463401412001174341566439778198655947145286933721

8637878256288080166288599141651606989971526435025637999249940041785274102681429554926643

1164414842391232732053071933003197860721675865149,

затем абонент А выбирает секретный ключ х, любое число 1<x<p-1:

x=2400537499864367983523897470372225622601907603849916976966298905791513713835366147386

9573170538532327600403843958900841318851912128308867411915056005844745278649518239323031

274216200463565706732552141447586999086459200588203682955054908688229735901893426099235

6484369784872932901509954849922748961514012930103.

Затем абонент  А  генерирует случайное число a<p:

a=142469148381591990339368847004582545476112354026774637028453605828840636928329225980658

59092748240123330440828111776856363929171394214399931361357226424887442286025497821037982

7288583799116166162703788090975118103574065542610754788091035162085103472517001485799025

221407613491234111257539200935957568903160301

Далее абонент А вычисляет  открытый ключ y по формуле y=axmod p:

y=87460337512132546400137787506384914295697326949174692362290611676037390598611889578128

2940129467178165010826714930101875573917876287958840939031495976095759582062839173314488

96155030943363272041560532601935366522494171190274091703345348160861811388906715517796600

3094078539462106838370484889129266395040987902.

Абонент А выбирает очередной сеансовый ключ, сформированный по алгоритму Нидхема-Шредера:

k=44935448813565677364042021872156867202486359

и вычисляет параметр ЭЦП r по формуле :

r=142469148381591990339368847004582545476112354026774637028453605828840636928329225980658

59092748240123330440828111776856363929171394214399931361357226424887442286025497821037982

7288583799116166162703788090975118103574065542610754788091035162085103472517001485799025

221407613491234111257539200935957568903160301.

Сформированный ранее по алгоритму Диффи-Хеллмана абонентами А и В общий секретный ключ имеет вид:

K=22215858046529138111949802472177706837106896625663263470867113862818175878 6814.

Исходное сообщение M (message) хешируется, т.е. подвергается обработки с помощью хеш-функции.  Получаем хеш-значение документа h:

h=7152392942269110646151437128549323330051380.

Затем по формуле S=frac{(h-kr)}{x}mod(p-1) непосредственно вычисляем параметр S, электронной цифровой подписью данного документа является совокупность чисел (r,S,H'),  где  H' - вычисляется с помощью конкатенации сформированного ранее общего секретного ключа K и параметров r и S.

S=832773583011115863647738049783314911048695259139848801880653430882052368545554760520904

936665205192061563441458059691091912561688725515515883076645509501596441443499286349187968

92872948421334448301898027131067040666725195521987571118959030180272973429296329241261240

2705839309817933994116831111519916859338755.

Для проверки ЭЦП программное обеспечение абонента B вычисляет по отдельности левую и правую части следующего уравнения:

alpha ^{h}=y^{S}r^{r}modp ,

 а также проверяет значение параметра r по формуле r=alpha ^{k}modp, используя в качестве k  очередной сеансовый ключ, сгенерированный по алгоритму Нидхема-Шредера.

Правая часть уравнения проверки=565556054676172643468909464122986633660765080017223711332399

8756257001887262879402398176289466344019098222266909074107129179774045645317495272246898

51706016446459492835553178611232444353620401791134688980008242633304431000729644309465461

328660857466099563830998582457020289637009756757858003022017382368618349.

Левая часть уравнения проверки=5655560546761726434689094641229866336607650800172237113323998

7562570018872628794023981762894663440190982222669090741071291797740456453174952722468985

17060164464594928355531786112324443536204017911346889800082426333044310007296443094654613

28660857466099563830998582457020289637009756757858003022017382368618349.

Переданное хеш-значение H'=7482654798263654681273459847382177432.

Вычисленное абонентом  В хеш-значение H_{1}=7482654798263654681273459847382177432.

Если после конкатенации Kleft | r right |S обе части уравнения проверки равны и H'=H_{1}, то электронная цифровая подпись соответствует документу и его можно считать подлинным. Абонент В вычисляет значение параметра r  по формуле r=alpha ^{k}modp, используя в качестве k текущее значение сеансового ключа, вычисленного по алгоритму Нидхема-Шредера.

ВЫВОДЫ

Реализованные на языке объектно-ориентированного программирования Java в среде NetBeans IDE 7.0.1 алгоритмы ЭЦП на основе задачи дискретного логарифмирования, с использованием одноразового сеансового ключа k, сформированного по алгоритму Нидхема-Шредера и дополнительного параметра H', с помощью алгоритма Диффи-Хеллмана, прошли тестирование на правильность результатов формирования и проверки электронной цифровой подписи. Применение составного модуля и дополнительных параметров  k  и   H'  позволяет построить более криптостойкие схемы ЭЦП по сравнению со случаем применения простого модуля, что ускоряет процесс создания и проверки ЭЦП.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

  1. Молдовян Н.А. Криптография: от примитивов к синтезу алгоритмов. / Н.А.Молдовян,   А.А.Молдовян, М.А.Еремеев. – СПб.: БХВ – Петербург, 2004. – 448 с.
  2. Молдовян Н.А. Криптография с открытым ключом. / Н.А.Молдовян, А.А.Молдовян, М.А.Еремеев. – СПб.: БХВ – Петербург, 2004. – 288 с.
  3. Введение в криптографию/ Под общ. Ред. В.В. Ященко.-М.:МЦНОМ: «ЧеРо», 2000. -287 с.
  4. Венбо  Мао.    Современная   криптография: теория  и практика. / – М.: Издательский дом Вильямс, 2005. – 297 с.
  5. Джон  Родли  Создание  Java-апплетов. –  The Coriolis Group, Inc., 1996, Издательство НИПФ “ДиаСофт Лтд.”, 1996.


Все статьи автора «Yulia_T»


© Если вы обнаружили нарушение авторских или смежных прав, пожалуйста, незамедлительно сообщите нам об этом по электронной почте или через форму обратной связи.

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

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

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: