為什麼添加 PKCS#1 v1.5 填充會使 RSA 加密變得不確定？

我是密碼學的初學者，但在過去的幾周里，我一直在使用 PyCrypto 庫根據規範實施一些加密。

我發現單獨使用 RSA 公鑰加密時，加密似乎是確定性的（意味著多次加密同一消息會產生相同的密文）。但是，一旦我添加了 PKCS#1 v1.5 填充，它就會變得不確定（密文在後續加密中會有所不同）。

這在以下 Python3/PyCrypto 程式碼中得到了展示：

import os

from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA


with open(os.path.expanduser('~/.ssh/id_rsa.pub')) as public_key_file:
   public_key = RSA.importKey(public_key_file.read())

message = b'hi'

print("Encrypting without padding:")
print(public_key.encrypt(message, None)[0].hex())
print(public_key.encrypt(message, None)[0].hex())
print(public_key.encrypt(message, None)[0].hex())

cipher = PKCS1_v1_5.new(public_key)

print("Encrypting with PKCS1#v1.5")
print(cipher.encrypt(message).hex())
print(cipher.encrypt(message).hex())
print(cipher.encrypt(message).hex())

輸出以下內容：

Encrypting without padding:
14cdd5f88f2858aca9e12b3a282783e80e2cc3aff70c1afe2e71e107a0528f4b5feba278175c6ed32300c4fa916d033de55c4b43d1254012f94ced05763bc87475395a04a50f7bf18b4a6f4cc711a07e5447a1470f24d22bc6c01d9ed03b26d151cd4fa6d7999ee14ef50f550b3cd39ac2be7b7f22408bcc7592de437796bf147174c097f5e3237aeaae17ec994a5d370e06301389b31cca3542e19b182df58aab5c74401da11eafb57f9beca920dca7acee556e26b133f945c7477745b5f29f7fd77fc624faa7e2db3a6d43d806cc5918b54e68094becb5b57a18530c955d354869a446441391bdca142aa035addb2e2303a2dc776ce40ba4eb44ff21033951
14cdd5f88f2858aca9e12b3a282783e80e2cc3aff70c1afe2e71e107a0528f4b5feba278175c6ed32300c4fa916d033de55c4b43d1254012f94ced05763bc87475395a04a50f7bf18b4a6f4cc711a07e5447a1470f24d22bc6c01d9ed03b26d151cd4fa6d7999ee14ef50f550b3cd39ac2be7b7f22408bcc7592de437796bf147174c097f5e3237aeaae17ec994a5d370e06301389b31cca3542e19b182df58aab5c74401da11eafb57f9beca920dca7acee556e26b133f945c7477745b5f29f7fd77fc624faa7e2db3a6d43d806cc5918b54e68094becb5b57a18530c955d354869a446441391bdca142aa035addb2e2303a2dc776ce40ba4eb44ff21033951
14cdd5f88f2858aca9e12b3a282783e80e2cc3aff70c1afe2e71e107a0528f4b5feba278175c6ed32300c4fa916d033de55c4b43d1254012f94ced05763bc87475395a04a50f7bf18b4a6f4cc711a07e5447a1470f24d22bc6c01d9ed03b26d151cd4fa6d7999ee14ef50f550b3cd39ac2be7b7f22408bcc7592de437796bf147174c097f5e3237aeaae17ec994a5d370e06301389b31cca3542e19b182df58aab5c74401da11eafb57f9beca920dca7acee556e26b133f945c7477745b5f29f7fd77fc624faa7e2db3a6d43d806cc5918b54e68094becb5b57a18530c955d354869a446441391bdca142aa035addb2e2303a2dc776ce40ba4eb44ff21033951

