计算机安全学

ComSec讲义：A Brief Introduction to

2017-08-23  本文已影响33人  Bintou老师

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

Introdution

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

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

Why we need ECC?

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}$$

X 0 1 2 3 4 5 6 7 8 9 10
$$y^2 = x^3 + x + 6$$ 6 8 5 3 8 4 8 4 9 7 4
QR? N N Y Y N Y N Y Y N Y
Y 4, 7 5, 6 2, 9 2, 9 3, 8 2, 9

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$$:

g 2g 3g 4g 5g 6g 7g 8g 9g 10g 11g 12g 13g
(2, 7) (5, 2) (8, 3) (10, 2) (3, 6) (7, 9) (7, 2) (3, 5) (10, 9) (8, 8) (5, 9) (2, 4) (0, 6)

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

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日

上一篇下一篇

猜你喜欢

热点阅读