Cấu trúc môđun của tập điểm có bậc hữu hạn trên đường cong elliptic và ứng dụng trong mật mã

Journal of Science – 2015, Vol. 8 (4), 10 – 21

Part D: Natural Sciences, Technology and Environment

CẤU TRÚC MÔĐUN CỦA TẬP ĐIỂM CÓ BẬC HỮU HẠN TRÊN ĐƯỜNG CONG
ELLIPTIC VÀ ỨNG DỤNG TRONG MẬT MÃ
Võ Anh Tuấn1
1

ThS. Trường Đại học An Giang
Thông tin chung:
Ngày nhận bài: 30/12/14
Ngày nhận kết quả bình duyệt:
15/02/15
Ngày chấp nhận đăng: 12/15

ABSTRACT

Title:
Module structure of the set of
points having finite order on
elliptic curve and application in
cryptography

Weierstrass form over

Từ khóa:
Đường cong elliptic không kỳ
dị, điểm có bậc hữu hạn, cấu
trúc module, mật mã
Keywords:
Nonsingular elliptic curve, the
point has finite order, the
module structure, cryptography

The main aim of this article is describing module structure of the set of the points
P on elliptic curve which satisfy nP=O. In this set, P is the point having finite
order on nonsingular elliptic curve E. The elliptic’s equation is given by

p

field (p is a prime number greater than 3) and O is

the point at infinity. The set of the points which satisfy this condition is a subgroup
and its structure is a

 n  module. Beside this new  n  module structure,

this article also describes a new encryption method based on this structure by
maple 13.0 software.

TÓM TẮT
Mục đích chính của bài báo này là mô tả cấu trúc môđun của tập hợp những điểm
P nằm trên đường cong elliptic thỏa mãn điều kiện nP=O. Trong đó, P là điểm
có bậc hữu hạn trên đường cong elliptic E không kỳ dị, phương trình của đường
cong elliptic E được cho bởi dạng Weierstrass trên trường  p (là số nguyên tố
lớn hơn 3), O là điểm tại vô cùng. Tập hợp những điểm mà nó thỏa mãn điều kiện
này là một nhóm con và cấu trúc của nó là  n  môđun. Bên cạnh cấu trúc
môđun mới này, bài báo còn mô tả một phương pháp mã hóa dựa trên cấu trúc
này bằng phần mềm maple 13.0.

 p n là nhóm con của

1. GIỚI THIỆU

nP=O thì khi đó E 

Ta ký hiệu tập điểm của đường cong elliptic E trên

 p  và cấu trúc của nhóm con này là một

trường  p (p là số nguyên tố lớn hơn 3) là

E 

 p  . Để tập điểm này trở thành nhóm aben ta

E 

 n  module. Trong trường hợp n là một số

bổ sung vào điểm tại vô cùng O và quy tắc cộng
điểm. Một điểm P trên đường cong elliptic E được
gọi là có bậc n nếu nP  O, mP  O với mọi

nguyên tố ta sẽ có được một phương pháp mã hóa
dựa vào cấu trúc môđun của nhóm con này.
Trong suốt bài báo này phương trình của đường
cong elliptic E được cho bởi dạng Weierstrass:

 p n là tập

số nguyên 1  m  n . Nếu gọi E 

2

3

y  x  ax  b

hợp những điểm trên đường cong elliptic thỏa mãn

3

2

4a  27b  0.
10

thỏa

mãn

điêu

kiện

Journal of Science – 2015, Vol. 8 (4), 10 – 21

Part D: Natural Sciences, Technology and Environment

2. CẤU TRÚC MÔĐUN CỦA TẬP ĐIỂM CÓ BẬC HỮU HẠN TRÊN ĐƯỜNG CONG ELLPTIC
2.1 Định nghĩa
Điểm P trên đường cong elliptic được gọi là điểm có bậc n nếu nP = O , mP  O, với mọi số nguyên

1  m  n và ký hiệu bậc của P là deg(P).
2.2 Mệnh đề
Cho P là điểm có bậc n trên đường cong elliptic E không kỳ dị. Khi đó, với mọi số nguyên k   thì điểm
kP  mP . Trong đó m là số dư trong phép chia k cho n. Hay nói cách khác với mọi

k  m   n , P  E  p  thì kP  mP .
n

