椭圆曲线

标准的椭圆曲线

$F2^m$

• m: 质数
• $y^2+xy =x^3+ax2+b $
• $a, b ∈ F2^m , b \neq 0$

$F_p$

• $y^2 = x^3 + ax + b$
• $a, b ∈ F_p$
• $4a^3 + 27b^2(mod p) \neq 0$

点加法

有限域上的有理点

$F_{2^m}:E(x,y) = y^2 + xy − x^3 − ax^2 − b$
$F_p : E (x , y ) = y^2 − x^3 − ax − b$
$E(F_q) = {(x,y) | x,y ∈ Fq,E(x,y) = 0}\cup{O} $ //E(F_q)：椭圆曲线方程哪到Fq上去解
O: the point at infinity
$F_{2^m}: |E(F_q)| = 2×大素数 or 4×大素数$
$Fp: |E(Fq)| =大素数

椭圆曲线上的离散对数问题(ECDLP)

P的阶是一个大素数n
d: 随机数 $0 \leq d < n$
Q=[d]P //找一个点算d倍

椭圆曲线上的离散对数问题:
椭圆曲线上的点p，p为阶点，n是p的阶，n个p加起来是无穷远点，随机找一个d，把p个d加起来，得q，把d做二进制展开，可以很快算出q，把q算出来后，知道pqn还有椭圆曲线方程，唯一不告诉的是d，要去计算d。
当n为很大的数是，已知p和q很难算出d（点乘）

公共信息：P，Q
如何在多项式时间内计算d？

点加公式:$F2^m$

• O+O=O //无穷远点加无穷远点等于无穷远点

• 对于所有$(x,y)∈E(F_{2^m})$有限的有理点,(x,y)+O=O+(x,y)=(x,y)//可交换

• 对于所有$(x,y)∈E(F_{2^m})$\ {O},(x,y)+(x,x+y)=O,i.e. //−(x,y)=(x,x+y)

• $P_1+P_2=P_3$

• $P_1 \neq O,P_2\neq O,P_3 \neq O$

• $P_1=(x_1,y_1),P_2=(x_2,y_2),P3=(x_3,y_3)$

点之间的加是定义的抽象的加，系数的加是有限域里面的加

$P1 \neq P2$

• $λ = (y_2 + y_1)/(x_2 + x_1) $//λ是斜率
• $x_3 =λ^2 +λ+x_1 +x_2 +a $
• $y_3 = λ(x_1 + x_3) + x_3 + y_1$
  P1 = P2
• $λ = x_1 + y_1/x_1$
• $x_3 = λ^2 + λ + a$
• $y3 = x_1^2 + (λ + 1)x_3$

加点公式：Fp

O+O=O
所有$(x,y)∈E(F_p)$\ {O},(x,y)+O=O+(x,y)=(x,y)
所有$(x,y)∈E(F_p)$\ {O},(x,y)+(x,−y)=O,i.e.,
−(x, y) = (x, −y)

$P_1+P_2=P_3$
$P_1\neq O,P_2\neq O,P_3 \neq O$
$P_1=(x_1,y_1),P_2=(x_2,y_2),P3=(x_3,y_3)$

$P1 \neq P2$

• $λ = (y_2 − y_1)/(x_2 − x_1) $
• $x_3 = λ^2 − x_1 − x_2$
• $y_3 = λ(x_1 − x_3) − y_1$
  $P1 = P2$
  $λ = (3x_1^2 + a)/(2y_1) $
  $x_3 = λ^2 − 2x_1$
  $y_3 = λ(x_1 − x_3) − y_1$

椭圆曲线Diffie-Hellman密钥协商（ECDH）

Alice，Bob
公共参数：E：曲线，Fq有限域，G点∈E（Fq）{O}，n是G的阶，n是一个大素数 //e、g、n可以公开
Alice：选择x←−Zn，计算X=[x]G，并将X发送给Bob,//算G的x倍
Bob：选择y←−Zn，计算Y=[y]G，并将Y发送给Alice
Alice：计算$K_a=[x]Y（=[xy]G）$//Alice的密钥
Bob：计算$K_b=[y]X（=[xy]G）$
$K_a=K_b$

椭圆曲线相比有限域里离散对数好处：效率更高、传输更少，更节省计算时间和带宽
xy数据规模小，传的快

CDH和DDH

CDH：计算型Diffie-Hellman问题
DDH：决策型Diffie-Hellman问题
攻击者：[x]G，[y]G //xy随机
目标：计算[xy]G

E/Fq，G，n //椭圆曲线
CDH:,给定[x]G，[y]G，不可能在（概率）多项式时间内计算[xy]G。 //xy攻击者不知道
DDH：给定[x]G，[y]G，[z]G，不可能在（概率）多项式时间内区分（[x]G，[y]G，[xy]G）和（[x]G，[y]G，[z]G）。 //xyz攻击者不知道
DDH是困难的⇒CDH是困难的 //cdh更难一些，因为要算，ddh只需要区分，ddh容易的都做不出来，cdh一定做不出来，ddh很有用，

中间人攻击

