Асимметричное шифрование

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

Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. Введём функцию шифрования E_e для произвольного ключа eK. Этой функцией зашифруем сообщение m и получим шифротекст c: E_e(m) = c. Здесь cC, где C — пространство шифротекстов, а mM, где M — пространство сообщений. Теперь введем функцию расшифрования D_d, с помощью которой можно найти сообщение m, зная шифротекст c: D_d(c) = m.

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

Учитывая сделанные выше предположения рассмотрим передачу информации некоторого отправителя A получателю B (А и В здесь могут быть как физическими лицами, так и организациями и так далее):

1. A выбирает пару (e,d) и пересылает ключ шифрования e (открытый ключ) B по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу, либо его подлинность должна быть гарантирована некоторым сертифицирующим органом).

2. Чтобы послать сообщение m для A, B применяет функцию шифрования, определённую открытым ключом e: E_e(m) = c, c — полученный шифротекст.

3. A расшифровывает шифротекст c, применяя обратное преобразование D_d, однозначно определённое значением d.

Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций. Односторонняя функция (англ. one-way function)  эта такая функция, которая эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает эту функцию с более чем экспоненциально малой вероятностью. Т.е., зная x, легко вычислить f(x), а зная f(x) очень сложно найти x.

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

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

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

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

1. В начале необходимо выбрать трудную задачу Р. Она должна решаться сложно в смысле теории: нет алгоритма, с помощью которого можно было бы перебрать все варианты решения задачи Р за полиномиальное время относительно размера задачи.

2. Можно выделить легкую подзадачу P' из Р. Она должна решаться за полиномиальное время, лучше, если за линейное.

3. "Перетасовываем и взбалтываем" Р', чтобы получить задачу Р, совершенно не похожую на первоначальную. Задача Р, по крайней мере, должна выглядеть как оригинальная труднорешаемая задача Р.

4. Р открывается с описанием, как она может быть использована в роли ключа зашифрования. Как из Р получить Р', держится в секрете как секретная лазейка.

5. Криптосистема организована так, что алгоритмы расшифрования для легального пользователя и криптоаналитика существенно различны. В то время как первый решает Р задачу, второй использует секретную лазейку и решает Р' задачу.

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

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

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

Еще одна форма атаки — вычисление закрытого ключа, зная открытый (рис. 13.2). Криптоаналитик знает алгоритм шифрования E_e и по нему пытается найти D_d. Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B. Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее.

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

Рис. 13.1. Схема дешифрации зашифрованного сообщения	Рис. 13.2. Вариант атаки на криптосистему с открытым ключом

Преимущества асимметричного шифрования:

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

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

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

• В больших сетях число ключей в асимметричной криптосистеме значительно меньше, чем в симметричной.

Недостатки асимметричного шифрования:

• В алгоритмы симметрично шифрования проще вносить изменения.

• Хотя сообщения надежно шифруются, но "засвечиваются" получатель и отправитель самим фактом пересылки шифрованного сообщения.

• Несимметричные алгоритмы используют более длинные ключи, чем симметричные.

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

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