Golang encryption and decryption RSA (with php)

A brief history of the RSA encryption algorithm

RSA was developed in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman ) were proposed together. All three of them were working at MIT at the time. RSA is composed of the initial letters of their last names spelled together.

RSA Encryption Algorithm Principle

Friends who have studied algorithms know that algorithms in computers are actually mathematical operations. Therefore, before explaining the RSA encryption algorithm, it is necessary to understand some necessary mathematical knowledge. Let’s start with mathematical knowledge.

Required mathematical knowledge

In the RSA encryption algorithm, only a few simple mathematical knowledge such as prime numbers, coprime numbers, exponential operations, and modular operations are used. Therefore, we also need to understand these concepts.

Prime number

A prime number, also known as a prime number, refers to a natural number greater than 1 that is not divisible by other natural numbers except 1 and the integer itself. We have all learned this concept in junior high school and even elementary school, so I won’t explain it too much here.

Coprime numbers

The explanation on Baidu Encyclopedia is: Two numbers with a common factor of only 1 are called coprime numbers. ; The explanation on Wikipedia is: co-prime, also known as co-prime. If the greatest common factor of N integers is 1, then these N integers are said to be relatively prime.

Common common methods for judging coprime numbers include the following:

1. Two different prime numbers must be coprime numbers. For example, 2 and 7, 13 and 19.

2, one quality number, the other is not its multiple, these two numbers are the number of mutual quality. For example, 3 and 10, 5 and 26.

3. Two adjacent natural numbers are co-prime. Such as 15 and 16.

            4. Two adjacent odd numbers are co-prime numbers. Such as 49 and 51.

5. The larger number is the two numbers of the quality. Such as 97 and 88.

6. The decimal is quality, and the two numbers are not the multiple of the decimal number. For example 7 and 16.

7, 2 and any odd number are co-prime numbers. For example 2 and 87.

8. 1 is neither a prime number nor a composite number. It is coprime with any natural number. Such as 1 and 9908.

9. Euclidean division.

Exponent operation

Exponential operation is also called exponentiation calculation, and the calculation result is called power. nm refers to multiplying n by itself m times. Treating nm as the result of exponentiation is called "n raised to the m power" or "n raised to the m power". Among them, n is called the "base" and m is called the "exponent".

Modular operation

Modular operation is the remainder operation. "Module" is the transliteration of "Mod". A concept closely related to modular arithmetic is "congruence". Mathematically, when two integers are divided by the same positive integer and get the same remainder, then the two integers are congruent.

Two integers a, b, if the remainders obtained by dividing them by a positive integer m are equal, then a and b are said to be congruent modulo m, denoted as: a ≡ b (mod m); read as: a is congruent to b modulo m, or a and b are congruent modulo m. For example: 26 ≡ 14 (mod 12).

RSA encryption algorithm

Generation of public key and secret key

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 way:

1. Randomly select two large prime numbers p and q, p is not equal to q, and calculate N=pq.

        2. According to the Euler function, find r = (p-1)(q-1)

        3. Choose an integer e that is less than r, and find Obtain the modular inverse element of e with respect to modulo r, and name it d. (The modular inverse element exists if and only if e and r are mutually prime)

4. Destroy the records of p and q.
(n, e) is the public key, (n, d) is the private key. Alice passes her public key (N,e) to Bob and hides her private key (N,d).

Encrypted message

Suppose Bob wants to send a message m to Alice, and he knows the N and e generated by Alice. He uses the format he originally agreed with Alice to convert m into an integer n less than N. 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 paragraphs and then convert each paragraph into n. Using the following formula, he can encrypt n into c:

　ne ≡ c (mod N)

Calculating c is not complicated. After Bob figures out c, he can pass it to Alice.

Decrypt 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 decoding principle is:

cd ≡ n e·d(mod N)

and ed ≡ 1 (mod p-1) and ed ≡ 1 (mod q- 1). It can be proved by Fermat’s little theorem (because p and q are prime numbers)

　n e·d ≡ n (mod p) 　And n e·d ≡ n (mod q)

This shows (because p and q are different prime numbers, so p and q are relatively prime)

　n e·d ≡ n (mod pq)

Signed message

RSA can also be used to A message signature. If A wants to deliver a signed message to B, then she can calculate a hash value (Message digest) for her message, then use her key (private key) to encrypt the hash value and add this "signature" At the end of the message. This message can only be decrypted using her public key. After B obtains the message, he can use A's public key to decrypt the hash value, and then compare this data with his own hash value calculated for the 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 during the propagation path.

Golang Encryption and Decryption of RSA

In PHP, many functions are often solved by one function; but in Go, this is not the case. This article will learn Go's RSA-related API through PHP encryption, Go decryption; Go encryption, PHP decryption.

This article discusses Go RSA encryption and decryption. All operations are completed under linux.

1. Overview

This is an asymmetric encryption algorithm that generally uses public key encryption and private key decryption.

In the encryption and decryption process, openssl is used to generate the key. Perform the following operations:

1) Create a private key:

openssl genrsa -out private.pem 1024 //密钥长度，1024觉得不够安全的话可以用2048，但是代价也相应增大

2) Create a public key:

openssl rsa -in private.pem -pubout -out public.pem
这样便生产了密钥。

