Hệ mật mã dựa trên đường cong Elliptic - Nguyễn Ánh Việt

Công nghệ thông tin N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” 224 HỆ MẬT MÃ DỰA TRÊN ĐƯỜNG CONG ELLIPTIC Nguyễn Ánh Việt1*, Nguyễn Kim Tuấn2 Tóm tắt: Các ý tưởng về an ninh thông tin dẫn đến sự phát triển của ngành mật mã học. Nói cách khác, mật mã học là “khoa học giữ an toàn thông tin”. Nó bao gồm việc mã hóa và giải mã các thông điệp. Mã hóa là quá trình chuyển đổi một văn bản đơn giản thành văn bản mật mã và giải mã là quá trình lấy lại thông điệp ban đầu từ văn bản mã hoá. Về mật mã học ngoài việc mang tính bảo mật, thì mang tính xác thực, tính toàn vẹn và tính chống chối bỏ. Mấu chốt của mật mã nằm trong khóa công khai và khóa bí mật của các khóa được sử dụng để mã hóa hoặc giải mã. Một yếu tố quan trọng khác là là kích thước của khóa sao cho khó có thể thực hiện giải mã theo cách thuần túy. Đã có nhiều thuật toán mật mã được gợi ý trong một số tài liệu về mật mã học. Trong bài báo này, chúng tôi nghiên cứu và phân tích các hệ thống mật mã dựa trên đường cong Elliptic (ECC) và đơn giản hóa thành những thuật toán gần với các ngôn ngữ đặc tả của chuyên ngành CNTT. Thuật toán mã hóa đường cong Elliptic đã được chứng minh là mạnh hơn các thuật toán đã biết như RSA / DSA. Từ khóa: Đường cong Elliptic; Hệ mật mã công khai; Elliptic Curve. 1. MỞ ĐẦU Tháng 3 năm 2016, Bộ Ngoại Giao Hoa Kỳ, đứng đầu là bộ trưởng John Kerry, đã dẫn một đoàn đại biểu tới các nước ASEAN trong đó có Việt Nam để thảo luận về phát triển Fintech và đặc biệt là về công nghệ Blockchain. Tháng 9 năm 2015, ủy ban giao dịch hàng hoá tương lai Mỹ công bố, Bitcoin đã chính thức được đưa vào danh sách hàng hóa được phép giao dịch tại Mỹ. Công nghệ Blockchain và Bitcoin là công nghệ tiền số ra đời năm 2009 và ngày càng có nhiều quốc gia và các tổ chức, doanh nghiệp cho phép lưu hành và thanh toán bằng loại tiền số này trong không gian mạng Internet toàn cầu. Tháng 4-2016, giá trị thương mại của Bitcoin đã lên đến 6.5 tỷ USD. 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). 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ơ 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ố Thông tin khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 225 nguyên ra thừa cố nguyên tố [2, 3, 4], hoặc dùng để kiểm tra tính nguyên tố của số nguyên [3]. 2. BÀI TOÁN LOGARITHM RỜI RẠC Định nghĩa 2. Bài toán Logarithm rời rạc trên đường cong Elliptic (ECDLP): Cho đường cong E trên trường hữu hạn Fq, điểm ∈ () với bậc ( = = ∞) và điểm ∈ (), tìm số nguyên ∈ [0, − 1]sao cho Q = kP. Số nguyên k được gọi là Logarithm rời rạc của Q với cơ sở P, được viết là k = logP Q. Bất kỳ một hệ mật khóa công khai nào cũng phải sử dụng một bài toán khó để xây dựng hàm một chiều. Ý nghĩa một chiều ở đây có nghĩa là tính thuận thì dễ (thuật toán giải trong thời gian đa thức) và tính ngược thì khó (thuật toán giải với thời gian không phải là đa thức - thường là hàm mũ hoặc nửa mũ). Các tham số của Hệ mật dựa trên đường cong Elliptic (ECC) cần phải được lựa chọn cẩn thận để tránh được các tấn công đối với bài toán ECDLP. Thuật toán vét cạn để giải bài toán ECDLP là lần lượt tính thử các điểm P, 2P, 3P,... cho đến khi điểm mới tính được đúng bằng điểm Q. Trong trường hợp xấu nhất sẽ phải cần đến n bước thử, trung bình thường là n/2 là đạt được điểm Q, do đó cần phải chọn n đủ lớnđể bài toán vét cạn là không khả thi (n ≥ 2160). Thuật toán tốt nhất hiện nay để tấn công bài toán ECDLP là sự kết hợp của thuật toán Pohlih-Hellman và Pollard’s rho, thuật toán này có thời gian tính sẽ là (), với p là ước số nguyên tố lớn nhất của n, do đó, phải chọn số n sao cho nó chia hết số nguyên tố p lớn nhất có đủ lớn để giải bài toán này là không khả thi. Trong phần dưới đây, một số phương pháp tấn công bài toán Logarithm rời rạc sẽ được đề cập đến, đa số các phương pháp này có thể áp dụng được cho một nhóm bất kỳ. Chi tiết có thể tham khảo trong [3, 6, 8]. Cho Glà nhóm các điểm trên đường cong , , ∈ là các điểm trên đường cong E, chúng ta cần giải bài toán kP = Q, N là bậc của G. 2.1. Phương pháp bước nhỏ, bước lớn Phương pháp này do Shanks đề xuất và được H. Cohen mô tả trong [9]. Thuật toán 2.1. Phương pháp bước nhỏ, bước lớn 1. Chọn ≥ √và tính mP. 2. Tính và lưu trữ danh sách iP với 0 ≤ i < m 3. Tính Q - jmP với j = 0,1,..., m - 1 4. ifiP = Q - jmPthen 5. k = i + jm( mod N) 6. end if 7. Quay về bước 3 Dễ dàng nhận thấy Q = iP + jmPhay Q = (i + jm)P từ đó k = i + jm. Điểm iP được tính bằng cách cộng thêm P vào (i - 1)P đây được gọi là bước nhỏ. Q - jmP được tính bằng cách cộng thêm mP vào Q - (j - 1)mP và đây được gọi là bước lớn. 2.2. Phương pháp Pollard’s và λ Công nghệ thông tin N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” 226 Phương pháp này do Pollard đề xuất trong [10]. Định nghĩa hàm f : G → G một cách ngẫu nhiên Pi+i = f (Pi) với P0 cũng được chọn một cách ngẫu nhiên. Bởi vì G là tập hữu hạn do đó sẽ có các chỉ số i0< j0 mà Pi0 = Pj0, từ đó ta có: Pi0 + 1 = f (Pi0 ) = f (Pj0 ) = Pj0 + 1 Tương tự sẽ có Pi0+1 = Pj0+1 với l ≥ 0, từ đó, chuỗi Pi là chuỗi tuần hoàn với chu kỳ là j0- i0. Hàm biểu diễn chuỗi Pi thường giống chữ cái Hi Lạp và đó là lý do tại sao phương pháp này có tên là phương pháp . Hàm f được chọn như sau: Chia tập G thành s tập con không trùng nhau Si, S2,..., Ss có kích thước tương đương nhau, s thường được chọn là 20, chọn 2s số ngẫu nhiên ai,bi mod N. Đặt: Mi = aiP + biQ Và định nghĩa: f(g) = g + Mi, ∈ Biểu diễn Pj dưới dạng Pj = ujP + vjQ, khi Pi0= Pj0 ta có: uj0 P+ vj0 Q = ui0 P + vi0 Q (ui0- uj0)P = (vj0- vx’j0)Q k = (vj0 – vx’j0 )1(ui0 - uj0) mod N Phương pháp này cũng tương tự như phương pháp trên cần√ bước, tuy nhiên, không gian lưu trữ sẽ nhỏ hơn. 2.3. Phương pháp Pohlig-Hellman Pohlig và Hellman đề xuất phương pháp này trong [11]. Nếu có thể phân tích bậc N của G thành các thừa số nguyên tố thì có thể viết: = Ý tưởng của phương pháp này là tìm ( với mỗi i, sau đó áp dụng định lý Đồng dư Trung Hoa để tính k (mod N). Coi q là số nguyên tố và qe là lũy thừa e của q được chia hết bởi N, viết k dưới dạng sau: k = k0 + k1q + k2q 2 + , 0 ≤ ki< q Lý giải thuật toán 2.3 như sau: = + + ⋯ = + + + ⋯ = Bởi vì NP = ∞ và từ đây có thể tìm được k0. Tiếp theo: Qi = Q - k0P = (kiq + k2q 2 + ...) P = + + ⋯ = + + + ⋯ = Thông tin khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 227 Từ đó tìm được k1, tương tự như vậy chúng ta sẽ tìm được k2, k3 ... Thuật toán sẽ dừng khi e = r + 1, khi đó N/qe+i không còn là số nguyên nữa và chúng ta không thể nhân Qe với một số hữu tỷ. Thuật toán 2.3. Phương pháp Pohlig-Hellman 1. Tính = | 0 ≤ ≤ − 1, 2. Tính , Đó là phần tử của T. 3. if e = 1 then 4. Nhảy đến bước 15. 5. end if 6. Q1 ← Q ← k0P 7. Tính . Đó là phần tử của T. 8. if e = 2 then 9. Nhảy đến bước 15. 10. end if 11. Lần lượt tính được các giá trị k0, k1, , kr-1 và Q0, Q1, , Qr-1 12. Qr ← Qr-1 – kr-1 q r-1 P 13. Xác định kr sao cho = 14. if e = r + 1 then 15. k = k0 + k1q 2 + k2q 2 + + ke-1q e-1 ( mod qe ) 16. Stop 17. end if 18. Quay về bước 11. 2.4. Phương pháp tấn công MOV Tấn công MOV là tên viết tắt của các tác giả Menezes, Okamoto, và Vanstone [12], sử dụng cặp Weil để chuyển đổi bài toán Logarithm rời rạc trong () thành bài toán Logarithm rời rạc trong . Bởi vì giải bài toán Logarithm rời rạc trong trường hữu hạn sẽ dễ dàng và nhanh hơn giải Logarithm rời rạc trong nhóm các điểm trên đường cong Elliptic. Chọn m sao cho: [] ⊆ Bởi vì tất cả các điểm trong E[N] đều có tọa độ trong =∪ , nên m tồn tại. Theo định nghĩa về cặp Weil và các thuộc tính của cặp song tuyến tính: = (, ) = (, ) = (, ) = Thuật toán 2.4. Tấn công MOV 1. Chọn điểm ngẫu nhiên ∈ . 2. Tính bậc M của T. 3. Cho d = gcd(M, N) và cho T1 = (M|d)T có nghĩa là T1 có bậc là d, chia hết bởi N, do đó ∈ []. 4. Tính các cặp Weil = (, ) và = (, ). Cả hai , ∈ ⊆ × . 228 như MOV, trong quá tr đư Định nghĩa 3. 1. 2. 3. 4. 5. 6. và ký s vi ph ph 4.1 [15] X9.63 và IEEE P1363. khai, hai bên cùng th gửi giá trị gửi lại cho A. Khi đó KB tính đư Đánh giá b đư truy 5. 6. Các tham s ợc mô tả trong chuẩn [13]. B Phương S là m Hai h P là m Đ Bài báo s ệc triển khai ứng dụng ECC. D. Hankerson ần mềm. L. Cao ần cứng. . Trao đ Năm 1998, Laurie và c . Sau đó giao th Hai bên = d ợc cả 2 khóa bí mật ền l ậc c các ph cách ng = x ồ B ợc. Xem s Giải b Lặp lại với điểm ngẫu nhi số 3 + ax + ng h ố c dAP à d d là ủa trư pháp bi ần t ầm đ ẫu nhi ệ số ột đi ệ ẽ đề cập đến một số thuật toán ứng dụng trong trao đổi khóa, m ơ b ổi khóa Diffie A dA . D ảo m AP ài toán Logarithm r N ố của hệ mật ECC cần đ Tham s ử ư a,b ể số ản. Chuẩn do công ty và B c P cho bên B, ngư ễ d và , từ đó xác định đ ờng củ ợc sử dụng trong tr ∈ b). m có b h = #E( àng nh ơ đ ật d ể a ên. [14] ức n ần tạo khóa phi ồ d : Đ BP, khi bi 3. THAM S ố h q là q. u di q. q đư ậ ỏa thuận điểm c , khóa phiên c ư ể t N. A. Vi ình l ệ m ễn trư ợc dùng đ c nguyên t q)/n. phân tích th — ày đ ận thấy ới đây: ìm dA,d ựa chọn hệ ECC cần phải đạt đ ật Hellman ECDH ộng sự đề xuất giao thức trao đổi khóa dựa tr đư B, trong khi ch ết D = (q, FR, S, a, b, P, n, h) ờ 4. TRAO Đ ã đư ợc lại b K ợc khóa chia sẻ K P, hacker bu ệt, N. K. Tuấn, “Hệ mật m ời rạc ên ược ng FR (field representation) đư ể ố ợc đ A T k (mod N) Ố CỦA HỆ MẬT ECC ường đ đ n và g Certicom ực hiện ên bí m ơ s ủa b = K cho đ ược ịnh ngh ưa vào ên B t ên B, khóa này ch = ến khi bội số chung nhỏ nhất của các l ư ọ ỔI KHÓA ở P A ỉ có thể bắt đ ựa chọn kỹ c ờng cong Elliptic đ ĩa đ i là đi các giao th ật trao đổi trong một k trên ạo s ộc phải giải b trong . xây d [7] các tiêu chu khóa bí m ẽ l ườ ểm cơ s phân tích tri E. Bên à K A ho ng cong E trên ựng [12] mô t A = d ỉ ri ặc K ã d × àng đ ở ức c êng hai bên ư ài toán Logarithm r ựa tr , sẽ tính đ là m P ẩn ANSI X9.42, ANSI A ật Ad B, hacker bu ợc thông tin tr ên đư ể tránh các tấn công ư ộ = (x ơ b tạo khóa bí mật dB BP, và c Công ngh ợc một số ti t t ợc s ược tạo ra một P ển khai ECC bằng ản của ECC bằng nhân v ờng cong Elliptic. ư ập h ử ,yP ả chi tiết trong ênh truy ủa b ợc ợp g dụ q (ngh ) ∈ ới A ộc phải t ệ thông tin k (mod N) ng cho E( P ên B s và B có th ên đư êu chí ồm: ĩa l q). ên ECC ền công sau đó à ã hóa dA ẽ l ờng ời rạc ” . y2 và à ể ìm Thông tin khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 229 dA = logP (dAP) và dB = logP (dBP) và đây là bài toán khó không giải được trong thời gian đa thức. 4.2. Tạo khóa bí mật chia sẻ ECMQV Tên đầy đủ của giao thức là Elliptic Curve Menezes-Qu-Vanstone. Thuật toán đã được đưa vào trong các chuẩn ANSI X9.63, IEEE 1363-2000, và ISO/IEC 15946-3. Theo các tiêu chuẩn này điểm cơ sở được ký hiệu là G thay vì là P như thường gặp. Lược đồ này thường được sử dụng khi bân Avà B có cặp khóa công khai và bí mật cố định, tương ứng là (a, aG) và (c, cG). Bên A sinh cặp số ngẫu nhiên (b,bG) và bên B tương ứng sinh cặp số ngẫu (d, dG), và trao đổi 2 cặp nay cho nhau giá trị bG và dG. Kí hiệu hàm x :E → ℕ, lấy giá trị x của điểm trên đường cong E. Thuật toán 4.2: Tạo khóa bí mật chia sẻ ECMQV INPUT: Các tham số của hệ mật (K, E, q, h, G), các số a, b, aG, bG, cG và dG. OUTPUT: Khóa bí mật chia sẻ Q (chia sẻ với với đối tượng có khóa công khai cG) 1. n ← [log2 (≠k)]/2. 2. u ← (x(bG)(mod 2n) + 2n. 3. s ← b + ua((mod q). 4. v ← (x(dG)(mod 2n) + 2n. 5. Q ← s(dG + v(cG)). 6. if Q = ∞ then 7. Quay lại bước 1. 8. end if 9. Trả về khóa Q. Bên B có thể tính ra cùng số Q bằng cách thay (a, b, c, d) trong thuật toán trên bằng (c, d, a, b). Bên A sẽ có các giá trị uA, vA, sA và bên B sẽ có uB, vB, sB. Dễ dàng nhận thấy: uA = vB uB = vA QA= sA(dG + vA(cG)) = sA(d + vAc)G = sA(d + uBc)G = sAsBG QB= sB(bG + vB(aG)) = sB(b + vBa)G = sB(b + uAa)G = sBsAG QA= QB = Q Đánh giá bảo mật: Để hack được khóa chia sẻ, Hacker cần phải tính được các giá trị a, b, c, d muốn vậy Hacker phải giải các bài toán Logarithm rời rạc a = logG(aG), b = logG(bG), c = logG(cG), d = logG(dG). Đây là các bài toán khó không thể giải được trong thời gian đa thức tại thời điểm viết bài báo này. 5. XÁC THỰC – CHỮ KÝ SỐ 5.1. ECDSA(The Elliptic Curve Digital Signature Algorithm) Năm 1999, ECDSA(The Elliptic Curve Digital Signature Algorithm) đã được phê duyệt thành tiêu chuẩn của ANSI (ANSI X9.62-1998 ECDSA, phiên bản mới nhất là X9.62-2005), năm 2000 ECDSA cũng được IEEE và NIST phê duyệt thành tiêu chuẩn FIPS PUB 186-4 (Digital Signature Standard (DSS)), phiên bản mới Công nghệ thông tin N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” 230 nhất ban hành 7- ECDSA (The Elliptic Curve Digital Signature Algorithm) 2013. ISO năm 2002 cũng ban hành tiêu chuẩn ISO/IEC 159462:2002 trong đó có phần chuyên về ECDSA. Mô tả chi tiết về ECDSA có thể tìm thấy trong [16]. Người ký sẽ chọn số d làm khóa bí mật và tạo ra khóa công khai là Q = dP, sử dụng hàm băm H để tạo ra giá trị tóm lược văn bản e của văn bản m. Chữ ký số sẽ là cặp (r, s) được tính theo thuật toán 5.1. Thuật toán 5.1a: Sinh chữ ký số ECDSA INPUT: Tham số D = (q, FR. S, a,b,P,n,h), khóa bí mật d, thông điệp m. OUTPUT: Chữ ký số (r,s). 1. Chọn ngẫu nhiên k ∈ [l,n- 1], 2. R ← kP = (x1,y1) và chuyển đổi x1 ← 3. r←(mod n). 4. if r = 0 then Nhảy đến bước 1: 5. end if 6. e ← H(m). 7. s ← k-1(e + dr) (mod n). 8. if s = 0 then Nhảy đến bước 1: 9. end if 10. Trả về (r,s) Người nhận nhận được văn bản m' và chữ ký số (r, s) của người ký, sẽ tính giá trị tóm lược e' của văn bản nhận được là m' và áp dụng thuật toán 5.2 để xác định chữ ký số có phù hợp với văn bản nhận được hay không, từ đó, có thể khẳng định văn vản có do người ký ký thật hay không hoặc văn bản có bị sửa đổi hay bị lỗi do đường truyền hay không. Thuật toán 5.1b: Xác thực chữ ký số ECDSA INPUT: Tham số D = (q, FR, S, a,b, P, n, h), khóa công khai Q = dP, thông điệp nhận được m', chữ ký (r, s). OUTPUT: Chữ ký hợp lệ hoặc không hợp lệ. 1. Kiểm tra r và s có phải là những số nguyên nằm trong khoảng [1,n-1], Nếukhông trả về return(“Chữ ký không hợp lệ”). 2. e'←H (m’). 3. w← s-1(mod n). 4. u1← e’w(mod n) và u2← rw(mod n). 5. R'←u1P + u2Q. 6. ifR' = ∞then 7. return(“Chữ ký không hợp lệ”). 8. end if 9. Chuyển đổi x1 của R’→ số nguyên 10. r’← (mod n). 11. if r’ = rthen 12. return (“Chữ ký hợp lệ”). 13. else Thông tin khoa h Tạp chí Nghi m ch và khóa bí m Logarithm r đư 5.2 đã FIPS và công khai c nguyên t Thu INPUT: Khóa bí m OUTPUT: Ch Thu 14. 15. Ch hay N ứng minh. Đánh giá ợc trong thời gian đa thức. . Ch D đư Đ Có th ật toán 5.2a: Sinh chữ ký số Elgamal ật toán 5.2b: Xác thực chữ ký số Elgamal INPUT: Khóa công khai OUTPUT: Ch Ch return(“Ch end if ứ e = e' ếu ựa tr ợc đ 186 ịnh nghĩa h 1. 2. 3. 4. 1. 2. 3. 4. 5. 6. 7. ứng minh tính đúng đắn của thuật toán ng minh tính đúng đ e = e' ữ ký số ElGamal ên lư ưa vào thành chu [18] ể chọn h ố lớn.. Ch R s = k Tr Vi = ên c ời rạc ọn ng ← Kp. ả về ( Tính Tính ifV return (“Ch else return (“Ch end if ọc công nghệ ứu KH&CN thì ta s bả ật ợc đồ ký số do ElGamal đề xuất năm 1984 . ủa ng ữ ký số ( -1(m 1 = V f (R)Y + sR = f (R)xP + k ữ r' = r o m d, đ k = log àm àm ẫu nhiên – R,s ữ ký hợp lệ hoặc không hợp lệ. V1 V2 ký ẽ có ật f như sau: f (x,y) = x ư ật xf ) = f(R)Y + Sr = m’V 2then không h . Th : Đ ể t ời ký l x, thông đi R,s (R ữ ký hợp lệ”). ữ ký không hợp lệ”) quân s ực vậy: R' = k(e + rd)(e + rd) ể giả mạo đ ìm P )). ắn c đư R ẩn về chữ ký số DSS (Digital à ). ∈ Y = xP ự, ợp lệ”). ủ ợc 2 giá trị n và , trong đó x là s (x, Y) | Y = xP. N [1 Số Đặc san a thu d = log ệp , . Thông đi ược chữ ký, ∶ m. − ật toán P 1] -1(m Q || , CNTT : c ày và đây đ → ố nguy ệp nhận đ : khi — ần phải chứng minh rằng nếu Hacker Hacker ℤ xf (R))R = mP = m'P = V , 12 -1P = kP = R là b m' - 20 ều l ên ậc của điểm P th = m: 17 c bu à 2 bài toán khó, chưa gi Signature 0 < x < q. ược ần phải t ộc phải giải 2 b [17] m’ , ch là đi , phiên b ữ ký ( ìm Standard) trong Cặp khóa bí mật ều cần phải được giá trị ản sửa đổi ường l R.s 2 ài toán ) 231 m' = à s k ải ố 232 tính đư Hacker bu toán không gi 6.1 [32] ý ngh Đánh giá mA rời rạc th 6.2 Ch Đánh giá do đó và đây là 6.3 m ISO/IEC 15946 Đánh giá b . Mã hóa Massey Massey ,m ời gian đa thức. . Mã hóa ElGamal Trên cơ s ứng minh tính đúng đắn của l . Mã hóa ECIES (The Elliptic Curve Integrated En ECIES do Bellare và Rogaway đ ật ElGamal, sau đó vào năm 1986. Lư ĩa về mặt lịch sử. B đ m , Hacker c ợc ể t A b 2 s bu ộc phải giải b -Omura là hai tác gi bảo m ìm = log ở hệ mật ElGamal M = M ảo m bài toán khó. ả ộc phải tính đ ải đ đư - o m ư ật ợc các giá trị n M M 2 ật: Đ ần phải giải 2 b 3, IEEE P1363a và ật ợc trong thời gian đa thức. - : Đ 1 — : Đ Omura ợc đồ m ể phá khóa trong l và XB ể giải m , thu N. A. Vi ể giả mạo chữ ký số, Hacker buộc phải tính đ ài toán Logarithm r m M ật toán n 6. MÃ HÓA B = log 1 = M + kY ược ả để xuất l ã hóa này ít ày Hacker ph [17] ư ã đư ài toán Logarithm r ệt, N. K. Tuấn, “Hệ mật m k Ml , lư ợc đồ m ợc văn bản M, Hacker buộc phải t ày đ và khóa bí m M ề xuất v [13] ư 2, và đây là 2 bài toán chưa gi ợc đồ m B — ã . – ược đồ m đư ợc đồ n ã hóa X đư ời rạc GI ợc sử dụng trong thực tế nh ải lần l B M à là m ợc đ ẢI M ã hóa : 1 ưa vào các chu ật k = log ã hóa ày, Hacker ph = M + k(x ời rạc ột biến thể của m x, đ Ã ượt giải 2 b đư ã d ể tính đ ợc phát biểu nh k = log cryption System) ựa tr PR đư B ên đư và ợc P) Công ngh ư x mô t ải t ài toán Logarithm — P ẩn ANSI X9.63 v ờng cong Elliptic. ợc 2 giá trị n = log ìm x M1 ư ả trong Patent đư ải đ ư sau: B (kP) = M ìm và = ã hóa dùng h ệ thông tin ợc s m P ưng nó có ợc giá t ư đư Y, là bài ợc trong ợc log à đ k P Y ” ể ày rị và B, ệ à Thông tin khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 233 Tham số D = (q, FR, S, a, b, P, n, h) được chọn tương tự như với ECDSA. ở đây cần lựa chọn thêm các hàm mã hóa/giải mã đối xứng ký hiệu là Ek (m) và Dk (c). Trong đó, m là bản rõ cần mã hóa, c là bản đã được mã. Thuật toán mã hóa đối xứng được chọn ở đây để phục vụ quá trình mã hóa/giải mã được dễ dàng hơn và nhanh hơn so với các thuật toán bất đối xứng. Ngoài ra, thay vì sử dụng hàm băm đơn giản, ECIES sẽ sử dụng hai hàm băm sau: • Message authentication code MACk (c): MAC : {0,1}n × {0,1}* → {0,1}n • Key derivation function KD(T,l): KD : E × ℕ → {0,1}* l là độ dài khóa (k1||k2). {0,1} là chuỗi bit có giá trị 0,1 có độ dài n hoặc không xác định. Người nhận có cặp khóa công khai/bí mật là (Y, x) trong đó Y = xP. Thuật toán 6.3a: Mã hóa ECIES INPUT: Văn bản cần mã hóa m, khóa công khai Y. OUTPUT: Văn bản đã được mã hóa (U, c, r). 1. Chọn k ∈[1, q — 1]. 2. U ← kP. 3. T ← kY. 4. (ki||k2) ← KD(T,l). 5. Mã hóa văn bản, c ← Ekl (m). 6. Tính giá trị MAC cho văn bản mã hóa r = MACk2 (C) Trả về return (U, c, r). Mỗi thành phần trong (U, c, r) đều có ý nghĩa quan trọng: • U cần thiết để tính khóa phiên Diffie-Hellman T. • c là bản đã được mã hóa. • r được dùng để xác thực mã văn bản. Thuật toán 6.3b: Giải mã ECIES INPUT: Văn bản mã hóa U.c.r. khóa bí mật x. OUTPUT: Văn bản đã giải mã m hoặc thông báo “văn bản mã không hợp lệ”. 1. T ← xU. 2. (k1||k2) ← KD (T,l). 3. Giãi mã văn bản, m ← Dk1(c). 4. ifr ≠ MACk2(C) then 5. xuất thông báo “văn bản mã không hợp lệ” 6. end if 7. Trả về văn bản đã được giải mã m. Khóa phiên T sau khi được tính trong phần giải mã sẽ có giá trị giống như trong phần mã hóa. Thực vậy: TDecryption = xU = x(kP ) = k(xP) = kY = TEncryption Công nghệ thông tin N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” 234 Đánh giá bảo mật: Để phá khóa được lược đồ này Hacker cần phải tìm được khóa bí mật x hoặc giá trị k bằng cách giải bài toán x = logP Y hoặc k = logP U, và đây là 2 bài toán khó chưa giải được trong thời gian đa thức. 7. KẾT LUẬN Đường cong Elliptic là một trường hợp đặc biệt của phương trình Diophant. Lý thuyết về đường cong Elliptic (EC) rất phong phú và đồ sộ. Trong [5] tác giả Serge Lang đã phát biểu về phương diện học thuật: “Có thể viết vô tận về đường cong Elliptic”. Phạm vi của bài báo cũng được giới hạn với những khái niệm và lý thuyết đủ cho các ứng dụng cơ bản của EC, các phát triển của EC thành hệ mật ID-Based, hoặc các ứng dụng về chữ ký số tập thể, chữ ký số nhóm, chữ ký ngưỡng, chứ ký ủy nhiệm, chứ ký số mù sẽ không được đề cập đến trong khuôn khổ của bài báo này. Bài báo này có thể được sử dụng làm tài liệu tham khảo cho những người nghiên cứu về đường cong Elliptic trong lĩnh vực toán học cũng như Công nghệ thông tin. 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]. J. H. Silverman and J. T. Tate, “Rational Points on Elliptic Curves - Second Edition”. Springer, 2015. [3]. L. C. Washington, “Elliptic Curves Number Theory and Cryptography, Second Edition”. CRC Press, 2008. [4]. J. W. S. Cassels, “Lectures on Elliptic Curves”. University of Cambridge, 1991. [5]. S. Lang, “Elliptic Curves Diophantine Analysis”. Springer, 1978. [6]. J. H. Silverman, “The Arithmetic of Elliptic Curves”. Springer, 2009. [7]. D. Hankerson, J. L. Hernandez, and A. Menezes, “Software Implementation of Elliptic Curve Cryptography over Binary Fields,” CHES2000, vol. 1965, pp. 243-267, 2000. [8]. I. Blake, G. Seroussi, and N. Smart, “Elliptic Curves in Cryptography”. Cambridge University Press, 1999. [9]. H. Cohen, “A Course in Computational Algebraic Number Theory”. Springer Verlag, 1993. [10]. J. M. Pollard, “Monte Carlo Methods for Index Computations (mod p),” Mathematics of Computation, vol. 32, no. 143, pp. 918-924, 1978. [11]. S. C. Pohlig and M. E. Hellman, “An Improved Algorithm for Computing Log¬arithms over GF(p) and its Cryptographic Significance,” IEEE Transactions on Information Theory, vol. 24, pp. 106-110, 1978. [12]. A. J. Menezes, T. Okamoto, and S. A. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field,” IEEE Trans. Inform. Theory, vol. 39, no. 5, pp. 1639-1646, 1993. [13]. C. Research, Standards For Efficient Cryptography, SEC 1: “Elliptic Curve Cryptography”. Certicom Corp, 2000. Thông tin khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 235 [14]. L. Gao, S. Shrivastava, and G. E. Sobelman, “Elliptic Curve Scalar Multiplier Design Using FPGAs,” CHES’99, vol. 1717, pp. 257-268, 1999. [15]. L. Laurie, M. Alfred, Q. Minghua, S. Jerry, and V. Scott, “An Efficient Protocol for Authenticated Key Agreement,” Designs Codes and Cryptography, vol. 28, no. 2, 1998. [16]. D. Johnson, A. Menezes, and S. Vanstone, “The Elliptic Curve Digital Signature Algorithm (ECDSA),” 2001. [17]. T. E. Gamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” CRYPTO ’84, vol. 196, pp. 10-18, 1985. ABSTRACT ELLIPTIC CURVE CRYPTOGRAPHY The idea of information security lead to the evolution of Cryptography. In other words, Cryptography is the science of keeping information secure. It involves encryption and decryption of messages. Encryption is the process of converting a plain text into cipher text and decryption is the process of getting back the original message from the encrypted text. Cryptography, in addition to providing confidentiality, also provides Authentication, Integrity and Non-repudiation. The crux of cryptography lies in the key involved and the secrecy of the keys used to encrypt or decrypt. Another important factor is the key strength, i.e. the size of the key so that it is difficult to perform a brute force on the plain and cipher text and retrieve the key. There have been various cryptographic algorithms suggested. In this project we study and analyze the Elliptic Curve cryptosystems. This system has been proven to be stronger than known algorithms like RSA/DSA. Keywords: Cryptography, Public Key Systems, Elliptic Curve. Nhận bài ngày 16 tháng 8 năm 2017 Hoàn thiện ngày 26 tháng 11 năm 2017 Chấp nhận đăng ngày 28 tháng 11 năm 2017 Địa chỉ: 1Viện CNTT – Viện KH&CN quân sự; 2Trường Đại học Lạc Hồng. * Email: nguyenanhviet@hcmpreu.edu.vn.