Tiêu chuẩn Elliptic Curve Cryptography (ECC). 

Mật mã đường cong Elliptic (ECC) là một trong những loại mật mã mạnh nhất hiện nay. Tại nhiều công ty tại Mỹ, như CloudFlare, đã sử dụng rộng rãi ECC để bảo mật mọi thứ từ các kết nối HTTPS của khách hàng đến cách thức chuyển dữ liệu giữa các trung tâm dữ liệu của họ...

I. Giới thiệu

Mật mã đường cong Elliptic (ECC) là một trong những loại mật mã mạnh nhất hiện nay. Tại nhiều công ty tại Mỹ, như CloudFlare, đã sử dụng rộng rãi ECC để bảo mật mọi thứ từ các kết nối HTTPS của khách hàng đến cách thức chuyển dữ liệu giữa các trung tâm dữ liệu của họ. ECC là thế hệ mật mã khóa công khai và dựa trên toán học, cung cấp một nền tảng an toàn hơn so với các hệ thống mã hóa khóa công khai thế hệ đầu tiên như RSA.

Lịch sử của mật mã học có thể được chia thành hai thời đại: kỷ nguyên cổ điển và kỷ nguyên hiện đại. Bước ngoặt xảy ra vào năm 1977, khi cả thuật toán RSA và thuật toán trao đổi khóa Diffie-Hellman được giới thiệu. Các thuật toán mới này mang tính cách mạng bởi vì chúng đại diện cho các sơ đồ mã hóa khả thi đầu tiên trong đó bảo mật dựa trên lý thuyết về các con số; đó là lần đầu tiên cho phép liên lạc an toàn giữa hai bên mà không có bí mật chung.

Mật mã hiện đại được thành lập dựa trên ý tưởng rằng khóa mà bạn sử dụng để mã hóa dữ liệu của mình có thể được công khai trong khi khóa được sử dụng để giải mã dữ liệu của bạn có thể được giữ kín. Như vậy, các hệ thống này được gọi là hệ thống mật mã khóa công khai. Hệ thống đầu tiên, và vẫn được sử dụng rộng rãi nhất, được gọi là RSA - được đặt theo tên viết tắt của ba người đàn ông lần đầu tiên mô tả công khai thuật toán: Ron Rivest, Adi Shamir và Leonard Adeld. RSA đã trở thành hệ thống mật mã đầu tiên áp dụng cho chữ ký số và mã hóa dữ liệu, mặc dù ý tưởng này lần đầu tiên được đưa ra ánh sáng vào năm 1978 . Thuật toán RSA bao gồm ba bước chính: tạo cặp khóa, mã hóa và giải mã. Khóa công khai được truyền qua kênh mở, trong khi Khóa riêng vẫn giữ bí mật. Dữ liệu, được mã hóa bằng Khóa riêng, chỉ có thể được giải mã bằng Khóa công khai, được liên kết về mặt toán học với Khóa riêng. RSA có thể được sử dụng để xác định nguồn gốc dữ liệu.

II. Một số đặc điểm chính của Mật Mã Đường Cong ELLIPTIC

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. Nhà toán học nổi tiếng J. Silverman cũng như nhiều nhà thám mã khác đã nghiên cứu các thuật toán tương tự, như thuật toán tính chỉ số để áp dụng cho ECDLP nhưng đều không thành công. Hiện nay, thuật toán tốt nhất để giải bài toán ECDLP là Pollard với độ phức tạp cỡ, trong đó G là nhóm điểm đường cong elliptic. Điều này đã tạo ra những ưu việt của hệ mật ECC so với các hệ mật khóa công khai khác.

Mật mã ECC cung cấp tính an toàn tương đương với các hệ mật khóa công khai truyền thống, trong khi độ dài khóa nhỏ hơn nhiều lần. Người ta đã ước lượng rằng cỡ khoá 3248 bit của hệ mật RSA cho cùng một độ an toàn như 256 bit của hệ mật ECC. Điều đó có nghĩa là việc cài đặt ECC sử dụng tài nguyên hệ thống ít hơn, năng lượng tiêu thụ nhỏ hơn.... Với ưu thế về độ dài khóa nhỏ, ECC đang được ứng dụng rộng rãi trong nhiều lĩnh vực.

