Public-key cryptography

Классификация ключей

Криптографические ключи различаются согласно алгоритмам, в которых они используются.

• Секретные (Симметричные) ключи — ключи, используемые в симметричных алгоритмах (шифрование, выработка кодов аутентичности). Главное свойство симметричных ключей: для выполнения как прямого, так и обратного криптографического преобразования (шифрование/расшифровывание, вычисление MAC/проверка MAC) необходимо использовать один и тот же ключ (либо же ключ для обратного преобразования легко вычисляется из ключа для прямого преобразования, и наоборот). С одной стороны, это обеспечивает более высокую конфиденциальность сообщений, с другой стороны, создаёт проблемы распространения ключей в системах с большим количеством пользователей.
• Асимметричные ключи — ключи, используемые в асимметричных алгоритмах (шифрование, ЭЦП). Более точно, они являются ключевой парой, поскольку состоят из двух ключей:
  • Закрытый ключ (англ. Private key) — ключ, известный только своему владельцу. Только сохранение пользователем в тайне своего закрытого ключа гарантирует невозможность подделки злоумышленником документа и цифровой подписи от имени заверяющего.
  • Открытый ключ (англ. Public key) — ключ, который может быть опубликован и используется для проверки подлинности подписанного документа, а также для предупреждения мошенничества со стороны заверяющего лица в виде отказа его от подписи документа. Открытый ключ подписи вычисляется как значение некоторой функции от закрытого ключа, но знание открытого ключа не даёт возможности определить закрытый ключ.

Главное свойство ключевой пары: по секретному ключу легко вычисляется открытый ключ, но по известному открытому ключу практически невозможно вычислить секретный.

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

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

• Сеансовые (сессионные) ключи — ключи, вырабатываемые между двумя пользователями, обычно для защиты канала связи. Обычно сеансовым ключом является общий секрет — информация, которая вырабатывается на основе секретного ключа одной стороны и открытого ключа другой стороны. Существует несколько протоколов выработки сеансовых ключей и общих секретов, среди них, в частности, алгоритм Диффи — Хеллмана.
• Подключи — ключевая информация, вырабатываемая в процессе работы криптографического алгоритма на основе ключа. Зачастую подключи вырабатываются на основе специальной процедуры развёртывания ключа.

Длина ключа

Количество информации в ключе, как правило, измеряется в битах.

Для современных симметричных алгоритмов (AES, CAST5, IDEA, Blowfish, Twofish) основной характеристикой криптостойкости является длина ключа. Шифрование с ключами длиной 128 бит и выше считается сильным, так как для расшифровки информации без ключа требуются годы работы мощных суперкомпьютеров. Для асимметричных алгоритмов, основанных на проблемах теории чисел (проблема факторизации — RSA, проблема дискретного логарифма — Elgamal) в силу их особенностей минимальная надёжная длина ключа в настоящее время — 1024 бит.

Для асимметричных алгоритмов, основанных на использовании теории эллиптических кривых (ECDSA, ГОСТ Р 34.10-2001, ДСТУ 4145-2002), минимальной надёжной длиной ключа считается 163 бит, но рекомендуются длины от 191 бит и выше.

Certificate authorities

The procedure of obtaining a Public key certificate

In the X.509 trust model, a certificate authority (CA) is responsible for signing certificates. These certificates act as an introduction between two parties, which means that a CA acts as a trusted third party. A CA processes requests from people or organizations requesting certificates (called subscribers), verifies the information, and potentially signs an end-entity certificate based on that information. To perform this role effectively, a CA needs to have one or more broadly trusted root certificates or intermediate certificates and the corresponding private keys. CAs may achieve this broad trust by having their root certificates included in popular software, or by obtaining a cross-signature from another CA delegating trust. Other CAs are trusted within a relatively small community, like a business, and are distributed by other mechanisms like Windows Group Policy.

Certificate authorities are also responsible for maintaining up-to-date revocation information about certificates they have issued, indicating whether certificates are still valid. They provide this information through Online Certificate Status Protocol (OCSP) and/or Certificate Revocation Lists (CRLs). Some of the larger certificate authorities in the market include IdenTrust, DigiCert, and Sectigo.

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

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

В этой модели Ева перехватывает открытый ключ e{\displaystyle e}, посланный Бобом Алисе. Затем создает пару ключей e′{\displaystyle e’} и d′{\displaystyle d’}, «маскируется» под Боба, посылая Алисе открытый ключ e′{\displaystyle e’}, который, как думает Алиса, открытый ключ, посланный ей Бобом. Ева перехватывает зашифрованные сообщения от Алисы к Бобу, расшифровывает их с помощью секретного ключа d′{\displaystyle d’}, заново зашифровывает открытым ключом e{\displaystyle e} Боба и отправляет сообщение Бобу. Таким образом, никто из участников не догадывается, что есть третье лицо, которое может как просто перехватить сообщение m{\displaystyle m}, так и подменить его на ложное сообщение m′{\displaystyle m’}. Это подчеркивает необходимость аутентификации открытых ключей. Для этого обычно используют сертификаты. Распределённое управление ключами в PGP решает возникшую проблему с помощью поручителей[неавторитетный источник?][источник не указан 2571 день].

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

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

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

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

