Фрагмент для ознакомления
2
Введение
На сегодняшний день, в век информатизации и компьютеризации практически всех сфер человеческой деятельности, глобальное распространение получили электронные документы, которые используются не только совместно с традиционными бумажными документами, но и зачастую вместо них. Использование систем электронного документооборота позволяет добиться огромного экономического эффекта, поскольку снижает не только затраты, связанные с печатью документов, но и время их рассмотрения, изменения, корректировок и принятия к рассмотрению.
В связи с этим одним из важнейших направлений развития информационных систем на стыке защиты информации и электронного документооборота является внедрение электронных подписей.
В данной работе предметом исследования является электронно-цифровая подпись, как средство защиты электронного документа (сообщения).
Во многих ситуациях сообщение отправляется от имени компании и является правомерным только в случае одобрения или согласия со стороны нескольких людей. В таком случае требуется получение подписи более одного соглашающегося. Распространенным примером такой политики является крупная банковская операция, требующая подписи более чем одного человека. Такая политика может быть осуществлена, если каждый, чья подпись требуется, будет иметь отдельную электронную подпись, однако при таком подходе усилия, требующиеся для проверки подлинности сообщения, линейно увеличиваются с увеличением числа подписей. Решением проблемы является пороговая подпись. Для решения таких проблем используется пороговая схема электронной подписи (t, n). Понятие пороговой подписи тесно связано с концепцией пороговой криптографии, которую впервые продемонстрировал Десмедт (Desmedt) [21, 22, 23]. В 1991 году Десмедт (Desmedt) и Франкель (Frankel) [22] впервые предложили пороговую схему электронной подписи (t, n), основанную на предположении RSA.
В данной работе мы рассмотрим направленную пороговую схему электронной подписи (t, n), основанную на пороговой схеме электронной подписи Шамира (Shamir) [98] и схеме электронной подписи Шнорра (Schnorr) [94].
В большинстве ситуаций подписывающий и проверяющий подлинность подписи – одно и то же лицо. Тем не менее, когда сообщение передается из одной организации в другую, сообщение будет правомерным только в случае одобрения или согласия со стороны нескольких людей. В этом случае генерация подписи и ее проверка будут проводиться не одним, а несколькими лицами. Целью работы является анализ пороговой схемы электронной подписи с пороговой проверкой подлинности.
Задачами работы является проведение анализа пороговой схемы ЭЦП, анализ ее безопасности.
Глава 1. Направленная пороговая схема электронной подписи
Направленная пороговая схема электронной подписи
Пусть G – множество из n определенных пользователей, из которых любые t и более членов могут генерировать подпись на сообщение m для пользователя B. Пользователь B в случае необходимости может проверить подлинность, а также подтвердить подлинность любой третьей стороне C. Без помощи пользователя B проверка подлинности подписи невозможна.
Для наших построений предположим, что существует доверенный центр распределения долей (SDC), который определяет секретные параметры группы и секретные доли v_i,iϵG. Пусть H – любое подмножество множества G, состоящее из t членов. Предположим также наличие определенного комбинатора DC, собирающего частичные подписи от каждого пользователя в подмножестве H. Каждый владелец доли в группе имеет равные права в отношении секрета группы. Для генерации направленной подписи необходимо t из n владельцев долей и взаимодействие с DC.
Эта схема содержит следующие шаги.
1.1 Генерация группового секретного ключа и секретных долей
(a) SDC выбирает открытые параметры p, q, g группы и стойкую к коллизиям, необратимую хэш-функцию h. SDC также выбирает многочлен
f(x)=a_0+ a_1 x+⋯a_(t-1) x^(t-1) modq приa_0=x_G=f(0).
Здесь x_G- это секретный ключ группы G.
(b) SDC рассчитывает открытый ключ группыy_G следующим образом: y_G=g^f(0)modp.
(c) SDC рассчитывает секретные доли v_i для каждого члена группы G как
v_i=f(u_i )modq,
здесь u_i - открытое значение, ассоциируемое с каждым пользователем i в группе G.
(d) SDC тайно рассылаетv_i каждому пользователю.
1.2 Генерация подписи любыми t пользователями
Если любые t из n членов группы хотят подписать сообщение m для пользователя B, они должны проделать следующие шаги:
(a) Каждый член группы i случайным образом выбирает K_(i_1 )иK_(i_2 ) ϵ Zq и рассчитывает
w_i=g^(K_(i_2 )-K_(i_1 ) ) mod p и z_i=y_B^(K_(i_2 ) ) mod p.
(b) Каждый член открыто предоставляет w_iи тайно - z_i, каждому члену группы H. Когда всеw_i иz_iдоступны, каждый рассчитывает Z, W и R следующим образом:
W= ∏_iϵH▒〖w_i modq,〗 Z= ∏_iϵH▒〖z_i modq〗 иR=h(Z,W,m)modq.
(c) Каждый член i изменяет свою долю следующим образом:MS_i= v_i ∏_(j=1,j≠i)^t▒〖(-u_j)/(u_i-u_j ) modq〗.
(d) Каждый член группы i использует свою измененную долю,MS_i и случайное целое число K_(i_1 ) для вычисления своей частичной подписиs_i по формуле:
s_i=K_(i_1 )-MS_i.R mod q.
(e) Каждый член i отправляет свою частичную подпись доверенному комбинатору DC, который собирает частичные подписи и вычисляет групповую подпись
S=∑_(i=1,)^t▒〖s_i modq〗.
(f) DC отправляет B подпись {S,W,R,m}группы G на сообщении m.
1.3 Проверка подписи пользователем B
(a) B рассчитываетμ=[g^S (y_G )^R W]modp и Z= μ^(x_B ) modp.
(b) B устанавливает достоверность подписи, проверяя равенство R=h(Z,W,m)modq.
1.4 Доказательство достоверности подписи пользователем B любой третьей стороне C.
1.2. История создания ЭЦП
В 1976 году Уитфилд Диффи, Мартин Хеллманом и Ральф Меркле первыми предложили «одностороннюю функцию-ловушку» — теорию, которая позволяла передать зашифрованное сообщение без передачи ключа для разгадывания послания.
Если совсем просто, их метод заключается в том, что сделать определенное математическое действие легко только в одну сторону и очень трудно в обратную. Например, если пять умножить на десять получится пятьдесят. Чтобы пятьдесят разложить на произведение пяти и десяти нужно несравнимо больше времени. Это как если вам дадут разобранные механические часы, обратно вы их едва ли соберете.
Допустим вы открыто договорились об общем ключе и обменялись секретными данными, измененными определенным образом. Таким образом, у вас на руках окажутся: открытый ключ, свои секретные данные и зашифрованное послание. У злоумышленников может оказаться ключ и оба зашифрованных послания. Но зашифрованное послание вы можете расшифровать только при помощи своей не зашифрованной информации.
Уитфилд Диффи, Мартин Хеллманом и Ральф Меркле начали новую волну в шифровании, но в наше время их система уже не используется, а срок действия их патента под номером U.S. Patent 4 200 770 истек.
У придуманного ими способа обнаружились недостатки. Во-первых, требуется некоторое время, чтобы обменяться сообщениями, во-вторых, что наиболее серьезно, если у вас много контактов, необходимо хранить множество ключей. Предположим, что Алиса — это банк, в таком случае таких как Боб у нее тысячи. С каждым необходимо договориться о секретном ключе.
Следующей вехой в шифровании стал алгоритм RSA — Рональда Ривеста, Ади Шамира и Леонарда Адлемана. Придуманный в 1977 году
Фрагмент для ознакомления
3
Blakley G.R. (1979). Safeguarding cryptographic keys, Proceeding, AFIPS 1979 Nat. Computer conference - 48, p.p. 313-317.
Desmedt Y. (1988). Society and group oriented cryptography, Advances in Cryptology – Crypto - 87, Springer Verlag, p.p. 120 - 127.
Desmedt Y. (1994). Threshold cryptography, European Transactions on Telecommunications and Related Technologies - 5(4), p.p.35 – 43.
Desmedt, Y. and Frankel Y. (1990). Threshold cryptosystems, Advances in Cryptology –Crypto - 89, Springer Verlag, LNCS # 293, p.p. 307-315.
Desmedt, Y. and Frankel Y. (1991). Shared generation of authenticators and signatures, Advances in Cryptology –Crypto - 91, Springer Verlag, p.p. 457-469.
ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Transactions on Information Theory. 1985, Vol. IT-31, No. 4. pp.469 – 472.
Menezes A. J., Vanstone S.A. Handbook of Applied Cryptography. CRC Press, 1996. – 780 p.
Rivest R.L., Shamir A., and Adleman L.M. A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM, 1978, vol. 21, n. 2, pp. 120-126.
Shamir A. (1979). How to share a secret, Communications of the association for computing machinery – 22, p.p. 612 - 613.
Гортинская Л. В., Молдовян Д. Н. Основанная на сложности факторизации схема ЭЦП с простым модулем // Вопросы защиты информации. 2005. № 4 (71). С. 7-11.
Костин А. А., Молдовян Д. Н., Молдовян Н. А. Новая криптосистема с открытым ключом на основе RSA-модуля // Вопросы защиты информации. 2005 (68). № 1. С. 8-12.
Молдовян Д. Н. Схемы цифровой подписи на основе сложности факторизации модуля // Вопросы защиты информации. 2004. № 4 (67). С. 6-11.
Молдовян Д.Н. Схема ЭЦП с проверкой подлинности по длине // В кн. Инновационная деятельность в вооруженных силах Российской Федерации. Труды всеармейской научно-практической конференции. СПб, 17-18 ноября 2005 г. СПб, 2005. С. 196-199.
