Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя
Запропоновано білінійні схеми підпису з відкритим індивідуальним ключем користувача, які є аналогами алгоритмів, визначених в українському (ДСТУ 4145-2002), німецькому (EC-GDSA) та корейському (EC-KCDSA) стандартах, а також на їх базі проводиться побудова порогових схем. Такі схеми можуть бути альте...
Gespeichert in:
| Datum: | 2012 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/84116 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя / А.А. Кулага // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 155-162. — Бібліогр.: 23 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84116 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841162015-07-04T03:01:38Z Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя Кулага, А.А. Программно-технические комплексы Запропоновано білінійні схеми підпису з відкритим індивідуальним ключем користувача, які є аналогами алгоритмів, визначених в українському (ДСТУ 4145-2002), німецькому (EC-GDSA) та корейському (EC-KCDSA) стандартах, а також на їх базі проводиться побудова порогових схем. Такі схеми можуть бути альтернативою схемам з інфраструктурою відкритого ключа, яка базується на сертифікатах, особливо якщо потрібне ефективне управління ключами при помірному рівні безпеки. This paper proposes bilinear schemes of identity-based digital signature being an analog to the algorithms defined by the Ukrainian (4145-2002), German (EC-GDSA), and Korean (EC-KCDSA) State Standards as well as threshold schemes based on such bilinear schemes. Such protocols offer an alternative to those with public key infrastructure based on certificates, especially if effective key management is required at rather moderate security level. 2012 Article Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя / А.А. Кулага // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 155-162. — Бібліогр.: 23 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84116 004.056.2 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Программно-технические комплексы Программно-технические комплексы |
| spellingShingle |
Программно-технические комплексы Программно-технические комплексы Кулага, А.А. Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя Кибернетика и системный анализ |
| description |
Запропоновано білінійні схеми підпису з відкритим індивідуальним ключем користувача, які є аналогами алгоритмів, визначених в українському (ДСТУ 4145-2002), німецькому (EC-GDSA) та корейському (EC-KCDSA) стандартах, а також на їх базі проводиться побудова порогових схем. Такі схеми можуть бути альтернативою схемам з інфраструктурою відкритого ключа, яка базується на сертифікатах, особливо якщо потрібне ефективне управління ключами при помірному рівні безпеки. |
| format |
Article |
| author |
Кулага, А.А. |
| author_facet |
Кулага, А.А. |
| author_sort |
Кулага, А.А. |
| title |
Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя |
| title_short |
Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя |
| title_full |
Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя |
| title_fullStr |
Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя |
| title_full_unstemmed |
Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя |
| title_sort |
построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Программно-технические комплексы |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84116 |
| citation_txt |
Построение билинейных цифровых подписей с открытым ключом на основе личностных данных пользователя / А.А. Кулага // Кибернетика и системный анализ. — 2012. — Т. 48, № 3. — С. 155-162. — Бібліогр.: 23 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT kulagaaa postroeniebilinejnyhcifrovyhpodpisejsotkrytymklûčomnaosnoveličnostnyhdannyhpolʹzovatelâ |
| first_indexed |
2025-07-06T11:04:11Z |
| last_indexed |
2025-07-06T11:04:11Z |
| _version_ |
1836895281565663232 |
| fulltext |
ÓÄÊ 004.056.2
À.À. ÊÓËÀÃÀ
ÏÎÑÒÐÎÅÍÈÅ ÁÈËÈÍÅÉÍÛÕ ÖÈÔÐÎÂÛÕ ÏÎÄÏÈÑÅÉ
Ñ ÎÒÊÐÛÒÛÌ ÊËÞ×ÎÌ ÍÀ ÎÑÍÎÂÅ ËÈ×ÍÎÑÒÍÛÕ
ÄÀÍÍÛÕ ÏÎËÜÇÎÂÀÒÅËß
Êëþ÷åâûå ñëîâà: áèëèíåéíûå îòîáðàæåíèÿ, ïîäïèñü Ýëü-Ãàìàëÿ, ýëëèïòè-
÷åñêèå êðèâûå, ïîðîãîâûå ñõåìû, êðèïòîñèñòåìû ñ îòêðûòûì èíäèâèäóàëü-
íûì êëþ÷îì.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ íàó÷íûì ñîîáùåñòâîì ðàññìàòðèâàåòñÿ ðÿä ïåðñïåêòèâíûõ
íàïðàâëåíèé, ñâÿçàííûõ ñ èñïîëüçîâàíèåì êðèïòîãðàôè÷åñêèõ ïðèìèòèâîâ íà áè-
ëèíåéíûõ îòîáðàæåíèÿõ (áèëèíåéíûõ ñïàðèâàíèÿõ) òî÷åê ýëëèïòè÷åñêèõ êðèâûõ.
Ýòî ïîçâîëÿåò óïðîùàòü íåêîòîðûå êðèïòîñèñòåìû, à òàêæå ðåøàòü íåêîòîðûå
ñïåöèôè÷åñêèå çàäà÷è â êðèïòîãðàôèè, âêëþ÷àÿ ñîçäàíèå àñèììåòðè÷íûõ êðèï-
òîñèñòåì ñ îòêðûòûì èíäèâèäóàëüíûì êëþ÷îì (Identity Based Cryptosystems).
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàþòñÿ ñâîéñòâà áèëèíåéíûõ îòîáðàæåíèé, îïèñû-
âàåòñÿ ïîñòðîåíèå ñõåì öèôðîâîé ïîäïèñè ñ îòêðûòûì èíäèâèäóàëüíûì êëþ÷îì,
êîòîðûå ÿâëÿþòñÿ áèëèíåéíûìè àíàëîãàìè àëãîðèòìîâ, îïðåäåëåííûõ â óêðàèí-
ñêîì (ÄÑÒÓ 4145-2002) [1], ãåðìàíñêîì (EC-GDSA) è êîðåéñêîì (EC-KCDSA)
ñòàíäàðòàõ ôîðìèðîâàíèÿ è ïðîâåðêè öèôðîâîé ïîäïèñè, à òàêæå ïðèâîäèòñÿ ïî-
ñòðîåíèå ïîðîãîâûõ ñõåì íà áàçå ýòèõ áèëèíåéíûõ àíàëîãîâ.
ÊÐÈÏÒÎÑÈÑÒÅÌÛ Ñ ÎÒÊÐÛÒÛÌ ÈÍÄÈÂÈÄÓÀËÜÍÛÌ ÊËÞ×ÎÌ
Èäåÿ ñîçäàíèÿ ñèñòåì ñ îòêðûòûì èíäèâèäóàëüíûì êëþ÷îì ïîëüçîâàòåëÿ áûëà
ïðåäëîæåíà À. Øàìèðîì â 1984 ã. [2] êàê àëüòåðíàòèâà ñèñòåìàì ñ èíôðà-
ñòðóêòóðîé îòêðûòîãî êëþ÷à (Public Key Infrastructure — PKI), èñïîëüçóþùàÿ
ñåðòèôèêàòû. Îäíàêî ïðîáëåìà ïîñòðîåíèÿ òàêèõ àñèììåòðè÷íûõ êðèïòîñèñòåì
îñòàâàëàñü îòêðûòîé äî 2001 ã., êîãäà Ä. Áîíå è Ì. Ôðýíêëèí ïðåäñòàâèëè
ñâîþ ñõåìó øèôðîâàíèÿ [3], èñïîëüçóþùóþ ñâîéñòâà áèëèíåéíîãî ñïàðèâàíèÿ
Âåéëÿ íà ýëëèïòè÷åñêîé êðèâîé, ïîñêîëüêó íè îäíà ñõåìà, ïðåäëîæåííàÿ ðàíåå,
íå îòâå÷àëà âñåì òðåáîâàíèÿì áåçîïàñíîñòè è ýôôåêòèâíîñòè. Îíà ÿâëÿåòñÿ
ïåðâîé ïîëíîôóíêöèîíàëüíîé, ýôôåêòèâíîé è áåçîïàñíîé ñõåìîé øèôðîâàíèÿ.
Ïîñëå ðàáîòû Áîíå è Ôðýíêëèíà ïîÿâèëèñü äðóãèå àñèììåòðè÷íûå ñõåìû, ñðå-
äè êîòîðûõ ïîëó÷èëè èçâåñòíîñòü ñõåìû øèôðîâàíèÿ Ãåíðè–Ñèëüâåðáåðãà [4],
Áîíå–Áîéåíà [5] è äð., à òàêæå ñõåìû ïîäïèñè Çàíãà–Êèìà [6], Õåññå [7].
 êðèïòîñèñòåìàõ ñ îòêðûòûì èíäèâèäóàëüíûì êëþ÷îì íåò íåîáõîäèìîñòè
