ĐẠI HỌC CÔNG NGHỆ
ĐẠI HỌC QUỐC GIA HÀ NỘI

BÁO CÁO MÔN HỌC
MẬT MÃ VÀ AN TOÀN DỮ LIỆU
HỆ MÃ HÓA TRÊN ĐƯỜNG CONG ELLIPTIC
Lớp môn học:
Giảng viên:
Mật mã và an toàn dữ liệu
PGS.TS Trịnh Nhật Tiến
Học viên thực hiện :
Bùi Thị Phương
HÀ NỘI – 2014
1

HỆ MÃ HÓA TRÊN ĐƯỜNG CONG ELLIPTIC
Họ tên : Bùi Thị Phương
Ngày sinh : 15/03/1989
Mã học viên : 12025278
Email : [email protected]
Điện thoại : 0973413012
1 Đường cong Elliptic trên trường số thực
Đường cong Elliptic là đường cong có dạng:
y
2
=
x
3
+ ax + b
Trước khi khảo sát đồ thị của đường cong Elliptic, chúng ta xem lại đường bậc 3 sau:
y = f(x) = x

P qua trục hoành, như vậy.
3. Với 2 điểm P, Q bất kỳ, kẻ một đường thẳng đi qua P và Q thì sẽ cắt đường
cong Elliptic tại một điểm thứ 3 là điểm S. Phép cộng P và Q sẽ là
Trong trường hợp P và Q đối xứng qua trục hoành, hay nói cách khác Q = thì
đường thẳng nối P, Q sẽ cắt đường cong Elliptic tại vô cực, hay P + ( )=0. Điều
này phù hợp với định nghĩa 2.
4. Để tính P + P , ta vẽ đường thẳng tiếp tuyến với đường cong Elliptic tại P , đường
thẳng này cắt đường cong tại điểm S, lúc đó R= P + P= .
4
Có thể thấy, tập E(a, b) cùng với phép cộng định nghĩa như trên tạo thành một nhóm
Abel
Tính giá trị của phép cộng:
Gọi tọa độ của điểm P là (x
p,
y
p
) , của điểm Q là (x
Q,
y
Q
) . Ta tính tọa độ của điểm R = P
+ Q = -S như sau:
Đặt hệ số góc đường thẳng là :
Ta tính được:
5
Tương tự, thực hiện tính tọa độ của điểm R= P + P = -S, khi y
p
0 ta có:
6
2 Đường cong Elliptic trên trường Zp.

