Về một phương pháp chứng minh thuật toán mã hóa RSA

 VỀ MỘT PHƯƠNG PHÁP CHỨNG MINH THUẬT TOÁN MÃ HÓA RSA

A Demonstration of the RSA Public key cryptography

Thái Thanh Sơn

Hệ mật mã khóa bất đối xứng RSA – gọi theo tên của các tác giả Ron Rivest, Adi Shamir và Leonard Adleman ,là một hệ mật mã hiện đại quen thuộc và phổ biến.

-          Điều thú vị là để tìm ra “thuật toán ngược” – tức là thuật tóan giải mã trong hệ mật mã RSA người ta đã dựa trên một bài toán học cổ hiện nay được gọi là Định lý Trung hoa về các số dư – The Chinese Remainder theorem và một kết quả toán học huyền thoại – Định lý nhỏ Fermat – Petit théorème de Fermat.

-          Thế nhưng, một điều khá ngạc nhiên là nội dung cơ bản của định lý số dư Trung hoa lần đầu tiên được đề cập trong bộ sách Tôn tử toán kinh xuất hiện vào thời Hậu Hán (Từ năm 25 – 220) – tương truyền là do Tôn Võ, thời Đông Chu ở Trung quốc (770 – 256 trước Công nguyên) lưu lại. Đời Minh (1368–1644), Trình Đại Vỹ sau nhiều công trình nghiên cứu  đã chính thức gọi tên là bài toán "Hàn Tín điểm binh" và đến nay tên gọi này hầu như được thừa nhận. Trong các tác phẩm đó có đưa ra một công thức giải hoàn toàn đúng nhưng không có chứng minh. Đã có hàng chục công trình nghiên cứu trên thế giới tìm cách chứng minh công thức Hàn Tín. Ở Việt Nam, năm 1943, Hoàng Xuân Hãn đã đưa ra một lời giải chỉ sử dụng hoàn toàn các kiến thức số học sơ cấp - nhưng có lẽ vì hạn chế đó nên phải chấp nhận một đẳng thức không giải thích ly do.

-          Định lý nhỏ của Fermat còn gọi là định lý Fermat cuối cùng- the last Fermat theorem - được lưu lại trong một lá thư viết tay cho người bạn Frénicle de Bessy đề ngày 18 tháng 10 năm 1640. Trong hơn 300 năm nhiều nhà toán học nổi tiếng như Euler, Leibnitz…đều tìm những cách chứng minh “định lý nhỏ” đó nhưng mãi  đến năm 1995 Andrew Wiles, một nhà toán học Mỹ, sau 7 năm làm việc liên tục trong cô độc, mới đưa ra một lời giải hoàn chỉnh dài hơn 200 trang.

-          Trong bài này dựa trên chứng minh trong cách giải bài toán Hàn Tín điểm binh của Hoàng Xuân Hãn và để giới thiệu một  phương pháp giải sử dụng khái niệm hệ phương trình đồng dư – và tiếp đó suy rộng để giải bài toán tổng quát, hay là định lý số dư Trung hoa,-

-          Ở phần cuối trình bày sơ qua về định lý nhỏ Fermat và áp dụng định lý trong việc chứng minh tính đúng đắn của thuật toán ngược RSA.

1.      Thuật toán ngược trong một hệ mã bất đối xứng.

Trong một hệ mã bất đối xứng, có hai thuật toán: Thuật toán lập mã E và thuật toán giải mã D, thực chất là 2 thuật toán ngược nhau:        D = E^-1

Nhưng nếu như thuật toán ngược có thể suy từ thuật toán thuận một cách đơn giản thì khi biết được thuật toán lập mã E do A gửi công khai cho B. kẻ đứng giữa -  man-in-the-midle  C có thể tự tìm được thuật toán ngược của E là D: tính bảo mật của thông điệp đã mã hóa không còn nữa.

Chẳng hạn :     Phép cộng với số E có phép toán ngược là phép trừ cho E:  D = -E

Phép nhân với E có phép toán ngược là phép chia cho E:  D = E^-1

Phép lũy thừa với số mũ E: e^E  có thuật toán ngược là e ^{–E, …}

đều là những thuật toán ngược hoàn toàn dễ tìm được nếu biết thuật toán thuận.

Năm 1976, Whitfield Diffie và Martin Hellman công bố một hệ thống mật mã hóa khóa bất đối xứng trong đó nêu ra phương pháp trao đổi khóa công khai. Công trình này chịu ảnh hưởng từ kết quả của Ralph Merkle có tên là hệ thống câu đố Merkle. Mật mã Diffie-Hellman là phương pháp phân phối khóa đầu tiên thông qua kênh thông tin không an toàn.

