Hệ mật mã dựa trên đường cong Elliptic

Công nghệ thông tin<br /> <br /> HỆ MẬT MÃ DỰA TRÊN ĐƯỜNG CONG ELLIPTIC<br /> Nguyễn Ánh Việt1*, Nguyễn Kim Tuấn2<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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ã.<br /> 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<br /> giải mã theo cách thuần túy.<br /> Đã 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.<br /> 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<br /> đường cong Elliptic (ECC) và đơn giản hóa thành những thuật toán gần với các<br /> ngôn ngữ đặc tả của chuyên ngành CNTT. Thuật toán mã hóa đường cong Elliptic<br /> đã được chứng minh là mạnh hơn các thuật toán đã biết như RSA / DSA.<br /> Từ khóa: Đường cong Elliptic; Hệ mật mã công khai; Elliptic Curve.<br /> <br /> 1. MỞ ĐẦU<br /> Tháng 3 năm 2016, Bộ Ngoại Giao Hoa Kỳ, đứng đầu là bộ trưởng John Kerry,<br /> đã 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<br /> về phát triển Fintech và đặc biệt là về công nghệ Blockchain. Tháng 9 năm 2015,<br /> ủy ban giao dịch hàng hoá tương lai Mỹ công bố, Bitcoin đã chính thức được đưa<br /> vào danh sách hàng hóa được phép giao dịch tại Mỹ. Công nghệ Blockchain và<br /> 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à<br /> 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<br /> trong không gian mạng Internet toàn cầu. Tháng 4-2016, giá trị thương mại của<br /> Bitcoin đã lên đến 6.5 tỷ USD. Nền tảng cơ sở của Bitcoin chính là lý thuyết về<br /> 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<br /> đường cong Elliptic (ECC).<br /> 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<br /> trong thực tiễn ngành Công nghệ thông tin [1]. Các trang Web bảo mât https (http-<br /> secure) thường được dùng trong thanh toán điện tử hay ứng dụng riêng tư như<br /> gmail đều sử dụng các giao thức TLS (Transport Layer Security) mà trước đó là<br /> SSL (Secure Socket Layer). Trong các giao thức này ECC được sử dụng để trao<br /> đổi khóa phiên. Các giao dịch remote access được sử dụng rất nhiều trong thế<br /> giới Unix, Linux là SSH (Secure SHell) cũng sử dụng ECC để trao đổi khóa. Ưu<br /> điểm của hệ mật sử dụng đường cong Elliptic (ECC) là có độ dài khóa nhỏ (160<br /> bit tương đương với khóa độ dài 1024 Bit trong hệ mật RSA), do sử dụng độ dài<br /> 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<br /> đó 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ế<br /> để thay thế RSA.<br /> 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<br /> đường cong Elliptic. Ngoài việc đường cong Elliptic là cơ sở cho hệ mật ECC, hệ<br /> mật ID-Based, đường cong Elliptic (EC) còn là công cụ hữu hiệu để phân tích số<br /> <br /> <br /> 224 N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.”<br /> Thông tin khoa học công nghệ<br /> <br /> 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ố<br /> nguyên [3].<br /> 2. BÀI TOÁN LOGARITHM RỜI RẠC<br /> Định nghĩa 2. Bài toán Logarithm rời rạc trên đường cong Elliptic (ECDLP):<br /> Cho đường cong E trên trường hữu hạn Fq, điểm ∈ ( ) với bậc ( = =<br /> ∞) và điểm ∈ ( ), tìm số nguyên ∈ [0, − 1]sao cho Q = kP. Số nguyên k<br /> được gọi là Logarithm rời rạc của Q với cơ sở P, được viết là k = logP Q.<br /> 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ó để<br /> 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ễ<br /> (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<br /> 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ố<br /> 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<br /> để 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<br /> 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<br /> đượ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ử,<br /> 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<br /> toán vét cạn là không khả thi (n ≥ 2160).<br /> 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<br /> thuật toán Pohlih-Hellman và Pollard’s rho, thuật toán này có thời gian tính sẽ là<br /> ( ), 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<br /> 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<br /> khả thi.<br /> 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<br /> sẽ được đề cập đến, đa số các phương pháp này có thể áp dụng được cho một<br /> nhóm bất kỳ. Chi tiết có thể tham khảo trong [3, 6, 8].<br /> Cho Glà nhóm các điểm trên đường cong , , ∈ là các điểm trên đường<br /> cong E, chúng ta cần giải bài toán kP = Q, N là bậc của G.<br /> 2.1. Phương pháp bước nhỏ, bước lớn<br /> Phương pháp này do Shanks đề xuất và được H. Cohen mô tả trong [9].<br /> Thuật toán 2.1. Phương pháp bước nhỏ, bước lớn<br /> 1. Chọn ≥ √ và tính mP.<br /> 2. Tính và lưu trữ danh sách iP với 0 ≤<br /> i