Generally , each language will also provide API for generating keys. In Go, check out the encoding/pem package and the crypto/x509 package.

Encryption and decryption involves many standards. I personally recommend learning them temporarily when needed.

2. Go RSA encryption and decryption

1. For rsa encryption and decryption, you will definitely check the crypto/ras package

Package rsa implements RSA encryption as specified in PKCS#1.

This This is the description of this package: Implements RSA encryption technology, based on the PKCS#1 specification.

For what is PKCS#1, you can check the relevant information. PKCS (Public Key Cryptozoology Standard), and #1 is the RSA standard. You can view: PKCS Series Introduction

From the names of the functions in this package, you can see that there are two pairs of encryption and decryption functions.

EncryptOAEP和DecryptOAEP
EncryptPKCS1v15和DecryptPKCS1v15

This is called the encryption scheme. You can view the details. PKCS #1 v2.1 RSA algorithm standard

is visible. When interacting with other languages, it needs to be determined. Which solution to use.

PublicKey and PrivateKey represent the public key and private key respectively. Regarding how to set the members of these two types, this involves the RSA encryption algorithm. In this article, examples of these two types are analyzed through the article The key generated at the beginning is obtained.

2. Parse the key to get instances of PublicKey and PrivateKey

This process also took me a long time (mainly not familiar with various encryption things): How to parse the key file generated by openssl into public key and private key instances?

In the encoding/pem package, I saw the words --BEGIN Type ---. This is similar to the key form generated by openssl, so give it a try.

In this package, a block represents the structure of PEM encoding. For PEM, please check the relevant information. We want to parse the key, of course using the Decode method:

func Decode(data []byte) (p *Block, rest []byte)

In this way, we get an instance (pointer) of Block.

Analysis to see crypto/x509. Why x509? This involves a bunch of concepts again. Regardless of these, I also found out by looking at the sub-packages of the encoding and crypto packages.

In the x509 package, there is a function:

func ParsePKIXPublicKey(derBytes []byte) (pub interface{}, err error)

From the description of the 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 the parsing of PublicKey. In addition, when it comes to PEM here, the encoding/pem above can be correct.

There are several methods for parsing private keys. From the above introduction, we know that RSA is PKCS#1, and there is exactly one method:

func ParsePKCS1PrivateKey(der []byte) (key *rsa.PrivateKey, err error)

Return is rsa.PrivateKey.

3. Decryption and decryption implementation

Through the above introduction, it is not difficult to implement RSA decryption and decryption in Go. The code is as follows:

// Encryption

func RsaEncrypt(origData []byte) ([]byte, error) {
  block, _ := pem.Decode(publicKey)
  if block == nil {
    return nil, errors.New("public key error")
  }
  pubInterface, err := x509.ParsePKIXPublicKey(block.Bytes)
  if err != nil {
    return nil, err
  }
  pub := pubInterface.(*rsa.PublicKey)
  return rsa.EncryptPKCS1v15(rand.Reader, pub, origData)
}

// Decryption

func RsaDecrypt(ciphertext []byte) ([]byte, error) {
  block, _ := pem.Decode(privateKey)
  if block == nil {
    return nil, errors.New("private key error!")
  }
  priv, err := x509.ParsePKCS1PrivateKey(block.Bytes)
  if err != nil {
    return nil, err
  }
  return rsa.DecryptPKCS1v15(rand.Reader, priv, ciphertext)
}

其中，publicKey和privateKey是openssl生成的密钥，我生成的如下：

// 公钥和私钥可以从文件中读取

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、使用例子

package main
  
import (
  "fmt"
)
 
func main() {
  data, err := RsaEncrypt([]byte("git@github.com/mrkt"))
  if err != nil {
    panic(err)
  }
  origData, err := RsaDecrypt(data)
  if err != nil {
    panic(err)
  }
  fmt.Println(string(origData))
}

  

该例子是加密完git@github.com/mrkt后立马解密

三、跨语言加解密

语言内部正常，还得看看和其他语言是否一致，即：其他语言加密，Go语言得正确解密；Go语言加密，其他语言正确解密

1、PHP RSA加解密

这里，我选择PHP，使用的是openssl扩展。PHP中加解密很简单，如下两个方法（这里只考虑用公钥加密，私钥解密）：

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 ] )

   

最后一个参数是加密方案（补齐方式）。由于Go中使用的是PKCS1而不是OAEP，所以，使用默认值即可。

PHP代码如下：

$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@github.com/mrk");
  $decrypted = rsaDecrypt($crypted);
  echo "encrypt and decrypt:" . $decrypted;
 
}

   

main();

这里也是用PHP加解密git@github.com/mrkt

2、Go和PHP一起工作

这里要注意的一点是，由于加密后是字节流，直接输出查看会乱码，因此，为了便于语言直接加解密，这里将加密之后的数据进行base64编码。

3、使用

示例中，php和Go版本都支持-d参数传入加密好的字符串，将其解密；不传时，会输出加密好并base64编码的串，可用于其他语言解密。

总结

以上就是用Go语言实现了RSA的加密解密的全部内容，文章很深入的讲解了RSA的加密解密过程，对学习相关知识的朋友很有帮助。如果有疑问欢迎留言讨论。

更多Golang加密解密之RSA（附带php）相关文章请关注PHP中文网！