RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。
RSA加密算法原理
學(xué)過算法的朋友都知道，計算機中的算法其實就是數(shù)學(xué)運算。所以，再講解RSA加密算法之前，有必要了解一下一些必備的數(shù)學(xué)知識。我們就從數(shù)學(xué)知識開始講解。
必備數(shù)學(xué)知識
RSA加密算法中，只用到素數(shù)、互質(zhì)數(shù)、指數(shù)運算、模運算等幾個簡單的數(shù)學(xué)知識。所以，我們也需要了解這幾個概念即可。
素數(shù)
素數(shù)又稱質(zhì)數(shù)，指在一個大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。這個概念，我們在上初中，甚至小學(xué)的時候都學(xué)過了，這里就不再過多解釋了。
互質(zhì)數(shù)
百度百科上的解釋是：公因數(shù)只有1的兩個數(shù)，叫做互質(zhì)數(shù)。；維基百科上的解釋是：互質(zhì)，又稱互素。若N個整數(shù)的最大公因子是1，則稱這N個整數(shù)互質(zhì)。
常見的互質(zhì)數(shù)判斷方法主要有以下幾種：
1、兩個不同的質(zhì)數(shù)一定是互質(zhì)數(shù)。例如，2與7、13與19。
2、一個質(zhì)數(shù)，另一個不為它的倍數(shù)，這兩個數(shù)為互質(zhì)數(shù)。例如，3與10、5與 26。
3、相鄰的兩個自然數(shù)是互質(zhì)數(shù)。如 15與 16。
4、相鄰的兩個奇數(shù)是互質(zhì)數(shù)。如 49與 51。
5、較大數(shù)是質(zhì)數(shù)的兩個數(shù)是互質(zhì)數(shù)。如97與88。
6、小數(shù)是質(zhì)數(shù)，大數(shù)不是小數(shù)的倍數(shù)的兩個數(shù)是互質(zhì)數(shù)。例如 7和 16。
7、2和任何奇數(shù)是互質(zhì)數(shù)。例如2和87。
8、1不是質(zhì)數(shù)也不是合數(shù)，它和任何一個自然數(shù)在一起都是互質(zhì)數(shù)。如1和9908。
9、輾轉(zhuǎn)相除法。
指數(shù)運算
指數(shù)運算又稱乘方計算，計算結(jié)果稱為冪。nm指將n自乘m次。把nm看作乘方的結(jié)果，叫做”n的m次冪”或”n的m次方”。其中，n稱為“底數(shù)”，m稱為“指數(shù)”。
模運算
模運算即求余運算。“模”是“Mod”的音譯。和模運算緊密相關(guān)的一個概念是“同余”。數(shù)學(xué)上，當兩個整數(shù)除以同一個正整數(shù)，若得相同余數(shù)，則二整數(shù)同余。
兩個整數(shù)a，b，若它們除以正整數(shù)m所得的余數(shù)相等，則稱a，b對于模m同余，記作: a ≡ b (mod m)；讀作：a同余于b模m，或者，a與b關(guān)于模m同余。例如：26 ≡ 14 (mod 12)。
RSA加密算法
公鑰與密鑰的產(chǎn)生
假設(shè)Alice想要通過一個不可靠的媒體接收Bob的一條私人訊息。她可以用以下的方式來產(chǎn)生一個公鑰和一個私鑰：
1、隨意選擇兩個大的質(zhì)數(shù)p和q，p不等于q，計算N=pq。
2、根據(jù)歐拉函數(shù)，求得r = (p-1)(q-1)
3、選擇一個小于 r 的整數(shù) e，求得 e 關(guān)于模 r 的模反元素，命名為d。（模反元素存在，當且僅當e與r互質(zhì)）
4、將 p 和 q 的記錄銷毀。
(N,e)是公鑰，(N,d)是私鑰。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來。
加密消息
假設(shè)Bob想給Alice送一個消息m，他知道Alice產(chǎn)生的N和e。他使用起先與Alice約好的格式將m轉(zhuǎn)換為一個小于N的整數(shù)n，比如他可以將每一個字轉(zhuǎn)換為這個字的Unicode碼，然后將這些數(shù)字連在一起組成一個數(shù)字。假如他的信息非常長的話，他可以將這個信息分為幾段，然后將每一段轉(zhuǎn)換為n。用下面這個公式他可以將n加密為c：
ne ≡ c (mod N)
計算c并不復(fù)雜。Bob算出c后就可以將它傳遞給Alice。
解密消息
Alice得到Bob的消息c后就可以利用她的密鑰d來解碼。她可以用以下這個公式來將c轉(zhuǎn)換為n：
cd ≡ n (mod N)
得到n后，她可以將原來的信息m重新復(fù)原。
解碼的原理是：
cd ≡ n e·d(mod N)
以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由費馬小定理可證明（因為p和q是質(zhì)數(shù)）
n e·d ≡ n (mod p) 和 n e·d ≡ n (mod q)
這說明（因為p和q是不同的質(zhì)數(shù)，所以p和q互質(zhì)）
n e·d ≡ n (mod pq)
簽名消息
RSA也可以用來為一個消息署名。假如甲想給乙傳遞一個署名的消息的話，那么她可以為她的消息計算一個散列值(Message digest)，然后用她的密鑰(private key)加密這個散列值并將這個“署名”加在消息的后面。這個消息只有用她的公鑰才能被解密。乙獲得這個消息后可以用甲的公鑰解密這個散列值，然后將這個數(shù)據(jù)與他自己為這個消息計算的散列值相比較。假如兩者相符的話，那么他就可以知道發(fā)信人持有甲的密鑰，以及這個消息在傳播路徑上沒有被篡改過。
Golang加密解密之RSA
在PHP中，很多功能經(jīng)常是一個函數(shù)解決；而Go中的卻不是。本文會通過PHP加密，Go解密；Go加密，PHP解密來學(xué)習(xí)Go的RSA相關(guān)的API。
該文討論Go RSA加密解密。所有操作在linux下完成。
一、概要
這是一個非對稱加密算法，一般通過公鑰加密，私鑰解密。
在加解密過程中，使用openssl生產(chǎn)密鑰。執(zhí)行如下操作：
1）創(chuàng)建私鑰：
|
1
|
openssl genrsa -out private.pem 1024 //密鑰長度，1024覺得不夠安全的話可以用2048，但是代價也相應(yīng)增大 |
2）創(chuàng)建公鑰：
|
1
2
|
openssl rsa -in private.pem -pubout -out public.pem這樣便生產(chǎn)了密鑰。 |
一般地，各個語言也會提供API，用于生成密鑰。在Go中，可以查看encoding/pem包和crypto/x509包。
加密解密這塊，涉及到很多標準，個人建議需要的時候臨時學(xué)習(xí)一下。
二、Go RSA加密解密
1、rsa加解密，必然會去查crypto/ras這個包
|
1
|
Package rsa implements RSA encryption as specified in PKCS#1. |
這是該包的說明：實現(xiàn)RSA加密技術(shù)，基于PKCS#1規(guī)范。
對于什么是PKCS#1，可以查閱相關(guān)資料。PKCS（公鑰密碼標準），而#1就是RSA的標準。可以查看：PKCS系列簡介
從該包中函數(shù)的名稱，可以看到有兩對加解密的函數(shù)。
|
1
2
|
EncryptOAEP和DecryptOAEPEncryptPKCS1v15和DecryptPKCS1v15 |
這稱作加密方案，詳細可以查看，PKCS #1 v2.1 RSA 算法標準
可見，當與其他語言交互時，需要確定好使用哪種方案。
PublicKey和PrivateKey兩個類型分別代表公鑰和私鑰，關(guān)于這兩個類型中成員該怎么設(shè)置，這涉及到RSA加密算法，本文中，這兩個類型的實例通過解析文章開頭生成的密鑰得到。
2、解析密鑰得到PublicKey和PrivateKey的實例
這個過程，我也是花了好些時間（主要對各種加密的各種東東不熟）：怎么將openssl生成的密鑰文件解析到公鑰和私鑰實例呢？
在encoding/pem包中，看到了—–BEGIN Type—–這樣的字樣，這正好和openssl生成的密鑰形式差不多，那就試試。
在該包中，一個block代表的是PEM編碼的結(jié)構(gòu)，關(guān)于PEM，請查閱相關(guān)資料。我們要解析密鑰，當然用Decode方法：
|
1
|
func Decode(data []byte) (p *Block, rest []byte) |
這樣便得到了一個Block的實例（指針）。
解析來看crypto/x509。為什么是x509呢？這又涉及到一堆概念。先不管這些，我也是看encoding和crypto這兩個包的子包摸索出來的。
在x509包中，有一個函數(shù)：
|
1
|
func ParsePKIXPublicKey(derBytes []byte) (pub interface{}, err error) |
從該函數(shù)的說明：ParsePKIXPublicKey parses a DER encoded public key. These values are typically found in PEM blocks with “BEGIN PUBLIC KEY”。可見這就是解析PublicKey的。另外，這里說到了PEM，可以上面的encoding/pem對了。
而解析私鑰的，有好幾個方法，從上面的介紹，我們知道，RSA是PKCS#1，剛好有一個方法：
|
1
|
func ParsePKCS1PrivateKey(der []byte) (key *rsa.PrivateKey, err error) |
返回的就是rsa.PrivateKey。
3、解密解密實現(xiàn)
通過上面的介紹，Go中RSA的解密解密實現(xiàn)就不難了。代碼如下：
// 加密
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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)} |
// 解密
|
1
2
3
4
5
6
7
8
9
10
11
|
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生成的密鑰，我生成的如下：
// 公鑰和私鑰可以從文件中讀取
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
var privateKey = []byte(`-----BEGIN RSA PRIVATE KEY-----MIICXQIBAAKBgQDZsfv1qscqYdy4vY+P4e3cAtmvppXQcRvrF1cB4drkv0haU24Y7m5qYtT52Kr539RdbKKdLAM6s20lWy7+5C0DgacdwYWd/7PeCELyEipZJL07Vro7Ate8Bfjya+wltGK9+XNUIHiumUKULW4KDx21+1NLAUeJ6PeW+DAkmJWF6QIDAQABAoGBAJlNxenTQj6OfCl9FMR2jlMJjtMrtQT9InQEE7m3m7bLHeC+MCJOhmNVBjaMZpthDORdxIZ6oCuOf6Z2+Dl35lntGFh5J7S34UP2BWzF1IyyQfySCNexGNHKT1G1XKQtHmtc2gWWthEg+S6ciIyw2IGrrP2Rke81vYHExPrexf0hAkEA9Izb0MiYsMCB/jemLJB0Lb3Y/B8xjGjQFFBQT7bmwBVjvZWZVpnMnXi9sWGdgUpxsCuAIROXjZ40IRZ2C9EouwJBAOPjPvV8Sgw4vaseOqlJvSq/C/pIFx6RVznDGlc8bRg7SgTPpjHG4G+M3mVgpCX1a/EU1mB+fhiJ2LAZ/pTtY6sCQGaW9NwIWu3DRIVGCSMm0mYh/3X9DAcwLSJoctiODQ1Fq9rreDE5QfpJnaJdJfsIJNtX1F+L3YceeBXtW0Ynz2MCQBI89KP274Is5FkWkUFNKnuKUK4WKOuEXEO+LpR+vIhs7k6WQ8nGDd4/mujoJBr5mkrwDPwqA3N5TMNDQVGv8gMCQQCaKGJgWYgvo3/milFfImbp+m7/Y3vCptarldXrYQWOAQjxwc71ZGBFDITYvdgJM1MTqc8xQek1FXn1vfpy2c6O-----END RSA PRIVATE KEY-----`) var publicKey = []byte(`-----BEGIN PUBLIC KEY-----MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDZsfv1qscqYdy4vY+P4e3cAtmvppXQcRvrF1cB4drkv0haU24Y7m5qYtT52Kr539RdbKKdLAM6s20lWy7+5C0DgacdwYWd/7PeCELyEipZJL07Vro7Ate8Bfjya+wltGK9+XNUIHiumUKULW4KDx21+1NLAUeJ6PeW+DAkmJWF6QIDAQAB-----END PUBLIC KEY-----`) |
4、使用例子
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package main import ( "fmt")func main() { if err != nil { panic(err) } origData, err := RsaDecrypt(data) if err != nil { panic(err) } fmt.Println(string(origData))} |
該例子是加密完[email protected]/mrkt后立馬解密
三、跨語言加解密
語言內(nèi)部正常，還得看看和其他語言是否一致，即：其他語言加密，Go語言得正確解密；Go語言加密，其他語言正確解密
1、PHP RSA加解密
這里，我選擇PHP，使用的是openssl擴展。PHP中加解密很簡單，如下兩個方法（這里只考慮用公鑰加密，私鑰解密）：
|
1
2
3
4
|
bool openssl_public_encrypt ( string $data , string &$crypted , mixed$key [, int $padding = OPENSSL_PKCS1_PADDING ] ) boolopenssl_private_decrypt ( string $data , string &$decrypted , mixed$key [, int $padding = OPENSSL_PKCS1_PADDING ] ) |
最后一個參數(shù)是加密方案（補齊方式）。由于Go中使用的是PKCS1而不是OAEP，所以，使用默認值即可。
PHP代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
$privateKey = '-----BEGIN RSA PRIVATE KEY-----MIICXQIBAAKBgQDZsfv1qscqYdy4vY+P4e3cAtmvppXQcRvrF1cB4drkv0haU24Y7m5qYtT52Kr539RdbKKdLAM6s20lWy7+5C0DgacdwYWd/7PeCELyEipZJL07Vro7Ate8Bfjya+wltGK9+XNUIHiumUKULW4KDx21+1NLAUeJ6PeW+DAkmJWF6QIDAQABAoGBAJlNxenTQj6OfCl9FMR2jlMJjtMrtQT9InQEE7m3m7bLHeC+MCJOhmNVBjaMZpthDORdxIZ6oCuOf6Z2+Dl35lntGFh5J7S34UP2BWzF1IyyQfySCNexGNHKT1G1XKQtHmtc2gWWthEg+S6ciIyw2IGrrP2Rke81vYHExPrexf0hAkEA9Izb0MiYsMCB/jemLJB0Lb3Y/B8xjGjQFFBQT7bmwBVjvZWZVpnMnXi9sWGdgUpxsCuAIROXjZ40IRZ2C9EouwJBAOPjPvV8Sgw4vaseOqlJvSq/C/pIFx6RVznDGlc8bRg7SgTPpjHG4G+M3mVgpCX1a/EU1mB+fhiJ2LAZ/pTtY6sCQGaW9NwIWu3DRIVGCSMm0mYh/3X9DAcwLSJoctiODQ1Fq9rreDE5QfpJnaJdJfsIJNtX1F+L3YceeBXtW0Ynz2MCQBI89KP274Is5FkWkUFNKnuKUK4WKOuEXEO+LpR+vIhs7k6WQ8nGDd4/mujoJBr5mkrwDPwqA3N5TMNDQVGv8gMCQQCaKGJgWYgvo3/milFfImbp+m7/Y3vCptarldXrYQWOAQjxwc71ZGBFDITYvdgJM1MTqc8xQek1FXn1vfpy2c6O-----END RSA PRIVATE KEY-----'; $publicKey = '-----BEGIN PUBLIC KEY-----MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDZsfv1qscqYdy4vY+P4e3cAtmvppXQcRvrF1cB4drkv0haU24Y7m5qYtT52Kr539RdbKKdLAM6s20lWy7+5C0DgacdwYWd/7PeCELyEipZJL07Vro7Ate8Bfjya+wltGK9+XNUIHiumUKULW4KDx21+1NLAUeJ6PeW+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(){ $decrypted = rsaDecrypt($crypted); echo "encrypt and decrypt:" . $decrypted;} |
main();
這里也是用PHP加解密[email protected]/mrkt
2、Go和PHP一起工作
這里要注意的一點是，由于加密后是字節(jié)流，直接輸出查看會亂碼，因此，為了便于語言直接加解密，這里將加密之后的數(shù)據(jù)進行base64編碼。
3、使用
示例中，php和Go版本都支持-d參數(shù)傳入加密好的字符串，將其解密；不傳時，會輸出加密好并base64編碼的串，可用于其他語言解密。
總結(jié)
以上就是用Go語言實現(xiàn)了RSA的加密解密的全部內(nèi)容，文章很深入的講解了RSA的加密解密過程，對學(xué)習(xí)相關(guān)知識的朋友很有幫助。如果有疑問歡迎留言討論。
