ECC : Elliptical Curve Cryptography

by allenlu2007

 

這也是 abstract algebra 的應用。

Andrea Corbellini 一系列的 ECC 介紹文章非常優異。

四篇文章包含:

1. Elliptic curves over real numbers and the group law

2. Elliptic curves over finite fields and the discrete logarithm problem

3. Key pair generation and two ECC algorithms: ECDH (EC Diffie-Hellman) and ECDSA

4. Algorithms for breaking ECC security, and a comparison with RSA

 

幾個要點:

* Elliptic Curves definition:  y^2 = x^3 + ax + b  => very useful, even for solving Fermat Last Theorem

NewImage

 

* 定義 EC (infinite) group as below over 2-D real field. 

NewImage

EC group 是 Abelian group.

重點是如何定義 a + b.  可以由 geometry 看出:

NewImage

a + b + c =  0   =>   a + b = -c

舉例而言:

NewImage

 

假設 P = Q    P + Q = P + P,  就用切線來替代:

NewImage

 

 

下一步是定義 scalar multiplication.  嚴格來說 group 沒有 multiplication, 但可以視為連加

nP = P + P + P … + P  (n times)

Let Q = nP  where n is a positive integer.   這是 ECC 的核心。

如果 n, P 已知,可以容易算 Q.

反之, 如果 Q and P 已知,很難算 n.  這稱為 logarithm problem.

 

* EC over finite field GF(p)

注意此時我們用 finite field GF℗ 取代 real group.  因為是 field, 可以定義除法。

NewImage

 

因為定義 modulo p +, -, x, /.  所以原來的幾何特性很難看出。因為全部都折回 [0, p-1] 的 2D 內。

NewImage

不過似乎所有滿足 EC over finite field GF℗ 並非所有值。(i.e. p^2)  有些值並不會出現。這很合理。

畢竟並非所有的 (x, y) 都滿足 EC curve.  但 EC curve values 本身是 finite field, 所以應該是 prime number or prime number 的 power.

 

下一個重要問題是: How many points are there exactly?

The Order of an Elliptic Curve Group

1.  The set of the multiples of P is a cyclic subgroup.   P is called generator or base point of the cyclic subgroup.

1. Calculate the EC order N using Schoof’s algorithm

2. Find all divisors of N

3. For every division n of N, compute nP

4. The smallest n such that nP = 0 is the order of the subgroup.

NewImage

如果 N 是 prime number,  可以想見 n = N.  也就是 prime finite field. 

所以所有參數有:  a, b, p, N (or n as a prime number), P (base point or generator).

比起 real group case 多了 p, N, and P.

核心問題是  Q = k P 容易。但已知 Q and P 找  k (< n) 非常困難。Discrete logarithm.

類似 b = G^k mod p.  (最早的 Diffie-Hellman)  domain parameters (G, p). 已知 b 如何找 k?

k 是 private key;  b 是 public key.

 

Domain Parameters

Our EC algorithm will work in a cyclic subgroup of an elliptic curve over a finite field, including the following parameters:

* prime p (order of the finite field for modulo operation)

* a and b of the EC

* base point G that generates the subgroup

* order n of the subgroup nG = 0  (n 要是一個  prime number)

* cofactor h of the subgroup where h = N/n.   N 是 EC 的 order.  (N = n * h)

Domain parameters = (p, a, b, G, n, h)

 

ECC – Elliptic Curve Cryptography

1. private key is a random integer d from { 1, …, n-1}  where n is the order of the subgroup (big prime number).

2. public key is the point H= dG (where G is the base point of the subgroup).

所以從 d and G 算 H 很容易。但從 H and G 找 d 非常難。

 

Encryption with ECDH

1. Alice and Bob has their own private and public keys (da, Ha) and (db, Hb)

2. Alice and Bob exchange their public keys Ha and Hb over insecure channel.

3. Alice compute S = da Hb = da db G = db da G = db Ha  same as Bob’s computation.

4. Use S as a key to encrypt all messages.

5. 其他的人可以得到 Ha and Hb, 但無法得到 S = da Hb = db Ha

 

接下來可以用 S 做 AES, DES3 等等的 encryption. 

 

Example: (from OpenSSL source code)

NewImage

n >> p.  h = 1 =>  N = n 也就 EC order 是一個 prime number.  G = (xG, yG)

 

Curve: secp256k1
Alice's private key: 0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb
Alice's public key: (0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677, 0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)
Bob's private key: 0xcef147652aa90162e1fff9cf07f2605ea05529ca215a04350a98ecc24aa34342
Bob's public key: (0x4034127647bb7fdab7f1526c7d10be8b28174e2bba35b06ffd8a26fc2c20134a, 0x9e773199edc1ea792b150270ea3317689286c9fe239dd5b9c5cfd9e81b4b632)
Shared secret: (0x3e2ffbc3aa8a2836c1689e55cd169ba638b58a3a18803fcf7de153525b28c3cd, 0x43ca148c92af58ebdb525542488a4fe6397809200fe8c61b41a105449507083)

 可以看到 private key 是一個數字。但 public key 是一對數字。Share key 也是一對數字。

 

Signing with ECDSA

第一步是先 hash of the message.  但要 truncated so that the bit length of the hash is the same as the bit length of n (order of the subgroup).   The truncated hash is an integer and will be denoted as z.

Alice 

1. Take a random integer k from {1, …, n-1}.

2. Compute P= kG

3. Compute the number r = xp mod n (where xp is the x coordinate of P)  注意非 mod p!!

4. if r=0 choose another k and try again

5. Compute s = k^(-1) (z + r da) mod n (where da is private key and k^-1 is the multiplicative inverse of k modulo n)

6. If s=0 choose another k and try agin.

The pair (r, s) is the signature

NewImage

Verification:

1. compute the integer u1 = s^-1 z mod n.

2. compute the integer u2 = s^-1 r mod n.

3. compute P = u1 G + u2 Ha 

 

 

 

 

Advertisements