ïîëüçîâàòåëÿì îáìåíèâàòüñÿ ñâîèìè ñåðòèôèêàòàìè îòêðûòûõ êëþ÷åé, òàê êàê
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 155
© À.À. Êóëàãà, 2012
îòêðûòûå êëþ÷è âûâîäÿòñÿ èç ëè÷íîñòíûõ äàííûõ ïîëüçîâàòåëÿ, êîòîðûå îáùåèçâåñ-
òíû (íàïðèìåð, e-mail ïîëüçîâàòåëÿ, åãî èìÿ èëè íîìåð åãî ìîáèëüíîãî òåëåôîíà è
äð.). Ñåêðåòíûå êëþ÷è ïîëüçîâàòåëåé ñõåìû è ñèñòåìíûå ïàðàìåòðû ãåíåðèðóþòñÿ
äîâåðåííûì îðãàíîì — Öåíòðîì ãåíåðàöèè êëþ÷åé (Private Key Generator — PKG).
 òàêèõ ñèñòåìàõ âìåñòî òîãî ÷òîáû ïîääåðæèâàòü ðàáîòó PKI, íåîáõîäèìî
ïîääåðæèâàòü ðàáîòó PKG, ÷òî çíà÷èòåëüíî ïðîùå, ïîñêîëüêó íåò íåîáõîäèìî-
ñòè â îáñëóæèâàíèè, óïðàâëåíèè, ñîçäàíèè, óäàëåíèè è ðàñïðåäåëåíèè ñåðòèôè-
êàòîâ, à ýòî ïðèâîäèò ê óìåíüøåíèþ çàòðàò íà óïðàâëåíèå èíôðàñòðóêòóðîé îò-
êðûòûõ êëþ÷åé [8]. Íî äëÿ ýòîãî îáÿçàòåëüíî âûïîëíåíèå òàêèõ óñëîâèé: ïîëü-
çîâàòåëü äîëæåí áûòü ïîëíîñòüþ óâåðåí â êîððåêòíîñòè äàííûõ,
èäåíòèôèöèðóþùèõ ïîëüçîâàòåëÿ, êîòîðûå îí èñïîëüçóåò, è PKG äîëæåí ïåðå-
äàâàòü çàêðûòûå êëþ÷è òîëüêî èõ õîçÿåâàì. Íåîáõîäèìî îòìåòèòü, ÷òî îäèí èç
íåäîñòàòêîâ êëàññè÷åñêèõ êðèïòîñèñòåì ñ îòêðûòûì èíäèâèäóàëüíûì êëþ-
÷îì — âîçìîæíîñòü ñî ñòîðîíû PKG êîíòðîëÿ íàä ñåêðåòíûìè êëþ÷àìè ïîëüçî-
âàòåëåé, à îäíèì èç ñïîñîáîâ ïðåîäîëåíèÿ ýòîãî íåäîñòàòêà ÿâëÿåòñÿ èñïîëüçîâà-
íèå ïîðîãîâûõ ñõåì.  íàó÷íîé ëèòåðàòóðå îïèñàíî áîëüøîå êîëè÷åñòâî ïîðîãî-
âûõ ñõåì íà îñíîâå ðàçíûõ àëãîðèòìîâ. Òàê, íàïðèìåð, â ðàáîòàõ [9–11]
ïðåäëîæåíû ïîðîãîâûå ñõåìû öèôðîâîé ïîäïèñè (ÖÏ) íà îñíîâå ðîññèéñêèõ
ñòàíäàðòîâ ÃÎÑÒ 34.10-94 è ÃÎÑÒ 34.10-2001.
ÝËÜ-ÃÀÌÀËß–ÏÎÄÎÁÍÛÅ ÑÕÅÌÛ ÏÎÄÏÈÑÈ
Ðåøåíèå çàäà÷ ïîñòðîåíèÿ ñõåì àñèììåòðè÷íîãî øèôðîâàíèÿ è ÖÏ îñóùå-
ñòâëÿåòñÿ ñ ïîìîùüþ îäíîñòîðîííåé ôóíêöèè ñ «ëàçåéêîé», ÷òî áûëî âïåð-
âûå ïðåäëîæåíî Ýëü-Ãàìàëåì â [12], ãäå äëÿ ïîñòðîåíèÿ òàêîé ôóíêöèè îí
ïðèìåíèë èäåþ èñïîëüçîâàíèÿ äâóõ êëþ÷åé. ×òî êàñàåòñÿ êðèïòîñèñòåì íà ýë-
ëèïòè÷åñêèõ êðèâûõ, êîòîðûå ïîÿâèëèñü ïîçäíåå, òî îíè íàñëåäóþò îñíîâíûå
ïðîòîêîëû Ýëü-Ãàìàëÿ–ïîäîáíûõ ñõåì, ïîñêîëüêó èõ àëãåáðàè÷åñêèå ñòðóêòó-
ðû ïîñòðîåíû íà êîíå÷íûõ ãðóïïàõ ýëåìåíòîâ. Âñå êðèïòîàëãîðèòìû ñ àëãåá-
ðîé ïîëÿ àäàïòèðóþòñÿ â àääèòèâíîé ãðóïïå òî÷åê ýëëèïòè÷åñêîé êðèâîé
ñ îïåðàöèåé ñêàëÿðíîãî óìíîæåíèÿ òî÷êè âìåñòî ýêñïîíåíöèðîâàíèÿ
â ìóëüòèïëèêàòèâíîé ãðóïïå [13]. Òàêèì îáðàçîì, áîëüøèíñòâî àëãîðèòìîâ
ÖÏ, êîòîðûå ïîñòðîåíû íà àðèôìåòèêå ãðóïïû òî÷åê ýëëèïòè÷åñêîé êðèâîé,
îñíîâàíû íà ñõåìå Ýëü-Ãàìàëÿ [12]. Â 90-õ ãîäàõ áûë ïðèíÿò íàöèîíàëüíûé
ñòàíäàðò ÖÏ ÑØÀ, êîòîðûé ïðåäñòàâèë àëãîðèòì ÖÏ DSA êàê ìîäèôèêàöèþ
ñõåìû Ýëü-Ãàìàëÿ. Ïîñëå 1999 ã. ïîÿâèëèñü íàöèîíàëüíûå è ìåæäóíàðîäíûå
ñòàíäàðòû êðèïòîãðàôèè íà ýëëèïòè÷åñêèõ êðèâûõ. Ñóùåñòâóþùèå ñòàíäàðòû è
èõ ïðîåêòû [1, 14–16] îïèñûâàþò ðàçíûå àëãîðèòìû ñ ðàçëè÷íîé ñòîéêîñòüþ è
âû÷èñëèòåëüíîé ñëîæíîñòüþ, ÷òî ðàñøèðÿåò âîçìîæíîñòè âûáîðà ïðè ðàçðàáîò-
êå êðèïòîñèñòåì. Ðàññìîòðèì íàèáîëåå ðàñïðîñòðàíåííûå àëãîðèòìû, íà÷èíàÿ ñ
îáîáùåííîé ïîäïèñè ñõåìû Ýëü-Ãàìàëÿ [12, 17] â àääèòèâíîé ãðóïïå.
Ñèñòåìíûìè ïàðàìåòðàìè ÿâëÿþòñÿ óðàâíåíèå ýëëèïòè÷åñêîé êðèâîé E,
îïðåäåëåíèå ïîëÿ � è òî÷êà P êðèâîé èçâåñòíîãî áîëüøîãî ïîðÿäêà N , êîòîðàÿ
ÿâëÿåòñÿ îáðàçóþùèì ýëåìåíòîì ïîäãðóïïû G ãðóïïû òî÷åê ýëëèïòè÷åñêîé êðè-
âîé E ( )� . Îòêðûòûì êëþ÷îì ïðîâåðêè ÿâëÿåòñÿ òî÷êà Q dP� , ãäå d — ñåêðåò-
íûé êëþ÷ ïîäïèñè. Ïîäïèñü ñîîáùåíèÿ m , êîòîðóþ ôîðìèðóåò ïîëüçîâàòåëü A,
ýòî ïàðà ( , )R s , ãäå R kP� — ñëó÷àéíàÿ òî÷êà (ýëåìåíò ãðóïïû G), îïðåäåëÿåìàÿ
ñëó÷àéíûì ÷èñëîì k , 0 1� � �k N , ÷òî óäîâëåòâîðÿåòñÿ óðàâíåíèåì
h R Q sR h m P( ) ( )� � , (1)
ãäå h m( ) — õåø-çíà÷åíèå îò ñîîáùåíèÿ m, à h R( ) — õåø-çíà÷åíèå îò êîíêà-
òåíàöèè êîîðäèíàò òî÷êè R x y� ( , ).
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ðåøèòü óðàâíåíèå (1) îòíîñèòåëüíî s ìîæíî, çíàÿ òîëüêî ñåêðåòíîå çíà÷å-
íèå d :
sR h m P h R Q h m P h R dP� � � �( ) ( ) ( ) ( ) .
Òàêèì îáðàçîì, sP k h m h R d P� ��1 ( ( ) ( ) ) . Èç ýòîãî óðàâíåíèÿ ñëåäóåò, ÷òî
s k h m h R d� ��1 ( ( ) ( ) ) . (2)
×òîáû ïîäïèñàòü ñîîáùåíèå m , ïîëüçîâàòåëü A äîëæåí âûïîëíèòü òàêèå
äåéñòâèÿ:
1) âûáðàòü k , 0 1� � �k N , è âû÷èñëèòü R kP� ;
2) âû÷èñëèòü çíà÷åíèå s â ñîîòâåòñòâèè ñ (2).
Ïîëüçîâàòåëü B ñ öåëüþ ïðîâåðêè ïîäïèñè äîëæåí ïðîâåðèòü âåðèôèêàöè-
îííîå ñîîòíîøåíèå (1).
Ðàññìîòðèì íåêîòîðûå àòàêè íà òàêóþ ñõåìó ÖÏ (áîëåå ïîäðîáíî àòàêè íà
Ýëü-Ãàìàëÿ–ïîäîáíûå ñõåìû ðàññìàòðèâàþòñÿ â [13, 8]).
×òîáû ïîääåëàòü ïîäïèñü ïîä ñîîáùåíèåì �m , íåîáõîäèìî âû÷èñëèòü ñëó-
÷àéíîå R kP� è çàòåì ïàðàìåòð s , s k h m h R d� � ��1 ( ( ) ( ) ) . Äëÿ ýòîãî íóæíî, çíàÿ
Q dP� , âû÷èñëèòü ñåêðåòíîå çíà÷åíèå d , ò.å. ðåøèòü çàäà÷ó äèñêðåòíîãî ëîãà-
ðèôìèðîâàíèÿ â ãðóïïå òî÷åê ýëëèïòè÷åñêîé êðèâîé G íàä êîíå÷íûì ïîëåì, êî-
òîðàÿ áîëåå ñëîæíàÿ, ÷åì ýòà æå çàäà÷à â ìóëüòèïëèêàòèâíîé ãðóïïå êîíå÷íîãî
ïîëÿ ïðè óñëîâèè âûïîëíåíèÿ íåêîòîðûõ òðåáîâàíèé ê ýëëèïòè÷åñêîé êðèâîé.
Åñëè ñóùåñòâóåò äðóãîé ñïîñîá ïîääåëêè ïîäïèñè ïîä ñîîáùåíèåì m� (ò.å.
âû÷èñëèòü ïàðó ( , )R s òàê, ÷òîáû âûïîëíÿëîñü ñîîòíîøåíèå (1) ), òî ýòèì ñïîñî-
áîì ìîæíî ðåøàòü çàäà÷è äèñêðåòíîãî ëîãàðèôìèðîâàíèÿ â ýòîé ãðóïïå: âû÷èñ-
ëèòü ñåêðåòíûé êëþ÷ ïîäïèñè d h m sk h R� � � �( ( ) ) ( ) 1. Òàêèì îáðàçîì, ïðîáëåìà
ïîääåëêè ïîäïèñè íàñòîëüêî æå ñëîæíàÿ, êàê è çàäà÷à äèñêðåòíîãî ëîãàðèôìè-
ðîâàíèÿ â ãðóïïå òî÷åê ýëëèïòè÷åñêîé êðèâîé G .
Ïðè ðåàëèçàöèè òàêîé ñõåìû ïîäïèñè ñëåäóåò çíà÷åíèå k óíè÷òîæèòü ñðàçó
ïîñëå ôîðìèðîâàíèÿ ïîäïèñè, ïîñêîëüêó àòàêóþùèé ïî çíà÷åíèþ k è çíà÷åíèþ
ïîäïèñè ( , )R s ìîæåò âû÷èñëèòü ñåêðåòíûé êëþ÷ d h m sk h R� � �( ( ) ) ( ) .1
Âû÷èñëèòü ñåêðåòíûé êëþ÷ òàêæå âîçìîæíî ïðè ïîâòîðíîì èñïîëüçîâàíèè
÷èñëà k. Ïðåäïîëîæèì, ÷òî ñ îäíèì è òåì æå çíà÷åíèåì k ñôîðìèðîâàíû äâå
ïîäïèñè: ( , )R s1 è ( , )R s2 îò ñîîáùåíèé m1 è m2 ñîîòâåòñòâåííî. Ïðè ýòîì
s k h m h R d1
1
1� �� ( ( ) ( ) ) è s k h m h R d2
1
2� �� ( ( ) ( ) ) .
Òîãäà s s k h m h m1 2
1
1 2� � �� ( ( ) ( )) . Ïðè s s1 2� èìååì k h m h m� � �( ( ) ( ))1 2
� � �( ) ,s s1 2
1 à çíàÿ çíà÷åíèå k , ìîæíî âû÷èñëèòü d .
 àëãîðèòìå ïîäïèñè èñïîëüçóåòñÿ íå ñàìî ñîîáùåíèå, à åãî õåø-çíà÷åíèå,
