Hệ mật mã khóa công khai
Giới thiệu
Mô hình mật mã cổ điển giữa Alice (người gửi) và Bob (người nhận) sử dụng một khóa bí mật K để mã hóa và giải mã thông tin Trong hệ thống này, quy trình giải mã dK có thể giống với eK hoặc dễ dàng phân tích từ eK, như trong hệ mật DES Các hệ mật này được gọi là hệ mật khóa bí mật, và nếu khóa bị lộ, tính an toàn của hệ thống sẽ bị đe dọa Nhược điểm của hệ mật này thể hiện qua hai khía cạnh chính.
Vấn đề trao đổi khóa giữa người gửi và người nhận đòi hỏi phải có một kênh an toàn để bảo mật thông tin, đảm bảo rằng chỉ có hai bên biết về khóa Tuy nhiên, trong bối cảnh khối lượng thông tin toàn cầu ngày càng lớn, việc thiết lập một kênh an toàn như vậy trở nên khó khăn và tốn kém, dẫn đến chậm trễ trong quá trình trao đổi.
● Tính bí mật của khóa: Không có cơ sở quy trách nhiệm nếu mà khóa bị tiết lộ.
Vào năm 1976, Whitfield Diffie và Martin Hellman đã phát minh ra mã hóa khóa công khai, hay còn gọi là mã hóa bất đối xứng, giúp giải quyết vấn đề bảo mật thông tin Đây được xem là một bước đột phá quan trọng trong lĩnh vực mã hóa.
Xét lại mô hình mã hóa đối xứng:
Để khắc phục điểm yếu của mã hóa đối xứng, nghiên cứu đã tập trung vào việc tìm kiếm phương pháp cho phép mã hóa và giải mã sử dụng hai khóa khác nhau Cụ thể, quy trình sẽ là C = E(P, K1) và P = D(C, K2) Nếu thành công, chúng ta sẽ có hai phương án thực hiện mã hóa hiệu quả hơn.
Phương án 1 đề xuất rằng người nhận, Bob, giữ bí mật khóa K2, trong khi khóa K1 được công khai cho tất cả mọi người Khi Alice muốn gửi dữ liệu cho Bob, cô sử dụng khóa K1 để mã hóa thông tin Bob sau đó sử dụng khóa K2 để giải mã Tuy nhiên, nếu có một kẻ tấn công như Charlie biết khóa K1, hắn vẫn không thể giải mã dữ liệu mà không có khóa K2.
Chỉ có Bob mới có khả năng giải mã dữ liệu bằng cách sử dụng khóa K2, điều này đảm bảo tính bí mật trong quá trình truyền dữ liệu Một lợi thế lớn của phương pháp này là không cần thiết phải truyền khóa K1 qua kênh an toàn.
Phương án 2 đề xuất rằng Alice giữ khóa bí mật K1 và công khai khóa K2 Khi Alice muốn gửi dữ liệu cho Bob, cô sử dụng K1 để mã hóa, trong khi Bob dùng K2 để giải mã Mặc dù Charlie cũng biết K2 và có thể giải mã, phương pháp này vẫn đảm bảo tính chứng thực và chống chối bỏ, vì chỉ Alice biết K1 Nếu Bob giải mã được bản tin bằng K2, điều đó chứng tỏ Alice là người gửi Tuy nhiên, nếu Charlie có K1 và gửi bản mã, Alice sẽ bị quy trách nhiệm làm lộ khóa K1 Một điểm thuận lợi là không cần truyền K2 qua kênh an toàn.
Kết hợp phương án 1 và phương án 2 sẽ giúp mô hình đề xuất khắc phục hoàn toàn nhược điểm của mã hóa đối xứng Trong hai phương án này, một khóa được giữ bí mật chỉ cho một người biết, trong khi khóa còn lại được công khai.
Mô hình mã hóa này được gọi là mã hóa khóa công khai hay mã hóa bất đối xứng Để dễ dàng hơn trong việc trao đổi thông tin, chúng ta sẽ quy ước các ký hiệu như sau:
● Khóa bí mật hay private key trong mô hình trên sẽ được ký hiệu là KS.
● Khóa công khai hay public key được ký hiệu là KP.
● Bản rõ ký hiệu là M còn bản mã giữ nguyên ký hiệu là C
● Phương án 1 viết lại thành:
● Phương án 2 viết lại thành:
Vấn đề đặt ra là liệu có mô hình mã hóa và giải mã với hai khóa khác nhau hay không KP và KS cần có mối quan hệ nhất định để thực hiện mã hóa và giải mã, tức là KS = f(KP) Tuy nhiên, điều quan trọng là việc tính toán KS từ KP phải là bất khả thi về mặt thời gian, nếu không, bí mật của khóa KS sẽ không còn ý nghĩa Để đạt được điều này, các hàm một chiều (one way function) thường được sử dụng, vì hàm nghịch đảo của chúng rất khó thực hiện Ví dụ, việc tính tích N = pq từ hai số nguyên p và q là dễ dàng, nhưng việc phân tích N để tìm lại p và q lại là điều bất khả thi về mặt thời gian Có nhiều phương pháp mã hóa thuộc loại mã hóa công khai.
● Hệ mật RSA: Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số nguyên lớn.
Hệ mật Merkle - Hellman dựa trên độ khó của bài toán tổng các tập con, một bài toán NP đầy đủ, thuộc nhóm các bài toán không có giải thuật hiệu quả trong thời gian đa thức Tuy nhiên, tất cả các hệ mật xếp ba lô khác đều đã được chứng minh là không an toàn, ngoại trừ hệ mật Chor-Rivest.
Hệ mật McEliece dựa trên lý thuyết mật mã đại số và vẫn được coi là an toàn, với khả năng giải mã cho các mã tuyến tính, một bài toán được xác định là NP đầy đủ.
● Hệ mật ElGamal: Dựa trên tính khó giải của toán logarithm rời rạc trên các trường hữu hạn.
● Hệ mật Chor-Rivest: Cũng được coi một hệ mật xếp ba lô Tuy nhiên nó vẫn được coi là an toàn.
Hệ mật trên đường cong Elliptic là biến thể của hệ mật ElGamal, hoạt động trên các đường cong Elliptic thay vì trên các trường hữu hạn Hệ mật này cung cấp mức độ bảo mật cao với kích thước khóa nhỏ hơn so với các hệ mật khóa công khai khác.
Hệ mật khóa công khai không thể đảm bảo độ mật tuyệt đối, vì khi phân tích một bản mã, kẻ tấn công có thể thử nghiệm các bản tin rõ bằng luật mã hóa công khai cho đến khi tìm ra bản rõ duy nhất Kết quả này chính là bản giải mã của bản mã đã phân tích Do đó, chúng ta chỉ có thể đánh giá độ mật của các hệ mật này từ góc độ tính toán.
Trong nghiên cứu về hệ mật khóa công khai, khái niệm hàm cửa sập một chiều (one way trapdoor functions) đóng vai trò quan trọng Hàm mã hóa công khai eK của Bob cần phải dễ tính toán, nhưng việc tìm hàm ngược (hàm giả mã) lại rất khó khăn đối với những người không phải là Bob Đặc tính này được gọi là đặc tính một chiều, do đó, điều kiện cần thiết là eK phải là hàm một chiều.
Lý thuyết số
Phép chia modulo là phép chia lấy phần dư
Một cách tổng quát: a mod n = r với a ≥ 0; n > 0; 0 ≤ r ≤ n-1
Hai số a và b được gọi là đồng dư trong phép chia modulo n nếu chúng có cùng số dư khi chia cho n Sự so sánh đồng dư này được ký hiệu bằng a ≡ b (mod n) hoặc a ≡ b mod n.
Phép toán modulo chia tập số tự nhiên N thành n lớp tương đương dựa trên các giá trị của r trong tập {0, 1, 2, 3…, n-1} Chẳng hạn, khi n = 4, ta có 4 lớp tương đương.
Tính chất của phép modulo
Cho a, b và n là các số nguyên, phép modulo có các tính chất:
(a 𝗑 b) mod n = [(a mod n) 𝗑 (b mod n)] mod n Ước số
Nếu a mod n = 0 (hay a ≡ 0 mod n), điều này có nghĩa là a chia hết cho n, tức là n là ước số của a Ước số chung lớn nhất (UCLN) của hai số a và b được ký hiệu là gcd(a, b) Để xác định UCLN của hai số này, chúng ta có thể áp dụng thuật toán Euclid.
Một số p được gọi là số nguyên tố nếu p chia hết cho 1 và chính nó, ngoài ra không chia hết cho số nào khác từ 2 đến p - 1.
Số nguyên tố cùng nhau
Hai số nguyên a và b được xem là nguyên tố cùng nhau khi ước số chung lớn nhất (UCLN) của chúng bằng 1, ký hiệu là a⏊b Ví dụ, 3 và 8, cũng như 7 và 9, là những cặp số nguyên tố cùng nhau Ngược lại, hai số 20 và 15 không phải là nguyên tố cùng nhau vì UCLN của chúng là 5.
Phần tử nghịch đảo trong phép nhân modulo
Nếu hai số nguyên a và n nguyên tố cùng nhau, thì tổn tại một số nguyên w sao cho: a.w ≡ 1 mod n
Ta gọi w là phần tử nghịch đảo của a trong phép modulo cho n và ký hiệu là a -1
Ví dụ: n = 10, a = 7 là hai số nguyên tố cùng nhau, do đó tìm được a -1 = 3
(21 ≡ 1 mod 10) n = 10, a = 2 không phải là hai số nguyên tố cùng nhau, ta có bảng phép nhân
Trong bảng trên, không có số a -1 nào sao cho a.a -1 đồng dư 1 mod 10, điều này chứng tỏ rằng không tồn tại phần tử nghịch đảo Để tính toán a -1, có thể áp dụng thuật toán Euclid mở rộng.
Tính chất phần tử sinh của z n ¿
Nhóm số nguyên modulo n, ký hiệu z_n, có phần tử sinh nếu và chỉ nếu n thuộc các dạng 2, 4, p^k hoặc 2p^k, với p là một số nguyên tố lẻ và k ≥ 1 Đặc biệt, nếu p là một số nguyên tố, thì z_n chắc chắn có phần tử sinh.
Nếu α là một phần tử sinh của z n ¿ thì: z n ¿ ={ α ⅈ mod n | 0 ≤ⅈ ≤ ϕ ( n)−1}
Giả sử rằng α là một phần tử sinh của nhóm z_n Khi đó, b = α^i mod n cũng là một phần tử của z_n nếu và chỉ nếu (i, ϕ(n)) = 1 Từ đó, ta có thể kết luận rằng z_n là nhóm cyclic với số lượng phần tử sinh là ϕ(ϕ(n)).
α ∈ Z n ¿ là một phần của z n ¿ nếu và chỉ nếu α Φ ( n ) ∕ p ≠ 1 ( mod n) đối với mỗi nguyên tố p của ϕ ( n )
1.2.2 Định lý Fermat Định lý:
Nếu p là số nguyên tố và a là số nguyên không chia hết cho p thì a p-1 ≡ 1 mod p
Xét tập X gồm p-1 phần tử:
Ta có hai nhận định sau:
- Không có phần tử nào của tập X bằng 0 vì a nguyên tố cùng nhau với p.
Không có hai phần tử i và j (với i ≠ j) thỏa mãn điều kiện ia mod p = ja mod p Vì a là số nguyên tố cùng nhau với p, nên tồn tại a^(-1) trong phép modulo p Do đó, nếu ia ≡ ja mod p, thì ta có iaa^(-1) ≡ jaa^(-1) mod p, dẫn đến i = j.
≡ j mod p Điều này trái với giả thiết i ≠ j.
Từ hai nhận xét trên ta suy ra các phần tử của X sẽ là một hoán vị các giá trị {1, 2, 3…, p-1} Do đó: a 𝗑 2a 𝗑 …(p-1)a ≡ [1 𝗑 2 𝗑 … (p-1)] mod n
Sau đây là một sốt ví dụ của Fermat p = 5, a = 7 4 => 49.49 = 2401, 2401 ≡ 1 mod 5 p = 7, a = 4 6 => 64.64 = 4096, 4096 ≡ 1 mod 5
Ta định nghĩa phép lũy thừa modulo như hình, để tính y từ a, x từ n và các số nguyên: y = a x mod n = (a.a…a) mod với x số a nhân với nhau
Ta chỉ xét trường hợp n là số nguyên tố Bảng minh hoặc các giá trị của phép lũy thừa modulo với n = 19, a và x từ 1 đến 18.
Hình 2 Bảng giá trị modulo với n = 19
Nhìn vào bảng trên, ta thấy rằng không phải hàng nào cũng có giá trị từ 1 đến 18 Xét hàng a = 11, ta có:
Do đó hang a = 11 (tương ứng với dãy 11 1 , 11 2 , , 11 18 ) chỉ có ba giá trị 11,
7, 1 được lặp theo chu kỳ.
Trong bảng trên, chỉ các giá trị a = 2, 3, 10, 13, 14, 15 tạo ra dãy a1, a2, …, a18 với đầy đủ các giá trị từ 1 đến 18 khi thực hiện phép modulo 19 Do đó, chỉ có các giá trị a này mới đảm bảo rằng phép lũy thừa modulo là khả nghịch.
Trong trường hợp tổng quát với mỗi n chỉ có một trường hợp của a thì phép lũy thừa là khả nghịch Lúc này a được gọi là primitive root của n.
Và cũng tương tự như số thực, nếu biết y, a và n, muốn tìm lại x thì ta cũng dùng làm logarit, được gọi là logarit rời rạc. x = d log a, n y
Việc tính logarit rời rạc, đặc biệt khi a và n là các số lớn, đã được chứng minh là tốn kém về thời gian và gần như bất khả thi Vì lý do này, phép lũy thừa modulo được coi là một hàm một chiều và được ứng dụng hiệu quả trong phương pháp trao đổi khóa Diffie-Hellman.
Bảo mật, Chứng thực và Chống chối bỏ
Khi Alice muốn gửi dữ liệu cho Bob bằng mã hóa công khai, cả hai sẽ chọn cặp khóa bí mật - khóa công khai Cặp khóa của Alice được ký hiệu là KPA - KSA, trong khi cặp khóa của Bob là KPB - KSB Để gửi dữ liệu bí mật cho Bob, Alice sẽ mã hóa dữ liệu bằng khóa công khai KPB của Bob, và Bob sẽ sử dụng khóa bí mật KSB để giải mã.
Để đảm bảo tính xác thực và trách nhiệm của Alice trong việc gửi dữ liệu, cô sẽ áp dụng phương án 2: mã hóa dữ liệu bằng khóa riêng KSA, trong khi Bob sẽ sử dụng khóa công khai KPA của Alice để tiến hành giải mã.
Hình 4 Mô hình chống chối bỏ với mã hóa công khai
Để đảm bảo tính bảo mật và xác thực trong việc truyền tải thông điệp, mô hình kết hợp giữa tính bí mật, chứng thực và chống chối bỏ là cần thiết Trong trường hợp Bob nhận được bản giải mã hợp lệ, điều này chứng tỏ Alice là người gửi, bởi chỉ cô mới sở hữu khóa bí mật KSA Tuy nhiên, nếu Charlie can thiệp và chỉnh sửa bản mã C, Bob sẽ nhận được một thông điệp vô nghĩa Nếu Charlie có được khóa KSA, Alice sẽ không thể thoái thác trách nhiệm về việc lộ khóa Ngoài ra, Charlie cũng biết khóa công khai KPA của Alice, cho phép hắn giải mã bản mã C và nắm được nội dung của bản rõ M.
Hình 5 Mô hình kết hợp bảo mật, chúng thực và chống chối bỏ
Trao đổi khóa
1.4.1 Trao đổi khóa công khai
Khi hai người muốn truyền dữ liệu qua phương pháp mã hóa khóa công khai, việc đầu tiên họ cần làm là trao đổi khóa công khai Do đây là khóa công khai, quá trình trao đổi không cần giữ bí mật và có thể thực hiện công khai trên các kênh truyền thông thông thường Alice, Bob hoặc bất kỳ ai khác đều có thể công bố khóa công khai của mình một cách rộng rãi.
Hình 6 Trao đổi khóa công khai tự phát
Để giải quyết vấn đề chứng thực trong việc xác định khóa công khai của Bob, Alice cần sử dụng mô hình "Chứng chỉ khóa công khai" (public key certificate) Trong mô hình này, một tổ chức được gọi là trung tâm chứng thực (Certificate Authority - CA) sẽ cấp chứng chỉ Điều này giúp ngăn chặn việc mạo danh, như trường hợp Charlie có thể giả mạo Bob bằng cách sử dụng khóa của mình Các bước cấp chứng chỉ cho Alice sẽ được thực hiện thông qua trung tâm chứng thực.
➔ Alice gửi định danh IDa và khóa công khai KPA của mình đến trung tâm chứng thực.
➔ Trung tâm chứng nhận kiểm tra tính hợp lệ của Alice, ví dụ nếu IDa là
“Microsoft”, thì Alice phải có bằng chứng chứng tỏ mình thực sự là công ty Microsoft.
Trung tâm chứng thực cấp chứng chỉ Ca để xác nhận rằng khóa công khai KPA tương ứng với IDa, và chứng chỉ này được ký bằng khóa riêng của trung tâm, đảm bảo tính xác thực của nội dung chứng chỉ do trung tâm phát hành.
➔ Alice công khai chứng chỉ CA.
Bob cần trao đổi thông tin với Alice, vì vậy anh sẽ giải mã chứng chỉ CA bằng khóa công khai của trung tâm chứng thực để lấy khóa công khai KPA của Alice Nếu Bob tin tưởng vào trung tâm chứng thực, anh sẽ tin rằng KPA tương ứng với IDa, tức là tương ứng với Alice.
Hình 7 Trao dổi khóa công khai dùng trung tâm chứng thực
Như vậy có thể nhận thấy rằng nếu Bob muốn gửi thông điệp cho Alice,David, thì Bob không cần phải tin tưởng vào khóa công khai của Alice,
David hay bất kỳ ai Bob chỉ cần tin tưởng vào trung tâm xác thực và khóa công khai của trung tâm chứng thực là đủ.
Mô hình chứng chỉ khóa công khai hiện đang được áp dụng rộng rãi với chuẩn X.509 Trên toàn cầu, có khoảng 80 tổ chức chứng thực chứng chỉ khóa công khai.
1.4.2 Dùng mã hóa công khai để trao đổi khóa bí mật
Phương pháp mã hóa khóa công khai có thời gian mã hóa và giải mã chậm hơn so với mã hóa đối xứng, do đặc điểm toán học của nó Tuy nhiên, để đảm bảo tính bảo mật, mã hóa đối xứng vẫn được ưa chuộng trong thực tế Mã hóa khóa công khai chủ yếu được sử dụng để thiết lập khóa bí mật cho mỗi phiên trao đổi dữ liệu, gọi là khóa phiên (session key), và mỗi phiên sẽ sử dụng một khóa bí mật khác nhau.
Hình 8 Thiết lập khóa phiên bí mật bằng mã hóa khóa công khai
Alice tạo một khóa phiên (KS) được mã hóa bằng khóa bí mật của mình và sau đó mã hóa tiếp bằng khóa công khai của Bob Bob giải mã khóa phiên này bằng khóa bí mật của mình và khóa công khai của Alice, đảm bảo rằng chỉ có Bob và Alice biết được KS Nhờ vào tính bí mật và tính chống chối bỏ, khóa phiên này có thể được sử dụng làm khóa bí mật cho mã hóa đối xứng trong việc trao đổi dữ liệu giữa hai bên Sau khi hoàn tất phiên trao đổi, KS sẽ được hủy bỏ, giảm thiểu khả năng bị lộ Trong quá trình này, vai trò của mã hóa công khai không chỉ là bảo mật dữ liệu mà còn là đảm bảo tính bí mật của khóa đối xứng, chỉ có Alice và Bob nắm giữ thông tin về khóa KS.
Phương pháp trao đổi khóa Diffie - Hellman
Phương pháp trao đổi khóa Diffie-Hellman cho phép thiết lập một khóa bí mật giữa người gửi và người nhận mà không cần sử dụng mã hóa công khai Phương pháp này dựa trên hàm một chiều và logarit rời rạc, và khác biệt với RSA về mặt mã hóa.
Alice và Bob đồng ý sử dụng chung một số nguyên tố p và một số nguyên tố g nhỏ hơn p, với g là primitive root của p Hai số p và g không cần giữ bí mật Alice chọn một số bí mật a, trong khi Bob cũng chọn một số bí mật b Alice tính toán g^a mod p và gửi kết quả cho Bob, sau đó Bob tính g^b mod p và gửi lại cho Alice.
Alice và Bob chia sẻ giá trị g^ab mod p, được sử dụng làm khóa mã hóa đối xứng Tuy nhiên, kẻ phá mã Charlie không thể tính g^ab mod p từ g^a và g^b do tính phức tạp của logarit rời rạc Điều này có nghĩa là khóa chung giữa Alice và Bob được bảo mật Dù vậy, thuật toán Diffie-Hellman vẫn có thể bị tấn công bởi phương pháp Man in the Middle, trong đó Charlie đứng giữa, chặn và giả mạo thông điệp giữa Alice và Bob Charlie có thể thiết lập khóa g^ac mod p với Alice và g^bc mod p với Bob, cho phép hắn xem được dữ liệu mà không ai hay biết.
Trong tấn công Man in the Middle, phương pháp Diffie-Hellman yêu cầu quá trình thiết lập khóa phải được mã hóa bằng một khóa công khai để đảm bảo an toàn Mặc dù có thể sử dụng khóa đối xứng khác, nhưng Diffie-Hellman vẫn có những ưu điểm nhất định, đặc biệt trong những tình huống mà tấn công Man in the Middle không thể thực hiện.
Trong mô hình thiết lập khóa phiên bằng mật mã khóa công khai, nếu Charlie ghi lại tất cả thông điệp giữa Alice và Bob, khi phát hiện ra khóa bí mật KSA và KSB, Charlie có khả năng khôi phục khóa đối xứng KS Từ đó, Charlie có thể giải mã các bản rõ được mã hóa bằng khóa KS Mô hình này sử dụng phương pháp Diffie-Hellman được bảo vệ bằng mã hóa khóa công khai.
Hình 10 Bảo vệ khóa Diffie – Hellman bằng khóa công khai
Trong mô hình này, mặc dù Charlie có thể phát hiện khóa bí mật KSA và KSB của Alice và Bob, cũng như các giá trị g a mod p và g b mod p, nhưng Charlie vẫn không thể khôi phục khóa bí mật g ab mod p Do đó, Charlie không thể khôi phục các bản rõ giữa Alice và Bob, điều này thể hiện rõ ý nghĩa của phương pháp Diffie-Hellman.
Hệ mật đường cong Elliptic
Đường cong Elliptic
Đường cong Elliptic phổ biến thường được biểu diễn qua phương trình Weierstrass y² = x³ + Ax + B, trong đó A và B là các hằng số Các giá trị A, B và x thường thuộc về các trường hữu hạn như trường số thực R, số phức C, số hữu tỉ Q, hoặc các trường Fp (Zp*) với số nguyên tố p, và các trường hữu hạn Fq với q = pk, k≥1 Đây là những trường thường được sử dụng trong nghiên cứu mật mã trên đường cong Elliptic.
Nếu K là một trường mà A, B thuộc K, thì E được gọi là được xác định trên K Chúng ta quy ước rằng E và K là ký hiệu của đường cong Elliptic cùng với trường mà E được xác định trên đó.
Nếu ta muốn xét các điểm có các tọa độ thuộc một trường L ⊇ K thì ta viết E(L) Theo định nghĩa tập này luôn luôn có điểm ∞ được định nghĩa :
E(L) = {∞} ∪ {(x, y) ∈ LxL | y² = x³ + Ax + B} Để hiểu rõ về đường cong Elliptic, ta cần nghiên cứu trên trường số thực R, với hai dạng cơ bản: đường cong y² = x³ - x có ba nghiệm thực khác nhau, trong khi đường cong y² = x³ + x chỉ có một nghiệm thực duy nhất Nếu có nghiệm bội, điều này sẽ không được chấp nhận, do đó giả thiết rằng 4A³ + 27B² ≠ 0 là cần thiết.
Nếu đường bậc 3 có các nghiệm r1, r2, r3 thì có thể chứng minh rằng biệt thức của đường cong này là (( r 1 −r 2 ) ( r 1 −r 3 )( r 2 −r 3 )) 2 =−( 4 A 3 +27 B 2 ) a y 2 =x 3 − x b y 2 = x 3 + x
Các nghiệm của đường cong phải khác nhau, tuy nhiên, trường hợp các nghiệm không khác nhau cũng rất thú vị nhưng sẽ không được đề cập trong tài liệu này Phương trình tổng quát của đường cong Elliptic theo dạng Weierstrass được biểu diễn như sau: y² + a₁xy + a₃y = x³ + a₂x² + a₄x + a₆.
Trong đó a1, …, a6 là các hằng số, và dạng tổng quát này rất hữu ích khi làm việc với trường đặc số 2 và 3 (chap(K)) Nếu đặc số của trường khác, việc áp dụng các hằng số này sẽ mang lại những lợi ích nhất định trong nghiên cứu.
2 thì có thể chia cho 2 và biến đổi về dạng:
Hay có thể viết nó như sau y 1 2
2 và các hằng số a 2 ' , a ' 4 ,a 6 ' Khi K có đặc số bằng 3 hay khác
3 ta có thể dùng phép thế x 1 = x + a 2
Để cải thiện đường cong Elliptic, việc thêm điểm ở vô cùng là rất hữu ích Điểm này có thể được biểu diễn đơn giản là ∞, đặt ở đỉnh của trục y, và được xem như là một ký hiệu hình thức phục vụ cho các quy tắc tính toán Ví dụ, một đường thẳng được coi là đi qua điểm ∞ khi nó là trục thẳng đứng, tức là x.
Điểm ∞ có vẻ không tự nhiên nhưng mang lại lợi ích khi xem xét hai đầu của trục y như gặp nhau tại điểm này Trong trường hợp làm việc với trường hữu hạn, việc phân biệt giữa đỉnh và đáy của trục y trở nên không có ý nghĩa do không thể sắp xếp các phần tử Do đó, việc giới thiệu các tọa độ xạ ảnh là cần thiết để hiểu rõ hơn về trục y Điều này cho thấy ∞ nên được coi là một ký hiệu hình thức thỏa mãn những tính chất nhất định, và cần thiết để sắp xếp cho hai đường thẳng đứng gặp nhau.
Theo tính đối xứng, hai đường thẳng gặp nhau ở đỉnh và đáy của trục y phải là một điểm duy nhất Do đó, "đỉnh ∞" và "đáy ∞" chỉ là một, thể hiện tính chất có lợi của ∞ trong toán học.
2.1.2 Cộng các điểm trên đường cong Elliptic
Xét hai điểm P 1 =( x 1 , y 1 ) và P 2 =( x 2 , y 2 )trên đường cong Elliptic E y 2 +a 1 xy +a 3 y= x 3 +a 2 x 2 + a 4 x+ a 6
Phép cộng giữa hai điểm trên đường cong E được định nghĩa như sau:
( x 3 , y 3 ' )là giao điểm của đường cong E và đường thẳng đi qua P 1 và P 2 Vì 2 điểm P 3( x 3 , y 3 )và − P 3
' ( x 3 , y 3 ' )đều nằm trên đường cong E nên ( x 3 , y 3 )và ( x 3 , y 3 ' )phải thỏa mãn phương trình (1.2). Công thức để tính các giá trị ( x 3 , y 3 )sẽ được chứng minh ở dưới đây
Hình 11 Phép cộng trên đường cong Elliptic
Trong các tài liệu về đường cong Elliptic, như [3, 7, 8], vẫn chưa có sự thỏa mãn với các dẫn dắt và chứng minh cho công thức tổng quát của các giá trị (x₃, y₃) Vì vậy, bài viết này sẽ cung cấp chứng minh chi tiết cho các công thức này Đường thẳng đi qua hai điểm P₁ và P₂ được biểu diễn bằng phương trình: y = λx + μ.
Trong đó λ là hệ số góc của đường thẳng đi qua P 1 , P 2 Ta có: y 1 =λ x 1 + μ y =λ x + μ y 3 ' = λ x 3 + μ
2.1.2.1 Trường hợp 2 điểm không trùng nhau P 1 ≠ P 2
Từ (1.5) và (1.6) suy ra: y 1 − y 2 = x ( x 1 − x 2 ), khi P 1 ≠ P 2 , nghĩa là x 1 ≠ x 2 ta có công thức: λ= y 1 − y 2 x 1 − x 2 μ= y 1 − λ x 1 = y 1 − y 1 − y 2 x 1 − x 2 × x 1 = x 1 y 2 − x 2 y 1 x 1 − x 2
Tiếp theo thay y ở (1.4) vào phương trình (1.2) ta có:
Từ đó dẫn đến phương trình r ( x )=0 với: r ( x )= x 3 +( a 2 − λ 2 − a 1 λ ) x 2 + ( a 4 −2 λμ−a 3 λ−a 1 μ ) x+ a 6 − μ 2 −a 3 μ Biết rằng r(x) có
Để phân biệt nghiệm của đa thức r(x) = (x - x1)(x - x2)(x - x3), ta có thể sử dụng các phương trình liên quan đến các hệ số của r(x) Đồng nhất các hệ số x² trong hai phương trình (*) và (**) cho thấy rằng x1 + x2 + x3 = -(a² - λ² - a1λ) Từ đó, ta có thể tính giá trị x3 theo công thức x3 = λ² + a1λ - a² - x1 - x2 Khi đã xác định được x3, ta tiếp tục tính giá trị y3, và từ đó có thể viết lại phương trình thành dạng y² + (a1x3 + a3)y - (x3³).
+a 4 x 3 +a 6) =0 Phương trình bậc 2 này có 2 nghiệm là: y 3 , y 3 ' = −( a 1 x 3 +a 3) ± √ Δ
Cộng 2 nghiệm này ta sẽ có y 3 ' + y 3 =−a 1 x 3 −a 3 , mặt khác do y 3 ' nằm trên đường thẳng P 1 , P 2 nên y 3 ' = λ x 3 + μ Từ đây có thể tính được y 3 theo công thức: y 3 =− λ x 3 −μ−a 1 x 3 −a 3
Thay à từ (1.9) ta cú thể tớnh y3 dưới dạng sau: y 3 = λ ( x 1 −x 3 ) − y 1 −a 1 x 3 −a 3
2.1.2.2 Trường hợp 2 điểm trùng nhau P 1 =P 2
Khi x1 = x2 và y1 = y2, công thức tính λ không khả thi do xuất hiện phép chia cho 0 Trong trường hợp này, λ là hệ số góc của đường thẳng tiếp tuyến với đường cong E tại điểm P1 hoặc P2 Hệ số góc này tương ứng với đạo hàm dy/dx Bằng cách áp dụng các quy tắc đạo hàm cho tích và hàm số hợp, cũng như lấy đạo hàm hai vế của phương trình (1.2) theo dx, ta có thể viết: d(y² + a₁xy + a₃y)/dx = d(x³ + a₂x² + a₄x + a₆)/dx, từ đó suy ra d(y²)/dx + d(a₁xy)/dx + d(a₃y)/dx = 3x² + 2a₂x + a₄.
2 y dy dx + a 1 ( y + x dy dx ) + a 3 dy dx ¿ 3 x 2 +2 a 2 x +a 4
Như vậy với điểm P 1 =( x 1 , y 1 ) ta có: λ= 3 x 1 2 +2 a 2 x 1 +a 4 −a 1 y 1
Trong tất cả các trường hợp điểm P 3 là tổng của 2 điểm P 1 , P 2 sẽ là điểm có tọa độ là:
Với đường cong E dạng (1.1), khi đó a 1 =a 3 =a 2 =0 và P 3 sẽ được tính theo công thức:
P 3 ( x 3 , y 3 ) =¿ ) Trong trường hợp P 1 = P 2 , (1.18) sẽ được biến đổi thành: λ= 3 x 1 2 +a 4
2.1.3 Nhân vô hướng các điểm trên đường cong Elliptic
Với n ∈ N ∖ { 0 } định nghĩa phép nhân vô hướng của điểm P nằm trên đường cong E là phép cộng n lần chính bản thân điểm P:
Để tối ưu hóa phép nhân vô hướng, phương pháp Nhân đôi và cộng có thể được áp dụng Đầu tiên, số n được biểu diễn dưới dạng tổng n = n0 + 2n1 + 2^2n2 + + 2^mnm, trong đó [n0 … nm] thuộc {0,1} Sau đó, thuật toán sẽ được thực hiện để tính toán kết quả.
Thuâ ̣t toán 1.1 Phương pháp Nhân đôi và cô ̣ng
Ngoài phương pháp Nhân đôi-và-cộng, phương pháp Trượt-cửa sổ cũng có thể được áp dụng để tối ưu hóa việc nhân vô hướng.
• Không tồn tại phép nhân 2 điểm trên đường cong E, có nghĩa là không tồn tại P × Q với P, Q ∈ E
Không tồn tại thuật toán chia vô hướng Q : n, với Q = nP Bài toán tìm số n là bài toán Logarithm rời rạc, sẽ được đề cập ở chương sau Đây là bài toán khó, thường phải thử lần lượt n = 1, 2, , n − 1 phép cộng điểm P cho đến khi tổng bằng Q Mặc dù có một số thuật toán tối ưu hơn để tìm n, nhưng bài toán này vẫn không thể giải được trong thời gian đa thức Dựa vào độ khó này, có thể xây dựng hệ mật đường cong Elliptic với các giao thức cho mã hóa, xác thực và trao đổi khóa.
Hình 12 Ví dụ về tính chất kết hợp trên đường cong Elliptic
2.1.4 Nhóm (+) của các điểm trên đường cong Elliptic
Xét đường cong Elliptic E được định nghĩa bởi phương trình y 2 = x 3 + Ax +
B Xét 3 điểm nằm trên đường cong E là P1, P2, P3 lần lượt có các tọa độ là (x1, y1), (x2, y2), (x3, y3). Để các điểm trên đường cong Elliptic tạo thành nhóm (+), “điểm vô cùng” (∞) sẽ được thêm vào đường cong, kí hiệu là O, điểm này sẽ nằm ở trên cùng và dưới cùng của trục y Một trong những thuộc tính quan trọng nhất của đường cong Elliptic là tồn tại nhóm các điểm với phép cộng nằm trên đường cong. Định lý 1.5.1 Phép cộng với các điểm P, P1, P2, P3 trên đường cong E thỏa mãn các tính chất của nhóm:
3 (Điểm nghịch đảo): Tồn tại P’ của P sao cho P + P’ = ∞;
Mật mã trên đường cong Elliptic
Alice muốn gửi một văn bản, thường được gọi là bản rõ (Plaintext), tới Bob.
Alice mã hóa văn bản thành bản mã (Ciphertext) bằng cách sử dụng khóa mã hóa (Encryption key), trong khi Bob sử dụng khóa giải mã (Decryption key) để giải mã bản mã mà anh nhận được.
Có hai phương pháp mã hóa cơ bản: mật mã đối xứng, trong đó khóa mã hóa và khóa giải mã giống nhau, và mật mã khóa công khai, hay còn gọi là mật mã không đối xứng, sử dụng hai khóa khác nhau.
2.2.1 Bài toán lô ga rít rời rạc (DLP) trên đường cong elliptic Định nghĩa : Giả sử G là một nhóm cyclic hữu hạn có cấp n Gọi a là phần tử sinh của G và a là một phần tử cũng thuộc G Khi đó Lô-ga-rít rời rạc của a theo cơ sở a trên G, được ký hiệu là logaa, là một số nguyên duy nhất x với 0 a x a n - 1 sao cho a = a x
Trong các cấu trúc nhóm cyclic, việc tính toán a = a x khi đã biết trước a và x là dễ dàng và có thể thực hiện trong thời gian đa thức Ngược lại, nếu đã biết a và a mà cần tính x, thì đây là một bài toán khó khăn, thường được thực hiện trong thời gian hàm mũ Độ khó của bài toán Lô-ga-rít còn phụ thuộc vào cấu trúc đại số mà nó được xác định.
Giả sử P là một điểm có bậc hữu hạn trên đường cong elliptic, khi đó tập
Trong nhóm cyclic với P là phần tử sinh, nếu số điểm trên đường cong elliptic là một số nguyên tố N, thì mọi điểm P trên đường cong này đều là phần tử sinh, tức là P có bậc N.
Bài toán lô-ga-rít rời rạc trên đường cong Elliptic (ECDLP)
Cho một đường cong Elliptic E trên trường hữu hạn GF(q) Giả sử P là một điểm có bậc n và Q là một điểm thuộc E Cần xác định số nguyên k, với 0 ≤ k < n - 1, sao cho Q = kP nếu tồn tại số nguyên k thỏa mãn điều kiện này.
Còn hai bài toán liên quan nữa là bài toán Diffie-Hellman Elliptic ( ECDHP) và bài toán quyết định Diffie-Hellman Elliptic (ECDDHP).
Cho trước các điểm P, aP và bP của E trên GF(q) Hãy tính abP.
Rõ ràng bài toán này có thể giải được nếu bài toán ECDLP là giải được.
Cho trước P, aP và bP của E trên GF(q) và cho trước điểm Q a E Hãy xác định xem Q = abP hay không?
Bài toán lô-ga-rít rời rạc trên đường cong Elliptic (ECDLP) trong trường hữu hạn GF(q) là nền tảng cho các thuật toán mật mã an toàn nhất hiện nay, do chưa có thuật toán nào có thể tấn công bài toán này trong thời gian tiểu hàm mũ.
Chuyên đề này sẽ khám phá các thuật toán ứng dụng trong trao đổi khóa, mã hóa và ký số cơ bản, với sự chú ý đặc biệt đến chuẩn ECC do công ty Certicom phát triển Tác giả D Hankerson đã phân tích việc triển khai ECC thông qua phần mềm, trong khi tác giả L Cao tập trung vào việc thực hiện các giao thức cơ bản của ECC bằng phần cứng.
2.2.2.1 Trao đổi khóa Diffie-Hellman ECDH
Năm 1998, Laurie và các cộng sự đã giới thiệu một giao thức trao đổi khóa dựa trên mã hóa ECC Giao thức này sau đó được công nhận và đưa vào các tiêu chuẩn như ANSI X9.42, ANSI X9.63 và IEEE P1363.
Hai bên A và B cần thiết lập một khóa phiên bí mật thông qua một kênh truyền công khai bằng cách thỏa thuận điểm cơ sở P trên E Bên A tạo ra khóa bí mật dA và gửi giá trị dAP cho bên B, trong khi bên B tạo khóa bí mật dB nhân với P và gửi lại cho A Kết quả là khóa phiên của bên A được tính là KA = dAdBP, và của bên B là KB = dBdAP Điều này cho thấy KA và KB là bằng nhau, và chỉ hai bên A và B mới có khả năng tính toán được khóa này.
Bên A Bên B dA dAP dAP dBP dBP dB
Đánh giá bảo mật cho khóa chia sẻ KA và KB cho thấy rằng để hacker có thể tìm ra các khóa bí mật dA và dB, họ cần phải giải quyết bài toán Logarithm rời rạc Mặc dù hacker có thể thu thập thông tin dAP và dBP từ đường truyền, việc tính toán dA = logP(dAP) và dB = logP(dBP) là một thách thức lớn, vì đây là bài toán khó không thể giải được trong thời gian đa thức.
2.2.2.2 Tạo khóa bí mật chia sẻ ECMQV
Tên đầy đủ của giao thức là Elliptic Curve Menezes-Qu-Vanstone. Thuật toán đã được đưa vào trong các chuẩn ANSI X9.63, IEEE 1363-
Theo tiêu chuẩn ISO/IEC 15946-3 và các quy định năm 2000, điểm cơ sở được ký hiệu là G thay vì P như thường thấy Lược đồ này thường áp dụng khi các bên A và B sử dụng cặp khóa công khai và bí mật cố định, tương ứng là (a, aG) và (c, cG).
Bên A tạo ra cặp số ngẫu nhiên (b, bG), trong khi bên B cũng sinh ra cặp số ngẫu nhiên (d, dG) Hai bên sau đó trao đổi giá trị bG và dG Hàm x được định nghĩa từ E đến N, với x là giá trị tại một điểm trên đường cong E.
Thuật toán: Tạo khóa bí mật chia sẻ ECMQV
INPUT: Các tham số của hệ mật (K, E, q, h, G), các số a, b, aG, bG, cG, dG
OUTPUT: Khóa bí mật chia sẻ Q (chia sẻ với với đối tượng có khóa công khai cG).
6: if Q = ∞ then 7: Quay lại bưóc 1.
8: end if 9: Trả về khóa Q.
Bên B có thể tính số Q bằng cách thay thế (a, b, c, d) trong thuật toán bằng (c, d, a, b) Kết quả là bên A sẽ có các giá trị uA, vA, sA, trong khi bên B sẽ có uB, vB, sB Điều này dẫn đến mối quan hệ rõ ràng: uA = vB và uB = vA.
QA = sA(dG + vA(cG)) = sA(d + vAc)G = sA(d + uBc)G = sAsBG
QB = sB(bG + vB(aG)) = sB(b + vBa)G = sB(b + uAa)G = sBsAG
Đánh giá bảo mật cho khóa chia sẻ yêu cầu Hacker tính toán các giá trị a, b, c, d bằng cách giải các bài toán Logarithm rời rạc, cụ thể là a = logG(aG), b = logG(bG), c = logG(cG), d = logG(dG) Những bài toán này rất khó và không thể giải quyết trong thời gian đa thức.
Mô hình mã hóa dữ liệu sử dụng đường cong elliptic (Elliptic Curve Encryption Scheme - ECES) bao gồm 2 thao tác: mã hóa và giải mã.
Nhúng số vào điểm trên đường cong Elliptic
Đối với mật mã khóa công khai, khi Alice muốn gửi thông điệp cho Bob, cô ấy phải chuyển đổi thông điệp thành một tập hợp các số nguyên và sau đó mã hóa chúng Trong mật mã trên đường cong elliptic, chúng ta làm việc với các điểm trên đường cong Do đó, bước đầu tiên là nghiên cứu các phương pháp chuyển đổi bản rõ thành dạng điểm P trên đường cong elliptic Lưu ý rằng ở giai đoạn này, việc chuyển đổi này không được coi là một phép mã hóa để bảo mật thông tin.
2.3.1 Chuyển thông báo thành số nguyên thuộc F p
Có nhiều phương pháp để thực hiện việc chuyển đổi thành điểm trên đường cong elliptic Bài viết này sẽ giới thiệu một trong những phương pháp đó, nhằm làm rõ quy trình và cách thức thực hiện.
Xét việc chuyển đoạn thông báo gồm 3 ký tự thành một phần tử của trường
F31013 cho (m1,m2,m3) là đơn vị thông báo như vậy, miaZ27 (ký hiệu khoảng cách nhận giá trị 0) Tính x= m1.27 2 +m2 27+m3.
Khi đó, xa Fp nếu p ≥ 26.27 2 +26 27+26 = max{x : miaZ27 , i=1 3} 19682.
Giả sử p = 41113, thông báo "LETS GET SEAFOOD" cần được chuyển đổi thành các phần tử của Fp Thông điệp này được chia thành các đoạn ba ký tự, tạo thành các nhóm như sau: "LET", "S G", "ETS", " SEA", "FOO", "D".
Bản rõ LET SGE TSE AFO OD_
Cách đơn giản để ánh xạ số nguyên x tới điểm P aE(Fp) là tìm điểm có hoành độ x Chẳng hạn, với đường cong y² = x³ + 2x - 1 trên F41113, ta có CAT = 3(27)² + 1.27 + 20 = 2234 Điểm cần tìm là P(2234, 23945) thuộc aE(F41113) Từ điểm P, ta có thể dễ dàng xác định lại giá trị của CAT.
Khoảng một nửa các giá trị x aFp là hoành độ của các điểm trên đường cong elliptic Ví dụ, giá trị Map = 13.27^2 + 1.27 + 16 = 9520 không phải là thặng dư bậc 2 theo modulo 41113, do đó không có điểm nào trên đường cong nhận 9520 làm hoành độ Tương tự, có khoảng một nửa giá trị x như vậy.
Khi x tăng dần từng đơn vị cho đến khi đạt điểm P với giá trị mới làm hoành độ, ta có điểm 9527 là điểm đầu tiên đạt tiêu chuẩn Do đó, MAP ↪(9527, 2121) Nếu chuyển 9527 về cơ số 27, ta có 9527 = 13.27^2 + 1.27 + 23 = MAW Như vậy, MAP, MAQ, MAR, …, MAW ↪(9527, 2121).
Để thực hiện ánh xạ x↪lx với số nguyên lớn l và nhúng lx, cần đảm bảo rằng trường của ta đủ lớn, cụ thể là max{lx} = l.19682 < p, nhằm tìm lại lx duy nhất Điều quan trọng là x sẽ được ánh xạ tới duy nhất một điểm của E(Fp) nếu ít nhất một trong các số f(lx), f(lx+1), …, f(lx+l-1) là thặng dư bậc 2 Xác suất không tìm được duy nhất lx cho x đã cho là 1/2 l, và số nguyên l được gọi là tham số nhúng.
Trên trường F910307, với đường cong elliptic đã đề cập, có khoảng 1 trên 5000 triệu cơ hội để không có số nào trong dãy f(lx), f(lx+1), …, f(lx+31) là thặng dư bậc 2 Nếu muốn nhúng thông điệp "YOU HAVE TWO HOURS" vào đường cong này, bảng minh họa quá trình lặp cho thấy chỉ có một điểm đối xứng duy nhất trong các giá trị rõ x.
Bản rõ YOU HAV ETW OHU ORS
Nếu đã biết tham số nhúng l, ta có thể chuyển đổi một điểm trên đường cong elliptic thành số nguyên x một cách duy nhất Giả sử ta có điểm P = (xp, yp) và cần tìm giá trị x Với l đủ lớn, ta có thể giả định rằng xp = lx + m, trong đó 0 ≤ m < l.
Khi đó x p l = x + m l , và theo giả thiết nói trên thì m/l < 1 Vì thế x = ⌊ x p l ⌋ Cần chú ý rằng ta có xác suất (1/2 l ) để bất đẳng thức 0 ≤ m < l là không đúng.
Độ an toàn của hệ mật trên đường cong Elliptic
Sức mạnh của ECC đến từ độ phức tạp trong việc thám mã, khi phải xác định số ngẫu nhiên bí mật k từ kP và P Phương pháp S – Pollard là cách nhanh nhất để giải bài toán này, với độ phức tạp tính toán khoảng 3,8 x 10^10 MIPS-năm cho khóa 150 bit So với RSA, phương pháp sàng trường số để phân tích hợp số n thành tích của hai số nguyên tố p và q có độ phức tạp là 2 x 10^8 MIPS-năm cho n 768 bit, và 3 x 10^11 MIPS-năm cho n 1024 bit Khi độ dài khóa RSA tăng lên 2048 bit, độ phức tạp cần thiết là 3 x 10^20 MIPS-năm, trong khi ECC chỉ cần khóa 235 bit đã yêu cầu tới 1,6 x 10^28 MIPS-năm.
Bài 1: Sử dụng thuật toán Euclide mở rộng để tìm ước chung lớn nhất của hai số a = 1573, b = 308
Bài 2: Tìm số nghịch đảo (nếu có) của 30 theo môđun 101 Định nghĩa: Nếu số nguyên dương x < b thỏa mãn x*b mod m = 1 thì x là nghịch đảo của b mod m, kí hiệu b -1 mod m.
Cách 1: Sử dụng thuật toán Euclide mở rộng
Bài 3: Tìm phần tử nghịch đảo của 3 trong Z*31
Giả sử b là nghịch đảo của 3 trong Z * 31
b = 3 -1 mod 31 Áp dụng thuật toán Euclide mở rộng tính: b = 3 -1 mod 31 i ri qi xi yi
Nghịch đảo của 3 trong Z * 31 là: 21
Bài 4: Tìm khóa bí mật của hệ mật RSA với pa, q) biết khóa công khai e Tính bản mã của bản rõ m7 và tiến hành giải mã ngược lại để kiểm tra lại kết quả
Trong hệ mật RSA ta có: n = p.q = 61.29 = 1769
Sô mũ giải mã: d = e -1 mod Φ(n) = 19 -1 mod 1680
Sử dụng thuật toán Euclide mở rộng tính 19 -1 mod 1680
Số mũ giải mã d = 19 -1 mod 1680 = 619
2 Mã hóa bản tin với m = 37
Trong hệ mật RSA, ta có bản mã: c = m e mod n = 37 19 mod 1769 Áp dụng thuật toán nhân bình phương có lặp ta tính: c = 37 19 mod 1769
3 Giải mã Để giải mã, ta tìm: m = c d mod n
Vậy bản rõ ban đầu: m = 582 619 mod 1769 = 37
Bài 6: Hãy tính các căn bậc hai của 12 mod 37
- Ta có 37 là số nguyên tố và 37 ≡ 5 mod 8
- Áp dụng thuật toán bình phương có lặp ta có:
⇨ r = 7 Vậy có 2 căn bậc hai (7, 30)
Bài 7: Tìm r với r2 ≡ 5 (mod 41) p là số nguyên tố ⇒ Ф(p) = p - 1
⇒ Φ(p) = 41 –1 = 40 Áp dụng định lý nếu α € Z * 41 là phần tử sinh khi đó β = α i mod n là phần tử sinh khi và chỉ khi gcd(i, Φ(p)) = 1
Căn bậc hai của r 2 ≡ 5 mod 41:
Bài 8: Cho đường cong E={(x,y) :y2=x3+x+ 6 mod 11}
Xác định tất cả các điểm của đường cong Tính tất cả các giá trị của kα với 1< k