Bài giảng Mật mã ứng dụng: Bài toán logarit rời rạc và Diffie-Hellman

Mật mã ứng dụng

Bài toán logarit rời rạc và Diffie-Hellman

Nội dung

• Bài toán Logarit rời rạc • Bài toán Diffie-Hellman

Định nghĩa Nhóm

Một nhóm Abel (",⋅) thoả mãn các tính chất sau:

1. Có phần tử đơn vị: 1 ∈ # thoả mãn

∀% ∈ #, % ⋅ 1 = 1 ⋅ % = % 2. Mọi phần tử đều khả nghịch:

∀% ∈ #, ∃* ∈ # thoả mãn % ⋅ * = 1 3. Kết hợp: ∀%, *, + ∈ # ta có % ⋅ (* ⋅ +) = (% ⋅ *) ⋅ + 4. Giao hoán: ∀%, * ∈ # ta có % ⋅ * = * ⋅ %

Cấp của một phần tử trong nhóm

• Cấp của phần tử !, ký hiệu ord(a), là số " > 0 nhỏ nhất thoả mãn

!! = 1 ∈ (.

• Định lý Lagrange: Trong nhóm hữu hạn ( với lực lượng ), ta có

∀! ∈ (, ord(!) ∣ ).

• Hệ quả: Trong nhóm hữu hạn ( với lực lượng ), ta có

∀! ∈ (,

!" = 1.

• Ký hiệu: ⟨!⟩ = {!# ∣ 2 ≥ 0} là nhóm con sinh bởi !.

Nhóm vòng

• Ký hiệu ⟨"⟩ = {"! ∣ ' ≥ 0} là nhóm con sinh bởi ".

• Nếu ⟨"⟩ = + thì " là một phần tử sinh của +.

• Khẳng định: |⟨"⟩| = ord(").

• Định nghĩa: G là nhóm vòng nếu có g thoả mãn ⟨/⟩ = +

Hàm logarit rời rạc và hàm mũ

• Khẳng định: Nếu + là nhóm vòng cấp 0 và / là phần tử sinh,

thì quan hệ

1 ↔ /"

là 1-to-1 giữa {0,1, … , 0 − 1} và +.

• Hàm mũ x à gx

• Hàm logarit rời rạc gx à x

Tính ngẫu nhiên của lũy thừa 627x (mod 941)

Bài toán Logarit rời rạc

∗ . ∗ và ℎ ∈ ℤ#

• Xét / là một phần tử sinh của ℤ#

• Bài toán Logarit rời rạc (DLP) là bài toán tìm một số mũ 1 thỏa

mãn

/" ≡ ℎ mod ;.

• Số 1 được gọi là logarit rời rạc cơ sở / của ℎ và ký hiệu

Dlog%(ℎ).

Bài tập

Hãy tính các logarit rời rạc sau.

1. Dlog&(13) trong modun nguyên tố 23 2. Dlog'((22) trong modun nguyên tố ; = 47. 3. Dlog)&*(608) trong modun nguyên tố ; = 941.

Tính Logarit rời rạc

• Xét số nguyên tố ; = 56509, và ta có thể kiểm tra / = 2 là một

căn nguyên thủy modun ;.

• Làm thế nào để tính log&(38679)? • Một phương pháp là tính

2(, 2', 2&, 2+, ⋯ mod 56509 cho đến khi được lũy thừa bằng 38679.

• Bạn có thể kiểm tra rằng

2''&+, ≡ 38679 mod 56509.

Nội dung

• Bài toán Logarit rời rạc • Bài toán Diffie-Hellman

Bài tập

∗ . Hãy tính hai giá trị sau trong ℤ'+ • DH*(10,5) • DH&(12,9) biết rằng

(mod p)

DHg(ga, gb) = gab

⟨2⟩ = {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7} ⟨7⟩ = {1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2}

Nhắc lại: Giao thức Diffie-Hellman (1977)

Xét nhóm vòng G (e.g G = (Zp)* ) với cấp n Lấy một phần tử sinh g thuộc G (i.e. G = {1, g, g2, g3, … , gn-1 } )

Alice

Bob

Chọn ngẫu nhiên a in {1,…,n}

Chọn ngẫu nhiên b trong {1,…,n}

A = ga

B = gb

= Ab

= (ga)b

Ba = (gb)a

kAB = gab

Bài tập

• Alice và Bob dùng số nguyên tố ; = 1373 và cơ sở / = 2 để

trao đổi khóa.

• Alice gửi Bob giá trị F = 974. • Bob chọn số bí mật G = 871. • Bob nên gửi cho Alice giá trị gì, và khóa bí mật họ chia sẻ là gì? • Bạn có thể đoán được số bí mật " của Alice không?

Một câu hỏi mở

• Nếu ta có thể giải bài toán Logarit rời rạc, vậy ta có thể giải bài

toán Diffie-Hellman. Tại sao?

• Nhưng nếu ta có thể giải được bài toán Diffie-Hellman, vậy liệu

ta có thể giải được bài toán logarit rời rạc không?

Một số nhóm hay được dùng

∗ = {1, … , 1 − 1} với 1 nguyên tố • Nhóm ℤ! ∗ } • Nhóm thặng dư bình phương ℚ! = {%# ∣ % ∈ ℤ! ∗ = {% ∈ {1, … , 6 − 1} ∣ gcd(%, 6) = 1}. • Nhóm ℤ$ Hệ RSA sử dụng ℤ!% với 1, 7 là các số nguyên tố ngẫu nhiên lớn. ∗ } • Nhóm ℚ$ = {%# ∣ % ∈ ℤ$ • Nhóm điểm trên đường cong Elliptic

Mật mã ứng dụng

Hệ mật mã dựa trên đường cong Elliptic

Nội dung

1. Đường cong Elliptic (Elliptic Curve, EC)

2. Bài toán Logarit rời rạc trên EC

3. Giao thức trao đổi khoá Diffie-Hellman trên EC

156

6 Introduction to Public-Key Cryptography

(MQ) or some lattice-based schemes are examples of this. Another common prob-

lem is that they have poor implementation characteristics, like key lengths in the

range of megabytes, e.g., the McEliece cryptosystems. However, there are also some

other schemes, for instance, hyperelliptic curve cryptosystems, which are both as ef-

ﬁcient and secure as the three established families shown above, but which simply

have not gained widespread adoption. For most applications it is recommended to

use public-key schemes from the three established algorithm families.

6.2.4 Key Lengths and Security Levels

All three of the established public-key algorithm families are based on number-

theoretic functions. One distinguishing feature of them is that they require arith-

metic with very long operands and keys. Not surprisingly, the longer the operands

and keys, the more secure the algorithms become. In order to compare different

algorithms, one often considers the security level. An algorithm is said to have a

“security level of n bit” if the best known attack requires 2n steps. This is a quite

natural deﬁnition because symmetric algorithms with a security level of n have a key

of length n bit. The relationship between cryptographic strength and security is not

as straightforward in the asymmetric case, though. Table 6.1 shows recommended

bit lengths for public-key algorithms for the four security levels 80, 128, 192 and 256

bit. We see from the table that RSA-like schemes and discrete-logarithm schemes

require very long operands and keys. The key length of elliptic curve schemes is signiﬁcantly smaller, yet still twice as long as symmetric ciphers with the same cryptographic strength.

Vấn đề: Tìm hệ mật với tham số ngắn hơn

Table 6.1 Bit lengths of public-key algorithms for different security levels

Algorithm Family Cryptosystems

Security Level (bit)

128

192

256 1024 bit 3072 bit 7680 bit 15360 bit Integer factorization RSA Discrete logarithm DH, DSA, Elgamal 1024 bit 3072 bit 7680 bit 15360 bit 512 bit Elliptic curves 256 bit Symmetric-key

160 bit 256 bit 384 bit 80 bit 128 bit 192 bit

ECDH, ECDSA AES, 3DES

Kích thước theo bit của các hệ mật mã khoá công khai ở mức an toàn khác nhau

You may want to compare this table with the one given in Sect. 1.3.2, which provides information about the security estimations of symmetric-key algorithms. In order to provide long-term security, i.e., security for a timespan of several decades,

a security level of 128 bit should be chosen, which requires fairly long keys for all

three algorithm families.

An undesired consequence of the long operands is that public-key schemes are

extremely arithmetically intensive. As mentioned earlier, it is not uncommon that

one public-operation, say a digital signature, is by 2–3 orders of magnitude slower

than the encryption of one block using AES or 3DES. Moreover, the computational

9.1 How to Compute with Elliptic Curves

241

solutions of the equations. For example, the point (x = r, y = 0) fulﬁlls the equation

of a circle and is, thus, in the set. The point (x = r/2, y = r/2) is not a solution to the

polynomial x2 + y2 = r2 and is, thus, not a set member. An elliptic curve is a special

type of polynomial equation. For cryptographic use, we need to consider the curve

not over the real numbers but over a ﬁnite ﬁeld. The most popular choice is prime

ﬁelds GF(p) (cf. Sect. 4.2), where all arithmetic is performed modulo a prime p.

Deﬁnition 9.1.1 Elliptic Curve

The elliptic curve over Zp, p > 3, is the set of all pairs (x, y)

∈

which fulﬁll

(9.1)

x3 + a

x + b mod p

≡

together with an imaginary point of inﬁnity O, where

a, b

∈

and the condition 4

a3 + 27

= 0 mod p.

The deﬁnition of elliptic curve requires that the curve is nonsingular. Geometri-

cally speaking, this means that the plot has no self-intersections or vertices, which

is achieved if the discriminant of the curve

16(4a3 + 27b2) is nonzero.

−

For cryptographic use we are interested in studying the curve over a prime ﬁeld

as in the deﬁnition. However, if we plot such an elliptic curve over Zp, we do not get

anything remotely resembling a curve. However, nothing prevents us from taking an

elliptic curve equation and plotting it over the set of real numbers.

3x + 3 is shown over the real

−

Example 9.3. In Figure 9.3 the elliptic curve y2 = x3 numbers.

Đường cong Elliptic

Đường cong Elliptic trên K là tập mọi cặp (x,y) ∈ K thoả mãn phương trình y2 = x3 + a·x + b

cùng với một điểm vô cực O,

trong đó

a, b ∈ K và thoả mãn 4·a3 +27·b2 ≠ 0.

Fig. 9.3 y2 = x3

3x + 3 over R

y2 = x3 −3x+3 trên R

−

Đường cong không điểm kỳ dị

Đường cong y2 = x3 + 2x + 2 trên Z17

Danh sách điểm

(7, 11) (9, 1) (9, 16) (10, 6) (10, 11) (13, 7) (13,10) (16, 4) (16, 13)

! (0, 6) (0,11) (3,1) (3,16) (5, 1) (5,16) (6, 3) (6, 14) (7, 6)

Phép toán nhóm trên EC

• Ký hiệu phép toán nhóm bởi ký hiệu cộng “+”. • Cho hai điểm P = (x1, y1) và Q = (x2, y2) • Ta phải tính toạ độ của điểm thứ ba R thoả mãn:

P + Q = R (x1, y1) + (x2, y2) = (x3, y3)

• Phép cộng điểm P + Q: Trường hợp R = P + Q và P ≠ Q • Nhân đôi điểm P + P: Trường hợp P + Q nhưng P = Q.

243

Phép toán nhóm

9.1 How to Compute with Elliptic Curves y

P + Q

•

P •

•Q

Fig. 9.4 Point addition on an elliptic curve over the real numbers

Cộng điểm P + Q

Nhân đôi P + P = 2P

draw the tangent line through P and obtain a second point of intersection between

this line and the elliptic curve. We mirror the point of the second intersection along

the x-axis. This mirrored point is the result R of the doubling. Figure 9.5 shows the

•

2 P

•

Fig. 9.5 Point doubling on an elliptic curve over the real numbers

doubling of a point on an elliptic curve over the real numbers.

You might wonder why the group operations have such an arbitrary looking form.

Historically, this tangent-and-chord method was used to construct a third point if

two points were already known, while only using the four standard algebraic op-

erations add, subtract, multiply and divide. It turns out that if points on the elliptic

curve are added in this very way, the set of points also fulﬁll most conditions neces-

sary for a group, that is, closure, associativity, existence of an identity element and

existence of an inverse.

Of course, in a cryptosystem we cannot perform geometric constructions. How-

ever, by applying simple coordinate geometry, we can express both of the geomet-

Phép toán cộng và nhân đôi các điểm

!! = #" − !# − !" mod % &! = #(!# − !!) − &# mod %

với

# = )

+, - ≠ / +, - = /

(&" − &#)/(!" − !#) mod % " + 2)/(2&#) mod % (3!#

Ví dụ

Xét đường cong

#! = %" + 2% + 2 ()* 17

Ta muốn nhân đôi điểm - = (5,1).

# + .)/(2)") = (2 ⋅ 1)$"(3 ⋅ 5# + 2) = 2$" ⋅ 9 = 13 345 17

2" = " + " = 5,1 + 5,1 = (!, )! . + = (3(" (! = +# − (" − (# = 13# − 5 − 5 = 6 345 17. )! = + (" − (! − )" = 13 5 − 6 − 1 = −14 = 3 345 17 2" = 5,1 + 5,1 = 6,3

Tính toán với Sagemath

sage: E = EllipticCurve(GF(17),[2,2]) sage: E Elliptic Curve defined by y^2 = x^3 + 2*x + 2 over Finite Field of size 17 sage: P = E(5,1) sage: Q = P + P sage: print Q (6 : 3 : 1) sage: E.is_on_curve(6,3) True

Luật cộng đầy đủ cho EC

1. : + : = :. 2. : + ((#, )#) = ((#, )#). 3. ((", )") + : = ((", )"). 4. ((", )") + ((", −)") = :. 5. cho )" ≠ 0, ((", )") + ((", )") = +# − 2(", +((" − (!) − )"

với s= (3("

# + .)/2)".

6. cho (" ≠ (#, ((", )") + ((#, )#) = +# − (" − (#, +((" − (!) − )"

với s = ()# − )")/((# − (").

Kiểm tra các tính chất với Sagemath

1.: + : = :. 2.: + ((#, )#) = ((#, )#). 3.((", )") + : = ((", )"). 4.((", )") + ((", −)") = :

- P

Phần tử đơn vị

sage: O = P + -P sage: O (0 : 1 : 0) sage: O + O == O True sage: P + O (5 : 1 : 1) sage: P + O == P True sage: O + P == P True

Hệ toạ độ chiếu

• Điểm chiếu (X :Y : Z), Z ≠ 0 tương ứng với điểm

trên Affine (X/Z,Y/Z).

• Phương trình chiếu của EC là 3!4 = 5" + 654! + 74".

• Điểm tại vô cực 9 tương ứng với (0:1:0),

và phần tử nghịch đảo của (X: Y: Z) là (X: -Y: Z).

Lợi ích của hệ toạ độ chiếu

• Tính toán phép “+” hiệu quả hơn do tránh được phép nghịch

đảo trên trường hữu hạn

• Phép toán cơ bản " # trở nên dễ dàng

(x’, y’) = 2 (x, y) (+ʹ ∶ -ʹ ∶.ʹ) =2(+∶-∶.)

!"!#$ s = %& &' = '% − 2& *' = ' & − &' − *

+ʹ = 2-Z ( (3+2+/.2)2 − 8-2+. ) -ʹ = (3+2 +/.2)( 12-2+.− (3+2 + /.2)2 ) − 8-4.2 .ʹ = 8-3.3

Ví dụ trên Sagemath

def point_doubling(x, y, z, a):

x_ = 2*y*z*((3*x^2 + a*z^2)^2 - 8*y^2*x*z) y_ = (3*x^2 + a*z^2)*(12*y^2*x*z

- (3*x^2 + a*z^2)^2) - 8*y^4*z^2

z_ = 8y^3z^3 return (x_,y_,z_)

F = GF(17) x,y,z,a = F(13),F(7),F(1),F(2) print (point_doubling(x,y,z,a))

E = EllipticCurve(GF(17),[2,2]) P = E(13,7) print (P+P)

Tính toán với Sagemath

sage: E = EllipticCurve(GF(17),[2,2]) sage: E Elliptic Curve defined by y^2 = x^3 + 2*x + 2 over Finite Field of size 17 sage: for P in E: ....: print P ....: (0 : 1 : 0) (0 : 6 : 1) (0 : 11 : 1) (3 : 1 : 1) (3 : 16 : 1)

(5 : 1 : 1) (5 : 16 : 1) (6 : 3 : 1) (6 : 14 : 1) (7 : 6 : 1) (7 : 11 : 1) (9 : 1 : 1) (9 : 16 : 1) (10 : 6 : 1) (10 : 11 : 1) (13 : 7 : 1) (13 : 10 : 1) (16 : 4 : 1) (16 : 13 : 1)

Nội dung

1. Đường cong Elliptic (Elliptic Curve, EC)

2. Bài toán Logarit rời rạc trên EC

3. Giao thức trao đổi khoá Diffie-Hellman trên EC

(

Nhóm con vòng (cyclic)

16P = (10,11) 17P = (6,14) 18P = (5,16) 19P = !

P = (5,1) 2P = (6,3) 3P = (10,6) 4P = (3,1) 5P = (9,16)

6P = (16,13) 7P = (0,6) 8P = (13,7) 9P = (7,6) 10P = (7,11)

11P = (13,10) 12P = (0,11) 13P = (16,4) 14P = (9,1) 15P = (3,16)

Định lý. Các điểm trên đường cong Elliptic cùng với điểm 0 có nhóm con vòng. Dưới một số điều kiện các điểm trên EC lập thành một nhóm vòng.

E: y2 = x3 + 2x + 2 mod 17

Tính logP(Q) với P = (5,1) và Q = (10,11)

11P = (13,10) 12P = (0,11) 13P = (16,4) 14P = (9,1) 15P = (3,16) 16P = (10,11) 17P = (6,14) 18P = (5,16) 19P = !

P = (5,1) 2P = (6,3) 3P = (10,6) 4P = (3,1) 5P = (9,16) 6P = (16,13) 7P = (0,6) 8P = (13,7) 9P = (7,6) 10P = (7,11)

E: y2 = x3 + 2x + 2 mod 17

9.1 How to Compute with Elliptic Curves

241

solutions of the equations. For example, the point (x = r, y = 0) fulﬁlls the equation

of a circle and is, thus, in the set. The point (x = r/2, y = r/2) is not a solution to the

polynomial x2 + y2 = r2 and is, thus, not a set member. An elliptic curve is a special

type of polynomial equation. For cryptographic use, we need to consider the curve

not over the real numbers but over a ﬁnite ﬁeld. The most popular choice is prime

ﬁelds GF(p) (cf. Sect. 4.2), where all arithmetic is performed modulo a prime p.

Deﬁnition 9.1.1 Elliptic Curve

The elliptic curve over Zp, p > 3, is the set of all pairs (x, y)

∈

which fulﬁll

(9.1)

x3 + a

x + b mod p

≡

together with an imaginary point of inﬁnity O, where

a, b

∈

and the condition 4

a3 + 27

= 0 mod p.

The deﬁnition of elliptic curve requires that the curve is nonsingular. Geometri-

cally speaking, this means that the plot has no self-intersections or vertices, which

is achieved if the discriminant of the curve

16(4a3 + 27b2) is nonzero.

−

For cryptographic use we are interested in studying the curve over a prime ﬁeld

as in the deﬁnition. However, if we plot such an elliptic curve over Zp, we do not get

anything remotely resembling a curve. However, nothing prevents us from taking an elliptic curve equation and plotting it over the set of real numbers.

3x + 3 is shown over the real

−

Example 9.3. In Figure 9.3 the elliptic curve y2 = x3 numbers.

Bài toán logarit rời rạc trên EC (ECDLP)

ĐN. Cho đường cong elliptic 1. Ta xét một điểm # và điểm khác 2. Bài toán DL nhằm tìm số nguyên 3 thoả mãn

P + P +

+ P

= dP = T.

AAACKHicbVBNS8NAEN342davqkcvi0UQhJKooBex6MVjhVaFppTNZtoubjZhdyKWkJ/jxb/iRUSRXv0lbmoPfj2Y5e2bGWbmBYkUBl137MzMzs0vLJbKlaXlldW16vrGlYlTzaHNYxnrm4AZkEJBGwVKuEk0sCiQcB3cnhf56zvQRsSqhaMEuhEbKNEXnKGVetXTsp+qEHSgGYesSfdoET4PYzTFJ+9lIfUR7jGjKCIweU5PaNi0T6teLld61Zpbdyegf4k3JTUyRbNXffHDmKcRKOSSGdPx3AS7GdMouIS84qcGEsZv2QA6lipmZ3azyaE53bFKSPuxtqGQTtTvHRmLjBlFga2MGA7N71wh/pfrpNg/7mZCJSmC4l+D+qmkGNPCNRoKDRzlyBLGtbC7Uj5k1jO03hYmeL9P/kuu9uveQX3/8rDWOJvaUSJbZJvsEo8ckQa5IE3SJpw8kCfySt6cR+fZeXfGX6UzzrRnk/yA8/EJ+lCiyQ==

· · · d (cid:105)(cid:66)(cid:75)(cid:50)(cid:98)

{z

}

|

Fig. 9.3 y2 = x3

3x + 3 over R

−

Bài tập

Xét đường cong

E: y2 = x3 + 2x + 2 mod 17

Ta đã tính các “mũ” của P.

16P = (10,11) 17P = (6,14) 18P = (5,16) 19P = :

P = (5,1) 2P = (6,3) 3P = (10,6) 4P = (3,1) 5P = (9,16)

6P = (16,13) 7P = (0,6) 8P = (13,7) 9P = (7,6) 10P = (7,11)

11P = (13,10) 12P = (0,11) 13P = (16,4) 14P = (9,1) 15P = (3,16)

Với P = (5,1) và T = (16,4), hãy tìm số nguyên d sao cho P = T.

Số điểm của EC

Hass’s Theorem: Cho đường cong > modun ?, số điểm trên đường cong ký hiệu bởi #> và bị chặn bởi:

? + 1 − ? ≤ #> ≤ ? + 1 + 2 ?

• #E ≈ p

• Nếu ta cần một đường cong với số điểm 2160 ta phải sử dụng số

nguyên tố cỡ 160 bit

Tính an toàn

• Mọi giao thức EC dựa trên tính khó giải của bài toán ECDLP • Nếu EC được chọn cẩn thận, thuật toán tốt nhất để tính

ECDLP cần ≈ ; bước.

• VD: p ≈ 2160

tấn công cần ≈ 2160 = 280 bước

Nội dung

1. Đường cong Elliptic (Elliptic Curve, EC)

2. Bài toán Logarit rời rạc trên EC

3. Giao thức trao đổi khoá Diffie-Hellman trên EC

Pha 1: Tham số miền cho ECDH

1.Chọn một số nguyên tố p và đường cong

#! = %" + 6% + 7 mod ;

2. Chọn điểm P = (xP, yP) trên đường cong

Pha 2: Trao đổi khoá

Alice

Bob

Chọn b ∈ {1,…,#E -1}

Chọn a ∈{2,…, #E -1}

A = a P

B = bP

= bA = b(aP)

aB = a(bP) =

kAB = abP

Phép nhân với hằng số

Trường hợp tồi nhất: 31P = 2(2(2(2P +P )+P )+P )+P .

def scalarmult(n,P):

Trường hợp trung bình: 35P = 2(2(2(2(2P))) + P) + P.

4 phép nhân đôi; 4 phép cộng.

if n == 0: return 0 if n == 1: return P R = scalarmult(n//2,P) R=R+R if n % 2: R = R + P return R

5 phép nhân đôi; 2 phép cộng. Thời gian CPU bị chặn bởi

log2 (n)

lần nhân đôi điểm

Tính an toàn của giao thức trao đổi khoá Diffie Hellman

• Kẻ tấn công nhìn thấy giá trị aP và bP • Và phải tính giá trị Kab = abP • Khó khăn của tính toán được dẫn từ hai bài toán được tin là khó

Bài toán quyết định (DDH): • Cho (P, aP, bP, cP), hãy kiểm tra liệu ab == c.

Bài toán tính toán Diffie Hellman (CDH): • Cho (P, aP, bP), hãy tính abP.

DLP è DH

Quyết định Diffie Hellman (DDH): • Cho (P, aP, bP, cP), kiểm tra liệu ab == c

Tính toán Diffie Hellman (CDH): • Cho (P, aP, bP), hãy tính abP.

Nhiều người tin là ”đúng”

Bài toán logarit rời rạc (DLP) • Cho (P, aP), hãy tính a

Giả sử tính toán Diffie Hellman

Giả sử tính toán DH đúng trong E nếu: P, aP , bP ⇏ abP

với mọi thuật toán hiệu quả A:

Pr[ A(P, aP, bP ) = abP ] < rất nhỏ

với P ⟵ {phần tử sinh của E} , a, b ⟵ Zn

Đường cong P256

Đường cong có dạng

y2 = x3 – 3x + b mod p

• Số nguyên tố p = 2256 – 2224 + 2192 + 296 - 1 • và b ở hexa là: b := 5ac635d8 aa3a93e7 b3ebbd55 769886bc 651d06b0

cc53b0f6 3bce3c3e

• Số nguyên tố gần bằng 2256, số điểm gần bằng 2256. • Tính logarit rời rạc mất khoảng 2128 bước • Tham số b trong P256 được chọn thế nào? • P256 được dùng rộng rãi trong thực tế

P256 trên Sagemath

sage: p = 2^256 - 2^224 + 2^192 + 2^96 -1 sage: is_prime(p) True sage: b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e sage: b 9559645253501865577261459496814587248748736692591040757213546036286 sage: P256 = EllipticCurve(GF(p), [-3,b]) sage: P256.order() 115792089210356248762697446949407573530139109078099854062854297063875752950436 sage: P= P256.random_element() sage: P (44003593087052944491133812927777446441384567907740211507216944250174958576726 : 5520086247573023097393606373907129377872093705027768026391600457848619693219 : 1)