Giáo trình Số học thuật toán - Chương 7: Đường cong Elliptic

ều. Khi “sửa” một đ−ờng cong elliptic bằng cách chuyển 
các hệ số thành các đồng d− modulo p, ta có thể nhận đ−ợc một đ−ờng cong có kì dị. 
Thật vậy, biệt thức của đ−ờng cong (khác không) có thể dồng d− 0 modulo p, và khi 
đó, đ−ờng cong nhận đ−ợc có điểm bội trên tr−ờng hữu hạn. Tuy nhiên, rõ ràng điều 
đó chỉ xảy ra khi p là một −ớc số của biệt thức của đ−ờng cong xuất phát, và do đó, 
chỉ xẩy ra với một số hữu hạn giá trị của p. Ta nói đ−ờng cong elliptic đã cho có sửa 
xấu tại những giá trị của p đó, và có sửa tốt tại những giá trị p khác. 
 123
Điều cần quan tâm đầu tiên khi nghiên cứu một đ−ờng cong elliptic trên tr−ờng hữu 
hạn là: đ−ờng cong đó có bao nhiêu điểm? Giả sử E là đ−ờng cong elliptic trên 
tr−ờng Fq có q phần tử. Các điểm của đ−ờng cong là các cặp (x,y), x, y∈Fq thoả mãn 
ph−ơng trình trong Fq: 
y2=x3+a4x+a6 
Nh− vậy, nếu với giá trị x, x3+a4x+a6 là một thặng d− bình ph−ơng modulo q thì sẽ 
có hai điểm (x,y) và (x,-y) thuộc đ−ờng cong. Trong tr−ờng hợp ng−ợc lại, không có 
điểm nào của đ−ờng cong ứng với giá trị x. Từ đó, khi q là số nguyên tố, theo định 
nghĩa của kí hiệu Legendre, số điểm của đ−ờng cong ứng với giá trị x là 
1+
x a x a
q
3
4 6+ +



Thêm điểm tại vô cùng, ta có công thức tính số điểm của đ−ờng cong trong tr−ờng 
hợp q là số nguyên tố: 
#E(Fq)=1+ 1+ 
x a x a
qx Fq
3
4 6+ +


∈∑ 
Trong tr−ờng hợp q không phải là số nguyên tố, trong công thức trên đây, thay cho 
kí hiệu Legedre, ta hiểu đó là kí hiệu Jacobi, và dấu đẳng thức đ−ợc thay thế bởi bất 
đẳng thức ≤ . 
Định lí trên đây cho ta một −ớc l−ợng của số điểm của đ−ờng cong E trên tr−ờng Fq. 
Định lí Hasse. Giả sử N là số điểm của đ−ờng cong elliptic xác định trên tr−ờng Fq. 
Khi đó ta có: 
|N-(q+1) | ≤2 q . 
Bạn đọc có thể tìm thấy chứng minh của định lí này trong [Sil]. 
Một trong những ứng dụng mới nhất của đ−ờng cong elliptic trên tr−ờng hữu hạn, 
xuất hiện trong những năm gần đây, là các hệ mật mã khoá công khai elliptic. Phần 
tiếp theo đ−ợc dành để trình bày vấn đề đó. 
Đ5. Đ−ờng cong elliptic và hệ mật mã khoá công khai. 
5.1. Hệ mật mã khoá công khai sử dụng đ−ờng cong elliptic dựa trên độ phức tạp 
của thuật toán tìm số nguyên x sao cho xB=P, trong đó P, B là các điểm cho tr−ớc 
của đ−ờng cong (nếu số nh− thế tồn tại). Chú ý rằng, các điểm của đ−ờng cong lập 
thành một nhóm, và ta có thể quan niệm xB nh− là “Bx”: bài toán này hoàn toàn 
t−ơng tự nh− bài toán tìm logarit cơ sở b của một số p cho tr−ớc (xem ch−ơng 6). 
Tr−ớc tiên, ta cần xét thuật toán tìm bội của một điểm trên đ−ờng cong. 
 124