Chứng minh. Với k  m   n thì tồn tại số nguyên a   sao cho k  m  an . Khi đó với mọi

P  E  p  ta có kP  m  an  P . Bằng phương pháp quy nạp ta chứng minh kP  mP .
n

Thật vậy, với a  0  kP  mP hiển nhiên đúng.





+ Với a  1  kP  m  n P  mP  nP do cấu trúc   môđun và vì nP=O nên

kP  mP .





+ Với a  2  kP  m  2n P lý luận tương tự như trên ta được kP  mP .



 



+ Giử sử đúng a  l  1 ta chứng minh đúng với a  l . Nghĩa là kP  m  l  1 n P  mP





ta chứng minh kP  m  ln P  mP . Thật vậy,













kP  m  l  1  1 n P  kP  m  l  1 n  n P  m  l  1 n P  nP





 

Do giả thuyết quy nạp m  l  1 n P  mP

 kP  mP  nP
Vì nP  O nên ta thu được kP  mP .

 n . □

Dễ dàng chứng minh được điểm mP  E  p
2.3 Mệnh đề

Cho đường cong Elliptic E xác định trên trường  p (p> 3) thỏa mãn điều kiện không kỳ dị. Khi đó,

 

E p

n

là một   môđun.
n

Chứng minh.

 

i. Trước tiên ta chứng minh E  p

 

+ E p

n

 

n

 

là nhóm con của E  p .

 

 E  p , điểm O  E  p

n

 

do đó E  p

11

n

 .

Journal of Science – 2015, Vol. 8 (4), 10 – 21

 

+ P , Q  E  p

n

Part D: Natural Sciences, Technology and Environment

 .

ta chứng minh P  Q  E  p

n

Thật vậy, ta xét điểm n(P  Q )  nP  nQ do tính chất của một   môđun.

 

Mà P , Q  E  p

n

nên nP  O, nQ  O  nP  nQ  O  n (P  Q )  O

 

 P Q  E p

n

+ Ta xét phần tử đối của P, giả sử Q là phần tử đối của P. Khi đó, ta có:

P  Q  O  n(P  Q )  O
Mặt khác, n(P  Q )  nP  nQ  nP  nQ  O , mà nP  O , do đó: nQ  O . Từ đây

 

ta có được Q  E  p

 

Như vậy, E  p

n

n

.

 

bảo toàn phép toán cộng do đó nó là nhóm con của E  p .

ii. Tiếp theo ta xây dựng phép nhân ngoài.

 

n  E  p

n

(m, P )

 

 E p

n

 mP

  . Ta có: k (lP )  k (lP )

a. Tính chất kết hợp: k , l   n , P  E  p

n

 k (lP )  k (lP )  k (lP )  (kl )P  k (lP )  (kl )P  k (lP )  (kl )P .

  . Ta có:

b. Tính chất phân phối: k , l   n , P , Q  E  p

n

+ (k  l )P  (k  l )P  (k  l )P  (k  l )P  (k  l )P  (k  l )P

 (k  l )P  kP  lP  (k  l )P  kP  lP .
+ k (P  Q )  k (P  Q )  k (P  Q )  kP  kQ  k (P  Q )  kP  kQ .
c. Tính chất Unita. Ta có: 1P  1P  P .
Rõ ràng đây là một   môđun.
n

3. ỨNG DỤNG
Ví dụ 1. Sử dụng giao thức trao đổi chìa khóa của Diffie-Hellman vào phương pháp mã hóa sử dụng điểm
có bậc hữu hạn. Giả sử T cần gởi văn bản mật cho C là:
“Mathematics is my favorite subject”.

12

Journal of Science – 2015, Vol. 8 (4), 10 – 21

Giả sử khóa bí mật của T là
trong



ví dụ

Part D: Natural Sciences, Technology and Environment

k1  2 , khóa bí mật của B là k2  3 và u là phần tử được chọn ngẫu nhiên

u  7 . Khi đó: Khóa công khai của T là KSCKT  7k1  49 . Khóa công khai của

C là KSCKC  7

k2

 343 .

* Tiến trình mã hóa: T muốn gởi văn bản cho C tiến hành như sau: T đặt tương ứng văn bản rõ với một
điểm P có bậc là một số nguyên tố n thuộc đường cong E và tính khóa bí mật cho phiên làm việc này là
k

