RSA (cryptosystem)

Coprime

Coprime In number theory, two integers a and b are said to be relatively prime, mutually prime or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1. Consequently, any prime number that divides one does not divide the other. This is equivalent to their greatest common divisor (gcd) being 1

co-prime:

• Any two prime numbers are co-prime
• a is a prime number, b is not a multiple of a, then a and b are co-prime
• 1 and any natural number are co-prime
• p is an integer greater than 1, then p and p-1 are co-prime
• p is an odd number greater than 1, then p and p-2 are co-prime
• …

congruence relation

Modular arithmetic can be handled mathematically by introducing a congruence relation on the integers that is compatible with the operations on integers: addition, subtraction, and multiplication. For a positive integer m, two numbers a and b are said to be congruent modulo m, if their difference a − b is an integer multiple of m (that is, if there is an integer k such that a − b = km). This congruence relation is typically considered when a and b are integers, and is denoted

compatibility with multiplication：

if ，，then

Proof：

division rules:

and if , and c, m are co-prime，then:

Proof：

Since c, m are co-prime, has a factor of m , then：

Fermat’s little theorem

Fermat’s little theorem

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that is an integer multiple of p, or in symbols:

Simple proof:

we get a arbitrary prime number, such as 7, a given number set { 1,2,3,4,5,6 }, multiply these numbers by a number that is co-prime with 7, such as 3, then we get a number set { 6,12,18,24,30,36 }, for modulo 7, the set is congruence relation with { 6,5,4,3,2,1 }, acturally, these remainders are number set { 1,2,3,4,5,6 },

then we factor these numbers, we get:

and factor the number set { 6,12,18,24,30,36 } also，extraction of common factors 3，we get:

then:

since and 7 are co-prime，from the above compatibility with multiplication, division rules available，then:

use p instead of 7，use a instead of 3，then we get Fermat’s little theorem

Euler’s totient function

Euler’s totient function

In number theory, Euler’s totient function counts the positive integers up to a given integer n that are relatively prime to n

if n is a prime number，then

Euler’s theorem

Euler’s theorem

In number theory, Euler’s theorem (also known as the Fermat–Euler theorem or Euler’s totient theorem) states that if n and a are coprime positive integers, then：

where  is Euler’s totient function.

The theorem is a generalization of Fermat’s little theorem,

when n is a prime number，then we get Fermat’s little theorem:

Modular multiplicative inverse

Modular multiplicative inverse

If two positive integers a and n are co-prime，then there must be a integer b，which is satisfied that ab - 1 can be divisible by n.

Proof: Since Euler’s theorem： then: then:

RSA

rsa

step：

1 - generate two random unequal large prime numbers p and q, whose product number of is the bit of the key Number, usually set the number of bits is 1024, 2048, 3072, 4096, etc.

2 - calculate the product of p and q n

3 - calculate the Euler function of n, and get

4 - randomly select an integer e, with the condition 1 < e < , and e and

In openssl is fixed at 65537 > [point] Fermat number: For e, ‘3, 5, 17, 257 and 65537’ are usually available.Because they are all prime numbers, and only the second bit in the binary are 1, which can speed up the calculation of d. The optional values of e are actually the first 5 numbers of the Fermat number, and the Fermat number is defined as , to are prime numbers, but starting with is not a prime number. For example: , in practice, is usually selected as .

5 - calculate Modular multiplicative inverse d of e to

6 - n and e are encapsulated into a public key, and n and d are encapsulated into a private key.

7 - for the information , the encryption and decryption functions are as follows:

• public key n, e encryption:
• private key n, d decryption:

we need to proof:

Example

1：

2：

3：

4：

5：

6：public key, private key

7：Assuming , substituting the formula:

Reliability

number:

public key: ( n 和 e )

private key: ( n 和 d )

So d can be derived if n and e are known?

1. , only and can be used to calculate ;
2. ，only and can be used to calculate ;
3. ，only factor to calculate and .

solution：If can be factored，then can be calculated，which means that the private key is cracked.

Fundamental theorem of arithmetic：In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors.

Integer factorization

Proof

Proof one of these：

proof：

since:

1. assume and are co-prime: since Euler’s theorem:

   then:

2. assume and are not co-prime: since is equal to the product of prime numbers and ，so must equal to or ( is an integer)，Assume ，since and must be co-prime，since Fermat’s little theorem, we get:

   At this time, must be divisible by , that is, , then:

   since ，，then:

Challenge from quantum computing

The premise of the RSA encryption system to ensure security is that no computer can decompose a very large integer in an acceptable time, even a supercomputer takes several years.。

Based on the quantum computer-based prime factor decomposition algorithm, the Shor algorithm, the most attractive feature of this algorithm is that it can reduce the complexity of the prime factor decomposition problem from exponential difficulty to near polynomial difficulty.

shor

Shor’s algorithm