Hệ mật mã khóa công khai dựa trên đường cong Elliptic

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

3
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài báo "Hệ mật mã khóa công khai dựa trên đường cong Elliptic" nhằm mục đích tổng hợp những khái niệm và kiến thức cơ bản nhất của EC liên quan đến cơ sở toán học của Hệ mật dựa trên đường cong Elliptic.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Hệ mật mã khóa công khai dựa trên đường cong Elliptic

HỆ MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN ĐƯỜNG CONG ELLIPTIC Vũ Văn Nam 1 1. Viện Kỹ Thuật Công Nghệ, Trường Đại học Thủ Dầu Một TÓM TẮT Blockchain lần đầu tiên được phát minh và thiết kế bởi Satoshi Nakamoto vào năm 2008 và được hiện thực hóa vào năm sau đó như là một phần cốt lõi của Bitcoin, khi công nghệ blockchain đóng vai trò như là một cuốn sổ cái cho tất cả các giao dịch. Nền tảng cơ sở của Bitcoin chính là lý thuyết về mật mã mà cụ thể ở đây là hàm băm và lý thuyết về chữ ký số dựa trên Hệ mật đường cong Elliptic (ECC - Elliptic Curve Cryptography). Bên cạnh việc sử dụng trong tiền số Bitcoin, ECC còn được ứng dụng rất nhiều trong thực tiễn ngành Công nghệ thông tin [1]. Các trang Web bảo mật https(http-secure) thường được dùng trong thanh toán điện tử hay ứng dụng riêng tư nhưgmail đều sử dụng các giao thức TLS (Transport Layer Security) mà trước đó là SSL (Secure Socket Layer). Trong các giao thức này ECC được sử dụng để trao đổi khóa phiên. Các giao dịch remote access được sử dụng rất nhiều trong thế giới Unix, Linux là SSH (Secure SHell) cũng sử dụng ECC để trao đổi khóa. Ưu điểm của hệ mật sử dụng đường cong Elliptic (ECC) là có độ dài khóa nhỏ (160 bit tương đương với khóa độ dài 1024 Bit trong hệ mật RSA), do sử dụng độ dài khóa nhỏ nên tài nguyên phục vụ cho ECC thường nhỏ hơn rất nhiều, bên cạnh đó hiệu năng tính toán cũng được nâng cao rõ rệt. Hiện nay ECC đang là xu thế để thay thế RSA. Các phương trình của đường cong Elliptic có một đặc điểm hết sức có giá trị cho mục đích mã hóa, vì chúng dễ thực hiện nhưng vô cùng khó đảo ngược. ECC được phát triển bởi Certicom, một nhà cung cấp hệ thống bảo mật kinh doanh điện tử trên điện thoại và gần đây được cấp phép bởi Hifn, nhà sản xuất vi mạch tích hợp và các sản phẩm an ninh mạng. Rất nhiều công ty bao gồm 3COM, Cylink, Motorola, Pitney Bowes, Siemens, TRW và VeriFone có hỗ trợ ECC trên các sản phẩm của họ. Bài báo này nhằm mục đích tổng hợp những khái niệm và kiến thức cơ bản nhất của EC liên quan đến cơ sở toán học của Hệ mật dựa trên đường cong Elliptic. Từ khóa: Nhóm giao hoán, Elliptic, giải mã, khóa, mã hóa, modulo. 1. ĐẶT VẤN ĐỀ 1.1 Nhóm giao hoán – Nhóm Abel Một nhóm giao hoán hay nhóm Abel là một tập hợp, G, cùng với một phép toán hai ngôi, "*", từ G×G → G thỏa mãn các tính chất sau: 1. Tính kết hợp: phép toán có tính kết hợp, tức là (a*b)*c = a*(b*c) với mọi a, b và c  G. 2. Phần tử đơn vị: tồn tại duy nhất một phần tử gọi là phần tử đơn vị (ký hiệu là e) sao cho với mọi phần tử a G thì a*e = e*a = a. 3. Phần tử nghịch đảo: với mỗi phần tử a thuộc G tồn tại duy nhất một phần tử x, gọi là phần tử nghịch đảo của a, sao cho x*a = a*x = e. x được ký hiệu là a-1. 521
4. Tính giao hoán: phép toán có tính giao hoán, tức là a*b = b*a với mọi a, b  G. Ví dụ 1: (Z, +) tức là tập số nguyên với phép cộng, là một nhóm Abel, trong đó số 0 là phần tử đơn vị e. Dễ thấy a+0=0+a  a  Z. Phần tử nghịch đảo của a là (–a) là duy nhất. Ta có a+(-a) = 0 = phần tử đơn vị. Phép cộng có tính kết hợp và tính giao hoán. Ví dụ 2: (Z, ) tức là tập số nguyên với phép nhân, không là một nhóm Abel, trong đó số 1 là phần tử đơn vị e. Dễ thấy a x 1 = 1 x a,  a  Z. Tuy nhiên với  a  Z thì phần tử nghịch đảo của a là a-1 = 1/a không phải là số nguyên  a  Z. Cơ sở toán học của hệ mật ECC là nhóm giao hoán Abel các điểm nằm trên đường cong Elliptic. Ngoài việc đường cong Elliptic là cơ sở cho hệ mật ECC, hệ mật ID-Based, đường cong Elliptic (EC) còn là công cụ hữu hiệu để phân tích số nguyên ra thừa cố nguyên tố [2, 3], hoặc dùng để kiểm tra tính nguyên tố của số nguyên [2]. EC cũng là cơ sở để chứng minh định lý Fermat nổi tiếng đã tồn tại nhiều trăm năm qua. Trong bài viết này, các đường cong Elliptic sẽ được nghiên cứu dưới dạng sau: y2 = x3 + Ax + B; Trong đó A và B là các hằng số. Các giá trị của x; y; A; B thường là các giá trị trên một trường nào đó, ví dụ như R (số thực), Q (số hữu tỷ), C (số phức). Nếu K là một trường có a; b  K, khi đó ta nói đường cong Elliptic được định nghĩa trên trường K. Điểm (x; y) trên đường cong Elliptic với (x; y)  K được gọi là điểm K–Hữu tỷ. [5] 1.2 Các loại đường cong Elliptic [3] Đường cong Elliptic có thể được phân loại dựa trên số giao điểm với trục x, hay được gọi là nghiệm của phương trình x3 + ax + b = 0. ▶ Xét x → ±∞, số giao điểm với trục x có thể = 1, hoặc 2, hoặc 3. Hình 1: Số giao điểm bằng 1 522
Hình 2: Số giao điểm = 3 Hình 3: Số giao điểm = 2 523
Ở ví dụ hình 1 và 2, đường cong được gọi là chuẩn tắc (thông thường). Trong ví dụ hình 3, đường cong được gọi là đặc biệt vì phương trình bậc 3 x3 + ax + b = 0 có nghiệp kép. Để loại trừ các đường cong đặc biệt chúng ta giả sử rằng định thức ∆ = 4a3 + 27b2  0. 2. CÁC PHÉP TOÁN TRÊN ĐƯỜNG CONG ELLIPTIC 2.1 Phép cộng hai điểm trên đường cong Elliptic [3] Cho đường cong Elliptic E và hai điểm P, Q ∈ E, chúng ta định nghĩa phép cộng P + Q ∈ E như sau: Hình 4: Mô tả phép cộng trên đường cong Elliptic ▶ Kẻ đường thẳng L qua hai điểm P và Q. Đường thẳng L sẽ cắt đường cong Elliptic E tại điểm thứ 3 R. ▶ Lấy đối xứng điểm R qua trục x ta nhận được điểm S. Lưu ý rằng nếu R = (x, y) ∈ E, thì S = (x, -y) ∈ E. ▶ Ta định nghĩa P + Q = S. Các trường hợp đặc biệt trong phép cộng: ▶ Nếu chúng ta thử cộng điểm P vào chính nó thì quá trình sẽ không hoạt động, do một điểm đơn không xác định được một đường thẳng. Thay vào đó, trong trường hợp này, chúng ta lấy L là tiếp tuyến của đường cong tại điểm P. Đường thẳng L cắt đường cong E tại một điểm R mới, và chúng ta lấy đối xứng R theo trục x để có được S. Cho đến nay, P + Q được xác định rõ ràng trừ khi chúng nằm trên một đường thẳng đứng, đường thẳng này sẽ không cắt đường cong Elliptic E tại một điểm khác. ► Để khắc phục khó khăn này chúng ta tạo thêm một điểm gọi là điểm ở vô cực. Chúng ta coi nằm ở trên cùng và dưới cùng của mọi đường thẳng đứng. Do đó, nếu P, Q ∈ E nằm trên một đường thẳng đứng thì P = (x, y) và Q = (x, -y), và ta định nghĩa P + Q = . Làm thế nào để thực hiện phép cộng với điểm vô cực ? ► Cho P = (x, y) ∈ E, để tính P + , lưu ý rằng đường thẳng L đi qua P và là đường thẳng đứng đi qua P. L cắt E tại Q = (x, −y), và lấy đối xứng Q qua trục x trả lại P. Do đó P + = P. ► Điểm ở vô cực, , đóng vai trò giống như số 0 hoặc phần tử đơn vị cho phép cộng của chúng ta, và do đó chúng ta định nghĩa + = . 524
► Nếu Q là đối xứng của P qua trục x thì P + Q = . ► Do đó, chúng ta có thể viết −P = Q, và −P là nghịch đảo cộng của P. Quan sát rằng nếu P = (x, y) thì −P = (x, − y). 2.2 Đường cong Elliptic là nhóm Abel Quy tắc cộng trên đường cong Elliptic có các tính chất sau: Với mọi P, Q và R trên đường cong hoặc bằng : (1) P + Q nằm trên đường cong hoặc bằng , (2) P + = + P = P, (3) P + ( −P) = , (4) P + (Q + R) = (P + Q) + R, và (5) P + Q = Q + P. Nói cách khác, các điểm trên đường cong Elliptic cùng với tạo thành một nhóm Abel: ► Nghịch đảo của P là −P và đơn vị là điểm ở vô cực . ► Nhóm bao gồm tất cả các điểm trên đường cong cùng với điểm ở vô cực, được trang bị phép cộng, có thể được tham chiếu đến một đường cong Elliptic. 2.3 Công thức đại số cho phép cộng [4] Giả sử E là đường cong Elliptic cho bởi y2 = x3 + ax + b, với ∆ = 4a3 + 27b2  0. Cho P = (x,y), P1 = (x1, y1) và P2 = (x2, y2) là các điểm trên E. Đầu tiên, chúng tôi liệt kê một số trường hợp đặc biệt không nằm trong trường hợp tổng quát sau đây. (1) P + = + P = P. (2) Nếu P1 P2 và x1 = x2 thì P1 + P2 = . (3) Nếu P1 = P2 và y1 = 0 thì P1 + P2 = 2P1 = . Bây giờ ta đưa ra trường hợp tổng quát. (1) Nếu P1  P2 (và x1  x2), y2 − y1 y x − y2 x1 đặt  = và  = 1 2 x2 − x1 x2 − x1 (2) Nếu P1 = P2 (và y1  0), 3x1 + a 2 − x3 +ax1 + 2b đặt  = và  = 1 2 y1 2 y1 Khi đó P1 + P2 = (λ2 − x1 − x2, −λ3 + λ(x1 + x2) – ν). (1) Nếu chúng ta viết P1 + P2 = (x3, y3), với công thức x3 và y3 như trên, thì một công thức thay thế cho y3 là y3 = λ(x1 − x3) − y1. Vậy ta có P3(x3, y3) = P1 + P2 thì x3 = λ2 − x1 − x2 và y3 = λ(x1 − x3) − y1 và có thể bỏ qua ν. (2) Đường thẳng L trong mô tả hình học là y = λx + ν, với λ và ν đã cho ở trên. 525
3. ĐƯỜNG CONG ELLIPTIC THEO MODULO p Định nghĩa: Đường cong Elliptic modulo p là một đồng dư có dạng y2 ≡ x3 + ax + b (mod p), trong đó a và b là các số nguyên thỏa mãn 4a3 + 27b2 ≢ 0 (mod p). Việc đưa điều kiện thứ hai vào có nghĩa là chúng ta thực sự đang định nghĩa một đường cong Elliptic chuẩn tắc, nhưng vì chúng ta chỉ giải quyết trường hợp này nên chúng ta thường bỏ việc này. 3.1 Cấu trúc nhóm Abel [3] Các điểm trên đường cong Elliptic modulo p, cùng với điểm ở vô cực và phép toán được xác định bằng phép cộng đại số của các điểm modulo p, tạo thành một nhóm Abel có cấp hữu hạn. ► Phần khó khăn là chứng minh định luật kết hợp. Điều này có thể được thực hiện bằng cách sử dụng các công thức, nhưng khá dài và khó nên sẽ được trình bày ở bài viết sau. ▶ Điểm ở vô cực , là phần tử đơn vị và nghịch đảo của P = (x, y) là −P = (x, −y) = (x, p − y). Chú ý rằng đường cong Elliptic E sẽ có trục đối xứng y = p/2, chứ không phải y = 0 như đường cong Elliptic tổng quát. Ta có (-y) (mod p) = (p-y) (mod p), nên ta có điểm đối của điểm P(x,y) là –P(x,p-y) (mod p). Ví dụ: Tìm tất cả các điểm trên đường cong Elliptic E: y2 ≡ x3 + 4x + 4 (mod 5). Lưu ý rằng a = 4 và b = 4, do đó 4a3 + 27b2 = 4 · 64 + 27 · 16 ≡ (−1)(−1) + 2 · 1 ≡ 3 ≢ 0 (mod 5), và đường cong là chuẩn tắc. Ta chỉ cần xét các giá trị 0, 1, 2, 3, 4 cho x và y. Thay vào thặng dư bậc 2 ta thấy có 7 điểm trên đường cong là (0, 2), (0, 3), (1, 2), (1, 3), (2, 0), (4 , 2), (4, 3). 3.2 Vô cực và phép cộng Chúng ta có thể cộng các điểm trên đường cong lại với nhau với một điểm ở vô cực . Cộng các điểm trên đường cong Elliptic: ► (x1, y1) + = (x1, y1), ► (x1, y1) + (x1, −y1) = , ► ngược lại (x1, y1) + (x2, y2) = (x3, y3), trong đó x3 = λ2 − x1 − x2, y3 = λ(x1 − x3) − y1, và  y2 − y1 x − x Nếu x1  x2 hoặc y1  y2  2 1 = 2  3x1 + a Nếu x1 = x2 và y1 = y2  2 y1  Chú ý: Tất cả đều (mod p)!!! Ví dụ: Tính (1, 2) + (4, 3) cho đường cong vừa xét: y2 ≡ x3 + 4x + 4 (mod 5). Chúng ta thấy rằng: y2 − y1 3 − 2 −1 = = = 3  2(mod5) x2 − x1 4 − 1 x3 = λ2 − x1 − x2 = 4 − 1 − 4 ≡ 4 (mod 5) và y3 = λ(x1 − x3) − y1 = 2(1 − 4) − 2 ≡ 2 (mod 5). Tức là (1, 2) + (4, 3) = (4, 2). Lưu ý rằng d−1 được diễn giải bằng cách giải d−1d ≡ 1 (mod p). Vì vậy, giải 3x ≡ 1 (mod 5) ở trên, ta có 3−1 ≡ 2 (mod 5). Để làm rõ thêm về cách tính thặng dư bậc 2 modulo p, ta xét ví dụ sau: Tìm tất cả các điểm trên đường cong Elliptic E : y2 ≡ x3 + x + 6 (mod 11). Bước 1: Đầu tiên lưu ý rằng 4a3 + 27b2 ≡ 8 ≢ 0 (mod 11). Bước 2: Sau đó tính thặng dư bậc hai (QR- quadratic residues) modulo 11: 526
Rõ ràng sau một quãng p =11 giá trị nguyên liên tiếp thì x (mod p) sẽ quay lại giá trị ban đầu, vì vậy chúng ta sẽ lấy 11 giá trị đại diện cho x từ 0 đến 10, và đó cũng chính là các số dư khi chia một số nguyên cho p = 11. Dòng thứ hai ta tính i2 (mod p), đại diện cho vế trái y2 (mod p). i 0 1 2 3 4 5 6 7 8 9 10 i2 (mod 11) 0 1 4 9 5 3 3 5 9 4 1 Bảng 1: Thặng dư bậc 2 modulo 11 Lưu ý rằng ở đây chúng ta gọi 0 là thặng dư bậc hai; điều này không hoàn toàn chính xác và hoàn toàn là để thuận tiện. Bước 3: Bây giờ chúng ta tính điểm trên đường cong: Ta thấy với x = 2 thì x3 + x + 6 = 8 + 2 + 6 = 16  5 (mod 11). Tra bảng trên ta có 2 giá trị 4 và 7 khi bình phương lên rồi (mod 11) = 5. Do đó ứng với x = 2, ta có 2 giá trị tương ứng y1 = 4 và y2 = 7 có cùng thặng dư bậc hai (QR- quadratic residues) modulo 11. Hay nói cách khác là ta tìm được 2 điểm (2,4) và (2,7) thuộc đường cong Elliptic E. Dễ thấy 2 điểm này có y1=4, y2=7 và 4+7 =11 = p. Do đó hai điểm này chính là nghịch đảo của nhau trong nhóm Abel. Tương tự ta kiểm tra tiếp cho các trường hợp khác. Rõ ràng thặng dư bậc hai (QR- quadratic residues) modulo 11 chỉ thuộc vào tập giá trị {1, 3, 4, 5, 9} nên các số dư khác ta bỏ qua. x x3 + x + 6 QR? y 0 6 1 8 2 5 ✓ 4,7 3 3 ✓ 5,6 4 8 5 4 ✓ 2,9 6 8 7 4 ✓ 2,9 8 9 ✓ 3,8 9 7 10 4 ✓ 2,9 Bảng 2: Đối chiếu thặng dư bậc 2 tìm các cặp điểm trên đường cong Elliptic Bước 4: Bao gồm điểm ở vô cực, nhóm có 13 phần tử: , (2, 4), (2, 7), (3, 5), (3, 6), (5, 2), ( 5, 9), (7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9) Hình 5: Biểu diễn các điểm của đường cong Elliptic E trên mặt phẳng 527
3.3 Bài toán logarit rời rạc trên đường cong Elliptic [3] Trong bài toán logarit rời rạc, ta được cho b sao cho b ≡ ak (mod p), trong đó p là số nguyên tố và a là nghiệm nguyên thủy modulo p, và chúng ta muốn tìm k. Đối với đường cong Elliptic, phép tính không phải là phép nhân mà là phép cộng. Bài toán tương ứng là: Cho điểm A và B trên đường cong Elliptic và biết rằng: tìm k? Trong số học modulo tiêu chuẩn, có một cách hiệu quả để tính ak (mod p), đó là bằng cách bình phương lặp lại. Phương pháp tương ứng trong số học đường cong Elliptic để tính kA là lặp lại phép nhân đôi. Tức là ta tính được 2A, 4A, 8A, 16A,... . . , rồi cộng các giá trị này một cách thích hợp để có kA. Ví dụ: 11A = 8A + 2A + A. 3.4 Nhân vô hướng các điểm trên đường cong Elliptic [5] Với n  N \ {0} định nghĩa phép nhân vô hướng của điểm P nằm trên đường cong E là phép cộng n lần chính bản thân điểm P: Để tối ưu phép nhân vô hướng, có thể sử dụng phương pháp Nhân đôi-và-cộng, đầu tiên biểu diễn số n dưới dạng: n = n0 + 2n1 + 22n2 + · · · + 2mnm với [n0…nm]  {0; 1}, sau đó áp dụng thuật toán: Phương pháp Nhân đôi-và-cộng 1: Q  0 2: for i = 0 to m do 3: if ni = 1 then 4: Q  CộngĐiểm(Q, P) 5: end if 6: P  NhânĐôi(P) 7: end for 8: return Q Nói một cách đơn giản: Ta phân tích số n hay k ra hệ nhị phân, duyệt trên dãy nhị phân đó, nếu gặp bit 1 ta làm phép cộng Q = Q + P, rồi lại nhân đôi P do mỗi vị trí bit trong số nhị phân về mặt giá trị hơn kém nhau 2 lần. Nên vị trí tăng lên 1 thì giá trị tăng thêm 21 = 2. 4. ĐƯỜNG CONG ELLIPTIC VÀ HỆ MẬT MÃ ELGAMAL Nhiều hệ thống mật mã, bao gồm tất cả các hệ thống liên quan đến logarit rời rạc, đều có các phiên bản đường cong Elliptic. Ngoài ra còn có các phiên bản RSA và thuật toán phân tích nhân tử tốt sử dụng đường cong Elliptic. Một số trong số này sử dụng các số modulo đường cong khác với số nguyên tố và cũng cho phép sử dụng các đường cong đơn lẻ. Chúng ta sẽ chỉ xem xét một ứng dụng, đó là hệ thống mật mã đường cong Elliptic ElGamal. 528
4.1 Thiết lập hệ mật mã Elliptic ElGamal [3] 1. Chọn số nguyên tố p và đường cong Elliptic chuẩn tắc E modulo p. 2. Chọn một điểm α trên E. Chọn một số nguyên s nhỏ hơn bậc của α. k là bậc của α nếu kα = . 3. Tính β = sα. Công khai E, p, α và β, nhưng không công khai s. Khóa riêng là s. Để an toàn, p và bậc của α sẽ cần phải lớn. Lưu ý rằng để công bố đường cong elliptic E, chúng ta chỉ cần xác định các số a và b từ công thức y2 ≡ x3 + ax + b (mod p). 4.2 Mã hóa và giải mã Mã hóa: 1. Sử dụng phương pháp đã thỏa thuận, văn bản được chuyển đổi thành điểm x (hoặc các điểm) trên đường cong. Chọn ngẫu nhiên một số k rồi tính: γ1 = kα và γ2 = x + kβ. 2. Truyền γ1 và γ2. Lưu ý đây là các điểm trên E nên phải truyền đi 4 số, là tọa độ của γ1 và γ2 trên đường cong Elliptic E. Giải mã: 1. Tính điểm trên E cho bởi γ2 − sγ1. Đây sẽ là điểm ban đầu x. Để kiểm tra xem quá trình giải mã có hoạt động hay không: γ2 − sγ1 = x + kβ − skα = x + ksα – skα = x. Ví dụ: Sử dụng ví dụ trước E : y2 ≡ x3 + x + 6 (mod 11) với α = (2, 7) và khóa bí mật s = 10. Tính β = 10α = (8, 8). Giả sử có người muốn gửi tin nhắn x = (3, 5). Chọn số k = 3 và tính: γ1 = kα = 3(2, 7) = (8, 3), γ2 = x + kβ = (3, 5) + 3(8, 8) = (2, 4 ). Truyền (8, 3) và (2, 4). Để giải mã: Tính γ2 − sγ1 = (2, 4) − 10(8, 3) = (3, 5), chính là x được gửi đi. 5. KẾT QUẢ VÀ THẢO LUẬN Nhóm Abel với các tính chất kết hợp, giao hoán, cùng phần tử đơn vị và nghịch đảo trên tập dữ liệu đóng và phép toán hai ngôi đảm bảo cho kết quả các phép toán luôn là một ánh xạ thuộc vào tập dữ liệu đóng đó. Đường cong Elliptic E: y2 = x3 + Ax +B, có = 4a3 + 27b2  0, với phép toán cộng (+) được định nghĩa: với 2 điểm P, Q  E, kẻ đường thẳng L qua P,Q cắt E tại R. Lấy đối xứng R qua trục x, ta được điểm SE. S chính là tổng của P+Q. Như vậy kết quả của phép cộng (+) trên đường cong Elliptic E luôn thuộc một điểm trên E. Để đảm bảo đường cong Elliptic là một nhóm Abel, chúng ta bổ sung thêm điểm ở vô cực trên hai đầu mỗi đường thẳng song song với trục y làm phần tử đơn vị. Phần tử nghịch đảo của điểm P(x,y) có tọa độ là P’(x,-y). Rõ ràng đường thẳng L nối P và P’ luôn song song với trục y, vì nếu không song song, nó sẽ cắt đường cong Elliptic E tại 1 điểm thứ 3 khác. Do tính 529
chất đối xứng của đường cong Elliptic E nên L sẽ cắt thêm đường cong Elliptic E tại điểm thứ 4. Điều này mâu thuẫn vì phương trình bậc 3 chỉ có tối đa 3 nghiệm. Để áp dụng đường cong Elliptic E vào hệ mật ElGamal, chúng ta sử dụng đường cong Elliptic E với modulo p, y2 = x3 + Ax + B (mod p) có = 4a3 + 27b2 ≢ 0 (mod p). Tất cả các tính toán đều qui về modulo p. Ngoài phần tử đơn vị là điểm ở vô cực, ta còn có phần tử nghịch đảo của điểm P(x,y) có tọa độ là P’(x,p-y), do (p-y) (mod p) = (-y) (mod p). Số điểm của đường cong Elliptic E (mod p) là hữu hạn, do phụ thuộc vào thặng dư bậc 2 với modulo p. Tuy nhiên đường cong Elliptic E modulo p thỏa mãn tất cả mọi tính chất của một nhóm Abel. Ngoài phép cộng thông thường theo modulo p, ta còn có phép nhân vô hướng một điểm P với một số k tự nhiên, bản chất là việc lặp lại phép cộng nhiều lần với điểm P. Để tăng tốc độ tính toán, chúng ta có thể sử dụng giải thuật Nhân đôi và cộng với modulo p. Để thiết lập hệ mật mã Elliptic ElGamal ta chọn số nguyên tố p lớn và đường cong Elliptic chuẩn tắc E modulo p. Chọn một điểm α trên E và một số nguyên s nhỏ hơn bậc của α. Tính điểm β = sα. Công khai khóa E(a,b), p, α và β, giữ s làm khóa riêng. Để mã hóa, văn bản được chuyển đổi thành điểm x (hoặc các điểm) trên đường cong E. Chọn ngẫu nhiên một số k rồi tính: γ1 = kα và γ2 = x + kβ. Truyền γ1 và γ2. Giải mã: Tính điểm trên E cho bởi γ2 − sγ1. Đây sẽ là điểm ban đầu x. Để so sánh ECC với RSA, chúng tôi sử dụng kết quả nghiên cứu được đưa ra trong [6] với các biểu bảng về độ lớn nhỏ nhất tương đương của hai phương pháp. Số bit an toàn Giải thuật mã hóa đối xứng Độ lớn (bits) nhỏ nhất của Khóa công khai RSA ECC 80 Skipjack 1024 160 112 3DES 2048 224 128 AES-128 3072 256 192 AES-192 7680 384 256 AES-256 15360 512 Bảng 3: So sánh bảo mật cho các kết hợp kích thước khóa thuật toán khác nhau Đặc biệt, thời gian bẻ khóa, được đo bằng MIPS Years ( Million Instructions Per Second – Một triệu phép tính trên giây, được tính trong thời gian một năm) rất khác biệt. Bảng 4: Hiệu năng của RSA và ECC 530
6. KẾT LUẬN Lý thuyết về mật mã, đặc biệt là về chữ ký số dựa trên Hệ mật đường cong Elliptic (ECC - Elliptic Curve Cryptography). Bên cạnh việc sử dụng trong tiền số Bitcoin, ECC còn được ứng dụng rất nhiều trong thực tiễn ngành Công nghệ thông tin, đặc biệt là bảo mật của các trang Web có thanh toán điện tử hay ứng dụng riêng tư. Trong các giao thức này ECC được sử dụng để trao đổi khóa phiên. Ưu điểm của hệ mật sử dụng đường cong Elliptic (ECC) là có độ dài khóa nhỏ tiết kiệm được tài nguyên và nâng cao hiệu năng tính toán. Hiện nay ECC đang là xu thế để thay thế RSA. Khóa mật mã là bất đối xứng và có 2 phần: Phần khóa công khai và khóa riêng. Với số nguyên tố p lớn và việc tính toán modulo trên lũy thừa bậc cao đòi hỏi tốn rất nhiều thời gian và việc bẻ khóa là bất khả thi. Bài báo này nhằm mục đích tổng hợp những khái niệm và kiến thức cơ bản nhất của EC liên quan đến cơ sở toán học của Hệ mật dựa trên đường cong Elliptic, đưa ra các ví dụ về cách tính toán các phép cộng, nhân vô hướng trên đường cong Elliptic, đồng thời có các ví dụ về cách tính số điểm trên đường cong Elliptic modulo p, cũng như mã hóa và giải mã ElGamal trên đường cong Elliptic. TÀI LIỆU THAM KHẢO 1. J. W. Bos, J. A. Halderman, N. Heninger, J. Moore, M. Naehrig, and E. Wustrow, “Elliptic Curve Cryptography in Practice,” Financial Cryptography and Data Security, vol. 8437, pp. 157–175, 2014. 2. L. C. Washington, Elliptic Curves Number Theory and Cryptography, Second Edition. CRC Press, 2008. 3. Chayne Planidlen (2023). Mathematics for Cryptography. University of Wollongong, School of Mathematics and Statistics. 4. J. H. Silverman, The Arithmetic of Elliptic Curves. Springer, 2009. 5. Đặng Minh Tuấn, Chế tạo thiết bị VPN IPSec bằng phần cứng đầu tiên ở Việt Nam, Tạp chí CNTT & TT, No. 2, pp. 41–45, 2014. 6. Kerry Maletsky, RSA vs. ECC Comparison for Embedded Systems, Microchip Technology Inc. White Paper DS00003442A. 531