似乎有类似这样的资源,还有一些介绍,这些讨论通常讨论椭圆曲线以及如何使用它们。但是我想知道的是,为什么这些特定的曲线在密码学中如此重要,而不是让您可以在某个组上进行修改的任何其他多项式度数\\ gt $ 2。似乎一旦应用了模数,其他函数类型也应该被接受。

仅查看气泡与曲线的关系似乎更加不直观:


由于存在其他曲线(可以说是正弦波到$ x ^ 3 + x $甚至是某些形状不规则的轮廓),所以可以完成这项工作。似乎它们会提供更多的表面积以在$ \ mathbb {Z} _p $中获得更大的空间,或者实际上是从任意$ P $和$ Q $连接线的更多可能组合,从而获得$ R $。从某种泡沫(似乎不必要地减少了可能的组合)开始,直到某种限制(在图形上),然后使用模数来实现离散对数问题。

对不起,如果这似乎是有点天真,我正在尝试编写一个实现,只是为了完全理解它,即使那意味着问一些理所当然的事情。从“ A想要与B对话”一直到“现在E可以”,也许只是简单地讲一个简单的例子(我搜索过的大多数例子不过是什么),仅需几句话便会很有帮助。 t在A和B之间收听”。

编辑:

因此,这似乎是有限域上的椭圆曲线的版本:



是的,看起来很随意。但是我仍然没有真正看到为什么它们是唯一具有密码学意义的方程式。很难想象,如果仅采用其他一些更高阶的方程式并应用模数(放置在组中),那么似乎您会得到相对随机的东西似乎也很有意义。

#1 楼

椭圆曲线不是唯一具有组结构或在密码学中使用的曲线。但是,它们在安全性和效率之间的平衡点要比其他所有点都好。

例如,圆锥截面(二次方程式)确实具有定义明确的几何加法则:给定$ P $和$ Q $,通过它们追踪一条线,并通过身份元素追踪一条平行线。这是最著名的圆锥曲线之一的方便图片,单位圆$ x ^ 2 + y ^ 2 = 1 $:



如果使用标识元素设为$(1,0)$,则得到非常简单的加法公式(取模您喜欢的素数)

$$(x_3,y_3)=(x_1x_2-y_1y_2,x_1y_2 + x_2y_1)$ $

这比常规的椭圆曲线公式快得多,为什么不使用它呢?嗯,圆锥曲线的问题在于,该组中的离散对数不强于基础场上的离散对数!因此,我们将需要非常大的键,例如素数域离散对数,而没有任何优势。不好。

因此,我们继续进行椭圆曲线,该椭圆曲线不会降低基础字段的对数。

但是,我们可以将椭圆曲线概括为更高的学位。实际上,当遵守$ g> 1 $并有一些限制时,

$$ y ^ 2 = x ^ {2g + 1} + \ ldots $$
称为超椭圆曲线,我们也可以对其进行处理。但是对于这些曲线,没有像圆锥曲线和椭圆曲线那样添加点的良好几何规则。因此,我们不得不在这些曲线的Jacobian组中工作,这不再是点的组,而是除数(如果有任何意义,它们就像点的多项式)。当对素数$ p $取模时,该组的大小为$ \ approx p ^ g $。

超椭圆曲线确实具有一些优点:由于组大小远大于素数,因此对于相同的密码强度,我们可以对较小的素数进行模运算。但是最终,当$ g $开始增长时,超椭圆曲线也会成为索引计算的对象。实际上,\ {2,3 \} $中只有$ g \,即度为$ 5 $或$ 7 $的多项式提供与椭圆曲线相似的安全性。正如沃森所说,为了加重侮辱性,随着$ g $的增加,加法公式也变得更加复杂。

超椭圆曲线也有进一步的概括,例如超椭圆曲线$ C_ {a, b} $曲线,依此类推。但是也有类似的评论:它们根本没有在速度或安全性方面超过椭圆曲线。

