ecc
doc
Technical Guideline TR-03111 Elliptic Curve Cryptography
Elliptic Curve Cryptography: ECDH and ECDSA
Cryptography - The ElGamal Public key System (Public key encryption from Diffie Hellman)
Elliptic Curve Public Key Cryptography
CPSC 467: Cryptography and Computer Security
An Introduction to the Theory of Elliptic Curves
Elliptic Curve Integrated Encryption Scheme (ECIES)
A Survey of the Elliptic Curve Integrated Encryption Scheme
Elliptic Curve Integrated Encryption Scheme (ECIES)
A Comparison of the Standardized Versions of ECIES
使用KA(key agreement)协商一个密钥S，使用KDF基于S生成会话密钥，其实基本上就是ECDH。
会话密钥用于ENC对称加密，同时还有MAC函数, HASH函数。
因此plaintext长度基本不受限。
ec elgamal
Elgamal Encryption using Elliptic Curve Cryptography
相当于在ec上的elgamal，此时plaintext长度受限于group size。与rsa类似，计算时要mod N。
实例见 Crypt::PK::ECC
ec point
如果是ec point变换，则受限于ec point的个数。本原根。
ecdsa
Elliptic Curve Cryptography: ECDH and ECDSA
malleability
(r, s) , (r, -s) 均可校验成功，签名构造。
low-s value 可修复该漏洞。
Verification Without Hash Pre-Image
可根据public key 任意构造(r, s, h)
因此，校验必须带原message，而非只校验h=hash(message)
RFC6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)
sony ps3 的案例是没有按算法要求生成随机数k。
RFC6979 的处理是，用SP800-90A的HMAC_DRBG随机数生成器生成k，其中，熵值用私钥(x)，nonce用hash(message)。
RFC8032 EdDSA的做法也类似。
Deterministic ECDSA and EdDSA Signatures with Additional Randomness
完全确定的签名，又容易被side-channel and fault injection attacks，又把random加回去：Deterministic ECDSA and EdDSA Signatures with Additional Randomness
思路是 random + private key + message 三者结合，搞出随机数，或者签名参数
curves
RFC7748: Elliptic Curves for Security
SafeCurves: choosing safe curves for elliptic-curve cryptography
ECCHacks: A gentle introduction to elliptic-curve cryptography
Edwards curve: x^2 + y^2 = 1 + dx^2y^2 , p = 3 mod 4
twisted Edwards curve: ax^2 + y^2 = 1 + dx^2*y^2 , p = 1 mod 4
short Weierstrass curve: y^2 = x^3 + a*x + b
amicable pair
Amicable pairs and aliquot cycles for elliptic curves
amicable pair: (p, q)
˜Ep(Fp) = q and # ˜Eq(Fq) = p and p<q
基于amicable pair进一步扩展，定义size l 的循环为aliquot cycle
l=1的prime即为anomalous prime，ECDLP降至linear time
CM curves: elliptic curves having complex multiplication
if E/Q has CM with j(E) 6 = 0, and if q = # ˜Ep(Fp) is prime, then there are only two possible values for # ˜Eq(Fq), namely p and 2q + 2 − p
Montgomery
Montgomery curves and the Montgomery ladder
Montgomery ladder就是scalar multiples of points的快速算法, n*P算得比较快
Weierstrass curve: a0y^2 + a1xy + a3y = x^3 + a2x^2 + a4*x + a6
Montgomery curve: By^2 = x^3 + Ax^2 + x
可见，Montgomery curve 属于Weierstrass curve
Montgomery curve可以跟 (twisted) Edwards curve 互相转换
Montgomery curve 的 x(2*P) 可以直接从 x(P) 算得，无需代入y(P)
Montgomery curve 的 x(P + Q) 可以从Montgomery ladder的(X : Y : Z)快速求得
Elligator
Elliptic curve points indistinguishable from random strings
Elligator: 本质上是如何隐藏信息。
通过string <-> ecc point的映射，使得交互时仅传输string，而非ecc point结构体。
进而使得中间人难以观测到实质上传输的是一个ecc point。
Elligator1 要求：q为prime, q = 3 mod 4, E 为 complete Edwards curve。
curve1174 适用 Elligator1。
Elligator2 要求： y^2 = x^3 + Ax^2 + Bx，其中 AB(A^2 - 4B)不为0。
curve25519 适用 Elligator2。
curve25519 vs curve448
Elliptic curve ed25519 vs ed448 - Differences
curve25519 约2^`125, curve448 约 2^224, Curve41417 约 2^200
X25519 vs Ed25519
Why Curve25519 for encryption but Ed25519 for signatures?
椭圆曲线计算无非是标量乘法:
- Fixed-base: 预知固定标量，例如签名计算时的基点乘法
- variable-base: 动态变换的标量，例如ECDH
- double-base：做两次标量乘法，然后相加，例如签名校验
X25519针对variable-base计算做了优化，其实就是Montgomery Curve，利用Montgomery ladder搞x轴。
Ed25519针对fixed-base & double-base计算做了优化，其实就是twisted Edwards curve，利用complete twisted Edwards addition law。
因此，默认不用X25519来做Ed25519的签名，但是，也可以结合Montgomery ladder应用，参考qDSA。
RFC7748给出了X25519 (u, v)与Ed25519 (x, y)的转换公式。
How do Ed25519 keys work?，图画的挺好。
Using Ed25519 signing keys for encryption，加密时直接用公式把公钥的point中的y转换为u，解密时从ed25519的key做hash提取前32byte的私钥。
use an X25519 key for EdDSA，定义一个从Montgomery私钥k到Edwards曲线的(A, a)的转换，再定义xeddsa、vxeddsa两种签名机制。
the Reference Implementation of Ed25519
Why EdDSA held up better than ECDSA against Minerva
EdDSA for more curves
Curve25519: new Diffie-Hellman speed records
secret EdDSA scalars 是 n+1 bits，c<=n<=b （这里b=256，c=3），n应该足够大，抗kangaroo攻击。注意，最高bit置1，最低的c bits置0。
sign bit
如果 b-1 bits 的 x > b-1 bits 的 -x，则，置 x 为 negative
压缩表示 b bits 的 (x , y )： b-1 bits 的 y，加上一个sign bit；如果sign bit为1，则标识 x 为 negative。
pureEdDSA
k 为 EdDSA secret key，b bits string
通过 H(k) 转换为 2b bits 的 string，然后拆分计算签名。由于最终签名(R, S)都有消息M的参与，比较抗锻造。
cofactorless verification
默认的校验是等式两边都乘上 cofactor = 2^c 做校验。如果等式两边不乘以cofactor，即为cofactorless verification。
small group attack
基点选得不好，non-prime order，可能被Pohlig-Hellman method加速计算。
attack
fault attack
Security of Hedged Fiat–Shamir Signatures under Fault Attacks 把去掉的nonce又加上……
