Jianshu支持公式太差了。分享文档在此：链接: https://pan.baidu.com/s/1jHJNGt4 密码: rpvi 。大家自己下载阅读吧。

Introdution

本文是简单介绍椭圆曲线密码学的基本内容，目标是直观、简化，忽略严谨性。切记，简单是为了导向严肃而不是庸俗。

阅读以下内容，在有群论与密码学的基础上，大概需要1个小时。如果没有密码学基础，可忽略密码学，而重点关注椭圆曲线的定义与相关计算。

Why we need ECC?

• Efficiency
• More properties

What exactly is an elliptic curve?

Definition

Let $$a ∈ ℝ$$, $$b ∈ ℝ$$, be constants such that $$4a^3 + 27b^2 ≠ 0$$. A non-singular elliptic curve is the set $$E$$ of solutions $$(x, y) ∈ ℝ \times ℝ$$ to the equation: $$y^2 = x^3 + ax + b$$ together with a special point $O$ called the point at infinity.

The solution set $$E$$ forms an Abelian group.

Graphical Representation

Elliptic curve

Addition of the Group E

Three cases:

Case1 x1 ≠ x2

Addition is defined as follows:

Let $$(x_1, y_1) + (x_2, y_2) = (x_3, y_3) ∈ E$$ where

$$x_3 = λ^2 - x_1 - x_2$$

$$y_3 = λ(x_1 – x_3) - y_1$$,

and $$λ = (y_2 – y_1) / (x_2 – x_1)$$

**Case2 x1 = x2 and y1 = - y2 **

Addition is defined as follows:

$$(x_1, y_1) + (x_2, y_2) = (x_3, y_3) ∈ E$$ where

$$(x, y) + (x, -y) = O$$, the point at infinity.

Case3 x1 = x2 and y1 = y2

Addition is defined as follows:

$$(x_1, y_1) + (x_2,y_2) = (x_3, y_3) ∈ E$$ where

$$x_3 = λ^2 - x_1 - x_2$$

$$y_3 = λ(x_1 – x_3) - y_1$$, and

$$λ = (3x_1^2 + a) / 2y_1$$

If you want to know why the computations are correct, please read Silverman's text: Rational Points on Elliptic Curves.

ECC mod p

Definition. Let $$p > 3$$ be prime. The elliptic curve $$y^2 = x^3 + ax + b$$ over $$ℤ_p$$ is the set of solutions $$(x, y) \in ℤ_p \times ℤ_p$$ to the congruence: $$y^2 ≡ x^3 + ax + b ; (mod ; p) $$ where $$a \in ℤ_p$$, $$b \in ℤ_p$$, are constants such that $$4a^3 + 27b^2 ≢ 0 \quad (mod ; p)$$, together with a special point $$O$$ called the point at infinity.

Solutions still form an Abelian group.

Example

Let’s examine the following elliptic curve as an example:

$$y^2 = x^3 + x + 6$$ over $$ℤ_{11}$$

Generating the group

Since the $$O(E)$$ is prime, the group is cyclic. We can generate the group by choosing any point other than the point at infinity. Let our generator be $$ g = (2, 7)$$

Generate the group by using the rules of addition we defined earlier where $$2g = g + g$$:

Where $$\lambda = 8$$. You could check that.

Discrete logarithm problem on elliptic curve groups

Definition. (Informal!) Suppose $$E$$ is an elliptic curve and $$P \in E $$ . Given a multiple $$Q$$ of $$P$$, the elliptic curve discrete log problem(ECDLP) is to find $$n$$ such that $$nP = Q$$.

Example. Given $$g$$ and $$Q=(3, 5)$$, find $$n=8$$, s.t., $$ng = Q$$.

We believe ECDLP problem is hard, more rigorous results may be found here.

A real example from the NSA

Curve P-192

• p = 62771017353866807638578942320766641608390870039024961279
• r = 627710173538668076385789423176059013767194773182842284081
• a = 3099d2bb bfcb2538 542dcd5f b078b6ef 5f3d6fe2 c745de65
• b = 64210519 e59c80e7 0fa7e9ab 72243049 feb8deec c146b9b1
• Gx = 188da89e b03090f6 7cbf20eb 43a18800 f4ff0afd 82ff1012
• Gy = 07192b95 ffc8da78 631011ed 6b24cdd5 73f977a1 1e794811

ECC in Sage

Play with following simple code:

sage: p = 137
sage: F = FiniteField(p)
sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])
sage: print E
Elliptic Curve defined by y^2 = x^3 + 112*x + 106 over Finite Field of size 137
sage: E.points()
[(0 : 1 : 0), (2 : 8 : 1), (2 : 129 : 1),......

Now, to visualize a EC, actually, it looks like that ...

sage: show(plot(E, hue=.9))

EC137.png

Diffie-Hellman in ECC

sage: p = next_prime(randrange(10^40))
sage: print p
sage: F = FiniteField(p)
sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])
sage: P = E.random_element()
sage: print P
sage: b = randrange(1000); b
sage: B = b*P
sage: a = randrange(1000); a
sage: A = a*P
sage: if(a*B == b*A): print "We share a common secret."

Show me more...

2017年8月24日