Shulou(Shulou.com)06/01 Report--

In symmetric encryption, encryption and decryption use the same key, so the key must be distributed to the decryptor, that is, the key distribution problem. In asymmetric encryption, the public key and private key are used for encryption and decryption respectively, and the public key is public, so the key distribution problem can be avoided. Asymmetric encryption algorithm, also known as public key encryption algorithm.

In 1977, Ron Rivest, Adi Shamir and Leonard Adleman published a public key encryption algorithm in the United States, that is, RSA public key encryption algorithm. RSA is the most influential and commonly used public key encryption algorithm at present, which can be said to be the de facto standard of public key encryption algorithm.

RSA encryption principle

If M and C are used to represent plaintext and ciphertext respectively, the process of RSA encryption and decryption is as follows:

Where the combination of e and n (e, n) is the public key, and the combination of d and n (d, n) is the private key. Of course, e, d, n are not arbitrary values, need to meet certain conditions, the following is the solution process of e, d, n.

Generate key pair

The solving process of e, d, n, that is, the process of generating key pairs. The following steps are involved:

1. Take two large prime numbers (also known as primes) p and Q _ pq n = prime.

2. Take positive integers e and d such that ed mod (pmur1) (QMUEL) = 1, that is, ed ≡ 1 mod (PMUE 1) (QMel 1).

E and d are multiplicative inverses of module (pmur1) (qmur1). There exists d only if e and (pmae1) (qmer1) are coprime.

Give an example to verify:

1. P and Q are 13 and 17 respectively. N = pq = 221.

2. While (pmur1) (qmur1) = 12x16 = 192, e and d are 13,133 and 13x133 mod 192 = 1, respectively.

Take plaintext M = 60, public key encryption, private key decryption, encryption and decryption process are as follows:

The proving process of RSA encryption principle

Manually solve the d in the key pair

Ed mod (pmur1) (qmai 1) = 1, we know that e and (pmur1) (qmurl) find d, that is to say, we find the multiplicative inverse of e pair module (pmur1) (qmur1).

As in the above example, p, Q are 13, 17, (pMel 1) (Q Mel 1) = 192, take eBay 13 and find the d in 13d mod 192 = 1.

13d ≡ 1 (mod 192), add a multiple of 192 to the right so that the result is divisible by 13.

13d ≡ 1 + 192x9 ≡ 13x133 (mod 192), so d = 133

Other calculation methods are: Fermat's small law, extended Euclid algorithm, Euler theorem.

RSA security

Because the public key is public, that is, e, n are public.

Therefore, to crack the RSA private key is to find d when e and n are known.

Because ed mod (pmur1) (qmurl) = 1 and n=pq, the problem evolves into finding p and Q for n prime factorization.

At present, it has been proved that e and n are equivalent to d and p and Q for n prime factorization. In practice, the length of n is more than 2048 bits, but it is very difficult to decompose n when n > 200bit, so RSA algorithm is still considered to be safe and practical.

RSA timing and Prevention

The essence of RSA decryption is modular exponentiation, that is:

Among them, C is ciphertext, (dMagne n) is the private key, and all are large number operations with more than 1024 bits, so direct calculation is not feasible, so the most classical algorithm is Montgomery algorithm. This kind of calculation is time-consuming, so * * users can observe the decryption time corresponding to different inputs and infer the private key through analysis, which is called timing *. The method to prevent RSA timing is to add random factors during decryption, so that the decryption time cannot be accurately obtained by * * users.

The specific implementation steps are as follows:

Implementation of RSA encryption and decryption in go Standard Library

Decryption in the go standard library implements the defense against timing * *. The code is as follows:

/ / encryption / / m is plaintext / / (pub.E, pub.N) is public key / / c is ciphertext func encrypt (c * big.Int, pub * PublicKey, m * big.Int) * big.Int {e: = big.NewInt (int64 (pub.E)) c.Exp (m, e, pub.N) return c} / / decryption / / incoming random supports defense timing * * func decrypt (random io.Reader, priv * PrivateKey) C * big.Int) (m * big.Int, err error) {if c.Cmp (priv.N) > 0 {err = ErrDecryption return} if priv.N.Sign () = = 0 {return nil, ErrDecryption} var ir * big.Int if random! = nil {var r * big.Int for {/ / step 1 generates a random number rr between 0 and NLMI Multiplicative inverse ir of err = rand.Int (random, priv.N) if err! = nil {return} if r.Cmp (bigZero) = 0 {r = bigOne} var ok bool / / r In step 4, use ir, ok = modInverse (r, priv.N) if ok {break}} bigE: = big.NewInt (int64 (priv.E)) / / calculate C'rpowe: = new (big.Int) .Exp (r, bigE) in step 2 Priv.N) / / N! = 0 cCopy: = new (big.Int) .set (c) cCopy.Mul (cCopy, rpowe) cCopy.Mod (cCopy, priv.N) c = cCopy} if priv.Precomputed.Dp = = nil {/ / step 3 Use C'to calculate the corresponding M'm = new (big.Int) .Exp (c, priv.D, priv.N)} else {/ / slightly} if ir! = nil {/ / step 4 calculate the actual M m.Mul (m, ir) m.Mod (m, priv.N)} return} / / the principle of src/crypto/rsa/rsa.goRSA signature and verification at the code location.

Asymmetric encryption algorithm can not only support encryption, but also realize signature. The principle is as follows:

Signature:

1. Extract the message digest, encrypt the message digest using the sender's private key, and generate the message signature.

2. sign the message together with the message and encrypt it with the receiver's public key to obtain the ciphertext.

Check the signature:

1. Use the receiver's private key to decrypt the ciphertext and get the message and message signature.

2. Use the sender's public key to decrypt the message signature and obtain the message digest.

3. Use the same method to re-extract the message digest, compared with the message digest in the previous step, if the same, the signature verification is successful.

The attached intention is as follows:

Implementation of RSA signature in go Standard Library / / signature func SignPKCS1v15 (rand io.Reader, priv * PrivateKey, hash crypto.Hash, hashed [] byte) ([] byte, error) {/ / Hash extraction message digest hashLen, prefix, err: = pkcs1v15HashInfo (hash, len (hashed)) if err! = nil {return nil Err} tLen: = len (prefix) + hashLen k: = (priv.N.BitLen () + 7) / 8 if k < tLen+11 {return nil, ErrMessageTooLong} / / EM = 0x00 | | 0x01 | | PS | | 0x00 | T em: = make ([] byte, k) em [1] = 1 for I: = 2 I < k-tLen-1 Copy + {em [I] = 0xff} / / integrate the message digest and message body copy (em [k-hashLen:k], prefix) copy (em [k-hashLen:k], hashed) m: = new (big.Int) .SetBytes (em) / / encrypt the message digest and message body using the sender's private key That is, signature c, err: = decryptAndCheck (rand, priv, m) if err! = nil {return nil, err} copyWithLeftPad (em, c.Bytes () return em, nil} / / verify signature func VerifyPKCS1v15 (pub * PublicKey, hash crypto.Hash, hashed [] byte, sig [] byte) error {/ / Hash extract message Digest hashLen, prefix, err: = pkcs1v15HashInfo (hash) Len (hashed)) if err! = nil {return err} tLen: = len (prefix) + hashLen k: = (pub.N.BitLen () + 7) / 8 if k < tLen+11 {return ErrVerification} c: = new (big.Int) .SetBytes (sig) / / decrypt using the sender's public key Extract message body and message signature m: = encrypt (new (big.Int), pub, c) em: = leftPad (m.Bytes (), k) / / EM = 0x00 | | 0x01 | | PS | | 0x00 | T / / compare the sender and receiver message body and message signature ok: = subtle.ConstantTimeByteEq (em [0], 0) ok & = subtle.ConstantTimeByteEq (em [1], 1) ok & = subtle.ConstantTimeCompare (em [k-hashLen:k]) Hashed) ok & = subtle.ConstantTimeCompare (em [k-tLen:k-hashLen], prefix) ok & = subtle.ConstantTimeByteEq (em [k-tLen-1], 0) for I: = 2 I < k return ErrVerification return nil 1; iTunes + {ok & = subtle.ConstantTimeByteEq (return ErrVerification [I], 0xff)} if ok! = 1 {return ErrVerification} Lenovo} / / Code location src/crypto/rsa/pkcs1v15.go postscript

A lot of knowledge of number theory is used in RSA algorithm, but the knowledge of number theory remains to be learned. To be continued.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.