close

Вход

Забыли?

вход по аккаунту

?

2308 drobotun b. n kriptosistemi s otkritim klyuchom ii b. n. drobotun g. a. sarsembaeva

код для вставкиСкачать
ISSN 1811-1807
РЫЛЫМИ ЖУРНАЛ
С ТОРАЙГЫРОВ АТЫНДАРЫ
s .:X s
J f i P
L
Павлодар
memaekettik
УНИВЕРСИТЕТ!
Ф
И
ЗН
К
А
-М
А
Т
Е
М
А
Т
И
К
А
Л
Ы
КС
Е
РИ
И
ПМУ ХАБАРШЫСЫ
ВЕСТНИК ПГУ
УД К 681.3.07
Б. Н. Дроботун, Г. А. Сарсембаева
КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ (И)
Предлагаемая статья является второй частью работы,
посвященной технологиям шифрования с открытым ключом. В
этой статье разрабатывается конкретная криптосистема,
позволяющая кодировать (и декодировать) сообщения,
записанные в алфавитах естественных языков.
1. Введение. Предлагаемая статья является второй частью
работы, посвященной технологиям шифрования с открытым ключом.
серия ФИЗИКО-МАТЕМАТИЧЕСКАЯ. 2013. №1
101
т т хят ж яю пю ю ш кяаю ж ят ш ш т т ш вт вт я& у^аят т т ит ят ят
В этой статье разрабатывается конкретная криптосистема.
позволяющая кодировать (и декодировать) сообщения, записанные в
алфавитах естественных языков.
Значительное внимание в работе уделяется построению и анализу
примеров, посредством которых демонстрируются возможности
построенной криптосистемы.
Роль примеров подобного содержания, сопровождающих процесс
обучения естественно-математическим дисциплинам в период
повсеместного внедрения коммуникационных и информационных
технологий трудно переоценить.
Это связано с тем, что: «... как показывает история развития
образовательных систем, отражающая историю развития общества,
характеру примеров, задач и упражнений, аргументации и
демонстрационному сопровождению процесса обучения в рамках
любой
специальности
прикладного
характера
традиционно
свойственно отражение специфики деятельности человека в ее
массовом проявлении» [1, с. 20].
В настоящее время содержание и особенности этого
демонстрационного сопровождения все еще определяют, в основном,
идеи и представления, отражающие процессы механизации трудовой
(то есть физической) деятельности человека. Тем не менее, с
наступлением эры машинной математики, кибернетических устройств
и робототехники, то есть эры повсеместного внедрения
автоматических систем, в той или иной степени моделирующих
мыслительную деятельность человека, подходы к разработке таких
примеров, задач и упражнений, выбору аргументов и демонстраций
должны постепенно меняться. Уже на языковом, ассоциативном
уровне такое показательно-демонстрационное сопровождение должно
вводить в мир образов и идей, обеспечивших приход эры
информационных и коммуникационных технологий.
С этих позиций, приведенные в работе примеры наиболее
показательным образом вводят в область приложений алгебры и
дискретной математики.
2.
П рим еры применения. Продемонстрируем технологию
применения криптосистемы < {rr,e}\{d\п} > на конкретном примере.
102
ISSN 1811-1807. Вестник ПГУ
ш$т2ттшш!8^тшттт1гтвт&эшэшш!>%&т№&&вшз&т№ттшзёш>
В качестве простых чисел р и q выбираем, соответственно,
числа 3 и 11. Тогда п = р -д = 3*11 =33. Понятно, что число
и
= 33 не
только теоретически, но и практически можно легко разложить на два
простых множителя. Т. е. криптосистема предлагаемого примера
может быть рассекречена, при необходимости, без особого труда. Но,
в данном случае, значимость примера определяется не надежностью,
предложенного в нем шифра, а демонстрационными задачами,
решение которых заведомо предлагает единство относительной
простоты
и доступности для
восприятия с детальным
воспроизведением всех технологических процессов.
Здесь уместно вспомнить классический пример о беседе двух
математиков, когда один из них пытался пояснить суть своих
результатов другому, используя сложнейшие построения в п -мерном
пространстве и трудно воспринимаемую систему символических
обозначений. Второй же математик, остановив его, попросил
рассказать, как все это выглядит в случае п = 2.
В предложенном примере (р{п) = <р(3 -11)= (р{Ъ) •<р{\ 1) = 2 •10 —20 и
в качестве параметра е можно взять число 13. Решая, далее, сравнение
ed = l(mod«), которое, в рассматриваемом случае, примет вид
13d = l(mod20), находим параметр d = 17. Таким образом, мы построили
криптосистему < {33;13};{17;33} > с открытым ключом {33;13}.
Пусть, к примеру передаче подлежит сообщение
X =<11100101010010 >.
Находя из неравенства 2* < 33 < 2*"' вида (1) длину блока в
разбиении последовательности X , получаем, что к = 5. Разбивая эту
последовательность справа - налево на блоки длины 5, будем иметь
1110
01010
10010
I ---- — :---I -------- ----(I)
------— ---1—ый блок
2 —ой блок
3 -и й блок
Т.к. первый блок в разбиении (1) имеет длину 4, то дополняем его
до блока длины 5, приписывая один 0 слева. По полученным блокам
сг, =<011Ю>; а } =<01010 >; сг3 =<10010>,
находим, соответственно, натуральные числа Л/, =14; М 2 =10 и
М, =18, двоичными разложениями которых эти блоки являются.
Используя соотношение С: =M '(m odn) / = 1,2,3. шифруем числа
серия ФИЗИКО-МА ТЕМА ТИЧЕСКАЯ. 2013. №1
М ,;Л/2;Л/3,
соответственно
числами
103
С, a !4l3(mod33);
С, = 1013(пкх133); С3 =18’J(rnod33).
Напомним, что С,;С,;С} выбираются, как наименьшие
неотрицательные вычеты по модулю л = 33 чисел 1413;10|3;1813,
соответственно.
Отсюда:
С, ■ 1413 = (142)6 •14 а 316 •14 а (312)3 •14 ■ 43 •14 = 896 a 5(mod33);
С2 я 1013 = (102)6 • 10 ш I6 • 10 a 10(mod33);
С, a 18” а (18а)‘ •18 = 27* 18 а (271)3 •18 = З3 •18 = 486 = 24(mod33).
Записями найденных чисел С, = 5;С3 = 10;С3 = 24 в двоичной
системы счисления будут новые двоичные блоки:
00101
01010 11000
С,
С2
С}
Формируя из этих блоков единую двоичную последовательность,
получаем шифрованное сообщение
Х'=< 001010101011000 >,
которое и будет отправлено.
Адресат, получив это сообщение, по личному коду {17;33}
находит из соотношения (1) длину блока к = 5, разбивает (справа налево) двоичную последовательность X ' на блоки этой длины и по
полученным блокам восстанавливает десятичные представления этих
двоичных блоков, т. е. числа С, =5; С2 = 10; С, = 24. При
«расшифровке» найденных чисел по формуле М, = С'1(mod 33)
(i —1,2,3), адресат должен будет найти наименьшие неотрицательные
вычеты чисел 5|7;10|7;2417по модулю 33.
Согласно теоретическим концептам, заложенным в основу
построения криптосистемы с открытым ключом, эти вычеты должны
быть равны, соответственно, 14=М,; 10 = Л/2; 18=М ,. Действительно,
проводя необходимые вычисления, получаем:
5П = (53)5 •52 = (125)5 •25 = (262)2 •26 •25 s 162 •24 а 25 •23 = 14(mod33);
1017 = (103)5 •102 л (1000)5 •100 s 10 •1a 10(mod33);
24*7 = (242)8 •24 а (152)4 •24 а (272)2 •24 = 9 ■24 а 216 а 18(mod33)
104
ISSN 1811-1807. Вестник ПГУ
Переводя, далее числа 14; 10; 18 в двоичную систему счисления,
адресат получает двоичные блоки < 01110 >;< 01010 >;< 10010 >.
Формируя из этих блоков единую двоичную последовательность, он
формирует расшифрованный «текст»
X =< 011100101010010 >
переданного (зашифрованного) сообщения.
3.
Криптосистемы с открытым ключом для работы с
сообщениями в алфавитах естественных языков. В заключительной
части работы предпринимается опьгг построения криптосистемы с
открытым ключом, применяя которую можно будет кодировать (и,
соответственно, декодировать) сообщения, заданные в алфавите
казахского языка и в алфавитах других естественных языков. Т.к.
алфавит этого языка содержит 42 буквы, то, с учетом необходимости
кодирования (кроме букв) еще и некоторых вспомогательных символов
(таких, как «,» - запятая, «:» - двоеточие, «!» - восклицательный знак и
т.п.), параметр п строящийся криптосистемы должен удовлетворять
условию п > 52. Если в качестве простых чисел р и q взять,
соответственно, числа 5 и 13, то полученное число n = p q = 5-13 = 65
будет удовлетворять вышеприведенному условию.
Т.к. <р(п) = <р(65) = <р(5 13) —4 12 = 48, то в качестве параметра е
можно выбрать число 11. Решая сравнение 11d = l(mod48), находим
d = 35. Вычислив все параметры, получаем криптосистему
<{65;11};{35;65> ^ с открытым ключом {65j11].
Отождествим теперь буквы алфавита казахского языка с
порядковыми номерами их следования в этом алфавите. Т.к. л = 65,
то, находя натуральное число к из условия 2* < 65 < 2**', получаем,
что к = 6. Таким образом, номер каждой буквы алфавита казахского
языка можно записать в виде двоичной последовательности длины 6.
В предлагаемой далее таблице (смотри таблицу 1) даны буквы этого
алфавита, указаны их порядковые номера и двоичные разложения
этих номеров, как чисел, заданных в десятичной системе счисления.
серия ФИЗИКО-МА ТЕМА ТИЧЕСКАЯ. 2013. N91
105
Таблица 1 - Двоичное представление букв и вспомогательных
символов алфавита казахского языка
А
1
000001
к
14 001110
¥
27
ОПОИ
э 40
101000
0
2
000010
к
15
001111
Y
28
011100
IO
41
101001
Б
В
Г
F
3
000011
л
16
010000
ф
29
011101
я
42
101010
010001
X
30
011110
43
101011
44
101100
4
Д
000100
м
17
5
000101
н
18
010010
h
31
011111
6
7
000110
19
010011
Ц
32
100000
000111
н
о
20
010100
100001
0
п
21
010101
ч 33
111 34
100010
22
010110
35
45
101101
9
46
101110
47
ЮПИ
100011
(
48
110000
)
Е
Е
8
001000
9
001001
Ж
10
001010
р
23
010111
щ
ъ
36
100100
3
11
001011
с
24
011000
ы
37
100101
И
12
001100
т
25
011001
I
38
й
13
001101
У
26
011010
ь 39
}
-
49
110001
50
110010
100110
;
«
51
110011
100111
»
52
110100
Пусть требуется передать сообщение: АСТАНА, предварительно
зашифровав его средствами построенной криптосистемы. Сведем все
необходимые для этого данные в единую таблицу (смотри таблицу 2).
В 1-ой строке этой таблицы указаны буквы передаваемого сообщения
в порядке их следования в этом сообщении, во 2-ой сгрокс обозначения А/ (/ = 1,2,3,4,5,6) порядковых номеров этих букв в
алфавите казахского языка, в 3-ей строке —их порядковые номера,
в 4-ой строке - двоичные разложения этих номеров.
Таблица 2 - Двоичное представление сообщения «АСТЛ11Л»
н
А
А
т
с
мг
М,
м,
М5
Щ
1
18
1
24
25
000001
011000
011001
000001
010010
А
М„
1
000001
Таким образом, передаче подлежит сообщение
X =< 000001011000011001000001010010000001 >.
являющееся двоичной версией исходного сообщения: АСТАНА.
106
ISSN 1811-1807. Вестник ПГУ
^ышш№шш№жшшж*в№шшшшяшаештшаезвзш&е1№№шжмякавтштй
Шифруя числа М, =1;Л/2 = 24;Л/3 = 25;М 4 =Л;М5 =18;Л/6 = 1,
на основе соотношения С( = Mf (mod65), получаем:
C1= l11sl(mod65)
С2 = (242)5 •241 (562)2 •56 •24 = 162 ■56 •24 = 19(mod65)
С31 25" = (252)5 •25 = (402)? •40 •25 = 402 •40 •251 25(mod65)
C4 =l"=l(m od65);
С5 =18и =(182)s •18 = (642)2 -64 ■18 = 1-64- 18 = 47 = 25(mod65);
C6 s l M= l(mod65).
Записывая найденные наименьшие неотрицательные вычеты
С, = 1; С2 = 19; С3 = 25; С4 = 1; С5 = 47; С6 -1
в двоичной системе
счисления, получим следующие блоки длины 6:
000001
010011
011001
000001
101111
000001
блок С ,
блок Щ блок Щ блок С 4 блок С5 блок С6
Таким образом, готовый к отправке зашифрованный вариант X '
исходного сообщения X будет иметь вид:
Х'=< 000001010011011001000001101111000001 >
Как и в примере из пятого параграфа, адресат, получив
сообщение X ' , по значению параметра п = 65 из своего личного кода
находит длину блока, на которые нужно будет разбить это сообщение.
При этом, он использует неравенство
2* < 65 < 2Ы.
Получив из этого неравенства значение к= 6 , он разбивает
сообщение X ' (справа - налево) на блоки длины 6:
000001
1- и блок
010011
| 011001
2 —ой блок
3 — им блок
000001
101111
4 - ый блок 5 —ый блок
000001
6 - ой блок
Восстановив по полученным двоичным блокам числа
Ц = 1; С2 -19; С3 =25; С4 =1; С5=47; Я 1,
адресат находит соответствующие им номера А/,;М2;А/3;Л/4;Л/5;Л/б
букв алфавита, используя соотношение Л/, = С"*(modи), при d = 35,
п = 65, / = 1;2;3;4;5;6:
серия ФИЗИКО-МАТЕМАТИЧЕСКАЯ. 2013. N91
107
тш т т е*шж11тмжш>№&тттт№йштж1т№»9тт11тя1тяжя№Р.9№»
М\
=
I 35
= l( m
o d 3 5 ) ;
М2 = !935 = (192) '7 •19 з (362)8 •36 •19 s (612)4 •36 •19 s (162)2 ■36 • 19 s
= 612 ■36 •19 э 16 •36 •19 s 24(mod65).
Л/3 =253S=(25z)f7-25з(4 0 2)8 -40-25 = (402)4 •40 •25 = (402)2 -40 25
= 402 ■40 •25 з 25(mod65).
Af4 = l3Ssl(mod35);
Ms =473S =(472)17 ■47 =(642)8 •64-47 = Iе •64 ■47a !8(mod65):
A/6 = l || a l(mod35).
По найденным порядковым номерам
А/, = 1;М2 = 24;М3 = 25;Л/4 = 1;М5 = 18;Л/6 = I
букв А; С; Т; А; Н; А он получает дешифрованное сообщение
АСТАНА.
Пусть теперь требуется передать сообщение:
«АЛГА, КАЗАКСТАН!»
Вновь сведем все данные в единую таблицу (смотри таблицу 3)
Таблица 3 - Двоичное представление сообщения «AJ1FА, КАЗАКСТАН!»
г А у к А 3 А к с Т Л 11 1
А л
М7 мя м., М,о М„ М}1 Мп »» Л/,,
А/, мг Л/, ц Ms к
1
00
00
01
16
01
00
00
6
00
01
10
1
00
00
01
43
10
10
11
15
00
11
11
1
00
00
01
11
00
10
11
1
00
00
01
15
00
11
11
24
01
10
00
25
01
10
01
1
18
00
00
01
01
00
10
Таким образом, передаче подлежит сообщение
Х = <000001010000000110000001101011001111000001
001011000001001111011000011001000001010010101!0О>
Шифруя числа
Л/, = 1;Л/2 = 16;Л/з =6;Л/4 = 1;Л/5 =43 \М6 = 15;М7 = |л / 8 = 11;
Л/, = 1; М101 15;Ми = 24; Л/12 = 25;Л/, 31 1; Л/14 = 18; М1$= 44.
на основе соотношения С, s A/'(mod65). получаем:
44
10
11
00
ISSN 1811-1807. Вестник ПГУ
108
С,= lM=l(mod65);
С 2 s l 6 11 =(162)5 -16=(612)2•61-16 = 61-6M6s61(mod65)
C3 нб" = (62)5 -6 = (362)2 -36-6 = 612 -36-6 = 16-36-6 = ll(mod65)
C4 = ln = l(mod65)
c 5 S 43'1= (432)s •431 (292)2 •29 •431 16■29 •43 1 62(mod65)
C6 = 15n =(152)5 -15 = (302)2 -30-15 = 35-30-15 = 20(mod65)
C7 = l“ = l(mod65)
Cg = 11" =(112)5 -11 = (562)2 -56*11=61-56-1 l = 6(mod65)
C9 = lu =l(mod65)
C10= 15n = (152)s •15 = (302)2 ■30 •15 = 35 -30 •15 = 20(mod65)
Cn s 24'1= (242)5 •24 s (562)2 •56 •241 61 •56 •24119(mod65)
CI21 25“ = (252)5 •25 i(4 0 2)2 •40 ■251 40 ■40 •25125(mod65)
Ci3 = l" =l(mod65)
C14= 18n =(182)5 -18s(642)2 -64-18 = l2 -64- 18=47(mod65)
C15г 44'11 (4421 ■44 =(512)2 •51 •44112 •51 •44 1 34(mod65).
Записывая найденные наименьшие неотрицательные вычеты
С, =1;С2 =61;С3=11;С4 =1;С5 =62;Сб =20;С7 =1;С8 =6;С9 =1;С10=20;
I , = 19;С121 25;С13j l;Cl4 = 47;CIS = 34
в двоичной системе счисления, получим следующие блоки длины 6:
000001 111101 001011 000001 111110 010100 000001 001000
|
I
I
I
■
S
000001 010100 010011 011001 000001 101111 100010
с9
с10
I
ЯГ
с
с12 ^13
с
с14 '-'1
с5
^11
Таким образом, готовый к отправке зашифрованный вариант X'
исходного сообщения х будет иметь вид:
Х'=
<
000001111101
001011000001111110
010100
000001001000000001 010100 010011011001000001101111100010>
Получив это сообщение, адресат действует по той же схеме, что
была продемонстрирована в предыдущем примере. Приводимые далее
вычисления показывают, что при декодировании сообщения X'
адресат действительно получит порядковые номера букв исходного
сообщения:
серия ФИЗИКО-МАТЕМАТИЧЕСКАЯ. 2013. №1
109
щвбавай«ееэеаша&щаб*06§ваseas*068836* * «0шэе5й01э®байнб^0*9081;*вез83(!!(щ?нс«.'*ш>
«АЛГА, КАЗАХСТАН!»
I35 = l(mod35).
6 l 35 = ( 6 1 2 ) 17 61 s ( 1 6 2 )R 16 -61 s (6 1 2) 4 16-61 = ( I 6 2) 2 -16 61 s
= 612 • 16-61 = 16-16-6l = 16(mod35).
II35 =(112)'7 - l l s ( 5 6 2)8 56 I1M 162)4 56 11 = (612)2 -56 •11 = 162 -56-11 =
=61-56-1 l=6(mod35).
I35 =l(mod35);
623S =(622)17 •62s(92)1' -9-62=(162)4 -9||2 =<6:!l')2 -9-62=162 -9-62 =
= 61-9-62 = 43(mod35).
203S = (202)17 -20э(Ю 2)" -10-20s(353)4 10-20г(552)2 l0-20 = 352 ■10 20 =
=55 10-20=15(mod35).
I35 = I(mod35);
63U ( 6 2)17 -6 = (362)* -36-6 = (612)4 -36-6 = (l62)2 -36 6 = 6I2 -36 6 =
= 16-36-6=1 l(mod35).
I35 =l(mod35);
2035 = (2 0 2)'7 -20 s ( 1 0 2)* • 10-20s (352)4 -10- 20 s (552)2 • 10-20 з
= 352 10 ■2 0 =55 • 10 •20 =15(mod35).
1935 = (I92)17 • 19 s (362)* -36-19 s (6 12) 4 36 I 9 s ( l 6 2)2 36 19 =
= 612 -36 19 = 16-36-J9 = 24(mod35).
253s = (252)17 •25 s (402)* •40 •25 = (402)J -40 •25 s (402)2 •40 25 =
= 402 •40•25= 40•40•25 = 25(mod35).
I15 = l(mod35);
4735 = (472)17 47 i( 6 4 2)" 64 47 1 1* •64 47 s 18(mod 35);
34 35 = ( 3 4 2)'7 -34 = ( 5 12)" 5 1 34 = 1* 51 34 = 4 4 (m o d 3 5 ).
Аналогичным образом, отождествляя буквы алфавита русского
языка с порядковыми номерами их следования в этом алфавите,
построим криптограмму с открытым ключом для шифрования
сообщений, записанных на русском языке. Т.к. алфавит русского
языка содержит 33 буквы, то, с учетом необходимости шифрования
символов пунктуационного назначения, параметр п криптосистемы
110
ISSN 1811-1807. Вестник ПГУ
должен удовлетворять условию п> 33. Из неравенства 2* <33<2*+|
находим, что к = 6, т. е. для того, чтобы зашифровать все буквы
русского алфавита и некоторые дополнительные символы, нужно
использовать блоки длины 6, как и при шифровании сообщений в
алфавите казахского языка.
Таким
образом,
построенная
ранее
криптосистема
({65;11},{35;65}), может быть применена и при шифровании
сообщений в алфавите русского языка.
В этом случае, исходная таблица будет иметь следующий вид:
(смотри таблицу 4).
Таблица 4 - Двоичное представление букв и вспомогательных
символов алфавита казахского языка.
А
Б
В
Г
д
Е
Е
Ж
3
И
И
К
1
2
3
4
5
6
7
8
9
10
11
12
000001
000010
000011
000100
000101
000110
000111
001000
001001
001010
001011
001100
л
м
Н
о
п
р
с
т
У
ф
X
ц
13
14
15
16
17
18
19
20
21
22
23
24
001101
001110
001111
010000
010001
010010
010011
010100
010101
010110
010111
011000
ч
ш
щ
ъ
ы
ь
э
ю
я
,
-
25
26
27
28
29
30
31
32
33
34
35
36
011001
ОПОЮ
011011
011100
011101
011110
011111
100000
100001
100010
100011
100100
СПИСОК ЛИТЕРАТУРЫ
!. Гончаров, С. С., Дроботун, Б. Н., Никитин, А. А. О логико­
алгебраической составляющей математического образования (I).
// Вестник ЕНУ им. Гумилева : Астана, 2012. -№ 4 . - С. 15-22.
Павлодарский государственный университет
имени С. Торайгырова, Павлодар.
Материал поступил в редакцию 20.03.13.
серия ФИЗИКО-МАТЕМАТИЧЕСКАЯ. 2013. Ыя1
111
твтштввеж&зтш&ш&йтзштвэттвтттэтштэвтшя.умш'ътт'ят
Б. Н. Дроботун, Г. А. Сарсембаева
Ашык кктгпен берЬтген криптожуйелер (II)
С. Торайгыров атындагы
Павлодар мемлекетгж университет!, Павлодар к.
Материал 20.03.13 редакцияга тусть
В. N. Drobotun, G. A. Sarsembayeva
Public-key cryptosystems (II)
Pavlodar State University named after S. Toraigyrov, Pavlodar.
Material received on 20.03.13.
Берьгген мсщала ашъщ кмтпен шифрлеу технологияларына
арналган жумыстьщ eKimui бел(ли болып табшады. Бул
макрлада жаратылыстану mindepi ёлтбшнде жазылгач
хабарламаларды кодтауга (жэне цайта кодтауга) мумюндт
беретш нацты криптожуйе цурастырылады.
The present article is the second pait of technology in public key
ciyptography. In this paper, we develop a specific cryptosystem to encode
(and decode) messages written in alphabets of natural languages.
Документ
Категория
Без категории
Просмотров
1
Размер файла
336 Кб
Теги
2308, otkritii, kriptosistemi, sarsembaeva, drobotun, klyuchom
1/--страниц
Пожаловаться на содержимое документа