RSA algorithm and its Mathematical principle proof

RSA algorithm is an asymmetric cryptographic algorithm, the so-called asymmetric, means that the algorithm requires a pair of keys, using one of the encryption, it needs to use the other to decrypt. The algorithm of RSA involves three parameters, n, E1 and e2. Where n is the product of two large prime numbers p and Q, and the number of bits occupied in the binary representation of n is the so-called key length. E1 and e2 are a pair of related values, E1 can be taken arbitrarily, but E1 is required to be coprime with (pmur1) * (QMu1), and then e2 is selected to require (e2*e1) mod ((pmae1) * (QMu1)) = 1. (nmeme1), (nmeme2) is a key pair. Where (nmeme1) is the public key and (nmeme2) is the private key. The algorithm of RSA encryption and decryption is exactly the same. If An is plaintext and B is ciphertext, then: B ≡ A ^ e2 mod nten A = B ^ E1 mod n; E1 and e2 can be used interchangeably, that is, B ≡ A ^ E1 mod n A = B ^ e2 mod n "≡": congruence symbol meaning: two integers a ≡ b, if the remainder obtained by dividing them by the integer m is the same, it is said that a force b is read as a congruence b (congruence m) as a congruence to b module m Or read as 26 ≡ 14 (mod 12) congruence property theorem: 1 reflexivity a ≡ a (mod m) 2 symmetry if a ≡ b (mod m) then b ≡ a (mod m) 3 transitivity if a ≡ b (mod m), b ≡ c (mod m), then a ≡ c (mod m) 4 congruence is added if a ≡ b (mod m), c ≡ d (mod m) Then if a ≡ b (mod m), c ≡ d (mod m), then ac ≡ bd (mod m) 6 is multiplied by a ≡ b (mod m), then a ^ n ≡ b ^ n (mod m) 7 Euler Theorem, let a ≡ m ∈ N, (mod m) = 1, then a ^ (φ (m)) ≡ 1 (mod m) (Note: the number of simple systems of φ (m) norm m φ (m) = m Mel 1, if m is a prime φ (m = Q1 ^ R1 * Q2 ^ R2 *. * Qi ^ ri) = m (1-1/q1) (1-1/q2). (1-1/qi) corollary: Fermat Little Theorem: if p is a prime, then a ^ p ≡ a (mod p) is a ^ (PMu1) ≡ 1 (mod p) (but when p | an is not equivalent) RSA proof process:

If p, Q are dissimilar prime numbers, rm = = 1 mod (pMui 1) (Q Mel 1)

An is any positive integer, b = a ^ m mod pq, c = b ^ r mod pq

Gcd (mless PQ) = 1

C = = a mod pq

In the process of proof, Fermat Little Theorem will be used, which is described as follows:

M is any prime number, n is any integer, then n ^ m = = n mod m

(in other words, if n and m are coprime, then n ^ (m mod 1) = = 1 m)

Because rm = = 1 mod (pmur1) (qmer1), rm = k (pmae1) (qmer1) + 1, where k is an integer

Because in modulo, it's preserve multiplication.

(X = = y mod z and u = = v mod z = > xu = = yv mod z)

So, c = = b ^ r = (a ^ m) ^ r = = a ^ (rm) = a ^ (k (pmur1) (qmur1) + 1) mod pq

1. If an is not a multiple of p or a multiple of Q,

Then a ^ (pmae1) = = 1 mod p (Fermat Little Theorem) = > a ^ (k (pmur1) (qmer1)) = = 1 mod p

A ^ (qmur1) = = 1 mod Q (Fermat Little Theorem) = > a ^ (k (pmur1) (qmer1)) = = 1 mod Q

So p and Q are divisible a ^ (k (pmae1) (qmai 1))-1 = > pq | a ^ (k (pmae 1) (qmai 1))-1

That is, a ^ (k (pmur1) (qmur1)) = = 1 mod pq

= > c = = a ^ (k (pmur1) (qmur1) + 1) = = a mod pq

two。 If an is a multiple of p but not a multiple of Q

Then a ^ (qmer1) = = 1 mod Q (Fermat's small theorem)

= > a ^ (k (pmur1) (qmur1)) = = 1 mod Q

= > c = = a ^ (k (pmur1) (qmur1) + 1) = = a mod q

= > Q | c-a

Because p | a

= > c = = a ^ (k (pmur1) (qmur1) + 1) = 0 mod p

= > p | c-a

So, pq | c-a = > c = = a mod pq

3. If an is a multiple of Q, but not a multiple of p, it is proved as above

4. If an is a multiple of both p and Q,

Then pq | a

= > c = = a ^ (k (pmur1) (qmur1) + 1) = 0 mod pq

= > pq | c-a

= > c = = a mod pq

This theorem states that when an is encoded into b and then decoded into c, a = = c mod n (n = pq).

But when we do encoding and decoding, the limit is 0.