Java中的确定性RSA加密

Question

这是我在本站上的第一个问题，我只有基本的RSA数学理解，请多包涵！ :)

我正在为我的大学毕业项目编写Java Web应用程序。它是“Pret-a-voter”的网络实现，是一种安全投票系统，对于那些听说过的人来说。

我的问题在于，我想让扮演审计员角色的人表现出：

• 一个源字节数组（要加密的明文）
• RSA公钥文件
• 一个“目标”字节数组，这是根据明文和公钥计算的密码数据的结果

然后我希望审计员能够使用前两个项目进行加密，并确信第三个项目是结果。因此，我需要加密是确定性的，即在重复使用相同的明文和公钥进行加密时生成相同的密码数据。

（注意-在这个项目中，我使用非常小的数据块-根本没有对称加密...我知道这是RSA的一个“有趣”的用途！）

无论如何，我发现在Java中，使用

cipher = Cipher.getInstance("RSA");

使用默认的随机填充方案，需要消耗11个字节（因此，使用2048位密钥对，可以加密2048/8-11=245个字节）。重复加密相同的明文将生成不同的密文，这显然不是我想要的ECB模式。

我的问题是——我应该使用以下内容吗？

cipher = Cipher.getInstance("RSA/ECB/NoPadding");

我在很多地方读到RSA没有填充时不安全。这是因为攻击者可以建立明文/密文的字典吗？这是确定性加密的副作用，我需要它来允许审计员验证我的加密，在我的方案中，审计员是受信任的，所以这没问题。

我的第二个问题与Java相关。如果我像上面那样使用RSA/ ECB / NoPadding，我相信我能够提供一个长度为128的源字节数组（例如，对于1024位RSA密钥对），并将其加密以获得另一个长度为128的字节数组。然后，如果我尝试使用不同的1024长度公钥再次加密那个数组，我会得到

 

javax.crypto.BadPaddingException：消息大于模数

有人知道为什么吗？

编辑-NoPadding加密并不总是生成此异常-它很难琢磨。但是，即使加密不会生成此异常，解密也会生成此异常：

 

javax.crypto.BadPaddingException：数据必须以零开始

非常感谢您阅读这篇文章！任何帮助都将不胜感激。

编辑-抱歉，我的原始问题没有很清楚地说明我想要做什么，所以这里有一个[尝试]的解释：

• 明文是选民在选举中的投票。
• Pret-a-voter旨在实现端到端可验证性，同时不牺牲选民的机密性（等等）。选民在投票后会收到一张收据，他们可以使用该收据验证他们的投票是否被正确记录，并且稍后还将显示他们的投票没有被篡改。选民将在其收据上的信息与发布在网络上的完全相同的副本进行比较。
• 但是，任何选民都不应该能够证明自己的投票方式（因为这可能会导致强制），因此信息不是明文，而是投票的加密副本。
• 事实上，明文被加密了四次，使用四个不同的非对称密钥进行加密 - 由两个不同的出纳员持有，每个出纳员持有两个密钥。因此，一个投票（明文）提供给一个出纳员，该出纳员使用公钥＃1加密它，然后使用其第二个公钥加密该密文，将该密文交给第二个出纳员，后者用相同的方式使用他的两个密钥加密它。结果的密文（四个顺序加密的结果）是发布到Web上的内容（公开发布）。出纳员是值得信赖的。
• 每个加密的选票可以被视为一个“洋葱”，其中心是选票，有几层加密。为了获得选票，必须逐层删除每个层，这意味着必须按相反的顺序应用对应的私钥（由出纳员持有）。这是安全的关键 - 所有出纳员必须合作才能解密投票。
• Web公告板可以被视为具有5列的表格 - 左侧的第一列包含完全加密的选票（也显示在每个选民的收据上），并且是投票阶段期间唯一可见的列。第二列包含相同的选票集，但已去除外层 - 出纳员2在计票阶段使用其私钥解密选票来填充此列和列3。在计票阶段结束时，第5列包含完全解密的选票，然后可以进行统计。
• 每个选民都会收到一个收据，将他们链接到第1列中的加密选票。这不显示他们的投票方式，但允许他们验证他们的投票是否未被篡改，因为在整个选举过程中，他们可以验证他们的加密选票仍然在第1列中未被触动。当然，这只是“端到端验证”的一半，因为选民无法验证解密是否已经正确完成，即在第2列中存在一个条目，其中是他们的投票减去外层加密。每个选民只负责到第1列之前的验证。
• 此后，审计员有责任检查第1列的条目是否解密为第2列等等。他们这样做的方法是依靠确定性加密和用于加密的公钥是公开的。
• 由于公钥是公开的，因此您不希望人们简单地从第5列到第1列画线，将某人的投票连接起来，因为它变得越来越多次加密 - 这样，将您与加密的选票联系起来的收据实际上将您与未加密的可读选票联系起来-->强迫！

  很抱歉以上内容有些冗长 - 我希望它能描述我对确定性加密的需求。我错过了很多基本细节（我已经大量修改了此方案），但是希望核心原则都在那里。非常感谢您的阅读 - 我真的很感激。