Reference¶

class (public_key, encoder)

The public key counterpart to an Curve25519
for encrypting messages.

Parameters

• public_key () – Encoded Curve25519 public key.

• encoder – A class that is able to decode the .

class (private_key, encoder)

Private key for decrypting messages using the Curve25519 algorithm.

Warning

This must be protected and remain secret. Anyone who
knows the value of your can decrypt
any message encrypted by the corresponding

Parameters

• private_key () – The private key used to decrypt messages.

• encoder – A class that is able to decode the .

An instance of that corresponds with
the private key.

classmethod ()

Generates a random object

Returns

An instance of .

class (private_key, public_key)

The Box class boxes and unboxes messages between a pair of keys

The ciphertexts generated by include a 16
byte authenticator which is checked as part of the decryption. An invalid
authenticator will cause the decrypt function to raise an exception. The
authenticator is not a signature. Once you’ve decrypted the message you’ve
demonstrated the ability to create arbitrary valid message, so messages you
send are repudiable. For non-repudiable messages, sign them after
encryption.

Parameters

• private_key – An instance of used
  to encrypt and decrypt messages

• public_key – An instance of used to
  encrypt and decrypt messages

classmethod (encoded, encoder)

Decodes a serialized .

Returns

An instance of .

(plaintext, nonce, encoder)

Encrypts the plaintext message using the given nonce (or generates
one randomly if omitted) and returns the ciphertext encoded with the
encoder.

Warning

It is VITALLY important that the nonce is a nonce,
i.e. it is a number used only once for any given key. If you
fail to do this, you compromise the privacy of the messages
encrypted.

Parameters

• plaintext () – The plaintext message to encrypt.

• nonce () – The nonce to use in the encryption.

• encoder – A class that is able to decode the ciphertext.

Returns

An instance of .

(ciphertext, nonce, encoder)

Decrypts the ciphertext using the nonce (explicitly, when passed as a
parameter or implicitly, when omitted, as part of the ciphertext) and
returns the plaintext message.

Parameters

• ciphertext () – The encrypted message to decrypt.

• nonce () – The nonce to use in the decryption.

• encoder – A class that is able to decode the plaintext.

Return bytes

The decrypted plaintext.

()

Returns the Curve25519 shared secret, that can then be used as a key in
other symmetric ciphers.

Warning

It is VITALLY important that you use a nonce with your
symmetric cipher. If you fail to do this, you compromise the
privacy of the messages encrypted. Ensure that the key length of
your cipher is 32 bytes.

Return bytes

The shared secret.

class (receiver_key)

The SealedBox class can box and unbox messages sent to a receiver key
using an ephemeral sending keypair.

(plaintext, encoder)

Encrypt the message using a Box constructed from an ephemeral
key-pair and the receiver key.

The public part of the ephemeral key-pair will be enclosed in the
returned ciphertext.

The private part of the ephemeral key-pair will be scrubbed before
returning the ciphertext, therefore, the sender will not be able
to decrypt the message.

Parameters

• plaintext () – The plaintext message to encrypt.

• encoder – A class that is able to decode the ciphertext.

Return bytes

The public part of the ephemeral keypair,
followed by the encrypted ciphertext

(ciphertext, encoder)

Decrypt the message using a Box constructed from the receiver key
and the ephemeral key enclosed in the ciphertext.

Parameters

• ciphertext () – The ciphertext message to decrypt.

• encoder – A class that is able to decode the ciphertext.

Return bytes

The decrypted message

Root programs

Some major software contain a list of certificate authorities that are trusted by default. This makes it easier for end-users to validate certificates, and easier for people or organizations that request certificates to know which certificate authorities can issue a certificate that will be broadly trusted. This is particularly important in HTTPS, where a web site operator generally wants to get a certificate that is trusted by nearly all potential visitors to their web site.

The policies and processes a provider uses to decide which certificate authorities their software should trust are called root programs. The most influential root programs are:

Browsers other than Firefox generally use the operating system’s facilities to decide which certificate authorities are trusted. So, for instance, Chrome on Windows trusts the certificate authorities included in the Microsoft Root Program, while on macOS or iOS, Chrome trusts the certificate authorities in the Apple Root Program. Edge and Safari use their respective operating system trust stores as well, but each is only available on a single OS. Firefox uses the Mozilla Root Program trust store on all platforms.

The Mozilla Root Program is operated publicly, and its certificate list is part of the open source Firefox web browser, so it is broadly used outside Firefox. For instance, while there is no common Linux Root Program, many Linux distributions, like Debian, include a package that periodically copies the contents of the Firefox trust list, which is then used by applications.

Root programs generally provide a set of valid purposes with the certificates they include. For instance, some CAs may be considered trusted for issuing TLS server certificates, but not for code signing certificates. This is indicated with a set of trust bits in a root certificate storage system.

Examples

Examples of well-regarded asymmetric key techniques for varied purposes include:

