Hanoi University of Science and Technology

GRADUATE THESIS
XÂY DỰNG THUẬT TOÁN TRAO ĐỔI KHĨA DỰA VÀO
TÍNH TỐN CẶP TATE TRÊN ĐƯỜNG CONG ELLIPTIC

Master of Science: Nguyen Thanh Long

HÀ NỘI


iii

MỤC LỤC
LỜI CẢM ƠN ........................................................................................................ i
LỜI CAM ĐOAN ................................................................................................. ii
MỤC LỤC ............................................................................................................iii
CÁC KÝ HIỆU, CHỮ VIẾT TẮT...................................................................... v
DANH MỤC BẢNG BIỂU ................................................................................. vi
DANH MỤC HÌNH VẼ ..................................................................................... vii
LỜI MỞ ĐẦU ....................................................................................................... 1
Chƣơng 1
TỔNG QUAN VỀ ĐƢỜNG CONG ELLIPTIC
1.1. Tổng quan và ứng dụng của đƣờng cong Elliptic trên trƣờng hữu hạn............. 3
1.1.1. Định nghĩa đƣờng cong Elliptic trên trƣờng hữu hạn Fp ..................... 3
1.1.2. Một số tính chất và phép toán trên đƣờng cong Elliptic ....................... 6
1.1.3. Ứng dụng của đƣờng cong Elliptic trong mật mã ............................... 12
1.2. Tổng quan về cặp Tate trên đƣờng cong Elliptic. ..................................... 16
1.2.1. Một số tính chất của Divisor. .............................................................. 16
1.2.2. Khái niệm cặp Tate trên đƣờng cong Elliptic. .................................... 19
1.2.3. Một số tính chất và hệ quả của cặp Tate. ............................................ 23

1.2.4. Ứng dụng của cặp Tate trên đƣờng cong Elliptic trong mật mã ......... 25
1.3. Kết luận chƣơng 1 ...................................................................................... 26
Chƣơng 2
NGHIÊN CỨU THUẬT TỐN TÍNH TỐN CẶP TATE TRÊN
ĐƢỜNG CONG ELLIPTIC
2.1. Các hàm tốn học liên quan sử dụng trong tính toán cặp Tate trên
đƣờng cong Elliptic........................................................................................... 27
2.2. Xây dựng thuật tốn tính tốn cặp Tate trên đƣờng cong Elliptic. ........... 28
2.2.1. Một số tính chất và hàm liên quan trong tính tốn cặp Tate ............... 28


iv

2.2.2. Thuật tốn tính tốn cặp Tate trên đƣờng cong Elliptic ..................... 34
2.3. Chứng minh tính đúng đắn của thuật tốn tính tốn cặp Tate trên đƣờng
cong Elliptic. ..................................................................................................... 39
2.4. Kết luận chƣơng 2 ...................................................................................... 40
Chƣơng 3
XÂY DỰNG THUẬT TOÁN TRAO ĐỔI KHĨA DỰA VÀO TÍNH
TỐN CẶP TATE TRÊN ĐƢỜNG CONG ELLIPTIC
3.1. Xây dựng thuật tốn trao đổi khóa dựa vào tính tốn cặp Tate trên
đƣờng cong Elliptic........................................................................................... 41
3.2. Một số yêu cầu đảm bảo an toàn đối với thuật tốn trao đổi khóa dựa
vào tính tốn cặp Tate trên đƣờng cong Elliptic............................................... 46
3.3. Xây dựng, mơ phỏng chƣơng trình trao đổi khóa dựa vào tính tốn cặp
Tate trên đƣờng cong Elliptic trên máy tính. .................................................... 46
3.3.1. Cơng cụ lập trình ................................................................................. 46
3.3.2. Xây dựng chƣơng trình mơ phỏng trao đổi khóa dựa trên tính tốn
cặp Tate trên đƣờng cong Elliptic. ................................................................ 47
3.3.3. Kết quả chƣơng trình mơ phỏng trao đổi khóa dựa trên tính tốn

cặp Tate trên đƣờng cong Elliptic ................................................................. 52
3.3.4. Đánh giá kết quả .................................................................................. 55
3.4. Kết luận chƣơng 3 ...................................................................................... 56
KẾT LUẬN ......................................................................................................... 57
TÀI LIỆU THAM KHẢO ................................................................................. 58
PHỤ LỤC ............................................................................................................ 60


v

CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Viết tắt

ANSI

DDH

EC

ECC

ECDSA

IKE

ISO

NIST

Tiếng Anh


Tiếng Việt

American National Standards

Viện Tiêu chuẩn Quốc gia

Institute

Hoa Kỳ

Decisional Diffie-Hellman

Elliptic Curve

Elliptic Curve Cryptography