Định lí 7.4. Cho E là một đ−ờng cong elliptic trên tr−ờng hữu hạn Fq, P là một điểm 
của đ−ờng cong. Khi đó có thể tính toạ độ của điểm kP bằng O(log klog3 q) phép tính 
bit. 
Tr−ớc khi đi vào chứng minh định lí, ta tìm hiểu sơ qua ph−ơng pháp rất thông 
th−ờng để tìm bội của các điểm trên đ−ờng cong: ph−ơng pháp nhân đôi liên tiếp. 
Xét ví dụ sau: giả sử cần tính 205P. Ta viết : 
205P=2(2(2(2(2(2(2P+P)+P)+P)+P))+P) 
Nh− vậy, việc tính 205P đ−ợc đ−a về 4 phép cộng hai điểm của đ−ờng cong và 7 
phép nhân đôi một điểm cho tr−ớc. 
Ta giả thiết rằng, tr−ờng Fq có đặc tr−ng khác 2, 3. Trong tr−ờng hợp q=2r hoặc 
a=3r, có những thuật toán nhanh hơn để tính toạ độ của các bội của một điểm cho 
tr−ớc. Nh− vậy, ph−ơng trình xác định đ−ờng cong có thể cho d−ới dạng Weierstrass: 
y2=x3+ax+b. 
Khi đó, theo định lí 7.2, tổng P+Q=(x3,y3) của hai điểm khác nhau P=(x1,y1) và 
Q=(x2,y2) đ−ợc tính theo công thức sau: 
x3= ( )
y y
x x
2 1
2 1
2−
− -x1-x2, (7.6) 
y3=-y1+(
y y
x x
2 1
2 1
−
− )(x1-x3). (7.7) 
Trong tr−ờng hợp P=Q, ta có công thức để tính 2P: 
x3= ( )
3
2
1
2
1
2x a
y
+
-2x1, (7.8) 
y3=-y1+ ( )
3
2
1
2
1
x a
y
+
 (x1-x3). (7.9) 
Nh− vậy, ta phải dùng không quá 20 phép nhân, chia, cộng, trừ để tính toạ độ của 
tổng hai điểm khi biết các toạ độ của các điểm đó. Số các phép tính bit đòi hỏi là 
O(log3 q) (xem ch−ơng 5). Khi dùng ph−ơng pháp nhân đôi liên tiếp, ta phải thực 
hiện O(log k) phép tính cộng hai diểm hoặc nhân đôi một điểm (xem ch−ơng 5). Nh− 
vậy, toàn bộ số phép tính bit phải dùng là O(log klog3 q). Định lí đ−ợc chứng minh. 
Tóm lại, ta có thuật toán thời gian đa thức để tính bội của một điểm. Ng−ợc lại, khi 
biết kP và P, việc tìm ra k với những thuật toán nhanh nhất hiện nay lại đòi hỏi thời 
gian mũ. Điều này hoàn toàn t−ơng tự nh− trong tr−ờng hợp các số mũ modulo p, và 
sẽ là cơ sở cho việc xây dựng hệ khoá công khai sử dụng đ−ờng cong elliptic. 
5.2. Mã hoá nhờ các điểm của đ−ờng cong elliptic trên tr−ờng hữu hạn. 
 125
