MOV攻击到底是什么?它是如何工作的?它的用途是什么?

这里已对其进行了简要说明,我想知道它的用途/其用途是什么? 。

#1 楼

如果可以解决离散对数问题,即基于给定的点$ P $和$ rP $,找到整数$ r $,则大多数基于椭圆曲线的密码系统都可以被破坏。

MOV攻击使用双线性配对,(大致而言)是一个函数$ e $,它将椭圆曲线$ E(\ mathbb {F} _q)$中的两个点映射到有限域$ \ mathbb {F} _ { q ^ k} $,其中$ k $是与曲线关联的嵌入度。双线性意味着对于点$ P,Q $ $ e(rP,sQ)= e(P,Q)^ {rs} $。因此,如果要计算$ rP $的离散对数,则可以为任何$ Q $计算$ u = e(P,Q)$和$ v = e(rP,Q)$。由于双线性,我们有$ v = e(P,Q)^ r = u ^ r $。现在,您可以求解$ \ mathbb {F} _ {q ^ k} $中的离散对数(给定$ u ^ r $和$ u $,找到$ r $),以便求解椭圆曲线上的离散对数!

通常,嵌入度$ k $非常大(与$ q $大小相同),因此将离散对数传递给$ \ mathbb {F} _ {q ^ k} $ won'不能帮助你。但是对于某些曲线,嵌入度足够小(特别是超奇异曲线,其中$ k <= 6 $),这可以启用MOV攻击。例如,具有256位$ q $的曲线通常可提供128位安全性(即可以使用$ 2 ^ {128} $步数进行攻击);但是如果它的嵌入度为$ 2 $,那么我们可以将离散对数映射到$ \ mathbb {F} _ {q ^ 2} $字段,该字段仅提供60位安全性。

在通过不使用嵌入度小的曲线,可以简单地避免攻击。标准化曲线是安全的。由于配对也有许多构造性应用,因此可以谨慎选择在攻击椭圆曲线本身或映射有限域的成本相同的情况下的曲线。

评论


$ \ begingroup $
实际上,X9.62(ECDSA的标准)在生成自己的曲线时指定了一些验证,包括验证嵌入度$ k $大于$ 100 $。如果要处理大小为$ n $(素数)的子组,该子组划分曲线顺序,则嵌入度为最小的$ k \ geq 2 $,因此$ n $除以$ q ^ k-1 $。然后,足以检查$ n $不会将所有值$ k $的$ q ^ k-1 $从$ 2 $除以$ 100 $。
$ \ endgroup $
–托马斯·波宁(Thomas Pornin)
2012年2月18日在16:20

$ \ begingroup $
在这种情况下,嵌入度是什么意思?
$ \ endgroup $
–Venkatesh
17年4月11日下午5:02

$ \ begingroup $
@Venkatesh嵌入度是椭圆曲线的一个属性。如Thomas所说,它是最小的$ k \ ge 2 $,因此$ n $(曲线的顺序,即曲线中的点数)除以$ q ^ k-1 $(其中$ q $是大小)基础有限字段的值)。
$ \ endgroup $
– Conrado
17年4月11日在11:19

$ \ begingroup $
@ConradoPLG您能解释一下解决ECDLP的Frey-Ruck攻击吗?
$ \ endgroup $
–Venkatesh
17年4月12日在6:24

$ \ begingroup $
与在$ E(\ mathbb {F} _q)$上获得两点相反,像Weil Pairing这样的可有效计算的双线性映射将不得不从$ E(\ mathbb {F} _q )$和一组,例如$ E(\ mathbb {F} _ {q ^ 2})$。否则,配对将退化。 Weil的$ e(P,P)= 1 $,这意味着当Q是P的倍数时,$ e(P,Q)= 1 $。求解$(1,1 ^ x)$的离散对数不会很不幸地揭示了x。我们实际上并不在乎实际的Q点本身,但重要的是不要将它放在$ E(\ mathbb {F} _q)$中
$ \ endgroup $
–尼古拉斯·皮皮托尼
18/12/5在5:17

#2 楼

MOV代表作者Albert Menezes,冈本达明(Tatsuaki Okamoto)和斯科特·凡斯通(Scott Vanstone),他写了将椭圆曲线对数简化为有限域中的对数。该方法已由Gerhard Frey和Hans-GeorgRück广泛推广。

与数学概念一样,没有什么比了解自己的数学更好的理解方法了。但是,可以认为该方法围绕着魔术函数的存在展开,该魔术函数以椭圆曲线点作为输入并输出有限域的元素。现在可以在容易得多的有限域中解决离散对数问题。
现在要考虑的问题是,对于所有曲线,这些函数是否存在以及有限域到底有多大。魔术函数与Weil和Tate配对紧密相关,后者在许多非常新颖,令人兴奋且富有成果的加密领域中都独具魅力,并得到广泛使用。