Bài toán giả định Difie Hellman
Đƣờng cong Elliptic
Hệ mật đƣờng cong
Elliptic

Elliptic Curve Digital Signature

Lƣợc đồ chữ ký số trên

Algorithm

đƣờng cong Elliptic


Internet Key Exchange

Giao thức trao đổi khóa

International Organization for

Tổ chức tiêu chuẩn hố

Standardization

quốc tế

National Institute of Standards

Viện Tiêu chuẩn và Cơng

and Technology

nghệ quốc gia Mỹ


2

Đề tài đƣợc chia làm 3 nội dung nhƣ sau:
Chƣơng 1: Tổng quan về đƣờng cong Elliptic.
Chƣơng này trình bày tổng quan về đƣờng cong Elliptic, ứng dụng của
đƣờng cong Elliptic và ứng dụng của cặp Tate trên đƣờng cong Elliptic trong
mật mã.
Chƣơng 2: Nghiên cứu thuật tốn tính tốn cặp Tate trên đƣờng
cong Elliptic.

Chƣơng này trình bày chi tiết về thuật tốn tính tốn cặp Tate trên đƣờng
cong Elliptic và cơ sở tốn học chứng minh tính đúng đắn của thuật toán.
Chƣơng 3: Xây dựng thuật toán trao đổi khóa dựa vào tính tốn
cặp Tate trên đƣờng cong Elliptic.
Chƣơng này trình bày chi tiết về thuật tốn trao đổi khóa dựa vào tính
tốn cặp Tate trên đƣờng cong Elliptic, một số yêu cầu đảm bảo an toàn đối
với thuật tốn và xây dựng chƣơng trình chạy thuật tốn trên máy tính.


3

Chƣơng 1
TỔNG QUAN VỀ ĐƢỜNG CONG ELLIPTIC
Chƣơng này trình bày tổng quan về đƣờng cong Elliptic, ứng dụng của
đƣờng cong Elliptic và ứng dụng của cặp Tate dựa trên đƣờng cong Elliptic
trong mật mã.
1.1. Tổng quan và ứng dụng của đƣờng cong Elliptic trên trƣờng hữu hạn
Mật mã đƣờng cong Elliptic đƣợc đề xuất bởi N.Kobbitz và V.Miller năm
1985. Mặc dù ra đời sau nhƣng hệ mật trên đƣờng cong Elliptic đang dần khẳng
định với nhiều ƣu thế so với các hệ mật khóa cơng khai trƣớc đó. Hiện nay nó
đƣợc rất nhiều các tổ chức viễn thơng trên thế giới nhƣ ANSI, IEEE, ISO,
NIST… chuẩn hóa thành các tiêu chuẩn cả về thuật toán và các ứng dụng.
1.1.1. Định nghĩa đường cong Elliptic trên trường hữu hạn Fp
Định nghĩa 1.1: Một đƣờng cong Elliptic dạng xạ ảnh của Weierstrass
đầy đủ trên trƣờng số hữu hạn K là tập tất cả các điểm xạ ảnh (x, y, z) thoả
mãn phƣơng trình:

y 2 z  a1xyz  a3 yz 2  x3  a2 x 2 z  a4 xz 2  a6 z 3
với a1, a2 , a3 , a4 , a6  K .
Điểm vô hạn của đƣờng cong này là   (0,1,0) .

Định nghĩa 1.2: Một đƣờng cong Elliptic dạng Affine của Weierstrass đầy
đủ trên trƣờng K là tập tất cả các điểm Affine (x, y) thoả mãn phƣơng trình:

y 2  a1xy  a3 y  x3  a2 x 2  a4 x  a6 ;
với a1, a2 , a3 , a4 , a6  K .
Điểm vô hạn của đƣờng cong đƣợc ký hiệu là 


4

Trong phạm vi đồ án này, ta chỉ xét K là một trƣờng nguyên tố Fp với
p là số nguyên tố; p  2,3 . Khi đó ta có đƣờng cong Elliptic dạng
Weierstrass rút gọn (kí hiệu là E p (a, b) hoặc E ( Fp ) ), gọi tắt là E đƣợc biểu
diễn bởi phƣơng trình:
E: y 2  x3  ax  b ; (a, b)  Fp
Định nghĩa 1.3: Biệt thức của đƣờng cong E đƣợc xác định bởi công thức:

  16(4a3  27b2 ) (mod p)
Định nghĩa 1.4: Cho f ( x)  x3  ax  b  y 2 . Điểm P( x, y )  E đƣợc gọi là
điểm khơng kì dị nếu tồn tại ít nhất một trong hai đạo hàm cấp 1 của f sao
cho:

df
df
hoặc
khác 0.
dy
dx