Thuật toán của RSA được tìm ra  vào năm 1977 tại MIT và được công bố vào năm 1978 . RSA sử dụng phép toán tính hàm mũ modulo n (modulo n là tích số của 2 số nguyên tố khá lớn) để mã hóa và giải mã cũng như tạo chữ ký số.

Việc giải các hệ phương trình đồng dư để tìm các tham số của khóa lập mã – công khai – và khóa giải mã – bí mật - có độ phức tạp rất cao. các tác giả của RSA đã tính được độ phức tạp của các thuật toán:   *Khóa công khai       = O(k²) bước tính toán.

  *Khóa riêng              = O(k³),

  *Tổng quát khóa      = O(k⁴) – k là số bit của modulo n

Nếu n bậc khoảng 10³ thì số bước tính toán tổng quát của thuật toán RSA lên đến trên bậc 10^24.

Do đó khả năng thám mã bằng cách giải các phương trình đồng dư để tìm số mũ giải mã D khi đã biết số mũ lập mã E là không khả thi trong thời gian thực.

An toàn của thuật toán còn  được đảm bảo hơn là do không tồn tại kỹ thuật hiệu quả để phân tích nhanh một số rất lớn n thành các thừa số nguyên tố p và q.

2.      Câu chuyện cổ (Truyền thuyết)

Hán Cao Tổ - Lưu Bang (người khởi đầu triều Hán ở Trung quốc) khởi nghĩa đánh nhà Tần. Quân đội thời  đó thường phiên chế thành đơn vị là Bách phu đội – đơn vị khoảng trên dưới 100 quân, và rồi đến cấp Thiên phu đội – thường gồm khoảng 10 bách phu đội, xấp xỉ 1000 quân.

Để đỡ khó khăn cho cấp dưới, Hàn Tín đưa ra một thuật toán đếm quân như sau:

-          Đơn vị trưởng đứng ngay cổng doanh trại, quân lính nắm tay nhau mỗi tổ 3 người đi vào, không quan tâm là có mấy nhóm, chỉ cần biết số dư cuối cùng chẳng hạn là a người. Lại cho nắm tay nhau mỗi tổ 5 người đi ra, còn dư b người. Cuối cùng nắm tay nhau mỗi tổ 7 người đi vào, còn dư c người. Biết a, b, c thì tính ngay được số người chính xác của đơn vị theo “qui tắc Hàn Tín” được ghi nhớ dễ dàng trong bài thơ sau đây. (Bài thơ này do Trịnh Đại Vỹ ghi lại, Hoàng Xuân Hãn dịch ra tiếng Việt).

-          Tam (3) nhân đồng hành, thất thập (70) hi

Ngũ (5) thụ mai hoa , trấp nhất (21) chi

Thất (7) tử đoàn viên chính bán nguyệt (15)

Trừ bách linh ngũ105) tiện đắc tri (Dị bản  Trừ bách linh ngũ định vi kỳ)
Dịch nghĩa: Trong 3 người cùng đi, hiếm có người 70 tuổi. 5 cây hoa mai có 21 cành.7 đúa con sum vầy vào ngày rằm (15). Trừ đi 105 thì biết con số.

Bản dịch của Hoàng Xuân Hãn:         Ba người cùng đi hiếm bẩy mươi

                                                       Năm cây mai hoa hăm mốt cành

            Bẩy trẻ xum vầy đúng nửa tháng.

  Trừ trăm linh năm biết số thành

Nên nhớ rằng “bài thơ”  này  chỉ có dạng một câu “khẩu quyết” mục đích giúp người ta dễ nhớ mấy con số quan trọng: 3 và 70, 5 và 21, 7 và 15, cuối cùng là số 105, không cần để ý đến nội dung ý nghĩa cụ thể của bài thơ!

Bài toán trên có thể được phát biểu  theo ngôn ngữ toán học hiện đại như sau:

·         Một đơn vị quân đội quân số chính xác là X, nếu chia cho 3 (tập hợp 3 hàng dọc) thì số dư là a, chia cho 5 (tập hợp 5 hàng dọc) thì số dư là b, chia cho 7 (tập hợp 7 hàng dọc) thì số dư là c.Tính X khi biết a, b, c.

·         Một điều rất quan trọng là phải biết ước lượng xem đơn vị quân đội đó là loại nào,:

Nếu là đơn vị bách phu thì X phải thỏa mãn điều kiện chẳng hạn là:     100 ≤ X ≤  200   (1)

