椭圆加密算法(ECC)是一种公钥加密体制,最初由Neal Koblitz和Victor Miller两人于1985年分别提出,其数学基础是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。

椭圆曲线密码体制来源于对椭圆曲线的研究,所谓椭圆曲线指的是由韦尔斯特拉斯(Weierstrass)方程:
$$$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$$$
所确定的平面曲线。其中系数$$$a_i$$$ $$$(i = 1, 2, \cdots, 6)$$$定义在某个域上,可以是有理数域、实数域、复数域,还可以是有限域$$$GF(p)$$$,椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。

椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个Abel群。在等式
$$$kP=\overbrace{P+P+\cdots+P}^{k\,\,\,times}=Q$$$
中,已知$$$k$$$和点$$$P$$$求点$$$Q$$$比较容易,反之已知点$$$Q$$$和点$$$P$$$$$$k$$$却是相当困难的,这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来。

https://playsecurity.org/getdoc/1993%5f1C3F2D201870EB3315AB049A1DD7B538/Weierstrass%20equations.pdf

描述一条$$$F_p$$$上的椭圆曲线,常用到六个参量:
$$$T=(p,a,b,G,n,h)$$$
$$$p$$$$$$a$$$$$$b$$$ 用来确定一条椭圆曲线,
$$$G$$$为基点,
$$$n$$$为点$$$G$$$的阶,
$$$h$$$ 是椭圆曲线上所有点的个数$$$m$$$$$$n$$$相除的整数部分)

这几个参量取值的选择,直接影响了加密的安全性。参量值一般要求满足以下几个条件:

1、$$$p$$$ 当然越大越安全,但越大,计算速度会变慢,200位左右可以满足一般安全要求;
2、$$$p≠n*h$$$
3、$$$pt≠1 (\bmod n), 1≤t<20$$$
4、$$$4a^3+27b^2≠0 (\bmod p)$$$
5、$$$n$$$ 为素数;
6、$$$h≤4$$$



$$$y^2 = x^3 + ax + b$$$对应的曲线:

ECC Add

最大值97的整数标绘的同一曲线:

ECC ADD over G(Fp)



ECC Slides

在F2m域上进行点加

$$$P+Q=R$$$

$$$s=\frac{y_{P}-y_{Q}}{x_{P}+x_{Q}}$$$
$$$x_{R} =s^{2}+s+x_{P}+x_{Q}+a$$$
$$$y_{R}=x_{R}+y_{P}+s(x_{P}+x{R})$$$


$$$2P=R$$$

$$$s=x_{P}+\frac{y_{P}}{x_{P}}$$$
$$$x_{R}=s^{2}+s+a$$$
$$$y_{R}={x_{P}}^{2}+(s+1)*x_{R}$$$

在Fp域上进行点加

$$$P+Q=R$$$

$$$s=\frac{y_{P}-y_{Q}}{x_{P}-x_{Q}} \bmod P$$$
$$$x_{R} = s^{2}-x_{P}-x_{Q} \bmod P$$$
$$$y_{R}=-y_{P}+s(x_{P}-x_{R}) \bmod P$$$


$$$2P=R$$$

$$$s=\frac{3{x_{P}}^{2}+a}{2y_{P}} \bmod P$$$
$$$x_{R}=s^{2}-x_{P}-x_{Q} \bmod P$$$
$$$y_{R}=-y_{P}+s(x_{P}-x_{R}) \bmod P$$$

$$$y^2≡x^3+2x+3 \pmod{97}$$$

$$$P=(3,6)$$$

$$$0P=0$$$
$$$1P=(3,6)$$$
$$$2P=(80,10)$$$
$$$3P=(80,87)$$$
$$$4P=(3,91)$$$
$$$5P=0$$$
$$$6P=(3,6)$$$
$$$7P=(80,10)$$$
$$$8P=(80,87)$$$
$$$9P=(3,91)$$$
$$$\cdots$$$

即: $$$kP=(k \bmod 5)P$$$

For Alice to sign a message $$$m$$$, she follows these steps:

  1. Calculate $$$e={\textrm {HASH}}(m)$$$, where HASH is a cryptographic hash function, such as SHA-2.
  2. Let $$$z$$$ be the $$$L_{n}$$$ leftmost bits of $$$e$$$, where $$$L_{n}$$$ is the bit length of the group order $$$n$$$.
  3. Select a cryptographically secure random integer $$$k$$$ from $$$[1,n-1]$$$.
  4. Calculate the curve point $$$(x_{1},y_{1})=k\times G$$$.
  5. Calculate $$$r=x_{1}\,{\bmod {\,}}n$$$. If $$$r=0$$$, go back to step 3.
  6. Calculate $$$s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$$$. If $$$s=0$$$, go back to step 3.
  7. The signature is the pair $$$(r,s)$$$.

