Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки
Запропоновано алгоритм створення електронного цифрового підпису в непозиційній поліноміальній системі числення, що формує три надмірні лишки за модулем однієї додаткової поліноміальної основи. Цей підпис дозволяє також виявляти і коректувати одиничну помилку і визначати багатократну. Показано однозн...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2012 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84121 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки / Р.Г. Бияшев, С.Е. Нысанбаева // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 14-23. — Бібліогр.: 9 назв. — рос. . |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859746714342129664 |
|---|---|
| author | Бияшев, Р.Г. Нысанбаева, С.Е. |
| author_facet | Бияшев, Р.Г. Нысанбаева, С.Е. |
| citation_txt | Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки / Р.Г. Бияшев, С.Е. Нысанбаева // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 14-23. — Бібліогр.: 9 назв. — рос. . |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано алгоритм створення електронного цифрового підпису в непозиційній поліноміальній системі числення, що формує три надмірні лишки за модулем однієї додаткової поліноміальної основи. Цей підпис дозволяє також виявляти і коректувати одиничну помилку і визначати багатократну. Показано однозначність процедури виявлення і виправлення одиничної помилки. Визначено формулу криптостійкості цифрового підпису.
The authors propose an algorithm for creating a digital signature in a nonpositional polynomial notation, which forms three surplus residues modulo one additional polynomial base. This signature allows single-error detection and correction (which is shown to be a unique procedure) and multi-error detection. A formula for the cryptographic security of the digital signature is obtained.
|
| first_indexed | 2025-12-01T21:28:14Z |
| format | Article |
| fulltext |
ÓÄÊ 004.056.5
Ð.Ã. ÁÈßØÅÂ, Ñ.Å. ÍÛÑÀÍÁÀÅÂÀ
ÀËÃÎÐÈÒÌ ÔÎÐÌÈÐÎÂÀÍÈß ÝËÅÊÒÐÎÍÍÎÉ ÖÈÔÐÎÂÎÉ
ÏÎÄÏÈÑÈ Ñ ÂÎÇÌÎÆÍÎÑÒÜÞ ÎÁÍÀÐÓÆÅÍÈß
È ÈÑÏÐÀÂËÅÍÈß ÎØÈÁÊÈ
Êëþ÷åâûå ñëîâà: ýëåêòðîííàÿ öèôðîâàÿ ïîäïèñü, íåïîçèöèîííàÿ ïîëèíîìè-
àëüíàÿ ñèñòåìà ñ÷èñëåíèÿ, ïîëíàÿ ñèñòåìà âû÷åòîâ, êðèïòîñòîéêîñòü.
Ñèñòåìû ýëåêòðîííîé öèôðîâîé ïîäïèñè (ÝÖÏ) âêëþ÷àþò äâà àëãîðèòìà:
ôîðìèðîâàíèå öèôðîâîé ïîäïèñè è åå ïðîâåðêà. Ïðè ðàçðàáîòêå ñõåì ÝÖÏ
èñïîëüçóþòñÿ ïðèíöèïèàëüíî ðàçëè÷íûå ïîäõîäû, êîòîðûå ìîæíî ðàçäåëèòü
íà òðè ãðóïïû. Ýòî ñõåìû íà áàçå:
� ñèñòåì øèôðîâàíèÿ ñ îòêðûòûìè êëþ÷àìè;
� ñèììåòðè÷íûõ ñèñòåì øèôðîâàíèÿ;
� ñïåöèàëüíî ðàçðàáîòàííûõ àëãîðèòìîâ âû÷èñëåíèÿ è ïðîâåðêè ïîäïèñè.
Ïðåäëàãàåìàÿ íèæå ñõåìà öèôðîâîé ïîäïèñè îòíîñèòñÿ ê ïîñëåäíåé ãðóïïå.
 îñíîâå èçâåñòíûõ ñèñòåì ÝÖÏ ëåæàò àëãîðèòìû RSA, Ýëü Ãàìàëÿ, à òàêæå
DSA, ïðåäëîæåííûé â 1991 ã. äëÿ èñïîëüçîâàíèÿ â êà÷åñòâå ñòàíäàðòà öèôðîâîé
ïîäïèñè DSS (Digital Signature Standard) â ÑØÀ. Ðîññèéñêèé ñòàíäàðò ÃÎÑÒ
Ð 34.10–94 âñòóïèë â äåéñòâèå â 1995 ã. Ýòè àëãîðèòìû è ñòàíäàðòû ðàçðàáîòàíû
íà áàçå êðèïòîñèñòåì ñ îòêðûòûìè êëþ÷àìè.
 Ðåñïóáëèêå Êàçàõñòàí ãîñóäàðñòâåííûì ñòàíäàðòîì ÑÒ ÐÊ 1073-2007