5.2.1. Nh− đã thấy trong ch−ơng 6, việc chuyển thông báo mật thực hiện bằng cách 
chuyển nó thành dạng chữ số, mã hoá thông báo “chữ số “ này và chuyển đi. Vì thế, 
để đơn giản khi trình bày, ta sẽ xem thông báo cần chuyển là một số nguyên d−ơng 
m nào đó. 
Việc đầu tiên là phải chọn một đ−ờng cong elliptic E nào đó trên tr−ờng hữu hạn Fq. 
Sau đó, phải tìm cách t−ơng ứng số nguyên m với một điểm của đ−ờng cong E. 
Để dễ hiểu quá trình lập mã, ta sẽ xem đ−ờng cong E đã đ−ợc chọn. Việc chọn 
đ−ờng cong sẽ đ−ợc trình bày ở tiết sau. 
5.2.2. T−ơng ứng một số m với một điểm của đ−ờng cong elliptic. 
Cho đến nay, ch−a có một thuật toán quyết định nào hữu hiệu để tìm đ−ợc một số đủ 
lớn các điểm của đ−ờng cong elliptic. Thuật toán mà ta trình bày sau đây là một 
thuật toán xác suất với thời gian đa thức. 
Tr−ớc hết ta chọn một số k nào đó theo yêu cầu sau: tr−ờng hợp thuật toán sẽ tiến 
hành không cho kết quả mong muốn chỉ xảy ra với xác suất không v−ợt quá 2-k. Nh− 
vậy, nói chung k=40 là có thể chấp nhận đ−ợc (ta nhắc lại rằng, trong tr−ờng hợp đó, 
xác suất sai lầm của một thuật toán sẽ bé hơn xác suất sai lầm của phần cứng của 
máy tính). 
Giả sử số m nằm trong khoảng 1≤m≤M. Ta luôn chọn q sao cho q>Mk. Tr−ớc tiên, 
ta t−ơng ứng mỗi số nguyên d−ơng s không v−ợt quá M với một phần tử của tr−ờng 
hữu hạn Fq. Việc đó dễ dàng làm đ−ợc bằng cách sau đây. Giả sử q=pr, và số s biểu 
diễn d−ới cơ số p có dạng s=(c0,c1,...,cr-1)p. Khi đó, đa thức 
S(X)= c Xi
i
i
r
=
−∑
0
1
modulo một đa thức bất khả quy nào đó bậc r sẽ t−ơng ứng với một phần tử của 
tr−ờng Fq (xem Ch−ơng 5). 
Nh− vậy, với m đã cho, với mỗi j, 1≤ j≤ k, ta có một phần tử t−ơng ứng xj của tr−ờng 
Fq. Ta sẽ chỉ ra một thuật toán để , với xác suất rất lớn, tìm đ−ợc một xj trong số đó 
sao cho tồn tại điểm (xj,yj) trên đ−ờng cong E. Khi đó, ta t−ơng ứng số m với điểm 
Pm=(xj,yj)∈E vừa tìm đ−ợc. 
Thuật toán tìm Pm: 
El1. Đặt j←1. 
El2. Nếu j>k: kết thúc thuật toán. Trong tr−ờng hợp 
ng−ợc lại, đặt Yj←xj3+axj+b. Nếu tồn tại yj sao cho 
Yj≡ yj2(mod q), in ra Pm=(xj,yj) và kết thúc thuật toán. Nếu 
ng−ợc lại, chuyển sang b−ớc El3. 
El3. Đặt j←j+1 và quay về b−ớc El2. 
Vì mỗi phần tử x∈Fq, xác suất để f(x) là chính ph−ơng bằng 1/2, nên thuật toán trên 
đây cho ta tìm ra điểm Pm với xác suất thất bại là 1/2
k. 
 126
Nh− vậy, ta đã có một thuật toán để mã hoá m bằng cách t−ơng ứng nó với một điểm 
của đ−ờng cong elliptic E. Tuy nhiên, cần nhắc lại rằng, một trong những yêu cầu 
của mã hoá là khi biết đ−ờng cong E trên Fq, biết Pm, ta phải khôi phục đ−ợc m một 
cách dễ dàng. Trong tr−ờng hợp này, yêu cầu đó đ−ợc đảm bảo. Thật vậy, giả sử 
Pm=(x,y). Khi đó m=
x
k
−



1
 (trong đó [ ] là kí hiệu phần nguyên). 