- Chris B

---

我认为RSA/ECB根本没有任何意义，因为ECB是块密码的链接模式（或者更准确地说，缺乏链接）。您有协议规范的链接吗？也许您错过了什么。 - Bruno Rohée

我在这里了解到了RSA/ECB/NoPadding getInstance参数： http://stackoverflow.com/questions/2714327/java-rsa-badpaddingexception-data-must-start-with-zero 不幸的是，协议规范都在我的脑海中和我编写的代码中 - 我可以发布代码，但它是一个巨大的eclipse项目，可能需要很长时间才能阅读和解释。 除了我提到的NoPadding选项（可能不安全，但似乎确实有效 - 尽管有时会生成“消息大于模数”的错误），是否还有其他方法在Java中进行确定性加密？ - Chris B

也许有一种方法可以为“随机”填充提供种子，使得对于给定的明文和填充种子，密文是恒定的。然后我可以将该种子提供给审计员。 - Chris B

当“消息大于模数”时，这并不是真的吗？你不应该使用RSA加密长文本，大多数实用协议只加密对称密码的随机密钥，因此一些实现不支持RSA加密长消息，因为它的实际价值很小...在您的情况下，您可能需要重新实现RSA，BigInteger上次我检查时非常可靠。 - Bruno Rohée

顺便说一句，从我对协议的了解来看，我认为它并不安全。也许你应该使用验证器密钥对每个投票进行加密，以提供足够的信息供他们验证，但可预测的加密听起来并不正确。你正在刻意删除安全功能... - Bruno Rohée

Answer 1

去除填充会使系统不安全。如果公钥确实是公开的，正如你所说的那样，那么攻击者可以简单地转到第5列，获取明文，并使用正确顺序的4个公钥对其进行加密。然后，他们可以将生成的密文与收据中的密文进行匹配，从而破坏“无强制性”的属性。

随机填充可以防止这种情况发生，因为攻击者不知道要添加什么填充。

您需要使用正常填充，但向审计员的子集（在选举系统中通常称为“监票人”）公开部分私钥。这意味着一个监票人可以确认第1列与第2列是否匹配，另一个监票人可以确认第2列与第3列是否匹配，依此类推。单个监票人无法将选民与选票匹配，只有合作的监票人才能做到。

---

您收到“消息大于模数”错误的原因是每个模数都不同，因此来自一个加密的密文可能超出下一个加密的允许范围。

- caf

---

非常感谢您的想法。我忘记提到的一个关键点是，被选人名单的“循环移位”（在每张选票上通过任何整数模N（对于N个候选人）旋转）是加密的——“X”位置以明文存储。然而，在加密的每个阶段还会添加“种子”，以防止攻击者能够像您所说的那样使用四个密钥进行加密——他们不知道要使用哪些种子，因此不知道应该如何通过种子值将循环移位反转（）。 - Chris B

鉴于此，我能回到不填充的状态吗？还是说我最好考虑向一部分监察员公开私钥子集？令人难以置信的是，到目前为止，我在Java中重复加密128字节数组（使用成本为11字节的随机填充）的方式是将4字节整数附加到byte[]，并将前15字节移至“溢出”数据库字段。解密时，这些溢出将适当地预置。这样做并不理想，但它确实起作用——唯一遇到问题的时候是发现它不是确定性的时候。 - Chris B

@Chris：由于候选人数N通常非常小，未知的循环移位不会显著增加攻击者的工作量 - 他们只需要尝试所有可能的明文移位中的N个即可。 - caf

我的想法是使用一个（可能很大的）循环移位，范围为2^32，并将其模N作为实际移位，希望这样做没问题。然而，考虑到我可能能够在不从头开始重新设计的情况下拯救这个项目并已经投入了几个小时的时间，我认为您的解决方案，即坚持随机填充并为每个审计员提供一个或两个私钥，是我将要使用的解决方案。我仍然希望能够只给他们明文+PK并要求他们验证我的密文计算，但不用担心。谢谢你的帮助 :) - Chris B

