在 PKCS#1 OAEP 加密/解密中交换公钥/私钥 [英] exchange public/private key in PKCS#1 OAEP encryption/decryption
问题描述
我对RSA只有一些非常初级的理论知识.
I only have some very rudimentary theoretical knowledge about RSA.
在阅读有关如何在实践中使用它的不同来源时，PKCS#1 OAEP 似乎是一件好事.
While reading different sources about how to use it in practice, it seemed that PKCS#1 OAEP would be a good thing.
对于测试实现，我使用 Python 和 PyCrypto.例如.this 是使用 PKCS# 的示例1 OAEP.
For a test implementation, I use Python with PyCrypto. E.g. this is an example using PKCS#1 OAEP.
使用公钥加密，然后使用私钥解密可以正常工作.例如.公众可以使用私钥向 X 人发送一些数据.
Encrypting using the public key and then decrypting using the private key works fine. E.g. the public can send some data to person X with the private key.
根据我对 RSA 工作原理的基本了解，我认为我可以互换公钥/私钥，即我可以使用公钥进行加密，使用私钥进行解密.例如.X 人可以使用自己的私钥加密一些数据，而公众可以使用公钥对其进行解密.如果解密工作正常，这可以证明数据来自 X.
From my basic understanding of how RSA works, I thought that I can just interchange the public/private key, i.e. I can use the public key for encrypting and the private key for decrypting. E.g. person X can encrypt some data with its own private key and the public can decrypt it using the public key. If the decryption works fine, this gives some sort of proof that the data is coming from person X.
当我尝试使用公钥解密时，PyCrypto 报错.
PyCrypto complains when I try to decrypt using the public key.
通过阅读 PyCrypto 源代码，在 _RSAKey._decrypt 函数(这里)，似乎密钥对象本身知道它是私钥还是公钥并且它们之间存在差异(令我惊讶的是，再次基于我非常基本的 RSA理解).
From reading the PyCrypto source code, in the _RSAKey._decrypt function (here), it seems that the key object itself knows if it is the private or public key and differs between them (to my surprise, again based on my very basic RSA understanding).
从那里看来，我可以破解解密函数，以便它使用公钥.或者有些不同:我可以在关键对象中交换公共指数 e 和私有指数 d.
From there, it looks like I could hack the decrypt function so that it uses the public key. Or somewhat differently: I could just interchange the public exponent e and the private exponent d in the key objects.
但这一切似乎不打算以这种方式使用/黑客攻击.所以我想在这里问一下我的误解.
But all this seems like it is not intended to be used/hacked this way. So I wanted to ask here about my misunderstandings.
另外，出于好奇，我生成了一些密钥 (RSA.generate(2048)) 并查看了 n、e 和d.在所有情况下，n 和 d 都非常大，而 e 在所有情况下都是 constant (65537) (I没想到会这样).
Also, just out of curiosity, I generated some keys (RSA.generate(2048)) and looked at n, e and d. In all cases, n and d was very huge while e was in all cases constant (65537) (I wouldn't have expected that).
从这一切看来，我真的不应该只交换 e 和 d.
I guess from all this that I really shouldn't just interchange e and d.
所以我想我应该使用其他方法进行签名，例如 PKCS1_PSS.
So I guess I should use some other method for the signature like PKCS1_PSS.
一些加密/解密代码，如果有人感兴趣的话:
Some code for the encrypting/decrypting, if anyone is interested:
def randomString(l):
import random
return ''.join(chr(random.randint(0, 0xFF)) for i in range(l))
def genkeypair():
from Crypto.PublicKey import RSA
key = RSA.generate(2048)
pubkey = key.publickey().exportKey("DER")
privkey = key.exportKey("DER")
return (pubkey,privkey)
def encrypt(v, rsapubkey):
from Crypto.PublicKey import RSA
rsakey = RSA.importKey(rsapubkey)
from Crypto.Cipher import PKCS1_OAEP
rsa = PKCS1_OAEP.new(rsakey)
import binstruct
from array import array
aeskey = randomString(32)
iv = randomString(16)
from Crypto.Cipher import AES
aes = AES.new(aeskey, AES.MODE_CBC, iv)
data = binstruct.varEncode(v)
data += array("B", (0,) * (-len(data) % 16))
out = binstruct.strEncode(rsa.encrypt(aeskey + iv))
out += array("B", aes.encrypt(data))
return out
def decrypt(stream, rsaprivkey):
from array import array
from StringIO import StringIO
if isinstance(stream, array): stream = stream.tostring()
if isinstance(stream, str): stream = StringIO(stream)
from Crypto.PublicKey import RSA
rsakey = RSA.importKey(rsaprivkey)
from Crypto.Cipher import PKCS1_OAEP
rsa = PKCS1_OAEP.new(rsakey)
import binstruct
aesdata = binstruct.strDecode(stream)
aesdata = rsa.decrypt(aesdata)
aeskey = aesdata[0:32]
iv = aesdata[32:]
from Crypto.Cipher import AES
aes = AES.new(aeskey, AES.MODE_CBC, iv)
class Stream:
buffer = []
def read1(self):
if len(self.buffer) == 0:
nextIn = stream.read(16)
self.buffer += list(aes.decrypt(nextIn))
return self.buffer.pop(0)
def read(self, n):
return "".join([self.read1() for i in range(n)])
v = binstruct.varDecode(Stream())
return v
(binstruct 是一个小可以编码/解码树数据结构的模块 - 类似于 JSON/BSON.)
(binstruct is a small module which can encode/decode tree data structures - similar to JSON/BSON.)
这就是我认为我也可以将 encrypt 与私钥一起使用，并将 decrypt 与公钥一起使用的地方.
That is where I thought I could just also use encrypt with the private key and and decrypt with the public key.
可以在 这里找到具有(希望)正确签名/身份验证的最终实现二进制结构.
推荐答案
您对交换公钥和私钥角色的一般理解是正确的.最后，RSA是基于这样的事实
Your general understanding about interchanging the roles of public and private key is correct. In the end, RSA is based on the fact that
m^(ed) congruent m (mod n)
通常称为 RSA 加密的通常是操作
What is normally titled RSA encryption is typically the operation
m^e mod n,
将消息提升到 e 次方，其中 e 是公钥.
raising the message to the e-th power where e is the public key.
然后解密
(m^e)^d mod n,
将加密消息提升到 d 次方，其中 d 是私钥.现在由于求幂规则和乘法是可交换的事实(这些仍然在模算术中成立)，我们有这个
raising the encrypted message to the d-th power with d being the private key. Now because of the rules of exponentiation and the fact that multiplication is commutative (these still hold in modular arithmetic) we have that
m congruent (m^e)^d congruent m^(ed) congruent m^(de) congruent (m^d)^e,
因此，如果您以相反的顺序应用这些操作，您会得到相同的结果.
and therefore you get the same result if you apply the operations in the reverse order.
您假设反转导致数字签名是正确的，因为每个人都可以使用公钥 e 验证(解密")签名，因此只有使用对应的私钥d.
You were right in assuming that the reversal leads to digital signatures, because everybody can verify ("decrypt") the signature with the public key e, so the message was authentic only if it was "encrypted" (signed) using the corresponding private key d.
事实证明，PyCrypto 只是试图防止您在这里误认为另一个，OpenSSL 或 Ruby OpenSSL 允许您例如 同时做:public_encrypt/public_decrypt 和 private_encrypt/private_decrypt.
As it turns out, PyCrypto is only trying to prevent you from mistaking one for the other here, OpenSSL or Ruby OpenSSL allow you for example to do both: public_encrypt/public_decrypt and private_encrypt/private_decrypt.
理论讲了这么多，现在来看看为什么有充分的理由不让你互换使用它们.我刚才描述的通常被称为教科书 RSA"，它仍然远非安全.需要注意其他事项以使结果在实践中可用.这就是为什么有一个专用的 签名包在 PyCrypto 中 - 这有效地完成了你所描述的事情，而且还处理了我提到的事情.虽然了解这些东西是如何工作的对我们的理解有好处，但我们应该始终在实践中使用这些包，因为它们已经犯了并修复了我们在推出自己的包时可能会引入的错误.
So much for the theory, now to why there is good reason for not letting you use them interchangeably. What I just described is often referred to as "textbook RSA" and it is still far from being secure. Additional things need to be taken care of to make the result usable in practice. And that's why there is a dedicated signature package in PyCrypto - this effectively does what you described, but also additionally takes care of the things I mentioned. While it is good for our understanding to know how these things work, we should always use such packages in practice because they already made and fixed the mistakes we would probably introduce when rolling our own.
至于为什么 e 总是 65537.它实际上不必是一个固定值，但通常选择它是一个非常小的数字，其二进制表示中的 1 尽可能少(65537 是 10001).在过去，也选择了 e=3 或 e=17，但在实践中被认为不安全，因为它们可以通过简单地获取密文的第 3 或第 17 根来进行攻击.如果 e=3 且 m=3，则 3^3 为 27，并且考虑到密文为 27，无论模数 n(通常大得多)如何，都不需要天才就能算出 m 为 3.所以危险在于密文，即使在取幂之后，也不会跨越模边界"，因此允许我们简单地取 e-th 根来得到原始消息.对于 1024 - 4096 位的典型模数，这不再是 e=65537 的问题.
As to why e is always 65537. It doesn't really have to be a fixed value, but it is commonly chosen to be a very small number with as few 1's in its binary representation as possible (65537 is 10001). In the past, e=3 or e=17 were also chosen, but were considered as not safe in practice because they could be attacked by simply taking the 3rd or 17th root of the ciphertext. If e=3 and m=3, then 3^3 is 27, and it takes no genius to figure out that m is 3 given that the ciphertext is 27, regardless of the modulus n (which is typically much larger). So the danger lies in the fact that the ciphertext, even after exponentiation, does not cross "the modulus boundary" and therefore allows us to simply take the e-th root to arrive at the original message. With typical moduli of 1024 - 4096 bits, this is no longer an issue with e=65537.
二进制表示中很少有 1 也有利于快速计算 m^e.模幂运算通常使用 乘方和平方 算法来实现，对于很少的小 e 的性能最好1的.为什么选择这种方式而不是相反，例如有一个小的 d 和几个 1?对于初学者来说，d 会更容易猜到.第二个优点是，使用数字签名，您通常对文档进行一次签名，但经常对其进行验证.这意味着 m^d 只执行一次，但 m^e 经常执行，因此您可以让常见任务执行得最好，而允许稀有任务执行得较差.
Few 1's in the binary representation are also good for computing m^e fast. Modular exponentiation is often implemented using a Multiply and Square algorithm, and performance is best for small e's with few 1's. Why is it chosen this way and not the other way round, for example having a small d with few 1's? Well for starters, d would be easier to guess that way. A second advantage is that with digital signatures, you typically sign a document once but verify it often. This means m^d is performed once but m^e often, so you have the common task perform best while the rare task is allowed to perform poor.
您问我是否可以进一步解释像 RSA-PSS 这样的方案为了安全而做了什么.
You asked whether I could further explain what schemes like RSA-PSS do in order to be secure.
比较 OAEP 的加密功能和 PSS 的签名功能时，两者看起来非常相似.事实上，它们都在过程中引入了随机化，这允许 OAEP 和 PSS 在某些假设下.我还发现此 论文 很有帮助.与老式的 PKCS 1.5 加密和签名相比，可证明的安全性是一个很大的优势，在相同的假设下，它可以被证明是不可证明的安全性(关键点:没有确定性方案可以，随机化是必不可少的).提议的签名和加密方案之间的一个明显区别是签名方案总是要求首先对要签名的消息进行哈希处理.这不仅在效率方面有意义，而且还可以防止一些原本可能发生的攻击.而且我想这导致了为什么我们应该始终使用签名方案进行签名和加密方案进行加密的要点:建议的方案附带安全证明，而我们的手工方案没有.
When comparing what OAEP does for encryption and what PSS does for signatures, the two look pretty similar. And in fact they are, they both introduce randomization in the process, which allows for provable security of OAEP and PSS under certain assumptions. I also found this paper to be helpful. Provable security is a big advantage over old-school PKCS 1.5 encryption and signatures, which can be shown to be not provably secure under the same assumptions (key point: no deterministic scheme can be, randomization is essential). An obvious difference between the proposed signature and encryption schemes is that the signature schemes always mandate the to-be-signed message to be hashed first. This makes sense not only with regard to efficiency, but it also prevents some attacks that would otherwise be possible. And I guess that leads to the gist of why we should always use signature schemes for signatures and encryption schemes for encryption: the proposed schemes come with security proofs attached, our handmade schemes don't.
密码学家发明这些方案是为了让我们这些凡人的生活变得更轻松 - 它们为我们提供了理想的工具，通过将选项数量减少到最低限度来避免滥用或误用.例如，即使您设法使用 RSA-OAEP 提出了一个好的签名方案，使用它的人可能不知道为什么他们应该在应用签名之前先散列他们的消息.RSA-PSS 甚至不可能发生这种滥用.
Cryptographers invent those schemes to make the lives of us mere mortals easier - they give us tools that ideally allow for no abuse or misuse by reducing the number of options to a minimum. For example, even if you managed to come up with a good signature scheme using RSA-OAEP, somebody who uses it might not know about why they should hash their messages first before applying the signature. That kind of misuse is not even a possibility with RSA-PSS.
您还询问了一些好的阅读材料.虽然这是一个非常主观的话题，但我真的很喜欢这些:
You also asked about some good reading material. Although this is a very subjective topic, I really enjoyed these:
实用方面:
应用密码学 - 仍然是经典，值得一读.一些安全人员说这很危险，因为它使人们相信他们知道的足够多，可以编写自己的加密货币.但我想我们都是成年人，不是吗?感觉外面有什么"还是很棒的
Applied Cryptography - still a classic and worth reading. Some security people say it is dangerous because it leads people to believing they know enough to write their own crypto. But I guess we are all grown-ups, aren't we? It's still great to get a feeling about "what's out there"
密码学工程 - 有一些很好的实用建议，还提到了实现加密代码时的注意事项.
Cryptography Engineering - Has some good practical advice and also mentions the caveats when implementing cryptography code.
应用密码学手册 - 它是免费的，仍然有很多好的建议，尤其是关于实现.
Handbook of Applied Cryptography - It's free and still has a lot of good advice especially with regard to implementations.
理论方面:
现代密码学 - 这是一个理论与实践相结合，对实践中可能出现的问题有很多洞察力.
Modern Cryptography - It's a hybrid between theory and practice and has a lot of insight how things can go wrong in practice.
密码学 - 理论与实践- 这对我来说改变了游戏规则，我喜欢这本书.如果你只读过一本书，那就是这本书吧:)
Cryptography - Theory and Practice - this was a game changer for me, I love this book. If you only ever read one book, let it be this one :)
现代密码学简介 -在解释现代方法"以及安全证明如何实际工作以及在哪些假设下工作方面做得很好.
Introduction to Modern Cryptography - does a great job at explaining "the modern approach" and how the security proofs actually work and under which assumptions.
密码学基础 I&II - 如果在上一本书之后您仍然无法获得足够的单向函数理论和朋友，那么这就是您的书.非常技术性.
Foundations of Cryptography I&II - if after the previous book you still can't get enough of the theory of one-way functions and friends, this is your book. Very technical.
安全不仅仅是密码学:
安全工程 - 有很多正确的原则在实践中如何出错的示例
Security engineering - has numerous examples how sound principles can go wrong in practice
信息安全 - 类似于安全工程，在比密码学更广泛的范围内说明安全性.
Information Security - Similar to Security Engineering, illustrating security in a scope wider than just cryptography.
除此之外，我尝试通过阅读有关新攻击、新技术等的最新论文来了解最新情况.我发现 r/netsec 非常有帮助，并且在 Twitter 上关注研究人员和从业者，他们会定期发布有趣的材料.
Apart from that, I try to keep up to date by reading recent papers about new attacks, technologies etc. I found r/netsec very helpful, as well as following researchers and practitioners on Twitter, they post interesting material regularly.
最后，如果您有时间，请参加 Coursera 和 Udacity 上的密码学课程！我想他们会在接下来的几周内重新开始，他们真的很棒，我相信你不会后悔的.他们有很多有趣的实践练习，很好地说明了攻击密码学实现的各种方法.
Finally, if you have the time, take the Cryptography courses on Coursera and Udacity! I think they'll start over in the next few weeks, they are really great, I'm sure you won't regret it. They had a lot of practical exercises that are a lot of fun and nicely illustrate various ways to attack cryptography implementations.
这篇关于在 PKCS#1 OAEP 加密/解密中交换公钥/私钥的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