-          Nếu là đơn vị thiên phu thì điều kiện chẳng hạn là                       900 ≤ X ≤  1100  (2)

·         Ý nghĩa của công thức Hàn Tín là: “ Lấy a (số dư khi chia cho 3) nhân với 70 cộng với b (số dư khi chia cho 5) nhân với 21, cộng với c (số dư khi chia cho 7 nhân voái 15), đem trừ đi một bội số của 105 (sao các cho điều kiện được thỏa mãn).

·         Ta có công thức :                                X = 70a + 21b + 15c - k 105,

trong đó k là số nguyên âm, dương chọn để đáp số thỏa mãn điều kiện (1) hoặc (2)

Xét một thí dụ cụ thể: Một bách phu cỡ 100 – 200 quân đi chiến đấu về, muốn điểm xem còn lại quân số đúng bao nhiêu? Giả sử số quân còn lại là 124, vậy thì chia cho 3 có a = 1, chia cho 5 có b = 4, chia cho 7 có c = 5. Áp dụng công thức Hàn Tin:    

X = (1 x 70) + (4 x 21) + (5 x15) – k 105 = 229 - k 105.

Nếu chọn k là số nguyên âm hoặc bằng 0 thì giá trị của X vượt quá 200: loại

Chọn k = 1 thì X = 229 – 105 = 124, thỏa mãn điều kiện: 100 ≤ X ≤  200

Nếu chọn k là số nguyên lớn hơn 1 thì giá trị của X bé hơn 100 : loại

Vậy đáp số đúng duy nhất chính là X = 124.

3.Chứng minh “qui tắc Hàn Tín điểm binh”.

Qui tắc Hàn Tín chính xác và sử dụng khá đơn giản, và khá bất ngờ, nhưng cũng như nhiều thành quả toán học cổ khác, các tác giả chỉ lưu lại kết quả mà không có chứng minh!

Bài toán này có thể qui về việc tìm nghiệm nguyên dương của một hệ phương trình gồm 3 phương trình, 4 ẩn số như sau: Tìm nghiệm nguyên, dương của hệ phương trình sau đây, thỏa mãn điều kiện (1) hoặc (2):     X = 3A + a

X = 5B + b

X = 7C + c

Trong đó X, m, n, p đều là ẩn số còn a, b, c là số đã biết.

Tuy nhiên, các bạn có thể thử để thấy ngay rằng việc sử dụng phương pháp thông thường giải hệ 3 phương trình vô định, 4 ẩn số là rất khó khăn!

Cách chứng minh của Hoàng Xuân Hãn:  Ta có hệ phương trình, trong đó A, B, C là số nguyên không âm:                                 X  = 3A + a
                                                X  = 5B + b
                                                X  = 7C + c

 Nhân hai vế đẳng thức đầu với 5.7.m (35m) ; được             35.m.\X = 105.m.A + 35.m.a.

Nhân hai vế của đẳng thức thứ hai với 3.7.n (21n); được:       21.n.X  = 105.n.B + 21.n.b

Nhân hai vế của đẳng thức thứ ba với 3.5.p (15p)  ; được:       15.p.X = 105.p.C + 15pc

Trong đó m, n, p là những số nguyên bất kỳ.

Cộng 3 đẳng thức mới ta được

        (35m + 21n + 15p)X = 105(mA + nB + pC) + 35ma + 21nb + 15pc             (3)

Ta sẽ tìm ba số nguyên m, n. p nghiệm đẳng thức sau này:

        35m + 21n + 15p = 105k + 1                                                                          (4) 

