ECC-奇异曲线

在几何中,对于一条曲线如果他是奇异的,那么该曲线至少有一个奇异点满足该点处的偏导数同时为零(该点处切线不定)。若一个曲线存在奇异点那么这个曲线一定是奇异曲线。

在ECC中对于常见的 Weierstrass 曲线可以用判别式判定该曲线是否奇异

$$ \Delta=-16(4a^3+27b^2) $$

当判别式为0时,该曲线为奇异曲线。当判别式不为0时,该曲线为非奇异曲线。奇异曲线在ECC中是应该绝对不允许使用的。下属奇异曲线均指椭圆曲线中的奇异曲线。

对于奇异曲线,有两种类型分别是尖点曲线自交点曲线。有这样的判断方式

对 $x^3+ax+b$ 进行因式分解,若有一个三重根则为尖点曲线,若有一个二重根则为自交点曲线。

尖点曲线

$$ y^2=x^3 $$

该曲线就是尖点曲线,可以注意到这个曲线在原点处有一个奇异点,也可以称之为尖点cusp

将原式转化为参数方程,并令$P=(t_1^2,t_1^3),Q=(t_2^2,t_2^3)$利用椭圆曲线上的加法原理得到$(P+Q).x=k^2-t_1^2-t_2^2$带入曲线方程化简得到$(P+Q).x=\frac{t_1^2t_2^2}{{t_1+t_2}^2}$,于是就能得到点加运算后的值$P+Q=R=(\frac{t_1t_2}{t_1+t_2}^2,\frac{t_1t_2}{t_1+t_2}^3)$,于是就可以构造处这样的映射关系$f(x,y)\to \frac{x}{y}$将原曲线上的加法运算同构映射到整数上的加法运算,有如下的特性

$$ \begin{align} &f(P+Q)=f(P)+f(Q)\\ &f(xP)=xf(P) \end{align} $$

于是就可以将困难的ECDLP问题转化到有限域上的乘法问题,就能快速解决了。

自交点曲线

$$ y^2=x^3-3x+2 $$

该曲线就是自交点曲线,可以注意到这个曲线在(1,0)处有一个奇异点,也可以称之为自交点node

和尖点曲线一样,我们试图对自交点曲线进行类似的同构映射以便将ECDLP转化。

首先可以通过图像的平移,将曲线$y^2=x^3+ax+b=(x+m)^2(x+n)$平移到自交点为原点处,同时受限于自交点自身的性质,所以此时的曲线方程一定是形如$y^2=x^3+Ax^2$,容易得到$A=n-m$,然后考虑一条过奇异点的直线$y=kx$,于是就可以利用k写出曲线的参数方程

$$ \left\{\begin{align} &y=kx\\ &y^2=x^3+Ax^2 \end{align}\right. \Rightarrow x=A-k^2 $$

得到奇异点处的两条切线斜率为$\pm \sqrt{A}$,然后构造这样的映射关系,将椭圆曲线上的加法运算同构映射到整数上的幂运算。

$$ f(x,y)\to \frac{y-\sqrt{A}(x+m)}{y+\sqrt{A}(x+m)} $$

该映射满足以下关系

$$ \begin{align} &f(P+Q)=f(P)\cdot f(Q)\\ &f(xP)={f(P)}^x \end{align} $$

最终将ECDLP问题转化为DLP问题

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