îïðåäåëåíû ÷åòûðå óðîâíÿ áåçîïàñíîñòè ñèñòåì ÝÖÏ [1].  ñîîòâåòñòâèè ñ óñòà-
íîâëåííûìè â íåì òðåáîâàíèÿìè ê ñðåäñòâàì êðèïòîãðàôè÷åñêîé çàùèòû èí-
ôîðìàöèè ïåðâîãî, âòîðîãî, òðåòüåãî è ÷åòâåðòîãî óðîâíåé äëèíà êëþ÷à ÝÖÏ
äîëæíà áûòü íå ìåíåå 60, 100, 150 è 200 áèò ñîîòâåòñòâåííî.
Ïðåäëàãàåìûé àëãîðèòì ðàçðàáîòàí ñ èñïîëüçîâàíèåì íåïîçèöèîííûõ ïîëè-
íîìèàëüíûõ ñèñòåì ñ÷èñëåíèÿ (ÍÏÑÑ), ñèíîíèìàìè êîòîðûõ ÿâëÿþòñÿ ìîäóëÿð-
íàÿ àðèôìåòèêà è ñèñòåìû ñ÷èñëåíèÿ â îñòàòî÷íûõ êëàññàõ.  ÍÏÑÑ îñíîâàíèÿìè
ÿâëÿþòñÿ íå ïðîñòûå ÷èñëà [2], à íåïðèâîäèìûå ìíîãî÷ëåíû íàä ïîëåì GF(2) [3].
Àëãîðèòìû è ìåòîäû, ñîçäàííûå íà áàçå ýòèõ ñèñòåì, íàçûâàþò íåòðàäèöèîííû-
ìè. Ïðèìåíåíèå ÍÏÑÑ ïðè ïîñòðîåíèè íåòðàäèöèîííûõ àëãîðèòìîâ êðèïòîãðà-
ôè÷åñêîé çàùèòû õðàíèìîé è ïåðåäàâàåìîé èíôîðìàöèè ïîçâîëÿåò çíà÷èòåëüíî
ïîâûñèòü èõ ýôôåêòèâíîñòü è êðèïòîñòîéêîñòü [4–7]. Íà áàçå ÍÏÑÑ ñîçäàíû
äâå ñèñòåìû ýëåêòðîííîé ïîäïèñè. Ïåðâàÿ ñõåìà ÝÖÏ ïðåäñòàâëåíà â [4, 6].
Íèæå ïðèâåäåíû ðåçóëüòàòû ïîñòðîåíèÿ âòîðîé ñèñòåìû ÝÖÏ.
Ðàññìîòðèì ïðîöåäóðó ïîñòðîåíèÿ ÍÏÑÑ. Ïóñòü îñíîâàíèÿìè ÍÏÑÑ âû-
áðàíû íåïðèâîäèìûå ìíîãî÷ëåíû p x p x p xS1 2( ), ( ), , ( )� íàä ïîëåì GF ( )2 ñòå-
ïåíè m m mS1 2, , ,� ñîîòâåòñòâåííî. Ýòè ïîëèíîìû ñ ó÷åòîì ïîðÿäêà èõ ðàñïî-
ëîæåíèÿ îáðàçóþò ñèñòåìû îñíîâàíèé è íàçûâàþòñÿ ðàáî÷èìè (èíôîðìàöèîí-
íûìè èëè ñèìâîëàìè). Â ñîîòâåòñòâèè c êèòàéñêîé òåîðåìîé îá îñòàòêàõ âñå
îñíîâàíèÿ äîëæíû áûòü ðàçëè÷íûìè, â òîì ÷èñëå è òîãäà, êîãäà îíè èìåþò îäíó
ñòåïåíü. Îñíîâíûì ðàáî÷èì äèàïàçîíîì â ÍÏÑÑ ÿâëÿåòñÿ ìíîãî÷ëåí P xS ( ) �
� p x p x p xS1 2( ) ( ) ( )� ñòåïåíè m mi
i
S
�
�
�
1
.  ýòîé ñèñòåìå ëþáîé ìíîãî÷ëåí F x( )
ñòåïåíè ìåíüøå m èìååò åäèíñòâåííîå ïðåäñòàâëåíèå âèäà
F x x x xS( ) ( ( ), ( ), , ( ))� � � �1 2 � , (1)
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
� Ð.Ã. Áèÿøåâ, Ñ.Å. Íûñàíáàåâà, 2012
ãäå F x x p xi i( ) ( ) ( ( ))� � mod . Ïîçèöèîííîå ïðåäñòàâëåíèå F x( ) âîññòàíàâëèâà-
åòñÿ ïî åãî íåïîçèöèîííîìó âèäó (1) [2, 3]:
F x x B xi i
i
S
( ) ( ) ( )�
�
��
1
, (2)
ãäå B x
P x
p x
M x p xi
S
i
i i( )
( )
( )
( ) ( ( ))� �1 mod .
Ìíîãî÷ëåíû M xi ( ) âûáèðàþòñÿ òàêèìè, ÷òîáû âûïîëíÿëîñü ñðàâíåíèå
â (2). Ýòà ôîðìóëà âîññòàíîâëåíèÿ F x( ) ïðèìåíÿåòñÿ ïðè îáðàáîòêå, õðàíåíèè è
ïåðåäà÷å èíôîðìàöèè. Åñëè ðàññìàòðèâàþòñÿ òîëüêî ïðîöåññû ïåðåäà÷è è õðà-
íåíèÿ íåïîçèöèîííîé èíôîðìàöèè, òî âîññòàíîâëåíèå ïîçèöèîííîãî âèäà ïîëè-
íîìà F x( ) îñóùåñòâëÿåòñÿ ïî ôîðìóëå [3–6]:
F x x P xi i
i
S
( ) ( ) ( )�
�
��
1
, (3)
ãäå P x
P x
p x
i
S
i
( )
( )
( )
� .
Ïðè ðàçðàáîòêå êðèïòîñèñòåì ýëåêòðîííîå ñîîáùåíèå äëèíîé N áèò
â ÍÏÑÑ èíòåðïðåòèðóåòñÿ êàê ïîñëåäîâàòåëüíîñòü îñòàòêîâ îò äåëåíèÿ íåêîòî-
ðîãî ìíîãî÷ëåíà (êîòîðûé îáîçíà÷èì òàêæå F x( )) ñîîòâåòñòâåííî íà ðàáî÷èå
îñíîâàíèÿ p x p x p xS1 2( ), ( ), , ( )� ñòåïåíè íå âûøå N , ò.å. â âèäå (1). Ýòè îñíîâà-
íèÿ âûáèðàþòñÿ èç ÷èñëà âñåõ íåïðèâîäèìûõ ïîëèíîìîâ ñòåïåíè îò m1 äî mS èç
óñëîâèÿ âûïîëíåíèÿ óðàâíåíèÿ [8]:
k m k m k m NS S1 1 2 2� � � �� , (4)
èç êîòîðîãî íàõîäÿòñÿ íåèçâåñòíûå êîýôôèöèåíòû k i , i S� �1 2, , , , ãäå
0 k ni i , ni — êîëè÷åñòâî âñåõ íåïðèâîäèìûõ ìíîãî÷ëåíîâ ñòåïåíè mi ,
1 m Ni , S k k kS� � � �1 2 � — ÷èñëî âûáðàííûõ ðàáî÷èõ îñíîâàíèé. Êàæ-
äîå ðåøåíèå (4) çàäàåò îäíó ñèñòåìó ïîëèíîìèàëüíûõ îñíîâàíèé. Ïîëíûå
ñèñòåìû âû÷åòîâ ïî ìîäóëÿì ìíîãî÷ëåíîâ ñòåïåíè mi âêëþ÷àþò â ñåáÿ âñå
ïîëèíîìû ñòåïåíè íå âûøå mi
1 , äëÿ çàïèñè êîòîðûõ íåîáõîäèìû mi áèò.
Ñ óâåëè÷åíèåì ñòåïåíè íåïðèâîäèìûõ ìíîãî÷ëåíîâ èõ êîëè÷åñòâî ñòðåìè-
òåëüíî âîçðàñòàåò (òàáë. 1), ñîîòâåòñòâåííî â ñâÿçè ñ ýòèì òàêæå çíà÷èòåëüíî
óâåëè÷èâàåòñÿ êîëè÷åñòâî ðåøåíèé óðàâíåíèÿ (4).
Àëãîðèòì ôîðìèðîâàíèÿ (âû÷èñëåíèÿ) ÝÖÏ äëÿ ýëåêòðîííîãî ñîîáùåíèÿ
çàäàííîé äëèíû N áèò ñîñòîèò èç òðåõ ýòàïîâ.
Ýòàï 1. Ôîðìèðóåòñÿ ÍÏÑÑ ïóòåì âûáîðà ñèñòåìû ðàáî÷èõ ïîëèíîìèàëüíûõ
îñíîâàíèé äëÿ ñîîáùåíèÿ äëèíîé N áèò â ñîîòâåòñòâèè ñ òðåáîâàíèÿìè âûïîëíåíèÿ
óðàâíåíèÿ (4). Çàòåì ïðîèçâîäèòñÿ âîññòàíîâëåíèå ôóíêöèè F x( ) ïî ôîðìóëå (3).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 15
Ñòåïåíü
íåïðèâîäèìûõ
ìíîãî÷ëåíîâ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Êîëè÷åñòâî
íåïðèâîäèìûõ
ìíîãî÷ëåíîâ
1 1 2 3 6 9 18 30 56 120 240 488 972 1938 3876 7749
Êîëè÷åñòâî
áèòîâ,
ïîêðûâàåìûõ
íåïðèâîäèìûìè
ìíîãî÷ëåíàìè
1 2 6 12 30 54 126 240 504 1200 2640 5856 12636 27132 58140 123984
Ò à á ë è ö à 1
Ýòàï 2. Îñóùåñòâëÿåòñÿ õýøèðîâàíèå ñîîáùåíèÿ äëèíîé îò N áèò äî N k
áèò ïóòåì ââåäåíèÿ èçáûòî÷íûõ (äîïîëíèòåëüíûõ èëè êîíòðîëüíûõ) îñíîâàíèé
èç ÷èñëà âñåõ íåïðèâîäèìûõ ìíîãî÷ëåíîâ ñòåïåíè íå âûøå N k è âû÷èñëåíèÿ èç-
áûòî÷íûõ âû÷åòîâ ïî ìîäóëÿì ýòèõ îñíîâàíèé. Èç ýòèõ âû÷åòîâ ñîñòàâëÿåòñÿ
õýø-çíà÷åíèå äëèíîé N k áèò.
Ýòàï 3. Øèôðîâàíèåì íàéäåííîãî õýø-çíà÷åíèÿ ïîëó÷àåì ÝÖÏ äëèíîé
N k . Äëÿ ýòîãî èñïîëüçóåòñÿ àëãîðèòì øèôðîâàíèÿ ýëåêòðîííîãî ñîîáùåíèÿ çà-
äàííîé äëèíû, ðàçðàáîòàííûé íà áàçå ÍÏÑÑ [4–6, 9].
Óñëîâèÿ âûáîðà äîïîëíèòåëüíûõ îñíîâàíèé çàâèñÿò îò ïðîöåäóðû õýøèðîâàíèÿ,
êîòîðàÿ è îïðåäåëÿåò ðàçëè÷íûå àëãîðèòìû ôîðìèðîâàíèÿ ýëåêòðîííîé ïîäïèñè.
Ïðîâåðêà ÝÖÏ îñóùåñòâëÿåòñÿ ïî ñëåäóþùåìó àëãîðèòìó. Ïðè ïîëó÷åíèè
ïîäïèñàííîãî ñîîáùåíèÿ àäðåñàò äîëæåí îñóùåñòâèòü ïðîâåðêó ÝÖÏ, ò.å. óäîñ-
òîâåðèòüñÿ â åå ïîäëèííîñòè. Äëÿ ýòîãî îí âû÷èñëÿåò äâà õýø-çíà÷åíèÿ: ïåðâîå
àäðåñàò îïðåäåëÿåò îò ïîëó÷åííîãî èì ñîîáùåíèÿ, à âòîðîå îí íàõîäèò â ðåçóëü-
òàòå ðàñøèôðîâàíèÿ ïðèêðåïëåííîé ÝÖÏ. Åñëè çíà÷åíèÿ ýòèõ õýø-çíà÷åíèé
ñîâïàäàþò, òî ïîäïèñü ïðèíèìàåòñÿ, â ïðîòèâíîì ñëó÷àå — íå ïðèíèìàåòñÿ.
 ïðåäëîæåííîì àëãîðèòìå ôîðìèðîâàíèÿ ýëåêòðîííîé ïîäïèñè íà ýòàïå
