forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Information Security.tex
736 lines (568 loc) · 59.4 KB
/
Information Security.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
\documentclass[10pt,a4paper,openany]{book}
%\documentclass[12pt,report,russian]{ncc}
%\usepackage{a4wide}
% Для векторых русских шрифтов в PDF не забудьте установить пакеты cm-super & cm-unicode
\usepackage{cmap} % Поддержка поиска русских слов в PDF (pdflatex)
\usepackage[X2, T2A]{fontenc}
%\usepackage[T2, OT1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,german,italian,latin,russian]{babel}
\usepackage{indentfirst} % Красная строка в первом абзаце
%\usepackage{misccorr}
%Может быть установлено 8pt, 9pt, 10pt, 11pt, 12pt, 14pt, 17pt, and 20pt
%\usepackage[12pt]{extsizes}
%\usepackage[mag=1000,a4paper,left=3cm,right=2cm,top=2cm,bottom=2cm,noheadfoot]{geometry}
% Подключение amsmath также даёт поддержку автоматических \dots
% см. http://tex.stackexchange.com/questions/77737/dots-versus-ldots-is-there-a-difference
% см. http://tex.stackexchange.com/questions/117730/what-is-the-difference-between-ldots-and-cdots
\usepackage{amsmath} % разрешить \texttt и аналогичные в формулах
\usepackage{amssymb} % дополнительные математические символы
\usepackage{graphicx} % поддержка изображений
%\usepackage{amsfonts, eucal, bm, color, }
\usepackage{algorithm, algorithmic} % 'algorithm' environments
\floatname{algorithm}{Алгоритм}
\usepackage{arydshln} % dash lines in tables
\usepackage{caption} % titles for figures
\usepackage{enumerate}
\usepackage{fancybox} % страница в рамке
\usepackage{float} % sub figures
\usepackage[totoc=true]{idxlayout} % балансировка индексов на последней странице, индекс в ToC
\usepackage{lscape} % поддержка поворота страниц на 90 градусов для широких таблиц
\usepackage{makeidx} % index
\usepackage{multicol} % поддержка колонок
\setlength{\columnsep}{0.1cm}
\usepackage{multirow} % multirow cells in tables
\usepackage{subfig} % sub figures
\usepackage{tikz} % векторная графика внутри TeX
\usepackage{tablefootnote} % footnote в таблицах
\usepackage{wrapfig} % sub figures
\usepackage[left=1.84cm, right=1.5cm, paperwidth=14cm, top=1.8cm, bottom=2cm, height=19.8cm, paperheight=20cm]{geometry}
\usepackage[parentracker=true,
backend=biber,
hyperref=auto,
language=auto,
citestyle=gost-numeric,
defernumbers=true,
bibstyle=gost-numeric,
sortlocale=ru_RU
]{biblatex} % библиография по ГОСТу
\addbibresource{bibliography.bib}
% поддержка гиперссылок; гиперссылки в pdf, должен быть последним загруженным пакетом
\ifx\pdfoutput\undefined
\usepackage[unicode,dvips]{hyperref}
\else
\usepackage[pdftex,colorlinks,unicode,bookmarks]{hyperref}
\fi
%\paperwidth=16.8cm \oddsidemargin=0cm \evensidemargin=0cm \hoffset=-0.33cm \textwidth=13.2cm
%\paperheight=24cm \voffset=-0.4cm \topmargin=0cm \headsep=0cm \headheight=0cm \textheight=19.8cm \footskip=0.9cm
% параметры PDF файла
\hypersetup{
pdftitle={Защита информации},
pdfauthor={Э. М. Габидулин, А. С. Кшевецкий, А. И. Колыбельников, С. М. Владимиров},
pdfsubject=учебное пособие,
pdfkeywords={защита информации, криптография, МФТИ}
}
% добавить точку после номера секции, раздела и т.~д.
\makeatletter
\def\@seccntformat#1{\csname the#1\endcsname.\quad}
\def\numberline#1{\hb@xt@\@tempdima{#1\if&\else.\fi\hfil}}
\makeatother
% перенос слов с тире
%\lccode`\-=`\-
%\defaulthyphenchar=127
% изменить подписи к рисункам, таблицам и т.~д.
\captionsetup{labelsep=endash} % Нумерационный заголовок и текст разделяются тире
\captionsetup{textformat=simple} % Текст подписи будет напечатан как есть
%\captionsetup[table]{position=above} % вертикальные отступы подписи таблицы для случая, когда подпись вверху
%\captionsetup[figure]{position=below} % вертикальные отступы подписи рисунка для случая, когда подпись внизу
%% стиль главы и секции вверху страницы
%\pagestyle{fancy}
%%\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
%\renewcommand{\sectionmark}[1]{\markright{#1}{}}
%
%%\fancyhf{}
%%\fancyfoot[СE,CO]{\thepage}
%%\fancyhead[LE]{\textsc{\nouppercase{\leftmark}}}
%\fancyhead[RO]{\textsc{\nouppercase{\rightmark}}}
%
%\fancypagestyle{plain}{ %
%\fancyhf{} % remove everything
%\renewcommand{\headrulewidth}{0pt} % remove lines as well
%\renewcommand{\footrulewidth}{0pt}}
% запретить выходить за границы страницы
\sloppy
\newtheorem{theorem}{Теорема}[section]
\newtheorem{lemma}[theorem]{Лемма}
\newtheorem{definition}[theorem]{Определение}
\newtheorem{property}[theorem]{Утверждение}
\newtheorem{corollary}[theorem]{Следствие}
%\newtheorem{algorithm}[theorem]{Алгоритм}
\newtheorem{remark}[theorem]{Замечание}
\newcommand{\proof}{\noindent\textsc{Доказательство.\ }}
%\newtheorem{example}{\textsc{\textbf{Пример}}}
\newcommand{\example}{\textsc{\textbf{Пример.}} }
\newcommand{\exampleend}
\DeclareMathOperator{\ord}{ord}
\newcommand{\set}[1]{\mathbb{#1}}
\newcommand{\group}[1]{\mathbb{#1}}
\newcommand{\E}{\group{E}}
\newcommand{\F}{\group{F}}
\newcommand{\GF}[1]{\group{GF}(#1)}
\newcommand{\Gr}{\group{G}}
\newcommand{\R}{\group{R}}
\newcommand{\Z}{\group{Z}}
\newcommand{\MAC}{\textrm{MAC}}
\newcommand{\HMAC}{\textrm{HMAC}}
\newcommand{\PK}{\textrm{PK}}
\newcommand{\SK}{\textrm{SK}}
\newcommand{\langde}[1]{нем. \foreignlanguage{german}{\textit{#1}}}
\newcommand{\langen}[1]{англ. \foreignlanguage{english}{\textit{#1}}}
\newcommand{\langit}[1]{итал. \foreignlanguage{italian}{\textit{#1}}}
\newcommand{\langlat}[1]{лат. \foreignlanguage{latin}{\textit{#1}}}
% Для раздела с задачами
\newcommand{\taskinit}{\newcounter{task-section}\setcounter{task-section}{0}\newcounter{task-number}}
\newcommand{\tasksection}{\addtocounter{task-section}{1}\setcounter{task-number}{0}}
\newcommand{\tasknumber}{\textbf{№ \addtocounter{task-number}{1}\arabic{task-section}.\arabic{task-number}.}~~}
%Наконец, существует способ дублировать знаки операций, который мы приведём безо всяких пояснений. Включив
%\newcommand*{\hm}[1]{#1\nobreak\discretionary{}{\hbox{\mathsurround=0pt #1}}{}}
%в преамбулу, можно написать $a\hm+b\hm+c\hm+d$, при этом в формуле a\hm+b\hm+c\hm+d при переносе знак + будет продублирован.
% Дублирование символов бинарных операций ("+", "-", "="), набранных в строчных формулах, при переносе на другую строку:
%%begin{latexonly}
%\renewcommand\ne{\mathchar"3236\mathchar"303D\nobreak
% \discretionary{}{\usefont
% {OMS}{cmsy}{m}{n}\char"36\usefont
% {OT1}{cmr}{m}{n}\char"3D}{}}
%\begingroup
%\catcode`\+\active\gdef+{\mathchar8235\nobreak\discretionary{}%
% {\usefont{OT1}{cmr}{m}{n}\char43}{}}
%\catcode`\-\active\gdef-{\mathchar8704\nobreak\discretionary{}%
% {\usefont{OMS}{cmsy}{m}{n}\char0}{}}
%\catcode`\=\active\gdef={\mathchar12349\nobreak\discretionary{}%
% {\usefont{OT1}{cmr}{m}{n}\char61}{}}
%\endgroup
%\def\cdot{\mathchar8705\nobreak\discretionary{}%
% {\usefont{OMS}{cmsy}{m}{n}\char1}{}}
%\def\times{\mathchar8706\nobreak\discretionary{}%
% {\usefont{OMS}{cmsy}{m}{n}\char2}{}}
%\mathcode`\==32768
%\mathcode`\+=32768
%\mathcode`\-=32768
%%end{latexonly}
\makeindex
\begin{document}
\selectlanguage{russian}
%\layout
% рамка границ страницы http://www.ctan.org/tex-archive/macros/latex/contrib/fancybox/fancybox-doc.pdf
% сделать поиск по fancypage, thisfancypage
%\thisfancypage{}{\fbox}
%\thisfancypage{\fbox}{}
%\fancypage{}{\fbox} % закомментировать
%\fancypage{\fbox}{\fbox} % закомментировать
%\fancypage{\setlength{\fboxsep}{32pt}\fbox}{}
\title{Защита информации \\ Учебное пособие}
\author{Габидулин Эрнст Мухамедович \\ Кшевецкий Александр Сергеевич \\ Колыбельников Александр Иванович \\ Владимиров Сергей Михайлович}
\date{
% \textbf{\textsc{Черновой вариант. Может содержать ошибки.}} \\
% \today
}
\maketitle
\setcounter{page}{3}
\newpage
%\thispagestyle{empty}
\setcounter{tocdepth}{2}
\tableofcontents
%\thispagestyle{empty}
\newpage
%\lhead[\leftmark]{}
%\rhead[]{\rightmark}
\input{foreword}
\input{Short_history_of_cryptography}
\input{definitions}
\chapter{Классические шифры}
В главе приведены наиболее известные \emph{классические} шифры, которыми можно было пользоваться до появления роторных машин. К ним относятся такие шифры, как шифр Цезаря\index{шифр!Цезаря}, шифр Плейфера\index{шифр!Плейфера}, шифр Хилла\index{шифр!Хилла}, шифр Виженера\index{шифр!Виженера}. Они наглядно демонстрируют различные классы шифров.
\input{monoalphabetic_ciphers}
\input{bigrammnye_substitution_ciphers}
\input{hills_cipher}
% \subsection{Омофонные замены}
%
% Омофонными заменами называют криптопримитивы, в основе которых лежит замена групп символов открытого текста $M$ на группу символов $C$ с использованием ключа $K$. Такой метод шифрования вносит неоднозначность между $M$ и $C$, это позволяет защититься от методов частотного криптоанализа.
% \subsection{шифрокоды}
% Шифрокоды -- это класс шифров сочетающих в себе свойства кодов и помехозащищённости со свойствами шифра и обеспечения конфиденциальности.
\input{vigeneres_cipher}
\input{polyalphabetic_cipher_cryptanalysis}
\input{perfect_secure_systems}
\chapter{Блочные шифры}\label{chapter-block-ciphers}\index{шифр!блочный|(}
\input{block_ciphers}
\input{lucifer}
\input{Feistel_cipher}
\input{DES}
\input{GOST_28147-89}
\input{AES}
\input{Block_cipher_modes}
\section{Некоторые свойства блочных шифров}
\input{feistel_network_reversibility}
\input{Feistel_cipher_without_s_blocks}
\input{Avalanche_effect}
\input{double_and_triple_ciphering}
\index{шифр!блочный|)}
\input{generators}
\input{stream-ciphers}
\input{hash-functions}
\input{public-key}
\input{key_distribution_protocols}
\input{secret-sharing}
\chapter{Примеры систем защиты}
\input{kerberos}
\input{pgp}
\input{tls}
\input{ipsec}
\section[Защита персональных данных в мобильной связи]{Защита персональных данных в \protect\\ мобильной связи}
\input{gsm2}
\input{gsm3}
%\section{Беспроводная сеть Wi-Fi}
%\subsection{WPA-PSK2, 802.11n, Radix?}
%\subsection{Wimax 802.16(?)}
\chapter{Аутентификация пользователя}
\section{Многофакторная аутентификация}
Для защищённых приложений применяется \textbf{многофакторная} аутентификация одновременно по факторам различной природы:
\begin{enumerate}
\item Свойство, которым обладает субъект. Например: биометрия, природные уникальные отличия (лицо, радужная оболочка глаз, папиллярные узоры, последовательность ДНК).
\item Знание -- информация, которую знает субъект. Например, пароль, PIN-код.
\item Владение -- вещь, которой обладает субъект. Например: электронная или магнитная карта, флеш-память.
% \item Факторы присвоения. Например, номер машины, RFID-метка.
\end{enumerate}
В обычных массовых приложениях из-за удобства использования применяется аутентификация только по \textbf{паролю}\index{пароль}, который является общим секретом пользователя и информационной системы. Биометрическая аутентификация по отпечаткам пальцев применяется существенно реже. Как правило, аутентификация по отпечаткам пальцев является дополнительным, а не вторым обязательным фактором (тоже из-за удобства её использования).
%Так же явно или неявно используется аутентификация по факторам:
%\begin{enumerate}
% \item Социальная сеть. Доверие к индивидууму в личном общении или интернет на основании общих связей.
% \item Географическое положение. Например, для проверки оплаты товаров по кредитной карте.
% \item Время. Доступ к сервисам или местам только в определённое время.
% \item И др.
%\end{enumerate}
\section[Энтропия и криптостойкость паролей]{Энтропия и криптостойкость \protect\\ паролей}
Стандартный набор символов паролей, которые можно набрать на клавиатуре, используя английские буквы и небуквенные символы, состоит из $D=94$ символов. При длине пароля $L$ символов и предположении равновероятного использования символов энтропия паролей равна
\[ H = L \log_2 D. \]
Клод Шеннон, исследуя энтропию символов английского текста, изучал вероятность успешного предсказания людьми следующего символа по первым нескольким символам слов или текста. В результате Шеннон получил оценку энтропии первого символа $s_1$ текста порядка $H(s_1) \approx 4{,}6$--$4{,}7$ бит/символ и оценки энтропий последующих символов, постепенно уменьшающиеся до $H(s_9) \approx 1{,}5$ бит/символ для 9-го символа. Энтропия для длинных текстов литературных произведений получила оценку $H(s_\infty) \approx 0{,}4$ бит/символ.
Статистические исследования баз паролей показывают, что наиболее часто используются буквы <<a>>, <<e>>, <<o>>, <<r>> и цифра <<1>>.
NIST использует следующие рекомендации для оценки энтропии паролей\index{энтропия!пароля}, создаваемых людьми.
\begin{enumerate}
\item Энтропия первого символа $H(s_1) = 4$ бит/символ.
\item Энтропия со 2-го по 8-й символы $H(s_{2 \leq i \leq 8}) = 2$ бит/символ.
\item Энтропия с 9-го по 20-й символы $H(s_{9 \leq i \leq 20}) = 1{,}5$ бит/символ.
\item Энтропия с 21-го символа $H(s_{i \geq 21}) = 1$ бит/символ.
\item Проверка композиции на использование символов разных регистров и небуквенных символов добавляет до 6 бит энтропии пароля.
\item Словарная проверка на слова и часто используемые пароли добавляет до 6 бит энтропии для коротких паролей. Для 20-символьных и более длинных паролей прибавка к энтропии 0 бит.
\end{enumerate}
Для оценки энтропии пароля нужно сложить энтропии символов $H(s_i)$ и сделать дополнительные надбавки, если пароль удовлетворяет тестам на композицию и отсутствие в словаре.
\begin{table}[!ht]
\centering
\caption{Оценка NIST предполагаемой энтропии паролей\label{tab:password-entropy}}
\resizebox{\textwidth}{!}{ \begin{tabular}{|c||c|c|c||c|}
\hline
\multirow{2}{*}{\parbox{1.5cm}{Длина пароля, символы}} & \multicolumn{3}{|c||}{\parbox{6cm}{Энтропия паролей пользователей по критериям NIST}} & \multirow{2}{*}{\parbox{2.5cm}{Энтропия случайных равновероятных паролей}} \\
\cline{2-4}
& \parbox{1.5cm}{Без проверок} & \parbox{2cm}{Словарная проверка} & \parbox{2.5cm}{Словарная и композиционная проверка} & \\
\hline
4 & 10 & 14 & 16 & 26.3 \\
6 & 14 & 20 & 23 & 39.5 \\
8 & 18 & 24 & 30 & 52.7 \\
10 & 21 & 26 & 32 & 65.9 \\
12 & 24 & 28 & 34 & 79.0 \\
16 & 30 & 32 & 38 & 105.4 \\
20 & 36 & 36 & 42 & 131.7 \\
24 & 40 & 40 & 46 & 158.0 \\
30 & 46 & 46 & 52 & 197.2 \\
40 & 56 & 56 & 62 & 263.4 \\
\hline
\end{tabular} }
\end{table}
В таблице~\ref{tab:password-entropy} приведена оценка NIST на величину энтропии пользовательских паролей в зависимости от их длины и сравнение с энтропией случайных паролей с равномерным распределением символов из набора в $D=94$ символов клавиатуры. Вероятное число попыток для подбора пароля составляет $O(2^H)$. Из таблицы видно, что по критериям NIST энтропия реальных паролей в 2--4 раза меньше энтропии случайных паролей с равномерным распределением символов.
\example
Оценим общее количество существующих паролей. Население Земли -- 7 млрд. Предположим, что всё население использует компьютеры и Интернет, и у каждого человека по 10 паролей. Общее количество существующих паролей -- $7 \cdot 10^{10} \approx 2^{36}$.
Имея доступ к наиболее массовым интернет-сервисам с количеством пользователей десятки и сотни миллионов, в которых пароли часто хранятся в открытом виде из-за необходимости обновления ПО и, в частности, выполнения аутентификации, мы:
\begin{enumerate}
\item имеем базу паролей, покрывающую существенную часть пользователей;
\item можем статистически построить правила генерирования паролей.
\end{enumerate}
Даже если пароль хранится в защищённом виде, то при вводе, пароль, как правило, в открытом виде пересылается по Интернету, и все преобразования пароля для аутентификации осуществляет интернет-сервис, а не веб-браузер. Следовательно, интернет-сервис имеет доступ к исходному паролю.
\exampleend
В 2002 г. был подобран ключ для 64-битного блочного шифра RC5 сетью \texttt{distributed.net} персональных компьютеров, выполнявших вычисления в фоновом режиме. Суммарное время вычислений всех компьютеров -- 1757 дней, было проверено 83\% пространства всех ключей. Это означает, что пароли с оценочной энтропией менее 64 бит, то есть \emph{все пароли} до 40 символов по критериям NIST, могут быть подобраны в настоящее время. Конечно, с оговорками на то, что 1) нет ограничений на количество и скорость попыток аутентификаций, 2) алгоритм генерации вероятных паролей эффективен.
Строго говоря, использование даже 40-символьного пароля для аутентификации или в качестве ключа блочного шифрования является небезопасным.
\subsubsection{Число паролей}
Приведём различные оценки числа паролей, создаваемых людьми.
Пароли, создаваемые людьми, основаны на словах или закономерностях естественного языка. В английском языке всего около $1\ 000\ 000 \approx 2^{20}$ слов, включая термины.
%http://www.springerlink.com/content/bh216312577r6w64/fulltext.pdf
%http://www.antimoon.com/forum/2004/4797.htm
Используемые слоги английского языка имеют вид V, CV, VC, CVV, VCC, CVC, CCV, CVCC, CVCCC, CCVCC, CCCVCC, где C -- согласная (consonant), V -- гласная (vowel). 70\% слогов имеют структуру VC или CVC. Общее число слогов $S = 8000 - 12000$. Средняя длина слога -- 3 буквы.
Предполагая равновероятное распределение всех слогов английского языка, для числа паролей из $r$ слогов получим верхнюю оценку
\[ N_1 = S^r = 2^{13 r} \approx 2^{4.3 L_1}. \]
Средняя длина паролей составит
\[ L_1 \approx 3 r. \]
Теперь предположим, что пароли могут состоять только из 2--3 буквенных слогов вида CV, VC, CVV, VCC, CVC, CCV с равновероятным распределением символов. Подсчитаем число паролей $N_2$, которые могут быть построены из $r$ таких слогов. В английском алфавите число гласных букв $n_v = 10, согласных n_c = 16, n = n_v + n_c = 26$. Верхняя оценка числа $r$-слоговых паролей:
\[ N_2 = (n_c n_v + n_v n_c + n_c n_v n_v + n_v n_c n_c + n_c n_v n_c + n_c n_c n_v)^r \approx \]
\[ \approx \left( n_c n_v(3 n_c + n_v) \right)^r, \]
\[ N_2 \approx \left( \frac{n^3}{2} \right)^r \approx 2^{13 r} \approx 2^{4.3 L_2}. \]
Средняя длина паролей:
\[ L_2 = \frac{n_c n_v(2 + 2 + 3 n_v + 3 n_c + 3 n_c + 3 n_c)}{n_c n_v (1 + 1 + n_v + n_c + n_c + n_c)} \cdot r \approx 3 r. \]
Как видно, получились одинаковые оценки числа и длины паролей.
Подсчитаем верхние оценки числа паролей из $L$ символов, предполагая равномерное распределение символов из алфавита мощностью $D$ символов: a) $D_1 = 26$ строчных букв, б) все $D_2 = 94$ печатных символа клавиатуры (латиница и небуквенные символы):
\[ N_3 = D_1^L \approx 2^{4.7 L}, \]
\[ N_4 = D_2^L \approx 2^{6.6 L}. \]
\begin{table}[!ht]
\centering
\caption{Различные верхние оценки числа паролей\label{tab:password-number}}
\resizebox{\textwidth}{!}{ \begin{tabular}{|c||c|c|c|}
\hline
\multirow{2}{*}{\parbox{1.5cm}{Длина пароля}} & \multicolumn{3}{|c|}{Число паролей} \\
\cline{2-4}
& \parbox{3cm}{На основе слоговой композиции} &
\parbox{3cm}{Алфавит $D=26$ символов} &
\parbox{3cm}{Алфавит $D=94$ символа} \\
\hline \hline
6 & $2^{26}$ & $2^{28}$ & $2^{39}$ \\
9 & $2^{39}$ & $2^{42}$ & $2^{59}$ \\
12 & $2^{52}$ & $2^{56}$ & $2^{79}$ \\
15 & $2^{65}$ & $2^{71}$ & $2^{98}$ \\
\hline
21 & $2^{91}$ & $2^{99}$ & $2^{137}$ \\
\hline
39 & $2^{169}$ & $2^{183}$ & $2^{256}$ \\
\hline
\end{tabular} }
\end{table}
Из таблицы~\ref{tab:password-number} видно, что при доступном объёме вычислений в $2^{60 \ldots 70}$ операций, пароли вплоть до 15 символов, построенные на словах, слогах, изменениях слов, вставках цифр, небольшом изменении регистров и других простейших модификациях, могут быть найдены перебором на кластере (или ПК) в настоящее время.
Для достижения криптостойкости паролей, сравнимой со 128- или 256-битовым секретным ключом, требуется выбирать пароль из 20 и 40 символов соответственно, что, как правило, не реализуется из-за сложности запоминания и ввода без ошибок.
%Подсчитаем число паролей $N_1$, которые могут могут построены из $r$ ~ 2-3 буквенных слогов: $cv, vc, ccv, cvc, vcc$, где $c$ -- согласная, $v$ -- гласная. В английском алфавите $n_v = 10, n_c = 16, n = n_v + n_c = 26$. Число паролей
% \[ N_1 = \left( n_v n_c (1 + 1 + n_c + n_c + n_c) \right)^r \approx 3^r n_v^r n_c^{2r}. \]
%Средняя длина паролей
% \[ L = r \left( \frac{2 + 2 + 3 n_c + 3 n_c + 3 n_c}{1 + 1 + n_c + n_c + n_c} \right) \approx 3r. \]
%
%%Учтем, что $b \leq r$ символов могут быть заглавными: $N_1 \rightarrow N_2 < N_1 \binom{L}{b} \left( \frac{n}{n_v} \right)^b$. Вставим $d$ цифр в случайные места: $N_2 \rightarrow N_3 = N_2 (10 (1 + L))^d \approx N_2 (10 L)^d$.
%%
%%Общее число паролей
%% \[ N = N_3 = 3^r 10^r 16^{2r} \binom{3r}{b} 2.6^b \left(10 \cdot 3 r \right)^d. \]
%%
%%\begin{table}[!ht]
%% \centering
%% \small
%% \begin{tabular}{|c|c|c|c|c||cr|}
%% \hline
%% \parbox{1.3cm}{Слогов, $r$} & \parbox{1.8cm}{Заглавных букв, $b$} & \parbox{1.5cm}{Вставок цифр, $d$} & \parbox{2.8cm}{Средняя длина пароля, $L+d$} & \parbox{3cm}{Верхняя оценка числа паролей $N$} & \multicolumn{2}{|c|}{\parbox{3.2cm}{Число всех паролей}} \\
%% \hline
%% $2$ & $0$ & $0$ & $6$ & $2^{26}$ & $2^{36}$ & a-z \\
%% $2$ & $2$ & $0$ & $6$ & $2^{32}$ & $2^{48}$ & A-Z, a-z \\
%% $2$ & $2$ & $2$ & $8$ & $2^{45}$ & $2^{48}$ & A-Z, a-z, 0-9 \\
%% \hline
%% $3$ & $0$ & $0$ & $9$ & $2^{39}$ & $2^{54}$ & a-z \\
%% $3$ & $3$ & $0$ & $9$ & $2^{49}$ & $2^{54}$ & A-Z, a-z \\
%% $3$ & $3$ & $2$ & $11$ & $2^{63}$ & $2^{65}$ & A-Z, a-z, 0-9 \\
%% \hline
%% $4$ & $0$ & $0$ & $12$ & $2^{52}$ & $2^{93}$ & a-z \\
%% $4$ & $3$ & $0$ & $12$ & $2^{64}$ & $2^{186}$ & A-Z, a-z \\
%% $4$ & $3$ & $2$ & $14$ & $2^{78}$ & $2^{222}$ & A-Z, a-z, 0-9 \\
%% \hline
%% \end{tabular}
%% \caption{Сравнение верхней оценки числа паролей, построенных на слогах, со всем доступным множеством паролей.}
%% \label{tab:password-number}
%%\end{table}
%
%Учтем, что $b$ символов в пароле могут быть взяты не из 26-символьного алфавита строчных букв, а из всего алфавита в $D=94$ печатных символа клавиатуры (латиница и небуквенные символы):
%\[
% \begin{array}{ll}
% b=1 & N_1 \rightarrow N_2 = \frac{n_v}{n_v+n_c} 3^r n_v^{r-1} n_c^{2r} \cdot L. \]
%
% \[ N_1 \rightarrow N_2 < N_1 \binom{L}{b} \left( \frac{D}{n_v} \right)^b. \]
%
%
%
%Общее число паролей
% \[ N < 3^r n_v^r n_c^{2r} \binom{L}{b} \left( \frac{D}{n_v} \right)^b = 3^r 10^r 16^{2r} \binom{3r}{b} \left( \frac{94}{10} \right)^b. \]
%
%\begin{table}[!ht]
% \centering
% \small
% \begin{tabular}{|c|c|c|c||cr|}
% \hline
% \parbox{1.5cm}{Слогов, $r$} & \parbox{3cm}{Средняя длина пароля, $L$} & \parbox{3cm}{Символов из всего алфавита, $b$} & \parbox{3cm}{Верхняя оценка числа паролей $N$} & \multicolumn{2}{|c|}{\parbox{3.2cm}{Число всех паролей, $D^L$}} \\
% \hline
% \multirow{3}{*}{2} & \multirow{3}{*}{6} & $0$ & $2^{26}$ & $2^{28}$ & a-z \\
% & & $1$ & $2^{32}$ & $2^{34}$ & A-Z, a-z \\
% & & $3$ & $2^{40}$ & $2^{39}$ & Весь алфавит \\
% \hline
% \multirow{3}{*}{3} & \multirow{3}{*}{9} & $0$ & $2^{39}$ & $2^{42}$ & a-z \\
% & & $2$ & $2^{50}$ & $2^{51}$ & A-Z, a-z \\
% & & $4$ & $2^{59}$ & $2^{59}$ & Весь алфавит \\
% \hline
% \multirow{3}{*}{4} & \multirow{3}{*}{12} & $0$ & $2^{52}$ & $2^{56}$ & a-z \\
% & & $3$ & $2^{69}$ & $2^{68}$ & A-Z, a-z \\
% & & $6$ & $2^{81}$ & $2^{77}$ & Весь алфавит \\
% \hline
% \end{tabular}
% \caption{Сравнение верхней оценки числа паролей, построенных на слогах, со всем доступным множеством паролей в алфавите из $D$ символов.}
% \label{tab:password-number}
%\end{table}
%
%Из таблицы~\ref{tab:password-number} видно, что при доступном объёме вычислений в $2^{60 \ldots 70}$ операций, пароли вплоть до 12 символов, построенные на словах, слогах, изменениях слов, вставках цифр, небольшого изменения регистров и другой простейшей обфускации, могут быть найдены перебором на кластере (или ПК) в настоящее время.
\subsubsection{Атака для подбора паролей и ключей шифрования}
В схемах аутентификации по паролю иногда используется хэширование и хранение хэша пароля на сервере. В таких случаях применима словарная атака или атака с применением заранее вычисленных таблиц для ускорения поиска.
Для нахождения пароля, прообраза хэш-функции, или для нахождения ключа блочного шифрования по атаке с выбранным шифротекстом (для одного и того же известного открытого текста и соответствующего шифротекста) может быть применён метод перебора с балансом между памятью и временем вычислений. Самый быстрый метод радужных таблиц (rainbow tables)\index{радужные таблицы}, 2003 г., заранее вычисляет следующие цепочки и хранит результат в памяти.
Для нахождения пароля, прообраза хэш-функции $H$, цепочка строится как
\[ M_0 \xrightarrow{H(M_0)} h_0 \xrightarrow{R_0(h_0)} M_1 \ldots M_t \xrightarrow{H(M_t)} h_t \xrightarrow{R_t(h_t)} M_{t+1}, \]
где $R_i(h)$ -- функция редуцирования, преобразования хэша в пароль для следующего хэширования.
Для нахождения ключа блочного шифрования для одного и того же известного открытого текста $M$ таблица строится как
\[ K_0 \xrightarrow{E_{K_0}(M)} c_0 \xrightarrow{R_0(c_0)} K_1 \ldots K_t \xrightarrow{E_{K_t}(M)} c_t \xrightarrow{R_t(c_t)} K_{t+1}, \]
где $R_i(c)$ -- функция редуцирования, преобразования шифротекста в новый ключ.
Функция редуцирования $R_i$ зависит от номера итерации, чтобы избежать дублирующихся подцепочек, которые возникают в случае коллизий между значениями в разных цепочках в разных итерациях, если $R$ постоянна. Rainbow-таблица размера $(m \times 2)$ состоит из строк $(M_{0,j}, M_{t+1,j})$ или $(K_{0,j}, K_{t+1,j})$, вычисленных для разных значений стартовых паролей $M_{0,j}$ или $K_{0,j}$ соответственно.
Опишем атаку на примере нахождения прообраза $\overline{M}$ хэша $\overline{h} = H(\overline{M})$. На первой итерации исходный хэш $\overline{h}$ редуцируется в сообщение $\overline{h} \xrightarrow{R_t(\overline{h})} \overline{M}_{t+1} $ и сравнивается со всеми значениями последнего столбца $M_{t+1,j}$ таблицы. Если нет совпадения, переходим ко второй итерации. Хэш $\overline{h}$ дважды редуцируется в сообщение $\overline{h} \xrightarrow{R_{t-1}(\overline{h})} \overline{M}_t \xrightarrow{H(\overline{M}_t)} \overline{h}_t \xrightarrow{R_t(\overline{h}_t)} \overline{M}_{t+1}$ и сравнивается со всеми значениями последнего столбца $M_{t+1,j}$ таблицы. Если не совпало, то переходим к третьей итерации и т.~д. Если для $r$-кратного редуцирования сообщение $\overline{M}_{t+1}$ содержится в таблице во втором столбце, то из совпавшей строки берётся $M_{0,j}$, и вся цепочка пробегается заново для поиска искомого сообщения $\overline{M}: ~ \overline{h} = H(\overline{M})$.
Найдём вероятность нахождения пароля в таблице. Пусть мощность множества всех паролей $N$. Изначально в столбце $M_{0,j}$ содержится $m_0 = m$ различных паролей. Предполагая случайное отображение с пересечениями паролей $M_{0,j} \rightarrow M_{1,j}$, в $M_{1,j}$ будет $m_1$ различных паролей. Согласно задаче о размещении,
\[
m_{i+1} = N \left( 1 - \left( 1 - \frac{1}{N} \right)^{m_i} \right) \approx N \left( 1 - e^{-\frac{m_i}{N}} \right).
\]
Вероятность нахождения пароля
\[
P = 1 - \prod \limits_{i=1}^t \left( 1 - \frac{m_i}{N} \right).
\]
Чем больше таблица из $m$ строк, тем больше шансов найти пароль или ключ, выполнив в наихудшем случае $O \left( m \frac{t(t+1)}{2} \right)$ операций.
Примеры применения атаки на хэш-функциях $\textrm{MD5}$\index{хэш-функция!MD5}, $\textrm{LM} \sim \textrm{DES}_{\textrm{Password}} (\textrm{const})$ приведены в таблице~\ref{tab:rainbow-tables}.
\begin{table}[!ht]
\centering
\caption{Атаки на радужных таблицах на \emph{одном} ПК\label{tab:rainbow-tables}}
\resizebox{\textwidth}{!}{ \begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{\parbox{1.0cm}{Длина, биты}} & \multicolumn{3}{|c|}{Пароль или ключ} &
\multicolumn{3}{|c|}{Радужная таблица} \\
\cline{2-7}
& \parbox{1.2cm}{Длина, симв.} & \parbox{1cm}{Множе- ство} & \parbox{1cm}{Мощ- ность} &
объём & \parbox{1.5cm}{Время вычисления таблиц} & \parbox{1.3cm}{Время поиска} \\
\hline \hline
\multicolumn{7}{|c|}{Хэш LM} \\
\hline
\multirow{3}{*}{$2 \times 56$} & \multirow{3}{*}{14} &
A--Z & $2^{33}$ & 610 MB & & 6 с \\
& & A--Z, 0-9 & $2^{36}$ & 3 GB & & 15 с \\
& & все & $2^{43}$ & 64 GB & \parbox{1.5cm}{несколько лет} & 7 мин \\
\hline \hline
\multicolumn{7}{|c|}{Хэш MD5} \\
\hline
128 & 8 & A-Z, 0-9 & $2^{41}$ & 36 GiB & - & 4 мин \\
\hline
\end{tabular} }
\end{table}
\section{Аутентификация по паролю}
Из-за малой энтропии пользовательских паролей во всех системах регистрации и аутентификации пользователей применяется специальная политика безопасности. Типичные минимальные требования:
\begin{enumerate}
\item Длина пароля от 8 символов. Использование разных регистров и небуквенных символов в паролях. Запрет паролей из словаря слов или часто используемых паролей. Запрет паролей в виде дат, номеров машин и других номеров.
\item Ограниченное время действия пароля. Обязательная смена пароля по истечении срока действия.
\item Блокирование возможности аутентификации после нескольких неудачных попыток. Ограниченное число актов аутентификаций в единицу времени. Временная задержка перед выдачей результата аутентификации.
\end{enumerate}
Дополнительные рекомендации (требования) пользователям:
\begin{enumerate}
\item Не использовать одинаковые или похожие пароли для разных систем, таких как электронная почта, вход в ОС, электронная платежная система, форумы, социальные сети. Пароль часто передается в открытом виде по сети. Пароль доступен администратору системы, возможны утечки конфиденциальной информации с серверов. Поэтому следует стараться выбирать случайные стойкие пароли.
\item Не записывать пароли. Никому не сообщать пароль, даже администратору. Не передавать пароли по почте, телефону, Интернету и т.~д.
\item Не использовать одну и ту же учётную запись для разных пользователей даже в виде исключения.
\item Всегда блокировать компьютер, когда пользователь отлучается от него даже на короткое время.
\end{enumerate}
\input{os_passwords}
\input{http_auth}
\chapter{Программные уязвимости}
\input{security_models}
\input{os_access_controls}
\section{Виды программных уязвимостей}
\textbf{Вирусом} называется самовоспроизводящаяся часть кода (подпрограмма)\index{вирус}, которая встраивается в носители (другие программы) для своего исполнения и распространения. Вирус не может исполняться и передаваться без своего носителя.
\textbf{Червём} называется самовоспроизводящаяся отдельная (под)программа\index{червь}, которая может исполняться и распространяться самостоятельно, не используя программу-носитель.
Первой вехой в изучении компьютерных вирусов можно назвать 1949 год, когда Джон фон Нейман прочёл курс лекций в Университете Иллинойса под названием <<Теория самовоспроизводящихся машин>> (изданы в 1966~\cite{Neumann:1966}, переведены на русский язык издательством <<Мир>> в 1971 году~\cite{Neumann:1971}), в котором ввёл понятие самовоспроизводящихся механических машин. Первым сетевым вирусом считается вирус Creeper 1971 г., распространявшийся в сети ARPANET, предшественнике Интернета. Для его уничтожения был создан первый антивирус Reaper, который находил и уничтожал Creeper.
Первый червь для Интернета, червь Морриса 1988 г., уже использовал \emph{смешанные} атаки\index{атака!смешанная} для заражения UNIX машин~\cite{EichinRochlis:1988, Spafford:1989}. Сначала программа получала доступ к удалённому запуску команд, эксплуатируя уязвимости в сервисах \texttt{sendmail}, \texttt{finger} (с использованием атаки на переполнение буфера) или \texttt{rsh}. Далее с помощью механизма подбора паролей червь получал доступ к локальным аккаунтам пользователей:
\begin{itemize}
\item получение доступа к учётным записям с очевидными паролями:
\begin{itemize}
\item без пароля вообще;
\item имя аккаунта в качестве пароля;
\item имя аккаунта в качестве пароля, повторенное дважды;
\item использование <<ника>> (\langen{nickname});
\item фамилия (\langen{last name, family name});
\item фамилия, записанная задом наперёд;
\end{itemize}
\item перебор паролей на основе встроенного словаря из 432 слов;
\item перебор паролей на основе системного словаря \texttt{/usr/dict/words}.
\end{itemize}
\textbf{Программной уязвимостью}\index{программная уязвимость} называется свойство программы, позволяющее нарушить её работу. Программные уязвимости могут приводить к отказу в обслуживании (Denial of Service, DoS-атака)\index{атака!отказ в обслуживании}, утечке и изменению данных, появлению и распространению вирусов и червей.
Одной из распространённых атак для заражения персональных компьютеров является переполнение буфера в стеке. В интернет-сервисах наиболее распространённой программной уязвимостью в настоящее время является межсайтовый скриптинг (Cross-Site Scripting, XSS-атака)\index{атака!XSS}.
Наиболее распространённые программные уязвимости можно разделить на классы:
\begin{enumerate}
\item Переполнение буфера -- копирование в буфер данных большего размера, чем длина выделенного буфера. Буфером может быть контейнер текстовой строки, массив, динамически выделяемая память и т.~д. Переполнение становится возможным вследствие либо отсутствия контроля над длиной копируемых данных, либо из-за ошибок в коде. Типичная ошибка -- разница в 1 байт между размерами буфера и данных при сравнении.
\item Некорректная обработка (парсинг) данных, введённых пользователем, является причиной большинства программных уязвимостей в веб-приложениях. Под обработкой понимаются:
\begin{enumerate}
\item проверка на допустимые значения и тип (числовые поля не должны содержать строки и т.~д.);
\item фильтрация и экранирование специальных символов, имеющих значения в скриптовых языках или применяющихся для декодирования из одной текстовой кодировки в другую. Примеры символов: \texttt{\textbackslash}, \texttt{\%}, \texttt{<}, \texttt{>}, \texttt{"}, \texttt{'};
\item фильтрация ключевых слов языков разметки и скриптов. Примеры: \texttt{script}, \texttt{JavaScript};
\item декодирование различными кодировками при парсинге. Распространённый способ обхода системы контроля парсинга данных состоит в однократном или множественном последовательном кодировании текстовых данных в шестнадцатеричные кодировки \texttt{\%NN} ASCII и UTF-8. Например, браузер или веб-приложения производят $n$-кратные последовательные декодирования, в то время как система контроля делает $k$-кратное декодирование, $0 \leq k < n$, и, следовательно, пропускает закодированные запрещённые символы и слова.
\end{enumerate}
\item Некорректное использование синтаксиса функций. Например, \texttt{printf(s)} может привести к уязвимости записи в указанный адрес памяти. Если злоумышленник вместо обычной текстовой строки введёт в качестве \texttt{s = "текст некоторой длины\%n"}, то функция \texttt{printf()}, ожидающая первым аргументом строку формата \texttt{printf(fmt, \dots)}, обнаружив \texttt{\%n}, возьмёт значения из ячеек памяти, следующих перед текстовой строкой (устройство стека функции описано далее), и запишет в адрес памяти, равный считанному значению, количество выведенных символов на печать функцией \texttt{printf()}.
\end{enumerate}
\input{stack_overflow}
\input{xss}
\input{sql-injections}
%\chapter{Послесловие}
%Это должно быть что-то в виде заключения, объяснения, почему именно эти темы выбраны, насколько актуален материал с теоретической и практической точки зрения.
\appendix
\renewcommand{\thechapter}{\Asbuk{chapter}} % использование русских букв для нумерации приложений
\chapter{Математическое приложение}\label{chap:discrete-math}
\section{Общие определения}
Выражением $\mod n$ обозначается вычисление остатка от деления произвольного целого числа на целое число $n$. В полиномиальной арифметике эта операция означает вычисление остатка от деления многочленов.
%далее будем обозначать целые числа или операции с целыми числами, взятыми \textbf{по модулю}\index{модуль} целого числа $n$ (остаток от целочисленного деления). Примеры выражений:
\[ a\mod n, \]
\[ (a + b) c\mod n. \]
Равенство
\[ a = b \mod n \]
означает, что выражения $a$ и $b$ равны (говорят также <<сравнимы>>, <<эквивалентны>>) по модулю $n$.
Множество
\[ \{ 0, 1, 2, 3, \dots, n-1 \mod n\} \]
состоит из $n$ элементов, где каждый элемент $i$ представляет все целые числа, сравнимые с $i$ по модулю $n$.
Наибольший общий делитель (НОД) двух чисел $a,b$ обозначается $\gcd(a,b)$ (greatest common divisor).
Два числа $a,b$ называются взаимно простыми, если они не имеют общих делителей, кроме 1, т.е. $\gcd(a,b) = 1$.
Выражение $a \mid b$ означает, что $a$ делит $b$.
\input{birthdays_paradox}
\input{groups}
\input{aes_math}
\input{modular_ariphmetics}
\input{pseudo-primes}
\input{groups_of_ec_points_over_finite_fields}
\section[Полиномиальные и экспоненциальные алгоритмы]{Полиномиальные и \\ экспоненциальные алгоритмы}
Данный раздел поясняет обоснованность стойкости криптосистем с открытым ключом и имеет лишь косвенное отношение к дискретной математике.
Машина Тьюринга (МТ) (модель, представляющая любой вычислительный алгоритм) состоит из следующих частей:
\begin{itemize}
\item неограниченная лента, разделённая на клетки; в каждой клетке содержится символ из конечного алфавита, содержащего пустой символ blank; если символ ранее не был записан на ленту, то он считается blank;
\item печатающая головка, которая может считать, записать символ $a_i$ и передвинуть ленту на 1 клетку влево-вправо $d_k$;
\item конечная таблица действий
\[ (q_i, a_j) \rightarrow (q_{i1}, a_{j1}, d_k), \]
где $q$ -- состояние машины.
\end{itemize}
Если таблица переходов однозначна, то машина Тьюринга\index{машина Тьюринга} называется детерминированной. \textbf{Детерминированная} машина Тьюринга может \emph{имитировать} любую существующую детерминированную ЭВМ. Если таблица переходов неоднозначна, то есть $(q_i, a_j)$ может переходить по нескольким правилам, то машина \textbf{недетерминированная}. \emph{Квантовый компьютер} является примером недетерминированной машины Тьюринга.
Класс задач $\set{P}$ -- задачи, которые могут быть решены за \emph{полиномиальное} время\index{задача!полиномиальная} на \emph{детерминированной} машине Тьюринга. Пример полиномиальной сложности (количество битовых операций)
\[ O(k^{\textrm{const}}), \]
где $k$ -- длина входных параметров алгоритма. Операция возведения в степень в модульной арифметике $a^b \mod n$ имеет кубическую сложность $O(k^3)$, где $k$ -- двоичная длина чисел $a,b,n$.
Класс задач $\set{NP}$ -- обобщение класса $\set{P} \subseteq \set{NP}$, включает задачи, которые могут быть решены за \emph{полиномиальное} время на \emph{недетерминированной} машине Тьюринга. Пример сложности задач из $\set{NP}$ -- экспоненциальная сложность\index{задача!экспоненциальная}
\[ O(\textrm{const}^k). \]
Описанный в разделе криптостойкости системы Эль-Гамаля\index{криптосистема!Эль-Гамаля} алгоритм Гельфонда решения задачи дискретного логарифмирования (нахождения $x$ для заданных основания $g$, модуля $p$ и $a = g^x \mod p$) имеет сложность $O(e^{k/2})$, где $k$ -- двоичная длина чисел.
В криптографии полиномиальные $\set{P}$ алгоритмы считаются \emph{лёгкими и вычислимыми} на ЭВМ, которые являются детерминированными машинами Тьюринга. Неполиномиальные (экспоненциальные) $\set{NP}$ алгоритмы считаются \emph{трудными и невычислимыми} на ЭВМ, так как из-за экспоненциального роста сложности всегда можно выбрать такой параметр $k$, что время вычисления станет сравнимым с возрастом Вселенной.
Класс $\set{NP}$-полных задач -- подмножество задач из $\set{NP}$, для которых не известен полиномиальный алгоритм для детерминированной машины Тьюринга, и все задачи могут быть сведены друг к другу за полиномиальное время на \emph{детерминированной} машине Тьюринга. Например, задача об укладке рюкзака является $\set{NP}$-полной.
Стойкость криптосистем с \emph{открытым} ключом, как правило, основана на $\set{NP}$ или $\set{NP}$-полных задачах:
\begin{enumerate}
\item RSA\index{криптосистема!RSA} -- $\set{NP}$-задача факторизации (строго говоря, основана на трудности извлечения корня степени $e$ по модулю $n$).
\item Криптосистемы типа Эль-Гамаля\index{криптосистема!Эль-Гамаля} -- $\set{NP}$-задача дискретного логарифмирования.
\end{enumerate}
\emph{Нерешённой} проблемой является доказательство неравенства
\[ \set{P} \neq \set{NP}. \]
Именно на гипотезе о том, что для некоторых задач не существует полиномиальных алгоритмов, и основана стойкость криптосистем с открытым ключом.
\input{coincide-index_method}
\input{tasks}
\printindex
\chapter*{Литература}
\addcontentsline{toc}{chapter}{Литература}
\begingroup
\renewcommand{\chapter}[2]{}%
%\bibliographystyle{ugost2008s}
%\bibliography{bibliography}
\printbibliography
\endgroup
\end{document}