K  (KSCKC ) 1  117649 . T tiến hành mã hóa bằng cách tính điểm nhân K .P  Q và gởi cho
C điểm Q.
* Tiến trình giải mã: C nhận được điểm Q tiến hành giải mã như sau:
k

C tính khóa của phiên làm việc này là M  (KSCKT ) 2 và tìm bậc của Q.
C tìm

m   n , tính nghịch đảo m

1

1

và giải mã bằng cách tính điểm m Q .

Chứng minh.
Vì n là một số nguyên tố. Khi đó,  n là một trường. Với mọi m   n , m  0 luôn tồn tại m
sao cho m.m

1

1

 n

 1 mà 1P  1P  P .

Như vậy, với một số nguyên k bất kỳ được chọn làm khóa thì luôn tồn tại m   n sao cho

k  m  m  n   kP  mP  Q .
1

1

1

Để khôi phục lại được dữ liệu, ta lấy m Q  m (mP )  (m m )P  1P .
Mà 1P  1P  P . Kết luận: Dữ liệu được khôi phục.
4. MÔ TẢ PHƯƠNG PHÁP BẰNG PHẦN MỀM MAPLE 13.0
Bảng tương ứng số - ký tự - điểm.

Tương ứng hệ
thập phân
0

Đồ hoạ
(Hiển thị ra
được)
Khoảng
trống (␠)

Tương ứng với
điểm trên
đường cong E

Tương ứng hệ
thập phân

Đồ hoạ
(Hiển thị ra
được)

Tương ứng với
điểm trên
đường cong E

[19,67]

49

w

[116,160]

1

A

[22,91]

50

x

[120,93]

2

B

[23,99]

51

y

[124,190]

3

C

[26,100]

52

z

[125,40]

4

D

[27,67]

53

!

[126,195]

5

E

[28,194]

54

#

[135,60]

6

F

[30,135]

55

$

[138,139]

7

G

[33,52]

56

%

[140,142]

8

H

[34,154]

57

&

[142,198]

13

Journal of Science – 2015, Vol. 8 (4), 10 – 21

Part D: Natural Sciences, Technology and Environment

Tương ứng hệ
thập phân

Đồ hoạ
(Hiển thị ra
được)

Tương ứng với
điểm trên
đường cong E

Tương ứng hệ
thập phân

Đồ hoạ
(Hiển thị ra
được)

Tương ứng với
điểm trên
đường cong E

9

I

[35,45]

58

'

[143,26]

10

J

[37,132]

59

(

[144,48]

11

K

[38,191]

60

)

[145,80]

12

L

[40,52]

61

*

[146,124]

13

M

[41,85]

62

+

[147,155]

14

N

[43,13]

63

,

[148,59]

15

O

[45,42]

64

-

[150,87]

16

P

[46,93]

65

.

[155,19]

17

Q

[47,170]

66

/

[157,4]

18

R

[49,32]

67

0

[161,109]

19

S

[50,147]

68

1

[164,88]

20

T

[53,101]

69

2

[167,189]

21

U

[54,194]

70

3

[168,15]

22

V

[55,189]

71

4

[173,51]

23

W

[56,177]

72

5

[179,189]

24

X

[57,178]

73

6

[181,140]

25

Y

[58,200]

74

7

[183,47]

26

Z

[61,36]

75

8

[189,84]

27

a

[62,68]

76

9

[190,158]

28

b

[64,72]

77

:

[191,199]

29

c

[65,35]

78

;

[195,14]

30

d

[69,101]

79

<

[196,184]

31

e

[70,141]

80

=

[197,11]

32

f

[77,17]

81

>

[198,7]

33

g

[80,45]

82

?

[202,83]

34

h

[86,145]

83

@

[205,74]

35

i

[90,127]

84

[

[206,84]

36

j

[92,117]

85

]

[212,14]

37

k

[94,25]

86

{

[213,23]

38

l

[95,175]

87

}

[215,116]

39

m

[97,46]

88

^

[219,89]

40

n

[98,42]

89

_

[220,22]

41

o

[99,49]

90

`

[222,53]

42

p

[101,148]

91

|

[224,6]

43

q

[104,135]

92

~

[234,53]

44

r

[106,13]

93

Ñ

[238,82]

14