For Bob to authenticate Alice's signature, he must have a copy of her public-key curve point $$$Q_{A}$$$. Bob can verify $$$Q_{A}$$$ is a valid curve point as follows:

  1. Check that $$$Q_{A}$$$ is not equal to the identity element $$$O$$$, and its coordinates are otherwise valid
  2. Check that $$$Q_{A}$$$ lies on the curve
  3. Check that $$$n\times Q_{A}=O$$$

After that, Bob follows these steps:

  1. Verify that $$$r$$$ and $$$s$$$ are integers in $$$[1,n-1]$$$. If not, the signature is invalid.
  2. Calculate $$$e={\textrm {HASH}}(m)$$$, where HASH is the same function used in the signature generation.
  3. Let $$$z$$$ be the $$$L_{n}$$$ leftmost bits of $$$e$$$.
  4. Calculate $$$w=s^{-1}\,{\bmod {\,}}n$$$.
  5. Calculate $$$u_{1}=zw\,{\bmod {\,}}n$$$ and $$$u_{2}=rw\,{\bmod {\,}}n$$$.
  6. Calculate the curve point $$$(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}$$$.
  7. The signature is valid if $$$r\equiv x_{1}{\bmod {n}}$$$, invalid otherwise.
public class BCECCDSATest {

    static final String EC_G = "046B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C2964FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5";
    static final String EC_N = "00FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551";

    public static void main(String[] args) {
        ECNamedCurveParameterSpec ecn = ECNamedCurveTable.getParameterSpec("secp256r1");
        ECCurve p256 = ecn.getCurve();

        ECPoint G = p256.decodePoint(Bytes.fromHex(EC_G).getBytes());
        BigInteger n = new BigInteger(Bytes.fromHex(EC_N).getBytes());

        BigInteger d = new BigInteger(255, new SecureRandom());
        ECPoint Q = G.multiply(d).normalize();
        System.out.println(d + " - d");
        System.out.println(Q + " - Q");

        String message = "Hello World.";
        byte[] hash = Digests.sha256().digest(message.getBytes(StandardCharsets.UTF_8)).getBytes();
        BigInteger e = new BigInteger(1, hash);
        System.out.println(e + " - e");

        // SIGN

        // (x1, x2)=kG
        BigInteger k = new BigInteger(255, new SecureRandom());
        ECPoint kG = G.multiply(k).normalize();
        System.out.println(k + " - k");
        System.out.println(kG + " - kG");

        // r=x1 mod n
        // s=k^-1(e+dr) mod n
        BigInteger r = kG.getXCoord().toBigInteger().mod(n);
        BigInteger s = k.modInverse(n).multiply(e.add(d.multiply(r))).mod(n);

        System.out.println(r + " - r");
        System.out.println(s + " - s");

        // VERIFY

        // c=s^-1 mod n
        // u1=ec mod n
        // u2=rc mod n
        // (x1, y1)=u1G+u2Q
        // v=x1 mod n
        BigInteger c = s.modInverse(n);
        BigInteger u1 = e.multiply(c).mod(n);
        BigInteger u2 = r.multiply(c).mod(n);
        ECPoint uGuQ = G.multiply(u1).add(Q.multiply(u2)).normalize();
        BigInteger v = uGuQ.getXCoord().toBigInteger().mod(n);

        // if v==r then success else fail
        System.out.println(v + " - v");
    }
}

Outputs:

8339335619003824837316171857090442185503111058507416390261190127801248406975 - d
(e84955cb02aabc9cfe4d9f227fdc64346c4c144f638b14a044b3cba2946c3f55,cf90454675395ec046ba2bdf943df5feaeac30cb3a971e4050aae88443c875df,1) - Q
110694911173530595670578600930991710652668442267815723053237189464905523473554 - e
2736360310200035368467746808912388965894573642370209205024023930990253492263 - k
(60990936a0c1bd64ced00284787a9e0839129e0cd3940c3fa32544851c91f740,470d84efe5e98fd75c4069b8d4e302e90e055705d56e52b8a2637969a86274dc,1) - kG
43692424653388573833405464958344316700408663786782137472117803965929307109184 - r
83697305946043570979035432403058877013859702222209490086131111455117628730238 - s
43692424653388573833405464958344316700408663786782137472117803965929307109184 - v

  • First, you find the two points $$$R$$$, $$$R′$$$ which have the value $$$r$$$ as the x-coordinate $$$r$$$.
  • You also compute $$$r^{−1}$$$, which is the multiplicative inverse of the value $$$r$$$ from the signature (modulo the order of the generator of the curve).
  • Then, you compute $$$z$$$ which is the lowest $$$n$$$ bits of the hash of the message (where $$$n$$$ is the bit size of the curve).