• Diffie–Hellman key exchange protocol
• DSS (Digital Signature Standard), which incorporates the Digital Signature Algorithm
• ElGamal
• Elliptic-curve cryptography
• Various password-authenticated key agreement techniques
• Paillier cryptosystem
• RSA encryption algorithm (PKCS#1)
• Cramer–Shoup cryptosystem
• YAK authenticated key agreement protocol

Examples of asymmetric key algorithms not widely adopted include:

• NTRUEncrypt cryptosystem
• McEliece cryptosystem

Examples of notable – yet insecure – asymmetric key algorithms include:

Merkle–Hellman knapsack cryptosystem

Examples of protocols using asymmetric key algorithms include:

• S/MIME
• GPG, an implementation of OpenPGP
• EMV, EMV Certificate Authority
• IPsec
• PGP
• ZRTP, a secure VoIP protocol
• Transport Layer Security standardized by IETF and its predecessor
• SILC
• SSH
• Bitcoin
• Off-the-Record Messaging

Генерация пары RSA

Вам будет интересно:Как в биосе отключить встроенную звуковую карту: способы для AWARD, AMI и UEFI

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

Генерировать модуль RSA (n).
Подбирают два простых числа p и q.
Находят производный номер e. Число e должно быть больше 1 и меньше (p — 1) (q — 1). Для e и (p — 1) (q — 1) не должно быть общего фактора, кроме 1.
Выполняют шифрование с помощью открытого ключа.
Пара чисел (n, e) формирует открытый ключ RSA. Хотя n является частью открытого ключа, трудности с факторизацией такого числа обеспечивают, что злоумышленник не может найти за конечное время два простых числа (p & q), используемых для получения n. Это понимание является основой RSA.

Создание секретного ключа состоит в следующем. Частный ключ d вычисляется из p, q и e. Для заданных n и e существует единственное число d. Число d является инверсией e по модулю (p — 1) (q — 1). Это означает, что d — это число меньше (p — 1) (q — 1), но такое, что при умножении на e оно равно 1 по модулю (p — 1) (q — 1). Это соотношение написано математически следующим образом:

ed = 1 mod (p − 1)(q − 1).

Расширенный евклидовый алгоритм принимает p, q и e в качестве входных данных и дает d в качестве вывода. Ниже приведен пример создания пары RSA Key. Для удобства понимания простые числа p & q, взятые здесь, являются небольшими значениями. Практически эти значения должны быть очень значимыми.

Алгоритм вычисления:

Пусть два простых числа равны p = 7 и q = 13. Таким образом, модуль n = pq = 7 x 13 = 91.
Выбирают e = 5, что является допустимым выбором, так как нет числа, которое является общим фактором 5 и (p — 1) (q — 1) = 6 × 12 = 72, за исключением 1. Пара чисел (n, e) = (91, 5) формирует открытый ключ и может быть доступна всем, кому нужно отправить зашифрованные сообщения. Вход p = 7, q = 13 и e = 5. Выход будет равен d = 29.
Убеждаются, что вычисленный d правильный — de = 29 × 5 = 145 = 1 mod 72.
Следовательно, открытый ключ — это (91, 5) и закрытые ключи (91, 29).

Why is the elliptic curve used?

The use of elliptical curve multiplication gives you a mathematical connection from your private key to your public key. It also has two important properties:

1. It’s not known how to work backwards to get the private key.

You can go forwards using elliptic curve multiplication, but you cannot do mathematics to go backwards.

This means that there is a mathematical connection going from your private key to your public key, but nobody can use your public key to figure out what your private key is.

Therefore you can give out your public key, but also keep your private key a secret.

2. You can prove that you have the private key without giving it away.

Basically, using some more elliptic curve mathematics, you can create a digital signature that proves that you have the corresponding private key for a public key, without ever having to give away your actual private key.

It’s like saying you have the password to an account, but you don’t have to show anyone your actual password to prove it.

This is thanks to the seeming magic of digital signatures, and it’s all made possible through elliptic curve mathematics.

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

Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркла о распространении открытого ключа, они предложили метод получения секретных ключей, используя открытый канал. Этот метод экспоненциального обмена ключей, который стал известен как обмен ключами Диффи — Хеллмана, был первым опубликованным практичным методом для установления разделения секретного ключа между заверенными пользователями канала. В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом. Эта же схема была разработана Малькольмом Вильямсоном (англ. Malcolm J. Williamson) в 1970-х, но держалась в секрете до 1997 года. Метод Меркле по распространению открытого ключа был изобретён в и опубликован в 1978 году, его также называют загадкой Меркле.

В 1977 году учёными Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом из Массачусетского технологического института был разработан алгоритм шифрования, основанный на проблеме разложения на множители. Система была названа по первым буквам их фамилий (RSA — Rivest, Shamir, Adleman). Эта же система была изобретена в 1973 году Клиффордом Коксом (англ. Clifford Cocks), работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года. RSA стал первым алгоритмом, пригодным и для шифрования, и для цифровой подписи.

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

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

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

Пусть есть 3 ключа KA{\displaystyle K_{A}}, KB{\displaystyle K_{B}}, KC{\displaystyle K_{C}}, распределенные так, как показано в таблице.

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

Теперь можно посылать сообщения группам агентов, не зная заранее состав группы.

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

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

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