Какие математические функции используются в алгоритме шифрования rsa

RSA Algorithm

RSA (Rivest–Shamir–Adleman) algorithm is an asymmetric cryptographic algorithm that is widely used in the modern public-key cryptosystems. We have been hearing RSA algorithm all the time, but some of us actually did not know what it really is and how it works.

In this article, I will systematically discuss the theory behind the RSA algorithm. The theory guarantees that the cryptosystems built on the top of the RSA algorithm are relatively safe and hard to crack, which is fundamentally interesting.

Prerequisites

Euler’s Totient Function

In number theory, Euler’s totient function, also called Euler’s phi function, denoted as $\varphi(n)$, counts the positive integers up to a given integer $n$ that are relatively prime to $n$. In other words, it is the number of integers $k$ in the range $1 \leq k \leq n$ for which the greatest common divisor $\gcd(n, k)$ is equal to 1.

Euler’s totient function is a multiplicative function, meaning that if two numbers $m$ and $n$ are relatively prime, then,

If $k$ numbers, $\$, are pairwise relatively prime, then

A concrete proof of this property could be found here, which requires to use the Chinese remainder theorem.

When $n$ is prime number, according to the definition of prime, $\varphi(n) = n-1$. If $m$ and $n$ are different prime numbers, because $m$ and $n$ are relatively prime, we have

Euler’s Theorem

If $m$ and $n$ are relatively prime, then,

where $\varphi(n)$ is Euler’s totient function. This theorem is very famous, and there a couple of different proofs to it. One of the proofs could be found here.

Multiplicative Inverse Theorem

Let $n$ and $x$ be positive integers. Then $x$ has a multiplicative inverse modulo $n$ if and only if $\gcd(n, x) = 1$. Moreover, if it exists, then the multiplicative inverse is unique.

Equivalently, that is to say, let $n$ and $x$ be positive integers,

$y \bmod n$ exists if and only if $\gcd(n, x) = 1$, and $y \bmod n$ is unique.

Note that as long as the multiplicative inverse $y \bmod n$ exists, all the integers that has the same $y \bmod n$ satisfy $xy \equiv 1 \pmod n$. But there is only one such integer that is $0 \leq y \leq n-1$. For instance, if there is a $y^\ast$ such that $xy^\ast \equiv 1 \pmod n$, then $xy^\ast — 1 = kn$ for some integer $k$. Any other $y$ where $y=y^\ast + tn$, for any integer $t$, also satisfies $xy — 1 = k^\prime n$ for some integer $k^\prime$ (This is easy to show). Therefore, we also have $xy \equiv 1 \pmod n$. Because there could be infinite number of $y$ which satisfies $xy \equiv 1 \pmod n$, we consider the multiplicative inverse to be $y \bmod n$ which is unique if it exists.

To prove for the sufficient condition and the uniqueness. There are $n$ possibilities of $y \pmod n$, $0, 1, 2, \cdots, n-1$. Then the value of $xy$ could be $0x, 1x, 2x, \cdots, (n-1)x$. We are going to show that $0x \bmod n, 1x \bmod n, 2x \bmod n, \cdots, (n-1)x \bmod n$ are distinct if $\gcd(n, x) = 1$. Suppose there are two distinct integer $a, b$, $0 \leq a, b \leq n-1$, and $ax \equiv bx \pmod n$. Then $(a-b)x = kn$ for some integer $k$. Because $\gcd(n, x) = 1$, $a-b = hn$ for some integer $h$. However, since $a-b$ is in a range of $[-n+1, n-1]$ and $a-b \neq 0$ because $a$ and $b$ are distinct, there is no integer $h$ which could satisfy $a-b = hn$. Thus, $0x \bmod n, 1x \bmod n, 2x \bmod n, \cdots, (n-1)x \bmod n$ have to be distinct if $\gcd(n, x) = 1$. Since there are $n$ possible values for $0x \bmod n, 1x \bmod n, 2x \bmod n, \cdots, (n-1)x \bmod n$ which are distinct, there is only one of them which must be 1. Therefore, $y \bmod n$ exists if $\gcd(n, x) = 1$ and $y \bmod n$ is unique.

To prove for the necessary condition. Given non-negative integer $y$ such that $xy \equiv 1 \pmod n$, we have $xy — 1 = kn$ for some integer $k$. Suppose $\gcd(n, x) > 1$, we divide $\gcd(n, x)$ at both sides of the equation.

Because $\frac<\gcd(n, x)>$ and $\frac<\gcd(n, x)>$ are integers, but $\frac<1><\gcd(n, x)>$ is not an integer because $\gcd(n, x) > 1$, there is no way for the equivalence. This raises a contradiction. Therefore, $\gcd(n, x) = 1$ if $y \bmod n$ exists.

This concludes the proof. $\square$

Lemma 1

If $m$ and $n$ are relatively prime, then,

where $\varphi(n)$ is Euler’s totient function, and $k$ could be any integer.

Using the compatibility with scaling in modular arithmetic properties, we multiply $m$ at both sides of $m^ <\varphi(n)>\equiv 1 \pmod n$ from Euler’s theorem, we have

We further multiply $m^<\varphi(n)>$ at the both sides of $m^ <\varphi(n)+1>\equiv m \pmod n$, we have

By induction, we could show that

for any non-negative integer $k$.

Similarly, we multiply $m^<-\varphi(n)>$ at the both sides of $m^ <\varphi(n)+1>\equiv m \pmod n$, we have

By induction, we could show that

for any negative integer $-k$.

This concludes the proof that the congruence is valid for any integer $k$. $\square$

RSA Algorithm

Basic Features of Public-Key Cryptosystems

The RSA algorithm is used as a typical public-key cryptosystem. Therefore, it has to match the four basic features for public-key cryptosystems. I am copying the descriptions for the features for the completeness of this article.