õýøèðîâàíèÿ âûáèðàåòñÿ òîëüêî îäíî èçáûòî÷íîå (êîíòðîëüíîå) îñíîâàíèå
p xS �1 ( ) èç ÷èñëà âñåõ íåïðèâîäèìûõ ìíîãî÷ëåíîâ ñòåïåíè ìåíüøå N k . Çàòåì
ôîðìèðóþòñÿ òðè èçáûòî÷íûõ âû÷åòà � S x�1 ( ), � S x� 2 ( ), � S x� 3 ( ), êîòîðûå â
ýòîì æå ïîðÿäêå ñîñòàâëÿþò õýø-çíà÷åíèå èç N k áèò. Ýòè âû÷åòû èñïîëüçóþòñÿ
íå òîëüêî äëÿ ñîçäàíèÿ ÝÖÏ, íî è äëÿ îáíàðóæåíèÿ è êîððåêöèè îäèíî÷íîé
îøèáêè è âûÿâëåíèÿ ìíîãîêðàòíîé îøèáêè.
Ïåðâûé âû÷åò — ýòî îñòàòîê ïî ìîäóëþ äîïîëíèòåëüíîãî îñíîâàíèÿ p xS �1 ( )
îò ñóììèðîâàíèÿ ïðîèçâåäåíèé ðàáî÷èõ âû÷åòîâ è èõ ïîðÿäêîâûõ íîìåðîâ
� �S i p x
i
S
x i x
S�
�
�
��1
1
1
( ) | ( )| ( )� , (5)
ãäå çíàê ñóììû �� îçíà÷àåò ïîðàçðÿäíîå ñëîæåíèå ïî ìîäóëþ 2,
| ( )| ( )i xi p xS
�
� 1
— âû÷åò ïî ìîäóëþ p x
S �1
( ) èëè âû÷åò îò äåëåíèÿ ïðîèçâåäå-
íèÿ i xi� ( ) íà èçáûòî÷íîå îñíîâàíèå p xS �1 ( ).
Âòîðîé èç äîïîëíèòåëüíûõ âû÷åòîâ îïðåäåëÿåòñÿ êàê ñóììà âñåõ ðàáî÷èõ
âû÷åòîâ ïî ìîäóëþ 2:
� �S i
i
S
x x�
�
� �2
1
( ) ( )� . (6)
Òðåòèé îñòàòîê âû÷èñëÿåòñÿ ïî ìîäóëþ äîïîëíèòåëüíîãî îñíîâàíèÿ îò ïî-
çèöèîííîãî ïðåäñòàâëåíèÿ ìíîãî÷ëåíà F x( ) ïî ôîðìóëå (3):
� �S i i p x
i
S
x x P x
S�
�
�
��3
1
1
( ) | ( ) ( )| ( )� . (7)
Êîððåêòèðóþùèå ôóíêöèè àëãîðèòìà ôîðìèðîâàíèÿ ÝÖÏ ïðåäíàçíà÷åíû
äëÿ ïðîâåðêè íàëè÷èÿ îøèáîê è èñïðàâëåíèÿ îäèíî÷íîé îøèáêè. Ïðè ðàñøèðå-
íèè ìíîãî÷ëåíà F x( ), â âèäå êîòîðîãî èíòåðïðåòèðóåòñÿ ýëåêòðîííîå ñîîáùå-
íèå, íà èçáûòî÷íûå âû÷åòû âûðàæåíèå (1) ïðèìåò âèä
F x x x x x x xj S S S( ) ( ( ), ( ), , ( ), , ( ), ( ), ( ),� � �� � � � � �1 2 1 2� � � S x� 3 ( )).
Ïðåäïîëîæèì, ÷òî ïðîèçîøëà îøèáêà â j-ì ðàáî÷åì îñíîâàíèè p xj ( ). Ïðè
íàëè÷èè îäíîé îøèáêè â èíôîðìàöèîííûõ âû÷åòàõ èçáûòî÷íûå âû÷åòû (5)–(7)
èçìåíÿò ñâîè çíà÷åíèÿ íà � S x�1
* ( ), � S x� 2
* ( ), � S x� 3
* ( ). Îøèáêà — ýòî ëþáîå èñ-
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
êàæåíèå � j x( ) ïî ìîäóëþ p xj ( ), è åå âåëè÷èíà ìîæåò áûòü ðàâíà ëþáîìó ýëå-
ìåíòó èç ïîëíîé ñèñòåìû âû÷åòîâ ïî ìîäóëþ p xj ( ), 1 j S . Òîãäà F x( )
ïðåäñòàâèòñÿ â âèäå
F x x x x x x xj S S S( ) ( ( ), ( ), , ( ), , ( ), ( ), (* *� � �� � � � � �1 2 1 2� � ), ( ))*� S x� 3 ,
ãäå � j x( ) ïðèíàäëåæèò ïîëíîé ñèñòåìå âû÷åòîâ ïî ìîäóëþ îñíîâàíèÿ p xj ( ).
Âûÿâëåíèå è êîððåêöèÿ îäèíî÷íîé îøèáêè îñóùåñòâëÿåòñÿ äâóìÿ èçáûòî÷-
íûìè âû÷åòàìè [2, 3].  ðàññìàòðèâàåìîì àëãîðèòìå äëÿ ýòîãî èñïîëüçóþòñÿ âû-
÷åòû (5) è (6). Ïóñòü � �j j jx x x( ) ( ) ( )� � � , ãäå � j x( ) — âåëè÷èíà îøèáêè. Åñëè
â õðàíèìîì èëè ïåðåäàâàåìîì ñîîáùåíèè ïðîèçîøëà îøèáêà � j x( ), òî ñèñòåìà
(5), (6) çàïèøåòñÿ â âèäå
� �
�
S i p x
i
S
j p x
S
x i x j x
S S�
�
�
� �
� ��1
1
1 1
*
( ) ( )( ) | ( )| | ( )| ,� �
2
1
* ( ) ( ) ( ),x x xi
i
S
j� �
�
�
�
�
�
� �
�� � �
(8)
ãäå � — îïåðàöèÿ ïîðàçðÿäíîãî ñëîæåíèÿ ïî ìîäóëþ 2. Âû÷èòàÿ (5) èç ïåð-
âîãî óðàâíåíèÿ (8), à (6) — èç âòîðîãî óðàâíåíèÿ (8), ïîëó÷èì
� �S S j p xx x j x
S� �� �
�1 1 1
*
( )( ) ( ) | ( )|� , � �S S jx x x� �� �2 2
* ( ) ( ) ( )� . (9)
Ââåäåì îáîçíà÷åíèÿ äëÿ íåâÿçîê, îïðåäåëÿåìûõ êàê
� � �( ) ( ) ( )*x x xS S� �� �1 1 , � � �( ) ( ) ( )*x x xS S� �� �2 2 . (10)
Òîãäà ñèñòåìó (9) ìîæíî ïåðåïèñàòü â âèäå
�( ) | ( )| ( )x j xj p xS
�
�
�
1
, �( ) ( )x xj� � . (11)
Êàê âèäíî, âåëè÷èíà îøèáêè îïðåäåëÿåòñÿ âòîðûì óðàâíåíèåì (11). Íîìåð
îøèáî÷íîãî îñíîâàíèÿ íàõîäèòñÿ èç ïåðâîãî óðàâíåíèÿ (11), â ñâÿçè ñ ýòèì âîç-
íèêàåò íåîáõîäèìîñòü îïðåäåëåíèÿ èíâåðñíîãî äëÿ � j x( ) ìíîãî÷ëåíà � j x
1 ( ).
Äëÿ ïðîâåðêè òîãî, áûëà ëè îøèáêà îäèíî÷íîé, âû÷èñëÿþòñÿ çíà÷åíèÿ âû-
÷åòà � S x� 3 ( ) äî è ïîñëå îáíàðóæåíèÿ è êîððåêöèè îøèáêè: åñëè ýòè çíà÷åíèÿ íå
ñîâïàäàþò, òî âûÿâëåííàÿ îøèáêà ÿâëÿåòñÿ ìíîãîêðàòíîé.
Ðàññìîòðèì ïðîöåññ îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê.
Ïðåäëîæåíèå 1. Êàæäîé îøèáêå � j x( ) ñîîòâåòñòâóåò îäíà ïàðà íåâÿçîê
�( )x , �( )x .
Ïðåäïîëîæèì îáðàòíîå, ò.å. îäíîé îøèáêå � j x( ) ñîîòâåòñòâóþò äâå ïàðû
íåâÿçîê � �( ), ( )x x è �� ( )x , �� ( )x . Òîãäà, êðîìå ñèñòåìû (11), áóäåò èìåòü ìåñòî
òàêæå è ñèñòåìà
� �
�
� ( ) | ( )| ( )x j xj p xS
�
1
, � �� ( ) ( )x xj� . (12)
Ïðè âû÷èòàíèè (11) èç (12) ïîëó÷èì, ÷òî � � �� �( ) ( )x x 0, � � �� �( ) ( )x x 0 , îò-
êóäà ñëåäóåò, ÷òî � �� �( ) ( )x x è � �� �( ) ( )x x . Òàêèì îáðàçîì, ïðåäïîëîæåíèå î
òîì, ÷òî îäíîé îøèáêå ñîîòâåòñòâóþò äâå ïàðû íåâÿçîê, îêàçàëîñü íåâåðíûì.
Ïðåäëîæåíèå 2. Êàæäîé ïàðå íåâÿçîê �( )x , �( )x ñîîòâåòñòâóåò îäíà îøèáêà
� j x( ).
Äîïóñòèì ïðîòèâîïîëîæíîå. Ïóñòü îäíîé ïàðå íåâÿçîê �( )x , �( )x ñîîòâåòñòâó-
þò äâå îøèáêè, íàïðèìåð, � j x( ) è � t x( ) ñîîòâåòñòâåííî ïî îñíîâàíèÿì p xj ( ) è
p xt ( ).  ýòîì ñëó÷àå ïîëó÷èì, êðîìå ñèñòåìû (11), åùå îäíó ñèñòåìó
�( ) | ( )| ( )x t xt p xS
�
�
�
1
, �( ) ( )x xt� � . (13)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 17
Âû÷òåì (11) èç (13), ðåçóëüòàòîì áóäåò ñèñòåìà
0
1
� �
�
| ( ) ( )| ( )t x j xt j p xS
� � , 0 � �� �t jx x( ) ( ), (14)
îòêóäà ñëåäóåò, ÷òî � �t jx x( ) ( )� . Òîãäà èç ïåðâîãî óðàâíåíèÿ (14) âûòåêàåò,
÷òî | ( ) ( )| ( )t j xj p xS
�
�
�
1
0. Òàê êàê � j x( ) � 0, òî t j� , à ýòî îçíà÷àåò, ÷òî äî-
ïóùåíèå áûëî íåâåðíûì.
Äëÿ òîãî ÷òîáû àëãîðèòì îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê óäîâëåòâîðÿë
ïðåäëîæåíèÿì 1 è 2, äîëæíî âûïîëíÿòüñÿ óñëîâèå èçîìîðôíîñòè ìíîæåñòâà
îøèáîê è ìíîæåñòâà íåâÿçîê: îáùåå ÷èñëî îøèáîê íå ìîæåò ïðåâûøàòü îáùåãî
êîëè÷åñòâà âñåõ íåâÿçîê. Ïîñêîëüêó èçáûòî÷íûå âû÷åòû � S x�1 ( ), � S x� 2 ( ),
� S x� 3 ( ) îïðåäåëÿþòñÿ ïî îäíîìó èçáûòî÷íîìó îñíîâàíèþ p xS �1 ( ), óêàçàííîå
óñëîâèå èçîìîðôíîñòè íàêëàäûâàåò îïðåäåëåííîå îãðàíè÷åíèå íà âûáîð ýòîãî
äîïîëíèòåëüíîãî îñíîâàíèÿ.
Ïðåäëîæåíèå 3. Âûáîð èçáûòî÷íîãî îñíîâàíèÿ çàâèñèò îò èñïîëüçóåìîé
ñèñòåìû ïîëèíîìèàëüíûõ ðàáî÷èõ îñíîâàíèé è èõ êîëè÷åñòâà.
Ïîêàæåì ýòî. Ââåäåì îáîçíà÷åíèå | | | | ( )� p xi
— ÷èñëî ýëåìåíòîâ â ïîëíîé
ñèñòåìå âû÷åòîâ ïî ìîäóëþ îñíîâàíèÿ p xi ( ), i S� � �1 2 1, , , . Óïîðÿäî÷èì (äëÿ
óäîáñòâà èçëîæåíèÿ) ðàñïîëîæåíèå ðàáî÷èõ îñíîâàíèé â ïîðÿäêå óâåëè÷åíèÿ
èõ ñòåïåíåé m m mS1 2 � , ò.å. çäåñü è äàëåå m1 — íàèìåíüøàÿ èõ ñòåïåíü,
à mS — íàèáîëüøàÿ. Òîãäà äëÿ ïîëíûõ ñèñòåì âû÷åòîâ ïî ìîäóëÿì ðàáî÷èõ
îñíîâàíèé ìîæíî çàïèñàòü
| | | | | | | | | | | |( ) ( ) ( )� � �p x p x p xS1 2
�
èëè
2 2 21 2m m mS � . (15)
Îáùåå ÷èñëî îøèáîê åñòü ñóììà ýëåìåíòîâ ïîëíûõ ñèñòåì âû÷åòîâ ïî âñåì
îñíîâàíèÿì. ×èñëî âñåõ íåâÿçîê îïðåäåëÿåòñÿ ïðîèçâåäåíèåì ÷èñëà ýëåìåíòîâ
ïîëíîé ñèñòåìû âû÷åòîâ ïî ìîäóëþ èçáûòî÷íîãî îñíîâàíèÿ è êîëè÷åñòâà ýëå-
ìåíòîâ ïîëíîé ñèñòåìû âû÷åòîâ ïî ìîäóëþ èíôîðìàöèîííîãî îñíîâàíèÿ íàè-
áîëüøåé ñòåïåíè | | | | | | | |( ) ( )� �p x p xS S�
�
1
, ÷òî ñëåäóåò èç (11). Òîãäà òðåáóåìîå
óñëîâèå îãðàíè÷åíèÿ íà èçáûòî÷íîå îñíîâàíèå p xS �1 ( ) çàïèøåòñÿ â âèäå
íåðàâåíñòâà
� | | | | | | | | | | | |( ) ( ) ( )� � �p x p x
i
S
p xi S S
�
�
�
� 1
1
. (16)
Ðàñïèñûâàÿ (16) ñ èñïîëüçîâàíèåì ÷èñëà ýëåìåíòîâ â ïîëíîé ñèñòåìå âû÷å-
òîâ, ïîëó÷èì
� 2 2 2
1
1m
i
S
m mi S S
�
� � . (17)
Òîãäà èç âûðàæåíèÿ (17) ñ ó÷åòîì (15) ñëåäóåò, ÷òî
2 1 1m m mS S S� �
� . (18)
Òàêèì îáðàçîì, äîêàçàíî: íåðàâåíñòâî (18) îïðåäåëÿåò óñëîâèÿ âûáîðà ñòå-
ïåíè èçáûòî÷íîãî îñíîâàíèÿ â îáùåì ñëó÷àå è õàðàêòåðèçóåò åå çàâèñèìîñòü îò
íàèáîëüøåé è íàèìåíüøåé ñòåïåíåé êîíêðåòíîé ñèñòåìû ðàáî÷èõ îñíîâàíèé è
èõ êîëè÷åñòâà S .
Ðàññìîòðèì íåêîòîðûå ÷àñòíûå ñëó÷àè âûáîðà èçáûòî÷íîãî îñíîâàíèÿ.
Ñëó÷àé 1. Ïóñòü âñå îñíîâàíèÿ, ðàáî÷èå è äîïîëíèòåëüíîå, p x p x1 2( ), ( ),�
� , ( ), ( )p x p xS S �1 èìåþò îäèíàêîâûå ñòåïåíè m m m mS S1 2 1� � � � �� . Òîãäà
èç íåðàâåíñòâà (18) ïîëó÷èì âûðàæåíèå
2 1mS S� � , (19)
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
ïîêàçûâàþùåå, ÷òî êîëè÷åñòâî ýëåìåíòîâ â ïîëíîé ñèñòåìå âû÷åòîâ ïî ìîäó-
ëþ èçáûòî÷íîãî îñíîâàíèÿ äîëæíî áûòü íå ìåíüøå ÷èñëà âñåõ èíôîðìàöèîí-
íûõ îñíîâàíèé S .
Ïðèìåð 1. Âûáåðåì â êà÷åñòâå âñåõ îñíîâàíèé (ðàáî÷èõ è èçáûòî÷íîãî)
30 íåïðèâîäèìûõ ìíîãî÷ëåíîâ âîñüìîé ñòåïåíè. Åñëè âñå èõ èñïîëüçîâàòü â êà-
÷åñòâå îñíîâàíèé, òî ðàáî÷èõ áóäåò 29, à 30-å îñíîâàíèå — èçáûòî÷íûì. Ïîä-
ñòàâëÿÿ â (19) S � 29, mi � 8, ïîëó÷èì 2 298 � , 256 29� , ÷òî îçíà÷àåò, ÷òî äëÿ ýòî-
ãî íàáîðà îñíîâàíèé óñëîâèå (19) âûïîëíÿåòñÿ. Ïðè ýòîì âûðàæåíèå (19) ïðà-
âèëüíî äëÿ ìàêñèìàëüíîãî çíà÷åíèÿ S � 29, ñëåäîâàòåëüíî, îíî áóäåò
ñïðàâåäëèâî è ïðè ìåíüøèõ çíà÷åíèÿõ êîëè÷åñòâà S ðàáî÷èõ îñíîâàíèé.
Ñëó÷àé 2. Ðàññìîòðèì åùå îäèí âàðèàíò âûáîðà îñíîâàíèé, êîãäà âñå ðàáî-
÷èå îñíîâàíèÿ èìåþò îäíó ñòåïåíü, à ñòåïåíü êîíòðîëüíîãî îñíîâàíèÿ mS �1 îò-
ëè÷àåòñÿ îò íåå. Òîãäà èç (18) ïîëó÷èì íåðàâåíñòâî (19).
Ïî ðåçóëüòàòàì ïðåäûäóùåãî ñëó÷àÿ (êîãäà âñå îñíîâàíèÿ èìåþò îäíó ñòå-
ïåíü) ñëåäóåò, ÷òî åñëè èçáûòî÷íîå îñíîâàíèå èìååò ñòåïåíü íå ìåíüøå ñòåïåíè
ðàáî÷èõ îñíîâàíèé, òî óñëîâèå (19) âûïîëíÿåòñÿ.
Ðàññìîòðèì ñëó÷àé, êîãäà èçáûòî÷íîå îñíîâàíèå èìååò ñòåïåíü ìåíüøóþ
íàèáîëüøåé ñòåïåíè ðàáî÷èõ îñíîâàíèé mS .
Ïðåäëîæåíèå 4. Ñòåïåíü èçáûòî÷íîãî îñíîâàíèÿ mS �1 äîëæíà áûòü íå
ìåíüøå íàèáîëüøåé ñòåïåíè ðàáî÷èõ îñíîâàíèé mS .
Êàê óêàçûâàëîñü ðàíåå, îøèáêà — ýòî ëþáîå èñêàæåíèå âû÷åòà � j x( ) ïî
ìîäóëþ p xj ( ), è åå âåëè÷èíà ìîæåò áûòü ðàâíà ëþáîìó ýëåìåíòó èç ïîëíîé ñèñ-
òåìû âû÷åòîâ ïî ìîäóëþ p xj ( ). Ïðåäïîëîæèì, ÷òî èçáûòî÷íîå îñíîâàíèå èìååò
ñòåïåíü m mS S�
�
1
, à îøèáêà ïðîèçîøëà ïî ðàáî÷åìó îñíîâàíèþ, ñòåïåíü êîòî-
ðîãî áîëüøå mS �1. Òîãäà îøèáêà (âû÷åò) ìîæåò ñîâïàñòü ñ èçáûòî÷íûì îñíîâà-
íèåì.  ýòîì ñëó÷àå íåâîçìîæíî îïðåäåëèòü ìåñòîïîëîæåíèå îøèáêè èç (11),
ò.å. íîìåð îøèáî÷íîãî îñíîâàíèÿ èç âûðàæåíèÿ
j x x x xj j p x j j xS j
� �
�
| ( ) ( )| | ( ) ( )|( ) ( )� � � � �
1 1
1
.
Èç ýòîãî ñëåäóåò, ÷òî ÷èñëî ýëåìåíòîâ ïîëíîé ñèñòåìû âû÷åòîâ ïî ìîäóëþ
èçáûòî÷íîãî îñíîâàíèÿ p xS �1 ( ) íå äîëæíî áûòü ìåíüøå êîëè÷åñòâà ýëåìåí-
òîâ ïîëíîé ñèñòåìû âû÷åòîâ ïî ìîäóëþ ðàáî÷åãî îñíîâàíèÿ p xS ( ):
m mS S� �1 . (20)
Òàêèì îáðàçîì, ïðè ôîðìèðîâàíèè ÝÖÏ ïî ïðåäñòàâëåííîìó àëãîðèòìó èç-
áûòî÷íîå îñíîâàíèå âûáèðàåòñÿ òàêèì, ÷òîáû âûïîëíÿëèñü îäíîâðåìåííî äâà
íàëàãàåìûõ íà íåãî óñëîâèÿ (18) è (20).
Îøèáêè ìîãóò ïðîèçîéòè íå òîëüêî ïî ðàáî÷èì âû÷åòàì. Ðàññìîòðèì âîç-
ìîæíûå âàðèàíòû îøèáîê ïî êîíòðîëüíûì âû÷åòàì.
Îøèáî÷íûì ÿâëÿåòñÿ îäèí èç äâóõ ïåðâûõ âû÷åòîâ: � S x�1 ( ) è � S x� 2 ( ).
Ïðè ïðîâåðêå ÝÖÏ íåâÿçêà ïî îøèáî÷íîìó âû÷åòó îêàæåòñÿ îòëè÷íîé îò íóëÿ,
äðóãèå äâå íåâÿçêè áóäóò ðàâíû íóëþ. Ïîñëå ïðîâåðêè ÝÖÏ îøèáî÷íûé âû÷åò
èñïðàâëÿåòñÿ çàìåíîé âíîâü âû÷èñëåííûì. Åñëè â ýòîì ñëó÷àå îøèáêà ïðîèçîø-
ëà òàêæå è â òðåòüåì êîíòðîëüíîì âû÷åòå � S x� 3 ( ), òî îøèáî÷íûå âû÷åòû çàìå-
íÿþòñÿ âíîâü âû÷èñëåííûìè.
Îøèáî÷íûìè ÿâëÿþòñÿ îáà ïåðâûõ âû÷åòà: � S x�1 ( ) è � S x� 2 ( ). Ïîñêîëü-
êó ïî ýòèì âû÷åòàì îáå íåâÿçêè îòëè÷íû îò íóëÿ, ïîëó÷àåì âàðèàíò íàëè÷èÿ îøèá-
êè, êîòîðàÿ ïðîèçîøëà â èíôîðìàöèîííîì ñèìâîëå ñîîáùåíèÿ. Èñõîäÿ èç ýòîãî
èùåì îøèáêó êàê îäèíî÷íóþ ïî èíôîðìàöèîííîìó îñíîâàíèþ. Îøèáî÷íûé âû÷åò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 19
ìîæíî âûÿâèòü è èñïðàâèòü, ò.å. ïðàâèëüíûé âû÷åò çàìåíèòü íà íåâåðíûé è òàêèì
îáðàçîì âíåñòè òðåòüþ îøèáêó. Çàâåðøàåì ïðîâåðêó âû÷èñëåíèåì òðåòüåãî äîïîë-
íèòåëüíîãî âû÷åòà � S x� 3 ( ), êîòîðàÿ ïîêàæåò, ÷òî íåâÿçêà ïî âû÷åòó � S x� 3 ( ) íå
áóäåò ðàâíà íóëþ. Ñëåäîâàòåëüíî, îøèáêà â ñîîáùåíèè íå îäèíî÷íà.
Íåâåðíûìè ìîãóò îêàçàòüñÿ âñå òðè èçáûòî÷íûõ âû÷åòà � S x�1 ( ), � S x� 2 ( ) è
� S x� 3 ( ).  ýòîì ñëó÷àå ïîñòóïàåì òàêæå.
Ïðè ôîðìèðîâàíèè ÝÖÏ åå äëèíà N k äîëæíà áûòü ñóùåñòâåííî ìåíüøå
äëèíû N ýëåêòðîííîãî ñîîáùåíèÿ, ò.å. N Nk �� .  ðàññìàòðèâàåìîì àëãîðèòìå
äëèíà ïîäïèñè ôîðìèðóåòñÿ òðåìÿ èçáûòî÷íûìè âû÷åòàìè � S x�1 ( ), � S x� 2 ( ) è
� S x� 3 ( ). Äëÿ çàïèñè êàæäîãî èç âû÷åòîâ � S x�1 ( ) è � S x� 2 ( ) ïî ìîäóëþ èçáû-
òî÷íîãî îñíîâàíèÿ p xS �1 ( ) íåîáõîäèìî mS �1 áèò, à äëÿ çàïèñè âû÷åòà � S x� 3 ( )
íåîáõîäèìî mS áèò. Ïîýòîìó äëèíà ÝÖÏ îãðàíè÷åíà óñëîâèåì
N m m Nk S S� � ��2 1 . (21)
Òîãäà ñòåïåíü èçáûòî÷íîãî âû÷åòà îïðåäåëÿåòñÿ íåðàâåíñòâîì
( ) / ( ) /N m m N mk S S S
� �
�2 21 . (22)
Èç (20) è (21) ñëåäóåò åùå îäíî îãðàíè÷åíèå íà äëèíó ÝÖÏ è ñòåïåíü p xS �1 ( )
3 3 1m N m NS k S� � �� . (23)
Êàê ïîêàçàíî âûøå, âûáîð êîíòðîëüíîãî îñíîâàíèÿ p xS �1 ( ) çàâèñèò îò íàè-
áîëüøåé ñòåïåíè mS èíôîðìàöèîííûõ îñíîâàíèé. Ñóùåñòâóåò îïðåäåëåííîå
êîëè÷åñòâî âñåõ âîçìîæíûõ ñèñòåì ðàáî÷èõ îñíîâàíèé, ïîêðûâàþùèõ ïîäïèñû-
âàåìîå ñîîáùåíèå äëèíîé N è èñïîëüçóåìûõ äëÿ ôîðìèðîâàíèÿ ÝÖÏ. Â êàæäîé
èç ýòèõ ñèñòåì èìååòñÿ ñâîå íàèáîëüøåå çíà÷åíèå èõ ñòåïåíè. Ïîýòîìó ïðè ïîä-
ïèñûâàíèè íåêîòîðîãî ýëåêòðîííîãî ñîîáùåíèÿ äëèíîé N ñòåïåíü mS ïðèíèìà-
åò çíà÷åíèÿ èç êîíêðåòíîãî äèàïàçîíà âîçìîæíûõ íàèáîëüøèõ ñòåïåíåé. Òîãäà,
êàê ñëåäóåò èç âûðàæåíèé (22) è (23), ïî îïèñàííîìó àëãîðèòìó ìîæíî ñôîðìè-
ðîâàòü íåñêîëüêî ÝÖÏ ñ ðàçëè÷íûìè äëèíàìè N k , k K� �1 2, , , , ãäå K — ÷èñëî
âñåõ öèôðîâûõ ïîäïèñåé, êîòîðûå ìîãóò áûòü ïîëó÷åíû äëÿ ñîîáùåíèÿ äëèíîé N .
Ïðåäëîæåíèå 5. Êðèïòîñòîéêîñòü íåòðàäèöèîííîãî àëãîðèòìà ôîðìèðîâà-
íèÿ ÝÖÏ ïî ìîäóëþ îäíîãî èçáûòî÷íîãî îñíîâàíèÿ îïðåäåëÿåòñÿ ÷èñëîì âñå-
âîçìîæíûõ ñïîñîáîâ âûáîðà îñíîâàíèé íà âñåõ ýòàïàõ àëãîðèòìà ôîðìèðîâàíèÿ
ÝÖÏ: ñèñòåìû ðàáî÷èõ îñíîâàíèé èç ìíîæåñòâà íåïðèâîäèìûõ ìíîãî÷ëåíîâ
ñòåïåíè íå âûøå N , èçáûòî÷íîãî îñíîâàíèÿ èç ìíîæåñòâà íåïðèâîäèìûõ ìíî-
ãî÷ëåíîâ ñòåïåíè íå âûøå N k ñ ó÷åòîì âñåõ îãðàíè÷åíèé íà åãî âûáîð è ïîëíî-
ãî êëþ÷à äëÿ øèôðîâàíèÿ õýø-çíà÷åíèÿ äëèíîé N k .
Ïîêàæåì ýòî.
1. Âûáîð îäíîé ñèñòåìû ðàáî÷èõ îñíîâàíèé p x p x p xS1 2( ), ( ), , ( )� ñòåïå-
íåé îò m1 äî mS îãðàíè÷åí óñëîâèåì, îïèñûâàåìûì óðàâíåíèåì (4), ñ ó÷åòîì
âñåõ ïåðåñòàíîâîê ðàáî÷èõ îñíîâàíèé. ×èñëî ðàçëè÷íûõ êîìáèíàöèé âûáîðà
îñíîâàíèé äëÿ êàêîé-ëèáî îäíîé ñòåïåíè îïðåäåëÿåòñÿ k i -ñî÷åòàíèÿìè èç âñåõ
ni íåïðèâîäèìûõ ìíîãî÷ëåíîâ ñòåïåíè mi . Ïðè âûáîðå mS äîëæíî ó÷èòûâàòüñÿ
óñëîâèå (23).  íåïîçèöèîííûõ ñèñòåìàõ ñ÷èñëåíèÿ ñóùåñòâåíåí è ïîðÿäîê ðàñ-
ïîëîæåíèÿ îñíîâàíèé, ïîýòîìó ÷èñëî ñèñòåì èç S âûáðàííûõ îñíîâàíèé áóäåò
Z k k k C C Cs n
k
n
k
n
k
S
S
1 1 2
1
1
2
2� � � �( )!� � . (24)
2. Êîëè÷åñòâî ñïîñîáîâ âûáîðà îäíîãî èçáûòî÷íîãî îñíîâàíèÿ p xS �1 ( ) ðàâ-
íî ÷èñëó nS �1 âñåõ íåïðèâîäèìûõ ìíîãî÷ëåíîâ ñòåïåíè mS �1:
Z C n
n S
S
2
1
1
1
� �
�
� . (25)
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Òîãäà âñå ñïîñîáû âûáîðà äîïîëíèòåëüíîãî îñíîâàíèÿ äëÿ îäíîé êîíêðåòíîé
ñèñòåìû ðàáî÷èõ îñíîâàíèé ðàâíî ïðîèçâåäåíèþ Z Z1 2 .
3. Øèôðîâàíèå õýø-çíà÷åíèÿ äëèíîé N k îñóùåñòâëÿåòñÿ íåòðàäèöèîííûì
àëãîðèòìîì øèôðîâàíèÿ, âêëþ÷àþùèì ôîðìèðîâàíèå ÍÏÑÑ (âûáîð ñèñòåìû
îñíîâàíèé ñòåïåíè íå âûøå N k ñ ó÷åòîì ïîðÿäêà èõ ðàñïîëîæåíèÿ) è ãåíåðàöèþ
êëþ÷åâîé (ïñåâäîñëó÷àéíîé) ïîñëåäîâàòåëüíîñòè [9]. Âñå îñíîâàíèÿ (ðàáî÷èå è
äëÿ øèôðîâàíèÿ õýø-çíà÷åíèÿ), èñïîëüçóåìûå íà ýòàïàõ 1 è 3 àëãîðèòìà ïî-
ñòðîåíèÿ öèôðîâîé ïîäïèñè, âûáèðàþòñÿ íåçàâèñèìî äðóã îò äðóãà, íî ñðåäè
íèõ ìîãóò áûòü è ñîâïàäàþùèå.
Âûáîð ñèñòåìû îñíîâàíèé r x r x r xW1 2( ), ( ), , ( )� äëÿ øèôðîâàíèÿ õýø-çíà÷å-
íèÿ îñóùåñòâëÿåòñÿ èç ÷èñëà íåïðèâîäèìûõ ìíîãî÷ëåíîâ ñ äâîè÷íûìè êîýôôè-
öèåíòàìè ñòåïåíè íå âûøå N k . Òîãäà õýø-çíà÷åíèå äëèíîé N k èíòåðïðåòèðóåò-
ñÿ êàê ïîñëåäîâàòåëüíîñòü îñòàòêîâ � � �1 2( ), ( ), ..., ( )x x xW îò äåëåíèÿ íåêîòîðîãî
ìíîãî÷ëåíà F x1 ( ) íà âûáðàííûå îñíîâàíèÿ r x r x r xW1 2( ), ( ), , ( )� ñîîòâåòñòâåííî
F x x x xW1 1 2( ) ( ( ), ( ), ..., ( ))� � � � , (26)
ãäå F x x r xj j1 ( ) ( ) ( ( ))� � mod , j W�1, .
Êëþ÷åâàÿ ïîñëåäîâàòåëüíîñòü ãåíåðèðóåòñÿ äëèíîé N k è èíòåðïðåòèðóåòñÿ
êàê ïîñëåäîâàòåëüíîñòü îñòàòêîâ � � �1 2( ), ( ), ..., ( )x x xW îò äåëåíèÿ íåêîòîðîãî
ïîëèíîìà G x1 ( ) íà òå æå îñíîâàíèÿ r x r x r xW1 2( ), ( ), , ( )� :
G x x x xW1 1 2( ) ( ( ), ( ), ..., ( ))� � � � , (27)
ïðè ýòîì G x x xj j1 ( ) ( ) ( ( ))� � mod r , j W�1, .
Òîãäà ïîëó÷åííóþ â ðåçóëüòàòå øèôðîâàíèÿ êðèïòîãðàììó � �1 2( ), ( ),x x �
� , ( )�W x ìîæíî ïðåäñòàâèòü êàê íåêîòîðóþ ôóíêöèþ H F x G x1 1 1( ( ), ( )):
H x x x xW1 1 2( ) ( ( ), ( ), , ( ))� � � �� , (28)
ïðè ýòîì H x x r xj j1 ( ) ( ) ( ( ))� � mod , j W�1, .
Îïåðàöèè â ôóíêöèÿõ (26)–(28) â ñîîòâåòñòâèè ñ îïåðàöèÿìè íåïîçèöèîííîé
ñèñòåìû ñ÷èñëåíèÿ âûïîëíÿþòñÿ ïàðàëëåëüíî ïî ìîäóëÿì ìíîãî÷ëåíîâ
r x r x r xW1 2( ), ( ), , ( )� , âûáðàííûõ â êà÷åñòâå îñíîâàíèé.
Îáîçíà÷èì ñòåïåíè è ÷èñëî íåïðèâîäèìûõ ìíîãî÷ëåíîâ, èñïîëüçóåìûõ ïðè
âûáîðå îñíîâàíèé r x r x r xW1 2( ), ( ), , ( )� , ñîîòâåòñòâåííî b b bW1 2, , ,� è
l l lW1 2, , ,� . Èç óðàâíåíèÿ (àíàëîãà (4))
v b v b v b NW W k1 1 2 2� � � �� , (29)
ãäå 0 v li i — íåèçâåñòíûå êîýôôèöèåíòû, 1 b Nj k , W v v vW� � � �1 2 � ,
íàõîäÿòñÿ W îñíîâàíèé, çàïèñü âû÷åòîâ ïî êîòîðûì ïîêðûâàåò øèôðóåìîå
õýø-çíà÷åíèå äëèíîé N k .
Òîãäà êîëè÷åñòâî êîìáèíàöèé ïîëíûõ êëþ÷åé ïðè øèôðîâàíèè õýø-çíà÷å-
íèÿ (âûáîð îäíîé ñèñòåìû èç W îñíîâàíèé è êëþ÷à, ðàñïðåäåëåíèå îñíîâàíèé â
ñèñòåìå) îïðåäåëèòñÿ ñîîòíîøåíèåì
� � � � �Z C C C
N
W l l l
k
W
W
3 1 22
1
1
2
2( )!� � �
� � �
� � .
Âñå âàðèàíòû âûáîðà ðàçëè÷íûõ ñèñòåì îñíîâàíèé è êëþ÷à ïîëó÷èì èç
âûðàæåíèÿ
Z C C C
N
W l l l
k
W
W
3 1 22
1
1
2
2� � � �� ( )!
, , ,
� � �
� � �
� � �
� �
�1 2 W
. (30)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 21
 (30) ñóììèðîâàíèå ïðîâîäèòñÿ ïî âñåì âîçìîæíûì êîìáèíàöèÿì öåëûõ