(Chỗ này Hoàng Xuân Hãn không giải thích tại sao phải có đẳng thức (4) ( ?)

Ta viết lại (4) như sau:                                    35m – 1 = 3(35k – 7n – 5p)                (4’)

Đẳng thức này chứng tỏ là vế đầu chia hết cho 3 .  Ví dụ lấy m là 2 thì có

35.2   -  1 = 3D, ở đây đặt :     D là một số nguyên nào đó.

Trừ hai đẳng thức trên, ta sẽ thấy:      35(m – 2) = 3D’, trong đó D’ = 35k – 7n – 5p - D

Vế thứ hai của đẳng thức này chia hết cho 3, nhưng ở vế đầu số 35 không chia  hết cho 3. Vậy  phải có m – 2 chia hết cho 3 .

 Ta đặt             m – 2 = 3M hay m =  2 + 3M , ở đây M là một số nguyên nào đó.

Tương tự ta tìm được   n = 1 + 5N   và    p = 1 + 7P, N và P cũng là những số nguyên nào đó

Làm như thế, ta tìm được vô số m, n, p nghiệm đẳng thức (2).

 Nếu chọn M = N = P = 0, ta được ba số  gọn nhất là:       m = 2,  n = 1, p = 1   .

 Thay chúng vào đẳng thức (1) ta sẽ được:   (105 + 1) X = 105 (2A + B + C) + 70a + 21b + 15c

Hay là, nếu đặt T = 2A + B + C thì ta được:   X = 105 T + (70a + 21b + 15c).

Vậy X bằng 70a + 21b + 15c rồi thêm bớt một bội số của 105

Chính là  quy tắc “ Hàn Tín điểm binh”

Chứng minh bằng cách sử dụng đồng dư thức: Chính xác hơn về mặt toán học (nhất là trong trường hợp tổng quát) người ta phải sử dụng phương pháp tìm nghiệm nguyên của một hệ phương trình đồng dư theo các modulo đôi một nguyên tố cùng nhau – đây là một kiến thức không hoàn toàn dễ hiểu ngay đối với sinh viên chuyên ngành Toán học

-           Định nghĩa: Ta gọi 2 số nguyên s, s’ là đồng dư theo modulo k,

ký hiệu là s  ≡  s’mod(k) nếu khi chia s và s’ cho k ta được cùng một số dư hay nói cách khác: s - s’ chia hết cho k  Suy ra:         Nếu     u          ≡  u’mod(k), và v  ≡  v’mod(k)

thì                                                        (u + v) ≡  (u’ + v’)mod(k) ; u.v  ≡  u’.v’mod(k) 

Trở lại chứng minh quy tắc Hàn Tín của Hoàng Xuân Hãn ở phần trên đây (giải thích tại sao có đẳng thức (4)).Từ dẳng thức :

(35m + 21n + 15p).X = 105k + (35ma + 21nb + 15pc)          (3)

Ký hiệu u = 35m + 21n +15pc , v = 35ma + 21nb + 15pc, thì đẳng thức (1) được viết thành:

                                                                                    u X  ≡  vmod(105)                  (5).

Nếu tìm đựơc các số nguyên m, n, p sao cho :           u      ≡  1mod(105)                  (6)

thì X có thể viết thành:                                               X     ≡  v.mod(105)

Tìm m, n, p thỏa mãn (3) như sau:                               u     = 35m + 21n + 15p = 1 + 105k

hoặc                                         35m - 1 = 105k -21n - 15p                                          (7)

Vế phải của (4) chia hết cho 3 nên vế trái cũng chia hết cho 3. Dễ dàng tìm được m = 2 là số nguyên dương nhỏ nhất để (35m - 1) chia hết cho 3

Tương tự ta tìm được n = 1, p = 1 là các số nguyên dương nhỏ nhất thỏa mãn (7).

Vậy :                                       X = 105k + (70a + 21b + 15p)

3.      Bài toán tổng quát:

Có thể phát biểu bài toán tổng quát như sau:

Tìm số nguyên X là nghiệm của hệ n phương trình đồng dư (X có thể có điều kiện ràng buộc nào đó để tìm nghiệm duy nhất):

            X  ≡ a₁ mod(m₁)

            X  ≡ a₂ mod(m₂)

            ……

            X  ≡  a_r mod(m_r)

Trong đó m_j là những số nguyên đôi một nguyên tố cùng nhau, còn a_j (các số dư) là những số nguyên không âm, a_j < m_j.

·         Định lý số dư Trung hoa:

Nếu các số m₁, m₂, ..., m_r là đôi một nguyên tố cùng nhau thì hệ phương trình đồng dư trên đây :                                       X ≡ a_i (mod m_i) với 1 ≤ i ≤ r,

có nghiệm duy nhất theo modulo M = M = m₁× m₂× ... × m_r

được biểu thị bằng công thức:                       

X ≡ a₁M₁y₁ + a₂M₂y₂ + ... + a_rM_ry_r (mod M),

trong đó:  M_i = M/m_i  còn:  y_i≡ (M_i)-1 (mod m) với 1 ≤ i ≤ r

4.      Phép toán ngược trong vành đồng dư và mã RSA.

Cơ sở toán học của hệ mã bất đối xứng RSA, là tìm cách một cặp biến đổi ngược trong vành modulo n. người ta ta chọn 2 số nguyên tố bất kỳ P và Q khá lớn (lớn hơn 1024) - (P và Q không công bố) gọi n = P.Q là modulo mã hóa và 2 số nguyên E và D, khóa lập mã công khai được công bố là (E,n) và khóa giải mã giữ bí mật là (D,n).

Mã hóa thông điệp gốc (số) M :          C   =  E (M) ≡  M^E (modn)

Tiếp đó giải mã ta lại có:                     M   =  D(C)   ≡  C^D (modn)

Ta phải chọn E và D sao cho:             M   ≡  C (modn) ≡ [M^E(modn)]^D(modn) ≡ M ^ED(modn)

Tức là phải có đẳng thức đồng dư:     ED ≡ 1(modn)                                                (8)

Như vậy muốn cho (n,E) và (n,D) là một cặp biến đổi ngược trong vành modulo thì giữa D và E phải thỏa mãn phương trình đồng dư (8)

Trong khi đó trong thuật toán RSA người ta đã sử dụng D được tính bới công thức:

                                                            E.D    ≡  1 mod[(p-1)(q-1)]                            (9)

Vậy giữa 2 công thức (8) và (9) có mối liên quan như thế nào?

Điều này được chứng minh bằng cách sử dụng một hệ quả của định lý nhỏ Fermat

.  Định lý nhỏ của Fermat.  Đưa vào khái niệm hàm thương chức năng Euler ф(n) – Euler totient function - của  số nguyên n:  ф(n) là số các số nguyên dương nhỏ hơn n, nguyên tố cùng nhau với n. Phát biểu định lý:

Nếu p là một số nguyên tố thì với mọi cố nguyên n, hiệu số n^p –n đều là bội số của p hay nói khác đi:                                       n^p        ≡ n (modp)                                          10)

