A brief history of RSA encryption algorithms
The RSA was proposed in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman. All three of them worked at MIT at that time. RSA is composed of the letters at the beginning of the last names of the three of them.
Principles of RSA encryption algorithm
Friends who have learned algorithms know that algorithms in computers are actually mathematical operations. Therefore, before explaining the RSA encryption algorithm, it is necessary to understand some essential mathematical knowledge. Let’s start with mathematical knowledge.
Essential mathematical knowledge
In RSA encryption algorithm, onlyPrime numbers, mutual prime numbers, exponential operations, modular operationsLet’s wait for a few simple math knowledge. Therefore, we also need to understand these concepts.
Prime numbers
Prime numbers, also known as prime numbers, refer to numbers that cannot be divided by other natural numbers except 1 and the integer itself. We have learned this concept in junior high school and even elementary school, so we won’t explain it too much here.
Muto prime number
The explanation on Baidu Encyclopedia is: two numbers with only 1 common factors are called mutual prime numbers. ;The explanation on Wikipedia is: mutual quality, also known as mutual quality. If the greatest common factor of N integers is 1, then the N integers are called co-equality.
There are several common methods for judging co-prime numbers:
1. Two different prime numbers must be mutual prime numbers. For example, 2 and 7, 13 and 19.
2. One prime number and the other are not multiples of it. These two numbers are mutual prime numbers. For example, 3 and 10, 5 and 26.
3. The two adjacent natural numbers are mutual prime numbers. Such as 15 and 16.
4. The two adjacent odd numbers are mutual prime numbers. Such as 49 and 51.
5. Two numbers whose larger numbers are prime numbers are mutual prime numbers. Such as 97 and 88.
6. The decimal number is a prime number, and two numbers whose large number is not a multiple of the decimal number are mutual prime numbers. For example 7 and 16.
7, 2 and any odd number are mutual prime numbers. For example 2 and 87.
8. 1 is not a prime number or a composite number. It is a co-prime number with any natural number. Such as 1 and 9908.
9. Transition and phase division.
Exponential operation
Exponential operation is also called multiplication calculation, and the calculation result is called power. nm refers to multiplying n itself m times. Considering nm as the result of multiplying is called "m power of n" or "m power of n". Among them, n is called the "base number" and m is called the "exponent".
Modular operation
Module operation is to find the residual operation. "Mod" is the transliteration of "Mod". A concept closely related to modulo operations is "consistency". Mathematically, when two integers are divided by the same positive integer, if the same remainder is obtained, the two integers are the same remainder.
If the remainders obtained by dividing them by the positive integer m are equal, then a and b are called congruent for modulo m, and are denoted as:a ≡ b (mod m)；Read as: a is conservative with b modulus m, or a and b are conservative with b about modulus m. For example: 26 ≡ 14 (mod 12).
RSA encryption algorithm
Generation of public keys and keys
Suppose Alice wants to receive a private message from Bob through an unreliable media. She can generate a public key and a private key in the following ways:
1. Choose two large prime numbers p and q at will. p does not equal q and calculate N=pq.
2. According to the Euler function, find r = (p-1)(q-1)
3. Select an integer e less than r, find the inverse element of e about modulo r, and name it d. (The modular inverse element exists if and only if e and r are coeligible)
4. Destroy the records of p and q.
(N,e) is the public key, and (N,d) is the private key. Alice passes her public key (N,e) to Bob and hides her private key (N,d).
Encrypted messages
Suppose Bob wants to send Alice a message m, and he knows the N and e generated by Alice. He converts m into an integer n smaller than N using the format that was originally agreed with Alice. For example, he can convert each word into the Unicode code of the word, and then connect these numbers together to form a number. If his message is very long, he can divide the message into several segments and then convert each segment into n. Using the following formula, he can encrypt n as c:
ne ≡ c (mod N)
Calculation of c is not complicated. Bob can pass it to Alice after calculating c.
Decrypt the message
After Alice gets Bob's message c, she can use her key d to decode it. She can use the following formula to convert c to n:
cd ≡ n (mod N)
After getting n, she can restore the original information m.
The principle of decoding is:
cd ≡ n e·d(mod N)
as well ased ≡ 1 (mod p-1)anded ≡ 1 (mod q-1)。It can be proved by Fermat's small theorem (because p and q are prime numbers)
n e·d ≡ n (mod p)andn e·d ≡ n (mod q)
This shows that (because p and q are different prime numbers, p and q are co-centric)
n e·d ≡ n (mod pq)
Signature message
RSA can also be used to sign a message. If A wants to pass a signed message to B, she can calculate a hash value for her message, then encrypt the hash value with her private key and add this "signature" to the message. This message can only be decrypted with her public key. After B obtains this message, he can use A's public key to decrypt the hash value, and then compare the data with the hash value he calculated for this message. If the two match, then he can know that the sender holds A's key and that the message has not been tampered with in the propagation path.
Golang Encryption Decryption RSA
In PHP, many functions are often solved by one function; but not in Go. This article will learn Go's RSA-related APIs through PHP encryption, Go decryption; Go encryption, and PHP decryption.
This article discusses Go RSA encryption and decryption. All operations are done under linux.
1. Summary
This is an asymmetric encryption algorithm, which is generally encrypted by public key and decrypted by private key.
During the encryption and decryption process, openssl is used to produce the key. Perform the following operations:
1) Create a private key:
openssl genrsa -out 1024 //Key length，1024If you think it's not safe enough, you can use it2048，But the cost increases accordingly
2) Create a public key:
openssl rsa -in -pubout -out This creates a key。
Generally, each language also provides APIs for generating keys. In Go, you can view itencoding/pemPackage andcrypto/x509Bag.
Encryption and decryption involve many standards. I personally recommend that you learn it temporarily when you need it.
2. Go RSA encryption and decryption
1. RSA is encrypted and decrypted, and you will definitely check itcrypto/rasThis bag
Package rsa implements RSA encryption as specified in PKCS#1.
This is the description of this package: Implementing RSA encryption technology, based on the PKCS#1 specification.
For what is PKCS#1, you can consult the relevant information. PKCS (public key cipher standard), and #1 is the RSA standard. You can view: Introduction to PKCS Series
From the name of the function in this package, you can see that there are two pairs of encrypted and decrypted functions.
EncryptOAEPandDecryptOAEP EncryptPKCS1v15andDecryptPKCS1v15
This is called an encryption scheme, you can view it in detail, PKCS #1 v2.1 RSA algorithm standard
It can be seen that when interacting with other languages, it is necessary to determine which solution is good to use.
PublicKeyandPrivateKeyThe two types represent public keys and private keys respectively. Regarding how members of these two types should be set, this involves the RSA encryption algorithm. In this article, instances of these two types are obtained by parsing the keys generated at the beginning of the article.
2. Parse the key to get instances of PublicKey and PrivateKey
I also spent a lot of time on this process (mainly not familiar with various encryption things): how toopensslWhat about the generated key file parsing to the public and private key instances?
existencoding/pemIn the package, I saw the words - BEGIN Type - like this, which is exactly the same asopensslThe generated key is similar in form, so try it.
In this package, a block represents the PEM encoding structure. For PEM, please refer to the relevant information. We want to parse the key, of courseDecodemethod:
func Decode(data []byte) (p *Block, rest []byte)
This gives an instance of Block (pointer).
Analyzecrypto/x509. Why x509? This involves a bunch of concepts again. No matter what, I'll see it tooencodingandcryptoThese two sub-packs were found.
In the x509 package, there is a function:
func ParsePKIXPublicKey(derBytes []byte) (pub interface{}, err error)
From the description of this function: ParsePKIXPublicKey parses a DER encoded public key. These values are typically found in PEM blocks with “BEGIN PUBLIC KEY”. It can be seen that this is what analyzes PublicKey. In addition, here we talk about PEM, you can use the encoding/pem above to be correct.
There are several methods for parsing private keys. From the above introduction, we know that RSA is PKCS#1, and there is just one method:
func ParsePKCS1PrivateKey(der []byte) (key *, err error)
The return is.
3. Decryption and decryption implementation
Through the above introduction, it is not difficult to implement decryption and decryption of RSA in Go. The code is as follows:
// Encryption
func RsaEncrypt(origData []byte) ([]byte, error) {
block, _ := (publicKey)
if block == nil {
return nil, ("public key error")
}
pubInterface, err := ()
if err != nil {
return nil, err
}
pub := pubInterface.(*)
return rsa.EncryptPKCS1v15(, pub, origData)
}
// Decrypt
func RsaDecrypt(ciphertext []byte) ([]byte, error) {
block, _ := (privateKey)
if block == nil {
return nil, ("private key error!")
}
priv, err := x509.ParsePKCS1PrivateKey()
if err != nil {
return nil, err
}
return rsa.DecryptPKCS1v15(, priv, ciphertext)
}
in,publicKeyandprivateKeyyesopensslThe generated key, I generated the following:
// The public and private keys can be read from the file
var privateKey = []byte(` -----BEGIN RSA PRIVATE KEY----- MIICXQIBAAKBgQDZsfv1qscqYdy4vY+P4e3cAtmvppXQcRvrF1cB4drkv0haU24Y 7m5qYtT52Kr539RdbKKdLAM6s20lWy7+5C0DgacdwYWd/7PeCELyEipZJL07Vro7 Ate8Bfjya+wltGK9+XNUIHiumUKULW4KDx21+1NLAUeJ6PeW+DAkmJWF6QIDAQAB AoGBAJlNxenTQj6OfCl9FMR2jlMJjtMrtQT9InQEE7m3m7bLHeC+MCJOhmNVBjaM ZpthDORdxIZ6oCuOf6Z2+Dl35lntGFh5J7S34UP2BWzF1IyyQfySCNexGNHKT1G1 XKQtHmtc2gWWthEg+S6ciIyw2IGrrP2Rke81vYHExPrexf0hAkEA9Izb0MiYsMCB /jemLJB0Lb3Y/B8xjGjQFFBQT7bmwBVjvZWZVpnMnXi9sWGdgUpxsCuAIROXjZ40 IRZ2C9EouwJBAOPjPvV8Sgw4vaseOqlJvSq/C/pIFx6RVznDGlc8bRg7SgTPpjHG 4G+M3mVgpCX1a/EU1mB+fhiJ2LAZ/pTtY6sCQGaW9NwIWu3DRIVGCSMm0mYh/3X9 DAcwLSJoctiODQ1Fq9rreDE5QfpJnaJdJfsIJNtX1F+L3YceeBXtW0Ynz2MCQBI8 9KP274Is5FkWkUFNKnuKUK4WKOuEXEO+LpR+vIhs7k6WQ8nGDd4/mujoJBr5mkrw DPwqA3N5TMNDQVGv8gMCQQCaKGJgWYgvo3/milFfImbp+m7/Y3vCptarldXrYQWO AQjxwc71ZGBFDITYvdgJM1MTqc8xQek1FXn1vfpy2c6O -----END RSA PRIVATE KEY----- `) var publicKey = []byte(` -----BEGIN PUBLIC KEY----- MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDZsfv1qscqYdy4vY+P4e3cAtmv ppXQcRvrF1cB4drkv0haU24Y7m5qYtT52Kr539RdbKKdLAM6s20lWy7+5C0Dgacd wYWd/7PeCELyEipZJL07Vro7Ate8Bfjya+wltGK9+XNUIHiumUKULW4KDx21+1NL AUeJ6PeW+DAkmJWF6QIDAQAB -----END PUBLIC KEY----- `)
4. Use examples
package main
import (
"fmt"
)
func main() {
data, err := RsaEncrypt([]byte("git@/mrkt"))
if err != nil {
panic(err)
}
origData, err := RsaDecrypt(data)
if err != nil {
panic(err)
}
(string(origData))
}
This example is encryptedgit@/mrktDecrypt it immediately
3. Cross-language encryption and decryption
The language is normal, and you have to see if it is consistent with other languages, that is, other languages are encrypted, Go language must be correctly decrypted; Go language is encrypted, other languages are correctly decrypted
1. PHP RSA encryption and decryption
Here, I chose PHP and used the openssl extension. Encryption and decryption in PHP are very simple, as follows two methods (here only considers encryption with public key and decryption with private key):
bool openssl_public_encrypt ( string $data , string &$crypted , mixed $key [, int $padding = OPENSSL_PKCS1_PADDING ] ) bool openssl_private_decrypt ( string $data , string &$decrypted , mixed $key [, int $padding = OPENSSL_PKCS1_PADDING ] )
The last parameter is the encryption scheme (compensation method). Since Go uses PKCS1 instead of OAEP, you can just use the default value.
The PHP code is as follows:
$privateKey = '-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQDZsfv1qscqYdy4vY+P4e3cAtmvppXQcRvrF1cB4drkv0haU24Y
7m5qYtT52Kr539RdbKKdLAM6s20lWy7+5C0DgacdwYWd/7PeCELyEipZJL07Vro7
Ate8Bfjya+wltGK9+XNUIHiumUKULW4KDx21+1NLAUeJ6PeW+DAkmJWF6QIDAQAB
AoGBAJlNxenTQj6OfCl9FMR2jlMJjtMrtQT9InQEE7m3m7bLHeC+MCJOhmNVBjaM
ZpthDORdxIZ6oCuOf6Z2+Dl35lntGFh5J7S34UP2BWzF1IyyQfySCNexGNHKT1G1
XKQtHmtc2gWWthEg+S6ciIyw2IGrrP2Rke81vYHExPrexf0hAkEA9Izb0MiYsMCB
/jemLJB0Lb3Y/B8xjGjQFFBQT7bmwBVjvZWZVpnMnXi9sWGdgUpxsCuAIROXjZ40
IRZ2C9EouwJBAOPjPvV8Sgw4vaseOqlJvSq/C/pIFx6RVznDGlc8bRg7SgTPpjHG
4G+M3mVgpCX1a/EU1mB+fhiJ2LAZ/pTtY6sCQGaW9NwIWu3DRIVGCSMm0mYh/3X9
DAcwLSJoctiODQ1Fq9rreDE5QfpJnaJdJfsIJNtX1F+L3YceeBXtW0Ynz2MCQBI8
9KP274Is5FkWkUFNKnuKUK4WKOuEXEO+LpR+vIhs7k6WQ8nGDd4/mujoJBr5mkrw
DPwqA3N5TMNDQVGv8gMCQQCaKGJgWYgvo3/milFfImbp+m7/Y3vCptarldXrYQWO
AQjxwc71ZGBFDITYvdgJM1MTqc8xQek1FXn1vfpy2c6O
-----END RSA PRIVATE KEY-----'; $publicKey = '-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDZsfv1qscqYdy4vY+P4e3cAtmv
ppXQcRvrF1cB4drkv0haU24Y7m5qYtT52Kr539RdbKKdLAM6s20lWy7+5C0Dgacd
wYWd/7PeCELyEipZJL07Vro7Ate8Bfjya+wltGK9+XNUIHiumUKULW4KDx21+1NL
AUeJ6PeW+DAkmJWF6QIDAQAB
-----END PUBLIC KEY-----';
function rsaEncrypt($data)
{
global $publicKey;
openssl_public_encrypt($data, $crypted, $publicKey);
return $crypted;
}
function rsaDecrypt($data)
{
global $privateKey;
openssl_private_decrypt($data, $decrypted, $privateKey);
return $decrypted;
}
function main()
{
$crypted = rsaEncrypt("git@/mrk");
$decrypted = rsaDecrypt($crypted);
echo "encrypt and decrypt:" . $decrypted;
}
main();
Here we also use PHP to decryptgit@/mrkt
2. Go and PHP work together
One thing to note here is that since the encryption is a byte stream, the direct output and viewing will be garbled. Therefore, in order to facilitate the direct encryption and decryption of the language, the encrypted data will be encoded in base64 here.
3. Use
In the example, both the php and Go versions support the -d parameter to pass in the encrypted string and decrypt it; when not passed, an encrypted and base64-encoded string will be output, which can be used for decryption in other languages.
Summarize
The above is all the content of RSA's encryption and decryption using Go language. The article explains the encryption and decryption process of RSA in depth, which is very helpful to friends who learn related knowledge. If you have any questions, please leave a message to discuss.