ïîëîæèòåëüíûõ ÷èñåë � � �1 2, , ,� W , óäîâëåòâîðÿþùèõ óðàâíåíèþ (29), ò.å. ïî
âñåì âîçìîæíûì êîìáèíàöèÿì W îñíîâàíèé èç îáùåãî ÷èñëà íåïðèâîäèìûõ
ìíîãî÷ëåíîâ ñòåïåíè b b bW1 2, , ,� .
Äëÿ îäíîé ñèñòåìû ðàáî÷èõ îñíîâàíèé ïðè êîíêðåòíûõ çíà÷åíèÿõ mS è
mS �1 âñå ñïîñîáû ôîðìèðîâàíèÿ ïðîâåðÿþùåé ïîäïèñè áóäóò îïðåäåëÿòüñÿ
ïðîèçâåäåíèåì Z Z Z1 2 3 . Òîãäà âñåâîçìîæíûå âàðèàíòû ôîðìèðîâàíèÿ ÝÖÏ
äëèíîé N k äîëæíû ó÷èòûâàòü âñå ñèñòåìû ðàáî÷èõ îñíîâàíèé, îïðåäåëÿåìûõ
óðàâíåíèåì (4), ò.å. îïèñûâàòüñÿ ôîðìóëîé
Z Z Z Zk
k k k
� � 1 2 3
1 2 S, , ,�
. (31)
Âñå ñïîñîáû ôîðìèðîâàíèÿ ÝÖÏ ñ ïðîâåðÿþùèìè ôóíêöèÿìè äëÿ ñîîáùåíèÿ
îäíîé îïðåäåëåííîé äëèíû N åñòü ñóììà âñåõ Zk èç (31)
Z Zk
k
K
�
�
�
1
.
(32)
Òîãäà îáðàòíàÿ âåëè÷èíà (32) îïðåäåëÿåò êðèïòîñòîéêîñòü àëãîðèòìà ôîðìè-
ðîâàíèÿ ïîäïèñè ñ êîððåêòèðóþùèìè ñâîéñòâàìè
p n k k k C C
N
k
K
S
k k k
s n
k
n
k
S
sig � � � �
�
�� �1 2
1
1 1 2
1 2
1
1/ ( )!
, , ,�
�
2
2k
n
k
C
S
S... �
�
�
�
�
�
�
�
�
� � � �
�
�
�
�
!
"
"
� ( )!
, , ,
� � �
� � �
� � �
1 2
1
1
2
2
� �
�
W l l l
C C C
W
W
1 2 W
. (33)
Òàêèì îáðàçîì, ïîëíûé êëþ÷ àëãîðèòìà îïðåäåëÿåòñÿ ïðîöåäóðàìè âûáîðà
îñíîâàíèé íà êàæäîì èç ýòàïîâ ôîðìèðîâàíèÿ öèôðîâîé ïîäïèñè.
Ðàññìîòðèì ïðèìåðû îïðåäåëåíèÿ êðèïòîñòîéêîñòè ÝÖÏ.
Ïðèìåð 2. Ïóñòü ÝÖÏ ñîçäàåòñÿ äëÿ ñîîáùåíèÿ äëèíîé 16 áèò. Â ýòîì ñëó-
÷àå ìèíèìàëüíîå çíà÷åíèå íàèáîëüøåé ñòåïåíè èíôîðìàöèîííûõ îñíîâàíèé
mS � 4, òàê êàê ïðè ìåíüøèõ åãî çíà÷åíèÿõ íå ñóùåñòâóåò ñèñòåì ðàáî÷èõ îñíî-
âàíèé, ïîêðûâàþùèõ 16 áèò. Èç íåðàâåíñòâà (20) ñëåäóåò, ÷òî âîçìîæíû äâà âà-
ðèàíòà çíà÷åíèé mS , äëÿ êîòîðûõ ïîëó÷àåì ñëåäóþùèå îãðàíè÷åíèÿ íà êîí-
òðîëüíîå îñíîâàíèå mS �1: 1) mS � 4, mS � 1 6; 2) mS � 5, mS � 1 5. Â ñâÿçè
ñ ýòèì ïðè ïîñòðîåíèè öèôðîâîé ïîäïèñè â ñîîòâåòñòâèè ñ óðàâíåíèåì (4) ìîãóò
áûòü ñôîðìèðîâàíû äâå ñèñòåìû ðàáî÷èõ îñíîâàíèé ïðè mS � 4, è øåñòü ñèñòåì
ïðè mS � 5. Ñîñòàâ ýòèõ âîñü-
ìè ñèñòåì îñíîâàíèé ïðèâåäåí
â ñòðîêàõ òàáë. 2. Òàê, ñèñòåìà
ðàáî÷èõ îñíîâàíèé ïîä íîìå-
ðîì 1 âêëþ÷àåò íåïðèâîäèìûå
ìíîãî÷ëåíû 1-é, 3-é è 4-é ñòå-
ïåíè, êîëè÷åñòâî êîòîðûõ ðàâ-
íî ñîîòâåòñòâåííî 1, 1 è 3.
Äîïóñòèìûìè ÿâëÿþòñÿ
óêàçàííûå äàëåå âàðèàíòû
çíà÷åíèé èçáûòî÷íîãî îñíî-
âàíèÿ mS �1 è äëèí ÝÖÏ:
1) mS � 4, mS � �1 4, N1 = 12;
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
Íîìåð
èñïîëüçóåìûõ
ñèñòåì ðàáî÷èõ
îñíîâàíèé
Ñòåïåíü íåïðèâîäèìûõ ìíîãî÷ëåíîâ,
âûáðàííûõ â êà÷åñòâå ðàáî÷èõ
îñíîâàíèé
1 2 3 4 5
1 1 — 1 3 —
2 — 1 2 2 —
3 1 — — — 3
4 — 1 — 1 2
5 1 1 1 — 2
6 — — 1 2 1
7 1 1 — 2 1
8 1 — 2 1 1
Ò à á ë è ö à 2
2) mS � 4, mS � �1 5, N 2 = 14; 3) mS � 5, mS � �1 5, N 4 = 15. Â ðåçóëüòàòå ïî ôîð-
ìóëå (33) ïîëó÷èì ñëåäóþùóþ âåëè÷èíó êðèïòîñòîéêîñòè: psig #
10 13 .
Ïðèìåð 3. Ñîîáùåíèå èìååò äëèíó 256 áàéò èëè 2048 áèò. Îïðåäåëèì
êðèïòîñòîéêîñòü ïðîâåðÿþùåé ïîäïèñè ïðè âûáîðå îäíîé ñèñòåìû èíôîðìàöè-
îííûõ îñíîâàíèé.
Ïóñòü â êà÷åñòâå ñèñòåìû âûáðàíû 80 ìíîãî÷ëåíîâ 16-é ñòåïåíè, 60 ìíî-
ãî÷ëåíîâ 12-é ñòåïåíè è 6 ìíîãî÷ëåíîâ 8-é ñòåïåíè. Òîãäà S �146 è
Z1
5295 10# � . Êîíòðîëüíûì îñíîâàíèåì âûáåðåì íåïðèâîäèìûé ìíîãî÷ëåí 16-é
ñòåïåíè: Z2 7749� .  ðåçóëüòàòå õýøèðîâàíèÿ ïîëó÷èì õýø-çíà÷åíèå äëèíîé
48 áèò. Äëÿ åãî øèôðîâàíèÿ ôîðìèðóåì ñèñòåìó èç òðåõ îñíîâàíèé 16-é ñòåïå-
íè, W � 3.  ðåçóëüòàòå ïîëó÷èì psig #
10 560 .
Êàê âèäíî èç âûøåèçëîæåííîãî, ïðè èñïîëüçîâàííîì ïîäõîäå äëèíà è íà-
äåæíîñòü ôîðìèðóåìîé ïîäïèñè îïðåäåëÿþòñÿ äëèíîé ïîäïèñûâàåìîãî ñîîáùå-
íèÿ, âûáîðîì ñèñòåìû ðàáî÷èõ îñíîâàíèé è èçáûòî÷íîãî îñíîâàíèÿ, à åå êðèï-
òîñòîéêîñòü ìîæåò äîñòèãàòü âûñîêèõ çíà÷åíèé.  íàñòîÿùåå âðåìÿ ïðîãðàì-
ìíûå ðåàëèçàöèè êðèïòîãðàôè÷åñêèõ àëãîðèòìîâ çàùèòû èíôîðìàöèè ìîãóò
óñïåøíî ñîïåðíè÷àòü ñ òðàäèöèîííûìè àïïàðàòíûìè ñðåäñòâàìè. Ïðèìåíåíèå
ÍÏÑÑ ïîçâîëÿåò ñîçäàâàòü ýôôåêòèâíûå êðèïòîãðàôè÷åñêèå ñðåäñòâà ïîâûøåí-
íîé íàäåæíîñòè, êîòîðûå îáåñïå÷èâàþò êîíôèäåíöèàëüíîñòü, àóòåíòèôèêàöèþ
è öåëîñòíîñòü õðàíèìîé è ïåðåäàâàåìîé èíôîðìàöèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ Ò Ð Ê 1073-2007. Ñðåäñòâà êðèïòîãðàôè÷åñêîé çàùèòû èíôîðìàöèè. Îáùèå òåõíè÷åñêèå
òðåáîâàíèÿ. — Ââåä. 2009. 01.01. — Àñòàíà, 2009. — 15 ñ.
2. À ê ó ø ñ ê è é È . ß . , Þ ä è ö ê è é . Ä . È . Ìàøèííàÿ àðèôìåòèêà â îñòàòî÷íûõ êëàññàõ. — Ì.: Ñîâ.
ðàäèî, 1968. — 439 ñ.
3. Á è ÿ ø å â Ð . Ã . Ðàçðàáîòêà è èññëåäîâàíèå ìåòîäîâ ñêâîçíîãî ïîâûøåíèÿ äîñòîâåðíîñòè â ñèñòåìàõ
îáìåíà äàííûìè ðàñïðåäåëåííûõ ÀÑÓ: Äèñ. ... äîêò. òåõí. íàóê. — Ì., 1985. — 328 ñ.
4. À ì å ð á à å â Â . Ì . , Á è ÿ ø å â , Ð . Ã . , Í û ñ à í á à å â à Ñ . Å . Ïðèìåíåíèå íåïîçèöèîííûõ ñèñòåì
ñ÷èñëåíèÿ ïðè êðèïòîãðàôè÷åñêîé çàùèòå // Èçâ. Íàö. àêàä. íàóê Ðåñïóáëèêè Êàçàõñòàí. Ñåð.
ôèç.-ìàò. íàóê. — Àëìàòû: Ãûëûì, 2005. — ¹ 3. — Ñ. 84–89.
5. Á è ÿ ø å â Ð . Ã . , Í û ñ à í á à å â à Ñ . Å . Âëèÿíèå ñîñòàâà ïîëèíîìèàëüíûõ îñíîâàíèé íåïîçèöèîííîé
ñèñòåìû ñ÷èñëåíèÿ íà íàäåæíîñòü øèôðîâàíèÿ // Ìàòåðèàëû VIII Ìåæäóíàð. íàó÷.-ïðàêò. êîíô.
«Èíôîðìàöèîííàÿ áåçîïàñíîñòü». — Òàãàíðîã: Èçä-âî ÒÐÒÓ, 2006. — Ñ. 66–69.
6. Á è ÿ ø å â Ð . Ã . , Í û ñ à í á à å â à Ñ . Å . Íåòðàäèöèîííûé ïîäõîä ê ñîçäàíèþ êðèïòîñèñòåì //
Èíôîðìàöèîííûå òåõíîëîãèè è áåçîïàñíîñòü: Ñá. íàó÷. òð. — 2006. — Âûï. 9. — Ñ. 20–28.
7. Á è ÿ ø å â Ð . Ã . , Ê à ï à ë î â à Í . À . , Í û ñ à í á à å â à Ñ . Å . Ðàçðàáîòêà è èññëåäîâàíèå ìîäèôè-
öèðîâàííîãî àëãîðèòìà Äèôôè–Õýëëìàíà íà áàçå ìîäóëÿðíîé àðèôìåòèêè // Àêòóàëüíûå ïðîáëåìû
áåçîïàñíîñòè èíôîðìàöèîííûõ òåõíîëîãèé: ìàòåðèàëû III Ìåæäóíàð. íàó÷.-ïðàêò. êîíô. / Ïîä îáù.
ðåä. Î.Í. Æäàíîâà, Â. Â. Çîëîòàðåâà; Ñèá. ãîñ. àýðîêîñì. óí-ò, Êðàñíîÿðñê, 9–11 ñåíò. 2009 ã. —
Êðàñíîÿðñê, 2009. — Ñ. 18–22.
8. Ì î è ñ è ë à ð . Ê . Àëãåáðàè÷åñêàÿ òåîðèÿ äèñêðåòíûõ àâòîìàòè÷åñêèõ óñòðîéñòâ. — Ì: Èçä-âî
èíîñòð. ëèò., 1963. — 680 ñ.
9. Ê à ï à ë î â à Í . À . , Í û ñ à í á à å â à Ñ . Å . Èññëåäîâàíèå àëãîðèòìà ãåíåðàöèè ïñåâäîñëó÷àéíûõ
ïîñëåäîâàòåëüíîñòåé // Èíôîðìàöèîííûå òåõíîëîãèè è áåçîïàñíîñòü. Ìåíåäæìåíò èíôîðìàöèîííîé
áåçîïàñíîñòè: Ñá. íàó÷. òð. — 2007. — Âûï. 10. — C. 32–39.
Ïîñòóïèëà 02.07.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 23
|
| id | nasplib_isofts_kiev_ua-123456789-84121 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T21:28:14Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Бияшев, Р.Г. Нысанбаева, С.Е. 2015-07-03T09:02:34Z 2015-07-03T09:02:34Z 2012 Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки / Р.Г. Бияшев, С.Е. Нысанбаева // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 14-23. — Бібліогр.: 9 назв. — рос. . 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84121 004.056.5 Запропоновано алгоритм створення електронного цифрового підпису в непозиційній поліноміальній системі числення, що формує три надмірні лишки за модулем однієї додаткової поліноміальної основи. Цей підпис дозволяє також виявляти і коректувати одиничну помилку і визначати багатократну. Показано однозначність процедури виявлення і виправлення одиничної помилки. Визначено формулу криптостійкості цифрового підпису. The authors propose an algorithm for creating a digital signature in a nonpositional polynomial notation, which forms three surplus residues modulo one additional polynomial base. This signature allows single-error detection and correction (which is shown to be a unique procedure) and multi-error detection. A formula for the cryptographic security of the digital signature is obtained. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки Алгоритм формування електронного цифрового підпису з можливістю виявлення і виправлення помилки Algorithm of creating a digital signature with error detection and correction Article published earlier |
| spellingShingle | Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки Бияшев, Р.Г. Нысанбаева, С.Е. Кибернетика |
| title | Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки |
| title_alt | Алгоритм формування електронного цифрового підпису з можливістю виявлення і виправлення помилки Algorithm of creating a digital signature with error detection and correction |
| title_full | Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки |
| title_fullStr | Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки |
| title_full_unstemmed | Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки |
| title_short | Алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки |
| title_sort | алгоритм формирования электронной цифровой подписи с возможностью обнаружения и исправления ошибки |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84121 |
| work_keys_str_mv | AT biâševrg algoritmformirovaniâélektronnoicifrovoipodpisisvozmožnostʹûobnaruženiâiispravleniâošibki AT nysanbaevase algoritmformirovaniâélektronnoicifrovoipodpisisvozmožnostʹûobnaruženiâiispravleniâošibki AT biâševrg algoritmformuvannâelektronnogocifrovogopídpisuzmožlivístûviâvlennâívipravlennâpomilki AT nysanbaevase algoritmformuvannâelektronnogocifrovogopídpisuzmožlivístûviâvlennâívipravlennâpomilki AT biâševrg algorithmofcreatingadigitalsignaturewitherrordetectionandcorrection AT nysanbaevase algorithmofcreatingadigitalsignaturewitherrordetectionandcorrection |