RSA is introduced

RSA is an algorithm proposed by Ron Rivest, Adi Shamir, and Lennard Adleman in 1977.

RSA encryption algorithm is a kind of asymmetric secret algorithm. The difficulty of factorizing huge integers determines the reliability of RSA algorithm.

Generation of public and private keys

  1. Take two large prime numbers: p and q
  2. So n is equal to p times q
  3. Calculation is less than the number of integer n and n co-prime, using euler formula can calculate &western (n) = (p – 1) ∗ (q – 1) \ omicron (n) = (p – 1) * (q 1) &western (n) = (p – 1) ∗ (q – 1)
  4. Random encryption private key e, make 1 < < e &western \ omicron (n) (n) &western (n), and e and &western (n) \ omicron &western (n) (n) co-prime
  5. Use the Euclidean algorithm to calculate and decrypt private key D so that Ed = 1 (mod(ο(n)\omicron(n)ο(n)))
  6. Public key pair {e,n} PK(to be disclosed); Private key pair {d,n} is SK(must not be disclosed)

How to Encrypt RSA

Ciphertext = plaintext e plaintext ^{e} plaintext emod n The ciphertext of RSA is obtained by modulo n of the plaintext to the e power. This encryption process only involves multiplication and division. Public key pair = {e, n}

How to decrypt RSA

Plaintext = ciphertext d ciphertext ^{d} Ciphertext d mod n The principle is that the ciphertext is raised to the d power and then modulo n to obtain the plaintext. Private key pair = {d,n}

A prime number

A prime number is a natural number greater than 1 that is not divisible by any natural number except 1 and the number itself. (1 is not prime.)

func isPrime(prime int) bool {
    flag := true
    for i := 2; i <= int(math.Sqrt(float64(prime))); i++ {
        if prime%i == 0 {
            flag = false
            break}}return flag
}
Copy the code

Greatest common factor

The largest positive integer that divides multiple integers exactly

func gcd(a, b int) int {
    if a == 0 || b == 0 {
        return 0
    }
    // until a == b
    fora ! = b {if a > b {
            a -= b
        } else {
            b -= a
        }
    }
    return a
}
Copy the code

Extended Euclidean algorithm

Pei Shu theorem: given two integers a and b, there must be integers x and y such that Ax + by = GCD (a,b), where GCD (a,b) is the greatest common diator of a and B.

func extGCD( a , b int , x , y * int ) int {
    if b == 0 {
        *x = 1
        *y = 0
        return a
    }
    d := extGCD(b, a%b, x, y)
    *x, *y = *y, *x-a/b*(*y)
    return d
}
Copy the code

congruence

Congruence is an equivalence relation in number theory. When two integers are divided by a positive integer, they are congruent if they have the same remainder.

An 🌰 :

3%4 ≡ 5%4

Fast power congruence module

func powMod(a, n, m int) int {
    // Do not consider less than zero
    if n == 0 {
        return 1
    }
    
    x := powMod(a, n/2, m)
    ans := x * x % m
    if n%2= =1 {
        ans = ans * a % m
    }
    return ans
}
Copy the code

The two numbers are mutually essential

if gcd(a,b ) == 1 {
  fmt.Println("A b interchangeable")}Copy the code

example

For example, set p = 47 and q = 71 to obtain the public and private keys used for RSA encryption

P and q are both larger prime numbers

Calculation process:

  1. Calculate n = p * q = 47 * 71 = 3337;
  2. Calculation is less than the number of n and n co-prime &western (n) = (p – 1) ∗ (q – 1) \ omicron (n) = (p – 1) * (q 1) &western (n) = (p – 1) ∗ (q – 1); At ο(n)=46∗70\omicron(n) =46 * 70ο(n)=46∗70 = 3220;
  3. Choose e = 79 randomly (e needs to be 1 < E < n, and e is intermass with ο(n)\omicron(n)ο(n));
  4. Private key D: 79 * D mod 3220 = 1.

Since e and N are mutually prime, 79 * d – k * 3220 = 1

D was calculated by division of toss and turn;

A. Equation (4) can be expressed as 79 * d – 3220 * k = 1 (where k is a positive integer);

B. If 3220 is modulo 79, the remainder 60 replaces 3220, then 79 * d – 60 *k = 1;

C. Similarly, if 79 is modulo 60, the remainder 19 replaces 79, then 19 * d – 60 *k = 1;

D. Similarly, if 60 is modulo 19, the remainder 3 replaces 60, then 19 * d – 3 * k = 1;

E. Similarly, modulo 19 to 3 to obtain the remainder 1 instead of 19, then 1 * d – 3 * k =1;