The encryption and decryption functions using the public key and private key in the RSA algorithm are denoted by $E$ and $D$, respectively. $M$ is used to represent the message to be encrypted and sent. The four basic features of a public-key cryptosystem, as well as the RSA algorithm, are:

• Decrypting an encrypted message gives you the original message.

• Encrypting a decrypted message gives you the original message.

$E$ and $D$ are easy to compute.

The publicity of $E$ does not compromise the secrecy of $D$.

RSA Basic Principle

A basic principle behind RSA is the observation that it is practical to find three very large positive integers $e$, $d$ and $n$ such that with modular exponentiation for all integers $m$ (with $0 \leq m < n$):

Here, the tuple $(n, e)$ is usually called the public key for encryption, and the tuple $(n, d)$ is usually called the private key for decryption. $m$ is the message because you could always represent a message using an integer uniquely. If somehow the message is too long and $m$ exceeds $n$, we dissect the messages into trunks and encrypt separately.

RSA Key Generations

We would show how the $e$, $d$, and $n$ were generated in the RSA algorithm to satisfy the RSA basic principle.

In the RSA algorithm,

where $p$ and $q$ are some large distinct prime numbers.

Because of the Euler’s theorem in the prerequisite, if the message $m$ and $n$ are relatively prime, then

where $\varphi(n)$ is Euler’s totient function.

There is an extremely rare case that when $m$ and $n$ are not relatively prime, that is only when $m = p$ or $m = q$, the decryption of the encrypted message would not recover the original content of the message. If we were that lucky, we would have cracked the RSA encryption system.

I am not sure if people have set rules to eliminate this extremely rare corner case. If we really want to do so, in each encryption, we could encrypt the same message several times, say three times, using $E(m)$, $E(m+1)$, and $E(m+2)$. We also have the digital signature for each of the messages. If the messages were from the authentic author, there is no message content modification, and we did not hit $p$ and $q$ by chance, the three digital signatures should all pass the digital signature verifications. We would recover the three messages, $m$, $m+1$, and $m+2$, and further recover the three messages to the exact same message $m$, $m$ and $m$. However, if we somehow hit $p$ or $q$ by chance, some of the digital signatures would fail the verification. We just have to extract the message information from the messages that passed the digital signature verification. After all, the three messages contain the exact same information. According to the pigeonhole principle, the three distinct messages could not be all relatively prime to $p$ or $q$.

Based on the property of the Euler’s totient function in the prerequisite, computing the Euler’s totient function for the product of two distinct prime numbers is actually very easy.

Based on the Lemma 1 in the prerequisite, for any integer $k$,

We immediately found that, based on the RSA basic principle, $ed = k\varphi(n)+1$. Although $n$ is public, factorizing $n$ to $p$ and $q$ is almost impossible using an modern computer, computing $\varphi(n)$ using mathematical definition and the equation $\varphi(n) = (p-1)(q-1)$ are almost not possible neither. Therefore, releasing $e$ as the public key does not lead to the disclosure of $d$ easily.

Then the question becomes how to choose appropriate integers $e$ and $d$. It seems that $e$ and $d$ could be any values as long as the equivalence $ed = k\varphi(n)+1$ is satisfied for some integer $k$.

This is equivalent to say we need to satisfy

Based on the multiplicative inverse theorem in the prerequisite, as long as $\gcd(e,\varphi(n)) = 1$, there must be a unique $d$ which satisfies the above congruence. Getting such $e$ might not be hard. Although $e$ does not have to be prime, for our convenience, we could simply select a prime number from a corpus of prime numbers and verify whether $\gcd(e,\varphi(n)) = 1$ since verifying relatively primeness is easy if one of the numbers are known to be prime. A typical $e$ generally used could be 65537, which is a prime number.

Once $e$ is determined, $d \bmod \varphi(n)$ could be determined using the Extend Euclidean algorithm which takes $O((\log\varphi(n))^2)$ to run. Note that it is not necessary to make $d$ infinitely large large to make the private key $d$ less suspectable to cracking. Using any $d$s that have the same remainder $d \bmod \varphi(n)$ decrypt the encrypted message exactly the same.

With such $e$ and $d$, the RSA basic principle is satisfied.

Message Encryption and Decryption

With the orchestrated $e$ and $d$, and the RSA basic principle, it is not hard to find that the encryption function $E$ is

where $c$ is the encrypted message. In practice,

The decryption function $D$ is

$$
c^d \equiv (m^e)^d \equiv m \pmod n
$$

In the above congruences, the first congruence is due to the compatibility with exponentiation in modular arithmetic properties, the second congruence is because of the RSA basic principle. Similarly, in practice,

Without any doubt, using such encryption and decryption, the first feature of the public-key cryptosystem, decrypting an encrypted message gives you the original message, is satisfied.

If we swap the positions of $e$ and $d$ in the RSA basic principle, surprisingly (or not?), the congruences and equivalences still hold, meaning that the second feature of the public-key cryptosystem, encrypting an decrypted message gives you the original message, also holds.

How about the third feature, $E$ and $D$ are easy to compute? $E$ and $D$ both involve exponential computations which would be extremely slow and memory consuming (actually no memory so far could fit a number with not very large exponents) using trivial algorithms if the exponents $e$ and $d$ are large. However, given $e$, it is meaningless for $d$ to be “infinitely” large to satisfy the congruence $ed \equiv 1 \pmod <\varphi(n)>$. Note that only $e$ and $d \bmod \varphi(n)$ are the actual keys. In addition, there are actually fast modular exponentiation algorithms which take $O(\log e)$ or $O(\log d)$ (i.e., $O(\log (d \bmod \varphi(n)))$) to run and are memory saving. We would not elaborate on it here, and would take it for granted that the third feature is satisfied.

The fourth feature of the public-key cryptosystems has also been satisfied. We have seen the related information in the earlier sections and will see more in the following sections.

Cracking the RSA Cryptosystem

Modern Computer