òàê êàê ìîæíî ïîäîáðàòü ñîîáùåíèå ïî èçâåñòíîìó çíà÷åíèþ ïîäïèñè, íàïðè-
ìåð âûáðàòü ñëó÷àéíûå ÷èñëà i è j , à çàòåì ïðèíÿòü
R iP jQ i dj P� � � �( ) ; s h R j N� � �( ) 1mod .
Òîãäà ïàðà ( , )R s áóäåò ïîäïèñüþ ñîîáùåíèÿ m si N� �mod � �h R j i N( ) 1 mod ,
òàê êàê
( ( ) ) ( ( ) ( ) )( ( ) )mP h R dP s h R j iP h R dP h R j� � � � � �� � � �1 1 1 1
� � � � � � � �� � �h R j i h R jP h R d h R jP iP djP R( ) ( ( )) ( ) ( ( ))1 1 1 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 157
Èç ýòîãî ñëåäóåò ðàâåíñòâî ( ( ) )mP h R dP sR� � è ïîäòâåðæäåíèå ïîäïèñè
h R Q sR mP( ) � � .
Òàêæå ïîäïèñü õåø-çíà÷åíèÿ îò ñîîáùåíèÿ íåîáõîäèìà äëÿ ïðåäîòâðàùå-
íèÿ àòàêè íà îñíîâå ãîìîìîðôèçìîâ.
Èç óðàâíåíèÿ (1) ïàðàìåòð R G ìîæíî âûðàçèòü ñëåäóþùèì îáðàçîì:
R s h m P h R Q s h m P h R d P� � � � �� �1 1( ( ) ( ) ) ( ( ) ( )( ) ) . (3)
Ðåøàÿ óðàâíåíèå (3) îòíîñèòåëüíî s , ïîëó÷èì sR skP h m P� � ( ) � �h R d P( )( ) ,
îòêóäà ñëåäóåò
s k h m h R d� � ��1 ( ( ) ( )( )) . (4)
Ïîäïèñü ïîä ñîîáùåíèåì m îáîçíà÷àåòñÿ êàê ïàðà ( ( ), )h R s , ïðè ýòîì ïîëü-
çîâàòåëü A, êîòîðûé ôîðìèðóåò ýòó ïîäïèñü, âû÷èñëÿåò ñëó÷àéíóþ òî÷êó R G
è ïàðàìåòð s â ñîîòâåòñòâèè ñ ôîðìóëîé (4), èñïîëüçóÿ ñåêðåòíûé êëþ÷ ïîäïèñè
�d . Äëÿ ïðîâåðêè ýòîé ïîäïèñè íåîáõîäèìî èñïîëüçîâàòü ôîðìóëó (3), íî íå êàê
ïðåäèêàò ïðîâåðêè, à äëÿ âû÷èñëåíèÿ òî÷êè R ïî èçâåñòíûì çíà÷åíèÿì h R( ) , s ,
h m( ) è ïî çíà÷åíèþ �dP , êîòîðîå ïðåäñòàâëÿåò ñîáîé îòêðûòûé êëþ÷ ïîäïèñè.
Õåø-çíà÷åíèå âû÷èñëåííîé íà ýòàïå ïðîâåðêè òî÷êè R è çíà÷åíèå h R( ) , êîòîðîå
âû÷èñëèë ïîëüçîâàòåëü A, äîëæíû áûòü îäèíàêîâûìè. Íà ýòîì îñíîâûâàåòñÿ
ïðåäèêàò ïðîâåðêè.
 (3) è (4) âìåñòî h R( ) ìîæíî èñïîëüçîâàòü äðóãîå çíà÷åíèå, êîòîðîå îáîçíà-
