RSA算法實戰(zhàn)

溫故知新
在?HTTPS系列之密碼學(xué)基礎(chǔ)--證書及簽名?文章中對證書和簽名進(jìn)行了簡單的介紹。核心在講述下面的內(nèi)容:
公鑰加密,私鑰解密。私鑰簽名,公鑰驗證。
本文將通過RSA算法來對實踐一下。
RAS算法
概念
RSA算法是一種非對稱加密算法,在公開密鑰加密和電子商務(wù)中被廣泛使用。RSA是由Ron Rivest、Adi Shamir、Leonard Adleman在1997你年一起提出來的。RSA是他們?nèi)?strong>姓氏開頭字母拼在一起組成的。
安全性
大質(zhì)數(shù)做因式分解困難。理論證明有興趣可以查看維基百科。
公私鑰生成流程
1.
隨機找兩個質(zhì)數(shù) P 和 Q ,P 與 Q 越大,越安全。(例如:61和53)
2.
計算p和q的乘積n。(n = 61×53 = 3233,n的長度就是密鑰長度。3233寫成二進(jìn)制是110010100001,一共有12位,所以這個密鑰就是12位。)
3.計算 n 的歐拉函數(shù) φ(n)。(根據(jù)公式φ(n) = (p-1)(q-1)算出φ(3233)等于60×52,即3120)
4.隨機選擇一個整數(shù) e,條件是1< e < φ(n),且 e 與 φ(n) 互質(zhì)。(條件是1< e < φ(n),且e與φ(n) 互質(zhì)。1到3120之間,隨機選擇了17。)
5.有一個整數(shù) d,可以使得 ed 除以 φ(n) 的余數(shù)為 1。(ed ≡ 1 (mod φ(n)),即17*2753 mode 3120 = 1)
6.將n和e封裝成公鑰,n和d封裝成私鑰。(n=3233,e=17,d=2753,所以公鑰就是 (3233,17),私鑰就是(3233, 2753)。)
RSA加密
首先對明文進(jìn)行比特串分組,使得每個分組對應(yīng)的十進(jìn)制數(shù)小于n(密鑰長度),然后依次對每個分組m做一次加密,所有分組的密文構(gòu)成的序列就是原始消息的加密結(jié)果,即m滿足0≤m<n。
加密算法為: c≡ me mod n; c為密文,且0≤c<n。
RSA解密
對于密文0≤c<n,解密算法為: m≡ cd mod n。
RSA簽名驗證
RSA密碼體制既可以用于加密又可以用于數(shù)字簽名。
已知公鑰(e,n),私鑰d。
1.對于消息m簽名為:sign ≡ md mod n
2.驗證:對于消息簽名對(m,sign),如果m ≡ signe mod n,則sign是m的有效簽名
圖解RSA算法
msg = “待加密字符串”;
msgHash = “待簽名字符串,由msg進(jìn)行hash得到”;
encryptedMsg = “msg加密后的字符串”;
signedMsg = “msgHash簽名后的字符串”;
注意:
B在簽名操作的時候,需要將原文msg和簽名后的signedMsg一起發(fā)送給A。
A在驗簽操作的時候,需要將原文msg進(jìn)行hash得到msgHash,再對signedMsg進(jìn)行驗簽。