When the coefficient of d becomes 1, d minus 3 times k is 1.

If I take k = 0 and plug it into (e), I get d =1;

Substitute d = 1 into (d), and you get k = 6;

Substitute k = 6 into (c), and you get d = 19;

Substitute d = 19 into equation (b), and you get k =25;

Substitute k =25 into (a), and you get d = 1019;

The final d is going to be the final d.

The whole process uses the idea of recursion to do a good job of figuring out the final d

implementation

// @author
// @date 
// @desc Simple implementation of the RSA algorithm
package main

import (
    "fmt"
    "math"
)

type (
    // 64-bit platform 64-bit
    IEEE[triple E]754 IEEE[Triple E]754 IEEE[Triple E]754
    PublicKey struct {
        E int
    }
    
    PrivateKey struct {
        D int
    }
    
    MiniRSA struct {
        PublicKey  PublicKey  `json:"public_key"`
        PrivateKey PrivateKey `json:"-"`
        N          int        `json:"n"`})func main(a) {
    var p, q, e, x, y int = 47.71.79.0.0
    // check whether p q is prime
    if! (isPrime(p) && isPrime(q)) {panic(fmt.Sprintf("isPrime(%d) = %v and isPrime(%d) = %v need isPrime", p, isPrime(p), q, isPrime(q)))
    }
    N := p * q
    setaN := (p - 1) * (q - 1)
    if gcd(e, setaN) > 1 || N < e {
        panic("E has to be interchangeable with setaN and less than N.")
    }
    extGCD(e, setaN, &x, &y)
    // Get the public and private keys
    miniRSA := MiniRSA{PrivateKey: PrivateKey{D: x}, PublicKey: PublicKey{E: e}, N: N}
    
    fmt.Printf("miniRSA %#v\n", miniRSA)
    plainText := 2020
    cipherText := enc(plainText, miniRSA.PublicKey.E, miniRSA.N)
    fmt.Println("Clear.", plainText, \t Ciphertext:", cipherText, "\ t decryption.", dec(cipherText, miniRSA.PrivateKey.D, miniRSA.N))
    
    plainText = 233
    cipherText = enc(plainText, miniRSA.PublicKey.E, miniRSA.N)
    fmt.Println("Clear.", plainText, \t Ciphertext:", cipherText, "\ t decryption.", dec(cipherText, miniRSA.PrivateKey.D, miniRSA.N))
    
}

// Find the greatest common divisor
func gcd(a, b int) int {
    if a == 0 || b == 0 {
        return 0
    }
    // until a == b
    fora ! = b {if a > b {
            a -= b
        } else {
            b -= a
        }
    }
    return a
}

// Extended Euclidean algorithm
func extGCD(a, b int, x, y *int) int {
    if b == 0 {
        *x = 1
        *y = 0
        return a
    }
    d := extGCD(b, a%b, x, y)
    *x, *y = *y, *x-a/b*(*y)
    return d
}

// Determine the prime number
func isPrime(prime int) bool {
    // 1 is not prime
    flag := true
    for i := 2; i <= int(math.Sqrt(float64(prime))); i++ {
        if prime%i == 0 {
            fmt.Println(prime, i)
            flag = false
            break}}return flag
}

// Use public key encryption
func enc(plainText int, e, n int) int {
    return powMod(plainText, e, n)
}

// Use the private key to decrypt
func dec(cipherText int, d, n int) int {
    return powMod(cipherText, d, n)
}

// Fast power problem
func quickPow(a, b int) int {
    // Do not consider less than zero
    if b == 0 {
        return 1
    }
    ans := quickPow(a, b/2)
    ans *= ans
    if b%2= =1 {
        ans *= a
    }
    return ans
    
}

/ / congruence
func powMod(a, n, m int) int {
    // Do not consider less than zero
    if n == 0 {
        return 1
    }
    
    x := powMod(a, n/2, m)
    ans := x * x % m
    if n%2= =1 {
        ans = ans * a % m
    }
    return ans
}

// end 

Copy the code

conclusion

  1. RSA algorithm to find the public key pair and private key pair of the entire process
  2. RSA uses public key encryption
  3. The RSA algorithm uses a private key for decryption
  4. The cotheorems can be used to avoid overflow problems
  5. Fast power ideas are used to speed up the encryption and decryption processes

reference

  1. RSA encryption algorithm
  2. Extended Euclidean algorithm
  3. Greatest common factor
  4. congruence
  5. Fermat’s Little theorem
  6. A prime number

Please like 🦀🦀 github