The principle and simple practice of RSA

RSA encryption is an asymmetric encryption. The principle is:

Two keys A and B can be generated using the algorithm
Information encrypted using A can be decrypted using B
Information encrypted using B can be decrypted using A

In daily use, we publish one as a public key. Use one as a private key and keep it yourself. In this way, anyone can use our public key to encrypt information and send it to us, and we can use our own private key to decrypt it.

As long as the private key is kept well, this communication system is very safe.

Math basics

1. Euler function

The input of the Euler function is a positive integer, and the output is the number of integers that are smaller than this positive integer and are relatively prime to it.

The definition is:

\[\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_m}) \]

$p_1, p_2, \cdots, p_m$express$n$There are $ m $ prime factors, and repeated ones count as one.

For example, 5 is a prime number with only one factor of itself, so$\phi(5) = 5 \times (1 - \frac{1}{5}) = 4$。
Of course you can guess it, because the number that is relatively prime to a prime number is all the natural numbers from 1 to its predecessor, so for any prime number$p$All

\[\phi(p) = p-1 \]

What about composite numbers? for example$6 = 2 \times 3$,so$\phi(6) = 6 \times \frac{1}{2} \times \frac{2}{3} = 2$, that is, 6 has 2 coprime numbers. If we count them, they are 1 and 5.
Look at another one like 12,$12 = 2^2 \times 3$,so$\phi(12) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$. Let’s count the four coprime numbers of 12: 1, 5, 7, and 11.

Regulation$\phi(1)=1$

The proof of the Euler function is relatively simple and can be done by yourself.

2. Euler’s Theorem

When a positive integer$a$and$n$When mutually prime, there is

\[a^{\phi(n)}\equiv 1 (\textbf{mod } n ) \]

in other words,$a^{\phi(n)} - 1$can be$n$Divisible.

For example, 7 and 10 are relatively prime.$7^{\phi(10)} = 7^4 = 2401$, multiples of 10 when subtracting 1;
in turn,$10^{\phi(7)} = 10^6 = 100,0000$, minus 1 is 999999,$999999 \div 7 = 142857$(That’s 1/7 of the cycle section).

3. Modular elements

It can be seen from the above calculation process that if a positive integer$a$and$n$When mutually prime, we must be able to find a positive integer$b$, making

\[ab \equiv 1 (\textbf{mod } n) \]

$b$Just call$a$The inverted element.
The anti-analogue element is definitely there. At least, because$a^{\phi(n)} = a a^{\phi(n) - 1} \equiv 1 (\textbf{mod } n)$So $ b = a^{\phi(n) - 1}$.

Actually,$b$Addition and subtraction$n$are all multiples of$a$The inverted element.
For example, as you saw above, the modular inverse element of 10 to 7 can be 100,000, because 1 million minus 1 is a multiple of 7. Then subtract 14285 times 7 from 100,000, which is 99995 to get 5, multiply 5 by 10 to get 50, and then subtract 1 is also a multiple of 7.

Key generation

The above is all the mathematical basis. These can be used to generate keys.

1. Randomly select two large prime numbers p and q and calculate their product n

For demonstration, here we choose p = 7 and q = 11, giving us n = 77.
In practical applications, n must have more than 600 digits to ensure security.

Because the binary digits of n are required to be greater than 2048, converted to decimal, it is more than 617 digits.

2. Calculate the Euler function of n$\phi(n)$

Although n is large, since p and q are prime numbers, it is simple

\[\phi(n) = (p -1)(q-1) \]

In our example it is 6*10 = 60.

For the convenience of writing later, letters are used$z$Represents the result of the Euler function:$z = \phi(n)$。

3. Choose a number e followed by$\phi(n)$Comparatively prime and calculate the modular inverse element d of e

Looking for a number to follow$z$Reciprocally prime, e can be compared to$\phi(n)$bigger. but$\phi(n)$It is already very large, so generally the maximum value is 65537.

Using public numbers does not reduce system security

It needs to be relatively prime with 60, so we choose e = 13.
By simply applying the above method, you can get$d = e^{\phi({60})-1}$。
This 60 is relatively small.$60=2^2 \times 3 \times 5$, so$\phi(60) = 16$， $d = 13 ^ {15}$Although it is large, it can be calculated.

But in practice,$z$Usually it is so large that even if its Euler function value can be found, the modular inverse element cannot be calculated.

Extended Euclidean Algorithm

Think differently. now that$ed \equiv 1 (\textbf{mod } z)$, that is$ed-kz=1$, k is an integer.
The extended Euclidean algorithm can not only find the greatest common divisor d of two integers a and b, but also find the integers x and y, such that

\[ax+by=d \]

The algorithm implementation is very simple:

fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        (a, 1, 0)
    } else {
        let (gcd, x1, y1) = extended_gcd(b, a % b);
        let x = y1;
        let y = x1 - (a / b) * y1;
        (gcd, x, y)
    }
}