這個流程不正是?HTTPS系列之密碼學(xué)基礎(chǔ)--證書及簽名?中冰女給卡爾寫信,卡爾回信的一個流程嗎!!
python實現(xiàn)
代碼
import rsa
# rsa加密
def rsaEncrypt(str):
? ?# 生成公鑰、私鑰
? ?(pubkey, privkey) = rsa.newkeys(512)
? ?print("公鑰:\n%s\n私鑰:\n:%s" % (pubkey, privkey))
? ?# 明文編碼格式
? ?content = str.encode("utf-8")
? ?# 公鑰加密
? ?crypto = rsa.encrypt(content, pubkey)
? ?return (crypto, privkey)
# rsa簽名
def rsaSignature(str):
? ?# 生成公鑰、私鑰
? ?(pubkey, privkey) = rsa.newkeys(512)
? ?print("公鑰:\n%s\n私鑰:\n:%s" % (pubkey, privkey))
? ?# 明文編碼格式
? ?content = str.encode("utf-8")
? ?# 私鑰簽名
? ?sign_content = rsa.sign(content, privkey, hash_method= "MD5")
? ?return (sign_content, privkey, pubkey)
# ?rsa簽名驗證
def ?verifySignature(str, sign_content, publicKey):
? ?verifyState = rsa.verify(str.encode("utf-8"), sign_content, publicKey)
? ?return verifyState
# rsa解密
def rsaDecrypt(str, pk):
? ?# 私鑰解密
? ?content = rsa.decrypt(str, pk)
? ?con = content.decode("utf-8")
? ?return con
if __name__ == "__main__":
? ?str, pk = rsaEncrypt("hello")
? ?print("加密后密文:\n%s" % str)
? ?content = rsaDecrypt(str, pk)
? ?print("解密后明文:\n%s" % content)
? ?sign_str, pk, pubkey= rsaSignature("無情劍客")
? ?print("簽名后的內(nèi)容是:\n%s" %sign_str)
? ?verifySignature("無情劍客", sign_str, pubkey)
注意一下這里的鑰匙,包括了d, e, n, p, q的值。

運行結(jié)果
公鑰:
PublicKey(6724473421617242406033381907376973847701520125454157522060405520033944305101855214760573237185166023091650432736600268403970570744813381953262177544625259, 65537)
私鑰:
:PrivateKey(6724473421617242406033381907376973847701520125454157522060405520033944305101855214760573237185166023091650432736600268403970570744813381953262177544625259, 65537, 2451148901674081874936775567775890386312184174999990372530036887072812234444050202758587277441923426272269899052384408399111077953647079855236631759734273, 4010988364819606716981934755585055372145464201482196612705679395958113663731500801, 1676512821776702924436322032243523484844142298453208720288227205443678059)
加密后密文:
b"Q\xd3*\xe3\x85\x01\x19\x12\x85\xc9\xf0PRbh\x7f\x01\xe6\x86\xd2:J\x12\xee\x9e\x11\x9fU;\xc5$H\xado\xab\x19\xeb\xf2'k\xab\xda\xc6 \x1c\xc6\xb0\xb2\x0eC\xccZ9\x89\xa9\x91\xaee\x81,|Qp\xe0"
解密后明文:
hello
公鑰:
PublicKey(8193891274525958296363775492883760563553517922477344673165506854369989686854027952057004806850378754875438172242728613760836138261927106484501676466689559, 65537)
私鑰:
:PrivateKey(8193891274525958296363775492883760563553517922477344673165506854369989686854027952057004806850378754875438172242728613760836138261927106484501676466689559, 65537, 2480284649954162697152212921370035889036341128615981256790169293330360792526935074929436520962790960483160278292175246636411096362939467659267719544939569, 7459041359283394484872085428762006331855202857395448848532451826326422789817766373, 1098518010538711151640961069219349068251138170748833890300964836048222283)
簽名后的內(nèi)容是:
b'\x1f\xdc\xa7\x01\xca\xed^\xd5\x10_\x19\x11N\xbd\xaa\x9a\x99\x02\xe3\x95\x15\xc9\x8f\\\xe4W\xc2\xc3\xab"s2K\xa7+\x96[\xdf\x9b\xcc^~\x03\xce\xdbvQ\xd6.\xa1\x0bn\xee\xc2\xf0c\x0e~^a\xe4\xddXN'
hash算法是:MD5
參考
RSA非對稱加密圖解和原理[1]?http://tool.chacuo.net/cryptrsapubkey?通俗易懂RSA[2]?維基百科?HTTPS系列之密碼學(xué)基礎(chǔ)--證書及簽名?https://www.ruiwen.com/wenxue/qingshi/74858.html?python3 RSA加解密[3]
公眾號
更多內(nèi)容, 歡迎關(guān)注我的微信公眾號: 無情劍客。

References
[1]
?RSA非對稱加密圖解和原理:?https://www.jianshu.com/p/2f7e8f2efcf3[2]
?通俗易懂RSA:?https://www.cnblogs.com/jockming/p/12111579.html[3]
?python3 RSA加解密:?https://blog.csdn.net/whatday/article/details/97617461/