Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом
Рассмотрен подход к решению задачи защиты информации в компьютерных системах и сетях, использующий достижения хаотической динамики. Предложена криптографическая система с открытым ключом, функционирующая как хаотическая динамическая система. Показано, что наиболее эффективный метод криптоанализа пре...
Saved in:
| Published in: | Реєстрація, зберігання і обробка даних |
|---|---|
| Date: | 2006 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем реєстрації інформації НАН України
2006
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50833 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом / П.Ю. Костенко, А.В. Антонов, С.И. Сиващенко // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 1. — С. 103-113. — Бібліогр.: 17 назв. — pос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50833 |
|---|---|
| record_format |
dspace |
| spelling |
Костенко, П.Ю. Антонов, А.В. Сиващенко, С.И. 2013-11-04T18:59:48Z 2013-11-04T18:59:48Z 2006 Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом / П.Ю. Костенко, А.В. Антонов, С.И. Сиващенко // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 1. — С. 103-113. — Бібліогр.: 17 назв. — pос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50833 681.3.06:519.248.681 Рассмотрен подход к решению задачи защиты информации в компьютерных системах и сетях, использующий достижения хаотической динамики. Предложена криптографическая система с открытым ключом, функционирующая как хаотическая динамическая система. Показано, что наиболее эффективный метод криптоанализа предложенной системы основан на решении обратной задачи хаотической динамики и имеет экспоненциальную зависимость сложности от длины ключа. Розглянуто підхід до вирішення задачі захисту інформації у комп’ютерних системах та мережах, що використовує досягнення хаотичної динаміки. Запропоновано криптографічну систему з відкритим ключем, що функціонує як хаотична динамічна система. Показано, що найбільш ефективний метод криптоаналізу запропонованої системи полягає у вирішенні зворотної задачі хаотичної динаміки і має експоненційну залежність складності від довжини ключа. The approach to providing security of information in computer systems and networks based on chaotic systems is considered. The open key cryptography system, which functions as a chaotic dynamic system, is proposed. It is shown that the most effective method of a cryptanalysis of the offered system is based on a solution of the inverse task of chaotic dynamics and has exponential dependence of complexity on a key length. ru Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом Рішення зворотної задачі хаотичної динаміки як найбільш ефективний метод аналізу криптографічної системи з відкритим ключем Solution of the Inverse Task of Chaotic Dynamics as the Most Effective Method of the Analysis of an Open Key Cryptography System Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом |
| spellingShingle |
Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом Костенко, П.Ю. Антонов, А.В. Сиващенко, С.И. Методи захисту інформації в комп’ютерних системах і мережах |
| title_short |
Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом |
| title_full |
Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом |
| title_fullStr |
Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом |
| title_full_unstemmed |
Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом |
| title_sort |
решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом |
| author |
Костенко, П.Ю. Антонов, А.В. Сиващенко, С.И. |
| author_facet |
Костенко, П.Ю. Антонов, А.В. Сиващенко, С.И. |
| topic |
Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet |
Методи захисту інформації в комп’ютерних системах і мережах |
| publishDate |
2006 |
| language |
Russian |
| container_title |
Реєстрація, зберігання і обробка даних |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| format |
Article |
| title_alt |
Рішення зворотної задачі хаотичної динаміки як найбільш ефективний метод аналізу криптографічної системи з відкритим ключем Solution of the Inverse Task of Chaotic Dynamics as the Most Effective Method of the Analysis of an Open Key Cryptography System |
| description |
Рассмотрен подход к решению задачи защиты информации в компьютерных системах и сетях, использующий достижения хаотической динамики. Предложена криптографическая система с открытым ключом, функционирующая как хаотическая динамическая система. Показано, что наиболее эффективный метод криптоанализа предложенной системы основан на решении обратной задачи хаотической динамики и имеет экспоненциальную зависимость сложности от длины ключа.
Розглянуто підхід до вирішення задачі захисту інформації у комп’ютерних системах та мережах, що використовує досягнення хаотичної динаміки. Запропоновано криптографічну систему з відкритим ключем, що функціонує як хаотична динамічна система. Показано, що найбільш ефективний метод криптоаналізу запропонованої системи полягає у вирішенні зворотної задачі хаотичної динаміки і має експоненційну залежність складності від довжини ключа.
The approach to providing security of information in computer systems and networks based on chaotic systems is considered. The open key cryptography system, which functions as a chaotic dynamic system, is proposed. It is shown that the most effective method of a cryptanalysis of the offered system is based on a solution of the inverse task of chaotic dynamics and has exponential dependence of complexity on a key length.
|
| issn |
1560-9189 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50833 |
| citation_txt |
Решение обратной задачи хаотической динамики как наиболее эффективный метод анализа криптографической системы с открытым ключом / П.Ю. Костенко, А.В. Антонов, С.И. Сиващенко // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 1. — С. 103-113. — Бібліогр.: 17 назв. — pос. |
| work_keys_str_mv |
AT kostenkopû rešenieobratnoizadačihaotičeskoidinamikikaknaiboleeéffektivnyimetodanalizakriptografičeskoisistemysotkrytymklûčom AT antonovav rešenieobratnoizadačihaotičeskoidinamikikaknaiboleeéffektivnyimetodanalizakriptografičeskoisistemysotkrytymklûčom AT sivaŝenkosi rešenieobratnoizadačihaotičeskoidinamikikaknaiboleeéffektivnyimetodanalizakriptografičeskoisistemysotkrytymklûčom AT kostenkopû ríšennâzvorotnoízadačíhaotičnoídinamíkiâknaibílʹšefektivniimetodanalízukriptografíčnoísistemizvídkritimklûčem AT antonovav ríšennâzvorotnoízadačíhaotičnoídinamíkiâknaibílʹšefektivniimetodanalízukriptografíčnoísistemizvídkritimklûčem AT sivaŝenkosi ríšennâzvorotnoízadačíhaotičnoídinamíkiâknaibílʹšefektivniimetodanalízukriptografíčnoísistemizvídkritimklûčem AT kostenkopû solutionoftheinversetaskofchaoticdynamicsasthemosteffectivemethodoftheanalysisofanopenkeycryptographysystem AT antonovav solutionoftheinversetaskofchaoticdynamicsasthemosteffectivemethodoftheanalysisofanopenkeycryptographysystem AT sivaŝenkosi solutionoftheinversetaskofchaoticdynamicsasthemosteffectivemethodoftheanalysisofanopenkeycryptographysystem |
| first_indexed |
2025-11-27T01:09:21Z |
| last_indexed |
2025-11-27T01:09:21Z |
| _version_ |
1850787312886087680 |
| fulltext |
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 103
УДК 681.3.06:519.248.681
П. Ю. Костенко, А. В. Антонов, С. И. Сиващенко
Харьковский университет Воздушных Сил им. Ивана Кожедуба
ул. Сумская, 77/79, 61023 Харьков, Украина
Решение обратной задачи хаотической динамики
как наиболее эффективный метод анализа
криптографической системы с открытым ключом
Рассмотрен подход к решению задачи защиты информации в компь-
ютерных системах и сетях, использующий достижения хаотической
динамики. Предложена криптографическая система с открытым
ключом, функционирующая как хаотическая динамическая система.
Показано, что наиболее эффективный метод криптоанализа предло-
женной системы основан на решении обратной задачи хаотической
динамики и имеет экспоненциальную зависимость сложности от дли-
ны ключа.
Ключевые слова: криптография с открытым ключом, хаотическая
динамика, обратная задача хаотической динамики, сложность крип-
тоанализа.
Один из новых подходов к совершенствованию криптосистем основан на их
рассмотрении с позиций хаотической динамики [1, 2]. При этом можно единооб-
разно оценить как существующие криптосистемы, так и вновь разрабатываемые.
Кроме того, есть основания утверждать, что решения задач защиты информации в
компьютерных системах и сетях с использованием методов хаотической динами-
ки могут оказаться достаточно эффективными с точки зрения их криптостойко-
сти. Разработке криптосистем с позиций хаотической динамики посвящены рабо-
ты зарубежных авторов, например [3–5].
Особенно актуальными для больших информационно-коммуникационных
систем и сетей являются криптосистемы с открытым ключом [6]. В настоящее
время схемой шифрования с открытым ключом, получившей наибольшее призна-
ние и распространение, является RSA [7]. Она используется для обмена ключами,
создания цифровой подписи и шифрования данных. Применяются также стандарт
цифровой подписи DSS [8], схемы Эль-Гамаля [9], Шнорра [10], криптопреобра-
зования в группе точек эллиптических кривых [11] и др. Дискретные преобразо-
вания, применяемые в некоторых из них, можно встретить и в хаотической дина-
мике. Их криптостойкость основана на «вычислительной сложности» криптоана-
© П. Ю. Костенко, А. В. Антонов, С. И. Сиващенко
Решение обратной задачи хаотической динамики
как наиболее эффективный метод анализа криптографической системы с открытым ключом
104
лиза теоретико-числовых алгоритмов. Однако «вычислительная сложность» зави-
сит от развития математических методов решения теоретико-числовых задач (на-
пример, разложения чисел на простые множители, дискретного логарифмирова-
ния), что делает эти системы потенциально уязвимыми [12–14]. Поэтому разра-
ботка потенциально стойкой криптосистемы с открытым ключом в современной
криптографии (в том числе и методами нелинейной динамики) представляется
актуальной задачей.
В работе предложена криптосистема с открытым ключом, функционирующая
как хаотическая динамическая система, криптостойкость которой основана на не-
однозначности обращения хаотического отображения (оценки его порядка) в слу-
чае незнания личного ключа.
Цель работы — показать, что решение обратной задачи хаотической динами-
ки является наиболее эффективным методом криптоанализа предложенной систе-
мы.
Хаотическая динамическая система задается оператором эволюции систе-
мы (отображением). Отображение можно задать в форме рекуррентного уравне-
ния — новое значение состояния динамической системы определяется по преды-
дущему. В режиме развитого хаоса состояние системы становится трудно прогно-
зируемо и может быть описано в текущий момент времени инвариантной плотно-
стью вероятности.
Для некоторых систем хаотическое решение рекуррентного уравнения можно
записать в явном виде с помощью формулы [15]:
)и(Ш n
n TkX = ,
где )(tY — периодическая функция (тригонометрическая, эллиптическая и др.);
k — параметр, определяющий порядок отображения; T — период функции )(Шt ;
)и(Ш0 Tx = — начальное значение хаотической системы (и — вещественное зна-
чение, удовлетворяющее данному условию). Конкретные формы записи для соот-
ветствующих отображений можно найти в [15]. Степень хаотичности системы ха-
рактеризуется показателем Ляпунова: )ln(k=l [16].
Важной особенностью некоторых отображений является так называемое по-
лугрупповое свойство
Ψr (Ψs (t)) = Ψr–s (t), (1)
и его следствие — свойство коммутативности:
Ψr (Ψs (t)) = Ψs (Ψr (t)). (2)
Рекуррентное уравнение для двухэлементного кусочно-линейного отображе-
ния задается в виде:
П. Ю. Костенко, А. В. Антонов, С. И. Сиващенко
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 105
ï
ï
î
ïï
í
ì
££
<£
-
-=+ ,1 ,
,0 ,
,1
11
n
n
n
n
n xa
ax
a
x
a
x
x
где n — натуральное число; x и a — вещественные числа, принимающие значе-
ния на интервале ( )1,0 . Параметр a определяет границы интервалов ( ]a,0 и ( )1,a
задания элементов отображения, и часто называется управляющим.
Для предельного значения 21=а решение рекуррентного уравнения записы-
вается в явном виде с помощью формулы:
)) 2( arccos(cos1
0xx n
n p
p
= .
Здесь 0x — начальное значение.
В общем случае отображение можно записать в виде:
( )( )xkxTk p
p
cos arccos1)( = ,
где k — порядок хаотического отображения, который определяет число его эле-
ментов.
Для кусочно-линейного отображения при целых значениях порядка справед-
ливы свойства (1) и (2). Рассмотрим криптографическое приложение отображения
)(xTk .
Криптосистема с открытым ключом на основе
кусочно-линейного отображения
Практически любая криптографическая система включает в себя три состав-
ляющих: формирование ключей, зашифрование и расшифрование сообщений.
Будем считать, что сообщение, подлежащее зашифрованию, представляется
(кодируется) натуральным числом М. В двоичной системе счисления М записыва-
ется не более чем m битами. Тогда емкость множества возможных сообщений
m
M MV 2max == .
Формирование ключей пользователем А включают в себя следующие основ-
ные этапы.
1. Генерирование простых чисел P и Q.
2. Нахождение неустойчивой неподвижной точки )(XTX N= отображения
порядка QPN ×= , которая должна находиться на интервале ( )m-2,0 определения
первого элемента кусочно-линейного отображения порядка .2m Для этого пара-
метры P и Q необходимо выбирать таким образом, чтобы выполнялось условие
mN 2> .
Решение обратной задачи хаотической динамики
как наиболее эффективный метод анализа криптографической системы с открытым ключом
106
3. Вычисление и опубликование открытого ключа:
)(XTY P= .
Значения X, P, Q, N являются секретными. Пара значений ( )QX , составляет
личный ключ. Значения P и N в дальнейших вычислениях не используются.
Для зашифрования сообщения пользователь Б действует в следующем поряд-
ке.
1. Получает открытый ключ Y пользователя А.
2. Вычисляет и отправляет пользователю А шифротекст:
)(YTC M= .
Таким образом, порядок отображения принимает значение шифруемого со-
общения М. Шифротекст C представляет собой вещественное число, принадле-
жащее интервалу ( )1,0 определения отображения.
Процедура расшифрования сообщения пользователем А состоит в вычисле-
нии значения выражения:
( )( )( )
X
CT
X
CT
M QQ )(cosarccos€ ==
p
p
, (3)
которое является оценкой сообщения M (порядка отображения).
Корректность работы криптосистемы основана на использовании полу-
групповых (1) и коммутативных (2) свойств отображения
))(()))((( XTTXTYTCT QPNMPMQ ×==== ,
а также неустойчивых неподвижных точек )(XTX N= , то есть:
)()( XTCT MQ = .
При выбранном интервале задания неустойчивых неподвижных точек X вы-
полняется неравенство 1£MX , с учетом которого
MXMXXTM == ))(arccos(cos1)( p
p
.
Тогда для оценки M€ справедливо выражение (3).
Информационная скрытность (стойкость) криптосистемы основана на не-
однозначности определения открытого текста M непосредственным обращением
П. Ю. Костенко, А. В. Антонов, С. И. Сиващенко
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 107
отображения ( )MT . По известным значениям открытого ключа Y и шифротекста
C можно получить множество { }M€ оценок
,...,1,0 ,2
2))( arccos(cos2))( (cos arccos€
=+±=
=+±=
+±
=
nn
YY
С
n
YY
С
Y
nСM n p
p
p
pp
(4)
емкость [ ]YMnVM ×=×= maxmax€ 2 которого зависит от значения открытого ключа Y
и максимально возможного значения открытого текста mM 2max = .
Множество { }M€ содержит одно натуральное значение MM =€ (остальные
оценки — вещественные числа). Поэтому критерием выбора MM =€ из множест-
ва { }M€ является ее натуральное значение.
Покажем, что сложность S криптоанализа решением обратной задачи хаоти-
ческой динамики (обращением хаотического отображения), определяемая числом
итераций процедуры оценки искомого параметра, необходимых для успешного
завершения криптоатаки, имеет экспоненциальную зависимость от длины ключа
(блока открытого текста).
Сложность криптоанализа, а значит и стойкость криптосистемы, определяет-
ся емкостью MV € множества M€ и равна 2€MM VS = , где [ ]YV m
M ×= 2€ .
Уменьшение сложности криптоанализа можно достичь учетом избыточности
в сообщении M (эквивалентно уменьшению значения maxM ) и уменьшением зна-
чения Y . В предположении, что в M устранена возможная избыточность (все со-
общения равновероятны), уменьшение сложности MS достигается смещением
значения открытого ключа Y к началу координат. Смещение достигается вычис-
лением
( )YTY ii =
~ , ,...2 ,1=i ,
до тех пор, пока значение iY~ не попадет в заданный интервал, принадлежащий
окрестности начала координат. Для требуемой сложности MS криптоанализа (см.
(4)) верхняя граница области определения смещенного значения ключа ( )YTY ii =
~
равна m
MSy 22 ×= . Сложность смещения открытого ключа Y в заданный интер-
вал ( ]y,0 при условии, что емкость множества значений личного ключа MQ VV > ,
определяется статистическими свойствами хаотического отображения (вероятно-
стью попадания iY~ в интервал ( ]y,0 ) и равна значению ySK 1= .
Далее из выражения (4), пользуясь свойствами (1) и (2), получаем:
Решение обратной задачи хаотической динамики
как наиболее эффективный метод анализа криптографической системы с открытым ключом
108
( )
( )
ï
ï
î
ïï
í
ì
-
+-
-
+
=
нечетное.если,~
1
четное,если,~
€
n
Y
CTn
n
Y
CTn
M
i
i
i
i
(5)
Если границу y интервала выбрать из условия my -£ 2 , то значение ( ]yYi ,0~ Î
и соответствующее ему значение i будут оценками личного ключа, которые по-
зволяют определить порядок отображения M без разрешения неоднозначности,
так как 0max =n . При этом для успешного криптоанализа не существенно соблю-
дение равенств iYX ~= и iQ = .
Суммарная сложность атаки равна:
[ ]ykykSSS m
MKKM
121 -+=+= ,
где k — число сообщений, криптоанализ которых необходимо выполнить. Ва-
риациями y можно изменять значение сложности KMS .
Представим сложность криптоанализа функцией ( ) ykymkys m 121,, -×+= , ко-
торая, как легко заметить, имеет один минимум при фиксированных значениях k
и m . Оптимальное значение верхней границы интервала ( ]y,0 , найденное из ус-
ловия ( )mkys
y
,,min , определяется выражением ( ) ( ) 21
opt 22,
-
×= mkmky . Тогда со-
ответствующее значение сложности равно:
( ) ( ) ( ) ( ) ( )( ) ( )( )( )mnlmnlmmm
m
ekOekkkkkmks 2222221211
21
222222
2
2, ×=×==+=
-- .(6)
Таким образом, зависимость ( )mks , от длины m имеет экспоненциальный
характер. Можно утверждать, что оценка сложности криптоанализа предложен-
ной системы с использованием выражения (6) не меньше, а при росте k потенци-
ально выше, сложности криптоанализа преобразований на эллиптических кривых.
Значение miny задается верхней границей интервала определения первого элемен-
та отображения ( )YTM . Максимальная сложность криптоанализа потока сообще-
ний определяется сложностью атаки на ключ 12 -== m
KKM SS и достигается при
условии 12 -³ mk , вытекающего из неравенства ( ) mymky -=£ 2, minopt .
Выражение (6) получено в предположении отсутствия более эффективного
метода смещения открытого ключа Y в заданный интервал, чем последователь-
ный перебор i в ( )YTY ii =
~ . Однако можно предложить более эффективный метод
решения этой задачи, в основе которого лежит пошаговое смещение открытого
ключа.
Пошаговое смещение открытого ключа достигается вычислением значений
П. Ю. Костенко, А. В. Антонов, С. И. Сиващенко
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 109
( )1~
~~
-= nQn YTY
n
, ,...2,1=n ,
где YY =0
~ , а [ ]1
~2~
-= nn YQ . Если полученное на шаге n значение 2~~
1-> nn YY , то
значение nQ~ модифицируется как [ ] 1~2~
1 += -nn YQ , и вычисляется новое значение
nY~ для шага n . Смещение проводится до тех пор, пока оценка nY~ не попадет в
требуемый интервал. Далее значения nYY ~~ = , Õ
=
=
n
i
iQQ
1
~~ используются в выраже-
нии (5) для определения открытого текста. Оценим количество шагов maxn , необ-
ходимых для успеха атаки и получаемое при этом значение Q~ .
Очевидно, что за один шаг значение nY~ смещается в среднем в окрестность
точки 4~
1-nY , т.е. можно предположить, что:
0
2
01
~2~
4
1~
4
1~ YYYY n
n
nn
-
- =÷
ø
ö
ç
è
æ=» .
Для полученной на шаге n оценки nY~ в среднем:
( )
ú
û
ù
ê
ë
é
=ú
û
ù
ê
ë
é ×
=ú
û
ù
ê
ë
é
=
--
- 0
12
0
12
1
~
2
~
22
~
2~
YYY
Q
nn
n
n .
Соответственно на шаге n:
( ) ( )( )
( )
( ) ( )( )( )
( )
( )( )
( )
nn
n
nnn
n
nnn
n
nnnn
i
i YYYY
QQ ÷÷
ø
ö
çç
è
æ
===
×××
==
-++-+---
=
Õ
00
1
0
1...212
0
22212
1
~
2
~
22
~
22
~
2...222~~ .
Для эффективного противодействия криптоанализу решением обратной зада-
чи хаотической динамики целесообразно выбирать значение открытого ключа Y
в интервале ( )25,032,25,032 +- . Соответственно для дальнейших рассуждений
предположим, что 21~
0 == YY . Тогда:
( )1
0
2~
2~ +»÷÷
ø
ö
çç
è
æ
= nn
nn
Y
Q .
Можно показать, что, если точность задания параметров криптосистемы вы-
ражать количеством бит, необходимым для их представления в формате двоич-
ных чисел с фиксированной запятой, то для обеспечения однозначности крипто-
преобразований неустойчивые неподвижные точки Х необходимо задавать с точ-
Решение обратной задачи хаотической динамики
как наиболее эффективный метод анализа криптографической системы с открытым ключом
110
ностью не меньшей ( )14 +m бит. Такое значение получено в предположении, что
параметры P и Q задаются 1+= mp и 1+= mq битами соответственно. Откры-
тый ключ должен задаваться с точностью ( )13 +m бит, шифротекст — 32 +m би-
тами.
Если полученная оценка 12~ +> mQ , или ( ) imQ ++» 12~ , то ошибки округлений при
вычислениях приведут к тому, что i последних бит оценки M€ будут неверными.
В случае, если mQ 22~
> , то в оценке M€ не содержится ни одного бита открытого
текста.
Найдем n , для которого выполняется условие mQ 22~
£ :
mnn 222
2
£+ , mnn 22 £+ , mn 81
2
1
2
1
++-£ .
Учитывая, что в практических приложениях используются сообщения с
64³m , можно записать следующее выражение для оценки верхней границы n :
[ ]mn 2£ .
Таким образом, сложность смещения ключа Y до значения [ ]YY m222~ -= по
сравнению со сложностью последующей оценки сообщения ничтожно мала, и ее
можно не учитывать. Сложность оценки сообщения и атаки в целом:
[ ] 2221 2~2 --- »=» mmm
MKM YSS ,
или
( )( ) ( )( )( )mmmmmm ekOekkmks 222ln2222ln2222),(~ ----- ×=×=×= . (7)
Эффективность пошагового смещения открытого ключа по сравнению с по-
следовательным можно оценить как:
( ) ( ) ( )( ) ÷
ø
ö
ç
è
æ
×=== -+-
--
222ln2222
222
2 122
2
22
),(~
),( mmmm
mm
m
e
k
O
kk
k
mks
mks . (8)
Для 1=k , уже при 41>m бит отношение (8) меньше единицы и, таким обра-
зом, пошаговое смещение открытого ключа Y оказывается менее эффективным.
Оценка стойкости криптосистемы, основанная на анализе сложности решения
обратной задачи хаотической динамики, предполагает отсутствие более эффек-
тивных методов определения ее секретных параметров Q , P , N и, соответствен-
но, восстановления открытого текста. Однако в предложенном выше варианте
криптосистемы в распоряжении криптоаналитика оказывается достаточно инфор-
П. Ю. Костенко, А. В. Антонов, С. И. Сиващенко
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 111
мации о секретных системных параметрах для проведения более эффективных
атак, основанных на определении порядка N отображения и последующем нахо-
ждении Q и P , например, с использованием свойств неустойчивых неподвижных
точек хаотических отображений.
Криптоанализ с использованием неустойчивых
неподвижных точек
Для отображения ( )NT значения X являются неустойчивыми неподвижны-
ми точками по определению, а Y и все значения шифротекста C являются неус-
тойчивыми неподвижными точками вследствие выполнения следующих равенств:
( ) ( )( ) ( )( ) ( ) YXTXTTXTTYT PNPPNN ==== ,
( ) ( )( ) ( )( ) ( ) CYTYTTYTTCT MNMMNN ==== .
Решая уравнение ( )YTY N= , можно оценить порядок отображения:
,....1,0 ,212
2))( arccos(cos 2))( arccos(cos€
=+±=+±=
=+±=
+±
=
ii
Y
i
YY
Y
i
YY
Y
Y
iYN Y
i p
p
p
pp
(9)
Емкость множества оценок равна [ ]YNiVN ×=×= maxmax€ 2 . Таким образом, оп-
ределение целочисленного значения N из выражения (9) является более сложной
задачей по сравнению с криптоанализом, использующим выражение (4), вследст-
вие того, что maxMN > . Решение уравнения ( )CTC N= также дает оценки:
,....1,0 ,212
2))( arccos(cos2))( arccos(cos€
=+±=+±=
=+±=
+±
=
jj
C
j
CC
C
j
CC
C
C
jCN C
j p
p
p
pp
(10)
Емкость их множества равна [ ]CNjVN ×=×= maxmax€ 2 . Если криптоаналитик
получит значение C близкое к началу координат, то это позволит значительно
уменьшить емкость NV € , либо вообще исключить неоднозначность в (10). Кроме
того множества { }N€ , получаемые из выражений (9) и (10), имеют пересечение
{ } { } maxmax
11
€€ j
j
C
j
i
i
Y
i NN
== Ç , единственный элемент которого — искомое натуральное зна-
чение N . Соответственно попарно разделив левые и правые части выражений (9)
и (10), получим:
,...1,0 ,...,1,0 ,
1€
1€
==
×
×
=
±
± ji
jY
iC
N
N
C
j
Y
i .
Решение обратной задачи хаотической динамики
как наиболее эффективный метод анализа криптографической системы с открытым ключом
112
Для пересечения { } { } maxmax
11
€€ j
j
C
j
i
i
Y
i NN
== Ç :
C
Y
j
i
= . (11)
Таким образом, задача определения N с использованием соотношения (11)
оказывается достаточно просто решаемой. Сложность криптоанализа для предло-
женного варианта криптосистемы сводится к факторизации N на простые сомно-
жители P и Q, и соизмерима со сложностью криптоанализа RSA.
Вообще говоря, при формировании ключей числа P и Q можно выбирать не
только простыми, но и натуральными. Однако в этом случае неустойчивая непод-
вижная точка X может принадлежать орбите более низкого порядка, что позво-
лит определить личный ключ усилиями, соизмеримыми с ее порядком.
Для устранения возможности определения N с использованием (11) необхо-
димо модифицировать выбор ключей в криптосистеме следующим образом. Зна-
чение N выбираем простым, выполняя условие maxMN > . Это требование позво-
ляет исключить из группы неустойчивых неподвижных точек отображения ( )NT
неустойчивые неподвижные точки отображений меньшего порядка. В качестве
параметра Q следует выбирать любое натуральное значение близкое к N . То-
гда параметр QNP = будет вещественным значением. Такой выбор параметров
не нарушает свойство (1), которое выполняется для кусочно-линейного отображе-
ния не только при целых значениях порядка, но и в случае, если порядок внутрен-
него отображения )(XTP задается вещественным значением:
))),2(( arccos(cos1)))))( arccos(cos1(( arccos(cos1))(( nPXQXPQXTT PQ +-== p
p
p
p
p
p
где n целое, такое что 1)2(1 <+-<- nPX . Если Q — целое, то:
),()))( arccos(cos1)))2( arccos(cos1))(( XTQPXQnQPXXTT PQPQ ×==+-= p
p
pp
p
так как слагаемое Qnp2 кратно периоду функции ( )cos . Если Q — веществен-
ное, то слагаемое Qnp2 нельзя отбрасывать, и отображение имеет сложную струк-
туру. Очевидно, что для рассматриваемого случая свойство (2) не выполняется.
Для такого выбора ключей точки Y и C не будут являться неустойчивыми
неподвижными точками отображения ( )NT . Следовательно, можно утверждать,
что сложность криптоанализа в этом случае определяется сложностью решения
обратной задачи хаотической динамики.
Выводы
В работе предложен подход к решению задачи обеспечения защиты инфор-
мации в компьютерных системах и сетях, основанный на использовании достиже-
П. Ю. Костенко, А. В. Антонов, С. И. Сиващенко
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 113
ний хаотической динамики, который открывает новые возможности эффективно-
го ее решения. Анализ показал, что эффективность предложенного подхода опре-
деляется сложностью решения обратной задачи хаотической динамики, которая
имеет экспоненциальную зависимость от длины m блока открытого текста (клю-
ча). Даже при анализе одного сообщения подход обеспечивает стойкость не
меньшую, чем наилучшие в настоящее время криптосистемы с открытым ключом,
использующие преобразования на эллиптических кривых [17]. При этом стой-
кость основана не на «вычислительной сложности» криптоанализа теоретико-
числовых алгоритмов, а на неоднозначности обращения хаотического отображе-
ния (оценки порядка) в случае незнания личного ключа и его статистических
свойствах.
1. Птицин Н.И. Приложение теории детерминированного хаоса в криптографии. — М.:
МГТУ, 2002. — 79 с. ил.
2. Kocarev L. Chaos-Based Cryptography: A Brief Overview // IEEE Circuits and Systems Maga-
zine. — 2001. — Vol. 1. — P. 6–21.
3. Kocarev L., Tasev Z. Public-Key Encryption Based on Chebyshev Maps // Proc. IEEE Symp. on
Circuits and Systems (ISCAS-2003). — 2003. — Vol. 3. — P. 28–31.
4. Masuda N., Aihara K. Cryptosystem With Discretized Chaotic Maps // IEEE Transactions on
Circuits and Systems 1: Fundamental Theory and Applications. — 2002. — Vol. 49. — N 1. — P. 28–39.
5. Kotulski Z., et. al. Application of Discrete Chaotic Dynamical Systems in Cryptography — DCC
Method // International Journal Bifurcation and Chaos. — 1999. — Vol. 9. — P. 1121–1135.
6. Diffie W., Hellman M. New Directions in Cryptography // IEEE Transactions on Information
Theory. — 1976. — Vol. 22. — P. 644–654.
7. Rivest R., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public Key
Cryptosystem // ACM Communications. — 1978. — Vol. 21. — P. 120–126.
8. Федеральный стандарт обработки информации FIPS PUB 186 // NIST USA. — 1996.
9. ElGamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms
// IEEE Transactions on Information Theory. — 1985. — Vol. 31. — P. 469–472.
10. Schnorr C. Efficient Identification and a Signatures for Smart Card // Journal of Cryptology. —
1991. — N. 3.
11. Koblitz N. Elliptic Curve Cryptography // Math. Comput. — 1987. — Vol. 48. — Р. 203–209.
12. Cowie J., et al. A World Wide Number Field Sieve Factoring Record: On to 512 Bits // Proc.
ASIACRYPT’96. —1996, Nov.
13. Odiyzko A. The Future of Integer Factorization // CryptoBytes. — 1995, Sum.
14. Wiener M. Cryptanalysis of Short RSA Secret Exponents // IEEE Transactions on Information
Theory. — 1990. — Vol. IT-36.
15. Kotulski Z., et. al. On Constructive Approach to Chaotic Pseudorandom Number Generator //
RCMCIS. — 2002.
16. Шустер Г. Детерминированный хаос: Пер. с англ. — М.: Мир, 1985. — 255 с. ил.
17. Столингс В. Криптография и защита сетей: принципы и практика. — 2-е изд.: Пер. с англ.
— М.: Издательский дом «Вильямс», 2001. — 672 с. ил. — Парал. тит. англ.
Поступила в редакцию 20.02.2006
|