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

Ключевые слова: алгоритм Диффи-Хеллмана, алгоритм Нидхема-Шредера, дискретное логарифмирование, факторизация, электронная цифровая подпись

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

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

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

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

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

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

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

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

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

Дискретным логарифмированием называется задача обращения функции $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-раз общую для них произвольную информацию (М) h₁=H(M), h₂=H(h₁),…, h_m_-1=H(h_m_-2), h_m=H(h_m_-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]. В практических реализациях, для и используются числа порядка 10¹⁰⁰ и порядка 10³⁰⁰.

По уравнению формирования подписи из схемы 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=a^xmod 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'$ позволяет построить более криптостойкие схемы ЭЦП по сравнению со случаем применения простого модуля, что ускоряет процесс создания и проверки ЭЦП.

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

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

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

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

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

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

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

Авторам

О журнале

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

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