Nếu cả hai đạo hàm trên cùng bằng 0 thì điểm P là điểm kì dị.

Định nghĩa 1.5: Đƣờng cong Elliptic E là đƣờng cong khơng kì dị nếu tất cả
các điểm của nó khơng kì dị.
Ngƣợc lại, nếu có ít nhất một điểm kì dị thì E là đƣờng cong kì dị.
Đa thức bậc ba x3  ax  b

có nghiệm bội khi và chỉ khi

4a3  27b2  0. Nhƣ vậy, một đƣờng cong E là khơng kì dị khi và chỉ khi
  0 (mod p) .
Định nghĩa 1.6: Đại lƣợng j  bất biến của đƣờng cong E khi   0(mod p) là:
4a 3
j  j ( E )  1728 3
4a  27b 2

Định nghĩa 1.7: Cho E và E’ là hai đƣờng cong Ellliptic trên trƣờng K đƣợc
xác định bởi phƣơng trình Weierstrass rút gọn, tƣơng ứng với các biến số


5

( x, y) và ( x ', y ') đƣợc gọi là đẳng cấu trên trƣờng K khi và chỉ khi tồn tại các
hằng r, s, t  K và u  K * sao cho: với phép biến đổi song ánh x  u 2 x ' r ;

y  u 3 y ' su 2  t thì E biến thành E ' .
Khi hai đƣờng cong đẳng cấu theo định nghĩa 1.7 thì nó sẽ có giá trị

j  bất biến bằng nhau. Có hai giá trị đặc biệt của j  bất biến là:
- j  0: Khi đó đƣờng cong Elliptic có dạng y 2  x3  b .
- j  1728: Đƣờng cong Elliptic có dạng y 2  x3  ax .
Các đƣờng cong với j  0 và j  1728 là đặc biệt, chúng có các tự

đẳng cấu (tức là một song ánh có thể biến đổi từ đƣờng cong vào chính nó).
-

y 2  x3  b có một đồng cấu ( x, y)

( x,  y) với  là căn bậc ba

không tầm thƣờng của 1.
-

y 2  x3  ax có một đồng cấu ( x, y)

( x, iy ) , với i 2  1.

Định nghĩa 1.8: Nếu hai đƣờng cong Elliptic khác nhau đƣợc xác định trên
một trƣờng K có cùng một j  bất biến thì ta gọi chúng là “xoắn đơi-twist”
của nhau.
Đƣờng cong xoắn đơi theo định nghĩa 1.8 có dạng:

y 2  x3 

3j
2j
x
; j  1728
1728  j
1728  j

Định nghĩa 1.9: Cấp của một đƣờng cong Elliptic trên trƣờng Fp là số điểm
của E (kể cả điểm  ) và đƣợc ký hiệu là # E ( Fp ) .

Theo định lý Hasse ta có:

p  1  2 p  # E( Fp )  p  1  2 p


6

Định nghĩa 1.10: Đƣờng cong Elliptic E định nghĩa trên Fp đƣợc gọi là đƣờng
cong siêu kì dị nếu khơng có điểm cấp p trên Fp .
Định nghĩa 1.11: Đƣờng cong Elliptic E định nghĩa trên Fp thỏa mãn

# E ( Fp )  p đƣợc gọi là đƣờng cong kì dị.
Định nghĩa 1.12: Cho E là đƣờng cong Elliptic trên trƣờng Fp , P là điểm
thuộc E. Khi đó, n đƣợc gọi là cấp của điểm P khi và chỉ khi n là số nguyên
dƣơng nhỏ nhất thỏa mãn nP   .
Bài toán Logarit rời rạc trên đường cong Elliptic (ECDLP).
Phát biểu bài toán: Cho E là một đƣờng cong Elliptic và G  E là một điểm
có cấp n, điểm P  E . Hãy tìm số nguyên dƣơng x (với 2  x  n  2 ) sao
cho P  xG .
Hiện nay, chƣa có thuật toán nào đƣợc coi là hiệu quả để giải bài toán
này. Để giải bài toán logarit rời rạc trên đƣờng cong Elliptic cần phải kiểm tra
tất cả các giá trị của x [2, n  2] . Nếu điểm G đƣợc chọn với cấp n rất lớn thì
việc giải bài tốn ECDLP xem nhƣ khơng khả thi.
1.1.2. Một số tính chất và phép tốn trên đường cong Elliptic
1.1.3.1. Phép cộng điểm
Tập hợp các điểm ( x, y) với x, y  Fp thỏa mãn phƣơng trình của
đƣờng cong E và một điểm  cùng với một phép toán cộng sẽ tạo thành một
nhóm gọi là nhóm các điểm trên đƣờng cong Elliptic trong trƣờng Fp ký hiệu
là E ( Fp ) .



7

