

Luận văn

Hệ mật đường cong
elliptic
3.3. Logarit rời rạc trên đƣờng cong Elliptic( Discrete logarithm on
Elliptic) 24
3.4. Vấn đề trao đổi khoá Diffie- Hellman(D- H) trên Elliptic 24
3.5. Hệ mât mã hoá Elgamal trên đƣờng cong Elliptic 25
CHƢƠNG 4 27
MỘT VÀI ỨNG DỤNG 27
4.1. Lƣợc đồ chữ ký số trên đƣờng cong elliptic (Elliptic Curve Signature
Algorithm ) - ECDSA 27
4.1.1. Lƣợc đồ ký ECDSA 27
4.1.2. Độ an toàn của sơ đồ chữ ký ECDSA 28
4.2. Một số chuẩn sử dụng hệ mật ECC 29
KẾT LUẬN 32
TÀI LIỆU THAM KHẢO 33
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 2 - Lớp CT702

LỜI CẢM ƠN
Em xin bày tỏ lòng biết ơn tới TS Hồ Văn Canh đã tận tình hƣớng dẫn
và cung cấp những tài liệu quý báu để em hoàn thành luận văn này.
Em xin chân thành cảm ơn các Thầy cô giáo khoa công nghệ thông tin
trƣờng Đại Học Dân Lập Hải Phòng đã nhiệt tình giảng dạy chúng em trong 4
năm học.
Tôi cũng xin chân thành cảm ơn các bạn bè đồng nghiệp đã giúp đỡ tôi
trong quá trình học tập và hoàn thành tốt luận văn này! Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 3 - Lớp CT702

MỞ ĐẦU
Ngày nay với sự phát triển mạnh mẽ của công nghệ thông tin, truyền
thông nói chung và Internet nói riêng đã giúp cho việc trao đổi thông tin
nhanh chóng, dễ dàng, E-mail cho phép ngƣời ta nhận hay gửi thƣ ngay trên
máy tính của mình, E-business cho phép thực hiện các giao dịch trên mạn.
Do vậy một vấn đề phát sinh là thông tin có thể bị trộm cắp, có thể là sai lệch,
có thể giả mạo. Điều đó có thể ảnh hƣởng tới các tổ chứa, các công ty hay cả
một quốc gia. Những bí mật kinh doanh, tài chính là mục tiêu của các đối thủ
cạnh tranh. Những tin tức về an ninh quốc gia là mục tiêu của các tổ chức tình
báo trong và ngoài nƣớc.
Để giải quyết tình hình trên an toàn thông tin đƣợc đặt ra cấp thiết. Kỹ
thuật mật mã là một trong những giải pháp của an toàn truyên thông. Kỹ thuật
này có từ ngàn xƣa nhƣng nó đơn giản, ngày nay khi có mạng máy tính ngƣời
ta dùng mật mã hiện đại. Các nhà khoa học đã phát minh ra những hệ mật mã
nhằm che dấu thông tin cũng nhƣ là làm rõ chúng để tránh sự giòm ngó của
những kẻ cố tình phá hoại nhƣ các hệ mật: RSA, Elgamal… mặc dù cũng rất
an toàn nhƣng có độ dài khoá lớn nên trong một số lĩnh vực không thể ứng
dụng đƣợc.
Chính vì vậy ngƣời ta đã phát minh một hệ mật đó là hệ mật trên đƣờng
cong elliptic, hệ mật này đƣợc đánh giá là hệ mật có độ bảo mật an toàn cao
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 5 - Lớp CT702 CHƢƠNG 1
CƠ SỞ TOÁN HỌC
1.1. Phƣơng trình đồng dƣ bậc hai và thặng dƣ bậc hai
Ta xét phƣơng trình đồng dƣ bậc hai có dạng nhƣ sau:
x
2
≡ a (mod n)
Trong đó n là số nguyên dƣơng, a là số nguyên với gcd(a, n) ≡ 1, và x
là ẩn số. Phƣơng trình đó không phải bao giờ cũng có nghiệm, khi nó có
nghiệm thì ta gọi a là thặng dƣ bậc hai mod n. Ngƣợc lại thì a gọi là một bất
thặng dƣ bậc hai mod n.
Tập các số nguyên nguyên tố với n đƣợc phân hoạch thành hai tập con.
Tập Q
n
các thặng dƣ bậc hai mod n, và tập các bất thặng dƣ bậc hai mod n.

