# Quickly understand the commonly used asymmetric encryption algorithms, and no longer have to worry about the thorough inquiry of the interviewer

Interviewer: what are your commonly used encryption algorithms?

Encryption algorithms are usually divided into two kinds: symmetric encryption algorithm and asymmetric encryption algorithm. The symmetric encryption algorithm uses the same key in encryption and decryption; Asymmetric encryption algorithm uses different keys in encryption and decryption, which are divided into public key and private key. In addition, there is another kind of algorithm called message summarization algorithm, which summarizes data and is irreversible.

This time, let's take a look at the asymmetric encryption algorithm.

### Asymmetric encryption algorithm

Asymmetric encryption algorithm uses two different keys when encrypting and decrypting. One of the public keys is called public key, and the other one is called private key. Only the same public key and private key pair can be encrypted and decrypted normally.

For the same public key and private key pair, if the public key is used to encrypt the data, only the corresponding private key can be used to decrypt; If the private key is used to encrypt the data, only the corresponding public key can be used for decryption.

Common asymmetric encryption algorithms include RSA algorithm and DSA.

### RSA algorithm

RSA algorithm is the most influential public key encryption algorithm at present. It was proposed by Ron Rivest, Adi Shamir and Leonard Adleman when they worked at MIT in 1977. RSA is composed of the initial letters of their surnames. In addition, in 1973, Clifford Cocks, a mathematician working at the British government communications headquarters, proposed an equivalent algorithm in an internal document, but the algorithm was classified and was not disclosed until 1997.

RSA algorithm takes advantage of two number theory characteristics:

1. p1 and p2 are two prime numbers, n=p1 * p2. It is easy to find n when p1 and p2 are known, but it is difficult to find p1 and p2 when n is known.
2. (m^e) mod n=c, it is easy to find c when m, e and N are known, but it is difficult to find m when e, N and c are known.

Public key and private key generation process: randomly select two prime numbers p1 and p2, n=p1 * p2, and then randomly select one and φ (n) Coprime and less than φ (n) For the integer e, and then calculate E φ (n) Finally, we get that N and E are public keys and N and d are private keys.

Encryption process: (m^e) mod n = c, where m is plaintext, c is ciphertext, and N and e are public keys.

Decryption process: (c^d) mod n = m, where m is plaintext, c is ciphertext, and N and d are private keys.

Let's write an example in Java:

```import javax.crypto.Cipher;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.security.GeneralSecurityException;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Base64;

public class RsaUtil {

private static final String RSA = "RSA";
private static final Charset CHARSET = StandardCharsets.UTF_8;

/**
* encryption
*
* @param input     Plaintext
* @param publicKey Public key
* @return ciphertext
* @throws GeneralSecurityException
*/
public static String encrypt(String input, String publicKey) throws GeneralSecurityException {
Cipher cipher = Cipher.getInstance(RSA);
PublicKey pubKey = KeyFactory.getInstance(RSA)
.generatePublic(new X509EncodedKeySpec(Base64.getDecoder().decode(publicKey)));
cipher.init(Cipher.ENCRYPT_MODE, pubKey);
byte[] data = cipher.doFinal(input.getBytes(CHARSET));
return Base64.getEncoder().encodeToString(data);
}

/**
* decrypt
*
* @param input      ciphertext
* @param privateKey Private key
* @return Plaintext
* @throws GeneralSecurityException
*/
public static String decrypt(String input, String privateKey) throws GeneralSecurityException {
Cipher cipher = Cipher.getInstance(RSA);
PrivateKey priKey = KeyFactory.getInstance("RSA")
.generatePrivate(new PKCS8EncodedKeySpec(Base64.getDecoder().decode(privateKey)));
cipher.init(Cipher.DECRYPT_MODE, priKey);
byte[] data = cipher.doFinal(Base64.getDecoder().decode(input));
return new String(data, CHARSET);
}

public static void main(String[] args) throws GeneralSecurityException {
// Generate public / private key pair:
KeyPairGenerator kpGen = KeyPairGenerator.getInstance(RSA);
kpGen.initialize(1024);
KeyPair keyPair = kpGen.generateKeyPair();
String publicKey = Base64.getEncoder().encodeToString(keyPair.getPublic().getEncoded());
String privateKey = Base64.getEncoder().encodeToString(keyPair.getPrivate().getEncoded());
System.out.println("Public key:" + publicKey);
System.out.println("Private key:" + privateKey);

String msg = "I like you. Can you be my girlfriend?";
System.out.println("Before encryption:" + msg);
String pwd = RsaUtil.encrypt(msg, publicKey);
System.out.println("After encryption:" + pwd);
System.out.println("After decryption:" + RsaUtil.decrypt(pwd, privateKey));
}
}```

The operation results are as follows:

```Public key: MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDd4brSm8gdJqFi04m3aW8kjVYbd/T4ymyc7l3c2WmwOhVPlZO1eaZJpTvas61rW0HPf267CRIhc52Zp2+e1hoknApvT0gKeRkfSwC5aws/yoT2vZ9J627QbCFkFc8mmfP8LJ5V/rCpmUE12dIW4xVlEYtWPzmNK2iTMzuR99Jq9wIDAQAB
Before encryption: I like you. Can you be my girlfriend?
After encryption: tRt5hdF0XB8V2wk6BWC2i8UWVQj/jOCRZn3wIfGYqVaYJ9OjC/+VRUI3c5WgpZlKCZd5zrHo3g1LuQ02G934Gcb51cKH4uhWxRY8oxUgs/fibkvc9+w1X7FQarFwAGCs5SddHIL/vYUxHIvQslelyP9l9/EFpgSs0WWSfOfKcUc=
After decryption: I like you. Can you be my girlfriend?```

