A brief introduction.

The original public key scheme was proposed by Ron Rivest, Adi Shamir, and Len Adleman at MIT in 1977 and first published in 1978. Since then, RSA scheme has occupied an absolute dominant position, becoming the most widely accepted and implemented general public key encryption method. RSA is a block cipher. For a certain m, its plain text and ciphertext are integers ranging from 0 to N-1.

2. Use

Used to protect electronic communications over an open network environment, without relying on hidden or covert channels, and even for key exchange. Open network environments are vulnerable to various communication security problems, such as man-in-the-middle attacks and spoofing. Communications security generally includes the requirement that communications not be readable in transit (to preserve confidentiality), communications not be modified in transit (to ensure communication integrity), communications must come from an established source (sender authenticity), and recipients must not deny or reject receiving communications. Combine asymmetric Encryption with the Enveloped Public Key Encryption (EPKE) method to allow secure communication in an open network environment. In other words, even a cryptanalyst listening to the entire conversation, including the key exchange, would not be able to interpret the conversation.

The distinguishing technique used in public key cryptography is the use of asymmetric key algorithms, in which one party uses a different key to perform encryption than the other party uses to decrypt it. Each user has a pair of encryption keys — a public encryption key and a private decryption key. For example, a key pair for digital signature (including a private signature key and a public authentication key). Public keys can be widely distributed, while private keys are known only to their owners. They are mathematically related, but it is not feasible to select the parameters in order to compute the private key from the public key.

In contrast, symmetric key algorithms use a secret key that must be shared and kept private by both the sender (for encryption) and the receiver (for decryption). To use a symmetric encryption scheme, the sender and receiver must securely share the key beforehand.

Because symmetric key algorithms are almost always much less computationally intensive than asymmetric key algorithms, a key exchange algorithm is usually used to exchange keys, and data is then transmitted using that key and the symmetric key algorithm. The PGP and SSL/TLS scheme families use this process, hence the name hybrid cryptosystems. In summary, the asymmetric algorithm is applicable to

  • Key exchange
  • A digital signature
  • Mixing with symmetric encryption algorithms (PGP, SSL, TLS)

Principle of three.

For a certain plaintext block M and ciphertext block C, encryption and decryption have the following forms:



Both sender and receiver must know the values of n and e, and only the receiver knows the value of D. RSA Public Key Indicates the public key KU=< E, N > and private key KR=< D, n> of the cryptography algorithm. In order for the algorithm to be able to be used for public key encryption, it must meet the following requirements:

  • The values e, d, and n can be found such that Medmod n = M is true for all values.
  • For all values that satisfy M < n, it is relatively easy to compute Me and Cd.
  • You can’t derive d from e and n

The first two requirements are easily met. The third requirement can also be satisfied when e and n are large values. Figure 1 below summarizes the RSA algorithm.

  1. Start by selecting two prime numbers P and q and compute their product n as the modulus for encryption and decryption.
  2. Then we need to compute the euler function of n φ(n). φ(n) denotes the number of positive integers less than n and mutually prime with n.
  3. Then select the integer e that is interprime with φ(n), that is, the greatest common divisor of e and φ(n) is 1.
  4. Finally, the multiplicative inverse d of e with respect to the module φ(n) is calculated. D and E have the desired properties.

Suppose user A has published his public key, and user B wants to send A message M. So B computes C = Me(mod n) and sends C. When receiving the ciphertext, user A decrypts it by calculating M = Cd (mod n).

Figure 2 above shows an example. For this example, follow these steps to generate the key:

  • Choose two prime numbers: p=17 and q=11.
  • Calculate n = pq = 17×11 = 187.
  • Calculate φ(n) = (p-L)(q-L) = 16xL0 = 160.
  • Select e such that e and φ(n) =160 and less than φ(n) : select e=7
  • Calculate d such that de mod 160 = 1 and d<160. The correct value is d=23. That’s because 23×7 is equal to 161 is equal to 10×16 plus 1.

This gives the public key PU = <7, 187> and the private key PR = <23, 187>. The following example illustrates the use of the key when plaintext M= 88 is entered.

For encryption, calculate C = 887modL 87. Using the properties of modular operation, the calculation is as follows:






For decryption, calculate M = 1123 mod 187:







Four. Code implementation

At this point, we know that to implement the RSA algorithm, we need to solve the following mathematical problems:

  • How do you produce prime numbers? How do I test prime numbers?
  • How to do modular exponentiation, how to achieve fast modular exponentiation?
  • How to use Euclidean algorithm to find the greatest common factor?
  • How to solve Ax = b (mod m) with The Chinese remainder theorem (extended Euclidean algorithm)?
  • How to construct a congruence equation and find the multiplicative inverse?

1. Prime number selection and prime test