1, , ;
1, , .
khi a p
khi a Qp
khi a Qp









Chú ý:
+ Từ định nghĩa suy ra a là thặng dƣ bậc hai mod p khi và chỉ khi








p
a
= 1
+ Theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0 ta có:
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 6 - Lớp CT702







p
ab
=








p
a








p
b
;




p
1
=1 và









p
1
= (-1)
(p-1)/2
.
Định lý 1:








p

a
=








p
b

Định lý 3








p
2
= 1 p ≡ 1 mod 8 hay p ≡ 7 mod 8
-1 p ≡ 3 mod 8 hay p ≡ 5 mod 8

Ví dụ: Cho a = 186, p= 401 (p là số nguyên)




  


  








Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 7 - Lớp CT702
Tìm a có là thặng dƣ bậc hai không nghĩa là a

Q
401
?
Và tìm x? với x
2
≡ a mod 401














401
93
.
Theo định lý 3:
Vì 401 ≡ 1 mod 8








401
2
=1 vậy









=






401
3






401
31

Nhƣng






401
3
= (-1)
4
400.2

400.30







3
401
=






3
401
=






31
29
=






401
3
= -1).
Ta có p-1 = 400 = 2
4
.






3
25
→ b = n
S
= 186
25
mod 401 = 286 mod 401.
Còn r = a
2
1S
mod 401 = 186 mod 401 = 103.
Tính a
-1
mod 401 = 186

2
/a = -1

luỹ thừa bậc 2 của nó là 1

đặt j
1
=0, cứ thế j
2

=1(2 = K =

) Vậy j =5 vì 1.2
2
+1 = 5

Căn bậc 2 của 186 là b
5
r mod 401 = 304
Thử lại 304
2
≡ 186 mod 401?
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 8 - Lớp CT702
Ta có 304
2
= 92416 vậy 304
2
= 186 = 92230 ≡ 0 mod 401


2
a
a
p



………
ak
k
a
p




với a
1
, a
2
, … , a
k


1
P
1
, P
2
, ….P

2.
2
n



=
1, 1(mod8)
1 3(mod8)
khia
khia



 


3.
12
mm
n



=
1
m
n






  



Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 9 - Lớp CT702
Trong một trƣờng hợp đặc biệt khi n = p là số nguyên tố có dạng p =
4m + 3 tức là p đồng dƣ với 3 theo mod 4, và a là một số nguyên nguyên tố
với p. Theo tiêu chuẩn Euler ta biết phƣơng trình (*) có nghiệm khi và chỉ
khi a
(p-1)/2
≡ 1 (mod p). Khi đó ta có:

a
1
2
1