RSA algorithm solves the disadvantage that the security of symmetric algorithm depends on the same key. However, RSA algorithm is quite complex in calculation, and its performance is not good, which is far inferior to symmetric encryption algorithm. Therefore, in general practice, asymmetric encryption algorithm is often used to randomly create temporary symmetric key, and then symmetric encryption is used to transmit a large number of subject data.

### DSA

DSA (Digital Signature Algorithm) is a variant of Schnorr and ElGamal signature algorithm, which is based on the complexity of modulo arithmetic and discrete logarithm.

The National Institute of standards and Technology (NIST) proposed to use DSA for its DSS (digital signature standard) in 1991 and adopted it as FIPS 186 in 1994.

Unlike RSA algorithm, which uses public key encryption and private key decryption, DSA uses the private key to encrypt the data to generate a digital signature, and then uses the public key to compare the decrypted data with the original data to verify the digital signature.

Digital signatures provide information authentication (the receiver can verify the source of the message), integrity (the receiver can verify that the message has not been modified since signing), and non repudiation (the sender cannot falsely claim that they have not signed the message).

Let's write an example in Java:

```import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.security.GeneralSecurityException;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.Signature;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Base64;

public class DsaUtil {

private static final String DSA = "DSA";
private static final String SHA1withDSA = "SHA1withDSA";
private static final Charset CHARSET = StandardCharsets.UTF_8;

/**
* autograph
*
* @param data       data
* @param privateKey Private key
* @return autograph
* @throws GeneralSecurityException
*/
public static String sign(String data, String privateKey) throws GeneralSecurityException {
PrivateKey priKey = KeyFactory.getInstance(DSA)
.generatePrivate(new PKCS8EncodedKeySpec(Base64.getDecoder().decode(privateKey)));
Signature signature = Signature.getInstance(SHA1withDSA);
signature.initSign(priKey);
signature.update(data.getBytes(CHARSET));
return Base64.getEncoder().encodeToString(signature.sign());
}

/**
* verification
*
* @param data      data
* @param publicKey Public key
* @param sign      autograph
* @return Whether the verification is passed
*/
public static boolean verify(String data, String publicKey, String sign) throws GeneralSecurityException {
try {
PublicKey pubKey = KeyFactory.getInstance(DSA)
.generatePublic(new X509EncodedKeySpec(Base64.getDecoder().decode(publicKey)));
Signature signature = Signature.getInstance(SHA1withDSA);
signature.initVerify(pubKey);
signature.update(data.getBytes(CHARSET));
return signature.verify(Base64.getDecoder().decode(sign));
} catch (Exception e) {
throw new RuntimeException(e);
}
}

public static void main(String[] args) throws GeneralSecurityException {
// Generate public / private key pair:
KeyPairGenerator kpGen = KeyPairGenerator.getInstance(DSA);
kpGen.initialize(1024);
KeyPair keyPair = kpGen.generateKeyPair();
String publicKey = Base64.getEncoder().encodeToString(keyPair.getPublic().getEncoded());
String privateKey = Base64.getEncoder().encodeToString(keyPair.getPrivate().getEncoded());
System.out.println("Public key:" + publicKey);
System.out.println("Private key:" + privateKey);

String msg = "I like you. Can you be my girlfriend?";
System.out.println("Data:" + msg);
String sign = DsaUtil.sign(msg, privateKey);
System.out.println("Signature:" + sign);
System.out.println("Verification passed:" + DsaUtil.verify(msg, publicKey, sign));
}

}```

The operation results are as follows:

```Public key: MIIBtzCCASwGByqGSM44BAEwggEfAoGBAP1/U4EddRIpUt9KnC7s5Of2EbdSPO9EAMMeP4C2USZpRV1AIlH7WT2NWPq/xfW6MPbLm1Vs14E7gB00b/JmYLdrmVClpJ+f6AR7ECLCT7up1/63xhv4O1fnxqimFQ8E+4P208UewwI1VBNaFpEy9nXzrith1yrv8iIDGZ3RSAHHAhUAl2BQjxUjC8yykrmCouuEC/BYHPUCgYEA9+GghdabPd7LvKtcNrhXuXmUr7v6OuqC+VdMCz0HgmdRWVeOutRZT+ZxBxCBgLRJFnEj6EwoFhO3zwkyjMim4TwWeotUfI0o4KOuHiuzpnWRbqN/C/ohNWLx+2J6ASQ7zKTxvqhRkImog9/hWuWfBpKLZl6Ae1UlZAFMO/7PSSoDgYQAAoGABDM1s78NZ4C0Bh9V86Z1lylEyCjCg2oAj6Kxd3/2IXhSlplnSpJPLlomet9yWJpagLQieIWHAIyq6JLmdcVxOxUvnLIsrvWKIPr4lz7pIqO1xi4AYunP48gPECHlMgOKPyik3ZkQQ3iHl9MiaWOaeisqsw/gzTUtE1xi8CVscks=
Data: I like you. Can you be my girlfriend?
Signature: MCwCFHhnd/3yRCIygyD1GPa1K9ZVQ+4rAhR8zAtlrBim9KKEkv+Fxz47opvSuA==
Verification passed: true```

It can be seen from the Java example that the private key of the data will not be encrypted directly, but the data will be summarized through the information summary algorithm, and then the private key of the summary information will be encrypted.

### summary

Asymmetric encryption algorithm uses two different keys in encryption and decryption, which are called public key and private key respectively. Only the same public key and private key pair can encrypt and decrypt normally.

Common asymmetric encryption algorithms include RSA algorithm and DSA. RSA algorithm mainly encrypts the public key of data, and DSA mainly verifies the signature of data.

## After reading three things ❤️ 