CHƯƠNG 1: TỔNG QUAN VỀ TRAO ĐỔI KHOÁ TRÊN ĐƯỜNG CONG ELLIPTIC 1. Lý thuyết về đường cong Elliptic 1. Khái niệm đường cong Elliptic Phương trình đường cong Elliptic sử dụng trong mật mã thường dùng dạng weierstrass: 𝑦 2 = 𝑥 3 + 𝑎𝑥 + 𝑏(𝑚𝑜𝑑 𝑝) Với điều kiện: 4𝑎3 + 27𝑏2 (𝑚𝑜𝑑 𝑝) ≠ 0. Đường cong trên có thể được ký hiệu là 𝐸𝑝 (𝑎, 𝑏).
Phép toán trên đường cong Elliptic Giả sử 𝑃 = (𝑥1 , 𝑦1 ), 𝑄 = (𝑥2 , 𝑦2 ) là các điểm trong nhóm 𝐸𝑝 (𝑎, 𝑏), O là điểm vô cùng. Các quy tắc đối với phép cộng trên nhóm con E p ( a, b ) như sau: (1) 𝑃 + 𝑂 = 𝑂 + 𝑃 = 𝑃. Hệ mật trên đường cong Elliptic Năm 1993, Demytko đưa ra một thuật toán mới tương tự như RSA cho các đường cong Elliptic trên Z n , Menezes và Vanstone đã đưa ra phương pháp thực thi trên các thiết bị phần cứng để cải thiện các phép tính toán trên Elliptic trên một trường hữu 1 hạn. Những năm 1997, 1998 việc tìm ra các hệ mã trên đường cong Elliptic ngày càng thu hút nhiều sự chú ý và một số thuật toán đã được đưa thành chuẩn trong các RFC [1].
Sơ đồ hoạt động của hệ mật trên đường cong Elliptic được mô tả theo hình 1: Mã hóa Giải mã Đầu Đầu mối mối AA Kênh Kênh truyền truyền PR = Đầu Đầu mối mối B B R PM = M M R DA = a A tin tin DB = aB ( kG ) , ( PR + kPB ) ( PR + kPB ) − aB (kG) Lấy EB Nguồn Nguồn khóa khóa Tham Tham sốsố chung chung của của hệ hệ mật mật ECC: E p ( a, b ) , G E p ( a, b ) ECC: Khóa Khóa công công khai: khai: Công bố EA E A = PA EB = PB Công bố EB Hình 1. Sơ đồ hoạt động của hệ mật trên đường cong Elliptic Theo sơ đồ hoạt động của hệ mật trên đường cong Elliptic, đầu mối A cần truyền thông báo mật R cho đầu mối B qua kênh truyền tin, có sử dụng hệ mật trên đường cong Elliptic để bảo mật thông tin. Khi đó, hệ mật trên đường cong Elliptic được xây dựng như sau: Sinh tham số chung cho hệ mật: Khi sử dụng hệ mật Elliptic để bảo mật thông tin cho mạng liên lạc, các tham số sau cần phải được quy ước chung cho hệ mật: - Chọn một đường cong Elliptic 𝐸𝑝 (𝑎, 𝑏). Việc chọn một đường cong Elliptic sẽ ảnh hưởng đến tốc độ, tính hiệu quả, độ dài khóa và tính an toàn của hệ mật trên đường cong này.
- Chọn điểm sinh (điểm cơ sở) 𝐺 ∈ 𝐸𝑝 (𝑎, 𝑏). Để an toàn thì n phải là một số nguyên tố lớn. Các tham số của hệ mật: đường cong 𝐸𝑝 (𝑎, 𝑏) và điểm sinh 𝐺 ∈ 𝐸𝑝 (𝑎, 𝑏) được đưa ra công khai. Trong hệ mật này, mỗi bản rõ 𝑅 sẽ được biểu diễn lại thành một điểm 𝑃𝑅 trong tập hữu hạn các điểm của nhóm 𝐸𝑝 (𝑎, 𝑏) mà nhờ đó chúng ta có thể thực hiện được các tính toán trên 𝐸𝑝 (𝑎, 𝑏).
2 Lược đồ tạo khóa: Mỗi đầu mối liên lạc (mỗi người dùng) tạo một cặp khóa, bao gồm một khóa công khai và một khóa riêng bí mật tương ứng theo các bước sau: 1. Chọn một số nguyên ngẫu nhiên 𝑎, 2 ≤ 𝑎 ≤ 𝑛 − 2. Tính giá trị của điểm P như sau: 𝑃 = 𝑎𝐺. Đặt𝐾 = {(𝑎, 𝑃): 𝑃 = 𝑎𝐺}ta có khóa công khai là 𝐸𝐾 = 𝑃, khóa riêng bí mật là 𝐷𝐾 = 𝑎 Lược đồ mã hóa: A phải mã hóa bản rõ R để tạo bản mã M gửi cho B theo các bước sau: 1.
Nhận khóa công khai 𝐸𝐵 = 𝑃𝐵 của B. Biểu diễn bản rõ R thành một điểm PR trong tập hữu hạn các điểm của nhóm 𝐸𝑝 (𝑎, 𝑏). Chọn số nguyên ngẫu nhiên bí mật 𝑘, 2 ≤ 𝑘 ≤ 𝑝 − 2. Tính cặp điểm của bản mã PM bằng cách dùng khóa công khai PB của B: 𝑃𝑀 = [(𝑘𝐺), (𝑃𝑅 + 𝑘𝑃𝐵 )] (2) 5.
Gửi cặp điểm bản mã PM cho B. Lược đồ giải mã: Để khôi phục bản rõ R từ bản mã PM đã nhận. B phải dùng khóa riêng DB = aB và thực hiện phép tính sau: 1. Nhân điểm thứ nhất (kG ) với khóa riêng aB của B và lấy kết quả nhận được trừ đi điểm thứ hai trong cặp điểm của PM : (𝑃𝑅 + 𝑘𝑃𝐵 ) − 𝑎𝐵 (𝑘𝐺) = (𝑃𝑅 + 𝑘𝑎𝐵 𝐺) − 𝑎𝐵 (𝑘𝐺) = 𝑃𝑅 (3) Đây chính là điểm tương ứng với bản rõ R.
Chỉ có B mới có khóa riêng aB và mới có thể tách 𝑎𝐵 (𝑘𝐺) khỏi điểm thứ hai của 𝑃𝑀 để thu thông tin về bản rõ 𝑃𝑅. Ánh xạ điểm - điểm bản rõ PR trở lại thông báo gốc R. Bài toàn logarit rời rạc trên đường cong Elliptic (ECDLP) Định nghĩa: Cho 𝐸là một đường cong Elliptic và 𝐺 ∈ 𝐸 là một điểm có cấp 𝑛. 3 Cho điểm 𝑃 ∈ 𝐸, hãy tìm số nguyên dương 𝑥, 2 ≤ 𝑥 ≤ 𝑛 − 2 sao cho 𝑃 = 𝑥𝐺.
Hiện nay, chưa có thuật toán nào được xem là hiệu quả để giải bài toán này. Để giải bài toán logarit rời rạc trên đường cong Elliptic, cần phải kiểm tra tất cả các giá trị của 𝑥 ∈ [2, 𝑛 − 2]. Nếu điểm 𝐺 được chọn cẩn thận với 𝑛 rất lớn thì việc giải bài toán ECDLP xem như không khả thi. Việc giải bài toán ECDLP được đánh giá là khó hơn việc giải bài toán DLP trên trường hữu hạn.
Phép nhân với số nguyên và bài toán logarit rời rạc trên đường cong Elliptic. Giả sử 𝐺 là một điểm trên đường cong elliptic 𝐸 sinh ra nhóm cyclic < 𝐺 > Có lực lượng hữu hạn 𝑛 đối với phép cộng “+” của nhóm. Khi đó, mỗi điểm 𝑄 của < 𝐺 > có biểu diễn 𝑄 = 𝑘𝐺, 𝑘 ∈ 𝑍. Do đó, ta chỉ xét phép nhân: 𝑄 = 𝑘𝐺, 𝑘 ∈ 𝑍 +.
Ánh xạ nhân với một số nguyên có thể dễ dàng được tính nhờ sử dụng kỹ thuật nhân đôi và cộng. Giả sử 𝑘 là một số nguyên dương bất kỳ có biểu diễn nhị phân 𝑘 = 𝑘𝑛 2𝑛 + 𝑘𝑛−1 2𝑛−1 + ⋯ + 𝑘1 2 + 𝑘0, với 𝑘𝑛 = 1. Để xác định 𝑄 = 𝑘𝐺 ta có thể thiến hành như sau: -𝑄=𝑂 - Với 𝑖 = 𝑛 giảm đến 𝑖 = 0 (1) 𝑄 ≔ 𝑄 + 𝑄 (2) Nếu 𝑘𝑖 = 1 thì 𝑄 ≔ 𝑄 + 𝐺 Do vậy, một số 𝑘 chọn ngẫu nhiên ta có thể mong đợi việc tính 𝑘𝐺 sẽ dẫn đến (𝑛 + 1) phép nhân đôi điểm trên đường cong và cỡ (𝑛 + 1)/2 phép toán kiểu (𝑄𝑗 , 𝐺) → 𝑄𝑗 + 𝐺. Ví dụ: Cho đường cong Elliptic 𝑦 2 = 𝑥 3 + 4𝑥 + 11(mod 73).
Giả sử 𝑃 =(6,18) thuộc đường cong trên. Giao thức thỏa thuận khóa Diffie – Hellman trên đường cong Elliptic 1. Lược đồ giao thức thỏa thuận khóa Diffie – Hellman nguyên thủy Giao thức thỏa thuận khóa Diffie – Hellman dùng để thiết lập một khóa chia sẻ bí mật giữa người gửi và người nhận mà không cần dùng đến mã hóa công khai. Độ an toàn của giao thức thỏa thuận khóa phụ thuộc vào bài toán tính Logarith rời tạc.
Alice Bob a g mod p a R [0, p − 1] b R [0, p − 1] b g mod p K = (g a )b mod p K = (gb ) a mod p = g ab mod p = g ab mod p Hình 1. Lược đồ giao thức trao đổi khóa Diffie – Hellman nguyên thủy Trước tiên Alice và Bob sẽ thống nhất sử dụng chung một số nguyên tố p và một số g nhỏ hơn p và là căn nguyên thủy của p ( nghĩa là phép toán gx mod p khả nghịch ). Hai số p và g không cần giữ bí mật. Sau đó Alice chọn một số a và giữ bí mật số a này.
Bob cũng chọn số b và giữ bí mật số b. Tiếp theo Alice tính và gửi ga mod p cho Bob, Bob tính và gửi gb mod p cho Alice. Trên cơ sở đó Alice tính : (𝑔𝑏 )𝑎 𝑚𝑜𝑑 𝑝 = 𝑔𝑎𝑏 𝑚𝑜𝑑 𝑝 5 Bob tính : (𝑔𝑎 )𝑏 𝑚𝑜𝑑 𝑝 = 𝑔𝑎𝑏 𝑚𝑜𝑑 𝑝 Do đó Alice và Bob có chung giá trị gab mod p. Giá trị này có thể dùng làm khóa cho phép mã hóa đối xứng.
Như vậy, kẻ mã thám Oscar có thể có được g, p, ga và gb. Muốn tính được gab mod p , Oscar không thể dùng cách: 𝑔𝑎 𝑔𝑏 𝑚𝑜𝑑 𝑝 = 𝑔𝑎+𝑏 𝑚𝑜𝑑 𝑝 ≠ 𝑔𝑎𝑏 𝑚𝑜𝑑 𝑝 Muốn tính được gab mod p, Oscar phải tính được a hoặc b. Tuy vậy, việc tính a hay b theo công thức: 𝑎 = 𝑙𝑜𝑔𝑔 𝑔𝑎 𝑚𝑜𝑑 𝑝 hay 𝑏 = 𝑙𝑜𝑔𝑔 𝑔𝑏 𝑚𝑜𝑑 𝑝 là không khả thi do tính phức tạp của phép tính logarith rời rạc. Vậy Oscar không thể nào tính được gab mod p.
Hay nói cách khác, khóa dùng chung được trao đổi bí mật giữa Alice và Bob. Lược đồ giao thức thỏa thuận khóa Diffie – Hellman trên đường cong Elliptic Cũng giống như lược đồ thỏa thuận khóa Diffie-Hellman trên trường hữu hạn (nguyên thủy), lược đồ thỏa thuận khóa Diffie-Hellman trên đường cong Elliptic cũng công khai để dùng chung hai tham số cơ bản: đường cong Ep và điểm sinh 𝐺 ∈ 𝐸𝑝 (Điểm G có cấp n, n là một số nguyên tố lớn). 6 Alice Bob Khóa bí mật a Khóa bí mật b Khóa công khai Khóa công khai Ka = aG Kb= bG Ailce chia sẻ khóa công khai Ka cho Bob Bob chia sẻ khóa công khai Kb với Alice Alice tính toán Bob tính toán aKb = abG bKa = abG Hình 1. Lược đồ giao thức thỏa thuận Diffie – Hellman trên đường cong Elliptic Lược đồ thỏa thuận khóa Diffie-Hellman trên đường cong Elliptic được mô tả như sau: Giả sử có 2 người dùng Alice và Bob cần thỏa thuận khóa phiên với nhau, Alice và Bob sẽ thực hiện giao thức tương tác để thiết lập một khóa mật chung cho phiên liên lạc: 1.
Alice chọn một số ngẫu nhiên 𝑎 ( 2 a n − 2 ) và đây là khóa riêng của Alice không chia sẻ. Sau đó Alice tính 𝐾𝑎 = 𝑎𝐺 và gửi cho Bob. Tương tự Alice, Bob cũng chọn ngẫu nhiên 𝑏 ( 2 b n − 2) , giữ bí mật b. Sau đó Bob tính 𝐾𝑏 = 𝑏𝐺 và gửi cho Alice.
Alice và Bob cùng tính ra một khóa bí mật: Alice tính 𝐾𝑎,𝑏 = 𝑎𝐾𝑏 = 𝑎𝑏𝐺 Bob tính 𝐾𝑎,𝑏 = 𝑏𝐾𝑎 = 𝑎𝑏𝐺 Như vậy, kết thúc giao thức tương tác , Alice và Bob có thể cùng tính và dùng chung một khóa mật chung là 𝐾𝑎,𝑏 = 𝑎𝑏𝐺.