p
≡ a (mod p),
a
)1(2 m
≡ a (mod p).


-1
.
<G,*> đ ƣơc gọi là một nhóm giao hoán (nhóm Abelian) nếu b * a = a * b
với a, b

G.
- Một nhóm có cấp hữu hạn đƣợc gọi là nhóm hữu hạn
Nếu <G, *> là nhóm hữu hạn thì số các phần tử của <G, *> đƣợc gọi là
bậc của G và ký hiệu là |G| . Nếu <G, *> là nhóm nhân hữu hạn, bậc của một
phần tử a

G kà số nguyên dƣơng nhỏ nhất m thoả mãn a
m
= 1. Trong nhóm
có cấp hữu hạn, với mọi phần tử thuộc nhóm, m luôn tồn tại.
Nhóm Cylic
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 10 - Lớp CT702
Là nhóm mà mọi phần tử của nó đƣợc sinh ra từ một phần tử đặc biệt g

G.
Phần tử này đƣợc gọi là phần tử sinh (nguyên thuỷ) tức là:
Với

x

G(G là nhóm với toán tử * ):

n




Q nghĩa là F chứa Q nhƣ một trƣờng con. Trƣờng F đƣợc gọi là đặc
số p nếu F
0


Z
p
.
Trƣờng hữu hạn là trƣờng chứa hữu hạn các phần tử. Đối với một
trƣờng hữu hạn thì

a

F luôn luôn tồn tại một số nguyên dƣơng n sao cho: n
aa
= 0
Định nghĩa
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 11 - Lớp CT702
Trƣờng K với phần tử đơn vị nhân là 1. Với p dƣơng nhỏ nhất thoả
mãn
  
p
1 11 
= 0 đƣợc gọi là đặc số của K.

Đối với mỗi lũy thừa nguyên tố q = p
f

có tồn tại một trƣờng q phần tử và đó
là trƣờng duy nhất (theo nghĩa đẳng cấu).
Cấp của các phần tử trong F
*
q
theo nghĩa đối với phép nhân với F
*
q
là tập hợp
tất cả các phần tử khác không của trƣờng F
q
(q hữu hạn)
Chú ý rằng đối với mọi nhóm nhân hữu hạn, cấp của bất cứ một số phần tử
khác không nào cũng là ƣớc của số các phần tử trong nhóm. Cụ thể ta có định
lý
Định nghĩa
Giả sử phần tử g

F
q
nếu cấp của g là q-1 tức là {g
1
, g
2
,……, g
q-1
= 1}

x + a
6.

Trên trƣờng F biểu diễn bằng phƣơng trình Weiretrass:
y
2
+ a
1
xy + a
3
y = x
3
+ a
2
x
2
+a
4
x + a
6 2
(*)
Xét đƣờng cong E trên trƣờngnguyên tố hữu hạn F
p
(p nguyên tố, p>3 ) với
công thức biến đổi nhƣ sau:
X→X −
3
2a
, Y→ Y −
2

Phan Thị Thu Hiền - 13 - Lớp CT702
tức là 4a
3
+ 27b
2
≠ 0 mod p cùng với phần tử O - điểm O này đƣợc gọi là
điểm vô hạn.
Tức là đƣờng cong Elliptic là tập hợp S:
S = { (x, y) : y
2
= x
3
+ ax +b, x, y

K }

{O} .
Với a, b

K cho trƣớc sao cho 4a
3
+ 27b
2
≠ 0 theo mod p.
Nếu K là trƣờng đặc số 2 thì ta định nghĩa:
S = { (x, y) : y
-2
+ y= x
3
+ ax +b }

và P
2
sẽ cắt
một điểm duy nhất P
3
( x
3,
y
3
) có thể xác định thông qua P
1
và P
2
nằm
trên đƣờng cong E.
 Tiếp tuyến của đƣờng cong tại điểm bất kỳ P(x, y) trên đƣờng cong E
cũng cắt đƣờng cong elliptic E tại một điểm duy nhất nằm trên đƣờng
E, điểm này cũng có thể xác định đƣợc thông qua P.
Dựa vào những tính chất đó ngƣời ta đã nghiên cứu và phát hiện ra một
khả năng mới cho kỹ thuật mã hoá nói chung và chứng thực nói riêng, kỹ
thuật mã hoá dựa trên đƣờng cong elliptic.
Ngƣời ta đã chỉ ra rằng các hệ mã hoá bằng đƣờng cong elliptic có độ
bảo mật cao hơn nhiều so với các hệ mã hoá công khai khác nhƣ RSA,
Elgamal. Độ bảo mật dựa trên độ khó phân tích số nguyên thành các thừa số
nguyên tố cũng nhƣ bài toán logarit rời rạc, độ dài khoá giảm đi nhiều lần và
do đó tốc độ thực hiện cũng sẽ nhanh hơn rất nhiều. Chính vì vậy ta áp dụng
kỹ thuật mã hoá bằng đƣờng cong elliptic vào nhiều lĩnh vực khác nhau.
Các kỹ thuật mã hoá bằng phƣơng pháp đƣờng cong elliptic đƣợc sử
dụng hiệu quả nhất trong việc xây dựng các giải pháp bảo mật thông tin cho
Đồ án tốt nghiệp Hệ mật đường cong elliptic

trƣờng ) chỉ có khoảng một nửa số các điểm của Fq. Chính xác hơn, giả sử