÷èì r . Ïóñòü â äàííîì ñëó÷àå r áóäåò ðàâíî íåêîòîðîìó öåëîìó ÷èñëó x , âû÷èñ-
ëÿåìîìó èç ýëåìåíòà ïîëÿ � êîîðäèíàòû x � òî÷êè R . Äëÿ ôîðìèðîâàíèÿ ïîä-
ïèñè ( , )r s â ýòîì ñëó÷àå èñïîëüçóåòñÿ ôîðìóëà s k h m r d� � ��1 ( ( ) ( )) , à äëÿ ïðî-
âåðêè âû÷èñëÿåòñÿ òî÷êà R G ïî ôîðìóëå R s h m P r d P� � ��1 ( ( ) ( ) ) è
ñðàâíèâàåòñÿ öåëîå ÷èñëî x , êîòîðîå îïðåäåëÿåòñÿ èç ýëåìåíòà ïîëÿ � êîîðäèíà-
òû x âû÷èñëåííîé òî÷êè R, ñ ïàðàìåòðîì ïîäïèñè r. Òàêàÿ ñõåìà èñïîëüçóåòñÿ â
ñòàíäàðòå ECDSA (Elliptic Curve Digital Signature Algorithm).
Ðàññìîòðèì ïðèìåðû íàèáîëåå èçâåñòíûõ Ýëü-Ãàìàëÿ–ïîäîáíûõ ñõåì ïîäïè-
ñè, êîòîðûå îòëè÷àþòñÿ îò ïðèâåäåííûõ âûøå îñíîâíûì óðàâíåíèåì ïîäïèñè,
çíà÷åíèåì ïàðàìåòðà r è ôîðìîâàíèåì ñîîòâåòñòâóþùåãî ïðåäèêàòà ïðîâåðêè.
— ECSS (Elliptic Curve Signature Scheme). Âìåñòî óðàâíåíèÿ (1) èñïîëüçóåò-
ñÿ ðàâåíñòâî R sP rQ� � (ãäå r x h m� � ( )), èç êîòîðîãî ìîæíî íàéòè s : s k rd� � ,
à ïðè ïðîâåðêå â ñîîòâåòñòâèè ñ ýòèì óðàâíåíèåì âû÷èñëÿåòñÿ R .
— ÃÎÑÒ 34.10-2001 (Ðîññèéñêèé ñòàíäàðò) [16]. Âìåñòî óðàâíåíèÿ (1) èñ-
ïîëüçóåòñÿ óðàâíåíèå R h m sP h m rQ� �� �( ) ( )1 1 (ãäå r x� ), èç êîòîðîãî ìîæíî
íàéòè s : s kh m rd� �( ) . Ïðè ïðîâåðêå ïîäïèñè ( , )r s ïî îñíîâíîìó óðàâíåíèþ âû-
÷èñëÿþòñÿ R , à çàòåì r .
— ÄÑÒÓ 4145-2002 (Óêðàèíñêèé ñòàíäàðò, ïîäîáíûé ECSS) [1]. Âìåñòî
óðàâíåíèÿ (1) èñïîëüçóåòñÿ óðàâíåíèå R sP rQ� � , ãäå r x h m� ( ) , Q dP� � ,
s k rd� � . Ïðè ïðîâåðêå ïîäïèñè ( , )r s âû÷èñëÿåòñÿ R , à çàòåì r .
— EC-GDSA (Elliptic Curve based German Digital Signature Algorithm). Â êà-
÷åñòâå îñíîâíîãî óðàâíåíèÿ ïîäïèñè èñïîëüçóåòñÿ óðàâíåíèå R r sQ� ��1
� �r h m P1 ( ) , ãäå r x� , Q dP� , s kr h m d� �( ( )) , â ñîîòâåòñòâèè ñ êîòîðûì ïðè
ïðîâåðêå ïîäïèñè ( , )r s âû÷èñëÿåòñÿ ïàðàìåòð R .
— EC-KCDSA (Korean Certificate-based Digital Signature Algorithm using
Elliptic Curves). Îñíîâíîå óðàâíåíèå ïîäïèñè: R sQ r h C m PA� �
( ( ))� , ãäå
r h R� ( ) , Q d P� �1 , CA — ñåðòèôèêàò îòêðûòîãî êëþ÷à ïîëüçîâàòåëÿ A.  ñîîò-
âåòñòâèè ñ ýòèì óðàâíåíèåì ïðè ïðîâåðêå ïîäïèñè ( , )r s íàõîäèòñÿ R , ïàðàìåòð s
âû÷èñëÿåòñÿ ñëåäóþùèì îáðàçîì: s k r h C m dA� �
( ( ( )))� .
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
Ñðàâíèòåëüíûå õàðàêòåðèñòèêè ýòèõ àëãîðèòìîâ, âêëþ÷àÿ îáúåì íåîáõîäè-
ìûõ âû÷èñëåíèé äëÿ ôîðìèðîâàíèÿ è ïðîâåðêè ïîäïèñè, à òàêæå èõ ñòîéêîñòü
áîëåå äåòàëüíî ïðèâîäÿòñÿ â [13].
ÏÎÑÒÐÎÅÍÈÅ ÑÕÅÌ ÖÏ Ñ ÎÒÊÐÛÒÛÌ ÈÍÄÈÂÈÄÓÀËÜÍÛÌ ÊËÞ×ÎÌ
Äëÿ Ýëü-Ãàìàëÿ–ïîäîáíûõ ñõåì ÖÏ ÿâëÿåòñÿ âîçìîæíûì ïîñòðîåíèåì èõ àíà-
ëîãîâ ñ èñïîëüçîâàíèåì ìàòåìàòè÷åñêîãî àïïàðàòà áèëèíåéíûõ îòîáðàæåíèé ñ
öåëüþ ïîñòðîåíèÿ ñõåì ÖÏ ñ îòêðûòûì èíäèâèäóàëüíûì êëþ÷îì ïîëüçîâàòåëÿ.
Ïóñòü G1 è G2— ñîîòâåòñòâåííî àääèòèâíàÿ è ìóëüòèïëèêàòèâíàÿ ãðóï-
ïû ïðîñòîãî ïîðÿäêà q . Áèëèíåéíûì ñïàðèâàíèåì (èëè ïàðíûì îòîáðàæåíè-
åì) íàçûâàåòñÿ ëåãêî âû÷èñëÿåìîå íåâûðîæäåííîå áèëèíåéíîå îòîáðàæå-
íèå e G G G: 1 1 2� � , ò.å. îòîáðàæåíèå ñî ñëåäóþùèìè ñâîéñòâàìè.
1. Áèëèíåéíîñòü.
Äëÿ � P Q R G, , 1 : e P Q R e P R e Q R( , ) ( , ) ( , )� � è e P Q R( , )� � e P Q e P R( , ) ( , ) .
Èç ýòîãî ñëåäóåò, ÷òî äëÿ � P Q G, 1 è � a b q, *
� : e aP bQ e P Q ab( , ) ( , )� .
2. Íåâûðîæäåííîñòü.
Ñóùåñòâóåò P G 1 , e P P( , ) �1 , ò.å. åñëè P ÿâëÿåòñÿ îáðàçóþùèì ýëåìåí-
òîì G1 , òî e P P( , ) áóäåò îáðàçóþùèì ýëåìåíòîì G2 , òàê êàê G1 è G2 — ãðóïïû
ïðîñòîãî ïîðÿäêà.
3. Âû÷èñëèìîñòü.
Ñóùåñòâóåò ýôôåêòèâíûé ïîëèíîìèàëüíûé àëãîðèòì âû÷èñëåíèÿ
e P Q G( , ) 2 äëÿ � P Q G, 1.
Ïóñòü ID { , }*0 1 — ëè÷íîñòíûå äàííûå ïîëüçîâàòåëÿ ñõåìû, êîòîðûé ôîð-
ìèðóåò ïîäïèñü ñîîáùåíèÿ m , QID — åãî îòêðûòûé êëþ÷, s — ñåêðåòíûé ìàñ-
òåð-êëþ÷ PKG, P sPpub � — îòêðûòûé ìàñòåð-êëþ÷ PKG. Îòêðûòûé êëþ÷ QID
ïîëüçîâàòåëÿ âû÷èñëÿåòñÿ èç åãî ID ñ ïîìîùüþ õåø-ôóíêöèè h G1 10 1: { , }* � .
Ïîäïèñü ïîä ñîîáùåíèåì m , êîòîðóþ ôîðìèðóåò ïîëüçîâàòåëü ñ åãî îáùå-
èçâåñòíûìè äàííûìè ID , ýòî ïàðà ( , )r S (ãäå S G 1 , r h m R� ( ) , R e P P k� ( , ) —
ñëó÷àéíûé ýëåìåíò ãðóïïû G2 , îïðåäåëÿåìûé ñëó÷àéíûì ïàðàìåòðîì k q �
*)
òàêàÿ, ÷òî âûïîëíÿåòñÿ ðàâåíñòâî
e P P e S P e Q Pk
ID pub
r( , ) ( , ) ( , )� . (5)
Ðåøèòü ýòî óðàâíåíèå îòíîñèòåëüíî íåèçâåñòíîé òî÷êè ýëëèïòè÷åñêîé êðè-
âîé S ìîæíî, çíàÿ òîëüêî ñåêðåòíîå çíà÷åíèå s . Ïîýòîìó èìååì
e kP P e S P e rsQ PID( , ) ( , ) ( , )� , âåëè÷èíó sQID îáîçíà÷èì DID . Òîãäà
e kP P e S rD PID( , ) ( , )� � . Èç ýòîãî ñëåäóåò, ÷òî kP S rDID� � , à çíà÷åíèå ïàðà-
ìåòðà ïîäïèñè S âûðàæàåòñÿ ñëåäóþùèì îáðàçîì:
S kP rDID� � . (6)
Äëÿ ôîðìèðîâàíèÿ ïîäïèñè ïîëüçîâàòåëåì A ñ åãî ëè÷íîñòíûìè äàííûìè IDA
íåîáõîäèìî, ÷òîáû PKG ñãåíåðèðîâàë ñåêðåòíûé ìàñòåð-êëþ÷ s , âû÷èñëèë Ppub è
ïàðàìåòð DIDA
, êîòîðûé ÿâëÿåòñÿ ñåêðåòíûì êëþ÷îì ïîëüçîâàòåëÿ A. Ïîëüçîâàòåëü
A ïîëó÷àåò D GIDA
1 îò PKG ïî çàùèùåííîìó êàíàëó è ãåíåðèðóåò ñëó÷àéíîå çíà-
÷åíèå k q �
* , çàòåì âû÷èñëÿåò r è â ñîîòâåòñòâèè ñ (6) íàõîäèò ïàðàìåòð S .
Äëÿ ïðîâåðêè ýòîé ïîäïèñè, ò.å. ïàðû ( , )r S ïîä ñîîáùåíèåì m , ñëåäóåò âû÷èñ-
ëèòü çíà÷åíèå R â ñîîòâåòñòâèè ñ (5), çàòåì çíà÷åíèå h m R( ) è ñðàâíèòü åãî ñ ïàðàìåò-
ðîì ïîäïèñè r . Ýòè çíà÷åíèÿ äîëæíû áûòü îäèíàêîâûìè. Òàêóþ ñõåìó ìîæíî ñ÷è-
òàòü áèëèíåéíûì àíàëîãîì àëãîðèòìà ÖÏ, êîòîðûé îïðåäåëåí â ÄÑÒÓ 4145-2002.
Ñòîéêîñòü ýòîé ñõåìû îáóñëîâëåíà òðóäíîñòüþ ðåøåíèÿ ñëàáîé çàäà÷è
Äèôôè–Õåëëìàíà â àääèòèâíîé ãðóïïå (W-DH — Weak Diffie–Hellman problem),
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 159
êîòîðàÿ ôîðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì: äëÿ çàäàííîãî íàáîðà P Q sP, , , ãäå
P Q G, 1 è s q �
* , âû÷èñëèòü òî÷êó sQ . Ñ÷èòàåòñÿ, ÷òî ýòà çàäà÷à íå ñëîæíåå, ÷åì
âû÷èñëèòåëüíàÿ çàäà÷à Äèôôè–Õåëëìàíà (CDH problem — Computational
Diffie-Hellman problem) â àääèòèâíîé ãðóïïå. Â íàñòîÿùåå âðåìÿ íåèçâåñòíî, ìîæíî
ëè åå ðåøèòü, ìèíóÿ çàäà÷ó äèñêðåòíîãî ëîãàðèôìà äëÿ ýëëèïòè÷åñêèõ êðèâûõ.
Äîïóñòèì, ÷òî àòàêóþùåìó èçâåñòíû ïàðàìåòðû P , QID è P sPpub � . Äëÿ
òîãî ÷òîáû ïîääåëàòü ïîäïèñü, îí äîëæåí óìåòü íàõîäèòü êëþ÷ D sQID ID� , ò.å.
ðåøèòü çàäà÷ó W-DH. Äàëåå ïîñòðîèì áèëèíåéíóþ ñõåìó ÖÏ ñ îòêðûòûì èíäè-
âèäóàëüíûì êëþ÷îì íà áàçå àëãîðèòìà, êîòîðûé îïðåäåëåí â EC-GDSA. Êàê è
â âûøåïðèâåäåííîé ñõåìå, ÷òîáû ïîëüçîâàòåëü A ñ åãî ëè÷íîñòíûìè äàííûìè
IDA ñôîðìèðîâàë ïîäïèñü ïîä ñîîáùåíèåì m , íåîáõîäèìî, ÷òîáû PKG ñãåíåðè-
ðîâàë ñåêðåòíûé ìàñòåð-êëþ÷ s , âû÷èñëèë P sPpub � , à òàêæå ñåêðåòíûé êëþ÷
D sQID IDA A
� ïîëüçîâàòåëÿ A . Ïîëüçîâàòåëü A äîëæåí ïîëó÷èòü D GIDA
1 îò PKG
è ñãåíåðèðîâàòü ñëó÷àéíîå çíà÷åíèå k q �
* , çàòåì âû÷èñëèòü r R e P P k� � ( , ) è S
ïî ôîðìóëå S rkP h m DID� � ( ) .
Äëÿ ïðîâåðêè ïîäïèñè ( , )r S ïîä ñîîáùåíèåì m íåîáõîäèìî âû÷èñëèòü ïà-
ðàìåòð R : R e S P e Q Pr
ID pub
r h m�
� �
( , ) ( , ) ( )1 1
, çàòåì ñðàâíèòü ïàðàìåòð R ñ ïàðà-
ìåòðîì ïîäïèñè r , êîòîðûå äîëæíû áûòü îäèíàêîâûìè.
Êîððåêòíîñòü ñõåìû ìîæíî äîêàçàòü, èñïîëüçóÿ ñëåäóþùèå ñîîòíîøåíèÿ:
e S P e Q P e rkP h m D P e Qr
ID pub
r h m
ID
r( , ) ( , ) ( ( ) , ) (( )� � �
� �
1 1 1
ID pub
r h mP, ) ( )�
�
1
� � �� �e kP r h m D P e r h m Q sPID ID( ( ) , ) ( ( ) , )1 1
� � �� �e kP r h m D P e r h m D P e kP PID ID( ( ) , ) ( ( ) , ) ( , )1 1 .
 áèëèíåéíîé ñõåìå ÖÏ ñ îòêðûòûì èíäèâèäóàëüíûì êëþ÷îì íà áàçå àëãî-
