Some mathematical concepts

Before we can understand the RSA algorithm, we must understand some related mathematical concepts.

Primes and interprimes

A Prime number is a natural number greater than 1 that is not divisible by any other natural number except 1 and the number itself. Any natural number greater than 1 that is not prime is called composite.

Two or more integers are said to be prime (also known as prime) if their greatest common divisor is 1. Two integers a and b are mutually prime, denoted as a perpendicular b.

Two mutually essential numbers have the following properties

The integers A and b are mutually prime if and only if there are integers x,y such that xa+yb=1.

In other words, if a and B are mutually prime, then xa+yb=1 must have a solution. If xa+yb=1 has a solution, then A and B must be mutually prime; If xa+yb=1 has no solution, then A and B must not be mutually prime.

This property involves the extended Euclidean algorithm, which we’ll talk about later.

The main discriminant methods of mutual quality are:

  • Two different primes must be mutually prime. For example, 2 and 7, 13 and 19.
  • If the larger number is prime, the two numbers are mutually prime. Such as 33 and 51
  • One prime number, the other is not a multiple of it, and the two numbers are mutually essential. For example, 3 and 10, 5 and 26.
  • Two adjacent natural numbers are mutually essential. That is, if p is an integer greater than 1, then p is interchangeable with p-1 and p+1. 15 is interchangeable with 16 and 14
  • Two adjacent odd numbers are mutually prime. For example, 19 is interchangeable with 21 and 17
Extended Euclidean algorithm

The extended Euclidean algorithm can be used for the calculation of modular inverse elements, as we will say later, and for proving some properties.

Euclidean algorithm

Euclidean algorithm, also known as toss and turn division, is an algorithm to find the greatest common divisor.

Assuming that

a = q*b + r
Copy the code

Where a, b, q and r are all integers, and GCD is a common divisor function, then

gcd(a,b) = gcd(b,r)
Copy the code

namely

gcd(a,b) = gcd(b,a%b)
Copy the code

In this way, we can solve for the greatest common divisor of A and B in log n time. Achieved by Swift as:

func gcd(a:Int,b:Int)->Int{
    return b == 0 ? a : gcd(a:b, b:a%b)
}
Copy the code
Extended Euclidean algorithm

The basic process of extended Euclidean algorithm is as follows:

For non-negative integers a, b, GCD (a, b) that are not completely 0 represent the greatest common divisor of a, b, there must be integer pairs x, y, such that

A *x + b*y = GCD (a, b)Copy the code

If x0 and y0 are the solutions of the above binary first indeterminate equation, the general solution of the equation is:

X = x0 + (b/ GCD)*t y = y0 - (a/ GCD)*tCopy the code
Extended Euclid algorithm calculation process

If given any integer a and b, find the unknowns x and y, such that:

A *x + b*y = GCD (a, b)Copy the code

Achieved by Swift as:

static func gcdEx(a:Int,b:Int,x:inout Int,y:inout Int)->Int{
    ifB == 0 {// Recurse until b == 0 x = 1 y = 0return a
    }else{
        let r = gcdEx(a:b, b:a % b, x: &x, y: &y)
        let t = x
        x = y
        y = t - a/b * y
        return r
    }
}
Copy the code

The calculation process is roughly as follows:

  • Every time I takea=b.b=a%b, perform the same Euclidean extension algorithm, and then press the stack. We don’t know x and y, so we’re still starting with x and y
  • When you have a special caseb=0Because the common divisor of 0 and any number is the number itself. That is, whenb=0A times 1 plus 0 times 0 is equal to a, which means x is equal to 1 and y is equal to 0.
  • getx=1,y=0After that, the stack goes out in turn. If the solution at the top of the stack is x1 and y1, and the solution at the bottom of the stack (the previous solution) is x0 and y0, then the relationship between the two sets of solutions is as follows:
x0  = y1
y0  = x1 - (a0/b0) * y1
Copy the code
  • Finally, the original solution of A and B is obtained: x and y

The relationship between and two sets of solutions can be simply proved as follows:

For the integers A0 and b0, x0 and y0 exist such that:

A0 * x0 + b0 * y0 = GCD (a0,b0)Copy the code

We make