Then, the two public keys are $$$r^{−1}(sR−zG)$$$ and $$$r^{−1}(sR′−zG)$$$

public class BCECCDSARecoveryTest {

    static final String EC_G = "046B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C2964FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5";
    static final String EC_N = "00FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551";

    public static void main(String[] args) throws Exception {
        ECNamedCurveParameterSpec ecn = ECNamedCurveTable.getParameterSpec("secp256r1");
        ECCurve p256 = ecn.getCurve();

        ECPoint G = p256.decodePoint(Bytes.fromHex(EC_G).getBytes());
        BigInteger n = new BigInteger(Bytes.fromHex(EC_N).getBytes());

        BigInteger d = new BigInteger(255, new SecureRandom());
        ECPoint Q = G.multiply(d).normalize();
        System.out.println(d + " - d");
        System.out.println(Q + " - Q");

        String message = "Hello World.";
        byte[] hash = Digests.sha256().digest(message.getBytes(StandardCharsets.UTF_8)).getBytes();
        BigInteger e = new BigInteger(1, hash);
        System.out.println(e + " - e");

        // SIGN

        // (x1, x2)=kG
        BigInteger k = new BigInteger(255, new SecureRandom());
        ECPoint kG = G.multiply(k).normalize();
        System.out.println(k + " - k");
        System.out.println(kG + " - kG");

        // r=x1 mod n
        // s=k^-1(e+dr) mod n
        BigInteger r = kG.getXCoord().toBigInteger().mod(n);
        BigInteger s = k.modInverse(n).multiply(e.add(d.multiply(r))).mod(n);

        System.out.println(r + " - r");
        System.out.println(s + " - s");

        // RECOVERY
        BigInteger a = p256.getA().toBigInteger();
        BigInteger b = p256.getB().toBigInteger();
        BigInteger p = p256.getField().getCharacteristic();

        // get y from x (r)
        BigInteger ysquared = r.pow(3).add(r.multiply(a)).add(b);
        BigInteger y = ysquared.modPow((p.add(BigInteger.ONE)).divide(BigInteger.valueOf(4)), p);
        // y1=((x^3)+ax+b)^((p+1)/4) mod p
        BigInteger y1 = y.mod(p);
        // y2=y1*-1 mod p
        BigInteger y2 = y.multiply(BigInteger.valueOf(-1)).mod(p);

        System.out.println(Bytes.from(y1.toByteArray()).asHex() + " - y1");
        System.out.println(Bytes.from(y2.toByteArray()).asHex() + " - y2");

        // R=(r, y1)
        // P1=r^−1(sR−zG)
        ECPoint R = p256.createPoint(r, y1);
        ECPoint P1 = R.multiply(s).subtract(G.multiply(e)).multiply(r.modInverse(n)).normalize();
        System.out.println(P1 + " - P1");

        // R′=(r, y2)
        // P2=r^−1(sR′−zG)
        ECPoint R2 = p256.createPoint(r, y2);
        ECPoint P2 = R2.multiply(s).subtract(G.multiply(e)).multiply(r.modInverse(n)).normalize();
        System.out.println(P2 + " - P2");
    }
}

Outputs:

38019560345561684150635495742401303901141483643965249577125570930601841099743 - d
(6f3791d5d256991ec7282445ab60b2fa89166084d6e2d5ee9d3481d2deba2579,ff8af5f938a0ff18de95199e4b1930aa8b47cb1eeeed88455848b9cd826b20ef,1) - Q
110694911173530595670578600930991710652668442267815723053237189464905523473554 - e
33251217980662710263323006889465582954860547012072219586250831255749444299899 - k
(ee56d685d07b47f0b43056fc062b7fdf7b3800f78d5281e8e8885df21d5ac012,d1f77031280b1a2b71309f15ad3a626a9c0e86c96c9911763600fe1cf02e8b25,1) - kG
107803887391735132932602215427942167721389756739280384234415683210387469811730 - r
1911350382085751112357226628059825040558795379101842008034989625579356012673 - s
2e088fcdd7f4e5d58ecf60ea52c59d9563f179379366ee89c9ff01e30fd174da - y1
00d1f77031280b1a2b71309f15ad3a626a9c0e86c96c9911763600fe1cf02e8b25 - y2
(ecf83087d980f98c63b627ba6318f7e4861e699b0b25320e17f1f23e15b4b098,43e031098662b267c782f0e16a7e29ec12c17236093dd6e6105705075703367c,1) - P1
(6f3791d5d256991ec7282445ab60b2fa89166084d6e2d5ee9d3481d2deba2579,ff8af5f938a0ff18de95199e4b1930aa8b47cb1eeeed88455848b9cd826b20ef,1) - P2

