椭圆曲线上pollards袋鼠攻击的迭代
我想了解椭圆曲线上的Pollard袋鼠攻击。我发现这个波拉德袋鼠对椭圆曲线群的攻击 Q/A非常有用，但不完整。这些帖子为攻击提供了一个很好的算法：
def pollardKangaroo(P, Q, a, b, N):
# Tame Kangaroo Iterations:
xTame, yTame = 0, b * P
for i in range(0,N):
xTame += Hash(yTame)
yTame += Hash(yTame) * P
# yTame == (b + xTame) * P should be true
# Wild Kangaroo Iterations:
xWild, yWild = 0, Q
wildLimit = b - a + xTame
while xWild < wildLimit:
xWild += Hash(yWild)
yWild += Hash(yWild) * P
if yWild == yTame: return b + xTame - xWild
# No result was found:
return None我在纸上做了算法，它起了作用。P和Q是ECDLP：Q = n\cdot P中的点。a和b给出了攻击搜索n的间隔。因此，该算法只有在n \in [a,b]的情况下才能成功。现在我遇到了两个问题:哈希函数和参数N没有被解释/定义。
我的问题：
- 哈希函数仅仅是一个半随机生成器，并且可以非常简单(例如，H(point) =x+y+ 1)吗？
- N究竟是如何定义的？N应该是什么价值？N的值如何影响算法？
回答 1
Cryptography用户
发布于 2020-08-13 10:00:01
我的第一次尝试：
所以我在曲线上做了一些测试，E: y^2 = x^3 + x^2 + x和F_{131}，以及P = (42,69)和Q = 42 \cdot P。我对不同N的结果：
我的结果是一个不同的哈希函数：
这让我很困惑，因为我没有看到针对不同N的任何结果，我认为只有散列函数是用于优化的。但真正的答案要复杂得多。我的资料来源是维基百科，椭圆和超椭圆曲线密码学手册和原纸。
答案：
- 是的，散列函数是半随机数发生器.但这对算法来说是很重要的！算法的运行时间和故障率取决于散列函数.如果结果集变小，运行时就会变得非常糟糕。如果结果集太大，故障率就会增加。有了手册，我得到了结果集\{ 1,2,..., \sqrt{(b-a)}/2 \}，它运行得很好。
- 我在原始论文中找到了答案：N定义了故障率。当N较低时，故障率较大。这就是为什么我没有看到情节发生重大变化的原因。提示:我仍然不知道，如果我必须存储所有的中间结果驯服袋鼠是否。(如果我找到答案，我会编辑这篇文章)
新代码：
手册是代码优化的主要来源。这个python代码与SageMath一起使用：
hashValue = 0
def Hash(P):
if P == 0: return 1
return int(P.xy()[0]) % hashValue +int(P.xy()[1]) % hashValue+ 1
def pollardKangaroo(P, Q, a, b):
global hashValue
hashValue = math.ceil(sqrt((b-a))/2)
# Tame Kangaroo Iterations:
xTame, yTame = 0, b * P
for i in range(0,math.ceil(0.7*sqrt(b-a))):
xTame += Hash(yTame)
yTame += Hash(yTame) * P
# yTame == (b + xTame) * P should be true
# Wild Kangaroo Iterations:
xWild, yWild = 0, Q
for i in range(0, math.ceil(2.7*sqrt(b-a) ) ):
xWild += Hash(yWild)
yWild += Hash(yWild) * P
if yWild == yTame: return b + xTame - xWild
# No result was found:
return 0这现在总是为野生袋鼠(同样的曲线和基点)生成一个相当合理的地块：
提醒：
该算法有很大的改进。我的算法不完美！我的主要目标是了解哈希函数和迭代次数对算法的影响。和!如果我能找到一些更重要的信息，我会编辑这篇文章。
https://crypto.stackexchange.com/questions/83226
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号