Large numbers are generated in a random way, and primality tests are carried out on this large number in a certain number of rounds.

A prime number, also known as a prime number, is an integer greater than 1 that can only be divisible by 1 and itself (such as 2, 3, 5, etc.). A prime test is a test to see if a given integer is prime. Common testing methods for sterility are:

  • Try to divide
  • Probabilistic test algorithm
    • Fermat’s Little Theorem
    • Fermat Primality Test
    • Miller-rabin Primality Test

I will not expand here, interested friends can have a look at my blog. Below PrimalityTester. IsProbablePrime use is miller – rabin primality testing.

/** * randomly generates a number that may be prime *@paramRange Random number generation range *@returnA number that could be prime */
public static long probablePrime(int range, int rounds) {
    if (range > 0 && rounds > 0) {
        ThreadLocalRandom random = ThreadLocalRandom.current();
        while (true) {
            int num = random.nextInt(range) + 2;
            // Run the rounds test
            if (PrimalityTester.isProbablePrime(num, rounds))
                returnnum; }}return  -1;
}
Copy the code

2. Implement the modular inverse algorithm

Euclid algorithm: the use of toss and turn division to find the greatest common divisor.

public static long gcd(long m, long n) {
    while(true) {if ((m = m % n) == 0)
            return n;
        if ((n = n % m) == 0)
            returnm; }}Copy the code

Ax + by = GCD (a,b) is solved using an extended Euclidean algorithm that implements non-recursion.

private static long extendedEuclid(long a, long b) {
    long x = 0, y = 1, lastX = 1, lastY = 0, temp;

    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }

    while(b ! =0) {
        long q = a / b, r = a % b;
        a = b;
        b = r;

        temp = x;
        x = lastX - q * x;
        lastX = temp;

        temp = y;
        y = lastY - q * y;
        lastY = temp;
    }
    return lastY;
}
Copy the code

Solve the multiplicative inverse by solving the linear congruence equation Ax ≡ b(mod m) :

public static long linearCongruence(long a, long b, long m) {
    if(b % gcd(a, m) ! =0)
        return - 1;
    /* By extending the Euclidean algorithm to find the inverse element of x x' x = kx', b = k(a, m) so x = (b/GCD (a, m)) * x' */
    long result = (b / gcd(a, m)) * extendedEuclid(a, m);
    if(result < 0)
        result += m;
    return result;
}
Copy the code

3. Fast modular finger operation

The recursive and non-recursive algorithms of modular finger operation are realized. Because it is a theoretical experiment, the experimental data can be controlled within the range of no overflow, so the non-recursive method can be used. ModExpNonRec () implements a fast algorithm, the repeated square multiplication algorithm.

The recursive and non-recursive algorithms of modular finger operation are realized. Because it is a theoretical experiment, the experimental data can be controlled within the range of no overflow, so the non-recursive method can be used. ModExpNonRec () implements a fast algorithm, the repeated square multiplication algorithm.