Substituting 13 and 60, we get d=-23. Add a multiple of 60 to it to make it positive, so d=37.

In this way, the public key is [n, e]=[77,13], and the private key is [n, d]=[77,37].

Security of private keys

Can the private key be calculated if the public key is known?

because$ed \equiv 1 (\textbf{mod } z)$, and e is known, so if you want to calculate d, you need to know z
$z = \phi(n) = (p -1)(q-1)$, need to get p and q
$n = p \times q$, n is known, decomposing the prime factors can get p and q

So the guarantee of this logic is that the third step is difficult. And once successfully decomposed, the private key is easy to forget.

Encryption and decryption

encryption process

The encrypted message m needs to be an integer less than n (we can directly interpret any byte stream as an unsigned integer). If the message is too large and is larger than n when interpreted as an integer, then it is encrypted in segments.
In practical applications, we will not directly use RSA to encrypt messages. Instead, we will use RSA to encrypt a symmetric secret key, and then use this secret key to encrypt the message.

The encryption process is the process of calculating the following c:

\[m^{e} \equiv c (\textbf{ mod } n) \]

Assuming the message we want to encrypt is 50, use the calculation above

\[50^{13} \equiv c (\textbf{ mod } 77) \]

We can get c=29, which is the encrypted message.
The algorithm for calculating c can be found in

fn main() {
     let base = 50; // Original message, cannot be greater than 77
     let exponent = 13;
     let modulus = 77;
     let result = modular_exponentiation(base, exponent, modulus);
     println!("{}", result); // Encrypted result
 }

 fn modular_exponentiation(base: i64, exponent: i64, modulus: i64) -> i64 {
     let mut result = 1;
     let mut base = base % modulus;
     let mut exponent = exponent;
     while exponent > 0 {
         if exponent % 2 == 1 {
             result = (result * base) % modulus;
         }
         exponent >>= 1;
         base = (base * base) % modulus;
     }
     result
 }

Decryption process

The decryption process is the same, based on

\[c^{d} \equiv m (\textbf{ mod } n) \]

    let base = 29;
    let exponent = 37;
    let modulus = 77;
    let result = modular_exponentiation(base, exponent, modulus);
    println!("{}", result);

The output result is 50, which is our original message.

Proof of decryption basis

why when$m^{e} \equiv c (\textbf{ mod } n)$sometimes$c^{d} \equiv m (\textbf{ mod } n)$Woolen cloth?

\[\because m^{e} \equiv c (\textbf{ mod } n) \\ \therefore c= m^e-kn \]

Substitute into the target formula:

\[({m^e-kn})^d\equiv m (\textbf{ mod } n) \]

According to the binomial theorem, after the left-hand expansion, except for the first term which is $ m^{ed}$, the remaining terms contain$kn$, must be a multiple of n, so these terms are discarded. Just prove

\[m^{ed} \equiv m (\textbf{ mod } n) \]

That’s it.
By definition,

\[\because ed \equiv 1 (\textbf{ mod } z) \\ \therefore ed = 1+hz \]

Available by substitution

\[m^{1+hz} = m^{h \phi(n) + 1} \equiv m (\textbf{ mod } n) \]

When m and n are relatively prime

\[\because m^{\phi(n)} \equiv 1(\textbf{ mod } n) \\ \therefore m^{\phi(n)} = rn + 1 \\ m^{\phi(n)h} = (rn + 1)^h \overset{\underset{\mathrm{binomial theorem}}{}}{=} tn + 1 \\ \therefore m^{\phi(n)h} \equiv 1(\textbf{ mod } n) \\ \therefore m^{\phi(n)h} m \equiv m(\textbf{ mod } n) \]

Get certified.
2. When m and n are not mutually prime
When they are not relatively prime, m can only be a multiple of p or q.
by$m = kp$

\[\because m^{\phi(q)} \equiv 1(\textbf{ mod } q) \\ \therefore (kp)^{q-1} \equiv 1(\textbf{ mod } q) \\ \therefore (kp)^{q-1} =tq + 1 \\ \therefore (kp)^{(q-1)h(p-1)} =(tq + 1)^{h(p-1)} \]

According to the binomial theorem

\[(kp)^{(q-1)h(p-1)} \equiv 1(\textbf{ mod } q) \\ \therefore (kp)^{(q-1)h(p-1)} kp \equiv kp (\textbf{ mod } q) \\ (kp)^{ed} \equiv kp (\textbf{ mod } q) \\ \therefore (kp)^{ed} = kp + tq \]

For the equation to hold, each term needs to be a multiple of p, so tq is a multiple of p. Since q is not a multiple of p, t is a multiple of p t = vp:

\[(kp)^{ed} = kp + vpq \\ m^{ed} = m + vn \\ \therefore m^{ed} \equiv m (\textbf{ mod } n) \]

Get certified.