Cho E là một đƣờng cong Elliptic xác định bởi phƣơng trình

y 2  x3  ax  b . Gọi P  ( x1, y1 ) và Q  ( x2 , y2 ) là các điểm trên E với

P, Q   .
Khi đó:
Phép cộng hai điểm: Cho hai điểm P và Q phân biệt trên đƣờng cong
Elliptic E. Tổng của P và Q ký hiệu là R, đƣợc định nghĩa nhƣ sau:
Kẻ một đƣờng đi qua P và Q. Đƣờng thẳng này cắt E tại điểm R ' . Tiếp
tục kẻ đƣờng thẳng đi qua R ' vng góc với trục x, đƣờng thẳng này cắt E tại
điểm thứ hai chính là điểm P  Q  R .
y

R’
Q
P
x

P+Q=R

Hình 1.1: Phép cộng hai điểm P + Q = R
Cụ thể P  Q  R  ( x3 , y3 ) với ( x3 , y3 ) đƣợc tính nhƣ sau:
+ Nếu x1  x2 thì:
 x3   2  x1  x2 (mod p)

 y3   ( x1  x3 )  y1 (mod p)



8

Trong đó,  

y1  y2
(mod p) .
x1  x2

+ Nếu x1  x2 và y1  y2 thì P  Q   .
Phép nhân 2P: Cho một điểm P là một điểm trên E . Phép nhân đôi
điểm P ký hiệu là P  P  2P đƣợc định nghĩa nhƣ sau:
Kẻ qua P một tiếp tuyến của E, tiếp tuyến này cắt E tại điểm R ' . Ta kẻ
đƣờng thẳng qua điểm R ' vng góc với trục x, đƣờng thẳng này cắt E tại
điểm thứ hai chính là 2P.
y

P + P = 2P

P

x

R’

Hình 1.2: Phép nhân 2P = P + P
Cụ thể 2P  ( x3 , y3 ) với ( x3 , y3 ) đƣợc tính nhƣ sau:
+ Nếu y1  0 thì 2P   .
+ Nếu y1  0 thì
 x3   2  2 x1 (mod p)


 y3   ( x1  x3 )  y1 (mod p)


9

Trong đó,  

3x12  a
 mod p  .
2 y1

Luật nhóm: Đƣờng cong Elliptic E trên trƣờng số hữu hạn Fp với phép tốn
cộng điểm thỏa mãn các tính chất sau:
(1) Tính giao hốn: P1  P2  P2  P1 với mọi P1 , P2 trên E.
(2) Tồn tại phần tử đơn vị: P    P với mọi P trên E.
(3) Tồn tại phần tử nghịch đảo: Với điểm P cho trƣớc trên E, tồn tại một
điểm P ' trên E sao cho P  P '   . Điểm P ' đƣợc ký hiệu là –P.
(4) Tính kết hợp: ( P1  P2 )  P3  P1  (P2  P3 ) P1, P2 , P3  E .
1.1.3.2. Phép nhân điểm kP.
Phép nhân điểm với số nguyên k .P (với k là số nguyên) đƣợc thực hiện
bằng cách cộng liên tiếp P  P  ...  P .
k

Để tính tốn k .P , ta chỉ cần cộng P với chính nó k  1 lần, kết quả là
một điểm Q trên đƣờng cong. Một phƣơng pháp để thực hiện nhân điểm đó là
sử dụng phép cộng điểm và phép nhân đơi điểm lặp đi lặp lại nhiều lần.
Phƣơng pháp này gọi là “nhân đơi và cộng”. Sau đây là một ví dụ đơn giản của
phép nhân điểm:
Ví dụ 1: Cho P   3,10  E23 1,1 . Tính 2P.

Ta có:
2P  P  P  ( x1, y1 )  ( x1, y1 )

Đặt 2P  ( x3 , y3 ) . Khi đó:

3x12  a
3.32  1
5

( mod q) 

 41 (mod23)  6
2 y1
2.10
20


10

2
2

 x3     x1  x2  (mod q)  (6  3  3)  30 (mod 23)  7


 y3  ( ( x1  x3 )  y1 ) (mod q)  (6(3  7)  10)  34 ( mod 23)  12

Bởi vậy 2P = (x3, y3) = (7, 12)
Phép nhân kP nhận đƣợc bằng cách thực hiện liên tiếp các phép cộng
ta có kết quả ở bảng 1.1 sau:

Bảng 1.1: Kết quả của phép nhân kP trên GF(23)

k

 y2  y1
khi P  Q

x

x
   2 2 1
 3x1  a khi P  Q
 2y
1


x3 



kP
y3 
 2  x1  x2 mod 23 ( ( x1  x3 )  y1 ) mod 23  (x 3 , y3 )



1

(3, 10)


