Asymmetric encryption

Asymmetric encryption requires two keys, one public and one private; The public key is used for encryption and the private key for decryption.

The ciphertext obtained by encrypting plaintext with a public key can only be decrypted with the corresponding private key and the original plaintext can be obtained. The public key originally used for encryption cannot be used for decryption. Because encryption and decryption require two different keys, it is called asymmetric encryption;

The public key can be disclosed and released freely. The private key cannot be made public, must be held in strict confidence by the user, and must never be provided to anyone by any means, nor disclosed to the trusted party to the communication.

Common public key encryption algorithms include RSA, ElGamal, Rabin (a special case of RSA), DSA, and ECDSA. This article only discusses RSA, which is the most widely used of the records (apple’s previous one).

RSA

RSA Learning this article is very clear about how RSA is written, and there are a few concepts that you need to know before you understand it. The first is the Euler function, which produces a theorem called Fermat’s Little Theorem under certain circumstances, the second is the modular inverse element, and the Diffiermann key exchange.

Mathematical understanding

The final mathematical generation is m^e (mod N) ≡ c, c^d (mod N) ≡ m.

  • M: definitely
  • C: ciphertext after the public key is encrypted
  • N: a very large prime number (N is derived from the product of two large primes p,q, and after calculating φ(N) from p and q, p,q, φ(N) is destroyed, mainly used when e generates d)
  • E: a prime number less than N
  • D: the modulo inverse element of E with respect to N
  • Public key: (N, e)
  • Private key: (N, d), it can be seen from the above N that the private key can generate the public key, which can explain why this algorithm is generally open to the public key while the private key is saved.

The mathematical end result is the two formulas above.

The following mathematical basis is the solution to the formula, how to find N, φ(N), e, d relationship, so as to achieve asymmetric encryption.

The euler function

In number theory, for positive integers n, the Euler function is the number of positive integers less than n that are mutually prime with n (hence φ(1)=1).

This function is named after its first researcher Euler (Euler’s Totient function), it is also called Euler’s Totient function, φ function, Euler quotient and so on.

For example, φ(8)=4, because 1,3,5,7 are all interplasms with 8. φ(7)=6, because 1,2,3,4,5,6 are all co-plasms with 7.

If m and n are mutualmass, then φ(mn)=φ(m)φ(n).

Special properties:

  1. φ(2n)=φ(n) when n is not prime.
  2. If n is prime then φ(n)=(n-1). We mainly use this theoretical calculation of Euler’s function.

The formula is: m^φ(n) mod n ≡ 1

Fermat’s little theorem

Fermat’s little theorem is one of the four theorems of elementary number theory (Wilson’s theorem, Euler’s theorem, Chinese remainder theorem (also known as Sun Zi’s theorem), fermat’s little theorem), which has a very wide and important application in elementary number theory. In fact, it is a special case of Euler’s theorem (i.e., see “Euler functions.”).

A special case of Euler’s theorem: if two positive integers m and n are mutually prime, and n is prime! So phi of n is going to be n minus 1.

M ^φ n mod n ≡ 1 becomes m^(n-1) mod n ≡ 1.

For example, m = 3, n = 5, mn co-prime, m ^ (n – 1) = 3 ^ (5-1) = 3 ^ (4) = 81. | | 81 mod 5 = 1. You can use py to verify some large numbers

Modulo inverse, modulo inverse, or modulo inverse (very important, mainly the relationship between e and d and φ n)

A necessary and sufficient condition for the existence of a modular inverse of integer A to modular N is that a and N are mutually prime. If the modular inverse exists, division under modular N can be achieved by multiplication of the corresponding modular inverse, which is the same as the concept of real division.

It also means that if two positive integers e and n are mutually prime, then you must find an integer d such that Ed -1 is divisible by n. Then d is the modulo inverse element of E with respect to n. Ed mod n ≡ 1

Ed ≡ kn + 1

M to the e times d mod n ≡ m

From the three above

  1. M to the φ n mod n ≡ 1 because 1 to the k is 1, so m to the k φ n mod n ≡ 1
  2. Because you multiply both sides by m you get m to the k φ n plus 1 mod n ≡ m
  3. The modulus inverse is e * d mod n ≡ 1 is e * d ≡ kn + 1, where k is the coefficient and n is any number
  4. So when n in the inverse module is equal to φ(n) from pegasus’ little theorem, this becomes the final formula
  5. M to the e times d mod n ≡ m

So we know n (p, q, the product of phi (n) = (1) p (q – 1)), can be phi (n), phi (n) is the mode of the elements and the e co-prime n. d is relative to the phi e (n) of the element.

Finally, it can be seen that the relation of e, d and n in asymmetric encryption is the mutual prime of e and φ(n), and d is the modular inverse of e with respect to φ(n).

This is equivalent to c = m^e, so we can get the plaintext m from the ciphertext C, the private key (d,N).

Well, c is equal to m to the e, but if I plug in c to the d mod n, that’s the same thing as m to the e times d mod n is equal to m.