Cracking the RSA encryption system using brute force is not practically feasible. If the private key $d$ is large, it would take an extremely large number of iterations to guess the correct private key $d$, not even mention in each iteration, since you usually don’t know the message content, there is hardly any way to verify whether the decrypted message using the guessed private key $d$ is the original message that you have never seen.

A better way is to factorize the public $n$. If somehow you know the value of $\varphi(n)$, with the public key $e$, you would derive the value of $d \bmod \varphi(n)$. Remember what is important in the RSA algorithm is $d \bmod \varphi(n)$ instead of the actual value of $d$.

Quantum Computer

The ordinary algorithm to do integer factorization takes sub-exponential time according to the Wikipedia. This is the fundamental reason which makes the RSA cryptosystem so reliable.

Quantum computer, however, is good at integer factorization. Using Shor’s algorithm, quantum computer does integer factorization in polynomial time, which makes cracking the RSA cryptosystem possible.

Какие математические функции используются в алгоритме шифрования rsa

Криптосистема [math]\mathtt[/math] стала первой системой, пригодной и для шифрования, и для цифровой подписи.

Содержание

Реализация

Алгоритм [math]\mathtt[/math] включает в себя четыре этапа: генерация ключей, передача ключей, шифрование и расшифрование.

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

Определение:

Односторонняя функция (англ. one-way function) — математическая функция, которая легко вычисляется для любого входного значения, но задача нахождения аргумента по заданному значению функции относится к классу NP-полных задач.

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

В основу криптографической системы с открытым ключом [math]\mathtt[/math] положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложение числа на простые множители. В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе [math]\mathtt[/math] каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме [math]\mathtt[/math] образуют «согласованную пару» в том смысле, что они являются взаимно обратными. То есть для любых допустимых пар открытого и закрытого ключей [math](p,s)[/math] существуют соответствующие функции шифрования [math]E_p(x)[/math] и расшифрования [math]D_s(x)[/math] такие, что для любого сообщения [math]m \in M[/math] , где [math]M[/math] — множество допустимых сообщений, [math]m=D_s(E_p(m))=E_p(D_s(m)).[/math]

Создание открытого и секретного ключей

[math]\mathtt[/math] -ключи генерируются следующим образом:

1. Выбираются два различных случайных простых числа [math]p[/math] и [math]q[/math] заданного размера (например, [math]1024[/math] бита каждое).
2. Вычисляется их произведение [math]n=p\cdot q[/math] , которое называется модулем.
3. Вычисляется значение функции Эйлера от числа [math]n[/math] : [math]\varphi(n) = (p-1)\cdot (q-1).[/math]
4. Выбирается целое число [math]e[/math] ( [math]1 \lt e \lt \varphi(n)[/math] ), взаимно простое со значением функции [math]\varphi(n)[/math] . Обычно в качестве [math]e[/math] берут простые числа, содержащие небольшое количество единичных бит в двоичной записи.
   • Число [math]e[/math] называется открытой экспонентой (англ. public exponent)
   • Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в [math]e[/math] .
   • Слишком малые значения [math]e[/math] , например [math]3[/math] , потенциально могут ослабить безопасность схемы [math]\mathtt[/math] .
5. Вычисляется число [math]d[/math] , мультипликативно обратное к числу [math]e[/math] по модулю [math]\varphi(n)[/math] , то есть число, удовлетворяющее сравнению: [math]d\cdot e \equiv 1 \pmod<\varphi(n)>.[/math] Примечание Сравнеие двух целых чисел по модулю натурального числа [math]m[/math] — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на [math]m[/math] один и тот же остаток. Любое целое число при делении на [math]m[/math] дает один из [math]m[/math] m возможных остатков: число от [math]0[/math] до [math]m-1[/math] .
   • Число [math]d[/math] называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
6. Пара [math]\left\< e, n \right\>[/math] публикуется в качестве открытого ключа [math]\mathtt[/math] (англ. [math]\mathtt[/math] public key).
7. Пара [math]\left\< d, n \right\>[/math] играет роль закрытого ключа [math]\mathtt[/math] (англ. [math]\mathtt[/math] private key) и держится в секрете.

Определение:

Случайное простое число (англ. random prime numbers) — в криптографии, простое число, содержащее в двоичной записи заданное количество битов.

Передача ключей

Предположим, что Боб хочет отправить Алисе информацию . Если они решат использовать [math]\mathtt[/math] , Боб должен знать открытый ключ Алисы для того чтобы зашифровать сообщение, а Алиса должна использовать свой закрытый ключ для расшифрования сообщения. Чтобы позволить Бобу отправлять свои зашифрованные сообщения, Алиса передает свой открытый ключ Бобу через надежный, но не обязательно секретный маршрут. Закрытый ключ Алисы никогда никому не передается.

Шифрование

Предположим, Боб хочет послать Алисе сообщение [math]m[/math] . Сообщениями являются целые числа в интервале от [math]0[/math] до [math]n — 1[/math] , то есть [math]m \in \mathbb_[/math] . Алгоритм:

• Взять открытый ключ [math](e,n)[/math] Алисы
• Взять открытый текст [math]m[/math]
• Зашифровать сообщение с использованием открытого ключа Алисы: [math]c = E(m) = m^e \mod n

Расшифрование

• Принять зашифрованное сообщение [math]c[/math]
• Взять свой закрытый ключ [math](d,n)[/math]
• Применить закрытый ключ для расшифрования сообщения: [math]m = D(c) = c^d \mod n

Корректность схемы [math]\mathtt[/math]

Действительно, для [math]\forall m \in \mathbb_[/math]

[math]\forall m \in \mathbb_: m^ \equiv m \pmod

[/math] .

Возможны два случая:

• [math]m \not\equiv 0 \pmod

  [/math] .

Поскольку числа [math]e[/math] и [math]d[/math] являются взаимно обратными относительно умножения по модулю [math]\varphi(n)=(p-1)(q-1)[/math] , то есть