Encrypting with PKCS1#v1.5
1c5fb53f2814b2521b89bc6051c82c145ff5141c2cd3e2e76a9072d24b54940157283a0d897621aaef9aa1f315f3cec574616cdb00ce5c999eb7cb47bc65af3650af22f94322e930ce3f95829f50aa980293ee2a1eb225812b89ffb552283fb6649b07b14b6c2903cdd30ea5e91b7aef15aba11b9caf588c6150639718afd9a4c176f2a6221ce84db437a697b3ae6cde54dc272ac5363357f4ba8122d347b241636563e9a948aad8d016b03f03bfc17e6634cc7436f46751619227821089fb0245b444e58e6723f30e73f9ac9095d3f014a3c6aaaf95069159efff3e59ef21cc0f35601df3cac0551da6a62213f4cefff8ef7b4d8b6e40ca4e4a05975203c233
b5cc3075a7e604bbf1d6fdddf33b5f59d778066cb45d37faef5bb3853f9b78d9222c77ba483e6b90bab81ead44504b6b61535eb6f2f3aebfb6f9a350cc87a095337a678d6f088c87d95fd27f4f2fb1f5e2ee4ad46afa8b78a4e5aceb33e7fd7a42df0ce458478be8ecca81b432eb690de68041d9126bbcb6881c016e49b844400930fd41fb96235588f038cbb4ef858082b053496c9dd4bd67ac23197e170189198c2c228c89c9ba016a5da78f7451a1e134cd33de3507b2bcd0c4f7480afc735e265da8f95674710725b5bbb6ac550d0e13e8724b0fcf624b7d6f001ca68a5be6841dab06cfc905340afab10a925813e20c7230592d182fd3ccfd319739da59
710b7690cd3c682aceb125561ab826188add17ea6cb714831ad4f749d6d2b9573635cb4c5fc79990653216db99cc13fc1bb8cbe7f966718462d4e11a8d124b4745355eba34e6bf5674b7e2ee9b2c1d855edc086bfe629b13f5cf38b6a4c2fc3739a12e5cea6269f7f2b9e8c1cea0e9c380bba196c5f797a3dec3f11123796193755497c6448c9c495f2599feb9ec75c2bf2564d3e0683bebe101f8baa687f6a8da1934b0f0de48ec79d62693bffe9f8befc39dcfd833b8311eb3866da40a245553a2840de036a9ed5c19353af97ccd191392f6292e9f0ebe3cf6e9c5de5ed9d8f32ffc26cd136e0e36e1d76cac842880d28a997ce3dac415a47416c8a38be438

我的問題是：為什麼這兩種情況下的確定性存在差異？我理解為什麼加密中的非確定性是有用的（以防止攔截器注意到兩條消息相同），但為什麼單獨的 RSA 加密不能提供這個，以及填充如何添加這個？這是填充的目的之一嗎？

當您使用教科書 RSA 時，公鑰是 $ (e,N) $ 和消息的密文 $ m $ 是 $ c = m^e\bmod N $ . 教科書RSA的加密過程不涉及隨機性；這會導致問題。

很容易看出，當 $ m_1=m_2 $ 他們的密文 $ m_1^e =m_2^e \bmod N $ . 確定性加密不是 CPA 安全的。

當使用像 PKCS#1 v1.5 這樣的填充方案時，一個重要的方面是填充是隨機的，因此每次加密時都會有所不同。

在用於 RSA 的 PKCS#1 v1.5 中， $ m $ 被填充到 $ x=0x00||0x02||r||0x00||m $ 密文是 $ c=x^e\bmod N $ 代替 $ m^e\bmod N $ . 這裡 $ r $ 是一個足夠長的隨機字元串。因此，即使有 $ m_1=m_2 $ , 它們的密文將產生於 $ x_1\ne x_2 $ ，因此看起來完全不同。

當然，長度 $ r $ 很重要，如果太短，隨機性不夠，攻擊還是有可能的。在標準中，它規定

• 讓 $ N $ 是 $ k $ 字節長，然後 $ m $ 一定是 $ \leq $ $ k-11 $ 字節長。
• 填充字元串 ( $ x $ ） 一定是 $ k $ 字節長。

因此 $ r $ 是 $ k-3-|m| $ 字節長 ( $ |m| $ 是明文的字節數 $ m $ is)，它至少有 8 個字節長。然而，這可能還不夠。我記得在Kats & Lindell 的書中，它提到 $ r $ 大約需要一半的長度 $ N $ ，以便我們認為 RSA CPA 是安全的。

引用自：https://crypto.stackexchange.com/questions/66521