5.3. Mật mã khoá công khai sử dụng đ−ờng cong elliptic. 
Trong ch−ơng 6, ta làm quen với một hệ mã khoá công khai, trong đó sử dụng độ 
phức tạp của phép tính tìm logarit cơ số b modulo p. ở đây, ta có khái niệm hoàn 
toàn t−ơng tự. 
Giả sử B,P là các điểm của đ−ờng cong elliptic E, k là một số nguyên và P=kB. Khi 
đó ta nói k là logarit cơ sở B của P. Trong tr−ờng hợp E là đ−ờng cong trên tr−ờng 
Fq, q=p
r, p≠ 2, bài toán tìm logarit của các điểm trên một đ−ờng cong đòi hỏi thời 
gian mũ, và do đó, không thể thực hiện đ−ợc trong khoảng thời gian chấp nhận đ−ợc 
(nếu q đ−ợc chọn đủ lớn). 
Bây giờ giả sử có một tập hợp n cá thể cần trao đổi thông tin mật với nhau: 
A1,A2,...,An. 
Tr−ớc tiên, ta chọn một đ−ờng cong elliptic E trên tr−ờng hữu hạn Fq với một điểm 
B∈E dùng làm “cơ sở”. Những thông tin này đ−ợc thông báo công khai. Dĩ nhiên q 
phải là số đủ lớn. 
Sau đó, mỗi cá thể Aj chọn cho mình khoá ej, là một số nguyên nào đó. Khoá này 
đ−ợc giữ bí mật, nh−ng Aj thông báo công khai phần tử ejB. Điều này không làm lộ 
khoá ej do độ phức tạp của phép tính logarit. 
Giả sử Aj cần gửi thông báo mật m cho Ai. Tr−ớc tiên, m đ−ợc t−ơng ứng với điểm 
Pm∈E nh− đã trình bày ở trên. Sau đó, Aj sẽ chọn ngẫu nhiên một số s và chuyển cho 
Ai cặp điểm sau: (sB, Pm+s(eiB)), nhờ eiB đã đ−ợc công khai. Khi nhận đ−ợc cặp 
điểm này, Ai chỉ việc lấy số sau trừ đi ei lần số tr−ớc để nhận đ−ợc Pm: 
Pm=Pm+ s(eiB)- ei(sB). 
Chú ý rằng, chỉ có Ai làm đ−ợc điều này vì ei đ−ợc giữ bí mật, và số s không thể tìm 
thấy trong thời gian chấp nhận đ−ợc mặc dù biết sB, vì đó là logarit của (sB) cơ sở B. 
Trong hệ mã vừa trình bày, ta không cần biết số N của đ−ờng cong E. 
5.4. Hệ mã t−ơng tự mã mũ. 
Trong tr−ờng hợp này, các cá thể chọn chung cho mình một đ−ờng cong elliptic E 
trên tr−ờng hữu hạn Fq với N điểm. Các tham số này đ−ợc thông báo công khai. 
Để xây dựng hệ mã, mỗi cá thể Ai chọn cho mình khoá ei, là số nguyên d−ơng nằm 
giữa 1 và N, sao cho (ei,N)=1. Bằng thuật toán Euclid, Ai tìm đ−ợc di thoả mãn 
 127
diei≡ 1(mod N). Bây giờ, giả sử Ai cần gửi thông báo m cho Aj. Cũng nh− tr−ớc đây, 
Ai tìm điểm Pm t−ơng ứng trên đ−ờng cong. Sau đó, 
1) B−ớc 1: Ai gửi cho Aj thông báo eiPm. Dĩ nhiên, khi nhận đ−ợc thông báo này, Aj 
ch−a thể giải mã vì không biết ei và di. 
2) B−ớc 2: Aj nhận thông báo đ−ợc với ej và gửi trả lại cho Ai thông báo ej(eiPm). 
3) B−ớc 3: Ai lại gửi cho Aj thông báo sau khi đã nhân với di: di ej(eiPm). 
4) Nhận đ−ợc thông báo cuối cùng này, Aj nhân nó với khoá dj của mình để nhận 
đ−ợc Pm=djdieiejPm. Do cách chọn ei, di, ej,