[math]ed=1+k(p-1)(q-1)[/math] для некоторого целого [math]k[/math] ,

[math]\begin m^ & \equiv m^ <1 + k\left(

\right)\left( \right)> \pmod

\\ & \equiv m\left( > \right)^ \right)> \pmod

\\ & \equiv m\left( 1 \right)^ \right)> \pmod

\equiv m \pmod

\end[/math]

где второе тождество следует из теоремы Ферма.

• Рассмотрим второй случай:

[math]m^ \equiv 0 \pmod

\equiv m \pmod

[/math]

Таким образом, при всех [math]m[/math] выполняется равенство

[math]m^ \equiv m \pmod

[/math]

Аналогично можно показать, что:

[math]\forall m \in \mathbb_: m^ \equiv m \pmod[/math] .

Криптографическая стойкость

Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования

[math]c = E(m) = m ^ e \mod n[/math] .

Для вычисления [math]m[/math] по известным [math]c, e, n[/math] нужно найти такой [math]d[/math] , чтобы

[math]e \cdot d \equiv 1 \pmod<\varphi(n)>,[/math]

Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение [math]\varphi(n)[/math] . Для вычисления функции Эйлера от известного числа [math]n[/math] необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — «потайной дверцей» (англ. backdoor), которая используется для вычисления [math]d[/math] владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, факторизации, самый быстрый из которых на сегодняшний день — общий метод решета числового поля, скорость которого для k-битного целого числа составляет

[math] \exp (( c + o(1))k^<\frac<1><3>> \log^<\frac<2><3>>k)[/math] для некоторого [math]c \lt 2[/math] .

В [math]2010[/math] году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта [math]\mathtt[/math] длиной [math]768[/math] бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только [math]\mathtt[/math] -ключи длиной [math]1024[/math] бита и более. Причём от шифрования ключом длиной в [math]1024[/math] бит стоит отказаться в ближайшие три-четыре года. С [math]31[/math] декабря [math]2013[/math] года браузеры Mozilla перестали поддерживать сертификаты удостоверяющих центров с ключами [math]\mathtt[/math] меньше [math]2048[/math] бит.

Применение

Система [math]\mathtt[/math] используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP [1] и иных системах шифрования (к примеру, DarkCryptTC [2] и формат xdc [3] ) в сочетании с симметричными алгоритмами.

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

Алгоритм шифрования сеансового ключа выглядит следующим образом:

Шифрование

• Взять открытый ключ [math](e,n)[/math] Алисы
• Создать случайный сеансовый ключ [math]m[/math]
• Зашифровать сеансовый ключ с использованием открытого ключа Алисы: [math]c = E(m) = m^e \mod n[/math]
• Расшифровать сообщение [math]C[/math] с помощью сеансового ключа симметричным алгоритмом: [math]M_A = D_m(C)[/math]

Расшифрование

• Принять зашифрованный сеансовый ключ Боба [math]c[/math]
• Взять свой закрытый ключ [math](d,n)[/math]
• Применить закрытый ключ для расшифровывания сеансового ключа: [math]m = D(c) = c^d \mod n[/math]
• Зашифровать сообщение [math]M_A[/math] с помощью сеансового ключа симметричным алгоритмом: [math]C = E_m(M_A)[/math]

Минусы

Алгоритм [math]\mathtt[/math] намного медленнее, чем AES [4] и другие алгоритмы, использующие симметричные блочные шифры.

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