2

6

7

12

(7, 12)

3

12

19

5

(19, 5)

4

4

17

3

(17, 3)


5

11

9

4

(9, 16)

6

1

12

4

(12, 4)

7

7

11

3

(11, 3)


8

2

13

16

(13,16)

9

19

0

1

(0, 1)


11

k

 y2  y1
khi P  Q

 x2  x1
  2

 3x1  a khi P  Q
 2y
1


x3 



kP
y3 
  x1  x2 mod 23 ( ( x1  x3 )  y1 ) mod 23  (x 3 , y3 )



2

10

3

6

4

(6, 4)

11

21


18

20

(12,20)

12

16

5

4

(5, 4)

13

20

1

7

(1, 7)

14

13


4

0

(5, 19)

15

13

1

16

(18, 3)

16

20

5

19

(5, 19)

17

16


18

3

(18, 3)

18

21

6

19

(6, 19)

19

3

0

22

(0, 22)

20

19


13

7

(13, 7)

21

2

11

20

(11, 2)

22

7

12

19

(12, 19)

23

1


9

7

(9, 7)


12

k

 y2  y1
khi P  Q

 x2  x1
  2
 3x1  a khi P  Q
 2y
1


x3 



kP
y3 
  x1  x2 mod 23 ( ( x1  x3 )  y1 ) mod 23  (x 3 , y3 )




2

24

11

17

20

(17, 20)

25

4

19

18

(19, 18)

26

12

7


11

(7, 11)

27

6

3

13

(3, 13)

1.1.3. Ứng dụng của đường cong Elliptic trong mật mã
Đƣờng cong Elliptic đƣợc ứng dụng phổ biến trong lĩnh vực mật mã.
Cụ thể nó có thể đƣợc dùng để xây dựng hệ mật đƣờng cong Elliptic, xây
dựng các giao thức trao đổi khóa, ký số.
- Xây dựng hệ mật đường cong Elliptic:
Đầu mối A
D A = aA

Mã hóa

R

PM = kG(PR +kPB)

Lấy EB
Cơng bố EA


M

Kênh
truyền tin

Giải mã

M

PR = (PR +kPB) – aB(kG)

Đầu mối B

R

D B = aB

Nguồn khóa
Tham số chung của hệ mật ECC
Ep(a,b), G
Khóa cơng khai
EA = PA

EB = PB

Cơng bố EB

Hình 1.3: Sơ đồ hoạt động của hệ mật trên đƣờng cong Elliptic



13

Theo sơ đồ hoạt động của hệ mật đƣờng cong Elliptic, đầu mối A cần
truyền thông báo mật R cho đầu mối B qua kênh truyền tin, có sử dụng hệ mật
đƣờng cong Elliptic để bảo mật thông tin. Khi đó, hệ mật đƣờng cong Elliptic
đƣợc xây dựng nhƣ sau:
Sinh tham số chung cho hệ mật: Khi sử dụng hệ mật đƣờng cong
Elliptic để bảo vệ thông tin cho mạng liên lạc, các tham số sau đây phải đƣợc
quy ƣớc chung cho hệ mật:
- Chọn một đƣờng cong Elliptic E p (a, b) .
- Chọn điểm sinh G  Fp (a, b) có cấp n. Để đảm bảo an tồn thì n phải là
một số nguyên tố lớn.
- Các tham số của hệ mật: Đƣờng cong E p (a, b) và điểm sinh

G  E p (a, b) đƣợc công khai.
Trong hệ mật này mỗi bản rõ R sẽ đƣợc biểu diễn lại thành một điểm

PR trong tập hữu hạn các điểm của nhóm E p (a, b) mà nhờ nó chúng ta có thể
thực hiện đƣợc các tính tốn trên E p (a, b) .
Lược đồ tạo khóa: Mỗi đầu mối liên lạc (mỗi ngƣời dùng) tạo một cặp
khóa bao gồm một khóa cơng khai và một khóa riêng bí mật tƣơng ứng theo
các bƣớc sau:
1. Chọn một số nguyên ngẫu nhiên a, 2  a  n  2 .
2. Tính giá trị của điểm P nhƣ sau: P = a.G.
3. Đặt K  {(a, P) : P  aG} ta có khóa cơng khai là EK  P , khóa riêng
bí mật là DK  a .


14


Lược đồ mã hóa: A phải mã hóa bản rõ R để tạo bản mã M gửi cho B
theo các bƣớc sau:
1. Nhận khóa cơng khai EB  PB của B.
2. Biểu diễn rõ R thành một điểm PR trong tập hữu hạn các điểm của
nhóm E p (a, b) .
3. Chọn số nguyên bí mật k, 2  k  n  2 .
4. Tính cặp điểm của bản mã PM bằng cách dùng khóa cơng khai PB của B:
PM  [(kG), ( PR  kPB )]