Alice, Bob, Eve
公共参数: E /Fq , G ∈ E (Fq ) \ {O }, [n]G = O , n一个大素数
Alice: 选择 x ←− Zn, 发送 X = [x]G to Bob (Eve)
Eve: 选择 e1 ←− Zn, 发送 E1 = [e1]G to Bob
Bob: 选择 y ←− Zn, 发送 Y = [y]G to Alice (Eve)
Eve: 选择 e2 ←− Zn, 发送E2 = [e2]G to Alice
Alice: 计算 $K_a = [x]E_2(= [xe_2]G)$
Bob: 计算$ K_b = [y]E_1(= [ye_1]G)$
Eve: 计算 $K_1 = [e_2]X(= [xe_2]G), and K_2 = [e_1]Y(= [ye_1]G)$
$K_a =K_1,K_b =K_2$

a协商出来的密钥ka和攻击者的k1是一样的，b的密钥kb和攻击者的k2是一样的，a在传消息的时候没有对身份进行认证。防止：做身份认证。

认证的Diffie-Hellman密钥协议

• （MQV）
  公共参数：E/Fq，G∈E（Fq）{O}，[n]G=O，n是一个大素数，h（余因子，1，2，4）//
  Alice:私钥a∈Z∗n，公钥A=[a]G //A和a来做认证
  Bob:私钥b∈Z∗n，公钥B=[b]G
  
  R=（x，y）∈E（Fq）{O}，$R=（xmod2^L）+2L$

Alice：选择x←−Zn，计算X=[x]G，$S_a=x+a\bar{X}$，并将X发送给Bob。 //a是私钥,$\bar{X}$是X的横坐标前128bit取出来，加1bit的1，变成有限域中的一个数
Bob：选择y←−Zn，计算Y=[y]G，$S_b=y+b\bar{Y}$，并Y发送给Alice
Alice：计算$K_a=hS_a（y+\bar{Y}B）$//h是因子，Y是个点，$\bar{Y}$是有限域中的一个数，B是Bob的公钥，Ka算出来是个点
Bob：计算$K_b=hS_b（X+\bar{X}A）$

正确性证明

• $K_a = hS_a(Y +\bar{Y}B) = hS_a(yG +\bar{Y}bG) = hS_a(y +b\bar{Y})G = (hS_aS_b)G $
• $K_b = hS_b(X +\bar{X}A) = hS_b(xG +\bar{X}aG) = hS_b(x +a\bar{X})G = (hS_bS_a)G$
• $K_a = K_b$

中间人攻击为什么不会成功：Alice算的时候x、a只有她自己知道，攻击者也不知道公钥B

椭圆曲线Diffie-Hellman问题的比特安全

定理：在曲线族中计算一位椭圆曲线Diffie-Hellman秘密和计算整个秘密一样困难。//只要能算一个bit就能把整个x算出来

椭圆曲线数字签名算法（ECDSA）

比特币用两条曲线做数字签名的
系统参数：

• E/Fq：要使用的有限域和椭圆曲线方程
• G：基点
• n：素数，G的阶，即[n]G=O
• H：加密散列函数

私钥: 0 < d < n
公钥: Q = [d]G
//唯一不公开的是d

签名：

• m：要签名的文件
• k：随机数，0< k < n
• 计算(x1, y1) = [k]G
• 计算$r = x_1 mod n$
• 如果r=0，则从不同的随机k开始
• 计算$s = k^{−1}(H(m) + dr) mod n$
• 如果s=0，则从另一个随机k开始
• 签名：（r，s）
  //签名是两部分，如果n是256bit，r和s也是256bit，整个签名是512bit。短签名方案利用双线性对来做的，可以把签名做到256bit

认证：

• 检查Q是不是在椭圆曲线上
• 检查0 < r < n,0 < s < n
• 计算$w = s^{−1} mod n$
• 计算$u_1 = H(m) · w mod n$
• 计算$u_2 =r·w modn$
• 计算$(x_1, y_1) = [u_1]G + [u_2]Q. $如果$ (x_1, y_1) = O$, 那么签名就无效了。？？？
• 如果$r≡x_1 mod n$，则签名有效，否则无效。

ECDSA的bit安全性

• 对于许多ECDSA签名，k的一些连续位是已知的
• 若干签名：在$\sqrt {log_2^n}$中最多为线性
• 可证明恢复签名者私钥的概率多项式时间算法
• 一些连续位：最高有效位或最低有效位，,$\sqrt {log_2^n}$
• 工具: lattice basis reduction

双线性对

双线性对是形式的映射
$$e : G_1 × G_2 → G_T $$
其中$G_1，G_2$是加法群（点的集合），有同构的关系，$G_T$是乘法群（有限域中的）。

双线性对就是个映射，输入是两个点第一个点来自$G_1$群，第二个点来自$G_2$群，输出变成有限域中的元素

• (双线性)
  1.对于任意$P_1,P_2 ∈G1,Q∈G_2,e(P_1+P_2,Q)=e(P_1,Q)e(P_2,Q). $
  2.对于任意$P∈G1,Q_1,Q_2 ∈G_2,e(P,Q_1+Q_2)=e(P,Q_1)e(P,Q_2).$