The reverse c is equal to m to the d, if you plug in c to the e mod n, it’s the same thing as m to the e times d mod n is equal to m.

So if you only have n,e,d and you know either n,e, or n,d, anybody can be a private key or a public key. Or the public one is called a public key, and the private one is called a private key

The actual operation

Terminal encryption command in the MAC

Mac system built-in OpenSSL(open source encryption library), OpenSSL in the RSA algorithm commonly used instructions are mainly three:

  • Genrsa: Generates and enters an RSA private key
  • Rasutl: Use RSA for various encryption, decryption, authentication, etc
  • Rsa: Deals with key format conversion
Pem 1024 Extract the public key from the private key. Openssl rsa -in priv.pem -pubout pub.pem View the plaintext of the private key Openssl rsa-in priv.pem -text -out priv. TXT Use rsa pub.pem public key to encrypt. TXT openssl rsvautl -encrypt -in MSG. TXT -inkey pub.pem -pub-in enc. TXT Openssl rsvautl -decrypt -in enc.txt -inkey priv.pem -out Dec. TXT uses private key encryption and public key decryption TXT -inkey priv.pem -out privenc. TXT Public key decrypt (-verify verification command) openSSL rsautl -verify -in privEnc.txt -inkey pub.pem -pubin -out privDec.txtCopy the code

Public and private key viewingThe private key is much larger than the public key, which is extracted from the private key. You can view the privtxt.txt file in the command.

RSA code in OC

Certificates used in OC are all suffixed with cer, and the P12 file we distributed is equivalent to the private key.

We use the SecKeyEncrypt and SecKeyDecrypt functions to encrypt and decrypt in the seckey.h file in the system Framework’s Security library. The following article is relatively comprehensive or, when you need to refer to. RSA code

If you’re interested, look at the SecPadding parameter in the method, which has a lot of parameters for the hybrid encryption scheme, which one to search for.

Asymmetric encryption security, efficiency and cracking

Because it is a modular operation with very large primes, RSA is much less efficient than symmetric encryption and digest algorithms. So generally symmetric encryption carries on some key data encryption transmission.

On December 12, 2009, the number rSA-768 (768 bits, 232 digits) was also successfully decomposed. This event threatens the security of the current 1024-bit key, and it is generally believed that users should upgrade to 2048-bit or above as soon as possible.

When looking at the data, I saw a very interesting crack thinking, that is, when the computer is conducting modular operations, the operation time of different bits 1 is always longer than that of 0. If a lot of data and the operation time can be obtained, it is possible to get very close numbers in each bit.

confusion

At first I struggled with whether the RSA private key contained a public key, whether the private key generated a public key or whether they were independent. For verification, (n, e) is plaintext, (n, d is ciphertext, and d is calculated from e and φ(n). On OpenSSL, the public key is extracted from the private key. So it’s always a question of whether the private key contains the public key, or whether the public key generates the private key.

I did some research, and the best explanation is,

1. The private key generated by OpenSSL is a key pair, which contains a public key and a private key. Therefore, you can extract the private key from the public key. In this case, the private key must not be disclosed.

2. In cryptography, the public and private keys are just (n, e), (n, d). After calculating n and φ(n), e,d for two large primes p,q, p,q,φ(n) has been discarded. The only data the key knows is n, E, and d. The only way to solve it is to solve the large prime number n.

In this case, you can use any key as a public key or a private key, as long as you keep the key in your hand private.

Take a look at the OpenSSL documentation, it’s updated in real time, there’s a lot of interesting stuff about OpenSSL

Openssl version -d can get the openSSL installation directory, then open the directory and find the final folder with the share directory and the HTML for the document. The following is the document outline. If you are interested, you can check it out by yourself. Personally, I think I can first look at the commands and keywords of OpenSSL

The OpenSSL command line

OpenSSL version and configuration

Build OpenSSL

Run the OpenSSL command to view

Set up a trust store

Manual switch

Key and certificate management

Key generation

Create a certificate signing request

Create a CSR from an existing certificate

CSR generated | sign your certificate | create effective for more than one hostname of the certificates | | check the public

Key and certificate conversion

PEM and DER conversion

PKCS# 12 (PFX) conversion PKCS# 7 conversion.(p12)

TLS configuration | get support package | encryption level of security

Configure TLS 1.3

Configure OpenSSL default values generated DH parameter | | | recommend suite configuration suite of old configuration

Cipher suite keyword combination keyword | | building cipher suite list | keyword modifiers

Handling errors

Create private certificate issuing authority | characteristics and limitations

Create a root CA | | | root CA CA configuration directory structure root CA root CA | | operation generated root CA structure of the database file

Create a certificate for OCSP signing

Create the lower CA | | affiliate CA configuration CA CA | affiliate generated operating at a lower level

So it is equivalent to the key in the problem of tangle, one is the private key of cryptography, one is the private key of OpenSSL, not the same thing, also very painful…

conclusion

Asymmetric encryption is a combination of symmetric encryption and digest algorithm. There are many kinds of encryption schemes, such as re-signature in iOS and HTTPS. We will continue the discussion.

Welcome to the discussion.