Программные продукты и системы

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

Рис. 1. Заверение документа коллективом субъектов с использованием обычной схемы ЭЦП

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

Рис. 2. Заверение документа коллективом субъектов с использованием коллективной подписи

Развитием схемы коллективной подписи является так называемая композиционная подпись. Основным отличием композиционной подписи от коллективной является возможность подписи каждым пользователем отдельного документа одновременно с постановкой коллективной подписи. Композиционная подпись подтверждает то, что некоторая заданная совокупность документов подписана произвольно заданной совокупностью пользователей. При этом размер композиционной подписи остается фиксированным для произвольного числа подписанных документов и субъектов. Заметим, что некоторые из документов могут быть равными, могут реализовываться случаи, когда подмножество субъектов подписывает один и тот же документ (рис. 3).

Рис. 3. Заверение документа коллективом субъектов с использованием композиционной подписи

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

1. Открытые ключи упорядочиваются по возрастанию значения модуля. Пусть имеем n1

2. Последовательно формируются подписи S1=H1d1mod n1,S2=(S1H2)d2mod n2,…,Sm=(Sm-1Hm)dmmod nm. Значение Sm и является композиционной подписью.

Проверка композиционной подписи выполняется следующим образом: Sm-1=(Smem)Hm-1mod nm, Sm-2=(Sm-1em-1)Hm-1-1mod nm-1,…,S1=(S2 e2)H2-1mod n2, H¢=S1 e1mod n1. Если H¢=FH(M1)=H1, то это означает, что каждый субъект подписал соответствующий документ. Очевидно, что хранить хэш-функции от документов не нужно, так как их всегда можно вычислить при наличии полного комплекта документов. Таким образом, подписи всех пользователей к различным документам хранятся в одной композиционной подписи, размер которой равен значению |nm|»1024 бит - длине максимального модуля.

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

Исходя из этого, рекомендуется использовать алгоритмы композиционной ЭЦП, основанные на двух типах трудных вычислительных задач и использующие понятие коллективного открытого ключа: на дискретном логарифмировании в конечной мультипликативной группе [1] и дискретном логарифмировании на эллиптической кривой (ЭК) [2].

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

1. Каждый субъект, участвующий в протоколе, генерирует рандомизирующий множитель Ri= =gtimod p, где ti – случайное число, выбираемое i-м субъектом, i=1,2,…,m; g – генератор циклической подгруппы порядка q; p – большое простое число.

2. Вычисляется общий рандомизирующий множитель R=R1R2R3…Rmmod p.

3. Вычисляется элемент композиционной подписи e как значение некоторой сжимающей функции от R, например, e=f(R)=Rmod q.

4. Каждый субъект вычисляет свою долю в композиционной подписи: si=ti-ehikimod q, где ki – секретный ключ i-го субъекта, связанный с его открытым ключом yi соотношением yi=gkimod p.

5. Вычисляется второй элемент s общей подписи как сумма долей всех субъектов: s=s1+s2+… +smmod q.

Проверка подлинности композиционной ЭЦП осуществляется следующим образом.

1. Вычисляется композиционный открытый ключ по формуле: y=y1h1y2h2y3h3…yihi…ymhmmod p, где hi – хэш-функция от документа, подписываемого i-м субъектом.

2. Вычисляются значения R=yegsmod p и e¢=f(R). Если e¢=e, композиционная подпись верна.

Корректность процедуры проверки доказывается подстановкой значений  и  в уравнение проверки:  .

Действия каждого i-го пользователя могут быть проверены остальными участниками композиционной подписи по значениям hi, Ri и si, которые должны удовлетворять соотношению Ri=yiehigsimod p, проверяемому по его открытому ключу yi. Эта возможность предполагает, что весь комплект подписываемых документов направляется каждому участнику рассматриваемого протокола. Итоговая композиционная подпись обладает внутренней целостностью и не может быть урезана, расширена или модифицирована иным образом.

По аналогии с последним протоколом можно легко реализовать композиционную подпись с использованием ЭК. В этом случае R является точкой ЭК, вычисляемой по формуле R=R1+R2+… +Rm, где Ri=tiG и G – точка ЭК, значение порядка которой равно достаточно большому числу q. Элемент подписи e вычисляется по формуле e=xRmod q, где xR – абсцисса точки R. Композиционный открытый ключ формируется по формуле P=h1P1+h2P2+…+hmPm, где Pi – точка ЭК, являющаяся открытым ключом i-го субъекта, Pi=kiG, а доля подписи si – по формуле si=ti-ehikimod q. При проверке подписи (e,s) вычисляются точка R¢=eP+sG, затем значение e¢=xR¢mod q, которое сравнивается с e.

