Khái niệm đường cong Eliptic

Trong vài thập kỷ gần đây, đường cong elliptic đóng vai trò quan trọng đối với lý thuyết số và mật mã. Mật mã đường cong elliptic (ECC) được giới thiệu lần đầu vào năm 1991 bởi các công trình nghiên cứu độc lập của Neals Koblitz và Victor Miller. Độ an toàn của ECC dựa vào bài toán logarit rời rạc trên nhóm các điểm của đường cong elliptic (ECDLP). Đối với bài toán logarit rời rạc trên trường hữu hạn hoặc bài toán phân tích số, tồn tại các thuật toán dưới dạng dạng hàm mũ để giải các bài toán này (tính chỉ số hoặc sàng trường số). Tuy nhiên, đối với bài toán ECDLP cho đến nay vẫn chưa tìm được thuật toán dưới hàm mũ để giải

1. Đường cong Elliptic trên trường số thực

Đường cong Elliptic là đường cong có dạng:

y²₌  x³ + 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³ + ax + b

Nếu a>0 , f(x) đơn điệu tăng.

Nếu a<0, f(x) có 4 trường hợp sau:  Đặt

Từ đó chúng ta có các trường hợp sau đây của đường cong Elliptic (không sử dụng trường hợp λ=0 vì lúc này đường cong bị gãy):

Hình dưới minh họa hai đường cong Elliptic  y²= x³ –x và y²=x³ + x + 1

Trong đường cong Elliptic, chúng ta định nghĩa thêm một điểm O (điểm vô cực).

Gọi  E(a, b) là tập các điểm thuộc đường cong y²₌  x³ + ax + b cùng với điểm O. Ta định nghĩa phép cộng trên tập các điểm thuộc E(a, b) như sau:

1. Điểm O là phần tử đơn vị của phép cộng. Như vậy với  P∈ E(a,b), P ≠ 0 thì P + 0 = 0+P=P . Trong phần tiếp theo ta giả định P ≠0 và Q≠0.
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 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 = -P  thì  đường  thẳng  nối  P,  Q  sẽ  cắt  đường  cong  Elliptic  tại  vô  cực,  hay P + ( -P )=0. Điều này phù hợp với định nghĩa 2.

• Để  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= -S.

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à Delta:

Ta tính được:

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ó:

2. Đường cong Elliptic trên trường Zp

Đường  cong  Elliptic  trên  trường  Zp  là  đường  cong  có  các  hệ  số  thuộc  trường  Zp, đường cong này có dạng:

y² mod p ₌  (x³ + ax + b) mod p

Ví dụ trong trường Z₂₃, chọn a =1,b=1,x=9,y=7 ta có:

7 ² mod 23=(9³+ 9 +1)mod 23

49mod 23= 739 mod 23 =3

Khác  với  đường  cong  Elliptic  trong  trường  số  thực,  chúng  ta  không  thể  biểu  diễn đường cong Elliptic  Zp  bằng đồ  thị  hàm số  liên tục.  Bảng bên dưới liệt kê các điểm (x, y) của đường cong trong trường Z₂₃  với a=1, b=1:

Cũng tương tự  như khái niệm đối xứng qua trục hoành của đường cong Elliptic số thực, đường cong Elliptic Zp cũng đối xứng theo nghĩa đối xứng modulo. Giả sử điểm (x, y) thuộc đường cong Elliptic Zp  trên thì điểm (x, p – y) cũng thuộc đường cong trên vì:

(p-y)² ₌ p² – 2py + y² ≡ y² 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ó.

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 đó:

Ví dụ: trong E₂₃ (1,1) , chọn P = (3,10), Q=(9,7), vậy:

3. Đường cong Elliptic trên trường GF(2m)

Đường cong Elliptic trên trường GF(2^m) là đường cong có các hệ  số  thuộc trường GF(2^m), đường cong này có dạng hơi khác so với trên Zp:

y² + xy ₌  x³ + ax + b    a,b,x,y ∈ GF(2^m)

Bây giờ  chúng ta sẽ  xét tập E₂^m(a,b)  gồm các điểm trên đường cong Elliptic này cùng với điểm vô cực O.

Ví dụ, xét trường GF(2^m) với đa thức tối giản là m(x) = x⁴ + x + 1. Phần tử  sinh  g của trường này có điều kiện g⁴ = 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⁴):

y² + xy =  x³ + gx + 1 (a=g⁴, b=1)

Bảng bên dưới liệt kê các điểm thuộc đường cong này