Đường cong elip là tập hợp các điểm thỏa mãn một phương trình toán học cụ thể. Phương trình cho một đường cong elip:

y2 = x3 + ax + b

Đồ thị được biểu diễn như sau:

Hình 1: Đồ thị biểu diễn đường cong elliptic y2 = x3 + ax + b 

Có nhiều cách biểu diễn khác nhau của đường cong elliptic, nhưng về mặt kỹ thuật, một đường cong elliptic là các điểm đặt thỏa mãn một phương trình ở hai biến có độ hai ở một trong hai biến và độ ba ở biến khác. Một đường cong elipptic cần đảm bảo một số tính chất sau:

Đối xứng lạ

Nhìn kỹ hơn vào đường cong elip được vẽ ở trên. Nhận thấy, một trong số đó là đối xứng ngang. Bất kỳ điểm nào trên đường cong đều được phản ánh qua trục x và vẫn giữ nguyên đường cong. Một đặc tính thú vị hơn là bất kỳ đường không thẳng đứng nào cũng sẽ cắt đường cong ở nhiều nhất là ba điểm.
Chúng ta hãy tưởng tượng đường cong này là bối cảnh cho một trò chơi bi-a kỳ quái. Lấy hai điểm bất kỳ trên đường cong và vẽ một đường thẳng qua chúng, nó sẽ cắt đường cong tại đúng một điểm nữa. Trong trò chơi bi-a này, bạn lấy một quả bóng tại điểm A, bắn nó về phía điểm B. Khi nó chạm đường cong, quả bóng nảy thẳng lên (nếu nó nằm dưới trục x) hoặc thẳng xuống (nếu nó ở trên trục x) sang phía bên kia của đường cong.

Hình 2: Đồ thị biểu diễn đường cong elliptic

Ký hiệu việc di chuyển của viên bi qua hai điểm là "(+)", hay còn gọi là phép cộng trên đường cong Elliptic. Từ bất kỳ hai điểm nào trên đường cong cũng có thể dùng để tìm ra một điểm mới khi tuân theo phép cộng này.

A (+) B = C

Từ đó cũng có thể tạo một chuỗi chuyển động từ một điểm duy nhất:

A (+) A = B

A (+) B = C

A (+) C = D...

Việc này chỉ ra rằng nếu có hai điểm, với điều kiện một điểm thực hiện “(+)” chính nó n lần ra điểm còn lại, thì việc tìm ra n khi mà chỉ biết điểm đầu và điểm cuối là rất khó khăn. Áp dụng cho chính ví dụ về trò billiard, nếu một người chơi trò chơi này một mình trong một căn phòng trong một khoảng thời gian ngẫu nhiên. Rất dễ dàng cho anh ta để đánh bi đi theo các quy tắc mô tả ở trên. Đến khi một người khác bước vào phòng sau đó và nhìn thấy vị trí viên bi, ngay cả khi họ biết tất cả các quy tắc của trò chơi và vị trí bắt đầu, họ không thể xác định số lần viên bi được đánh mà không chơi qua toàn bộ trò chơi một lần nữa. Dễ thực hiện, khó suy ngược, đây chính là tính chất của một phương pháp mã hóa tốt.

Một hệ thống ECC có thể được định nghĩa bằng cách chọn một số nguyên tố làm giới hạn, một phương trình đường cong và một điểm trên đường cong đó. Một khóa riêng là một số priv, và một khóa công khai là kết quả của việc cộng điểm ban đầu với chính nó priv lần. Tính toán các khóa riêng từ khóa công khai trong hệ thống mã hóa này được gọi là logarit rời rạc trên đường cong Elliptic – Elliptic Curve Discrete Logarithm Problem (ECDLP). Đây chính là phương pháp mã hóa đang tìm kiếm.