ðèòìà EC-KCDSA ïàðàìåòð S âû÷èñëèì ïî ôîðìóëå S kP eDID� � , ãäå
e r h ID mA�
( ( ))� , r h R� ( ) , R e P P k� ( , ) .
Äëÿ ïðîâåðêè ïîäïèñè ( , )r S ñëåäóåò âû÷èñëèòü R â ñîîòâåòñòâèè ñ âûðàæå-
íèåì R e S P e Q PID pub
e� ( , ) ( , ) , çàòåì âû÷èñëèòü h R( ) . Ýòî çíà÷åíèå äîëæíî
áûòü ðàâíî ïàðàìåòðó ïîäïèñè r .
Êîððåêòíîñòü ýòîé ñõåìû ñëåäóåò èç ñëåäóþùèõ òîæäåñòâ:
h e S P e Q PID pub
e( ( , ) ( , ) ) �
� � � �h e kP eD P e Q P h e kP eD P e esQID ID pub
e
ID ID( ( , ) ( , ) ) ( ( , ) ( , ))P �
� � � � �h e kP eD esQ P h e kP P h e P PID ID
k( ( , )) ( ( , )) ( ( , ) ) .
ÏÎÐÎÃÎÂÀß ÑÕÅÌÀ ÏÎÄÏÈÑÈ
Èçâåñòíî, ÷òî áåçîïàñíîñòü àñèììåòðè÷íûõ êðèïòîñèñòåì ñóùåñòâåííî çàâè-
ñèò îò êîíôèäåíöèàëüíîñòè ñåêðåòíûõ êëþ÷åé. Ýòè êëþ÷è äîëæíû áûòü
íåäîñòóïíûìè äëÿ àòàêóþùèõ, ò.å. áåçîïàñíîñòü êðèïòîñèñòåìû çàâèñèò îò
íåñïîñîáíîñòè ïîëó÷åíèÿ èìè äîñòóïà ê êëþ÷àì.  ðàáîòàõ [18, 19] ïðåäëà-
ãàþòñÿ ñïîñîáû çàùèòû îò àòàê ïîäîáíîãî ðîäà íà îñíîâå ñõåì ðàçäåëåíèÿ ñåêðå-
òà, êîãäà ñåêðåòíûé êëþ÷ ðàçäåëÿåòñÿ ìåæäó íåñêîëüêèìè ó÷àñòíèêàìè, ïîñêîëüêó
âîññòàíîâëåíèå êëþ÷à â îäíîì ìåñòå ïðåäñòàâëÿåò ñîáîé ïðèâëåêàòåëüíóþ ìèøåíü
äëÿ àòàêè. Äëÿ ðåøåíèÿ ýòîé ïðîáëåìû áûëè ïðåäëîæåíû ïîðîãîâûå ñõåìû [20].
 òàêèõ ñèñòåìàõ êàæäûé ó÷àñòíèê ñîäåðæèò ÷àñòü ñåêðåòíîãî êëþ÷à, îò-