A1 = b0 (equation two) b1 = a0%b0 (equation three)Copy the code

For integers A1 and b1, there exists x1 and y1 such that:

A1 * x1 + b1 * y1 = GCD (a1,b1)Copy the code

In computers, there are

A0 % b0 = a0 - (a0/b0) * B0Copy the code

The Euclidean algorithm has:

GCD (a0,b0) = GCD (b0,a0%b0)Copy the code

By combining the above six equations:

x0  = y1
y0  = x1 - (a0/b0) * y1
Copy the code
The euler function
Definition of Euler function

Euler’ totient function: denoted by φ(n), is the number of positive integers less than or equal to n that are mutually prime with n.

For example, if the number less than 8 is compatible with 8, there are 1, 3, 5, 7, altogether 4, then φ(8)=4.

Some theorems on Euler functions

  • When n is 1, φ(1)=1.

  • When n is prime, φ(n)=n-1. Because if the larger of the two numbers is prime, the two numbers are mutually prime. So the prime number n is interprime with all numbers less than itself. And there are n minus 1 positive integers less than n

  • If the integers m and n are mutually prime, then φ(m*n)=φ(m)*φ(n); In other words, the Euler function is an integral function

  • If n is odd, φ(2n)=φ(n)

  • If n is a prime number p k power, is from (n) = (p = p ^ ^ k) k – p ^ (k – 1) = p (p – 1) ^ (k – 1), because in addition to multiples of p, other number with relatively prime to n.

Euler function calculation

Express n as a product of several prime numbers

n = p1^k1 * p2^k2 * p3^k3 ... * pn^kn
Copy the code

Where P1, P2, P3… Pn is all prime numbers

Then the general formula of Euler function is:

φ(n)=n * (1-1/p1) * (1-1/p2) * (1-1/p3)... * (1-1/pn)Copy the code

From the above equation, we can realize a method to find euler function:

static func euler(n:Int)->Int{
    var n  = n
    var i  = 2
    var result  = Double(n)
    while i*i <=  n {
        ifResult = result * (1.0-1.0 / Double(I))whileN % I == 0 {// all I factors n /= I}print("i=\(i) n=\(n) reuslt=\(result)"Result = result * (1-1 / Double(n))return Int(result)
}
Copy the code

The time complexity of this function is O(SQRT (n))

Note that:

  • The key to computing Euler’s function is to find all the prime factors of n, which is to factor n
  • Because of any composite number, there is at most one qualitative factor greater than SQRT (n). We’ve dealt with the last prime factor at the end of the function. So we just iterate to SQRT (n).
Die inverse element
Modular arithmetic

Modular operation, also known as modular, modular division, it is expressed by mod, that is, the remainder operation. Usually represented in programs as the % operator. Such as:

17 mod 5 = 17 % 5 = 2
Copy the code
The unit element

The definition of a unit element is that any binary operation performed on an element and the unit element equals the original element.

For example, if the unit element of addition is 0, any number n added with 0 will still give you n

According to this, we know that the identity element of multiplication is 1, and the identity element of matrix multiplication is the identity square matrix

The element

If one element x performs some operation f with another element y, and the result is the identity element of the operation f, then y is the inverse element of x in this case.

For example, the negative element of 3 is -3, because 3+ (-3) = 0

The inverse multiplicative of 3 is 1/3, because 3 times 1/3 is 1

Die inverse element

Modular antielements are also called modular inversions.

In terms of the antielement we said above, it should be an antielement under modular operations. The unit element of modular operation is 1, that is, any number n has n%1=n. Then if the modulo inverse element of the integer A is b, then:

A % b = 1 <=> A ≡ 1 (mod B)Copy the code

In fact, the modular inverse element has multiplication after the modular operation, which describes the relationship between the three numbers.

Or, you could say, multiplicative inverse elements under modular operations

If the modulo inverse element of an integer A with respect to the modulo (congruent)n is b, then

a * b = 1 (mod n)
Copy the code

In other words, if the product of a and b, modulo n has a remainder of 1, i.e

(a * b) % n = 1
Copy the code

Then, b is the modulo antielement of the integer A with respect to the congruence n.

For example, with congruence n=5, the modulo inverse element of the integer a=3 is b=2, because (3*2)%5=1

There must be a coefficient k, so that:

a * b - k*n + 1 
Copy the code

This is equivalent to a binary first order equation:

a * x +  n * y = 1
Copy the code
Properties of modular antielements

The necessary and sufficient condition for the existence of the modular inverse of the integer A to the modular n is that a and N are mutually prime

That is, if a and n are mutually prime, then the modulo antielements of the integer A with modulo n must exist. Conversely, if the greatest common divisor of A and n is not 1, then the modular inverse element must not exist.

Just to prove it:

If the modulo inverse of a with respect to the modulo n is x, according to the binary first order equation we derived in the last video, 1, 2, 2, 3, 3, 3

A times x plus n times y is equal to 1.Copy the code

According to Euclidean extended algorithm:

A * x + n * y = GCD (a,n)Copy the code

If a and n are mutually prime, then GCD (a,n)=1, then the binary first-order equation we have arrived at before must have a solution, and the modular antielement D exists.

If the GCD (a, n)! Equals 1, equation 1 and equation 2 are contradictory, there is no solution to the equation.

Calculation of modular inverse elements

According to the above toppling, we can get a binary first order equation:

a * d + (-k) * n = 1
Copy the code

For this bivariate equation, we can use the extended Euclidean algorithm.

func gcdEx(a:Int,b:Int,x:inout Int,y:inout Int)->Int{
    if b == 0 {
        x = 1
        y = 0
        return a
    }else{// r = GCD(a,b) = GCD(b,a%b) // a%b == 0let r = gcdEx(a:b, b:a % b, x: &x, y: &y)
        let t = x
        x = y
        y = t - a/b * y
        return r
    }
}
Copy the code

Then, find the solution of integer A to modular inverse element D of modular n, that is, a*d + (-k)*n = 1

static func modularInverse(a:Int,n:Int,d:inout Int,k:inout Int){
    var x : Int = 0
    var y : Int = 0
    _  = gcdEx(a: Int(a), b:Int(n), x: &x, y: &y)
    d  = x
    k  = -y
}
Copy the code

It’s important to note that the modulo inverse element d can be negative, whereas we expect it to be in the integer range. In other words, we expect both d and k to be greater than 0. The x = d = > 0, y = – k < = 0

However, there is more than one solution to the binary one-dimensional indefinite equation. According to the general solution:

X = x0 + (b/ GCD)*t y = y0 - (a/ GCD)*tCopy the code

Find the smallest set of solutions that satisfy our expectation, then find the modulo antielement of A with respect to the congruence n

static func modularInverse(a:UInt,n:UInt)->UInt{
    var x : Int = 0
    var y : Int = 0
    _ = gcdEx(a: Int(a), b:Int(n), x: &x, y: &y)
    if x < 0  || y > 0{
        let t0 = ceil((0 - Float(x)) / Float(n))
        let t1 = ceil((0 - Float(y)) / Float(a))
        let t  = Int(max(t0, t1))
        x = x + Int(n) * t
        y = y - Int(a) * t
    }
    let d  = UInt(x)
    let k  = UInt(-y)
    print("modular inverse a=\(a) n=\(n) d=\(d) k=\(k)")
    return d
}
Copy the code
Euler’s theorem

Euler’s theorem, also known as Ferma-Euler’s theorem, is a property of congruence.

Euler’s theorem shows that if n and a are positive integers and n and A are mutually prime, then:

A ^ φ(n) = 1 (mod n)Copy the code

That is:

A ^ φ(n) % n = 1Copy the code

That means that a to the φ of n, modulo n, has a remainder of 1.

According to Euler’s theorem:

A * a ^ (φ(n) -1) = 1Copy the code

That is, if the integers A and n are mutually prime, then there must be a modulo antielement D of A with respect to the modulo n

D = a ^ (φ(n) -1)Copy the code
Fermat’s Little theorem

Fermat’s little theorem is a special case of Euler’s theorem. That is, when the modulus n is prime, then:

φ(n) = n-1Copy the code

the

a ^ (n-1) = 1 (mod n)
Copy the code

Key generation

  • 1. Randomly select two unequal large prime numbersp,q. Suppose we take
P = 61, q = 53Copy the code
  • 2, calculatepandqThe product of then;nThe binary length of theThe key length, generally 1024 bits, 2048 bits for important occasions
n = p * q = 61 * 53 = 3233
Copy the code
  • Compute the Euler function of nPhi (n).

The Euler function φ(n) is the number of positive integers less than or equal to n that are mutually essential to n.

The Euler function of a number is equal to the product of the Euler functions of its factors, i.e

φ(n) = φ(p*q) = φ(p) * φ(q)
Copy the code

Because a prime number has a reciprocal relationship with every number less than it. so

φ(p) = p-1 φ(q) = Q-1Copy the code

Is:

From (n) = (p * q) = phi phi (p) * (q) = (1) p (q 1) = 60 * 52 = 3120Copy the code

  • 4, select a random integer e, the condition is 1< e < φ(n), and e and φ(n) mutually prime. So let’s say we pick 17, e is equal to 17. (In practice, 65537 is often selected.)

  • 5. Calculate the inverse element d of e to φ(n).

Ed ≡ 1 (mod φ(n))Copy the code

namely

17 * D ≡ 1 (mod 3120) <=> 17 * D-K * 3120 = 1Copy the code

It is solved by “extended Euclidean algorithm” and calculated by our above function modularInverse(a:n:), and finally d=2753 and k=15 are obtained

  • 6,(e,n)Encapsulated as a public key,(d,n)Encapsulate a private key, that is, a public key(17, 3233)The private key,(3) 2753323

The encryption algorithm

The public key (e,n) is used to encrypt plaintext M to obtain ciphertext C

C = M^e mod n
Copy the code

If M=65 and the public key obtained before is (17,3233), then:

C = 65^17 % 3233  = 2790
Copy the code

Note that:

  • 1. Plaintext M must be an integer. While M is usually a string, we need to convert it to the corresponding ASCII value or Unicode value, that is, toDataType to perform operations.
  • 2. M must be less than n. If M is greater than n, we have to do it in chunks. That is, if n is 1024 bits, and M is larger than 1024 bits, you need to cut it into blocks smaller than 1024 bits. And we’ll talk about that laterPaddingI have to subtract from each blockPaddingThe size of the.

Decryption algorithm

Decrypt ciphertext C with the private key to obtain plaintext M

M = C^d mod n
Copy the code

That is:

M = 2790 ^ 2753 % 3233 = 65
Copy the code

Signature algorithm

The private key (D,n) is used to sign the information M, and the signature S is obtained

S = M^d mod n
Copy the code

It is equivalent to encrypting information with a private key

Validation signature algorithm

Verify the algorithm, first use the public key (e,n) to perform the following operations on signature S to obtain M’

M' = S^d mod n
Copy the code

It is equivalent to decrypting the signature with a public key

Then compare M and M prime. If they are equal, the verification succeeds

A simple proof of the algorithm

So, how do you guarantee that the number decrypted with the private key is the original plaintext?

According to the encryption rules

C ≡ M^e mod n (Equation one)Copy the code

That is:

M^e % n = C
Copy the code

It can be written as:

M^e - kn is equal to C.Copy the code

Substitute the above formula into the decryption algorithm:

M ≡ C^d mod n (Equation three)Copy the code

There are

M ≡ (M1^ e-kn)^d mod nCopy the code

Is:

M^(ed) -k^dn^d - k2*n = M
Copy the code

Reduction to

M^(ed) - (k^dn^(d-1) - k2)*n = M
Copy the code

The equivalent of

M^(ed) - k3*n = M   
Copy the code

That is to say:

M^(Ed) ≡ M (mod n) (Equation 4)Copy the code

When the key is generated:

Ed ≡ 1 (mod φ(n)) (Equation 5)Copy the code

the

Ed = hφ(n) + 1Copy the code

Substitute the above equation into equation 4

M^(hφ(n) + 1) = M (mod n)Copy the code

Reduction to

M^hφ(n) = 1 (mod n)Copy the code

Now, I’m going to prove this in two cases.

###### (1) M and N are interchangeable.

Since m and N are mutually prime, according to Euler’s theorem:

M^φ(n) ≡ 1 (mod n) (Equation nine)Copy the code

Simultaneous equation eight and equation nine have

= phi phi h (n) (n)Copy the code

When h is equal to 1, this is true, this is proved.

###### (2) M and N are not reciprocal relations.

Since M and n are not mutually prime, M and n must be greater than one common divisor. N is the product of a prime number p and q, so n has only p and q. Then one of p and q of M and n must be a common divisor of M and n. So either M equals KP or M equals kq must be true.

If M is a multiple of p and q, M=ln>=n is mutually exclusive with the plaintext requirement M

If M is a multiple of P, and q is covalent, then it has

M is KP.Copy the code

Because M and Q are mutually prime, according to Euler’s theorem

M^(φ(q) = 1 (mod q)Copy the code

Is:

M^(φ(q) = 1 + l*q 
Copy the code

If YOU take both sides to the h power, you get

(M^(φ(q))^h = (1 + l*q)^hCopy the code

Because when I split it up, the only one that doesn’t have n is 1, so

(1 + l*q)^h % q = 1
Copy the code

namely

(1 + l*q)^h = 1 (mod q)Copy the code

Simultaneous equations twelve and thirteen, there are

(M^(φ(q))^h = 1 (mod q)Copy the code

Let h=j(p-1), and substitute M= KP and (φ(q)=q-1 into (equation 14), get

(KP)^(q-1))^(j(p-1)) ≡ 1 mod q (Equation 15)Copy the code

Substitute φ(n)=(p-1)(q-1) into the equation above, then

KP ^jφ(n) ≡ 1 mod q => KP ^(jφ(n) + 1) ≡ KP (mod q)Copy the code

If jφ(n) + 1 = Ed, substitute in the equation above, get

kp^ed = kp (mod q)
Copy the code

the

KP to the Ed is equal to Tq plus KP.Copy the code

If I take the magnitude of p on both sides,

kp^ed % p  = tq % p + kp % p
Copy the code

Have to

tq % p = 0
Copy the code

Since p and Q are mutually prime, t must be a multiple of P, i.e

t = rq
Copy the code

Substitute in equation 16

kp^ed   = rpq + kp
Copy the code

Because M= KP, n=pq, so:

M^ Ed = Rn + M => M^ Ed ≡ M (mod n)Copy the code

During key generation

Ed ≡ 1(modφ(n)) => Ed =hφ(n)+1Copy the code

the

M^(hφ(n)+1) ≡ M (mod n) 
Copy the code

the

M^hφ(n)  ≡  1 (mod n)
Copy the code

Finally, equation eight is proved, and the original formula is proved.

Algorithm security

As a public key, (n,e) can be publicly transmitted over the network. The most important is to ensure the security of the private key (n, D). N exists in both public and private keys, so d is critical.

The security of the algorithm depends on how hard it is to compute D from (n,e). And e, we already know, if we just solve for order n, we’ll get d.

An algorithm for solving φ(n) is presented, which belongs to brute force cracking, and its time complexity is O(SQR (n)). It seems simple and fast, but the complexity increases exponentially with each additional bit of n, and imagine the amount of computing power required when n reaches 1024 bits.

However, prime factorization of maximal numbers is still a world-class problem.

Even with supercomputers, it is difficult to effectively prime factor a composite number multiplied by two prime numbers, so such principles can be used in encryption algorithms.

When all the factors of composite numbers are large, it is difficult to obtain specific factors by brute force, which is the core of RSA system theory.

As of 2000, the maximum number of digits for RSA modular decomposition is 768.

Up to now, decomposition of RSA numbers above 1024 bits is still a costly engineering problem, and large integer decomposition is still considered difficult.

Therefore, for the time being, it is relatively safe to use 1024 bits for common scenarios, while 2048 bits are required for some more confidential scenarios.

As you can see in Apple’s keystring, most RSA integers are already 2018. In most applications, 1024 bits is enough. The higher the number of bits, the higher the performance cost.

The resources

  • Principle of RSA Algorithm (1)
  • Principle of RSA Algorithm (2)
  • Modular inverses in mathematics
  • Die inverse
  • Extended Euclidean algorithm in detail
  • Coprime – Wikipedia
  • A review of large number factorization algorithms RSA algorithm principle — (3) RSA encryption and decryption process and formula demonstration