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
|
\documentclass[a4paper,oneside]{article}
\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{amsthm}
\usepackage{minted}
\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{float}
\usepackage{algorithm}
\floatname{algorithm}{Алгоритм}
\newcommand{\Z}{\mathbb{Z}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newtheorem{theorem}{Теорема}
\newtheorem*{theorem*}{Теорема}
% --- Определение --- %
\theoremstyle{definition}
\newtheorem{definition}{Определение}
\newtheorem*{definition*}{Определение}
% ------------------- %
\theoremstyle{definition}
\newtheorem*{example}{Пример}
\title{{Криптографические методы защиты информации}\\{Лабораторная работа №5}}
\author{Гущин Андрей, 431 группа, 1 подгруппа, 2 вариант}
\date{\the\year{} г.}
\begin{document}
\maketitle
\section{Схема}
Рассмотрим следующее упрощение схемы Эль-Гамаля. Пусть $p$ --- простое число,
$g$ --- порождающий элемент мультипликативной группы $Z^\cdot_p$. Эти данные
открыты.
Пользователь выбирает секретное число $1 \leq a \leq p - 1$ и открывает значение
$y = g^a \pmod{p}$.
К сообщению $m \in \{ 0, 1 \}^*$ применяется известная хэш-функция, дающая
значение $h = h(m) \in Z_p$.
Допустим, что $\gcd(h, p - 1) = 1$. Этого можно добиться, внеся необходимые
коррективы в случае невыполнения.
При генерации подписи пользователь вычисляет значение
\begin{equation}
z = h^{-1} a \pmod{(p - 1)}
\label{eq:zpow}
\end{equation}
В качестве подписи под документом $m$ предлагается использовать $g^z$.
Проверка правильности подписи элементарна:
\begin{equation}
(g^z)^h = g^{h^{-1} h a} = g^a \pmod{p}
\label{eq:check}
\end{equation}
Подпись принимается, если полученное значение совпадает с $y$.
Необходимо объяснить почему упомянутая схема неприемлема.
\section{Неверность схемы}
Заметим, что в выражении \ref{eq:check} подразумевается, что значения $z$
и $h$ находятся в одном кольце и поэтому можно написать $z \cdot h =
h^{-1} \cdot a \cdot h = h^{-1} \cdot h \cdot a = a$.
Но, также можно заметить, что при вычислении $z$ в выражении \ref{eq:zpow}
умножаемые значения берутся по модулю $(p - 1)$. То есть, значение $z$
является элементом мультипликативной группы $Z^\cdot_{(p - 1)}$. При этом
значение $h$ является элементом группы $Z^\cdot_p$ по условию.
Таким образом, в общем случае мы можем сказать, что
\begin{equation*}
z \cdot h
= (h^{-1} \cdot a \pmod{(p - 1)}) \cdot h
\neq h^{-1} \cdot a \cdot h
\end{equation*}
Например, пусть $p = 31, a = 19, h = 11$. При этом $h^{-1} = 17$, где обратное
берётся в группе $Z^\cdot_p$.
\begin{align*}
z &= 17 \cdot 19 \pmod{30} = 23 \\
z \cdot h &= 23 \cdot 11 \pmod{31} = 5 \\
h^{-1} \cdot a \cdot h &= 17 \cdot 19 \cdot 11 \pmod{31} = 19
\end{align*}
Получаем
\begin{equation*}
z \cdot h = 5 \neq 19 = h^{-1} \cdot a \cdot h
\end{equation*}
Таким образом, получаем, что сгенерированную подпись невозможно проверить и
данная схема является неприменимой и неприемлемой.
\section{Взлом схемы}
Будем считать схему подписи \emph{неприемлемой}, если имеется возможность
создать подпись для произвольного сообщения не имея при этом секретного ключа.
Рассмотрим выражение \ref{eq:check}. Можно заметить, что $(g^z)^h = y$. Также
можем получить
\begin{equation*}
\left( \left( g^z \right)^h \right)^{h^{-1}} = y^{h^{-1}}
\end{equation*}
То есть
\begin{equation*}
g^z = y^{h^{-1}}
\end{equation*}
Но значение $y$ является частью открытого ключа, а $h^{-1}$ вычисляется из
публично известной хэш-функции для произвольного сообщения.
Таким образом, можно создать подпись для произвольного сообщения не имея при
этом секретного ключа, а основываясь только на публичных данных.
\end{document}
|