Из-за низкой скорости шифрования (около [math]30[/math] кбит/с при [math]512[/math] битном ключе на процессоре [math]2[/math] ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным сеансовым ключом (например, IDEA [5] , Serpent [6] , Twofish [7] ), а с помощью [math]\mathtt[/math] шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема.

RSA: от простых чисел до электронной подписи

Выясняем, как и откуда можно получить электронную подпись на примере криптосистемы RSA.

Содержание

Определения и обозначения

Описание криптосистемы RSA

Асимметричные криптографические системы

Шифрование и дешифрование

Получение подписи сообщения по RSA

Электронная подпись документов

Введение

Наверняка вы сталкивались с таким понятием, как «электронная подпись». Если обратиться к федеральному закону, то можно найти следующее её определение:

«Электронная подпись — информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией и которая используется для определения лица, подписывающего информацию»

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

Задача ЭП ясна, теперь хотелось бы увидеть и прочувствовать, что именно скрывается за этими двумя словами. Копаясь дальше в гугле, можно найти довольно много различных алгоритмов создания цифровой подписи (DSA, ГОСТ Р 34.10-2012, RSA-PSS и т.д.), разбираться в которых неподготовленному пользователю сложно.

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

Теорминимум

(На картинке изображён Лев Ландау, автор «теорминимума», серии экзаменов по теоретической физике)

Сформируем небольшой словарик терминов, которые нам пригодятся далее:

Открытый текст – данные, подлежащие шифрованию или полученные в результате расшифрования

Шифртекст – данные, полученные в результате применения шифра к открытому тексту

Шифр – совокупность обратимых преобразований, зависящая от некоторого параметра (ключа)

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

Факторизация – процесс разложения числа на простые множители.

НОД – наибольший общий делитель.

Числа a и b называются взаимно простыми, если НОД этих чисел равен 1.

Функция Эйлера φ(n) – функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним.

Хочу отметить, что на данном этапе подразумевается, что вы знакомы с арифметическими операциями по модулю. Если нет, то здесь можно о них почитать.

Как оно устроено

Прежде, чем окунуться в необъятный мир математики рассмотреть, как именно устроена RSA, обратимся к тому, как работают

Асимметричные криптосистемы

Рассмотрим задачу сохранности содержимого посылки при передаче от отправителя к адресату. Вот картинка с многим полюбившимся Алисой и Бобом:

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

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

Теперь к математике

Асимметричные криптографические системы основаны на так называемых односторонних функциях с секретом. Под односторонней понимается такая функция я y=f(x), которая легко вычисляется при имеющемся x, но аргумент x при заданном значении функции вычислить сложно. Аналогично, односторонней функцией с секретом называется функция y=f(x, k), которая легко вычисляется при заданном x, причём при заданном секрете k аргумент x по заданному y восстановить просто, а при неизвестном k – сложно.

Подобным свойством обладает операция возведения числа в степень по модулю:

Здесь φ(n) – функция Эйлера числа n. Пока условимся, что это работает, далее это будет доказано более строго. Теперь нужно понять, что из это является ключами Боба, а что сообщением. В нашем распоряжении имеются числа c, m, n, e, d.

Давайте посмотрим на первое выражение. Здесь число c получено в результате возведения в степень по модулю числа m. Назовём это действие шифрованием. Тогда становится очевидно, что m выступает в роли открытого текста, а c – шифртекста. Результат c зависит от степени e, в которую мы возводим m, и от модуля n, по которому мы получаем результат шифрования. Эту пару чисел (e, n) мы будем называть открытым ключом. Им Алиса будет шифровать сообщение.

Смотрим на второе действие. Здесь d является параметром, с помощью которого мы получаем исходный текст m из шифртекста c. Этот параметр мы назовём закрытым ключом и выдадим его Бобу, чтобы он смог расшифровать сообщение Алисы.

Что есть что разобрались, теперь перейдём к конкретике, а именно – генерации ключей Боба. Давайте выберем число n такое, что:

где p и q – некоторые разные простые числа. Для такого n функция Эйлера имеет вид:

Такой выбор n обусловлен следующим. Как вы могли заметить ранее, закрытый ключ d можно получить, зная открытый e. Зная числа p и q, вычислить функцию Эйлера не является вычислительно сложной задачей, ровно как и нахождение обратного элемента по модулю. Однако в открытом ключе указано именно число n. Таким образом, чтобы вычислить значение функции Эйлера от n (а затем получить закрытый ключ), необходимо решить задачу факторизации, которая является вычислительно сложной задачей для больших n (в современных системах, основанных на RSA, n имеет длину 2048 бит).

Возвращаемся к генерации ключей. Выберем целое число e:

Для него вычислим число d:

Для отыскания числа, обратного по модулю, можно воспользоваться алгоритмом Евклида.

Мы завершили с этапом генерации ключей. Теперь Боб публикует свой открытый ключ (e, n), прячет закрытый d, а мы переходим к Алисе.

Шифруем, дешифруем.

Возьмём в качестве сообщения число m (m ∈ [1, n − 1]). Чтобы Алисе зашифровать его, необходимо возвести его в степень e по модулю n. Эти числа идут вместе с открытым ключом Боба:

Здесь за с обозначен шифртекст, который Алиса будет должна передать Бобу. Отметим также, что c ∈ [1, n − 1], как и m. Расшифруем шифртекст, возведя его в степень закрытого ключа Боба d:

А теперь ответим на вопрос, почему m ≡ m′ . Ниже я приведу доказательство данного утверждения, но если оно (доказательство) вам не сильно интересно, то можете его пропустить и просто поверить, что это так.

Здесь нам понадобится теорема Эйлера:

Также полезной будет китайская теорема об остатках:

Получаем подпись сообщения

Ещё раз напишем две ключевые формулы шифрования и расшифрования соответственно:

Теперь давайте предположим, что Боб хочет отправить Алисе открытку m от своего имени. У Боба в распоряжении уже имеются два ключа (e, n) и d, которые он сгенерировал по алгоритму, описанному ранее. Поскольку d является закрытым ключом, то можно им воспользоваться как уникальным идентификатором Боба. Давайте «зашифруем» m с помощью d:

Результат данной операции и есть подпись сообщения Боба. Заметим, что подпись напрямую зависит от подписываемого сообщения, а не только от того, что его подписывает Боб. Далее, Алиса получает сообщение m, подпись s и открытый ключ (e, n). По аналогии с расшифрованием, проверка подписи осуществляется возведением подписи s в степень открытой экспоненты e:

Если Алиса получила, что m ≡ m′, то подпись считается правильной.

Дочитавших до этого места хочу поздравить с получением первой цифровой подписи «на бумаге»!

Подпись документов

Рассмотренный алгоритм получения подписи изящен и прост в осознании, однако операция возведения в степень несколько «мешается». Наша текущая задача – подписать объёмный документ. Чтобы сэкономить время, мы не будем подписывать содержимое документа, а прибегнем к помощи хэш-функций (если вы не знаете, что такое хэш-функция, рекомендую почитать википедию). Скажу лишь то, что выходная последовательность хэш-функции имеет небольшую (по сравнению с размером ключей) длину, а также по имеющемуся хэшу нельзя однозначно восстановить исходные данные.

На картинках наглядно показано, в какой момент мы используем хэширование. Создание подписи:

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

Заключение

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

Отмечу, что другие существующие алгоритмы создания ЭП основаны на схожих принципах, поэтому надеюсь, что после прочтения этой статьи вам будет проще разобраться в них. «Следующей по сложности» я обозначу криптосистему Эль-Гамаля, но о ней уже не в этом посте.

Спасибо за внимание!

Источники

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone

Криптографические методы защиты информации: учеб. пособие / С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий; под ред. А. В. Уривского. – М.: МФТИ, 2016

Маховенко Е. Б. Теоретико-числовые методы в криптографии — М.: Гелиос АРВ, 2006.

NIST Special Publication 800-57 Part 3 Revision 1

Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи. – СПб.: БХВ-Петербург, 2010. — Учебное пособие

Что такое шифрование RSA и как оно работает?

Шифрование RSA — это система, которая решает то, что когда-то было одной из самых больших проблем в криптографии: Как вы можете отправить кому-то закодированное сообщение не имея возможности ранее поделиться кодом с ними?

Эта статья научит вас всему, что вам нужно знать о как было разработано шифрование RSA, как это устроено, математика за этим, для чего он используется а также некоторые из самые большие проблемы безопасности, с которыми он сталкивается. Изучение RSA даст вам некоторые базовые знания, которые помогут вам понять, сколько частей нашей онлайн-жизни защищены.

Что такое шифрование RSA?

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

Если бы секрет был достаточно важен, вы не рискнули бы его записать в обычном порядке — шпионы или мошенник-почтальон могли бы просмотреть вашу почту. Кроме того, кто-то может прослушивать ваш телефон без вашего ведома и регистрировать каждый ваш звонок.

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

Если у вас была возможность поделиться кодом с вашим другом заранее, то любой из вас может отправить зашифрованное сообщение в любое время, зная, что вы двое — единственные, у кого есть возможность прочитать содержимое сообщения. Но что, если у вас не было возможности поделиться кодом заранее?

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

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

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

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

Смотрите также: Криптография с открытым ключом

Где используется шифрование RSA?

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

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

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

Шифрование RSA может использоваться в ряде различных систем. Это может быть реализовано в OpenSSL, wolfCrypt, cryptlib и ряде других криптографических библиотек..

Являясь одной из первых широко используемых схем шифрования с открытым ключом, RSA заложила основы для большей части наших безопасных коммуникаций. это было традиционно используется в TLS и был также оригинальный алгоритм, используемый в шифровании PGP. RSA по-прежнему используется в различных веб-браузерах, электронной почте, VPN, чатах и ​​других каналах связи..

RSA также часто используется для создания безопасных соединений между VPN-клиентами и VPN-серверами. В таких протоколах, как OpenVPN, рукопожатия TLS могут использовать алгоритм RSA для обмена ключами и установления безопасного канала..

Фон шифрования RSA

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

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

Последняя часть головоломки — это то, что мы сейчас называем Обмен ключами Диффи-Хеллмана. Малколм Дж. Уильямсон, другой сотрудник, выяснил схему, которая позволяла двум сторонам совместно использовать ключ шифрования, даже если злоумышленники контролировали канал.

Вся эта работа была предпринята в разведывательном агентстве Великобритании, правительственном штабе связи (GCHQ), который держал открытие в секрете. Частично из-за технологических ограничений GCHQ не мог видеть использование криптографии с открытым ключом в то время, поэтому разработка стояла на полке, пылясь. Лишь в 1997 году работа была рассекречена, и первоначальные изобретатели RSA были признаны.

Спустя несколько лет подобные концепции начали развиваться в публичной сфере. Ральф Меркл создал раннюю форму криптография с открытым ключом, который повлиял на Уитфилда Диффи и Мартина Хеллмана в дизайне обмена ключами Диффи-Хеллмана.

В идеях Диффи и Хеллмана отсутствовал один важный аспект, который сделал бы их работу основой криптографии с открытым ключом. Это был односторонняя функция, которую было бы трудно инвертировать. В 1977 году, Рон Ривест, Ади Шамир и Леонард Адлеман, чьи фамилии образуют аббревиатуру RSA, после года работы над решением этой проблемы было найдено решение.

Ученые из Массачусетского технологического института совершили прорыв после Пасхальной вечеринки в 1977 году. После ночи питья Ривест отправился домой, но вместо сна он лихорадочно провел вечер, сочиняя статью, в которой его идея была оформлена для необходимой односторонней функции..

Идея была запатентована в 1983 году MIT, но только в первые дни Интернета, алгоритм RSA начал рассматривать широкое распространение как важный инструмент безопасности.

Как работает шифрование RSA?

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

Есть несколько различных концепций, которые вы должны обдумать, прежде чем мы сможем объяснить, как все это сочетается. Это включает функции люка, порождающие простые числа, общая функция Кармайкла и отдельные процессы, участвующие в вычисление открытых и закрытых ключей используется в процессах шифрования и дешифрования.

Функции люка

RSA-шифрование работает при условии, что алгоритм легко вычислить в одном направлении, но почти невозможно наоборот. Например, если вам сказали, что 701111 — это произведение двух простых чисел, вы бы смогли выяснить, что это за два числа?

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

Если бы вам было достаточно скучно, вы бы смогли вытащить свой телефон или, возможно, посчитать его в своей голове, чтобы обнаружить, что ответ — это ранее упомянутые 701111. Эти 907 и 773 являются простыми числами, которые отвечают на наш первый вопрос, который показывает нам, что некоторые уравнения можно легко вычислить одним способом, но, по-видимому, невозможно наоборот.

Еще один интересный аспект этого уравнения заключается в том, что легко вычислить одно из простых чисел, если у вас уже есть другое, а также продукт. Если вам говорят, что 701111 является результатом 907, умноженного на другое простое число, вы можете выяснить это другое простое число с помощью следующего уравнения:

701,111 ÷ 907 = 773

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

Из-за этого RSA использует гораздо большие числа. Размер простых чисел в реальной реализации RSA варьируется, но в 2048-битном RSA они собираются вместе для создания ключей длиной 617 цифр. Чтобы помочь вам визуализировать это, ключом будет число такого размера:

Генерация простых чисел

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

Первым шагом шифрования сообщения с помощью RSA является генерировать ключи. Для этого нам нужно два простых числа (п и Q) которые выбраны с тестом на первичность. Тест на простоту — это алгоритм, который эффективно находит простые числа, такой как тест на простоту Рабина-Миллера.

Простые числа в RSA должны быть очень большими, а также относительно далеко друг от друга. Числа, которые являются маленькими или ближе друг к другу, намного легче взломать. Несмотря на это, в нашем примере будут использоваться меньшие числа, чтобы было легче следить и вычислять.

Допустим, тест на простоту дает нам простые числа, которые мы использовали выше, 907 и 773. Следующим шагом является обнаружение модуля (N), используя следующую формулу:

N знак равно п Икс Q

где п = 907 и Q = 773

N = 907 х 773

Тотальная функция Кармайкла

Как только мы N, мы используем Общая функция Кармайкла:

λ(Nзнак равно LCM (п — 1, Q — 1)

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

Для тех, кто не в курсе, λ (п) представляет кармайкл N, пока LCM означает самый низкий общий множитель, который является самым низким числом, которое оба п и Q можно разделить на. Есть несколько различных способов выяснить это, но самый простой — довериться онлайн-калькулятору, который сделает уравнение для вас. Итак, давайте поместим наши числа в уравнение:

λ(701111знак равно LCM (907 — 1, +773 — 1)

λ(701111знак равно LCM (906, +772)

Используя калькулятор, связанный выше, это дает нам:

λ(701111) = 349 716

Генерация открытого ключа

Теперь, когда у нас есть число Кармайкла наших простых чисел, это время, чтобы выяснить наш открытый ключ. Под RSA, открытые ключи состоят из простого числа е, также как и N. Число е может быть что угодно между 1 и значением для λ(N), что в нашем примере составляет 349,716.

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

Наши последние зашифрованные данные называются зашифрованным текстом (с). Мы выводим это из нашего открытого текста сообщения (м), применяя открытый ключ по следующей формуле:

с знак равно ме мод n

Мы уже придумали е и мы знаем N также. Единственное, что нам нужно объяснить, это модификация. Это немного из глубины этой статьи, но это относится к по модулю операции, что по существу означает остаток, оставшийся, когда вы делите одну сторону на другую. Например:

10 модификация 3 = 1

Это потому, что 3 входит в 10 три раза с остатком 1.

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

с знак равно ме модификация N

с = 411 модификация 701111

с = 4 194 304 модификация 701111

Опять же, чтобы сделать по модулю операции Легко, мы будем использовать онлайн калькулятор, но вы можете сами в этом разобраться. Ввод 4 194 304 в онлайн-калькулятор, он дает нам:

с = 688 749

Поэтому, когда мы используем RSA для шифрования нашего сообщения, 4, с нашим открытым ключом, это дает нам зашифрованный текст 688,749. Предыдущие шаги могли показаться слишком сложными, но важно повторить то, что на самом деле произошло.

У нас был сообщение 4, который мы хотели сохранить в секрете. Мы применили к нему открытый ключ, который дал нам зашифрованный результат 688 749. Теперь, когда он зашифрован, мы можем безопасно отправить номер 688,749 владельцу пары ключей. Они являются единственным человеком, который сможет расшифровать его с помощью своего закрытого ключа. Когда они расшифруют его, они увидят сообщение, которое мы действительно отправляли., 4.

Генерация закрытого ключа

В RSA-шифровании после преобразования данных или сообщений в зашифрованный текст с открытым ключом их можно расшифровать только с помощью закрытого ключа из той же пары ключей.. Закрытые ключи состоят из d и N. Мы уже знаем N, и следующее уравнение используется, чтобы найти d:

d = 1 /е мод λ(N)

в Генерация открытого ключа раздел выше, мы уже решили, что в нашем примере, е будет равно 11. Точно так же мы знаем, что λ(N) равняется 349 716 от нашей предыдущей работы под Тотальная функция Кармайкла. Все становится немного сложнее, когда мы сталкиваемся с этим разделом формулы:

1 /е модификация

Это уравнение может выглядеть так, будто оно просит вас разделить 1 на 11, но это не так. Вместо этого это просто символизирует, что нам нужно рассчитать модульная обратная из е (который в данном случае равен 11) и λ(N) (что в данном случае составляет 349 716).

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

d = 1 /11 модификация 349716

Чтобы выполнить эту операцию, просто введите 11 (или любое значение, которое вы можете иметь для е если вы пытаетесь это на собственном примере), где это говорит целое число и 349 716 (или любое значение, которое вы можете иметь для λ(N) если вы пытаетесь это на собственном примере), где говорится Модульное в онлайн калькуляторе, который был связан выше. Если вы сделали это правильно, вы должны получить результат, где:

d = 254, 339

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

м знак равно сd мод n

Теперь мы можем вернуться к зашифрованному тексту, который мы зашифровали под Генерация закрытого ключа раздел. Когда мы зашифровали сообщение открытым ключом, это дало нам значение для с 688 749. Сверху мы знаем, что d равняется 254 339. Мы также знаем, что N равно 701111. Это дает нам:

м = 688 749254339 модификация 701111.

Как вы, возможно, заметили, попытка привести число к 254 339-й степени может быть немного больше для большинства обычных калькуляторов. Вместо этого мы будем использовать онлайн-калькулятор расшифровки RSA. Если вы хотите использовать другой метод, вы бы применили полномочия, как обычно, и выполняли бы операцию модуля так же, как мы это делали в Генерация открытого ключа раздел.

В калькуляторе, указанном выше, введите 701111, где написано Модуль питания: N, 254,399, где говорится Ключ расшифровки: D, и 688 749, где говорится Зашифрованное сообщение в числовой форме, как показано ниже:

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

Как работает шифрование RSA на практике

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

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

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

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

Таким образом, шифрование RSA может использоваться ранее неизвестными сторонами для безопасной передачи данных между собой. Значительные части каналов связи, которые мы используем в нашей онлайн-жизни, были созданы из этого фонда.

Как более сложные сообщения шифруются с помощью RSA?

В нашем примере мы сильно упростили вещи, чтобы их было легче понять, поэтому мы зашифровали только сообщение «4». Возможность шифрования числа 4 не кажется особенно полезной, так что вы можете удивиться как вы можете зашифровать более сложный набор данных, такой как симметричный ключ (который является наиболее распространенным использованием RSA), или даже сообщение.

Некоторые люди могут быть озадачены тем, как ключ типа «n38cb29fkbjh138g7fqijnf3kaj84f8b9f…» или сообщение типа «купи мне сэндвич» можно зашифровать с помощью алгоритма, такого как RSA, который работает с числами, а не буквами. Реальность такова, что вся информация, которую обрабатывают наши компьютеры, хранится в двоичном формате (1 и 0), и мы используем такие стандарты кодирования, как ASCII или Unicode представлять их так, чтобы люди могли их понять (буквы).

Это означает, что ключи типа «n38cb29fkbjh138g7fqijnf3kaj84f8b9f…» и сообщения типа «купи мне сэндвич» уже существуют в виде чисел, который может быть легко вычислен в алгоритме RSA. Числа, которыми они представлены, намного больше и сложнее для нас, поэтому мы предпочитаем иметь дело с буквенно-цифровыми символами, а не с беспорядочными двоичными числами..

Если бы вы хотели зашифруйте более длинный сеансовый ключ или более сложное сообщение с помощью RSA, для этого потребуется гораздо большее число.

набивка

Когда RSA реализован, он использует то, что называется прокладка, чтобы помочь предотвратить ряд атак. Чтобы объяснить, как это работает, мы начнем с примера. Допустим, вы отправляли закодированное сообщение другу:

Дорогая Карен,

Я надеюсь, что с тобой все в порядке. Мы еще обедаем завтра?

Искренне Ваш,

Допустим, вы закодировали сообщение простым способом: меняя каждую букву на ту, которая следует за ней в алфавите. Это изменит сообщение на:

J ipqf zpv bsf xfmm. Bsf xf tujmm ibwjoh ejoofs upnpsspx?

Zpvst tjodfsfmz,

Если ваши враги перехватили это письмо, есть хитрость, которую они могут использовать, чтобы попытаться взломать код. Они могли посмотрите на формат вашего письма и попытайтесь угадать, что может быть сказано в сообщении. Они знают, что люди обычно начинают свои письма с «Привет», «Привет», «Дорогой» или ряда других соглашений..

Если они попытаются применить «Привет» или «Привет» в качестве первого слова, они увидят, что оно не будет соответствовать количеству символов. Затем они могут попробовать «Дорогой». Это подходит, но это не обязательно что-то значит. Злоумышленники просто попробуют и увидят, куда они их привели. Таким образом, они будут менять буквы «е», «f», «b» и «s» на «d», «e», «a» и «r» соответственно. Это дало бы им:

Уважаемый Ласео,

J ipqe zpv являются xemm. Являются ли xe tujmm iawjoh djooes upnpsspx?

Зпврт тьодеремз,

Это все еще выглядит довольно запутанно, поэтому злоумышленники могут попытаться взглянуть на некоторые другие соглашения, например, как мы заканчиваем наши письма. Люди часто добавляют «От» или «С наилучшими пожеланиями» в конце, но ни один из них не соответствует формату. Вместо этого злоумышленники могут попробовать «Искренне ваш» и заменить другие буквы, чтобы увидеть, где он их получает. Путем замены «z», «p», «v», «t», «j», «o», «d» и «m» на «y», «o», «u», «s», « i »,« n »,« c »и« l »соответственно, они получат:

Уважаемый Лазен,

Я думаю, ты xell. Есть ли у меня дела??

Искренне Ваш,

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

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

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

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

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

Несмотря на это, злоумышленники могут использовать ряд атак для использования математических свойств кода и взлома зашифрованных данных. Из-за этой угрозы, реализации RSA используют схемы заполнения, такие как OAEP, для встраивания дополнительных данных в сообщение. Добавление этого отступа перед шифрованием сообщения делает RSA намного более безопасным.

Подписание сообщений

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

Когда кто-то хочет доказать подлинность своего сообщения, он может вычислить гашиш (функция, которая берет данные произвольного размера и превращает их в значение фиксированной длины) открытого текста, а затем подписывает их своим закрытым ключом. Oни подписать хеш, применяя ту же формулу, которая используется при расшифровке (м = сd мод n). Как только сообщение подписано, они отправляют эту цифровую подпись получателю вместе с сообщением.

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

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

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

RSA безопасность & нападки

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

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

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

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

Несмотря на это, время и ресурсы, необходимые для такого рода атак, делают его недоступным для большинства хакеров и попадают в область национальных государств. Наилучшая длина ключа зависит от вашей индивидуальной модели угроз. Национальный институт стандартов и технологий рекомендует минимальный размер ключа 2048-бит, но 4096-битные ключи также используются в некоторых ситуациях, когда уровень угрозы выше.

Факторинг — это только один из способов, которым RSA может быть нарушена. Ряд других атак может нарушить шифрование с меньшим количеством ресурсов, но они зависят от реализации и других факторов, а не от самого RSA. Некоторые из них включают в себя:

Действительно ли простые числа случайны??

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

Плохая генерация ключей

Ключи RSA должны соответствовать определенным параметрам, чтобы обеспечить их безопасность. Если простые числа п и Q слишком близко друг к другу, ключ может быть легко обнаружен. Аналогично, число d который составляет часть закрытого ключа не может быть слишком маленьким. Низкое значение облегчает решение. Важно, чтобы эти цифры имели достаточную длину, чтобы сохранить ваш ключ в безопасности..

Атаки по побочным каналам

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

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

Большинство реализаций RSA избегают этой атаки, добавляя одноразовое значение во время процесса шифрования, что устраняет эту корреляцию. Этот процесс называется криптографическое ослепление.

Безопасно ли шифрование RSA на будущее??

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

Если вы хотите использовать шифрование RSA, убедитесь, что вы используете ключ не менее 1024 бит. Те, у кого более высокие модели угроз, должны придерживаться ключей длиной 2048 или 4096 бит, если они хотят использовать RSA с уверенностью. Если вы знаете о слабых сторонах RSA и используете его правильно, вы должны чувствовать себя в безопасности при использовании RSA для обмена ключами и других подобных задач, которые требуют шифрования с открытым ключом.