äåëüíûå äîëè êëþ÷à ñîõðàíÿþòñÿ êîíêðåòíî ó íèõ è íèêîãäà íå ðàñêðûâàþòñÿ
äðóãèì ñòîðîíàì, à äëÿ âûïîëíåíèÿ íóæíîé ôóíêöèè, íàïðèìåð ôîðìèðîâàíèÿ
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
ïîäïèñè, íåîáõîäèìî, ÷òîáû äîñòàòî÷íî áîëüøîå êîëè÷åñòâî ó÷àñòíèêîâ (ïîðî-
ãîâîå ÷èñëî) äåéñòâîâàëè ñîâìåñòíî. Êàæäûé èç íèõ ïîëó÷àåò ÷àñòè÷íûé ðå-
çóëüòàò. Ýòè ÷àñòè îáúåäèíÿþòñÿ ñ ïîìîùüþ îòêðûòîé, ò.å. íåñåêðåòíîé, ôóíê-
öèè, äëÿ ïîëó÷åíèÿ íóæíîãî ðåçóëüòàòà.  ýòîì ñëó÷àå ÿâíîãî âîññòàíîâëåíèÿ
ðàçäåëåííîãî êëþ÷à íå ïðîèñõîäèò.
Òàêèì îáðàçîì, äëÿ êîìïðîìåòàöèè ñèñòåìû àòàêóþùåìó íóæíî ñêîìïðî-
ìåòèðîâàòü òàêîå êîëè÷åñòâî äîëåé ñåêðåòà, êîòîðîå ÿâëÿåòñÿ íå ìåíüøèì, ÷åì
ïîðîãîâîå ÷èñëî, ïðè ýòîì èñêëþ÷àåòñÿ ñóùåñòâîâàíèå åäèíîãî ìåñòà, â êîòîðîì
ñèñòåìà ìîæåò áûòü ñêîìïðîìåòèðîâàííîé.
Íà îñíîâå ñõåìû ïîäïèñè, êîòîðàÿ îïèñûâàåòñÿ óðàâíåíèÿìè (5) è (6), ìîæíî
ïîñòðîèòü ïîðîãîâóþ ñõåìó, ãäå ñåêðåòíûé êëþ÷ DID äëÿ ôîðìèðîâàíèÿ ïîäïèñè
íå ïðèíàäëåæèò îòäåëüíîìó ïîëüçîâàòåëþ, à ðàçäåëÿåòñÿ ìåæäó íåêîòîðûìè ïî-
ëüçîâàòåëÿìè, êîëè÷åñòâî êîòîðûõ ðàâíî n, ñ ïîìîùüþ ïîðîãîâîé ñõåìû Øàìèðà
( , )t n [18]. Òàêèì îáðàçîì, âîññòàíîâèòü DID ìîæåò ëþáîå ïîäìíîæåñòâî
èç
ýòèõ ïîëüçîâàòåëåé, ðàçìåð êîòîðîãî íå ìåíüøå t . ×àñòè (äîëè, ïðîåêöèè) ñåêðåò-
íîãî êëþ÷à DID îáîçíà÷èì D D DID ID IDn1 2
, , ..., . Òîãäà D L DID i ID
i
i
�
�
, ãäå
L
x
x x
i
j i
j
i j
�
�
�
�
\{ }
, à x i ni , ,�1 , ïðèíàäëåæèò i-ìó ïîëüçîâàòåëþ.
PKG ôîðìèðóåò ñåêðåòíûé ìàñòåð-êëþ÷ s , êîòîðûé ïðåäñòàâëÿåòñÿ â âèäå
äîëåé s s sn1 2, , ..., òàêèõ, ÷òî s L si i
i
�
�
, ôîðìèðóåò îòêðûòûå ìàñòåð-êëþ÷è
P s Ppub ii
� , à òàêæå P sPpub � , äàëåå âû÷èñëÿåò D s QID i IDi
� , ïðè ýòîì
D L D L s Q L s Q sQID i ID
i
i i ID
i
i i
i
ID Ii
� � �
�
�
�
�
�
�
�
�
�
� � �
D . Çàòåì ïî çàùèùåííîìó
êàíàëó PKG ïåðåäàåò i-ìó ïîëüçîâàòåëþ äîëþ DIDi
èëè äîëþ ìàñòåð-êëþ÷à si ,
èñïîëüçóÿ ñõåìó Ôåëüäìàíà èëè Ïåòåðñåíà [21, 22], à çàêðûòûé êëþ÷ DIDi
âû-
÷èñëÿåò i-é ïîëüçîâàòåëü.
Äëÿ ôîðìèðîâàíèÿ ÷àñòè ïîäïèñè ( , )R Si i êàæäûé i-é ïîëüçîâàòåëü ãåíåðè-
ðóåò k i q �
* , âû÷èñëÿåò R e P Pi
ki� ( , ) , ïåðåäàâàÿ åãî âñåì äðóãèì ïîëüçîâàòå-
ëÿì, è â ñîîòâåòñòâèè ñ (6) âû÷èñëÿåò S k P rDi i IDi
� � . Ïðè ýòîì R îïðåäåëÿåòñÿ
ïî ôîðìóëå
R R e P P e P P e P Pi
L
i
k L
i
L k
ki i i
i
i
i
� � �
�
�
� �
( ( , ) ) ( , ) ( , ) . (7)
Ïðîâåðêà êàæäîé äîëè ïîäïèñè îñóùåñòâëÿåòñÿ â ñîîòâåòñòâèè ñ ïðåäèêà-
òîì (5), ò.å. e P P e S P e Q P
k
i ID pub
ri
i
( , ) ( , ) ( , )� , ñ ó÷åòîì (7).
Ðåêîíñòðóêöèÿ ïîäïèñè òàêæå âûïîëíÿåòñÿ ñ ïîìîùüþ èíòåðïîëÿöèè
Ëàãðàíæà:
S L S L k P rD L k P L rDi i
i
i i ID
i
i i i ID
ii
i i
� � � � � �
� � �
( ) �
� � � �
��( ) ,L k P r L D kP rDi i i ID
ii
IDi
R R e P Pi
L
i
ki� �
�
( , ) .
Òàêèì îáðàçîì, ðåêîíñòðóèðîâàííàÿ ïîäïèñü ( , )R S àíàëîãè÷íà ïîäïèñè, ñôîðìèðî-
âàííîé îäíèì ïîëüçîâàòåëåì ñî ñëó÷àéíûì k L ki i
i
q�
�
�
* è ñåêðåòíûì êëþ÷îì DID .
Ïîðîãîâàÿ ñõåìà ìîæåò èñïîëüçîâàòüñÿ äëÿ ïîâûøåíèÿ ñòîéêîñòè ñõåì ñ îò-
êðûòûì èíäèâèäóàëüíûì êëþ÷îì ê êîìïðîìåòàöèè êëþ÷åé. Àíàëîãè÷íî âû-
øåïðèâåäåííîé ïîðîãîâîé ñõåìå ÖÏ ìîæíî ïîñòðîèòü òàêæå ïîðîãîâûå ñõåìû
äëÿ áèëèíåéíûõ àíàëîãîâ àëãîðèòìîâ EC-GDSA è EC-KCDSA.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3 161
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ä Ñ Ò Ó 4 1 4 5 - 2 0 0 2 . ²íôîðìàö³éí³ òåõíîëî㳿. Êðèïòîãðàô³÷íèé çàõèñò ³íôîðìàö³¿.
Öèôðîâèé ï³äïèñ, ùî ´ðóíòóºòüñÿ íà åë³ïòè÷íèõ êðèâèõ. Ôîðìóâàííÿ òà ïåðåâ³ðÿííÿ. — Ê.:
Äåðæñòàíäàðò Óêðà¿íè, 2003. — 94 ñ.
2. S h a m i r A . Identity-based cryptosystems and signature schemes // Advances in Cryptology — Pro-
ceedings of CRYPTO 84. Lecture Notes in Computer Science. — 1985. — 196. — P. 47–53.
3. B o n e h D . , F r a n k l i n M . Identity based encryption from the weil pairing / Extended Abstract in
Crypto 2001 // SIAM J. of Computing. — 2003. — 32, N 3. — P. 586–615.
4. G e n t r y C . , S i l v e r b e r g A . Hierarchical ID-based cryptography / Y. Zheng (ed). Proceedings of
Asiacrypt 2002. Lecture Notes in Computer Science. — Springer-Verlag. — 2002.
5. B o n e h D . , B o y e n X . Efficient selective-ID secure identity based encryption without random or-
acles // In Proceedings of Eurocrypt, 2004.
6. Z h a n g F . , K i m K . ID-Based blind signature and ring signature from pairings // Advances in Cryptology
–Asiacrypt 2002. Lecture Notes in Computer Science. — Springer-Verlag. — 2002. — 2510.
7. H e s s F . Efficient identity based signature schemes based on pairings // SAC 2002. Lecture Notes
in Computer Science 2595. — Springer-Verlag. — 2002. — P. 310–324.
8. à î ð á å í ê î Þ . ² . , à î ð á å í ê î ² . Ä . ²íôðàñòðóêòóðà â³äêðèòèõ êëþ÷³â. Åëåêòðîííèé ï³äïèñ.
Òåîð³ÿ òà ïðàêòèêà. — Õàðê³â: Ôîðò, 2010. — 608 ñ.
9. Ç à ï å ÷ í è ê î â Ñ . Â . Ïîðîãîâûå ñõåìû öèôðîâîé ïîäïèñè íà îñíîâå ñòàíäàðòà ÃÎÑÒ
34.10-94 // Áåçîïàñíîñòü èíôîðìàöèîííûõ òåõíîëîãèé. — 2001. — ¹ 4. — Ñ. 45–51.
10. Ç à ï å ÷ í è ê î â Ñ .  . Îáåñïå÷åíèå êðèïòîãðàôè÷åñêîé ñòîéêîñòè ïðè êîìïðîìåòàöèè ÷àñòè
êëþ÷åé // Òàì æå. — 2008. — ¹ 4. — Ñ. 93–102.
11. Ñ å ð î â Ð . Å . Ïîðîãîâàÿ ñõåìà øèôðîâàíèÿ/ïîäïèñè íà îñíîâå ÃÎÑÒ 34.10-2001 // Òàì æå. —
2004. — ¹ 3. — Ñ. 87–90.
12. E l G a m a l T . Public key cryptosystems and a signature scheme based on discrete logarithms //
IEEE Transactions on Information Theory. — 1985. — IT-31, N 4. — P. 469–472.
13. Á å ñ ñ à ë î â À .  . , Ò å ë è æ å í ê î À . Á . Êðèïòîñèñòåìû íà ýëëèïòè÷åñêèõ êðèâûõ. — Êèåâ.:
²ÂÖ Âèä-âî «Ïîë³òåõí³êà», 2004. — 224 ñ.
14. A N S I X 9 . 6 2 - 1 9 9 9 . Public key cryptography for the financial services industry: the elliptic
curve digital signature algorithm (ECDSA), 1999.
15. F I P S 1 8 6 - 2 - 2 0 0 0 . Digital signature standard. national institute of standard and technology, 2000.
16. Ã Î Ñ Ò 3 4 . 1 0 - 2 0 0 1 . Èíôîðìàöèîííàÿ òåõíîëîãèÿ. Êðèïòîãðàôè÷åñêàÿ çàùèòà
èíôîðìàöèè. Ïðîöåäóðû ôîðìèðîâàíèÿ è ïðîâåðêè ýëåêòðîííîé öèôðîâîé ïîäïèñè. — Ì.:
Ãîññòàíäàðò Ðîññèè, 2001. — 20 ñ.
17. Á î ë î ò î â À . À . , Ã à ø ê î â Ñ . Á . , Ô ð î ë î â À . Á . , × à ñ î â ñ ê è õ À . À . Ýëåìåíòàðíîå
ââåäåíèå â ýëåïòè÷åñêóþ êðèïòîãðàôèþ. Ïðîòîêîëû êðèïòîãðàôèè íà ýëëèïòè÷åñêèõ êðèâûõ.
×. 2. — Ì.: ÊîìÊíèãà, 2006. — 280 ñ.
18. S h a m i r A . How to share a secret // Communications of the ACM. — 1979. — 2 2 . — P. 612–613.
19. B l a k l e y G . R . Safeguarding cryptographic keys // Proceedings of the National Computer Confe-
rence 48, 1979. — P. 313–317.
20. S e b e r r y J . Crypto topics and applications. II. University of Wollongong, 1999.
— http://ro.uow.edu.au/infopapers/348.
21. F e l d m a n P . A . Practical scheme for non-interactive verifiable secret sharing // Proc. 28th Annual
Symp. on Founds. of Comp. Sci., 1987. — P. 427–437.
22. P e d e r s e n T . P . Non-interactive and information-theoretic secure verifiable secret sharing // Ad-
vances in Cryptology — CRYPTO'91. Lecture Notes in Computer Science. — Springer-Verlag. —
1992. — 576. — P. 129–140.
23. D u t t a R . , B a r u a R . , S a r k a r P . Pairing-based cryptographic protocols: a survey. — Kolkata,
India. — h t t p : / / e p r i n t . i a c r . o r g / 2 0 0 4 / 0 6 4 .
Ïîñòóïèëà 22.11.2010
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 3
|