@Chris：问题在于只有mod N后的值才是重要的——所有其他可能的值都等同于0...N-1循环移位值之一。没问题。如果你们学院里有一个对RSA数学有深刻理解的人可以审查你的方案，那可能是个好主意。 - caf

Answer 2

填充（Padding）的作用是为了避免同一明文加密后得到相同的密文。如果您希望对于任何给定的明文都能得到确定性（单一）结果，则唯一的选择是关闭填充。具体信息请参考：https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Padding。

- Paul Ruane

---

谢谢。您有使用Java进行此操作的经验吗？如果我选择使用RSA/ECB/NoPadding，那么我是否被迫使用2^N字节的输入数据？我只需用零填充它吗？如果我的建议听起来荒谬，请原谅 - 我已经阅读了很多，但仍然不知道如何实现我需要的内容。如果有帮助的话，我在问题末尾添加了一些要点。再次感谢！ - Chris B

不，我没有这方面的第一手经验。你可以通过一个简单的实证测试来回答零填充的问题。从你列出的要点来看，在某些情况下，加密哈希可能更好。不过，我会明天再读一遍。 - Paul Ruane

Answer 3

所以我认为您正在尝试使用确定性RSA解决两个主要需求：

1. 允许选民确保其投票的完整性
2. 允许审计员确保所有选票的完整性

数字签名应该可以解决这个问题。您可以从第一列中获取密文，对其进行哈希处理，并使用私钥加密哈希值。然后将加密的哈希值放置在第二列中。要验证第一列的完整性，只需使用相应的公钥解密第二列中的哈希值，对第一列进行哈希处理，并比较这两个值。如果它们相等，则数据没有被篡改。只有拥有私钥的各方才可能篡改这些列中的数据，因为只有他们可以制作匹配的密钥对。这类似于HMAC，但具有使用公共/私有密钥而不是秘密共享密钥的优点。因此，任何人都可以验证，但只有可信任的各方才能修改。

关于确定性模式的一点需要注意的是，它会以多种方式泄露信息。假设我知道我投票支持蓝色作为我最喜欢的颜色。我可以看到我的投票结果的密文是0x12345678。如果模式是完全确定性的，我就知道任何其他具有相应密文0x12345678的人也投票支持蓝色。此外，由于通常会有一个有限的选票选择集，已知明文攻击非常容易。因此，你真的希望让RSA发挥其作用并使用预期的填充方案。

接下来，你可能要考虑的是通过对投票进行编号或类似的方式来保护系统免受重放攻击的影响。根据我理解你的模式，如果我以某种方式获取了你存储投票的位置（或者介入了任何通信过程），我基本上可以通过重放或复制我已经看到的数据来伪造或垃圾邮件式地进行虚假投票（这也是确定性模式的另一个问题）。

- Luke

---

非常感谢大家阅读并留下评论。我不确定我需要的是HMAC - 我在问题底部添加了一些要点，以尝试澄清为什么我希望RSA加密是确定性的。但我可能会错过某些东西或未能看到其他选择 - 如果您有时间查看和/或让我知道HMAC仍然可行，我将不胜感激。谢谢。 - Chris B

我再试了一次。你是对的，HMAC并不完全符合您的需求，但我认为数字签名是可以胜任的。我认为您尝试做的事情与数字签名非常接近。最重要的是，我强烈建议您不要按照您正在尝试使用RSA的方式。这将不会安全。 - Luke

花了一些时间思考这个问题，虽然我确信这或多或少是解决方案，但对于它的工作原理仍然不完全清楚。目标是说服选民，第1列中4倍加密的选票实际上就是第5列中的选票，只是经过加密和洗牌处理。第1、3、5列是公开的。对于第3列中的每个条目，审计员会被展示链接到第1或第5列（通过第2或第4列分别；他们的选择，所以每个人都可以相当有信心所有链接都是正确的）。按照你所说的做法-对第1列进行哈希处理，然后在第2-5列中进行四次私钥加密，难道没有人能够... - Chris B

在第5列中有一个4倍加密的哈希值，然后使用4个公钥进行解密，以将第5列中的投票与第1列中的加密投票关联起来 - 通过按顺序为每个密钥执行公钥解密？ - Chris B

听起来你真正想签名的是第5列，对吗？如果第5列是他们的明文投票，你希望他们确信他们的实际投票已经被正确记录（以一种也可以被审计员验证的方式）。对投票的明文进行哈希处理，使用私钥加密并提供公钥进行验证。将其放入您的表中。当我想要验证时，我拿出我的投票（我知道我的投票是什么），对其进行哈希处理，并在使用公钥解密后与表中的哈希进行比较。 - Luke