Đường cong đơn giản hóa ở trên rất hiệu quả trong việc xem xét và giải thích khái niệm chung về các đường cong elip, nhưng nó không đại diện cho các đường cong được sử dụng cho mật mã trông như thế nào.

Khi tính toán công thức cho đường cong elliptic (y2 = x3 + ax + b), chúng ta chọn tất cả là số nguyên tố, đường cong elip được gọi là đường cong chính và có các đặc tính mật mã tuyệt vời.

Dưới đây là ví dụ về đường cong (y2 = x3 - x + 1) được vẽ cho tất cả các số:

Hình 3: Đồ thị biểu diễn đường cong elliptic (y2 = x3 - x + 1)

Đây là hiển thị của cùng một đường cong với toàn bộ số điểm là số nguyên tố được biểu thị với tối đa 97 chấm.

Hình 4: Đồ thị biểu diễn đường cong elliptic (y2 = x3 - x + 1)

với các giá trị là số nguyên tố

Đồ thị này hầu như không giống như một đường cong elipptic truyền thống, nó giống như đường cong ban đầu được quấn quanh các cạnh và chỉ các phần của đường cong đánh vào tọa độ số nguyên được tô màu.

Một hệ thống mật mã đường cong elip có thể được xác định bằng cách chọn một số nguyên tố là cực đại, phương trình đường cong và điểm công khai trên đường cong. Khóa riêng là số riêng và khóa công khai là điểm chung được chấm. Việc tính toán khóa riêng từ khóa chung trong loại hệ thống mật mã này được gọi là hàm logarit rời rạc đường cong elip. Điều này chính là Chức năng bẫy cửa mà chúng ta đang tìm kiếm.

Các hàm logarit rời rạc đường cong elip là vấn đề khó khăn trong việc củng cố mật mã đường cong elliptic. Mặc dù đã có gần ba thập kỷ nghiên cứu, các nhà toán học vẫn chưa tìm thấy một thuật toán để giải quyết vấn đề này nhằm cải thiện cách tiếp cận. Nói cách khác, dựa trên toán học hiện đang hiểu, dường như không có một lối tắt nào thu hẹp khoảng cách trong Hàm Bẫy dựa trên vấn đề này. Điều này có nghĩa là đối với các số có cùng kích thước, việc giải các logarit rời rạc đường cong elip khó khăn hơn. Vì vậy cho ta một hệ thống mật mã mạnh hơn, theo sau đó, hệ thống mật mã đường cong elip khó bị phá vỡ hơn RSA và Diffie-Hellman.

Để hình dung mức độ khó phá vỡ hơn bao nhiêu, Lenstra mới đây đã giới thiệu khái niệm "An ninh toàn cầu". Bạn có thể tính toán lượng năng lượng cần thiết để phá vỡ thuật toán mật mã và so sánh với lượng nước mà năng lượng có thể đun sôi. Theo biện pháp này, việc phá khóa RSA 228 bit đòi hỏi ít năng lượng hơn so với việc đun sôi một muỗng cà phê nước. Một cách tương đối, việc phá khóa đường cong elip 228 bit đòi hỏi đủ năng lượng để đun sôi tất cả nước trên trái đất. Đối với mức bảo mật này với RSA, bạn cần một khóa có 2.380 bit.

Với ECC, có thể sử dụng các khóa nhỏ hơn để có cùng mức bảo mật. Các khóa nhỏ rất quan trọng, đặc biệt là trong một thế giới nơi ngày càng có nhiều mật mã được thực hiện trên các thiết bị ít mạnh hơn như điện thoại di động. ECC cung cấp một sự đánh đổi tốt hơn: bảo mật cao với các phím ngắn, nhanh.

