Принцип работы

Существует несколько хорошо известных асимметричных криптосистем: RSA, Эль Гамаля (El Gamal), Рабина (Rabin). Поскольку в этих криптосистемах вид преобразования определяется ключом, публикуют только открытый ключ с указанием, для какой криптосистемы он используется. Секретный и открытый ключ как правило взаимосвязаны между собой, но то, как конкретно они связаны - известно только их владельцу и получить секретный ключ по соответствующему открытому ключу вычислительно невозможно.

Итак, пусть имеются 2 абонента A и В. A имеет открытый ключ e и соответствующий секретный ключ d. Открытый ключ оперделяет преобразование зашифрования E_e , а секретный - преобразование расшифрования D_d. Открытый ключ e абонента А находится в общедоступном месте. Когда B желает послать сообщение m абоненту A, он берет открытый ключ e, принадлежащий А, и, используя его, получает шифртекст c=E_e(m). Затем он посылает c абоненту А. Для того, чтобы расшифровать сообщение, А, используя свой секретный ключ применяет  преобразование расшифрования и получает исходное сообщение: m=D_d (c).

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

Чтобы проиллюстрировать работу асимметричных криптосистем, приведем описание схемы RSA (в упрощенном варианте, т.е. без математических основ теории чисел, теорем и т.д.) и на ее примере рассмотрим основные моменты, присущие асимметричным криптосистемам.

1. Выбираются p,q - большие простые числа. Вычисляется произведение n=pq.

2. Выбирается число e - такое, что (e, n))=1 (т.е e и n) - взаимнопросты), где n)=(p-1)(q-1) - функция Эйлера от n.

3. Из уравнения ed=1(mod n)) находится число d. Запись x mod n означает, что берется остаток от деления x на n (x по модулю n), а запись x=a (mod n) означает, что остаток от деления x на n равен а. Т.е. находится такое число d, что остаток от деления произведения ed на n равен 1.

Полученные числа e,n - открытый ключ пользователя, а d - секретный ключ. Из условия 3 следует, что ed=1+kn),где k - какое-то число.

Процедура зашифрования: C=E_(e,n)(M)=M^e(mod n), где С-получаемый ш.т. , M - о.т., удовлетворяющий следующему условию: M^(n)=1(mod n).

Процедура расшифрования: M=D_(d,n)(C)=C^d(mod n)=(M^e)^d(mod n)=(M^1+k(n))(mod n)=M(M^(n))^k(mod n)=M.

В криптосистеме RSA, как и во многих других асимметричных криптосистемах, сообщение представляется в виде некоторого числа, которое потом обрабатывается определенным образом (например, зашифровывается). Практически все ассиметричные криптосистемы строятся на основе математических проблем, для которых пока не найдено эффективного алгоритма решения. Следовательно, все параметры RSA должны выбираться таким образом, чтобы злоумышленник не мог за приемлимое время получить ключи схемы или какие-либо другие параметры (например, числа p и q), позволяющие ему осуществить атаку. Так, для RSA рекомендована длина n768 бит, в случае долговременного  использования - 1024 бита (в этом случае длина p и q будет по 512 бит).

Скорость работы и экспонента e

Поскольку криптосистема работает с очень большими числами и выполняет такие "трудные" действия, как возведение в степень, то быстродействие криптосистемы невысоко. Асимметричные криптосистемы уступают в скорости симметричным именно "благодаря" использованию таких преобразований. Существуют различные методы повышения скорости RSA. Например, в качестве открытого ключа e берется e=3. Тогда для того, чтобы зашифровать, необходимо всего 3 умножения. Правда в этом случае получается большое d, но предполагают, что у расшифровывающего есть время. Однако использование малой экспоненты e приводит к проблемам с маленькими сообщениями, т.е таких, что M<n^1/e, поскольку в этом случае M может быть получено из шифртекста C=M^e mod n путем вычисления корня e-ой степени из C.

Добавление в сообщение дополнительной информации (salting)

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

Мультипликативные свойства

Пусть m1 b m2 - 2 различных открытых текста, а c1 и с2 - соответствующие им шифртексты. Заметим, что

(m₁m₂)^e=m₁^e m₂^e=c₁c₂ (mod n)

Другими словами, шифртекст открытого текста m=m₁m₂ есть c=c₁c₂ (mod n). Это свойство, называемое также гомоморфным свойством RSA, позволет осуществить атаку по выбранному шифртексту (см.Криптоанализ:Атаки на RSA).

Блочная структура

При́нцип Керкго́ффса — правило разработки криптографических систем, согласно которому в засекреченном виде держится только определённый набор параметров алгоритма, называемый ключом, а остальные детали могут быть открыты без снижения стойкости алгоритма ниже допустимых значений. Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей.

Впервые данный принцип сформулировал в XIX веке голландский криптограф Огюст Керкгоффс. Шеннон сформулировал этот принцип (вероятно, независимо от Керкгоффса) следующим образом: «Враг знает систему». Широко применяется в криптографии.