5. Gửi cặp điểm bản mã PM cho B.
Lược đồ giải mã: Để khôi phục bản rõ R từ bản mã PM đã nhận, B phải
dùng khóa riêng DB  aB và thực hiện phép tính sau:
1. Nhân điểm thứ nhất (k.G) với khóa riêng aB của B và lấy kết quả
nhận đƣợc trừ đi điểm thứ 2 trong cặp điểm của PM :
( PR  kPB )  aB (kG)  ( PR  ka B G)  aB (kG)  PR

Đây chính là điểm tƣơng ứng với bản rõ R. Chỉ có B mới có khóa riêng
aB và mới có thể tách aB (kG) khỏi điểm thứ hai của PM để thu thông tin về

bản rõ PR .
2. Ánh xạ điểm - điểm bản rõ PR trở lại thông báo gốc R.
- Ứng dụng đường cong Elliptic để xây dựng lược đồ trao đổi khóa.
Đƣờng cong Elliptic E xác định trên trƣờng hữu hạn Fq đƣợc công bố
công khai. Điểm P  E cũng đƣợc công bố công khai. P không nhất thiết phải
là phần tử sinh của E nhƣng cần phải có bậc lớn.


15


1. Alice chọn số nguyên dƣơng a có độ lớn cùng cỡ với q và công bố
công khai điểm aP  E .
2. Bob chọn số nguyên dƣơng b tƣơng tự với cách làm của Alice và
công bố công khai điểm bP  E .
3. Alice tính Ka  a(bP)  abP , Bob tính Kb  b(aP)  abP  E và sử
dụng K  K a  Kb nhƣ là khóa phiên chung với nhau.
- Xây dựng lược đồ chữ ký số trên đường cong Elliptic - ECDSA.
a) Lƣợc đồ ký ECDSA.
Alice muốn ký thông báo m là một số nguyên dƣơng thì Alice chọn
đƣờng cong Elliptic E trên trƣờng hữu hạn Fq sao cho # E( Fq )  r , với r là số
nguyên tố lớn.
Alice chọn điểm sinh G của E trên Fq có bậc r. Cuối cùng Alice chọn số
nguyên dƣơng a và tính Q  aG .
Alice công bố công khai các thông tin sau: Fq, E, r, G, Q.
Alice tạo chữ ký số:
1. Alice chọn số nguyên dƣơng ngẫu nhiên k với 1  k  r và tính

R  kG  ( x, y).
2. Alice tính s  k 1 (m  ax) (mod r ) và tài liệu ký là (m,R,s).
Bob kiểm tra chữ ký số:
1. Bob tính u1  s 1m (mod r ) và u2  s 1x (mod r )
2. Bob tính V  u1G  u2Q
3. Bob tuyên bố chữ ký hợp lệ nếu V  R .
Độ an toàn của sơ đồ ký EDCSA dựa trên bài toán logarit rời rạc trên
đƣờng cong Elliptic. Cho đến nay, các hệ mã hóa đƣờng cong Elliptic đã đƣợc


16

chỉ ra là rất an toàn và hiệu quả. Đối với bài tốn logarit rời rạc đƣờng cong

Elliptic thì có nhiều thuật tốn giải nó. Tuy nhiên chƣa có thuật tốn nào có
độ phức tạp tính tốn trong thời gian đa thức.
1.2. Tổng quan về cặp Tate trên đƣờng cong Elliptic.
1.2.1. Một số tính chất của Divisor.
Định nghĩa 1.13:

 

1) Cho E là một đƣờng cong Elliptic xác định trên trƣờng K, P  E K .
Một Divisor trên E là tổ hợp tuyến tính của hữu hạn các phần tử với các hệ số
nguyên của các kí hiệu [P]:

D   a j [ Pj ]
j

trong đó [Pj ] là công thức ký hiệu của Pj , a j  Z .
2) Bậc (degree) và Tổng (sum) của một Divisor đƣợc cho bởi công thức:

deg( a j [Pj ])   a j  Z
j

j

sum( a j [Pj ])   a j Pj  E ( K )
j

j

3) Nếu f là hàm không đồng nhất bằng 0 trên E, thì định nghĩa của hàm f là


div( f ) 



PE ( K )

ord P ( f )[ P]

Trong đó, ord ( f )  r đƣợc gọi là cấp của hàm f tại điểm P khi f có dạng
u r P g thỏa mãn điều kiện: r  Z , g ( P)  0,  và uP ( P)  0

Hàm uP đƣợc biến đổi từ f nhƣ trên thỏa mãn uP ( P)  0 là phép biến
đổi đƣợc gọi là dạng uniformizer tại P.


