密码学 | 6.4 椭圆曲线密码学

密码学 1年前 (2023) admin
283 0 0
密码学 | 6.4 椭圆曲线密码学

6.4 Elliptic Curve Cryptography

How Hard Is the ECDLP

我们在 5.4 一节介绍的碰撞方法可以在所有的群中使用。例如在椭圆曲线  。那么为了解出椭圆曲线下的离散对数问题: ,Eve 随机选择 1 至  之间的整数  和 ,并构造两个列表。

当他在两个列表中发现相同元素(碰撞)时,她就能解出 ,因为  那么有 。如我们在 5.4 一节所述,当  是一个稍大于  的数,,此时我们有很大的概率找到碰撞。
这样最基础的算法需要大量的存储空间,不过我们也不难在椭圆曲线上运用 Pollard’s  这样几乎不需要额外存储空间的算法。但不论如何,我们都是有算法可以在  步内解决椭圆曲线  上的 ECDLP 的。
前面我们已经介绍过很多更快速的解决  中的离散对数问题,如 3.8 一节介绍的 index calculus 算法仅有亚指数的复杂度,即复杂度是 。而我们之所以在密码学中使用椭圆曲线就是因为在椭圆曲线的代数结构中目前还没有发现诸如 index calculus 的解决 ECDLP 的快速算法。下面这一事实非常重要,值得强调
目前已知最快的解决  下 ECDLP 的算法大约需要  步
因此,ECDLP 要比 DLP 困难。不过回想一下,在 DLP 中有一些素数  会使得 DLP 问题变得非常容易,比如当  是一系列小素数的乘积的时候,那么使用 Pohlig-Hellman 算法就能够快速的解出DLP,所以相应的,也有一些椭圆曲线和素数会使得  下 ECDLP 变得相对容易。我们将在 6.9.1 一节中讨论这些在构建安全的密码学系统时需要避免的特殊的情况。

Elliptic Curve Cryptography

终于到了将椭圆曲线应用于密码学的时候了。我们将从最简单的 Diffie–Hellman 密钥交换开始,它只需要用椭圆曲线  的离散对数问题代替有限域  的离散对数问题。然后,我们将描述 Elganam 公钥密码系统和数字签名(DSA)在椭圆曲线下的变种。

6.4.1 Elliptic Diffie–Hellman Key Exchange

首先 ,Alice 和 Bob 先协商确定一条曲线  和曲线上的一个点 。Alice 选择一个秘密整数 ,Bob 也选择一个秘密整数 ,然后他们分别计算

接着他们互换 。Alice 使用她的秘密整数计算 ,Bob 同样计算 ,此时他们都拥有了共享密钥:。后续他们就可以将这个共享密钥用于对称密码系统中。
表 6.5 总结了椭圆曲线下的 Diffie-Hellman 密钥交换。
密码学 | 6.4 椭圆曲线密码学
例 6.19 Alice 和 Bob 都选择使用以下的素数、椭圆曲线、点

Alice 和 Bob 选择各自的秘密整数 ,然后他们分别计算

Alice 将  发送给 Bob, Bob 将  发送给 Alice,最后他们分别计算

Bob 和 Alice 都计算出了  ,接着他们会丢弃  坐标的值,使用值  作为最后真正的共享密钥值。
那么对于 Eve 来说,想要获得这个共享密钥值,一种方法就是解决 ECDLP 问题,这样他就可以获取 ,然后计算 。当然,也有可能存在某个方法 Eve 不需要解决 ECDLP 问题就能够获取密钥值。
定义 设  为有限域上的椭圆曲线,并有点 。那么 Elliptic Curve Diffie–Hellman Problem 即为根据已知的  计算值 

注 6.20 椭圆曲线的 Diffle-Hellman 密钥交换需要 Alice 和 Bob 交换曲线上的点。曲线上的一个点  包含两个坐标 ,其中  时有限域  上的元素,所以 Alice 就需要给 Bob 发送两个数字。然而,这两个数字并不是相互独立的,他们之间有如下关系

注意到 Eve 是知道 A 和 B 的,所以如果她能够猜到正确的 ,那么对于  就只有两种可能了,而实际上计算这两种可能并不是什么难事。

对于 Alice 来说,她没必要将  的两个坐标都发给 Bob ,因为  坐标并没有包含多少有用的消息。如果 Alice 只给 Bob 发送  坐标,那么 Bob 能在两个  坐标中选择一个。如果他选择了正确的 ,那么它使用的就是 ,如果他选择了错误的 (即 ),那么它使用的就是 。无论如何,Bob最后计算将是  之一。

同样的,Alice最后计算的也将是  之一。最后,Alice 和 Bob 都是用  坐标作为共享秘密值进行计算,因为无论选择哪个  的值都是一致的。

例 6.21 Alice 和 Bob 继续沿用 例 6.19 协定好的参数:

这一次她想发送给更少的数据给 Bob。Alice 和 Bob 选择各自的秘密值:,然后他们计算

然后,这一次 Alice 只发送  给 Bob,Bob 只发送  给 Alice。
Alice 将  带入  的式子中计算

Alice 需要计算  的平方根。这并不难,尤其当  的时候。根据命题 2.26,我们有  就是  在模  下的平方根,所以 Alice 计算

于是 Alice 计算出了和 Bob 同样的点 ,然后她计算 
同样的,Bob 也将  带入  的式子中并计算

Bob 使用点 ,这并不是 Alice 使用的点 。他计算 。Bob 和 Alice 最终计算的两个点在  中互为负数,但都是正确的,因为共享的秘密值是两个点的横坐标 
       

原文始发于微信公众号(山石网科安全技术研究院):密码学 | 6.4 椭圆曲线密码学

版权声明:admin 发表于 2023年4月28日 上午11:26。
转载请注明:密码学 | 6.4 椭圆曲线密码学 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...