Link bài viết gốc từ trang substack của mình, mọi người có thể theo dõi chi tiết tại đây https://open.substack.com/pub/cryptography101/p/bai-toan-logarit-roi-rac

Giới thiệu

Trong các bài trước, chúng ta đã tìm hiểu về thuật toán RSA – một phương pháp mã hóa dựa trên độ khó của việc phân tích một số nguyên lớn thành các thừa số nguyên tố.

Trong bài này, chúng ta sẽ khám phá một thuật toán khác cũng dựa trên một bài toán khó tương tự: logarit rời rạc.

Điểm chung của cả RSA và logarit rời rạc là chúng đều sử dụng một loại hàm đặc biệt gọi là hàm một chiều (one-way function).

Hiểu đơn giản, đây là loại hàm mà nếu biết đầu vào x, ta dễ dàng tính được đầu ra y = f(x) trong thời gian ngắn. Tuy nhiên, nếu chỉ biết y, thì việc tìm lại x sao cho *f(x) = y *là cực kỳ khó, gần như không thể trong thời gian đa thức.

Chính tính chất "dễ tính xuôi, khó tính ngược" này khiến các hàm một chiều trở thành nền tảng vững chắc cho các hệ thống mã hóa hiện đại.

Để tìm hiểu về bài toán logarit rời rạc, trước tiên chúng ta cần nắm một số khái niềm cơ bản như: Group, Cyclic Group. Chúng là những kiến thức nền tảng để hiểu về mã hoá công khai dự trên bài toán logarit rời rạc. Một trong những ví dụ tiêu biểu là Diffie-Hellman Key Exchange, chúng ta sẽ tìm hiểu về DHKE ở bài sau

Group

Group G là một tập hợp các phần tử với một toán tử ◦ (có thể là nhân, hoặc cộng) kết hợp 2 phần tử thuộc G với các tính chất sau:

• Closure (Tính đóng): For all a,b∈G, the result of the operation a∗b is also in G.
• Associativity (Tính giao hoán): For all a,b,c∈G, we have (a◦b)◦c=a◦(b◦c).
• Identity element(Phần tử đơn vị): There exists an element e∈G such that a◦e=e◦a=a for every a∈G.
• Inverse element(phần tử nghịch đảo) : For every a∈G, there exists an element a⁻¹ ∈G such that a◦a⁻¹=a⁻¹◦a=e.

Ví dụ:

(ℤ,+) tập hợp số nguyên với toán từ cộng là một group. ℤ = { …, -2. -1, 0, 1, 2 …}. Phần từ đơn vị là 0, và phần tử nghịch đảo của a là -a

Trong cryptography, chúng ta quan tâm tới một group Zp* đặc biệt, có rất nhiều ứng dụng. Đinh nghĩa group Zp*

Ví dụ với p = 9

gcd(1,9)=1 *
gcd(2,9)=1 *
gcd(3,9)=3
gcd(4,9)=1 *
gcd(5,9)=1 *
gcd(6,9)=3 *
gcd(7,9)=1 *
gcd(8,9)=1 *

Vậy Z9* = {1,2,4,5,7,8}

Kiểm tra lại cách tính chất của group trong Z₉*

• Tính đóng: mọi phần tử điều thuộc group
• Đơn vị: Hàng và cột 1 giữ nguyên giá trị — đúng với phần tử đơn vị
• Giao hoán: Bảng đối xứng
• Nghịch đảo: Mỗi hàng đều có 1 phần tử nghịch đảo, ví dụ: 2⋅5 = 10 ≡ 1 mod 9

Cyclic group

húng ta ký hiệu |G| là bậc của group G hoăc số phần tử của group G. Theo ví dụ trên |Z₉*| = 6.

Chúng ta có khái niệm bậc của group G, ngoài ra chúng ta còn có khái niệm bậc của phần tử trong group,

Cho một nhóm G với phép toán (∘), và một phần tử a ∈ G.Bậc của a là số nguyên dương nhỏ nhất k sao cho:

a ∘ a ∘ ... ∘ a (k lần) = e

Trong đó e là phần tử đơn vị của nhóm, và ta thường viết ngắn gọn là: a^k = e. Ký hiệu bậc của a là ord(a) hoặc |a|.

Ví dụ trong group Z₉*, tìm ord(5)?

5^1 = 5 mod 9 = 5 5^2 = 5 * 5 mod 9 = 7 5^3 = 7 * 5 mod 9 = 8 5^4 = 8 * 5 mod 9 = 4 5^5 = 4 * 5 mod 9 = 2 5^6 = 2 * 5 mod 9 = 1 => ord(5) = 6

Giả sử chúng ta cứ tiếp tục luỹ thừa lên thì điều gì xảy ra:

5^7 = 1 * 5 mod 9 = 5 5^8 = 5 * 5 mod 9 = 7 5^9 = 7 * 5 mod 9 = 8 5^10 = 8 * 5 mod 9 = 4 5^11 = 4 * 5 mod 9 = 2 5^12 = 2 * 5 mod 9 = 1

Như chúng ta thấy, kết quả luôn là tâp hợp {5, 7, 8, 1, 2, 1}.

Tiếp theo chúng ta có khái niệm cyclic group:

Một group 𝐺 được gọi là cyclic group nếu tồn tại một phần tử a ∈ 𝐺 sao cho mọi phần tử trong 𝐺 đều có thể biểu diễn dưới dạng lũy thừa (hoặc bội) của a. Ta gọi a là primitive elements hoặc generator của nhóm đó. Ta có: ord(a) = |G|

Trong ví dụ trước, ta có ord(5) = | Z₉*| = 6. Vậy 5 là generator trong Z₉* ( với phép nhân modular 9) .

Note: Vì 7 là số nguyên tố nên tất cả các nhỏ hơn 7 đều có gcd với 7 = 1. Ta hãy lập bảng luỹ thừa trong modular 7

Hàng 3 và 5 có đầy đủ các phần tử thuộc Z₇* => 3 và 5 là generator của Z₇*

Một tính chất khác là a^|G| luôn bằng 1 ( cột a^6) .

Từ bảng trên ta có tính chất sau: ord(a) divides |G| cho mọi a thuộc G. Ví dụ:

ord(2) = 3 ord(3) = 6 ord(4) = 3 ord(5) = 6 ord(6) = 2 => ord(a) divides |G|

Phần tiếp theo

Bài viết hôm nay đã đưa chúng ta qua khá nhiều khái niệm quan trọng: từ group, cyclic group cho đến cách xác định generator group. Nếu bạn theo dõi được tới đây, xin chúc mừng – bạn đã đặt nền móng vững chắc để bước vào thế giới thú vị của mật mã học hiện đại.

Trong phần tiếp theo, chúng ta sẽ cùng khám phá:

• Bài toán logarit rời rạc là gì?
• Vì sao nó lại “một chiều”?
• Và nó có vai trò gì trong các thuật toán bảo mật như Diffie-Hellman, ElGamal hay thậm chí là Elliptic Curve Cryptography (ECC).

Hãy subscribe trang Substack của mình để không bỏ lỡ bài viết bổ ích nào https://cryptography101.substack.com/