Từ những năm 2000, các nước Mỹ, Nga, Nhật Bản, Hàn Quốc và một số nước Châu Âu đã đầu tư nghiên cứu về hệ mật ECC và đưa vào các hệ thống tiêu chuẩn như ISO, ANSI, IEEE, SECG, FIPS. Một trong những quốc gia sử dụng mật mã elliptic nhiều nhất là Liên bang Nga. Năm 2001, Nga đã đưa ra chuẩn chữ ký số GOST R34-10-2001 sử dụng mật mã elliptic với độ dài khóa 256 bit. Phiên bản mới nhất của Nga về chữ ký số là GOST R34-10 năm 2012 với độ dài khóa cho hệ mật ECC là trong khoảng từ 256 bit đến 512 bit.

Có hai vấn đề trọng tâm cần nghiên cứu về mật mã elliptic là tiêu chuẩn an toàn tham số và các giao thức, thuật toán ECC an toàn.

 Về tiêu chuẩn an toàn cho tham số mật mã Elliptic, không phải cứ tuân thủ theo các tiêu chuẩn đã đưa ra là đảm bảo an toàn. Bằng chứng thứ nhất là năm 2006, Jung Hee Cheon đã đưa ra một tấn công hiệu quả hơn hẳn thuật toán Pollard sử dụng giả thuyết Diffie-Hellman mạnh. Tấn công này áp dụng đối với các lược đồ mật mã mà tạo ra một bộ tiên đoán có thể trả về lũy thừa khóa bí mật của nó với một đầu vào bất kỳ (ví dụ như lược đồ chữ ký số mù sử dụng trong an toàn giao dịch điện tử). Đến năm 2009, tấn công này mới được xem xét đưa vào chuẩn ISO và FIPS. Các chuẩn khác như ANSI hoặc SECG không được cập nhật về tấn công. Ngay cả trong chuẩn ISO và FIPS, các điều kiện đưa ra đối với tiêu chuẩn chống tấn công này cũng có những điểm khác nhau cơ bản. Năm 2012, sử dụng giả thuyết Diffi-Hellman, Masaya Yasuda và các cộng sự đã đưa ra một bằng chứng phá vỡ mật mã elliptic dựa trên cặp (pairing-based cryptography) với độ dài khóa là 160 bit (độ dài khóa 131 bit hiện vẫn chưa giải được theo các công bố công khai, 160 bit là độ an toàn mà hầu hết các chuẩn trên thế giới đưa ra).

Bằng chứng thứ hai thuyết phục hơn, liên quan đến các tham số đường cong elliptic cụ thể được khuyến nghị trong chuẩn của Mỹ. Năm 2013, tờ New York Times tiết lộ rằng bộ sinh số ngẫu nhiên tất định dựa trên đường cong elliptic (Dual_EC_DRBG, trong tiêu chuẩn quốc gia NIST SP800-90A), đã tồn tại một điểm yếu cố ý trong thuật toán, cũng như các đường cong elliptic được NIST đề nghị sử dụng. Các tài liệu rò rỉ từ Edward Snowden cho rằng NSA và RSA Security đã có một hợp đồng với kinh phí khá lớn để đưa thuật toán Dual_EC_DRBG vào sản phẩm B-SAFE của hãng. Tháng 9/2013, RSA Security đã phải công khai ban hành một khuyến nghị các khách hàng của mình không tiếp tục sử dụng bất kỳ sản phẩm nào của hãng dựa trên Dual_EC_DRBG (hãng RSA biện minh rằng mình đã bị lừa dối).

Các chuyên gia mật mã bày tỏ sự lo ngại về Dual_EC_DRBG, coi như là “một bẫy bí mật của NSA”, cũng như về sự an toàn của các đường cong elliptic do NIST đề nghị trong chuẩn FIPS 186-3.

Như vậy, vấn đề đặt ra là cần phải thường xuyên cập nhật thông tin, nghiên cứu phân tích và đánh giá về các tiêu chuẩn an toàn, các tấn công đối với hệ mật để có đủ cơ sở lý thuyết, cơ sở toán học vững chắc, đưa ra các tiêu chuẩn an toàn riêng cho tham số mật mã elliptic [ theo TS. Trần Văn Trường, TS. Nguyễn Quốc ToànViện KHCNMM, Ban Cơ yếu Chính phủ].

