使用 RSA 进行哈希
我正在考虑使用 RSA 加密算法创建一个哈希函数（如 md5 或 sha1）。我想知道是否有任何明显的原因导致该算法不起作用：
- 生成 RSA 公钥/私钥。
- 丢弃私钥，根本不存储它。
- 从长度为 RSA 加密的块大小的散列开始。
- 使用公钥加密消息，一次一个块。
- 对于消息的每个加密块，使用指定的算法（可能是 +、xor 等的组合）将其累积到哈希值。
要验证消息与存储的哈希值具有相同的哈希值，请使用保存的公钥并重复过程。
这可能、安全且实用吗？
感谢您的任何评论。
I am pondering creating a hash function (like md5 or sha1) using the RSA crypto algorithm. I am wondering if there are any obvious reasons that this algorithm wouldn't work:
- Generate RSA public/private keys.
- Discard private key, never store it at all.
- Begin with a hash with a length of the block size for the RSA encryption.
- Encrypt message using public key, one block at a time.
- For each encrypted block of the message, accumulate it to the hash using a specified algorithm (probably a combination of +, xor, etc.)
To verify a message has the same hash as a stored hash, use the saved public key and repeat the process.
Is this possible, secure, and practical?
Thanks for any comments.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
RSA 加密不是确定性的：如果您遵循 RSA 标准，您将看到注入了一些随机字节。因此，如果使用 RSA 对同一消息加密两次，很可能不会得到两次相同的输出。
此外，您的“未指定的第 5 步”可能很弱。例如，如果您定义一种散列块的方法，然后将块异或在一起，则 A||B 和 B||A （对于块大小值A和B）将散列为相同的值；这就是碰撞富矿。
在学术上，已经尝试过从数论结构（即不是原始 RSA，而是重用相同类型的数学元素）构建哈希函数；有关详细信息，请参阅 Lars Knudsen 的演示文稿。同样，ECOH 哈希函数 已提交给 SHA-3 竞赛，使用椭圆曲线它的核心（但它已“损坏”）。潜在的希望是散列函数安全性可以以某种方式与潜在的数论难题联系起来，从而提供可证明的安全性。然而，实际上，这样的哈希函数要么很慢，要么很弱，或者两者兼而有之。
RSA encryption is not deterministic: if you follow the RSA standard, you will see that some random bytes are injected. Therefore, if you encrypt with RSA the same message twice, chances are that you will not get twice the same output.
Also, your "unspecified step 5" is likely to be weak. For instance, if you define a way to hash a block, and then just XOR the blocks together, then A||B and B||A (for block-sized values A and B) will hash to the same value; that's collision bonanza.
Academically, building hash functions out of number-theoretic structures (i.e. not a raw RSA, but reusing the same kind of mathematical element) has been tried; see this presentation from Lars Knudsen for some details. Similarly, the ECOH hash function was submitted for the SHA-3 competition, using elliptic curves at its core (but it was "broken"). The underlying hope is that hash function security could somehow be linked to the underlying number-theoretic hard problem, thus providing provable security. However, in practice, such hash functions are either slow, weak, or both.
已经有一些散列基本上可以做到这一点，但可能不是特别针对 RSA 算法。它们被称为加密哈希，其突出点是它们在加密上是安全的 - 这意味着它们也具有与公钥加密函数相同的强度和面向安全的思想。
唯一的区别是，它们是从头开始设计为哈希的，因此它们也满足哈希函数的个性化要求，这可以被认为是密码函数不需要的额外优点。
此外，两者之间存在一些完全不一致的因素，例如，您希望散列函数在不影响安全性的情况下尽可能快，而缓慢通常被视为加密函数的一个特征，因为它大大限制了暴力攻击。
SHA-512 是一个很棒的加密哈希，可能值得您关注。 Whirlpool、Tiger 和 RipeMD 也是不错的选择。这些都不会出错。
还有一件事：如果您确实希望它变慢，那么您肯定不想要哈希函数，并且这样做完全是错误的。如果，正如我假设的那样，您想要的是一个非常非常安全的哈希函数，那么就像我说的那样，有许多选项比您的示例更适合，同时在加密上同样安全甚至更加安全。
顺便说一句，我并不完全相信你的混合算法没有弱点。虽然每个 RSA 块的输出旨在已经与高雪崩等保持一致，但我仍然担心这可能会给所选明文或类似消息的比较分析带来问题。
There are already hashes that do essentially this, except perhaps not with the RSA algorithm in particular. They're called cryptographic hashes, and their salient point is that they're cryptographically secure - meaning that the same strength and security-oriented thought that goes into public key cryptographic functions has gone into them as well.
The only difference is, they've been designed from the ground-up as hashes, so they also meet the individual requirements of hash functions, which can be considered as additional strong points that cryptographic functions need not have.
Moreover, there are factors which are completely at odds between the two, for instance, you want hash functions to be as fast as possible without compromising security whereas being slow is oftentimes seen as a feature of cryptographic functions as it limits brute force attacks considerably.
SHA-512 is a great cryptographic hash and probably worthy of your attention. Whirlpool, Tiger, and RipeMD are also excellent choices. You can't go wrong with any of these.
One more thing: if you actually want it to be slow, then you definitely DON'T want a hash function and are going about this completely wrong. If, as I'm assuming, what you want is a very, very secure hash function, then like I said, there are numerous options out there better suited than your example, while being just as or even more cryptographically secure.
BTW, I'm not absolutely convinced that there is no weakness with your mixing algorithm. While the output of each RSA block is intended to already be uniform with high avalanching, etc, etc, etc, I remain concerned that this could pose a problem for chosen plaintext or comparative analysis of similar messages.
通常，最好使用公开且经过审查流程的算法。尽管此类算法可能存在已知的弱点，但这可能比本土算法中的未知弱点要好。请注意，我并不是说所提出的算法有缺陷；而是说该算法有缺陷。只是，即使这里给出了大量的答案，说看起来不错，但并不能保证它不好。当然，对于MD5、SHA等算法也可以这样说。但至少对于这些算法，大量的人已经对它们进行了严格的分析。
除了之前针对设计自己的加密函数的“样板”警告之外，似乎所提出的解决方案在处理时间方面可能会有些昂贵。对大型文档进行 RSA 加密可能会令人望而却步。
Typically, it is best to use an algorithm that is publicly available and has gone through a review process. Even though there might be known weaknesses with such algorithms, that is probably better than the unknown weaknesses in a home-grown algorithm. Note that I'm not saying the proposed algorithm has flaws; it's just that even if a large number of answers are given here saying that it seems good, it doesn't guarantee that it doesn't. Of course, the same thing can be said about algorithms such as MD5, SHA, etc. But at least with those, a large number of people have put them through a rigorous analysis.
Aside from the previous "boilerplate" warnings against designing one's own cryptographic functions, it seems the proposed solution might be somewhat expensive in terms of processing time. RSA encryption on a large document could be prohibitive.
无需考虑太多，它似乎在加密上是安全的。
但是，您必须小心选择的明文攻击，如果您的输入很大，您可能会遇到速度问题（因为非对称加密比加密哈希慢得多）。
所以，简而言之：是的，这似乎是可能且安全的……但除非有真正令人信服的理由，否则如果您想要密钥哈希，我会使用标准 HMAC。
Without thinking too much about it, it seems like that would be cryptographically secure.
However, you'd have to be careful of chosen plaintext attacks, and if your input is large you may run into speed issues (as asymmetric crypto is significantly slower than cryptographic hashes).
So, in short: yes, this seems like it could be possible and secure… But unless there is a really compelling reason, I would use a standard HMAC if you want a keyed hash.
如上所述，步骤4.)是确定性的，即仅使用模数和公钥指数。
如果步骤 3.) 中的哈希值是私有的，那么这个概念对我来说似乎是安全的。
关于步骤5.)：在已知的内核算法的CBC模式中，在加密之前完成与先前结果的混合，步骤4.)，可能更好地避免串通，例如使用惰性散列；异或就可以了。
将应用这一点，因为已知哈希函数的可用实现可能有后门:)
确定性 Java RSA 是 这里。
编辑
另外值得一提的是，RSA 的可扩展性没有任何限制。这样的散列函数可以立即用作掩码生成函数。
As mentioned above step 4.) is to be done deterministic, i.e. with modulus and public key exponent, only.
If the hash in step 3.) is private, the concept appears secure to me.
Concerning Step 5.): In known CBC mode of kernel algorithms the mix with previous result is done before encryption, Step 4.), might be better for avoiding collusions, e.g. with a lazy hash; XOR is fine.
Will apply this, as available implementations of known hash functions might have backdoors :)
Deterministic Java RSA is here.
EDIT
Also one should mention, that RSA is scalable without any limits. Such hash function can immediately serve as Mask Generation Function.