Chẳng hạn thử lại: nếu n = 2 và p = 7, thì 2⁷ = 128, và 128 − 2 = 126 = 7 × 18 một bội số của 7.

Nếu n lại không chia hết cho p thì khi đó n ^(p-1) – 1 lại là một bội số của p hay:

                                                            n^(p-1)    ≡ 1 (modp)                                          (11)

Thử lại: Nếu n = 2 và p = 7 thì 2⁶ = 64 và 64 − 1 = 63 là bội số của 7.

. Tính đúng đắn của phép lập mã và giải mã trong RSA:  Nếu ф(n)   là hàm thương Euler và   p, q là nguyên tố thì rõ ràng là :              ф(p)     =   p -1 và ф(q)     =  q -1

Nếu     n = p.q,            p và q nguyên tố thì:  ф(n)     =   ф(p).ф(q)         = (p-1)(q-1)

                                                                                    =   n – (p+q) + 1

Do tính chất này, hệ thức:                  E.D      ≡  1 (mod ф(n))

tương đương với:                                E.D      =  k ф(n) + 1  ≡ 1 mod[(p-1)(q-1)]    (12)

Ta cần chứng minh:                             M         = M^E.D ≡ M^{k ф(n) + 1} (modn)                             (13)

Sử dụng Định lý Fermat – Euler trong Lý thuyết số: Với mọi cặp số nguyên M và n nguyên tố, ta đều có đẳng thức:                                    M ^ф(n)   ≡ 1 (modn)                                         

Đẳng thức (6) trở thành đẳng thức theo modulo n:

                                                            M = [M ^ф(n)]^K. M = 1^K.M = M                       (14)

Tài liệu tham khảo:

[1]   Hoàng Xuân Hãn - Toàn tập – Tri Tri – Hà Nội 1944

[2]   Tứ Hải  - Tập san Hội Trí Tri - Hà Nội 1943

[3]   Toán học từ điển- Tập san Hội Đồng Nghiên Cứu Khoa Học Đông Dương - Hà Nội-1943-1944

[4]   Thái Thanh Sơn - Bài toán Hàn Tín Điểm binh - Học suốt đời - Lifelong learning - Blogger

vitayson12.blogspot.com/2014/12/bai-toan-han-tin-iem-binh.html

[5]   Phương trình đồng dư một ẩn –

ttps://websrv1.ctu.edu.vn/coursewares/supham/sohoc/sohoc_6-2.htm

[6]  Thái Thanh Tùng – Mật mã học và hệ thống thông tin an toàn -NXB Thông tin & TT, 2011

 [7]  Evgeny Milanov – The RSA algorithm- June/03/2009         https://www.math.washington.edu/~morrow/336_09/papers/Yevgeny.pdf

[8]   Applications of the Chinese remainder theorem - http://mathoverflow.net/

[9]   The Chinese remainder theorem - http://nrich.maths.org/5466

[10] Fermat’s last theorem.           

http://fermatslasttheorem.blogspot.com/2005/08/fermats-little-theorem.html