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

Bài viết 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.
Nội dung trích xuất từ tài liệu:
Hệ mật mã dựa trên đường cong Elliptic Công nghệ thông tin 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ố 224 N. A. Việt, N. K. Tuấn, “Hệ mật mã dựa trên đường cong Elliptic.” Thông tin khoa học công nghệ 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 ...