$$$d_{A}Q_{B}=d_{A}d_{B}G=d_{B}d_{A}G=d_{B}Q_{A}$$$

public class BCECCDHTest {

    static final String EC_G = "046B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C2964FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5";

    public static void main(String[] args) {
        ECNamedCurveParameterSpec ecn = ECNamedCurveTable.getParameterSpec("secp256r1");
        ECCurve p256 = ecn.getCurve();

        ECPoint G = p256.decodePoint(Bytes.fromHex(EC_G).getBytes());

        BigInteger d = new BigInteger(255, new SecureRandom());
        ECPoint dG = G.multiply(d).normalize();
        System.out.println(d + " - d");
        System.out.println(dG + " - dG");

        BigInteger k = new BigInteger(255, new SecureRandom());
        ECPoint kG = G.multiply(k).normalize();
        System.out.println(k + " - k");
        System.out.println(kG + " - kG");

        ECPoint kQ = dG.multiply(k).normalize();
        ECPoint dkG = kG.multiply(d).normalize();

        System.out.println(kQ + "- kdG");
        System.out.println(dkG + " - dkG");
    }
}

Outputs:

8497170259015010226357615438591155947454283966527800158758512050710295813937 - d
(225096f66804e079cc0d6fac79f3a9859290acbdccaa29fe16acd36c68ce9eb9,6a3fe961ee97503a8d48f93595e6cddb1b5052ce18612e9ab4dddf7efc01afd6,1) - dG
8953799744019712250647492442755447078321881910728171228752570400323438092916 - k
(98e24a2d4e17dcc7a48f7187dee2a52fdc6c275fcd909cc37de270e61c893824,aa68f7052047ee83d0f3b5884619faba881bfdbe6dae5b1e5b26a6d725b7316,1) - kG
(cdbd94f33f7a582d760c2ec3a0ce074b6337b26c790999fe6a77142a9fcca2ee,279b4ff199cd95f9798f3940f3d1e63314381dad8bbf8079310e9e94a93b7ec2,1)- kdG
(cdbd94f33f7a582d760c2ec3a0ce074b6337b26c790999fe6a77142a9fcca2ee,279b4ff199cd95f9798f3940f3d1e63314381dad8bbf8079310e9e94a93b7ec2,1) - dkG