17

Ví dụ 2: Đƣờng cong E: y 2  x3  x . Tính uniformizer của hàm y tại điểm
P=(0,0) trong hai trƣờng hợp sau:
a) Ta có: f ( x, y )  x  y 2

1
1
 0,  tại (0,0). Nên
và
x2  1
x2  1

r=2


(1)

Đặt P  ( x, y)
Ta có uP ( P)  y . Suy ra
uP (0,0)  0 ,

(2)

nên uP ( P)  y là dạng uniformizer tại điểm (0,0).
Ta có g ( x, y ) 

1
. Suy ra
x 1
2

g (0,0) 

1
 1  0
0 1
2

(3)

Từ (1), (2), (3) suy ra:

ord(0,0) ( x)  2
b) Tƣơng tự:


ord(0,0) ( x / y)  1

Một số tính chất của Divisor:
Mệnh đề 1.1: Cho E là một đƣờng cong Elliptic và f là một hàm số không
đồng nhất bằng 0 trên E. Khi đó
1. f chỉ có hữu hạn các không điểm và điểm cực (điểm cực của f tại P
nghĩa là hàm f nhận giá trị  tại P và không điểm của f tại P nghĩa
là f nhận giá trị 0 tại P).
2. deg(div(f)) = 0


18

3. Nếu f khơng có điểm cực hoặc khơng điểm (div(f) = 0) thì f là một
hằng số.
Divisor của hàm số đƣợc gọi là Divisor chính.
Giả sử P1, P2, P3 là 3 điểm trên E và nằm trên đƣờng thẳng ax + by + c = 0 thì
hàm số f(x, y) = ax + by + c có các khơng điểm tại P1, P2, P3.
Nếu b  0 thì f có một điểm cực bội 3 tại  . Nhƣ vậy,
div(ax + by + c) = [P1] + [P2] + [P3] – 3[]
Đƣờng thẳng đi qua P3 = (x3, y3) và –P3 là x – x3 = 0. Divisor của nó là
div(x – x3) = [P3] + [-P3] – 2[]
Vì thế,
 ax  by  c 
div 
 = div(ax + by + c) – div(x – x3)
 x  x3 

= [P1] + [P2] – [-P3] – []
Do P1 + P2 = -P3 nên ta có thể viết lại nhƣ sau:

 ax  by  c 
[P1] + [P2] = [P1 + P2] + [] + div 

 x  x3 

Định lý 1.1: Cho E là đƣờng cong Elliptic. D là một Divisor trên E với
deg  D   0 . Khi đó, tồn tại một hàm f trên E thoả mãn

div(f) = D
khi và chỉ khi

sum( D)   .


19

1.2.2. Khái niệm cặp Tate trên đường cong Elliptic.
Định nghĩa 1.14: Cho E là đƣờng cong Elliptic trên một trƣờng K và n là số
nguyên không chia hết cho đặc số của K. Khi đó En

Zn  Zn . Ta có tập:

n  {x  K | x n  1}
là nhóm các căn bậc n của phần tử đơn vị trong K .
Vì đặc số của K khơng chia hết cho n, nên phƣơng trình x n  1 khơng
có nghiệm bội, nên có n nghiệm trong K . Do đó n là nhóm Cyclic bậc n.
Vậy một phần tử sinh  của n đƣợc gọi là căn nguyên thủy bậc n.
Điều này tƣơng đƣơng với  k  1 khi và chỉ khi n chia hết cho k.
Định lý 1.2: Cho E là đƣờng cong Elliptic trên trƣờng Fq . n là số nguyên sao
cho n | (q  1) . E(Fq)[n] là tập hợp các phần tử của E( Fq ) có cấp chia hết cho

n, n  {x  Fq | xn  1} . Giả sử E ( Fq ) chứa phần tử cấp n. Khi đó tồn tại cặp
song tuyến tính khơng suy biến:

.,. n : E ( Fq )[n]  E ( Fq ) / nE ( Fq )  Fq / ( Fq ) n
và

 n : E ( Fq )[n]  E ( Fq ) / nE( Fq )  n
Vì mỗi phần tử của E ( Fq ) / nE ( Fq ) có dạng Q  nE ( Fq ) . Để đơn giản
về mặt kỹ thuật, thay cho ký hiệu P, Q  nE ( Fq )
ký hiệu lại P, Q

n

n

và  n ( P, Q  nE ( Fq )n ) , ta

và  n ( P, Q) .

Chứng minh: Ánh xạ thứ nhất đƣợc xây dựng nhƣ sau:


20

P  E ( Fq )[n] .

Cho

là Divisor sao cho deg  DP   0 và


DP

sum( DP )  P . Khi đó:
deg ( DP  [P]  [])  0

 sum( DP  [P]  []) = 

