Vietebooks Nguyn Hong Cng
Trang 26
Tiếp tục theo cách tơng tự, có thể tính đợc các bội còn lại nh sau:

= (2,7) 2 = (5,2) 3 = (8,3)
4 = (10,2) 5 = (3,6) 6 = (7,9)
7 = (7,2) 8 = (3,5) 9 = (10,9)
10 = (8,8) 11 = (5,9) 12 = (2,4)

Do đó = (2,7) thực sự là phần tử nguyên thuỷ.

Một đờng cong elliptic xác định trên Z
p
(p là số nguyên tố >3) sẽ có
khoảng p điểm. Chính xác hơn, theo một định lý nổi tiếng của Hasse, số các
điểm trên E ( kí hiệu là #E) thảo mãn bất đẳng thức sau:
Việc tính toán chính xác giá trị của #E có khó hơn nhng đã có một
thuật toán hữu hiệu do Schoof đa ra giúp tính toán dễ dàn hơn.( Nghĩa hữu
hiệu ở đây đợc hiểu là thời gian chạy của thuật toán là thời gian đa thức
theo log p. Thuật toán Schoof có thời gian chạy khoảng O((log p)
8
) phép tính
trên bít và có thể thực hiện đối với các số nguyên tố p có vài trăm chữ số).

Bây giờ giả sử có thể tính đợc #E. Vấn đề tiếp theo là phải tìm một
nhóm con cyclic trong E sao cho bài toán DL trong nó là khó. Bởi vậy ta
phải biết một vài điều về cấu trúc của nhóm E. Định lý sau đây cung cấp một
thông tin đáng kể về cấu trúc nhóm của E.

Định lý 5.1
Cho E là một đờng cong elliptic trên Z

Chú ý là nếu n
2
= 1 thì E là một nhóm cyclic. Cũng vậy, nếu #E là một
số nguyên tố hoặc là tích của các số nguyên tố khác nhau thì E là nhóm
cyclic có chỉ số nhóm cyclic.

Các thuật toán Shanks và Pohlig - Hellman có thể áp dụng cho bài
toán rời rạc trên đờng cong Elliptic song tới nay vẫn cha có một thuật toán
ppEpp 2121 ++#+
Vietebooks Nguyn Hong Cng
Trang 27
thích hợp cho phơng pháp tính chỉ số đối với các đờng cong Elliptic.Tuy
nhiên, đã có một phơng pháp khai thác đẳng cấu một cách tờng minh giữa
các đờng cong Elliptic trong trờng hữu hạn. Phơng pháp này dẫn đến các
thuật toán hữu hiệu đối với một số lớp các đờng cong Elliptic. Kỹ thuật này
do Menezes, Okamoto và Vanstone đa ra và có thể áp dụng cho một số
trờng hợp riêng trong một lớp đặc biệt các đờng cong Elliptic (đợc gọi là
các đờng cong siêu biến, chúng đã đợc kiến nghị sử dụng trong các hệ
thống mật mã). Tuy nhiên, nếu tránh các đờng cong siêu biến thì lại xuất
hiện một đờng cong Elliptic có một nhóm con cyclic cỡ 2
160
, đờng cong
này sẽ cho phép thiết lập an toàn một hệ mật miễn là bậc của nhóm con phải
là bội của ít nhất một thừa số nguyên tố lớn ( nhằm bảo vệ hệ mật khỏi
phơng pháp tấn công của Pohlig - Hellman).

Xét một ví dụ về phép mã Elgamal sử dụng đờng cong elliptic nêu
trên ví dụ 5.7.

Ví dụ 5.8.

anh ta giải mã nh sau:
x = (10,2) - 7(8,3)
= (10,2) - (3,5)
= (10,2) + (3,6)
= (10,9)
Đây chính là bản rõ đúng.

Trên thực tế có một số khó khăn khi áp dụng hệ mật Elgamal trên
đờng cong Elliptic. Hệ thống này đợc áp dụng trong Z
p ( hoặc trong
GF(p
n
) với n > 1) sẽ có hệ số mở rộng bản tin là 2. Việc áp dụng đờng cong
Vietebooks Nguyn Hong Cng
Trang 28
Elliptic sẽ có thừa số mở rộng khoảng 4 lần. Điều này là do có xấp xỉ p bản
rõ, nhng mỗi bản mã lại gổm bốn phần tử của trờng. Một trở ngại là không
gian bản rõ chứa các điểm trên đờng cong E và không có phơng pháp nào
xác định tờng minh các điểm trên E

Menezes và Vanstone đã tìm ra một phơng án hiệu quả hơn. theo
phơng án này đờng cong Elliptic dùng để "che dấu", còn các bản rõ và bản
mã hợp lệ là các cặp đợc sắp tùy ý các phần tử khác không của trờng( tức
là chúng không đòi hỏi phải là các điểm trên E). Điều này sẽ tạo hệ số mở
rộng bản tin là 2 giống nh trong hệ mật Elgamal ban đầu. Hệ mật Menezes
- Vanstone đợc mô tả trên hình 5.10.

Nếu trở lại đờng cong y
2
= x

K = { (E,
,a,) : = a }
trong đó
E. Các giá trị và đợc công khai, còn a đợc giữ kín.
Đối với K = (E,
,a,), với số ngẫu nhiên bí mật k Z
| H |

và x = (x
1
,x
2
) Z
p
*
ì Z
p
*
, ta xác định:
e
K
(x,k) = (y
0
,y
1
,y
2
)
y
0

1
c
1
-1
mod p, y
2
c
2
-1
mod p)
trong đó a y
0
= (c
1
,c
2
)
Vietebooks Nguyn Hong Cng
Trang 29
Ví dụ 5.9
Cũng nh ví dụ trớc, giả sử
= (2,7) và số mũ mật của Bob là 7. Khi
đó
= 7 = (7,2)
Giả sử Alice muốn mã hoá bản rõ sau:
x = (x
1
,x
2
) = (9,1)


y = (y
0
,y
1
,y
2
) = ((7,9), 6, 3)
Khi Bob nhận đợc bản mã này, Trớc tiên anh ta tính:

(c
1
,c
2
) = (a y
0
) = 7(7,9) = (8,3)
và sau đó tính:
x = (y
1
c
1
-1
mod p, y
2
c
2
-1
mod p)
= ((6

1
, . . . , x
n
) sao cho:

=
=
n
i
ii
?Tsx
0Vietebooks Nguyễn Hoàng Cương
Trang 30
5.3. HÖ mËt xªp ba l« merkle - Hellman