public-key.tex

\chapter{Асимметричные криптосистемы}\label{chapter-public-key}
\selectlanguage{russian}

\emph{Асимметричной криптосистемой} или же \emph{криптосистемой с открытым ключом} (\langen{public-key cryptosystem, PKC}) называется криптографическое преобразование, использующее два ключа -- открытый и закрытый. Пара из \emph{закрытого}\index{ключ!закрытый} (\langen{private key, secret key, SK})\footnote{В контексте криптосистем с открытым ключом можно ещё встретить использование термина <<секретный ключ>>. Мы не рекомендуем использовать данный термин, чтобы не путать с секретным ключом\index{ключ!секретный}, используемым в симметричных криптосистемах.} и \emph{открытого}\index{ключ!открытый} (\langen{public key, PK}) ключей создаётся пользователем, который свой закрытый ключ держит в секрете, а открытый ключ делает общедоступным для всех пользователей. Криптографическое преобразование в одну сторону (шифрование) можно выполнить, зная только открытый ключ, а в другую (расшифрование) -- только зная закрытый ключ. Во многих криптосистемах из закрытого ключа теоретически можно вычислить открытый ключ, однако это является сложной вычислительной задачей.

Если прямое преобразование выполняется открытым ключом, а обратное -- закрытым, то криптосистема называется \emph{схемой шифрования с открытым ключом}. Все пользователи, зная открытый ключ получателя, могут зашифровать для него сообщение, которое может расшифровать только владелец закрытого ключа.

Если прямое преобразование выполняется закрытым ключом, а обратное -- открытым, то криптосистема называется \emph{схемой электронной подписи (ЭП)}. Владелец закрытого ключа может \emph{подписать} сообщение, а все пользователи, зная открытый ключ, могут проверить, что подпись была создана только владельцем закрытого ключа и никем другим.

Криптосистемы с открытым ключом снижают требования к каналам связи, которые требуются для передачи данных. В симметричных криптосистемах перед началом связи (перед шифрованием сообщения и его передачей) требуется передать или согласовать секретный ключ шифрования по защищённому каналу связи. Злоумышленник не должен иметь возможность ни прослушать данный канал связи, ни подменить передаваемую информацию (ключ). Для надёжной работы криптосистем с открытым ключом необходимо, чтобы злоумышленник не имел возможности подменить открытый ключ легального пользователя. Другими словами, криптосистема с открытым ключом, в случае использования открытых и незащищённых каналов связи, устойчива к пассивному криптоаналитику\index{криптоаналитик!пассивный}, но всё ещё должна предпринимать меры по защите от активного криптоаналитика\index{криптоаналитик!активный}.

Для предотвращения атак <<человек посередине>> (\langen{man-in-the-middle attack})\index{атака!<<человек посередине>>} с активным криптоаналитиком\index{криптоаналитик!активный}, который бы подменял открытый ключ получателя во время его передачи будущему отправителю сообщений, используют \emph{сертификаты открытых ключей}\index{сертификат открытого ключа}. Сертификат представляет собой информацию о соответствии открытого ключа и его владельца, подписанную электронной подписью третьего лица. В корпоративных информационных системах достаточно, если на всю организацию такое лицо, подписывающее сертификаты, будет одно. В этом случае его называют \emph{доверенным центром сертификации} или \emph{удостоверяющим центром}. В глобальной сети Интернет для защиты распространения программного обеспечения (например, защиты от подделок в ПО) и проверок сертификатов в протоколах на базе SSL/TLS\index{протокол!SSL/TLS} используется иерархия удостоверяющих центров, рассмотренная в разделе~\ref{section-CAs}. При обмене личными сообщениями и при распространении программного обеспечения с открытым кодом вместо жёсткой иерархии может использоваться \emph{сеть доверия}\index{сеть доверия}. В сети доверия каждый участник может подписать сертификат любого другого участника. Предполагается, что подписывающий знает лично владельца сертификата и удостоверился в соответствии сертификата владельцу при личной встрече.

Криптосистемы с открытым ключом построены на основе односторонних (однонаправленных) функций c потайным входом. Под \emph{односторонней} функцией понимают \emph{вычислительную} невозможность вычисления её обращения: вычисление значения функции $y = f(x)$ при заданном аргументе $x$ является лёгкой задачей, вычисление аргумента $x$ при заданном значении функции $y$ -- трудной задачей.

Односторонняя функция $y = f(x,K)$ с \emph{потайным входом}\index{функция!с потайным входом} $K$ определяется как функция, которая легко вычисляется при заданном $x$, и аргумент $x$ которой можно легко вычислить из $y$, если известен <<секретный>> параметр $K$, и вычислить невозможно, если параметр $K$ неизвестен.

Примером подобной функции является возведение в степень по модулю составного числа $n$:
	\[ c = f \left( m \right) = m ^ e \mod n.\]

Для того, чтобы быстро вычислить обратную функцию
	\[ m = f^{-1} \left( c \right) = \sqrt[e]{c} \mod n, \]
её можно представить в виде
	\[ m = c^{d} \mod n,\]
где
	\[ d = e^{-1} \mod \varphi \left( n \right). \]

В последнем выражении $\varphi \left( n \right)$ -- это функция Эйлера\index{функция!Эйлера}. В качестве <<потайной дверцы>> или секрета можно рассматривать или непосредственно само число <<$d$>>, или значение $\varphi \left( n \right)$. Последнее можно быстро найти только в том случае, если известно разложение числа $n$ на простые сомножители. Именно эта функция с потайной дверцей лежит в основе криптосистемы RSA\index{криптосистема!RSA}.

Необходимые математические основы модульной арифметики, групп, полей и простых чисел приведены в Приложении~\ref{chap:discrete-math}.

\input{rsa}

\input{el-gamal}

\input{elliptic_curve_cryptography}

\input{pki_key_length}

\section{Инфраструктура открытых ключей}\label{chapter-public-key-infrastructure}

\input{CAs}

\input{x509}