Система криптографического преобразования чисел линейными рекуррентными формами
Рассматривается двухступенчатая система кодирования чисел, основанная на представлении чисел в виде aPn + bQn, где Pn и Qn линейные рекуррентные последовательности. Последовательности Pn и Qn определяются разложением в цепные дроби квадратичных иррациональностей вида (a + √b)/c. В системах симметри...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и вычислительная техника |
|---|---|
| Datum: | 2016 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України
2016
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/117078 |
| 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: | Система криптографического преобразования чисел линейными рекуррентными формами / А.В. Анисимов // Кибернетика и вычислительная техника. — 2016. — Вип. 186. — С. 5-14. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-117078 |
|---|---|
| record_format |
dspace |
| spelling |
Анисимов, А.В. 2017-05-19T16:08:55Z 2017-05-19T16:08:55Z 2016 Система криптографического преобразования чисел линейными рекуррентными формами / А.В. Анисимов // Кибернетика и вычислительная техника. — 2016. — Вип. 186. — С. 5-14. — Бібліогр.: 6 назв. — рос. 0452-9910 https://nasplib.isofts.kiev.ua/handle/123456789/117078 519.72 Рассматривается двухступенчатая система кодирования чисел, основанная на представлении чисел в виде aPn + bQn, где Pn и Qn линейные рекуррентные последовательности. Последовательности Pn и Qn определяются разложением в цепные дроби квадратичных иррациональностей вида (a + √b)/c. В системах симметричной криптографии числа a, b и c является ключами. Розглядається двоступенева система кодування чисел, заснована на представленні чисел у вигляді aPn + bQn, де Pn та Qn лінійні рекурентні послідовності. Послідовності Pn і Qn визначаються розкладанням в ланцюгові дроби квадратичних іррациональностей виду (a + √b)/c. У системах симетричної криптографії числа a, b і c є таємними ключами. The purpose of the article is to develop and study a nondeterministic system of cryptographic integer encoding by means of linear recurrent sequences. Methods. We used methods of continued fractions, properties of linear forms, and bijective encoding of natural numbers. Results. We proved as a theorem that such a system of encoding is absolutely resistant to passive crypto-attacks. With some further additions it is also resistant to stronger types of attacks. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України Кибернетика и вычислительная техника Информатика и информационные технологии Система криптографического преобразования чисел линейными рекуррентными формами Система криптографічного перетворення чисел лінійними рекурентними формами System of Cryptographic Transformations of Numbers by Means of Linear Recurrent Forms 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 |
2016 |
| language |
Russian |
| container_title |
Кибернетика и вычислительная техника |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН України та МОН України |
| format |
Article |
| title_alt |
Система криптографічного перетворення чисел лінійними рекурентними формами System of Cryptographic Transformations of Numbers by Means of Linear Recurrent Forms |
| description |
Рассматривается двухступенчатая система кодирования чисел, основанная на представлении чисел в виде aPn + bQn, где Pn и Qn линейные рекуррентные последовательности. Последовательности Pn и Qn определяются разложением в цепные дроби квадратичных иррациональностей вида (a + √b)/c. В системах симметричной криптографии числа a, b и c является ключами.
Розглядається двоступенева система кодування чисел, заснована на представленні чисел у вигляді aPn + bQn, де Pn та Qn лінійні рекурентні послідовності. Послідовності Pn і Qn визначаються розкладанням в ланцюгові дроби квадратичних іррациональностей виду (a + √b)/c. У системах симетричної криптографії числа a, b і c є таємними ключами.
The purpose of the article is to develop and study a nondeterministic system of cryptographic integer encoding by means of linear recurrent sequences. Methods. We used methods of continued fractions, properties of linear forms, and bijective encoding of natural numbers. Results. We proved as a theorem that such a system of encoding is absolutely resistant to passive crypto-attacks. With some further additions it is also resistant to stronger types of attacks.
|
| issn |
0452-9910 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/117078 |
| citation_txt |
Система криптографического преобразования чисел линейными рекуррентными формами / А.В. Анисимов // Кибернетика и вычислительная техника. — 2016. — Вип. 186. — С. 5-14. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT anisimovav sistemakriptografičeskogopreobrazovaniâčisellineinymirekurrentnymiformami AT anisimovav sistemakriptografíčnogoperetvorennâčisellíníinimirekurentnimiformami AT anisimovav systemofcryptographictransformationsofnumbersbymeansoflinearrecurrentforms |
| first_indexed |
2025-11-26T01:42:45Z |
| last_indexed |
2025-11-26T01:42:45Z |
| _version_ |
1850605135227518976 |
| fulltext |
5
Информатика и
информационные технологии
УДК 519.72
СИСТЕМА КРИПТОГРАФИЧЕСКОГО
ПРЕОБРАЗОВАНИЯ ЧИСЕЛ ЛИНЕЙНЫМИ
РЕКУРРЕРТНЫМИ ФОРМАМИ.
А.В. Анисимов
Киевский национальный университет имени Тараса Шевченка
Рассматривается двухступенчатая система кодирования
чисел, основанная на представлении чисел в виде aPn + bQn, где Pn и Qn
линейные рекуррентные последовательности. Последовательности Pn и Qn
определяются разложением в цепные дроби квадратичных
иррациональностей вида
c
ba + . В системах симметричной
криптографии числа a, b и c является ключами.
Ключевые слова: линейные формы, цепные дроби,
недетерминированная криптография
Розглядається двоступенева система кодування чисел,
заснована на представленні чисел у вигляді aPn + bQn, де Pn та Qn лінійні
рекурентні послідовності. Послідовності Pn і Qn визначаються
розкладанням в ланцюгові дроби квадратичних іррациональностей виду
c
ba + . У системах симетричної криптографії числа a, b і c є таємними
ключами.
Ключові слова: лінійні форми, ланцюгові дроби,
недетермінірована криптографія
ВВЕДЕНИЕ
Рассматривается двухступенчатая система симметрического
криптографического числового преобразования, основанная на
представлении чисел в виде линейных комбинаций соседних пар линейных
рекуррентных последовательностей. На первом этапе исходное число x
недетерминировано раскладывается в сумму, x = aPn + bQn где Pn и Qn
соответственно числитель и знаменатель подходящей цепной дроби
квадратичной иррациональности вида a b
c
+ . Выбор n не детерминирован.
На втором этапе тройка чисел (a, b, n) взаимно — однозначно кодируется
при помощи линейной рекуррентной последовательности
P :
1 1 1,m m m mP a P P+ + −= + которая также определяется другой
квадратичной иррациональностью. Числа a, b и c являются симметричными
ключами системы шифрования. Доказывается абсолютная стойкость системы
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
6
в случае пассивных атак (наблюдение только потока шифротекстов без
доступа к машине шифрования). Дополнительно возможно первоначальное
недетерминированное изменение числа x при помощи внесения случайных
параметров типа ОАЕР [1].
1. ЛИНЕЙНЫЕ ФОРМЫ ЧИСЛОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Все числа, рассматриваемые в данном разделе, принадлежат
натуральному ряду. В дальнейшем это предполагается по умолчанию.
Пусть 1 2, ,...U u u= и 1 2, ,...V v v= — две заданные бесконечные
последовательности положительных натуральных чисел. Предполагаем, что
последовательность U неограниченна сверху. Это означает, что для любого
числа c существует такой номер n, что для всех ,m m n> выполняется
неравенство mu c> .
Выражение n nau bv+ , ,n nu U v V∈ ∈ называем линейной ( , )U V формой.
Представление натурального числа x в виде:
n nx au bv= + , (1)
где a > 0, называем линейным ( , )U V представлением. Число n называем
рангом представления (1).
Представление (1) определяется тройкой чисел (a, b, n).
Если для всех n члены последовательности un и vn взаимно просты, то
последовательности U и V называем ортогональными. В этом случае
используем обозначение U V⊥ .
В случае U V⊥ для любого числа x и любого ранга n существует
линейное представление (1) такое, что 0 < a ≤ vn (Приложение, Лемма 5.1).
При фиксированном ранге n представление (1) называем лево-
каноническим, если a > 0 и коэффициент a — минимальный.
Очевидно, что если U V⊥ то, лево-каноническое представление (1)
фиксированного ранга единственное.
В качестве примера рассмотрим линейные формы Фибоначчи.
В этом случае последовательность U задается последовательностью
чисел Фибоначчи:
0 1 2 1 20, 1, , 3.n n nF F F F F F n− −= = = = + ≥
Последовательность V получается сдвигом U на один шаг влево
1,n n n nu F v F += = . Рассматриваем представления чисел вида
1n nx aF bF += + .
Примеры разложения чисел в максимальные линейные формы
Фибоначчи:
5 6 9 10, 6 7 6 731 3 2 ,123 2 197 23 10 9 .F F F F F F F F= + = + = + = +
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
7
Заметим, что для числа 197 существует два представления
максимального ранга. Для числа 197 представление с наименьшим первым
коэффициентом 197 = 10F6 + 9F7 лево-каноническое.
Если a > 0, b ≥ 0, то представление (1) называем положительно-
определенным.
Положительно-определенное представление (1) максимального ранга
называем максимальным.
Если a > 0, b < 0, то представление (1) называем отрицательно-
определенным.
Отметим следующие свойства отрицательно-определенного линейного
представления (1). Предполагаем, что U V⊥ .
1. Для любого положительного числа x и любого ранга n существует
отрицательно-определенное представление (1).
2. Для произвольного числа x и произвольного фиксированного ранга n
количество отрицательно-определенных представлений (1) бесконечно.
Выбирая многообразие последовательностей U и V, получаем
многообразие форм линейного представления чисел. Для разных прикладных
задач возможен выбор специальных соответствующих последовательностей
U и V [ 2–6 ].
2. ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ И ЛИНЕЙНЫЕ
ФОРМЫ.
Пусть 3 4, , ...A a a= — последовательность положительных натуральных
чисел. Последовательность A определяет линейную рекуррентную
последовательность P следующего вида:
P : 1 2 1 21, , 2.n n n nP P P a P P n− −= = = + > (2)
Рассматриваем представление натуральных чисел в виде положительно-
определенных линейных форм следующего вида:
1n nx aP bP += + , (3)
где a > 0, b ≥ 0.
Последовательность P называем базисом представления. Для
представления (3) выполняются следующие свойства:
1. Для всех индексов n числа Pn и Pn+1 взаимно просты.
2. Для любого положительного натурального числа x существует
максимальное лево-каноническое представление (3). В таком представлении
выполняются неравенства
10 na P +< < .
3. Если для числа x существует положительно-определенное
представление (3) ранга n, n > 2, то тогда для x существует положительно -
определенные представления меньших рангов , 0 2n k k n− < ≤ − .
4. Если n ранг максимального представления (3), то выполняется
неравенство
1 2n nx P P+ +< .
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
8
Менее очевидны следующие два свойства максимальных линейных
форм, которые сформулируем в виде теорем.
Теорема 1. Положительно-определенное представление (3) максимальное
лево-каноническое тогда и только тогда, когда выполняются условия:
1
2
n
n
b a P
a +
+
< < .
(4)
Следствие 1. Предположим, для натуральных чисел a и b, a > 0
выполняется неравенство 1na b P ++ < . Тогда для любого номера m, m ≥ n,
линейная форма:
1( ) m my a b P bP += + + (5)
максимальная лево-каноническая.
Доказательство. Выполняются неравенства:
1 1
2
n m
m
b a b P P
a + +
+
< + < < .
Следовательно, согласно теореме 1, линейная форма (5) — максимальная
лево-каноническая.
Отметим, что декомпозиция числа x в максимальное лево-каноническое
представление (3) требует выполнения 0(log x) арифметических операций.
3. КОДИРОВАНИЕ ПАР НАТУРАЛЬНЫХ ЧИСЕЛ ОДНИМ ЧИСЛОМ
Хорошо известна Канторовская нумерация пар натуральных чисел. Пара
(a, b) взаимно-однозначно кодируются числом:
( )( 1)( , )
2
a b a ba b b+ + +
↔ + .
Для целей настоящей работы мы предлагаем альтернативную кодировку.
Предлагаемая кодировка не является взаимно-однозначным соответствием.
Для каждой пары (a, b) множество кодовых номеров бесконечно. Пара (a, b)
однозначно восстанавливается по любому ее кодовому номеру m за (log )O m
арифметических операций.
Пусть задана рекуррентная последовательность (2). Паре
( , ), , 0a b a b b> ≥ сопоставляем число c:
1( , ) ( ) n na b c a b P bP +→ = + + , (6)
где n — любой номер такой, что выполняется неравенство
1( ) na b P ++ < .
Согласно следствию 1, представление (6) задает максимальную лево-
каноническую форму. Поэтому пара (a, b) восстанавливается очевидным
способом путем декомпозиции числа c в максимальную лево-каноническую
форму и восстанавливаем числа a при помощи вычитания второго
коэффициента из первого коэффициента соответствующей линейной формы.
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
9
Получаем, пара (a, b) однозначно кодируется бесконечным количеством
чисел вида
1 1( ) , ,m m na b P bP m n a b P+ ++ + ≥ + < .
Если выбирать для кода пары (a, b) только наименьшее n такое, что
1n nP a b P +≤ + < , то такое кодирование будет инъекцией в множество
натуральных чисел.
Через l(x) обозначим битовую длину числа x.
Отметим, что (6) определяет неравенства:
2 2
12n nP c P +< < .
Это означает, что битовая длина l(c) всегда минимум в два раза
превышает битовую длину числа (max( , ))l a b .
Если возникает необходимость кодировать одним числом пары (a, b), где
допустимо равенство a = 0, то (6) необходимо заменить на соответствие
1 1( , ) ( 1) , 1n n na b c a b P bP a b P+ +→ = + + + + + < .
Обозначим через ( , )AC a b результат кодирования пары (a, b) при помощи
базисной рекуррентной последовательности P (2), определяемой
последовательностью A. ( , )AC a b — одно из кодовых чисел вида
1 1( ) ,m m ma b P bP a b P+ ++ + + < .
Выбор параметра m недетерминирован.
Отметим, что для пар натуральных чисел кодирование линейными
формами задает бесконечное множество кодирующих функций,
определяемых выбором последовательности P.
Кодирование кортежей натуральных чисел можно свести к
последовательному кодированию пар чисел. При таком кодировании
происходит экспоненциальный рост длины кода, т.к. кодирование по
формуле (6) при выборе минимального номера m удваивает длину кода по
сравнению с длиной числа max (a, b). Для целей сокращения длины кода
кортежей типа 1 2( , ,..., ), 0, 1...km m m m i k> = можно воспользоваться
следующим приемом.
Предположим, все числа записываются в выбранной стандартной
системе счисления по основанию M. Для удобства можно считать, что
выбрана двоичная система записи чисел.
Пусть S — строка в алфавите из M цифр, a — число. Запись a || s
обозначает число, получаемое из a путем дописывания к a справа строки S.
Предположим задано число c:
1 0( ... ) , 0 , 0,..., 1. 0m m M i mc c c c c M i m c M−= ≤ < = − < < .
Положим
1 00 ...mc c c−=% .
Тройке чисел 1( , , ), 0, 0, 0, n na b c a b c y AP BP +> ≥ > = + сопоставляем
число, где
1( || ) ( || , ) || , nA a c b c B b c A P += + = <% .
Разложив y в максимальную линейную форму в базисе P, мы определим
числа 1 || a a c= % и
1 || b b c= . Просматривая цифровую запись 1a и 1b справа
налево, определим первое несовпадение соответствующих цифр. В 1b это
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
10
будет позиция, занимаемая цифрой cm, а в a1 соответствующую позицию
занимает 0.
Таким образом однозначно восстанавливается число c. Затем, очевидным
образом находим a и b.
В общем случае для кода кортежа
1 2 1 2( , ,..., ), 0, 0, 0, 3...k im m m m m m i k> ≥ > = , к числу a1 дописываем справа
3 4|| || ... || km m m% % % , а к числу m2 дописываем справа 3 4|| || ... || ka a a .
Получаем числа 1 3|| || ... || kA a a a= % % и 2 3|| || ... || kB a a a= % % .
Кортеж
1 2( , ,..., )ka a a кодируется числом:
1( ) n ny A B P BP += + + , (7)
где
1nA B P ++ < .
Очевидно, аналогично выше рассмотренному случаю кодирования троек
чисел по цифровой записи A и B, однозначно восстанавливаются числа
1 2, ,..., ka a a .
Получаем, что при кодировании кортежей максимальными линейными
формами по формуле (7) в случае ограниченности чисел ai из (2) длина кода
для кортежа 1 2( , ,..., )km m m будет порядка
1 22( ( ) ( )... ( ))kl m l m l m+ + .
4. НЕДЕТЕРМИНИРОВАННАЯ КРИПТОГРАФИЯ
Предлагаем следующую схему кодирования положительных
натуральных чисел.
Пусть
0 1, ,...A a a= бесконечная последовательность целых
положительных чисел.
Последовательность A задает иррациональное число α, представленное
бесконечной цепной дробью
0 1[ ; ,...]a aα = .
Рассматриваем множество подходящих дробей
0 1[ ; ,..., ] n
n n
n
Pa a a
Q
α = = ,
где Pn числитель, а Qn — знаменатель подходящей дроби n-го порядка.
Положим 0 1, ,...U Q Q= и
0 1, ,...V P P= . Очевидно U V⊥ . Рассматриваем
линейные представления чисел (1) в таком базисе ( , )U V .
Кодирование числа x происходит в два этапа. Сначала число x
кодируется соответствующей тройкой (a, b, n), где a и b коэффициенты
отрицательно-определенной линейной формы
n nx aQ bP= − ранга n,
0, 0a b> < . На втором этапе тройка (a, b, n) кодируется по формуле (7)
задающей код троек чисел.
Кодирующий алгоритм
, ( )A BE x .
Вход: натуральное число x, последовательности натуральных
положительных чисел:
0 1 3 4, , ...; , , ...;A a a B b b= =
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
11
Результат: y = код (x).
Начало
Этап 1
1. Недетерминировано случайным (псевдослучайным) образом выбрать
ранг n.
2. Число x недетерминированным образом разложить в отрицательно-
определенную линейную форму ранга n, n nx aQ bP= − .
3. ( , , )z a b n← .
Этап 2
4. Сформировать линейную рекуррентную последовательность B .
1 2 1 1 1: 1, , 2.i i i iB B B b B B i+ + −= = = + >B
5. По ( , , )z a b n= вычислить:
1( || || , || ) (( || ) ( || )) ( || ) B m my C a n b n b n a n b n B b n B += + = + +% % ,
где 1( || ) ( || ) ma n b n B ++ <% .
Результат: y← .
Конец.
Недетерминированность шага 2 заключается в случайном выборе числа
0 1 0, ,n nk a a kP b b kP+= + = + , где
0 0n nx a Q b P= − — лево-каноническое
отрицательно-определенное представление числа x. Недетерминированность
шага 5 заключается в недетерминированном выборе ранга m.
Обозначим через
, ( )A BC x заключительный результат вышеописанного
кодирования числа x,
, ( )A By C x= .
Декодирующий алгоритм
, ( )A BD y
Начало
Вход:
, ( )A By C x= ; последовательности A, B.
Результат = x:
, ( )A BE x y= .
Декодирование происходит детерминировано в обратном порядке.
1. В базисе B разложить число y в максимальную лево-каноническую
линейную форму 1m my AB BB += + ;
2. Вычислить || , ||b n B a n A B= = −% ;
3. По ||b n и ||a n% вычислить n, b и a;
4. Вычислить исходное значение n nx aQ bP= − .
5. Результат x← .
Конец.
, ( )A BD y
Последовательности A и B считаем секретными симметричными
ключами.
Вышеописанную схему кодирования обозначим LRC(A, B) (LRC —
Linear Recurrence Coding).
Отметим, что на каждом шаге алгоритма кодирования
недетермининированный выбор соответствующих параметров может быть
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
12
реализован случайным образом путем использования параметров любых
доступных хаотичных процессов.
Предлагаемая схема кодирования обладает определенной доказуемой
криптостойкостью. А именно, наблюдение любого количества выходных
значений кодера без знания ключевых параметров не дает никакой
информации о входных значениях. Более точно, справедлива следующая
теорема.
Теорема 3. Пусть в системе LRC(A, B) задана последовательность
кодовых чисел
1 , 1 ,( ), ..., ( )A B k A B ky C x y C x= = .
Существует бесконечная последовательность A ́ такая, что
1 , 1 ,
( ), ..., ( )A B k nA B
y C x y C x′ ′
′ ′= = , где
1 ,..., nx x′ ′ некоторые числа, отличные
от 1,..., nx x . Множество таких последовательностей A ́ бесконечно
(континиум).
Доказательство. Пусть
0 1[ ; ,...]a aα ′ ′ ′= любое иррациональное число,
которое монотонно меньше
0 1, [ ; ,..., ]n
n n
n
P a a a
Q
α β
′
′ ′ ′= =
′
подходящая к α
рациональная дробь n-го порядка
nP ′ — числитель дроби,
nQ ′ — знаменатель.
Числа , 1,...,i i n i ni i
x a Q b P i k′ ′ ′= − = положительны и их кодирование
тройками ( , ,. )i i ia b n в базисе α ′ совпадает с соответствующими тройками
чисел ix в базисе α ′ .
Пусть
0 1: , ,...A a a′ ′ ′ последовательность, определяемая дробью α ′ .
Таким образом, в системе кодирования LRC(A ,́B) положительные числа
i i n i ni i
x a Q b P′ ′ ′= − получат такие же значения кодов, что и исходные числа
ix в системе LRC(A, B). Это означает, что, не имея никакой информации о
ключевой последовательности A, невозможно получить никакой информации
об исходном наборе 1,... kx x .
Теорема доказана.
Для ускорения процесса вычислений для выбора ключевой
последовательности A можно использовать только значения {1,2}ia ∈ . Даже
в этом упрощенном варианте выполняются условия теоремы 3 при условии,
что
0 1[ ; ,...]a aα = отлично от числа 1 3 [1,2,1,2,...]
2
+
= .
В системе симметричного кодирования LRC(A, B) последовательности A
и B являються секретными ключами. Их удобно задавать разложением в
цепные дроби квадратичних иррациональностей вида a b
c
+ . Таким образом
фактичными ключами являются числа (a, b, c).
Для усиления криптографической стойкости при помощи линейных
форм возможно внесение в исходное сообщение дополнительных случайных
параметров. Возможны такие варианты.
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
13
Пусть n исходное числовое сообщение. Выбираем случайное число
( ) ( ),r l r l m≤ . Кодируем m числом ( ) 1n ny m r P rP += + + , где
1nm r P ++ < . Другие
возможные комбинации максимальных линейных форм также могут быть
использованы.
Например: ( ) ( ) ( )( )1 1 1, || ,n n n n n nm r P rP m r P rP m H r P rP+ + +⊕ + + ⊕ +
где H(r) хеш функция.
1. Bellare M., Rogaway P.: Optimal Asymetric Encryption In: De Santis, A. (ed) Advances of
Cryptology: Proceedings of EURO-CRYPT '94 , LNCS, 1995. vol. 950. pp. 92–111.
2. Анисимов А. В. Кодирование данных линейными формами числовых
последовательностей. Кибернетика и системный анализ. 2003. № 1. С. 3–15.
3. Анисимов А. В. Представление чисел в смешанном базисе (2,3). Кибернетика и
системный анализ. 2009. № 4. С. 3–18.
4. Анисимов А. В. Представление чисел в двухбазисных системах. Кибернетика и
системный анализ. 2013. №4. С. 1–14.
5. Anisimov A. V. Prefix Encoding by Means of the (2,3) — Representation of Numbers. IEEE
Transactions on Information Theory. 2013. vol. 59. №4. pp. 2359–2374
6. Анисимов А. В., Завадский И. А. Помехоустойчивое префексное кодирование с
помощью нижнего (2,3) - представления чисел. Кибернетика и системный анализ.
2014. №2. С.1–15.
UDC 519.72
SYSTEM OF CRYPTOGRAPHIC
TRANSFORMATIONS OF NUMBERS BY MEANS
OF LINEAR RECURRENT FORMS
A.V. Anisimov
Taras Shevchenko National University of Kiev, Ukraine
Introduction. Two-level system of encoding integers by linear forms
aPn + bQn, where Pn and Qn are linear recurrent sequences. These sequences are
defined by factoring quadratic irrationalities into continued fractions. Firstly, a
number x is represented as a form
n nx aA bB= + , where /n nA B is a convergent
to some fixed quadratic irrationality. At the second stage the triple (a, b, n) is
encoded by a maximal linear form of another linear recurrent sequence
( ) 1, , n na b n cP dP +→ + . The sequences , ,n n nA B P are considered as hidden
symmetric keys given by coefficients of corresponding quadratic irrationalities.
Properties of such encodings are established.
The purpose of the article is to develop and study a nondeterministic system
of cryptographic integer encoding by means of linear recurrent sequences.
Methods. We used methods of continued fractions, properties of linear forms,
and bijective encoding of natural numbers.
Results. We proved as a theorem that such a system of encoding is absolutely
resistant to passive crypto-attacks. With some further additions it is also resistant to
stronger types of attacks.
Conclusion. The proposed system of integer encoding is easy to construct,
and it has some proven properties that allows using it as a primitive basic
procedure for light weighted cryptography.
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
14
Keywords: Linear forms, continued fractions, nondeterministic cryptography.
1. Bellare M., Rogaway P.: Optimal Asymetric Encryption In: De Santis, A. (ed) Advances of
Cryptology: Proceedings of EURO-CRYPT '94 , LNCS, 1995. vol. 950, pp. 92–111.
2. Anisimov A. V. Data Coding by Linear Forms of Numerical Sequences. Cybernetics and
Systems Analysis. 2003. N 1. P. 3–15.
3. Anisimov A. V. Integer representation in the mixed base (2,3). Cybernetics and Systems
Analysis. 2009. № 4. P. 3–18.
4. Anisimov A. V. Two-base numeration systems. Cybernetics and Systems Analysis. 2013.
№4. P. 1–14 .
5. Anisimov A. V. Prefix Encoding by Means of the (2,3)-Representation of Numbers. IEEE
Transactions on Information Theory. 2013. vol. 59. № 4. P. 2359–2374
6 Anisimov A. V. Zavadskyi I. A. Robust Prefix Encoding Using Lower (2,3) Number
Representation. Cybernetics and Systems Analysis. 2014. № 2. P.1–15.
Получено 3.10.16
А.В. Анисимов, 2016
ISSN 2519-2205 (Online), ISSN 0454-9910 (Print). Киб. и выч. техн. 2016. Вып. 186.
|