чётная или
нечётная в зависимости от чётности или нечётности его индекса.
Разобьем множество
)
;
(
n
g
S
на три подмножества, которые будем называть
соответственно: чётные, нечётные и смешанные. Любой набор (кортеж) из
n значных чисел будем называть чётным или нечётным, если все члены
данного набора состоят соответственно только из чётных или нечётных
элементов. Например, кортеж
k
x
x
x
x
x
a
2
0
4
2
2
является чётным, а кортеж
1
2
3
7
5
1
k
x
x
x
x
x
b
является нечётным. Кортеж называем смешанным, если хотя бы
два элемента в данном кортеже имеют позиции разных чётностей. Например,
1
2
2
2
1
k
k
x
x
x
x
c
. В результате получим три непересекающихся подмножества:
).
;
(
),
;
(
),
;
(
3
2
1
n
g
S
n
g
S
n
g
S
При этом имеем формулы:
(4)
).
;
(
)
;
(
)
;
(
);
;
(
)
;
(
)
;
(
)
(
3
2
1
3
2
1
n
g
S
n
g
S
n
g
S
n
g
S
n
g
S
n
g
S
g
S
n
Заметим, что любой элемент из последовательности (1), в частности, из
}
1
,
,
1
,
0
{
g
считается однозначным и будет в зависимости от номера индекса
элемента чётным или нечётным. В этом случае смешанные кортежи
отсутствуют, а их множество считается пустым. Следовательно, смешанные
кортежи существуют в случаях
2
n
.
171
Как известно из теории делимости целых чисел [1], всякое множество
целых чисел, состоящее из
g
элементов, попарно несравнимых по модулю
g
,
называется полной системой вычетов по модулю
g
, а последовательность
}
1
,
,
1
,
0
{
g
называется наименьшими неотрицательными вычетами по модулю
g
. На основании формулы Евклида (деление с остатком), каждое целое число
a
представляется однозначно в «многочленном» виде
(5)
;
1
1
1
1
1
g
k
k
g
k
k
k
k
a
a
a
a
a
g
a
g
a
g
a
a
где
g
j
k
a
k
g
j
g
a
g
a
;
1
,
,
2
,
1
,
,
0
,
1
выражает остаток при делении числа
a
на
g
, т.е.
1
0
;
g
a
a
bg
a
g
g
. Представление (5) называют также
систематическое представление числа
a
по основанию
.
g
На практике часто (в
криптографии, теории кодирования, нумерологии и др.) пользуются
некоторыми образованиями (кортежами), состоящих из слов, символов, а
также из кортежа многозначных чисел, расположенных друг за другом. В
наших рассмотрениях мы будем исследовать случай, когда основание числа
a
в
представлении (5) равно
.
10
g
Тогда будем иметь в качестве основного
множества
1
};
,
,
,
{
1
1
0
g
x
x
x
g
множество целых чисел, состоящее из полной
системы вычетов по модулю 10, т.е.
}
9
,
,
2
,
1
,
0
{
, и на их основе будем
рассматривать всевозможные
n
значные числа вида (3).
Следовательно, имеем следующие однозначные базовые множества:
(6)
}
8
,
6
,
4
,
2
,
0
{
)
1
;
10
(
};
9
,
7
,
5
,
3
,
1
{
)
1
;
10
(
2
1
S
S
.
Далее все
n
значные числа вида (3) формируются на базе элементов двух
базовых множеств:
},
8
,
6
,
4
,
2
,
0
{
)
1
;
10
(
};
9
,
7
,
5
,
3
,
1
{
)
1
;
10
(
2
1
S
S
где число элементов в
каждом из них поровну, т.е. по 5, а число смешанных элементов равно нулю.
Примеры:
1357591
a
нечётный семизначный кортеж, составленный из
нечётных чисел, принадлежащих множеству
)
1
;
10
(
1
S
,
2064248
b
чётный
семизначный кортеж, составленный из чётных чисел множества
)
1
;
10
(
2
S
и
1054749
c
смешанный семизначный кортеж, составленный из элементов
обоих множеств.
172
Далее исследуем вероятностный смысл каждого подмножества по
отношению к множеству
n
значных чисел для любого натурального числа
2
n
. и базовых однозначных подмножеств
)
1
;
10
(
),
1
;
10
(
2
1
S
S
.
Сформулируем общую задачу в общепринятом виде.
В ящике (урне) имеются шары трёх видов, пронумерованные
n
значными числами из множества
)
1
;
10
(
);
1
;
10
(
2
1
S
S
.
Другими словами, в урне
имеются шары, пронумерованные
n
значными числами, имеющими
только нечётные, чётные и смешанные цифры.
1. Найти общее количество всех
n
значных чисел, определить из них
количество с нечётными, чётными и смешанными цифрами кортежей.
2. При извлечении случайным образом одного шара из ящика, найти
вероятность
)}
(
{
n
N
X
P
p
i
i
появления каждого
n
значного числа.
3. Построить закон распределения дискретной случайной величины
)};
(
),
(
),
(
{
)
(
3
2
1
n
N
n
N
n
N
n
X
где
)
(
),
(
),
(
3
2
1
n
N
n
N
n
N
-
количество элементов в
каждом подмножестве, а также числовые характеристики случайной
величины
)
( n
X
:
математическое ожидание, дисперсия и стандарт.
Решение. Для полноты изложения сначала исследуем случай
.
2
n
Имеем:
,
25
2
}
99
;
;
93
,
91
;
;
19
,
17
,
15
,
13
,
11
{
)
2
;
10
(
1
1
N
S
.
20
2
}
88
;
86
;
84
;
82
,
80
;
;
28
,
6
2
,
24
,
2
2
,
20
{
)
2
;
10
(
2
2
N
S
Общее количество двузначных чисел равно
90
9
99
. Следовательно, число
смешанных двузначных чисел равно
45
45
90
, т.е.
45
3
N
. Следовательно, в
нашем случае мы получаем случайную величину с соответствующими
вероятностями:
)};
2
(
),
2
(
),
2
(
{
)
2
(
3
2
1
N
N
N
X
;
90
20
;
90
25
2
1
p
p
;
90
45
3
p
Таким образом, в этом случае закон распределения случайной величины
)
2
(
X
и таблица распределения будет выглядеть так:
2
X
2
1
N
2
2
N
2
3
N
2
P
90
25
90
20
90
45
173
Основные числовые характеристики находятся по известным формулам
(например, см.[2]):
,
89
,
33
)
2
(
2
3
1
i
i
i
N
p
МX
2
2
)]
2
(
[
)]
2
(
[
MX
X
M
D
n
X
;
268
,
126
237
,
11
n
X
n
X
D
. Аналогично рассматривается случаи
.
3
n
Решение задачи в общем случае. Для случаев
2
n
основное множество
)
;
10
(
n
S
распадается на три подмножества
n
значных чисел:
),
;
10
(
),
;
10
(
2
1
n
S
n
S
)
;
10
(
3
n
S
при этом условимся, что все чётные кортежи, для которых число ноль
находится спереди, учитывается только в одном единственном случае, когда
рассматриваются однозначные кортежи. В остальных случаях все числа,
представленные в кортеже должны быть
n
значными в соответствии с
формулой (5) т.е. старший коэффициент разложения
k
a
должен быть отличным
от нуля. Пусть
2
n
, тогда общее количество всех
n
значных чисел
вычисляется по формуле
1
1
10
9
1
10
1
10
n
n
n
n
N
. С
другой стороны
имеем:
)
(
)
(
)
(
3
2
1
n
N
n
N
n
N
n
N
. Нетрудно показать, что имеют место
равенства:
;
5
4
)
(
;
5
)
(
1
2
1
n
n
n
N
n
N
отсюда получим
1
2
5
9
1
1
3
n
n
n
N
.
Найдем соответствующие вероятности:
(7)
1
1
2
9
5
n
p
,
1
2
2
9
4
n
p
,
1
1
3
2
1
2
n
n
p
Закон распределения случайной величины
)}
(
),
(
),
(
{
3
2
1
n
N
n
N
n
N
n
X
задаётся следующей таблицей:
n
X
n
N
1
n
N
2
n
N
3
n
P
1
2
9
5
n
1
2
9
4
n
1
1
2
1
2
n
n
Далее, математическое ожидание, дисперсия и стандарт находятся по
известным формулам: именно
],
))
1
2
(
9
(
41
[
2
9
5
)
(
2
1
1
1
3
1
n
n
n
i
i
i
p
n
N
n
МX
аналогично находятся:
;
)]
(
[
)]
(
[
2
2
n
MX
n
X
M
D
n
X
n
X
n
X
D
при каждом .
n
На практике часто пользуются шестизначными числами, т.е. когда
6
n
.
Выпишем значения основных величин:
;
15625
6
;
900000
6
1
N
N
174
;
871875
6
;
12500
6
3
2
N
N
},
871875
;
12500
;
15625
{
)
6
(
X
;
9687
,
0
)
6
(
)
6
(
;
0139
,
0
)
6
(
)
6
(
;
0174
,
0
)
6
(
)
6
(
3
3
2
2
1
1
N
N
p
N
N
p
N
N
p
При
этом
выполняется равенство:
1
3
2
1
p
p
p
, т.е. мы имеем полную группу
событий. Теперь найдём числовые характеристики:
.
8575
,
302338
;
0635
,
8
9140878472
;
9375
,
845030
)
6
(
)
6
(
)
6
(
)
6
(
X
X
X
D
D
MX
Вывод: когда число знаков в номере шариков увеличивается, то число
наборов с четными цифрами убывает по сравнению с числом наборов с
нечетными цифрами, а число смешанных наборов стремительно растёт. Таким
образом, при кодировании указанными наборами естественно наиболее
выгодными являются наборы с четными цифрами, т.е. дешифровать случай с
четными наборами труднее в отличие от двух других случаев. Однако, всегда у
« взломщиков» остаётся надежда на случайность. Также отметим, что в общем
случае аналогичные задачи можно исследовать с иными условиями разбиения
элементов базового множества
1
};
,
,
,
{
1
1
0
g
x
x
x
g
. На этом мы ограничимся.
Литература
1. И.М. Виноградов «Основы теории чисел», Наука, Москва 1981 г., 176с
2. М.С. Бокаева, Д. Исмоилов, Н.Д. Сарбасова «Курс лекций по теории
вероятностей и математической статистике», ИнЕУ, Павлодар, 2014г, 430с (А4)
Капалова Н. А., Дюсенбаев Д.С.
ПОЗИЦИЯЛЫҚ ЕМЕС ПОЛИНОМДЫҚ САНАУ ЖҮЙЕСІНЕ
НЕГІЗДЕЛГЕН ШИФРЛЕУ АЛГОРИТМДЕРІНЕ СЫЗЫҚТЫҚ
КРИПТОТАЛДАУДЫ ҚОЛДАНУ
ҚР БҒМ ҒК «Ақпараттық және есептеуіш технологиялар институты»
Алматы, Қазақстан Республикасы
Дәстүрлі емес шифрлеу мен электрондық сандық қолтаңбаны қалыптастыру
және криптографиялық кілттерді тарату алгоритмдер мен әдістерін дамыту мен
175
зерттеуде позициялы емес полиномды санау жүйесін (ПЕПСЖ) қолдану
криптографиялық рәсімдердің сенімділігі мен тиімділігін айтарлықтай
арттырады [1-5]. Қалдықтар классының классикалық жүйесіне қарағанда
ПЕПСЖ модулдік негіздері коэффициентері екілік жүйеде болатын
келтірілмейтін көпмүшеліктерден (немесе GF(2) өрісінде) тұрады. Позициялы
емес полиномды санау жүйесін пайдаланып құрылған криптографиялық
алгоритмдердің криптографиялық беріктілігін бағалау үшін сызықтық анализ
жүргізілді.
Сызықтық криптоанализ – сызықтық емес теңдеулерден, кілтке, ашық және
жабық мәтінге қатысты сызықтық теңдеулер құру мүмкіндігіне негізделген [6].
Біріншіден, шифрлау алгоритм белгілі болуы тиіс. Екіншіден, сызықтық
теңдеулер жүйесін құрудағы сызықтық қиындық қаншалықты.
Жұмыстың негізгі мақсаты позициялы емес полиномды санау жүйесі негізінде
көпмүшеліктерді модуль бойынша көбейту арқылы шифрлау алгоритміне
сызықтық криптоанализ жүргізу әдістерін қарастыру.
ПЕПСЖ қалыптастыру [2-4] айтылған: осы негіздердің дәрежелері
??????
1
, ??????
2
, … , ??????
??????
болатын, сәйкесінше
??????
1
(??????), ??????
2
(??????), … , ??????
??????
(??????) (1)
GF(2) өрісінде келтірілмейтін көпмүшеліктер таңдалады.
Әрбір
?????? үшін GF(2
??????
??????
) кеңейтілген ақырлы өрісінде дәрежесі
??????
??????
болатын
??????
??????
(??????) -
келтірілмейтін көпмүшелігі бойынша GF(2) өрісінде GF(2)[x]/(
??????
??????
(??????))
факторсақиналарын құрайды.
Алдымен жұмыс негізі біреу болған жағдайы, яғни бір келтірілмейтін
көпмүшелік деп қарастырайық. Позициялы емес полиномді санау жүйесі
арқылы құрылған
??????(??????) ∗ ??????(??????) = ??????(??????)(?????????????????? ??????(??????)),
(2)
шифрлауды қарастырайық [2, 5].
Берілген (2) алгоритмде дешифрлау мына формула бойынша орындалады
??????(??????) ∗ ??????
−1
(??????) = ??????(??????)(?????????????????? ??????(??????)),
(3)
176
мұңдағы
??????(??????) ∗ ??????
−1
(??????) = 1(?????????????????? ??????(??????)).
∃??????(??????) ∈ ????????????(2)[??????]/(??????(??????)) - көпмүшелігі табылады және
??????(??????) ∗ ??????
−1
(??????) ⊕ ??????(??????) ∗ ??????(??????) = ??????(??????),
(4)
теңдігін қанағаттандырады.
Онда (4) теңдігінен төмендегідей теңдеулер жүйесін аламыз.
{
??????
??????−1
∗ ??????
??????−1
⊕ ??????
??????
∗ ??????
??????−2
= 0
??????
??????−1
∗ ??????
??????−2
⨁??????
??????−2
∗ ??????
??????−1
⨁??????
??????
∗ ??????
??????−3
⨁??????
??????−1
∗ ??????
??????−2
= 0
…
??????
??????−1
∗ ??????
1
⨁??????
??????−2
∗ ??????
2
⨁ … ⨁??????
1
∗ ??????
??????−1
⨁??????
??????
∗ ??????
0
⨁??????
??????−1
∗ ??????
1
⊕ … ⨁??????
2
∗ ??????
??????−2
= 0
??????
??????−1
∗ ??????
0
⨁??????
??????−2
∗ ??????
1
⊕ … ⨁??????
0
∗ ??????
??????−1
⨁??????
??????−1
∗ ??????
0
⨁ … ⨁??????
1
∗ ??????
??????−2
= ??????
??????−1
??????
??????−2
∗ ??????
0
⨁??????
??????−3
∗ ??????
1
… ⨁??????
0
∗ ??????
??????−2
⨁??????
??????−2
∗ ??????
0
⨁??????
??????−3
∗ ??????
1
⊕ … ⨁??????
0
∗ ??????
??????−2
= ??????
??????−2
…
??????
2
∗ ??????
0
⨁??????
1
∗ ??????
1
⨁??????
0
∗ ??????
2
⨁??????
2
∗ ??????
0
⨁??????
1
∗ ??????
1
⨁??????
0
∗ ??????
2
= ??????
2
??????
1
∗ ??????
0
⨁??????
0
∗ ??????
1
⨁??????
1
∗ ??????
0
⨁??????
0
∗ ??????
1
= ??????
1
??????
0
∗ ??????
0
⊕ ??????
0
∗ ??????
0
= ??????
0
(5)
?????? = (??????
??????−1
, ??????
??????−2
, … , ??????
2
, ??????
1
, ??????
0
) сандар тізбегі шифр мәтіннің бит түріңдегі пішіні
болғандықтан, олар бізге белгілі.
?????? = (??????
??????−1
, ??????
??????−2
, … , ??????
2
, ??????
1
, ??????
0
), ?????? = (??????
??????
, ??????
??????−1
, … , ??????
2
, ??????
1
, ??????
0
),
?????? = (??????
??????−1
, ??????
??????−2
, … , ??????
2
, ??????, ??????
0
) және ?????? = (??????
??????−2
, ??????
??????−3
, … , ??????
2
, ??????
1
, ??????
0
)
тізбектері белгісіз айнымалылар.
Қандай криптоанализ жүргізілсе де осы (5) теңдеулер жүйесінен шығады. Бұл
теңдеулер жүйесі кілттің, ашық және жабық мәтіннің мәңдерін
байланыстыратын басты схема.
Криптоаналитик ең алдымен шифртекстің әлсіз жерлерін іздейді, яғни
көпмүшеліктердің көбейтіндісінің дәрежесі келтірілмейтін көпмүшеліктің
(модуль негізі) дәрежесінен кіші болатын жағдайларды қарастырады. Өйткені,
ол жағдайларда (5) теңдеулер жүйесінде
??????
??????
және
??????
??????
айнымалыларына қатыссыз,
тек
??????
??????
және
??????
??????
айнымалыларына қатысты сызықтық теңдеулер жүйесі шығады.
Сондықтан кілтті таңдау кезінде ондай жағдайды жібермеуі керек.
Егер келтірілмейтін көпмүшеліктің
??????
??????
және
??????
0
коэффициенттерінің 1
болатынын ескерсек, онда (5) теңдеулер жүйесіндегі
??????
??????
айнымалыларынан
толық құтылып, теңдеулер жүйесі
??????
??????
,
??????
??????
және
??????
??????
айнымалыларына қатысты
болатын теңдеулердің саны n болады. Яғни жүйедегі теңдеулердің санын 2n-1-
177
ден n-ге дейін азайтамыз. Теңдеулер жүйесінің шешімдері көп. Бізге ақиқат
шешімін табу керек. Ол шешімді табу үшін әртүрлі әдістерді қолдануға болады.
??????
??????
айнымалылары ашық мәтіннің бит түріңдегі пішіні болғандықтан оларды
өзіміз жорамалдау арқылы береміз.
??????
??????
айнымалылары келтірілмейтін
көпмүшеліктердің коэффициенттері де белгісіз, сондықтан оларды теру арқылы
тексереміз.
Егер
?????? және ?????? айнымалылар тізбегін таңдадық десек, онда теңдеулер жүйесінде
?????? = (??????
??????−1
, ??????
??????−2
, … , ??????
2
, ??????
1
, ??????
0
) айнымалылары қалады.
Теңдеулер жүйесіндегі теңдеулердің саны мен айнымалылар саны тең.
Теңдеулер жүйесінің шешімі болуы үшін, осы жүйенің мәңдерінен құрылған
сәйкесінше матрицаның рангі айнымалылардың санына тең болу керек. Яғни,
теңдеулер жүйесінің шешімі
(??????
??????−1
′
, ??????
??????−2
′
, … , ??????
2
′
, ??????
1
′
, ??????
0
′
) болсын. Онда келесі
сандар тізбегін кему ретімен сәйкесінше коэффициенттері болатын
көпмүшеліктерге модуль бойынша көбейтеміз, дешфрлаудағы есептеулер
бойынша дешифрланған мәтін ашық мәтіннің ережелерін қанағаттандырмаса,
оқылмаса, онда келесі таңдауға көшеміз. Дәл осылай ашық мәтін шыққанша
орындалады. Келтірілмейтін көпмүшеліктердің дәрежесі артқан сайын, іздеу
қиындығы да артады (таблица 1-2).
Осы алгоритм
?????? = ∑
??????
??????
??????
??????=1
– кілттің ұзындығы болғандықтан теңдеудің әрбір
m
i
дәрежелі келтірілмейтін көпмүшелігіне сәйкес m қадам бойынша
тексеріледі.
Еңдігі жұмыс іздеу қиындығын есептеу. Сонда біз сызықтық криптоанализдың
тұрақтылығы қаншалықты екеніне жауап береміз.
Таблица 1. Кілтке қатысты ашық мәтінді іздеу мүмкіндігі.
Кілт ұзындығы
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Келтірілмейтін
көпмүшеліктердің
саны
2
3
6
9
18
30
56
99
186
335
630
1161
2182
4080
Ашық мәтенді
таңдау саны
8
16
32
64
116
116
232
464
928
1856
3712
7424
13456
13456
178
Таблица 2. Стандартты кеңейтілген файлдардың бастапқы байттары.
байт
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16
.docx 50 4b 03 04 14 00 06 00 08 00 00 00 21 00
.jpg
ff
d8 Ff e0 00 10 4a 46 49 46 00 01 01 01 01 2c
.pdf
25 50 44 46 2d 31 2e
.pdf* ef bb Bf 25 50 44 46 2d 31 2e
.htm
3c 21 44 4f 43 54 59 50 45 20 68 74 6d
.doc
d0 cf 11 e0 a1 b1 1a e1 00 00 00 00 00 00 00 00
.zip
50 4b 03 04
.exe
4d 5a 90 00 03 00 00 00 04 00 00 00 ff
ff
00 00
Екінші әдіс.
3
4
ықтималдылықпен
????????????⨁??????⨁?????? = 1 теңдігін қарастыруға болады.
Егер (5) теңдеулер жүйесіндегі айнымалылардың көбейтіндісін
???????????? = ??????⨁??????⨁1
өрнегімен жуықтау арқылы сызықтық теңдеулер жүйесін аламыз.
Егер теңдеулердегі
???????????? = ??????⨁?????? қателіктері жұп болып кездесетін болса, онда
олар ақиқаттықты береді. Осы құрылған теңдеулер жүйесінде алғашқы
әдістегідей арнайы таңдалған ашық мәтінтерді теру арқылы шығарамыз.
Кілт бөлікшесінің барлық мүмкін мәңдерін таңдауға айнымалылардың мүмкін
мәңдеріне келтірілмейтін көпмүшеліктердің санына көбейткенге тең. Ашық
мәтіннің статистикалық кездесу мүмкіндігі, сол көлемдегі барлық мүмкін
мәңдерінен кіші болғандықтан, теңдеулер жүйесін шешудегі мүмкіндігі ашық
мәтіннің кездесу мүмкіндігі мен келтірілмейтін көпмүшеліктердің санына
көбейткенмен тең. Кілтті толық табу үшін, осылай біртіндеп бөліктеп табуға
болады. Осы әдістерді тексеруде бағдарлама жазылуда, оның тексеру
мүмкіндігі кілт бөлікшелерінің ұзындығына тәуелді.
Мүмкін болу саны
16
64
256
832
2920
6400
19392
65328
237936
859696
3198256
11817520
41178512
96078992
Ықтималдылығы
0,0625
0,015625
0,003906
0,001202
0,000342
0,000156
5,16E
-05
1,53E
-05
4,2E
-06
1,16E
-06
3,13E
-07
8,46E
-08
2,428E
-08
1,041E
-08
179
Достарыңызбен бөлісу: |