public static int exp(int x, int b, int n) {
    if (b == 1) {
        return x % n;
    }
    if ((b & 1) 
L
/** Function to calculate (a ^ b) % c **/
public static long modExpNonRec(long a, long b, long c) {
    long res = 1;
    for (int i = 0; i < b; i++) {
        res *= a;
        res %= c;
    }
    return res % c;
}
Copy the code

4. Implement THE RSA algorithm by programming

Based on the above basic functions, RSA encryption and decryption algorithm can be written and encapsulated. In encryption, because converting val to char causes overflow problems when val exceeds 2 << 16, the modular inverse result value is split into two character representations and restored at decryption time.

package org.jordon.security.core.crypto.assymmetry;

import org.jordon.security.util.MathUtil;

import java.util.Base64;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/** * Implementation of native RSA encryption and decryption algorithm *@author Jrodon
 * @since2018/10 * /
public class RawRSACipherService {
    // Key attribute group
    private long n, d, e;
    // The selection range of prime numbers
    private static final int RANGE = 2 << 10;
    // It is encrypted
    private static final int SPLIT_POINT = 2 << 8;
    // The number of test rounds
    private static final int PRIMALITY_TESTING_ROUNDS = 4;
    // Base64 encoding tool
    private static final Base64.Encoder encoder = Base64.getEncoder();
    private static final Base64.Decoder decoder = Base64.getDecoder();

    public RawRSACipherService(a) {
        Random random = ThreadLocalRandom.current();
        // Select two large prime numbers at random
        long p = MathUtil.probablePrime(RANGE, PRIMALITY_TESTING_ROUNDS), q;
        do {
            q = MathUtil.probablePrime(RANGE, PRIMALITY_TESTING_ROUNDS);
        } while (p == q);

        this.n = p * q;
        long eulerVal = (p - 1) * (q - 1);

        // Randomly select a positive integer e, 1
        do {
            e = Math.abs(random.nextLong()) % eulerVal + 1;
        }while(MathUtil.gcd(e, eulerVal) ! =1);

        D = 1 (mod φ(n)) d = 1 (mod φ(n)
        d = (MathUtil.linearCongruence(e, 1, eulerVal)) % eulerVal;
    }

    /** * the encryption function that converts val to char when val exceeds 2 << 16 will overflow@paramPlaintext expressly *@returnCipher * /
    public String encrypt(String plaintext) {
        int[] plaintextBytes = changeToInts(plaintext.toCharArray());
        StringBuilder builder = new StringBuilder();
        for (int plaintextByte : plaintextBytes) {
            int modExpResult = (int) MathUtil.modExpNonRec(plaintextByte, e, n);
            builder.append((char) (modExpResult / SPLIT_POINT)).
                    append((char) (modExpResult % SPLIT_POINT));
        }
        return encoder.encodeToString(builder.toString().getBytes());
    }

    /** * decrypt function *@paramCipher ciphertext *@returnClear * /
    public String decrypt(String cipher) {
        // Get an array of decoded strings
        char[] cipherChars = new String(decoder.decode(cipher)).toCharArray();

        // Combine two adjacent characters with an integer to get the original array of encrypted results
        int[] cipherInts = new int[cipherChars.length / 2];
        for(int i = 0; i < cipherInts.length; i++)
            cipherInts[i] = (int)cipherChars[i * 2] * SPLIT_POINT
                                    + (int)cipherChars[i * 2 + 1];
        / / decryption
        int[] plaintextInts = new int[cipherInts.length];
        for(int i = 0; i < cipherInts.length; i++)
            plaintextInts[i] = (int)MathUtil.modExpNonRec(cipherInts[i], d, n);

        StringBuilder plainText = new StringBuilder();
        for (int plaintextInt : plaintextInts)
            plainText.append((char) plaintextInt);
        return plainText.toString();
    }

    /** * For Java character encoding issues and extensibility, convert character arrays to int arrays instead of bytes@paramChars character array *@returnInt * / an array
    private int[] changeToInts(char[] chars) {
        if(chars ! =null && chars.length > 0) {
            int[] result = new int[chars.length];
            for (int i = 0; i < chars.length; i++) {
                result[i] = chars[i];
            }
            return result;
        }
        return null; }}Copy the code

5. Use RSA to encrypt and decrypt data

JUnit was used to write test code, and n rounds of tests were carried out by randomly generating printable plaintext samples for easy viewing. For easy viewing, set the prime selection range to 100 and the plaintext length to less than 20.

package org.jordon.security.core.crypto.assymmetry;

import org.jordon.security.util.ArrayUtil;
import org.junit.Test;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

public class RawRSACipherServiceTest {
    private Random random = ThreadLocalRandom.current();

    @Test
    public void test(a) {
        RawRSACipherService service = new RawRSACipherService();
        for (int i = 0; i < 4; i++) { // Run 30 tests
            String example = genPlaintext();
            ArrayUtil.printInfo("example", example, false);
            String cipher = service.encrypt(example);
            ArrayUtil.printInfo("cipher", cipher, false);
            String plaintext = service.decrypt(cipher);
            ArrayUtil.printInfo("plaintext", plaintext, true); }}// Randomly generate plaintext samples
    private String genPlaintext(a) {
        // Randomly generate a string of [1, 50] printable characters
        int count = random.nextInt(20) + 1;
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < count; i++) {
            // Randomly fetches the printable character range
            int val = random.nextInt(126 -33) + 33;
            builder.append((char) val);
        }
        returnbuilder.toString(); }}Copy the code

The test results

example PQ? j+fMFCVcql`Q! W"Ca cipher AMKeAC8ASQDCjAArAMKIAE0AJABDAMKJAFgAfQDCtQAoAC8AIQBXACIAQwAF plaintext PQ? j+fMFCVcql`Q! W"Ca                                       

example                       qX(zN0"X cipher AH0AYwBgAMKFAMKxAAMAIgBj plaintext qX(zN0"X example \QWD6XO*=k? D6 cipher AMKSAC8AVwARAEEAYwAGAF0AGAAdAEkAEQBB plaintext \QWD6XO*=k? D6 example abXluHtY}37j5 cipher AAUAYgBjAMK1AMKXAHsAwpwAWQBxAFUANwDCjABo plaintext abXluHtY}37j5Copy the code

6. Encrypt big data

To encrypt big data, you can change the data type in the above procedure from Long to BigInteger, because BigInteger provides a set of methods specifically designed for RSA

  • Large prime generation: BigINTEger.probablePrime (built-in dual prime check)
  • Modular exponentiation: modPow()
  • ModInverse ()

So it’s easy to write the corresponding RSA algorithm:

package org.jordon.security.core.crypto.assymmetry;

import lombok.Getter;
import java.math.BigInteger;
import java.security.SecureRandom;

@Getter
public class RSACipherService {
    private final static BigInteger one      = new BigInteger("1");
    private final static SecureRandom random = new SecureRandom();

    private BigInteger privateKey;
    private BigInteger publicKey;
    private BigInteger modulus;

    // generate an N-bit (roughly) public and private key
    public RSACipherService(int N) {
        // Select the prime numbers p, q randomly
        BigInteger p = BigInteger.probablePrime(N / 2, random);
        BigInteger q = BigInteger.probablePrime(N / 2, random);
        // Compute euler function values
        BigInteger phi = (p.subtract(one)).multiply(q.subtract(one));

        modulus    = p.multiply(q);
        // In practice, the public key is usually 2^16 + 1
        publicKey  = new BigInteger("65537");
        // module inverse operation
        privateKey = publicKey.modInverse(phi);
    }
	/ / encryption
    public BigInteger encrypt(BigInteger message) {
        return message.modPow(publicKey, modulus);
    }
	/ / decryption
    public BigInteger decrypt(BigInteger encrypted) {
        return encrypted.modPow(privateKey, modulus);
    }

    public String toString(a) {
        String s = "";
        s += "public = " + publicKey  + "\n";
        s += "private = " + privateKey + "\n";
        s += "modulus = " + modulus;
        returns; }}Copy the code

Adding unit tests

package org.jordon.security.core.crypto.assymmetry;

import org.junit.Test;
import java.math.BigInteger;
import java.security.SecureRandom;

public class RSACipherServiceTest {
    private RSACipherService service = new RSACipherService(2 << 10);
    private final static SecureRandom random = new SecureRandom();

    @Test
    public void test(a) {
        int N = 1024;
        RSACipherService key = new RSACipherService(N);
        System.out.println(key);
        // create random message, encrypt and decrypt
        BigInteger message = new BigInteger(N - 1, random);
        BigInteger encrypt = key.encrypt(message);
        BigInteger decrypt = key.decrypt(encrypt);
        System.out.println("message = " + message);
        System.out.println("encrypted = " + encrypt);
        System.out.println("decrypted = "+ decrypt); }}Copy the code

The test results

public = 65537 private = 785259020723203916087379168846409103645053571745255907101671209937594055095471405946278788632250034413613955451587962319 233619419684294477185516608673828332379605742518654748599244341851328571319032151781862367473851070770615230185854638993 45444036005905759639826169641884190715470009961170662302049779058113 modulus = 111123511057904247384303352454411628574852901907645613196843638982726078745879922118460167927517210453802508633681810948 599960519752655050853574023973606618611715320478128088434295076817222464874390543837050033282496413714543565095232472865 740444355218882825770580971590396819382161816782243359703760806220343 message = 648174167953140785896270419757368173979975840287951855218972741812950085927671715895851064158111846093799111847333186596 517065556958480366013597473595218291055990145208456123870124612226278573646122892432892677637846026321084737420720815722 98228631598483984218130386362800051626492833278994468945333676583030 encrypted = 679024824200626582814967484566900895835286325702762159183929042361669773737567872203550165863538765425159487912355567063 910240253377776748733588632842401614497189041624411306785072736736276243422585144895842945192989795573294825632845437516 83385911800817642057923152429340572932972532657573862337149437977501 decrypted = 648174167953140785896270419757368173979975840287951855218972741812950085927671715895851064158111846093799111847333186596 517065556958480366013597473595218291055990145208456123870124612226278573646122892432892677637846026321084737420720815722 98228631598483984218130386362800051626492833278994468945333676583030Copy the code

7. Implement a simple GUI interface

RSA encryption and decryption interface RSAView and big data encryption and decryption interface RSABigIntegerView, code is very long not posted.

8. Analysis and summary

  • The RSA algorithm is based on the mathematical fact that large composite numbers are difficult to factor. as long as n is large enough, the password is hard to break.
  • In the case of determining password parameters, different D is used for decryption and plaintext cannot be restored.
  • In the process of generating large prime numbers, it is necessary to determine a more reliable primality test algorithm and carry out enough rounds of test verification.
  • Secure random number generation algorithms should be considered in random number generation, such as hashing seeds.
  • Modular power operation is the core operation of RSA. More efficient modular power algorithm should be considered in designing RSA implementation to improve the speed of RSA encryption and decryption.

In addition, the code snippet mentioned in this article has been uploaded to Github. Those who are interested can check it out. If it helps you, please click on star or fork to support it.