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
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: eE 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(k2) bước
tính toán.
*Khóa riêng =
O(k3),
*Tổng quát khóa = O(k4) – k là số bit của modulo n
Nếu n bậc khoảng 103
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 1024.
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
≡ a1 mod(m1)
X ≡ a2 mod(m2)
……
X
≡ ar mod(mr)
Trong đó mj là
những số nguyên đôi một nguyên tố cùng nhau, còn aj (các số dư) là
những số nguyên không âm, aj < mj.
·
Định
lý số dư Trung hoa:
Nếu các số m1,
m2, ..., mr là đôi một nguyên tố cùng nhau thì hệ phương
trình đồng dư trên đây : X ≡ ai (mod mi) với 1 ≤ i ≤ r,
có nghiệm duy nhất theo
modulo M = M = m1× m2× ... × mr
được biểu thị bằng công
thức:
X
≡ a1M1y1 + a2M2y2
+ ... + arMryr (mod M),
trong đó: Mi = M/mi còn: yi≡
(Mi)-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) ≡
ME (modn)
Tiếp đó giải mã ta lại có: M = D(C)
≡ CD (modn)
Ta phải chọn E và D sao cho: M
≡ C (modn) ≡
[ME(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ố np
–n đều là bội số của p hay nói khác đi: np ≡ n (modp) 10)
Chẳng
hạn thử lại: nếu n = 2 và p = 7, thì 27 = 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ì 26 = 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 = ME.D
≡ Mk ф(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 = 1K.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
[10] Fermat’s last
theorem.
http://fermatslasttheorem.blogspot.com/2005/08/fermats-little-theorem.html
Updated for February 2018