2
=
p
2
– 2py + y
2
y
2
mod p
Ví dụ (1, 7) đối xứng với (1, 16) vì 7+16 = 0 mod 23. Hình vẽ bên dưới minh họa tính
đối xứng này.
Các điểm đối xứng với nhau qua đường y = 11.5 . Riêng điểm (4, 0) xem như là
đối xứng với chính nó.
8
Cũng tương tự như nhóm Abel E(a,b) định nghĩa trên đường cong Elliptic số
thực, chúng ta cũng định nghĩa một nhóm Abel E
p
(a,b) gồm các điểm của đường
cong Elliptic Zp cùng với điểm vô cực O.
1) Điểm O là phần tử đơn vị của phép cộng. .
2) Phần tử nghịch đảo của điểm P trong phép cộng, ký hiệu – P, là điểm đối xứng
với P, như vậy P + (– P) = O
3) Với 2 điểm P, Q bất kỳ, phép cộng R= P + Q được xác định bằng công thức:
Trong đó:
9
Ví dụ: trong E
23
(1,1) , chọn P = (3,10), Q=(9,7), vậy:
10
3 Đường cong Elliptic trên trường GF(2

4
= g +1. Bảng các lũy thừa của g là:
:
Xét ví dụ về đường cong Elliptic trên GF(2
4
):
y
2
+ xy
=
x
3
+ gx + 1 (a=g
4
, b=1)
Bảng bên dưới liệt kê các điểm thuộc đường cong này
Tương tự như nhóm Abel E
p
(a,b) , chúng ta cũng xây dựng một
nhóm Abel gồm các điểm của đường cong Elliptic GF(2
m
) cùng với điểm vô cực
O.
11
1) Điểm O là phần tử đơn vị của phép cộng. P + O = O + P = O. .
2) Phần tử nghịch đảo của điểm P trong phép cộng, ký hiệu – P, là điểm
đối xứng với P, ký hiệu P =(x
p,
y
p

Vì 9P = Q nên ta xác định được k = 9. Trong thực tế chúng ta sẽ sử dụng đường
cong Elliptic Zp với giá trị p lớn, sao cho việc vét cạn là bất khả thi. Hiện nay người
ta đã tìm ra phương pháp tìm k nhanh hơn vét cạn là phương pháp Pollar rho.
Dựa vào hàm một chiều trên chúng ta có 2 cách sử dụng đường cong Elliptic
trong lĩnh vực mã hóa là trao đổi khóa EC Diffie-Hellman và mã hóa EC.
 
Trước tiên ta chọn một số nguyên q lớn, với q là số nguyên tố (nếu sử dụng
đường cong Elliptic Zp) hoặc q có dạng 2
m
(nếu chọn đường cong GF(2
m
)), và chọn 2
tham số a, b tương ứng để tạo thành nhóm E
q
(a,b). Ta gọi G là điểm cơ sở của nhóm nếu
12
tồn tại một số nguyên n sao cho nG=0. Số nguyên n nhỏ nhất như vậy được gọi là hạng
của G.
Trong trao đổi khóa EC Diffie-Hellman, ta chọn một điểm G có hạng n lớn, và
giao thức trao đổi khóa giữa Alice và Bob tiến hành như sau:
1) Alice chọn một số n
A
< n và giữ bí mật số n
A
này. Sau đó trong E
q
(a,b) Alice
Tính P
A=
n

và P
B
, tuy nhiên chỉ có thể tính được điều này là bất
khả thi như ta đã thấy ở phần trên.
Chú ý: khóa phiên K là một điểm trong đường cong Elliptic, để sử dụng khóa này
cho mã hóa đối xứng như DES hay AES, ta cần chuyển K về dạng số thường.
  !"
Tương tự như vấn đề trao đổi khóa, trong vấn đề mã hóa/giải mã, ta cũng chọn
các tham số để tạo một nhóm Abel E
q
(a,b) và chọn một điểm cơ sở G có hạng n lớn.
Các thành phần khóa khóa riêng và công khai trong mã hóa EC được định nghĩa
như sau:
Trong đó d<n và E=dG với d là một số bí mật do người sinh khóa chọn. Do tính
chất của hàm một chiều từ E và G không thể suy ra được d.
Từ đó chúng ta có hai cách thức thực hiện mã hóa/ giải mã như sau:
1) Phương pháp Elgamal:
13
Giả sử Alice muốn gửi một thông điệp M cho Bob, trước tiên Alice chuyển
M từ dạng dãy bít sang dạng điểm P
M
=(x, y). Bản mã C
M
(dùng khóa công khai của
Bob) được tính là một cặp điểm như sau:
C
M =
{kG, P
M
+ kE}với k là một số ngẫu nhiên do Alice chọn

2) Phương pháp Menezes - Vanstone:
Thông điệp M của Alice được tách thành hai phần M=(m1, m2) sao cho m1, m2
Zp. Alice chọn một số ngẫu nhiên k, kết hợp với khóa công khai của Bob, Alice tính
điểm P như sau:
P(x
p,
y
p
) = kE
Bản mã C
M
gồm 3 thành phần:
C
M =
{ c
0,
c
1,
c
2
} ={kG, x
p
m
1
mod p, y
p
m
2
mod p}
14

# $%& '()*+,-
Hiện nay, phương pháp nhanh nhất để tính logarit đường cong Elliptic (tính k biết
G và kG) là phương pháp Pollar rho. Bảng sau đây liệt kê kích thước hóa của phương
pháp ECC và phương pháp RSA dựa trên sự tương đương về chi phí phá mã.
Như vậy với cùng một độ an toàn thì mã hóa ECC chỉ dùng các phép tính có số
bít nhỏ hơn nhiều lần so với mã hóa RSA.
15