试图理解椭圆曲线中的p-进位对数映射
我遵循“椭圆曲线理论导论”http://www.math.brown.edu/johsilve/Presentations/WyomingEllipticCurve.pdf的幻灯片，但是我很难理解ECDLP是如何在异常曲线中解决的。
幻灯片上写着：“如果#E(Fp) = p，则有一个”p进位对数映射“，它给出了一个容易计算的同态对数p-adic: E(Fp) -> Z/pZ，在Z/pZ中很容易解决离散对数问题，所以如果#E(Fp) = p，则可以在O(log P)时间内求解ECDLP。”
但我很难理解一些概念。据我所知，椭圆曲线E(Fp)与整数Z/pZ的环之间存在同态。我可能错了，但据我所知，这种同态是映射phi，它满足这些性质。
- phi(O) =0
- phi(P + Q) = phi(P) + phi(Q)
- phi(kP) = k.phi(P)
我不明白的是，为什么在Z/pZ中很容易解决离散对数问题。Diffie密钥交换不是基于计算离散对数的难度吗？
但是，即使假设解决Z/pZ中的DLP很容易，如果我有DLP的解决方案，如何才能得到ECDLP的解决方案呢？
最后，有没有人知道我能读到更多关于这方面的书籍或报纸？我试着找，但什么也没找到
回答 1
Cryptography用户
发布于 2023-03-01 03:16:01
我不明白的是，为什么在\mathbb{Z}/p\mathbb{Z}中很容易解决离散对数问题。Diffie密钥交换不是基于计算离散对数的难度吗？
在加性群\mathbb{Z}/p\mathbb{Z}中，DLOG等价于计算模逆，这是有效的。我高度怀疑p-adic对数的目标是这个加性组，如
- 幻灯片对乘法组使用不同的表示法，
- 你说得对--如果它是乘法群，DLOG就不容易了，而且
- 对数将乘法转化为加法，因此对数馀域中的组运算实际上应该是加法。
但是，即使假设在\mathbb{Z}/p\mathbb{Z}中解决DLP很容易，如果我有DLP的解决方案，我如何才能得到ECDLP的解决方案呢？
一般情况下，给定一个有效的可计算内射同态\phi: G\to G'，如果G'中DLOG容易，则在G中容易。这是因为，考虑到t = g^a，我们可以
- 计算\phi(t) = \phi(g^a) = \phi(g)^a
- 计算\phi(t)的离散对数以恢复a。
如果\phi不是一个注入，您可能会遇到一些问题/不得不做一些更多的工作，但是这样的同态的存在对攻击者是有益的。我认为基于配对的密码学有更多的例子，如果你对其他的例子感兴趣，但我自己不知道细节。
https://crypto.stackexchange.com/questions/104435
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号