Пример реализации протокола композиционной подписи

Пусть три пользователя хотят подписать ЭД со значением хэш-функции Н, который состоит из двух частей со значениями хэш-функций H1 и H2 (подписью является пара чисел e и s). При этом первый пользователь подписывает первую часть документа, второй пользователь – вторую, а третий подписывает весь документ целиком. Возможность реализации коллективной ЭЦП с такими свойствами обеспечивается за счет того, что при проверке ЭЦП используется коллективный открытый ключ, формируемый в зависимости от открытых ключей пользователей по формуле P=H1P1+H2P2+HP3. При этом с учетом последнего модифицируется процедура генерации ЭЦП. В данном примере используется ЭК с параметрами, обеспечивающими достаточную стойкость для применения при решении реальных практических задач аутентификации информации, определяемая следующими параметрами:

a=5521767865737634555390416300599776622347333359784,

b=9717196 и

p=5521767865737634555390416300599776622347333359787.

Данная ЭК содержит количество точек, равное простому числу

N=5521767865737634555390416228783886913339823841723,

то есть любая ее точка является генератором ЭК и имеет порядок q=N. При формировании и проверке подлинности ЭЦП выполняют следующую последовательность действий.

1. Генерируют ЭК с параметрами, указанными выше.

2. Формируют секретные ключи в виде случайных чисел: k1=8182108890892890101467333434019;

   k2=3952504539403758278808581024791;

   k3=9763160941600092631935520658071.

3. Формируют открытые ключи в виде точек ЭК P1, P2, P3 по формуле Pi=kiG.

3.1. Генерируют точку G:

G=(4058138998817699569976678358233335958495037969465,

768568926336036825718495218916308682494116144160);

3.2. Генерируют точки P1, P2, P3 по формуле Pi=kiG, где i=1,2,3:

P1=(2406767665928158899446906165821747218883574602371, 562377648521692290689031507205008060205345636991);

P2 = (348708108378027085357389414044825237922683510732, 1402026191996080196399482770468472598076052599809)

P3 = (4307166077833519301063322533024162005091025020313, 5280296312549156028148905914215570655514986217509).

4. Принимают ЭД, представленный хэш-значением H и состоящий из двух частей с хэш-значениями H1 и H2:

H = 8925999026871145131520337612117778680659192576033;

H1 = 135708092215597910168314154751917220633712178686;

H2 = 3812498990028819155316571350634376652814331770527.

5. Формируют ЭЦП (e,s).

5.1. Пользователи генерируют случайные числа:

t1 = 2090880922625982683584460167862382379;

t2 = 5360383526856663700583896205266418341;

t3 = 7677118810723142352012317453400887449.

5.2. Пользователи вычисляют точки R1, R2 и R3 по формуле Ri=tiG, а затем их сумму R=R1+R2 +R3.

R = (2597097970263610863546069436833994580002105418569, 3304915040104400813802374282473985550015521973383).

5.3. Формируют число e по формуле e=xRmod g, где xR – абсцисса точки R и g=7118198218659321028989011: e=5079008233076932087473789.

5.4. Пользователи генерируют значения s1, s2 и s3 по формуле si=(ti-ewiki)mod q, где w1=H1, w2=H2, w3=H, q=N и i=1,2,3, и вычисляют значение s=s1+s2+s3mod q:

s=1350034913297537903802927493878220096776002980409.

6. Формируют первое проверочное число A, для чего вычисляют коллективный открытый ключ в виде точки P по формуле P=H1P1+H2P2+HP3:

P=(228426539485900338090938878090464611548638254406,

1202278174553095231135389060209649902535727110543).

Формируют точку R¢=eP+sG:

R¢= (2597097970263610863546069436833994580002105418569,

3304915040104400813802374282473985550015521973383)

и определяют A по формуле A=xR¢ Hmod g, где g=7118198218659321028989011:

A=5079008233076932087473789.

7. Сравнивают числа A и e. Сравнение показывает, что A и e совпадают, следовательно, композиционная подпись верна.

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

1. Молдовяну П.А., Молдовян Н.А., Доронин С.Е. Схемы коллективной подписи на основе задач дискретного логарифмирования. Инновационная деятельность в Вооруженных силах Российской Федерации. // Тр. Всеарм. науч.-практич. конф. – СПб: ВАС, 2007.

2. Молдовян А.А., Молдовян Н.А. Способ генерации и проверки подлинности электронной цифровой подписи, заверяющей электронный документ. // Патентная заявка РФ № 2007130982.