Криптосистема с открытым ключом

Криптографическая система с открытым ключом (или Асимметричное шифрование, Асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

Схема шифрования с открытым ключом

Пусть $K$ — пространство ключей, а $e$ и $d$ — ключи шифрования и расшифрования соответственно. $E_{e}$ - функция шифрования для произвольного ключа $e$$\in$$K$, такая что:

$E_{e}(m)=c$

Здесь $c$$\in$$C$, где $C$ — пространство шифротекстов, а $m$$\in$$M$, где $M$ — пространство сообщений.

$D_{d}$ - фукция расшифрования , с помощью которой можно найти исходное сообщение $m$, зная шифротекст $c$ :

$D_{d}(c)=m$

{$E_{e}$: $e$$\in$$K$}- набор шифрования, а {$D_{d}$: $d$$\in$$K$} — соответствуйщий набор для расшифрования. Каждая пара $(E,D)$ имеет свойство: зная $E_{e}$, невозможно решить уравнение $E_{e}(m)=c$, то есть для данного произвольного шифротекста $c$$\in$$C$, невозможно найти сообщение $m$$\in$$M$. Это значит, что по данному $e$ невозможно определить соответствующий ключ расшифрования $d$. $E_{e}$ является лазейкой.

Ниже показана схема передачи информации лицом А лицу В. Они могут быть как физическими лицами, так и организациями и так далее. Но для более лёгкого восприятия принято участников передачи отождествлять с людьми, чаще всего именуемых Алиса и Боб. Участника, который стремится перехватить и расшифровать сообщения Алисы и Боба чаще всего называют Евой.

1. Боб выбирает пару $(e,d)$ и шлёт ключ шифрования $e$ (открытый ключ) Алисе по открытому каналу, а ключ расшифрования $d$ (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу, либо его подлинность должна быть гарантирована некоторым сертифицирующим органом).
2. Чтобы послать сообщение $m$ Бобу, Алиса применяет функцию шифрования, определённую открытым ключом $e$: $E_{e}(m)=c$, $c$ — полученный шифротекст.
3. Боб расшифровывает шифротекст $c$, применяя обратное преобразование $D_{d}$, однозначно определённое значением $d$.

Идея криптосистемы с открытым ключом

Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, то есть таких функций $f(x)$, что

x	легко вычислимо	$f(x)$
	——————————→
	←···································
	сложновычислимо

По известному $x$ довольно просто найти значение $f(x)$, тогда как определение $x$ из $f(x)$ сложно в смысле теории.

Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом ипользует односторонние функции с лазейкой. Лазейка- это некий секрет, который помогает расшифровать. То есть существует такой $y$, что зная $f(x)$, можно вычислить $x$. К примеру, мы разобрали часы на множество составных частей, так что очень сложно собрать вновь работающие часы. Но если у нас есть инструкция по сборке (лазейка), мы сможем решить эту проблему.

Понять идеи и методы криптографии с открытым ключом помогает следующий пример — хранение паролей в компьютере. Каждый пользователь в сети имеет свой пароль. При входе, он указывает имя и вводит секретный пароль. Но если хранить пароль на диске компьютера, то Ева его может считать (особенно легко это сделать администратору этой сети) и получить доступ к секретной информации. Для решения задачи используется односторонней функцией. Вход в систему теперь будет выглядеть так:

Имя:	АЛИСА
Пароль:	РОМАШКА
Функция:	$f$

Здесь $f$ — односторонняя функция, РОМАШКА — открытый пароль Алисы. В то время как «секретный» пароль ГЛАДИОЛУС знает только Маргарита, такой что

$f$(ГЛАДИОЛУС) = РОМАШКА

Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл пароля может быть теперь просмотрен другими пользователями без потери секретности, так как функция необратимая.

Полезно рассмотреть также следующий пример. Пусть имеется большой абонентский справочник, состоящий из нескольких толстых томов. По нему очень легко найти номер любого жителя города, но почти невозможно найти по известному номеру абонента. Теперь для каждой буквы из отправляемого сообщения выбирается случайно имя, начинающееся на ту же букву. Таким образом, букве ставится в соответствие номер телефона абонента или шифр. Теперь можно зашифровать отправляемое сообщение: «КОРОБКА»:

Сообщение	Выбранное имя	Криптотекст
К	Королёв	5643452
О	Орехов	3572651
Р	Рузаева	4673956
O	Осипов	3517289
Б	Батурин	7755628
К	Кирсанова	1235267
А	Арсеньева	8492746

Криптотекстом будет являться цепочка номеров, записанных в порядке их появления в таблице. Из примера видно, что одному и тому же сообщению может соответствовать несколько криптотекстов.

Примеры таких криптотекстов:

Криптотекст 1	Криптотекст 2	Криптотекст 3
1235267	5643452	1235267
3572651	3517289	3517289
4673956	4673956	4673956
3517289	3572651	3572651
7755628	7755628	7755628
5643452	1235267	5643452
8492746	8492746	8492746

Чтобы расшифровать текст, достаточно иметь справочник, составленный согласно возрастанию номеров. Этот справочник является лазейкой (секрет, который помогает получить начальный текст) известной только легальным пользователям. Не имея на руках копии справочника, криптоаналитик затратит очень много времени на расшифровку.

Научная основа

Начало асимметричным шифрам было положено в 1976 году в работе Уитфилда Диффи и Мартина Хеллмана «Новые направления в современной криптографии». Они предложили систему обмена общим секретным ключом (см. Диффи — Хеллмана криптосистема) на основе проблемы дискретного логарифма. Вообще, в основу известных асимметричных криптосистем кладётся одна из сложных математических проблем, которая позволяет строить односторонние функции и функции-ловушки. Например, криптосистема Ривеста — Шамира — Адельмана использует проблему факторизации больших чисел, а криптосистемы Меркля — Хеллмана и Хора — Ривеста опираются на так называемую задачу об укладке рюкзака.

Основные принципы построения криптосистем с открытым ключом

1. Начинаем с трудной задачи Р. Она должна решаться сложно в смысле теории: нет алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи Р за полиномиальное время относительно размера задачи.
2. Можно выделить легкую подзадачу P' из Р. Она должна решаться за полиномиальное время, лучше, если за линейное.
3. «Перетасовываем и взбалтываем» Р', чтобы получить задачу Р, совершенно не похожую на первоначальную. Задача Р, по крайней мере, должна выглядеть как оригинальная труднорешаемая задача Р.
4. Р открывается с описанием, как она может быть использована в роли ключа зашифрования. Как из Р получить Р', держится в секрете как секретная лазейка.
5. Криптосистема организована так, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как первый решает Р задачу, второй использует секретную лазейку и решает Р' задачу.

Криптография с несколькими открытыми ключами

Реализуем схему, в которой Алиса шифрует сообщение так, что только Боб может прочитать его, и наборот, Боб шифрует сообщение так, что только Алиса может расшифровать его. Пусть у нас есть 3 ключа $K_{A}$, $K_{B}$, $K_{C}$, распределенные так, как показано в таблице.

Лицо	Ключ
Алиса	$K_{A}$
Боб	$K_{B}$
Кэрол	$K_{C}$
Дэйв	$K_{A}$, $K_{B}$
Эллен	$K_{B}$, $K_{C}$
Франк	$K_{A}$, $K_{C}$

Теперь Алиса может зашифровать сообщение ключом $K_{A}$, а Эллен расшифровать ключами $K_{B}$, $K_{C}$, Кэрол — ключом $K_{C}$, а Дэйв расшифровать ключами $K_{A}$, $K_{B}$. Если Дэйв зашифрует сообщение ключом $K_{A}$, то сообщение сможет прочитать Эллен, если ключом $K_{B}$, то его сможет прочитать Франк, если же обоими ключами $K_{A}$ и $K_{B}$, то сообщение прочитает Кэрол. По аналогии действуют и другие участники. Таким образом, если используется одно подмножество ключей для шифрования, то для расшифрования требуются оставшиеся ключи множества. Такую схему можно использовать для n ключей.

Шифруется ключом	Расшифровывается ключом
$K_{B}$ и $K_{C}$	$K_{A}$
$K_{A}$ и $K_{C}$	$K_{B}$
$K_{A}$ и $K_{B}$	$K_{C}$
$K_{C}$	$K_{A}$, $K_{B}$
$K_{A}$	$K_{B}$, $K_{C}$
$K_{B}$	$K_{A}$, $K_{C}$

Теперь мы хотим посылать сообщения группам агентов, не зная заранее состав группы. Рассмотрим для начала множество, состоящее из трех агентов: Алисы, Боба и Кэрол. Алисе выдадим ключи $K_{A}$ и $K_{B}$, Бобу — $K_{B}$ и $K_{C}$, Кэрол — $K_{A}$ и $K_{C}$. Теперь, если отправляемое сообщение зашифровано ключом $K_{C}$, то его сможет прочиать только Алиса, последовательно применяя ключи $K_{A}$ и $K_{B}$. Если хотим отправить сообщение Бобу, шифруем сообщение ключом $K_{A}$, Кэрол — ключом $K_{B}$. Если хотим отправить сообщение и Алисе и Кэрол, и спользуем для шифрования ключи $K_{B}$ и $K_{C}$.

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

Недостатком такой схемы является то, что необходимо также широковещательно передавать подмножество агентов(список имен может быть внушительным), которым хотим передать сообщение. Иначе каждому из них придется перебирать все комбинации ключей в поисках подходящей. Также агентам придется хранить немалый обем информации о ключах.

Криптоанализ алгоритмов с открытым ключом

Казалось бы, что криптосистема с открытым ключом — идеальная система, не требующая безопасного канала для передачи ключа шифрования. Это подразумевало бы, что два легальных пользователя могли бы общаться по открытому каналу, не встречаясь, чтобы обменяться ключами. К сожалению это не так. Рисунок иллюстрирует как Ева, выполняющая роль активного перехватчика может захватить систему (расшифровать сообщение, предназначенное Бобу) без взламывания системы шифрования.

В этой модели Ева перехватывает открытый ключ e, посланный Бобом Алисе. Затем создает пару ключей e' и d', "маскируется" под Боба, посылая Алисе открытый ключ e', который, как думает Aлиса, открытый ключ, посланный ей Бобом. Ева перехватывает зашифрованные сообщения от Aлисы к Бобу, расшифровывает их с помощью секретного ключа d', заново зашифровывает открытым ключом e Боба и отправляет сообщение Бобу. Таким образом, никто из участников не догадывается, что есть третье лицо, которое может как просто перехватить сообщение $m$, так и подменить его на ложное сообщение $m'$. Это подчеркивает необходимость аутентификации открытых ключей. Для этого обычно используют сертификаты. Распределенное управление ключами в PGP решает возникшую проблему с помощью поручителей.

Еще одна форма атаки — вычисление закрытого ключа, зная открытый (рисунок ниже). Криптоаналитик знает алгоритм шифрования $E_{e}$, анализируя его, пытается найти $D_{d}$. Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B.

Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее. Ниже приведены данные разложения на множители с помощью алгоритма "Квадратичное решето".

Год	Число десятичных разрядов в разложенном числе	Во сколько раз сложнее разложить на множители 512-битовое число
1983	71	> 20 миллионов
1985	80	> 2 миллионов
1988	90	250000
1989	100	30000
1993	120	500
1994	129	100

Также задачу разложения можно решить с помощью Алгоритма Шора при использовании достаточно мощного квантового компьютера.

Для многих методов несимметричного шифрования криптостойкость, полученная в результате криптоанализа, существенно отличается от величин, заявляемых разработчиками алгоритмов на основании теоретических оценок. Поэтому во многих странах вопрос применения алгоритмов шифрования данных находится в поле законодательного регулирования. В частности, в России к использованию в государственных и коммерческих организациях разрешены только те программные средства шифрования данных, которые прошли государственную сертификацию в административных органах, в частности, в ФСТЭК.

Особенности системы

Применение

Алгоритмы криптосистемы с открытым ключом можно использовать

• Как самостоятельные средства для защиты передаваемой и хранимой информации
• Как средства распределения ключей. Обычно с помощью алгоритмов криптосистем с открытым ключом распределяют ключи, малые по обему. А саму передачу больших информационных потоков осуществляют с помощью других алгоритмов.
• Как средства аутентификации пользователей

Преимущества

• Преимущество асимметричных шифров перед симметричными шифрами состоит в отсутствии необходимости предварительной передачи секретного ключа по надёжному каналу.
• В симметричной криптографии ключ держится в секрете для обеих сторон, а в асимметричной криптосистеме только один секретный.
• При симметричном шифровании необходимо обновлять ключ после каждого факта передачи, тогда как в асимметричных криптосистемах пару $(E,D)$ можно не менять значительное время.
• В больших сетях число ключей в асимметричной криптосистеме значительно меньше, чем в симметричной.

Недостатки

• Преимущество алгоритма симметричного шифрования над несимметричным заключается в том, что в первый относительно легко внести изменения.
• Хотя сообщения надежно шифруются, но «засвечиваются» получатель и отправитель самим фактом пересылки шифрованного сообщения.
• Несимметричные алгоритмы используют более длинные ключи, чем симметричные. Ниже приведена таблица, сопоставляющая длину ключа симметричного алгоритма с длиной ключа несимметричного алгоритма с аналогичной криптостойкостью:

Длина симетричного ключа (в битах)	Длина несимметричного ключа (в битах)
56	384
64	512
80	768
112	1792
128	2304

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

1. `Для ЭЦП сообщение предварительно подвергается хешированию, а с помощью асимметричного ключа подписывается лишь относительно небольшой результат хеш-функции.

1. `Для шифрования они используются в форме гибридных криптосистем, где большие объёмы данных шифруются симметричным шифром на сеансовом ключе, а с помощью асимметричного шифра передаётся только сам сеансовый ключ.

Виды симметричных шифров

блочные шифры

• DES (Data Encryption Standard, стандарт шифрования данных)
• 3DES (Triple-DES, тройной DES)
• AES (Advanced Encryption Standard, улучшенный стандарт шифрования)
• RC2 (Шифр Ривеста (Rivest Cipher))
• Blowfish
• Twofish
• ГОСТ Р 34.10-2001
• NUSH
• IDEA (International Data Encryption Algorithm, интернациональный алгоритм шифрования данных)
• CAST (по инициалам разработчиков Carlisle Adams и Stafford Tavares)
• CRAB

потоковые шифры

• RC4 (алгоритм шифрования с ключом переменной длины)
• SEAL (Software Efficient Algorithm, программно-эффективный алгоритм)
• WAKE (World Auto Key Encryption algorithm, всемирный алгоритм шифрования на автоматическом ключе)

Виды асимметричных шифров

• RSA (Rivest-Shamir-Adleman, Ривест — Шамир — Адлеман)
• DSA (Digital Signature Algorithm)
• Elgamal (Шифросистема Эль-Гамаля)
• Diffie-Hellman (Обмен ключами Диффи — Хелмана)
• ECC (Elliptic Curve Cryptography, криптография эллиптической кривой)
• Rabin
• Luc
• McEliece

См. также

• Хеш-функция
• Блочный шифр
• Поточный шифр

Использованная литература

• Саломаа А. Криптография с открытым ключом. — М.: Мир, 1995. — 318 с. — ISBN 5-03-001991-X.
• A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. Handbook of Applied Cryptography. — 1997. — ISBN 0-8493-8523-7.
• Брюс Шнайер. Прикладная криптография. — 2-е издание. — М.: Триумф, 2002. — 816 с.