To encrypt a message $$$m$$$ Alice does the following:

  1. generates a random number $$$r\in [1,n-1]$$$ and calculates $$$R=rG$$$;
  2. derives a shared secret: $$$S=P_{x}$$$, where $$$P=(P_{x},P_{y})=rK_{B}$$$ (and $$$P\neq O$$$);
  3. uses KDF to derive a symmetric encryption and a MAC keys: $$$k_{E}\|k_{M}={\textrm  {KDF}}(S\|S_{1})$$$;
  4. encrypts the message: $$$c=E(k_{E};m)$$$;
  5. computes the tag of encrypted message and {$$$S_{2}$$$: $$$d={\textrm  {MAC}}(k_{M};c\|S_{2})$$$;
  6. outputs $$$R\|c\|d$$$.


To decrypt the ciphertext $$$R\|c\|d$$$ Bob does the following:

  1. derives the shared secret: $$$S=P_{x}$$$, where $$$P=(P_{x},P_{y})=k_{B}R$$$ (it is the same as the one Alice derived because $$$P=k_{B}R=k_{B}rG=rk_{B}G=rK_{B})$$$, or outputs failed if $$$P=O$$$;
  2. derives keys the same way as Alice did: $$$k_{E}\|k_{M}={\textrm  {KDF}}(S\|S_{1})$$$;
  3. uses MAC to check the tag and outputs failed if $$$d\neq {\textrm  {MAC}}(k_{M};c\|S_{2})$$$;
  4. uses symmetric encryption scheme to decrypt the message $$$m=E^{{-1}}(k_{E};c)$$$.

It is imperative to have a random $$$m$$$ for every signature: from a pair of signatures that use the same $$$m$$$, we can compute $$$m$$$ and $$$k$$$.

$$$R=(mG)_x$$$

$$$S_1=\frac{e_1+kR}{m}$$$
$$$S_2=\frac{e_2+kR}{m}$$$

$$$S_1-S_2=\frac{e_1-e_2}{m}$$$
$$$m=\frac{e_1-e_2}{S_1-S_2}$$$

$$$k=\frac{mS_i-e_i}{R}=\frac{e_1S_2-e_2S_1}{R(S_1-S_2)} \pmod n$$$

public class BCECCDSATestCrack {

    static final String EC_G = "046B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C2964FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5";
    static final String EC_N = "00FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551";

    public static void main(String[] args) throws Exception {
        ECNamedCurveParameterSpec ecn = ECNamedCurveTable.getParameterSpec("secp256r1");
        ECCurve p256 = ecn.getCurve();

        ECPoint G = p256.decodePoint(Bytes.fromHex(EC_G).getBytes());
        BigInteger n = new BigInteger(Bytes.fromHex(EC_N).getBytes());

        BigInteger d = new BigInteger(255, new SecureRandom());
        ECPoint Q = G.multiply(d).normalize();
        System.out.println(d + " - d");
        System.out.println(Q + " - Q");

        String message1 = "Hello World.";
        byte[] hash1 = Digests.sha256().digest(message1.getBytes(StandardCharsets.UTF_8)).getBytes();
        BigInteger e1 = new BigInteger(1, hash1);
        System.out.println(e1 + " - e1");
        String message2 = "Hello World 2.";
        byte[] hash2 = Digests.sha256().digest(message2.getBytes(StandardCharsets.UTF_8)).getBytes();
        BigInteger e2 = new BigInteger(1, hash2);
        System.out.println(e2 + " - e2");

        // SIGN

        // (x1, x2)=kG
        BigInteger k = new BigInteger(255, new SecureRandom());
        ECPoint kG = G.multiply(k).normalize();
        System.out.println(k + " - k");
        System.out.println(kG + " - kG");

        // r=x1 mod n
        // s=k^-1(e+dr) mod n
        BigInteger r = kG.getXCoord().toBigInteger().mod(n);
        BigInteger s1 = k.modInverse(n).multiply(e1.add(d.multiply(r))).mod(n);
        BigInteger s2 = k.modInverse(n).multiply(e2.add(d.multiply(r))).mod(n);

        System.out.println(r + " - r");
        System.out.println(s1 + " - s1");
        System.out.println(s2 + " - s2");

        BigInteger r_mul_s1_sub_s2 = r.multiply(s1.subtract(s2));
        BigInteger e1_mul_s2_sub_e2_mul_s1 = e1.multiply(s2).subtract(e2.multiply(s1));
        System.out.println(r_mul_s1_sub_s2.modInverse(n).multiply(e1_mul_s2_sub_e2_mul_s1).mod(n) + " - cracked d");
    }
}

Outputs:

51466347005671828303957295741616726156421161252085572664583613357909095613902 - d
(f931f7bb9a2323c5a5dd1b4613112faf25942a14dac8dfc7e33450dd9e30dacb,fc1915d433c980b4bd00ac187bed3e70250d7fa8530a95a13aa35536d002ee8a,1) - Q
110694911173530595670578600930991710652668442267815723053237189464905523473554 - e1
66922269942863644750565189256646477005079910784186234771680458426111528822211 - e2
41683346796553297944617074501359868116670569134809166234464449225150848805153 - k
(b664941a9efeee94f70e02b394e98f07d1f385e4d8df2cf1d308b57cc25845d7,e4c4d73e9011771df96ed896e9e118c426e15c78673aa69916b2d6686776fa4,1) - kG
82498645324794474475605788790608602539149661560076504197275318302310303024599 - r
106427360426020067926327791739910945706371013406349559855935733611384228853644 - s1
48034008218942858557761667527638353342161906478309771728588300169611795827588 - s2
51466347005671828303957295741616726156421161252085572664583613357909095613902 - cracked d

https://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3console_hacking2010.pdf

SECG ANSI X9.62 NIST
sect163k1 NIST K-163
sect163r1
sect163r2 NIST B-163
sect193r1
sect193r2
sect233k1 NIST K-233
sect233r1 NIST B-233
sect239k1
sect283k1 NIST K-283
sect283r1 NIST B-283
sect409k1 NIST K-409
sect409r1 NIST B-409
sect571k1 NIST K-571
sect571r1 NIST B-571
secp160k1
secp160r1
secp160r2
secp192k1
secp192r1 prime192v1 NIST P-192
secp224k1
secp224r1 NIST P-224
secp256k1
secp256r1 prime256v1 NIST P-256
secp384r1 NIST P-384
secp521r1 NIST P-521