RSA的基本知識和重要名詞
RSA是一種asymmetric演算法，它是透過一組public key和private key來進行Encrypt/Decrypt或是Sign/Verify。它的優點是：資料交換過程當中，雙方只需要拿到對方的public key即可加密資料，然後將加密後的密文(cipher)傳送給對方。只有正確的接收者才會有private key能夠解出密文(cipher)。缺點是，加密或是解密的效能較差不適合用於大量的資料加密。RSA的private key的建議長度最少是1024 bits以上，才具有基本的安全性, private key長度越長所需要的加解密運算成本越高,相對也會更加安全。Key Length
RSA 的Key Length 決定了RSA被破解的強度，長度越長基本上越難以被破解。但是，不是永遠不能破解，只是目前還沒有提出有效的破解方法。Public Exponent
公開指數是為了滿足RSA演算法所需要的一個整數，而且必須是質數Exponent ，然而很多密碼學的函式庫所內建的RSA Public Exponent都是65537的質數。有個討論在探討RSA Public Exponent 選擇 3 是否不夠安全的問題，有興趣的可以參考這網頁。無論如何，基本上選擇 65537的質數應該是一個較為安全且建議的作法。雖然選擇過大的質數會影響解密和驗證的效率，但是除非是要應用在運算能力非常弱的環境上，否則選擇小的質數當作Public Exponent應該不建議的，特別是Padding Mode很差的情形。但是，若選用合適的Padding Mode時，即使選擇3當作 RSA Public Exponent對於安全性並沒有太大的不同。Padding Mode
RSA基本上必須透過隨機的Padding方式，以確保即使每次都加密相同明文(Plan-Text)時候，不會產生完全相同的密文(Cipher-Text)。而OpenSSL支援 4 種 Padding Modes，以下截取自OpenSSL官方文件。而M2Crypto目前只支援 RSA_PKCS1_PADDING 和 RSA_PKCS1_OAEP_PADDING，根據官方文件上的建議就是使用 RSA_PKCS1_OAEP_PADDING。• RSA_PKCS1_PADDING
• RSA_PKCS1_OAEP_PADDING
• RSA_SSLV23_PADDING
• RSA_NO_PADDING
RSA Encrypt / Decrypt 的基本範例程式解說
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 | import M2Crypto import M2Crypto.BN as BN def generate_keypair_as_pem(key_len, exponent): def empty_callback(): pass rsa = M2Crypto.RSA.gen_key(key_len, exponent, empty_callback) # Get RSA Public Key in PEM format buf = M2Crypto.BIO.MemoryBuffer('') rsa.save_pub_key_bio(buf) public_key = buf.getvalue() # Get Private Key in PEM format buf = M2Crypto.BIO.MemoryBuffer('') rsa.save_key_bio(buf, None) private_key = buf.getvalue() # RSA Private Key return (public_key, private_key) if __name__ == '__main__': keylen = 1024 # 1024 bits exponent = 65537 padding = M2Crypto.RSA.pkcs1_oeap_padding # Generate RSA key-pair in PEM files for public key and private key public_key, private_key = generate_keypair_as_pem(keylen, exponent) message = 'This is a plain text data' # Use public key to encrypt 'message' buf = M2Crypto.BIO.MemoryBuffer('') buf.write(public_key) rsa1 = M2Crypto.RSA.load_pub_key_bio(buf) cipher_message = rsa1.public_encrypt(message, padding) # Use private key to decrypt 'cipher_message' rsa2 = M2Crypto.RSA.load_key_string(private_key) plaintext_message = rsa2.private_decrypt(cipher_message, padding) |
- 使用RSA演算法之前，必須產生 RSA 金鑰(Public Key and Private Key Pair)
- 第 22 和 23 行指定 key長度為 1024 bits，選用的public exponent 為 65537
- 產生 RSA Key-Pair 在第 8 行，透過 M2Crypto.RSA.gen_key 函數並指定 key 長度和 public exponent。第 3 個參數基本上只要給 empty_callback 即可，若是沒有給時，你呼叫這個函數會在 standard output 中出現類似....++的符號。它只是用來表示初始化 RSA key-pair 的進度狀態。此時我們可以取得 RSA 的 instance，存在 rsa 變數中。
- 分別取得 RSA public key 和 private key。M2Crypto 提供的方法，會將 Public key 和Private key 轉成 PEM 格式。
- 第 10 ～12 行是取得 RSA public key 的方式，第 15 ～17 行是取得RSA private key的方式。差別在於 rsa.save_key_bio(buf, None) 的第 2 個參數設定為 None的原因，是希望直接取得真正的 RSA private key 而不要再經由 aes_128_cbc的方式來保護。否則執行到這段程式碼時，系統會在 console 要求使用者輸入 passphrase 。細節請參M2Crypto官方文件。 但是，一般來說如果是要存在系統中某個地方時候，是會透過另一種加密演算法來保護這把 RSA private key。
- 第 31 ～33 行是載入 RSA public key 取得 RSA的 instance 存在變數 rsa1 中，第 34 行呼叫 rsa1.public_encrypt(message, padding)來加密明文(Plain Text)，其中指定 padding mode 為 OEAP Padding 。
- 第 37 ～38 透過 RSA private key 解開密文(Cipher Text)，也必須指定相同的 padding mode 。
RSA Sign and Verify Signature 的基本範例程式解說
以下這個範例，是 sender 以安全的方式傳送一個 message 給 receiver 的 RSA 常見的應用。為了方便解釋，以下我們稱 A 為 sender, Ｂ為 receiver 。它大致上有 7 個步驟如下：- Ａ與Ｂ各自產生一個 RSA的 key-pair (private and public key)
- Ａ與Ｂ交換自己的 public key。
- Ａ使用Ｂ的 public key來加密訊息產生 Cipher message。
- Ａ再使用自己的 private key 來為 Cipher message 產生 Signature。
- 然後 Ａ 把 Signature 和 Cipher message 傳送給 B。
- B 必須用 Ａ的 public key 來驗證所收到的 Signature 是否正確。
- B 再用自己的 private key 來解開 Cipher Message，即可得到Ａ傳送的訊息內容。
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | import M2Crypto import M2Crypto.BN as BN def generate_keypair_as_pem(key_len, exponent): def empty_callback(): pass rsa = M2Crypto.RSA.gen_key(key_len, exponent, empty_callback) # Get RSA Public Key in PEM format buf = M2Crypto.BIO.MemoryBuffer('') rsa.save_pub_key_bio(buf) public_key = buf.getvalue() # Get Private Key in PEM format buf = M2Crypto.BIO.MemoryBuffer('') rsa.save_key_bio(buf, None) private_key = buf.getvalue() # RSA Private Key return (public_key, private_key) def get_data_digest(data): msg_digest = M2Crypto.EVP.MessageDigest('sha256') msg_digest.update (data) digest = msg_digest.digest() return digest def generate_secure_msg(A_private_key, B_public_key, message): padding = M2Crypto.RSA.pkcs1_oaep_padding buf = M2Crypto.BIO.MemoryBuffer('') buf.write(B_public_key) rsa1 = M2Crypto.RSA.load_pub_key_bio(buf) cipher_message = rsa1.public_encrypt(message, padding) # Use A's private key to sign the 'cipher_message' digest1 = get_data_digest(cipher_message) rsa2 = M2Crypto.RSA.load_key_string(A_private_key) signature = rsa2.sign(digest1, 'sha256') return cipher_message, signature def read_secure_msg(A_public_key, B_private_key, cipher_message, signature): try: # Use A's public key to verify 'signature' buf = M2Crypto.BIO.MemoryBuffer('') buf.write(A_public_key) rsa3 = M2Crypto.RSA.load_pub_key_bio(buf) # Verify digest2 = get_data_digest(cipher_message) rsa3.verify(digest2, signature, 'sha256') # Use B's private key to decrypt 'cipher_message' rsa4 = M2Crypto.RSA.load_key_string(B_private_key) padding = M2Crypto.RSA.pkcs1_oaep_padding plaintext_message = rsa4.private_decrypt(cipher_message, padding) return plaintext_message except Exception as err: print 'Verify Fail:%r'% err raise if __name__ == '__main__': keylen = 1024 # 1024 bits exponent = 65537 padding = M2Crypto.RSA.pkcs1_oaep_padding # Generate RSA key-pair in PEM files for public key and private key A_pub_key, A_priv_key = generate_keypair_as_pem(keylen, exponent) # Generate RSA key-pair in PEM files for public key and private key B_pub_key, B_priv_key = generate_keypair_as_pem(keylen, exponent) # A is sender, B is receiver msg = 'A want to send this message to B' # Sender's behavior cipher_msg, signature = generate_secure_msg(A_priv_key, B_pub_key, msg) # Receiver's behavior plain_text = read_secure_msg(A_pub_key, B_priv_key, cipher_msg, signature) |
附註：
實務上 RSA 通常都會搭配 AES 做 secure key 的保護，純粹是根據你所要保護的資料大小以及應用所著重的特點而有不同，此外 RSA 並不適合用來加密大量資料。
Reference:
- M2Crypto https://pypi.python.org/pypi/M2Crypto
- OpenSSL http://www.openssl.org
- Block Cipher mode of operation https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
- RSA algorithm http://www.di-mgt.com.au/rsa_alg.html
- Generating CA certs and CA signed certs using python m2crypto https://gist.github.com/eskil/2338529