评论


$ \ begingroup $
因此,椭圆曲线就像连续方程组中的最佳点一样,可能在组中使用。该连续体似乎范围从“计算成本太高”(超级/超级椭圆曲线)到“ DLP不够困难”(将P和Q放在圆锥截面或圆上)。尽管您的圆锥曲线让我想知道为什么$ R ^ {3} $中的球体不起作用,但可能太昂贵了。 +1并被接受。
$ \ endgroup $
– stackuser
2013年11月6日15:55

$ \ begingroup $
一个球体($ x ^ 2 + y ^ 2 + z ^ 2 = 1 $)仍然不安全;但是,如果将两个二次曲面(即由二次多项式定义的曲面)相交,则实际上可以得到一条安全曲线,它猜出什么是椭圆曲线! Jacobi相交曲线就是一个例子。
$ \ endgroup $
–塞缪尔·内维斯(Samuel Neves)
2013年11月8日在2:01



#2 楼

椭圆曲线具有许多不错的功能,使其非常适合加密。一个人可以写一本关于该主题的书(有些人会写),所以我将重点介绍几点。


有限域上的椭圆曲线上的点组成一个组。您提到的想法并非如此。
要离散登录其中的许多EC组非常困难。实际上,在这些组中没有子指数算法可以解决DLP,就像我们经常在加密中使用的其他组(例如$ \ mathbb {Z} _p $)一样。这意味着我们具有较小的密钥大小和更快的操作。
椭圆曲线已成功应用于密码分析问题,例如分解。
我们已经能够用椭圆曲线做其他一些很酷的事情,例如我们在其他任何场合都没有遇到过的配对。


评论


$ \ begingroup $
1.如果应用某些模数,任何曲线都不能形成群吗?除非$ a \ lt 0 $和$ b \ lt 1 $,否则许多ec甚至都没有泡沫,因此在这种情况下,似乎就像其他任何波浪线一样。
$ \ endgroup $
– stackuser
13年5月5日在2:37

$ \ begingroup $
您看到的看起来不错的EC超出了实际范围。有限域上的椭圆曲线看起来根本不是那样。实际上,它们看起来非常随机,这是它们适用于密码学的另一个原因。有限域上的AFAIK其他函数不组成一个组。
$ \ endgroup $
–mikeazo
13年5月5日在3:03

$ \ begingroup $
好吧,在看到它在有限域(例如从毛毛虫到蝴蝶)的前后转换之后,现在更有意义了。我添加了一个EDIT,以使我仍然不太了解为什么EC如此特别。似乎将模数(放置在组中)与大多数具有2个较高度变量的方程一起使用,将产生可比较的效果,以创建足够随机的东西用于加密目的。
$ \ endgroup $
– stackuser
13年5月5日,下午3:46

$ \ begingroup $
@stackuser虽然您可以使用类似的几何结构(例如椭圆曲线)为大多数类型的曲线定义某种“加法”,但并不能自动假定此操作是关联的并且具有中性和反元素,即组成一个小组。
$ \ endgroup $
–PaŭloEbermann
13年5月5日在7:31

$ \ begingroup $
既不指向自己,也不指向其他功能。 Paulo Ebermann所说,操作可以做到这一点,并且该操作可以具有创造性,但要遵循关联性,中性和逆性。
$ \ endgroup $
–Vadym Fedyukovych
18-2-7在23:17

#3 楼

您没看错:给定$ V $的任何变体,我们可以将Jacobian $ J(V)$形成为阿贝尔变种,尤其是可以使用Diffie-Hellman问题的阿贝尔群。但是,这样做有很多细节。首先,有必要计算雅可比阶数。我们只知道如何对椭圆曲线执行此操作。其次,对于较高的属,对于较低的属,有各种减少。最后,种类(即程度)越大,进行这些计算所使用的公式越复杂。 《椭圆和超椭圆曲线密码学手册》是有关这些问题的绝妙参考。