đó là Divisor của một hàm (định lý 1.1). Do đó, DP tƣơng đƣơng với [P] []
mod Divisor chính. Theo định lý 1.1 tồn tại hàm f sao cho
div( f )  nDP

Đặt DQ   ai [Qi ] là Divisor deg ( DQ )  0 và sum( DQ )  Q sao cho DP, DQ
i

khơng có các điểm chung. Khi đó
P, Q

n

 f ( DQ ) (mod ( Fq )n ) .

Ở đây, f là hàm bất kỳ mà Divisor khơng có các điểm chung với DQ.
Thật vậy: giả sử có hàm các hàm f1, f 2 cùng thỏa mãn công thức trên,
tức là div( f1 )  div( f 2 )  nDP thì f1 và f2 sai khác nhau bởi một hằng số.
Khi đó:

f ( DQ )   f (Qi )ai
i

Chú ý nó khơng phụ thuộc chọn DP, hàm f đƣợc xác định trên tích với một

hằng số. Vì 0  deg( DQ )   ai , nên bất kỳ hằng số nào cũng sẽ bị triệt tiêu
i

trong định nghĩa của cặp.
Ý tưởng chứng minh định lý 1.2: Hàm f đƣợc xác định trên Fq . Giá trị của
ánh xạ bắt buộc phải thuộc Fq . Điều này đƣợc chứng minh nhƣ sau: Xét


21

  G  Gal ( Fq / Fq ) , ( Gal ( Fq / Fq ) là nhóm Galois của Fq / Fq [10]). Cho
DP  [P]  [] . Vì  ( DP )  DP , do đó f  có cùng Divisor nhƣ f, nên f  / f




là hằng c  F q , nên tồn tại c1  F q sao cho c  c1 / c1,   G . Nghĩa là

f / c1 là cố định bởi mọi  , nên xác định trên Fq . Do đó f / c1 có cùng
Divisor nhƣ f.
Giả sử f xác định trên Fq . Đặt R là điểm bất kỳ thuộc E ( Fq ) và

DQ  [Q  R]  [R] , thì Q  R và R có các tọa độ trong Fq , do đó

f ( DQ )  f (Q  R) / f ( R)  Fq
Ta chứng minh ánh xạ thứ nhất không phụ thuộc vào việc chọn DP và DQ.
Thật vậy: Giả sử DP' và DQ' là các Divisor sao cho
'
'


deg( DP )  deg( DQ )  0

'
'

 sum( DP )  P, sum( DQ )  Q

Với các hàm g và h, ta có

DP'  DP  div( g ) , DQ'  DQ  div(h)
để đơn giản giả thiết g,h đƣợc định nghĩa trên Fq và tất cả các điểm trong
Divisor DP' , DQ' thuộc E ( Fq ) . Ta có div( f ')  nDP' với f ' là một hàm. Do đó

div( f ')  div( fg n ) ,
và

f '  cfg n , với c là hằng số.
Khi đó ta có: P, Q

'
n

 f '( DQ' )  f ( DQ' ) g (DQ' )n  f (DQ ) f (div (h ))g (DQ' )n .


22

Bổ đề 1.1: Cho f và h là hai hàm trên E và giả thiết rằng div( f ) và div(h)
khơng có các điểm chung. Khi đó


f (div(h))  h(div( f ))
Theo kết quả của bổ đề này ta có
P, Q

'
n

= f ( DQ )h(div( f )) g ( DQ' ) n
= f ( DQ )h( DP )n g ( DQ' )n
 P, Q

n

(mod( Fq ))

Do đó ánh xạ này khơng phụ thuộc vào chọn DP và DQ.
Chứng minh tính song tuyến tính:
+) Cho các điểm Q1, Q2  E ( Fq )[n] với DQ1 , DQ2 là các Divisor tƣơng ứng. Khi
đó

DQ1  DQ2 ~ [Q1 ]  []  [Q2 ]  [] ~ [Q1  Q2 ]  []
ở đây ~ là ký hiệu lớp tƣơng đƣơng của các Divisor mod Divisor chính. Do đó
P, Q1  Q2

n

 f ( DQ1 Q2 )  f ( DQ1 ) f ( DQ2 )  P, Q1 n . P, Q2

n


Điều này chứng minh tính tuyến tính theo biến thứ 2.
+) Cho P1, P2  E ( Fq )[n] và DP1 , DP2 là các Divisor tƣơng ứng với f1, f 2 là các
hàm tƣơng ứng, khi đó:

DP1  DP2 ~ [P1 ]  []  [ P2 ]  [] ~ [P1  P2 ]  []
nên

DP1  P2  DP1  DP2 và div( f1 f 2 )  nDP1  nDP2  nDP1  P2