đặc trƣng toàn phƣơng của F
q
(lấy

(0) = 0).
Ví dụ: Nếu q = p là 1 số nguyên tố thì

(x) =(
p
x
) là ký hiệu Legedre
Symbol). Do đó trong tất cả mọi trƣờng hợp số các nghiệm y

F
q
thoả mãn
phƣơng trình y
2
= u là bằng 1 +

(u). Vì vậy số các nghiệm ở phƣơng trình 1
và điểm vô hạn là:
1 +

Fqx
(1+

(x

Phan Thị Thu Hiền - 15 - Lớp CT702
2.3. Các phép toán trên đƣờng cong Elliptic
Giả sử p là một số nguyên tố >3. Ngƣời ta chứng minh đƣợc rằng bằng
phép biến đổi tuyến tính, ta có thể quy phƣơng trình đƣờng cong elliptic về
dạng Weierstrass nhƣ sau:
Y
2
= X
3
+ aX + b
Đƣờng cong elliptic Y
2
= X
3
+ aX + b trên Z
p
đƣợc định nghĩa là tập hợp tất
cả các điểm (x, y)

Z
p

Z
p
thoả mãn phƣơng trình:
Y
2
= X
3
+ aX + b (mod p),

x
3
=

2
- x
1
– x
2
, y
3
=

(x
1
– x
3
) –y
1,

Với


= (y
2
– y
1
) / (x
2
– x









xx
yy
- x
1
– x
2 (*)
y
3
=












y
ax
– 2x
2 (**)
y
3
=









1
1
2
2
3
y
ax
( x
1
– x

) cũng nằm trên một đƣờng
thẳng.
Ngoài ra ta định nghĩa thêm: P + O = O + P = P.

Tính chất
Dễ thấy rằng tập E với phép toán cộng đó tạo thành một nhóm Abelian:
P
Q
P+ Q
R
P
2P
R
-1
-2
2
1
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 17 - Lớp CT702
 Tính đóng: Nếu P, Q

E thì P + Q

E.
 Tính kết hợp: Nếu P, Q, R

E thì P + ( Q + R ) = R + ( Q + P ).
 Tồn tại phần tử trung hoà O: với mọi P

E thì P + O = O + P = P (theo




32
98
(-3-6) = -9 + (-1)(-9) =0.
Vậy P +Q = (6, 0). Bây giờ ta tính 2P áp dụng (**) ta có: x1= -3, y1 = 9
x3 =
4
25
và do đó y3=
8
35
. Vậy 2P = (
4
25
,
8
35
)
2.3.2. Phép nhân
Phép nhân một số nguyên k với một điểm P thuộc đƣờng cong elliptic
E là điểm Q đƣợc xác định bằng cách cộng k lần điểm P và dĩ nhiên Q

E: k

P = P + P + P……+ P ( k phép cộng điểm P).
Vì vậy nếu G là một điểm thuộc đƣờng cong elliptic E thì với mỗi số
nguyên dƣơng k luôn dễ dàng xác định đƣợc điểm Q = k


E, K và điểm cơ sở B

E cố định và công khai nhƣng việc chọn các tham số
này phù hợp là bƣớc quan trọng nhất.
2.5.1. Trƣờng K
Trƣớc hết chúng ta xem xét sự ảnh hƣởng của trƣờng K đến cấu trúc
nhóm của E(K) và các hệ mật mã trên E (K).
Một đƣờng cong elliptic trên một trƣờng hữu hạn tạo thành nhóm
Abelian đƣợc sử dụng trong mật mã học. Một ví dụ là việc chọn trƣờng F
2
r

giúp thực hiện các phép tính nhanh và dễ dàng triển khai đƣợc trên các thiết bị
cứng. Tuy nhiên, các đƣờng cong trên trƣờng F
2
r
có thể bị tấn công bởi
MOV, trong khi các đƣờng cong trên trƣờng F
p
(p là số nguyên tố lớn) lại
chống lại đƣợc kiểu tấn công này. Rõ ràng, các đƣờng cong elliptic trên
trƣờng số nguyên tố F
p
và trên trƣờng F
q
n
có các tính chất giúp chúng có thể
thực thi đƣợc trên các thiết bị mà vẫn đảm bảo an toàn.
Một chú ý nữa là việc tính số điểm trên # E (K). Với # E (K) thích hợp
có thể là điều kiện cho phép thực hiện tấn công Pohlig – Hellman. Có thể

). Khi đó:
 Tập tất cả các cặp nghiệm (x, y) của phƣơng trình y
2
+ax = x
3
+ bx + c
với a, b, c

F
q
và a = 0 (mod q) cùng với điểm trung hoà O tạo thành
một đƣờng cong elliptic dạng supersingular.
 Tập tất cả các cặp nghiệm (x, y) của phƣơng trình y
2
+ ax = x
3
+ bx + c
với a, b, c

F
q
và b = 0 (mod q) cùng với điểm trung hoà O tạo thành
một đƣờng cong elliptic dạng non-supersingular.
Supersingular Curve: Menezes và Vanstone đã tìm ra các ƣu điểm của
các đƣờng cong elliptic supersingular cho các hệ mật mã, đặc biệt trên trƣờng
F
2
r
. Tuy nhiên, các đƣờng cong supersingular có thể bị tấn công bằng MOV.
Nonsupersingular Curve: Ƣu điểm của các đƣờng cong nonsupersingular

5. Còn lại, đặt P = (x, y) và đƣờng cong y
2
= x
3
+ ax +b là đƣờng cong cần
chọn.
Tuy nhiên phƣơng pháp này có thể tạo ra các đƣờng cong không đảm bảo
một số yêu cầu định trƣớc. Một kỹ thuật cải tiến là xây dựng các đƣờng cong
với các tính chất cho trƣớc. Cũng có thể chọn những đƣờng cong để tạo các
hệ mã hoá không phụ thuộc vào bài toán EDLP, chẳng hạn các hệ elliptic dựa
trên RSA.
Các hệ mật mã elliptic làm việc với các nhóm con cylic của E với phần tử
sinh là điểm P. Vì vậy, việc lựa chọn P phù hợp là rất quan trọng.
Để đảm bảo việc chọn điểm thích hợp ta hãy chọn đƣờng cong elliptic
của chúng ta và trƣờng hữu hạn sao cho số N các điểm của đƣờng cong là một
số nguyên tố. Nếu chọn đƣợc nhƣ vậy thì mọi điểm B ≠ 0 đều là phần tử sinh.
độ thực hiện nhanh gấp 6 lần so với RSA). Cùng thời điểm đó, Kaliski chứng
minh rằng các hàm cửa sập một chiều đòi hỏi thời gian là hàm mũ để thực
hiện phép tính nghịch đảo. Menezes, Okamoto và Vanstone đã đƣa ra một
phƣơng pháp tấn công MOV để giải bài toán EDLP trong một số trƣờng hợp
riêng. Ngay sau đó, Miyaji đã tìm đƣợc các điều kiện để tránh khỏi tấn công
MOV và đề xuất một ứng dụng thực tế của các đƣờng cong elliptic cho các sơ
đồ chữ ký và định danh trên Smart Card.
Năm 1993, Demytko đƣa ra một thuật toán mới tƣơng tự nhƣ RSA cho
các đƣờng cong Elliptic trên vành Z
n
vƣợt qua các hạn chế của các phiên bản
trƣớc, và Menezes và Vanstone đã đƣa ra phƣơng pháp thực thi trên các thiết
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 22 - Lớp CT702
bị cứng có thể cài thiện các tính toán trên elliptic trên một trƣờng hữu hạn.
Những năm 1997, 1998 việc tìm ra các hệ mật mã trên các đƣờng cong
Elliptic ngày càng thu hút nhiều sự chú ý và một số thuật toán đã đƣợc đƣa
thành chuẩn trong các RFC.
3.2. Nhúng bản rõ lên đƣờng cong
Nhúng một bản rõ lên E là biểu diễn lại bản rõ đó nhƣ là các điểm trên
E mà nhờ đó chúng ta có thể thực hiện đƣợc các tính toán trên E. Có một số
phƣơng pháp thực hiện việc này. Trong đó có 2 phƣơng pháp chính là
imbedding và mask.
4.2.1. Imbedding
Muốn mã hoá bản rõ m trên một đƣờng cong elliptic cho trƣớc đƣợc
định nghĩa trên trƣờng F
q
trƣớc hết ta phải tìm cách nhúng nó lên E. Giả sử m
đƣợc coi là một số nguyên dƣơng nào đó. Bản rõ m đƣợc ứng với điểm P
m

nào đó(

=20, 30 hoặc

= 50 là đủ). Với m kà một số nguyên sao cho 0≤ m
≤M (M là số nguyên dƣơng lớn hơn mọi khối rõ m cần nhúng )
Trƣờng hữu hạn đã chọn sao cho q > M

.Biểu diễn các số nguyên từ 1 đến
M

dƣới dạng:
{m

+ j} 1≤ j ≤


Ta lập một ánh xạ 1- 1 tƣơng ứng giữa các số nguyên trên với tập hợp các
phần tử của F
q
. Ví dụ có thể viết một số nguyên nhƣ là một số nguyên cơ số p
có độ dài r và coi r nhƣ là một phần tử của Z/pZ , là hệ số của một đa thức
cấp r – 1 tƣơng ứng với một phần tử của F
q
. Nghĩa là số nguyên (a
r-1 ,
a
r-
2,…….
a

Y
2
= f(x) = x
3
+ ax + b và tìm căn bậc 2 của giá trì f(x) bằng cách sử dụng
phƣơng pháp đã nêu trong ví dụ 1.1.4.
Nếu tìm đƣợc một số y sao cho y
2
= f(x) thì lấy P
m
= (x, y). Nếu kết quả
f(x) là không bình phƣơng thì tăng x bởi 1 và tiếp tục tính toán từ đầu cho
đến khi tìm đƣợc một số x sao cho f(x) là một bình phƣơng cho đến khi j nhận
giá trị lớn

, có thể khôi phục lại đƣợc m từ điểm (x, y) bởi công thức:
-1)/

]
Trong đ ó là một số nguyên ứng với giá trị x bởi phép tƣơng ứng 1-1
giữa các số nguyên và các phần tử của F
q
. Vì f(x) là một bình phƣơng với xấp
xỉ 50% của mọi x cho nên chỉ có khoảng xác suất 2
-

để cho phƣơng pháp
này là sai.
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Phan Thị Thu Hiền - 24 - Lớp CT702

3.4. Vấn đề trao đổi khoá Diffie- Hellman(D- H) trên Elliptic
Giả sử A và B muốn thống nhất một khoá chung để liên lạc có bảo mật
giữa hai ngƣời bằng mật mã truyền thống. Trƣớc hết hai bên thống nhất công
khai chọn một trƣờng hữu hạn F
q
và một đƣờng cong elliptic trên nó khoá
chung của họ sẽ đƣợc xây dựng từ một điểm ngẫu nhiên P của đƣờng cong
vừa cho, họ làm cách này bằng cách chọn toạ độ x của P là ngẫu nhiên trong
F
q
. Sau đó nó đƣợc chuyển đổi thành số nguyên cơ số P có r số( q = p
r
) mà
đƣợc coi là khoá đối với hệ mã truyền thống của họ. Cụ thể nhƣ sau:
Trƣớc hết A, B chọn công khai một điểm B

E. B đóng vai trò nhƣ là
phần tử sinh g trong trƣờng hữu hạn của hệ thống Diifie-Hellman. Chúng ta
muốn có một nhóm con đƣợc sinh ra bởi B là lớn, tốt nhất là có cùng cấp nhƣ

Trích đoạn Lƣợc đồ ký ECDSA Một số chuẩn sử dụng hệ mật ECC

---