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

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.
Nội dung trích xuất từ tài liệu:
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ộtTÓ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 2008và đượ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ủaBitcoin 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ựatrên Hệ mật đường cong Elliptic (ECC - Elliptic Curve Cryptography). Bên cạnh việc sử dụngtrong 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ôngtin [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 đổikhó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 bittươ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àinguyê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ởiCerticom, 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ấtnhiề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 ECliê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 chovớ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. Tacó 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ủasố nguyên [2]. EC cũng là cơ sở để chứng minh định lý Fermat nổi tiếng đã tồn tạinhiề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ácgiá 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ộttrườ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ọilà 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 522Hình 2: Số giao điểm = 3Hì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ình3, đường co ...