NTRU 私钥的中间人攻击
我想知道是否有人可以告诉我如何在 NTRU 私钥的中间相遇攻击中表示私钥 f 的向量枚举。我无法理解此处给出的示例 http://securityinnovation.com/cryptolab/pdf/NTRUTech004v2 .pdf 如果有人能详细展示一个例子，我将非常感激。
I was wondering if anyone could tell me how to represent the enumeration of vectors of privite key f in a Meet-In-the-Middle Attack on an NTRU Private key. I can not understand the example, given here http://securityinnovation.com/cryptolab/pdf/NTRUTech004v2.pdf
I'll be very thankful if anyone could show an example in detail.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
（全面披露：我在 Security Innovation 工作，并在 NTRU 工作，直到 SI 收购我们）
警告：答案很长！
让我们看一个玩具示例：N = 11，q = 29。假设 df = 3，因此 f 由 3 个等于 1 的系数和 8 个等于 0 的系数组成。取 dg = 5。并假设 h = g*f ^{-1} mod p，而不是使用 f = 1+pF 的优化。那么我们可能有
你可以在这里检查 f*h = g 。
攻击者想要找到 f，因此他们可以对 df = 3 进行强力搜索。他们可以利用 f 的一些旋转（第一个位置有 1）这一事实来加速这一过程，因此他们只需要在（10选2）可能的位置中搜索f的另外两个非零系数。他们执行的完整搜索是这样的：
向下扫描，您可以看到 g 出现在 45 行中的第 14、26 和 34 行。 （g 出现了 3 次，因为 f 中有 3 个 1，所以 f 的 3 次旋转中前导位置都是 1）。
现在让我们看看中间相遇攻击。攻击者使用公式
so
使用 e[i] 来表示 e 的第 i 个系数，这意味着攻击者知道，
所以攻击者计算了 f1*h 的所有可能值。调用结果列表 {g1}。然后，他们计算 -f2*h，并针对每个结果 g2，查看 g2 是否与现有 g1 相同，或者 g2 与任何 g1 的每个系数差异是否不超过 1。换句话说，
将匹配
这样做，攻击者只需要完成以下工作：
这给出了以下内容。我对列表进行了排序，以便更容易发现匹配项。
您可以看到：
这里有 6 次碰撞，因为有 3 次旋转，其中 1 处于领先位置，并且对于每次旋转，有两种方法来选择其他两个系数。
因此，攻击者必须做大约 45/3 = 15 的工作才能通过暴力搜索找到密钥，并需要大约 10 的工作才能通过中间相遇攻击找到密钥（由于轮换，略小于 10） ，但我手边没有干净的公式）。
有各种优化，但这应该足以让您了解。
到目前为止我还没有处理的一件事是如何减少搜索时间。一种简单的方法就是在进行过程中对结果进行排序。插入条目或查找条目冲突的时间约为 log_2（搜索空间的大小）。或者，以使用更多内存为代价，可以通过为 g1 的前几个系数的每个可能值保留一个块来将此搜索时间降低到一个常数。
希望这有帮助。如果您还有其他问题，请告诉我。
(Full disclosure: I work for Security Innovation and worked for NTRU until SI acquired us)
Warning: Long answer!
Let's look at a toy example: N = 11, q = 29. Let's take df = 3, so f consists of 3 coefficients equal to 1 and 8 coefficients equal to 0. Take dg = 5. And assume that h = g*f^{-1} mod p, rather than using the optimizations that have f = 1+pF. Then we might have
You can check that f*h = g here.
The attacker wants to find f, so they can do the brute force search for df = 3. They can speed this up by taking advantage of the fact that there will be some rotation of f that has a 1 in the first position, so they only need to search the (10 pick 2) possible locations for the other two nonzero coefficients of f. The full search they perform is this:
Scan down there, and you can see that g appears in row 14, 26 and 34 of the 45 rows. (g appears three times because there are three 1's in f, so there are three rotations of f that have a 1 in the leading position).
Now let's look at the meet-in-the-middle attack. The attacker uses the formula
so
Using e[i] to mean the i'th coefficient of e, this means that the attacker knows that
So the attacker calculates all possible values of f1*h. Call the resulting list {g1}. They then calculate -f2*h and for each result g2, they see if g2 is the same as an existing g1 or if g2 differs from any g1 by no more than 1 in each coefficient. In other words,
would match
Doing it this way, the attacker needs only work through the following:
This gives the following. I've sorted the lists to make the matches easier to spot.
You can see that:
There are 6 collisions here because there are 3 rotations with a 1 in the leading position and for each rotation there are two ways to pick the other two coefficients.
So an attacker would have to do about 45/3 = 15 work to find the key with a brute force search and about 10 work to find the key with a meet-in-the-middle attack (slightly less than 10 due to the rotations, but I don't have a clean formula to hand).
There are various optimizations, but this should be enough to give you the idea.
One thing I haven't dealt with so far is how to keep the search time down. A straightforward way to do it is simply to sort the results as you're going along. The time to insert or look for a collision with an entry is about log_2(size of the search space). Alternatively, at the cost of using more memory, it's possible to bring this search time down to a constant by reserving a block for each possible value of the first few coefficients of g1.
Hope this helps. Let me know if you have any more questions.