III. Ứng dụng

 ECC hiện đang được sử dụng trong một loạt các ứng dụng: chính phủ Mỹ sử dụng để bảo vệ thông tin liên lạc nội bộ, các dự án Tor sử dụng để giúp đảm bảo ẩn danh, đây cũng là cơ chế được sử dụng để chứng minh quyền sở hữu trong Bitcoins, cung cấp chữ ký số trong dịch vụ iMessage của Apple, để mã hóa thông tin DNS với DNSCurve, và là phương pháp tốt để xác thực cho các trình duyệt web an toàn qua SSL/TLS. Thế hệ đầu tiên của thuật toán mã hóa khóa công khai như RSA và Diffie-Hellman vẫn được duy trì trong hầu hết các lĩnh vực, nhưng ECC đang nhanh chóng trở thành giải pháp thay thế cho RSA.

Cụ thể hơn nếu truy cập vào phiên bản HTTPS của các trang web phổ biến, như Google.com, Amazon.com, Facebook.com… từ một trình duyệt như Chrome hoặc Firefox, trình duyệt sẽ sử dụng ECC – như là sử dụng ECDHE_ECDSA. ECDHE là viết tắt của Elliptic Curve Diffie Hellman Ephemeral và là một cơ chế trao đổi khóa dựa trên đường cong Elliptic. ECDSA là Elliptic Curve Digital Signature Algorithm là cơ chế tạo chữ ký số để xác thực kết nối với máy chủ.

Sự cải thiện hiệu suất của ECDSA hơn RSA là rất rõ ràng. Ngay cả với một phiên bản cũ của OpenSSL không có tối ưu cho ECC, tạo một chữ ký ECDSA với khóa 256-bit là nhanh hơn 20 lần so với một chữ ký RSA với khóa 2048-bit.

Trong kỷ nguyên công nghệ thông tin và truyền thông hiện nay, nhu cầu đảm bảo an toàn thông tin là không thể thiếu. Với việc khóa mã hóa có độ dài ngày tăng dần theo thời gian, ECC đang là ứng viên phù hợp để thay thế RSA trong việc tạo ra các khóa mã ngắn hơn mà vẫn đảm bảo an toàn, từ đó có thể triển khai trên nhiều nền tảng thiết bị từ các mạch điện tử đơn giản đến máy tính lớn, dễ dàng tạo ra hệ thống mạng đáng tin cậy phục vụ tốt hơn cho xã hội.

Trong Thông tư số 39/2017/TT-BTTTT ngày 15/12/2017 của Bộ trưởng Bộ Thông tin và Truyền thông Công bố Danh mục tiêu chuẩn kỹ thuật về ứng dụng công nghệ thông tin trong cơ quan nhà nước quy định Khuyến nghị áp dụng tiêu chuẩn ECC - Elliptic Curve Cryptography và được xếp vào nhóm Tiêu chuẩn về an toàn thông tin.

Tài liệu tham khảo

  1. https://medium.com/coinmonks/elliptic-curve-cryptography-6de8fc748b8b
  2. https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
  3. https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

 

Nguyễn Thị Thu Trang

3117 Go top

Sự kiện nổi bật

Ý kiến về Trang thông tin điện tử Cục Tin học hóa?
1. Đạt yêu cầu, 1180 phiếu (88 %)
2. Chưa đạt yêu cầu, 107 phiếu (8 %)
3. Cần thêm chủ đề, 57 phiếu (4 %)
Tổng số phiếu: 1344
THÔNG KÊ TRUY CẬP
  • Người trực tuyến Người trực tuyến
    • Khách Khách 143
    • Thành viên Thành viên 0
    • Tổng Tổng 143
    • Tổng lượt truy cập: Tổng lượt truy cập: 16553417