• (非退化) 存在 $ P ∈ G1 and Q ∈ G2 such that e(P,Q) / = 1$
• (可计算性) 给一个输入p、q以后，素数e可以很快算出来
• Note: 对于任意 $P ∈ G_1,Q ∈ G_2,a,b ∈ Z, e([a]P,[b]Q)=e(P,Q)^{ab}.$
• //$e([a]P,[b]Q)=e(P,Q)^{ab}$ 表示线性的ab提出来可以做指数运算，椭圆曲线点的离散对数变成有限域中的离散对数

ECDLP → DLP

• E/Fq
• r：素数, r是Fq椭圆曲线上的有理点的个数|♯E(Fq) (♯E(Fq) = |E(Fq)|)
• k: 不能太大，一般10到20 (嵌入次数)
• Fq ⊂Fqk,[Fqk :Fq]=k
• $G_1⊂E(F_{q^{k}),G_2⊂E(F_{q}k}),G ⊂F_{q^k}$
• $|G_1| = |G_2| = |G_T | = r$, 素数

塔特配对

米勒函数:
$(f_{s,P}) = s(P) − ([s]P) − (s − 1)(O)$ //

Ate配对

//比塔特配对效率更高

米勒算法

• $l_{[m]P,[n]P}: the line through [m]P and [n]P $
• $v_{[m+n]P}: the vertical line through [m + n]P$
  

决策Diffie-Hellman问题（DDH）

• $ψ(·):G1到G2是同构的，记ψ(P) = Q$//难度降低，ddh出现问题

• $ψ(P) = Q ψ([a]P) = [a]ψ(P) = [a]Q$

• 一种新的双线性对$\hat{e}: G_1 × G_1 → G_T$

• $\hat{e}(P,P)=e(P,ψ(P))=e(P,Q)$

• $\hat{e}([a]P, [b]P) = e([a]P, ψ([b]P) = e(P, Q)^{ab}$

G1中的DDH很简单 //有双线性对的辅助，能快速的判定

• ([x]P, [y]P, [xy]P)
  $\hat{e}([x]P,[y]P) = e(P,Q)xy,\hat{e}(P,[xy]P) = e(P,Q)^{xy}$//两个值一样
• ([x]P, [y]P, [z]P)
  $\hat{e}([x]P,[y]P) = e(P,Q)xy,\hat{e}(P,[z]P) = e(P,Q)^z$//两个值不一样的可能性非常大

三方的Diffie-Hellman密钥协议

Alice: 私钥 a ∈ Z∗r , 公钥 A = [a]P
Bob: 私钥 b ∈ Z∗r , 公钥 B = [b]P
Charlie: 私钥c ∈ Z∗r ,公钥 C = [c]P
Alice 计算 $K_a = \hat{e}(B,C)^a $
Bob 计算 $K_b = \hat{e}(A, C )^b $
Charlie 计算 $K_c = \hat{e}(A, B)^c$
$K_a = K_b = K_c = \hat{e}(P,P)^{abc} = e(P,Q)abc$

短签名方案

系统参数：

• E/Fq：具有合适配对的椭圆曲线
  e : G1 × G2 → GT
  |G1| = |G2| = |GT| = r, 素数
  G1 =< P >, G2 =< Q >
  H: 加密哈希函数, {0,1} → G1//公开

私钥和公钥：
私钥: 0 < d < r
公钥: V = [d]Q //公钥变大，不好的点

签名:（私钥签名）

• m ∈ {0, 1}: 要签名的文件
  计算R = H(m) ∈ G1
  计算σ = [d]R
  σ = (s,y) //σ也是G1中的点
  签名: s //σ的横坐标

验证:（公钥验证）

• 计算$\tildeσ=(s,y) E(Fq)$中的y（正负都行）.如果y不存在，则签名不合法。
  计算$\tildeσ$ 的阶是不是r. 如果不是，签名不合法。
  计算R = H(m) ∈ G1
  看$e(\tildeσ,Q) = e(R,V) 或 e(\tildeσ,Q)^{−1} = e(R,V)$是不是至少有一个正确. 如果是，则输出有效；否则，输出无效。
  //双线性对前面的d可以放到后面

双线性Diffie-Hellman假设（BDH）

双线性对： $\hat{e}: G1 × G1 → GT$

攻击者: [a]P, [b]P, [c]P
目标：计算$\hat{e}(P, P)^{abc}$

基于身份的加密：IND-CPA

• 双线性对 $\hat{e}: G1 × G1 → GT$
  |G1| = |GT| = r, 大素数//元素个数
  G1 =< P >//G1里面有个p
  s ∈ Z∗r , $P_{pub}a = [s]P$ //s是私钥，P公钥
  密码哈希函数 H1 : {0, 1}∗ → G1 \ {O } //G1当中除了无穷远点意外的其他点
  密码哈希函数 H2 : GT → {0, 1}m //GT当中的元素变成长为m的{0, 1}比特算法
  //哈希函数可以公开，唯一不公开的是s

提取

• $ID∈{0,1},Q_{ID} =H_1(ID)∈G_1\ {O} $//H1把ID变成了一个点
  私钥