Bài giảng Cơ sở lý thuyết mật mã - Chương III: Mật mã khoá công khai - Hoàng Thu Phương

Hoàng Thu Phương - Khoa ATTT1
Hoàng Thu Phương - Khoa ATTT2
Chương 3. Mật mã khoá công khai
Hoàng Thu Phương - Khoa ATTT3
Nội dung chính
1. Giới thiệu
2. Một số kiến thức toán học
3. Một số hệ mật khoá công khai
Hoàng Thu Phương - Khoa ATTT4
1. Giới thiệu
 Trong hệ mật khóa đối xứng thì khóa phải được 
chia sẻ giữa hai bên trên một kênh an toàn trước khi 
gửi một bản mã bất kì. Trên thực tế điều này rất khó 
đảm bảo.
 Ý tưởng về một hệ mật khoá công khai được Diffie 
và Hellman đưa ra vào năm 1976 
 Rivesrt, Shamir và Adleman hiện thực hóa ý tưởng 
trên vào năm 1977, họ đã tạo nên hệ mật nổi tiếng 
RSA..
Hoàng Thu Phương - Khoa ATTT5
1. Giới thiệu
 Đặc điểm của hệ mật KCK:
– Mỗi bên có một khoá công khai và một khoá bí mật.
- Bên gửi dùng khoá công khai của bên nhận để mã hoá.
- Bên nhận dùng khoá bí mật của mình để giải mã.
Hoàng Thu Phương - Khoa ATTT6
1. Giới thiệu
 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 xếp ba lô Merkle - Hellman:
– Hệ này và các hệ liên quan dựa trên tính khó giải của 
bài toán tổng các tập con (bài toán này là bài toán NP 
đầy đủ).
Hoàng Thu Phương - Khoa ATTT7
1. Giới thiệu
 Hệ mật McEliece:
– Hệ này dựa trên lý thuyết mã đại số và vẫn còn được 
coi là an toàn. Hệ mật McEliece dựa trên bài toán giải 
mã cho các mã tuyến tính (cũng là một bài toán NP đầy 
đủ) 
 Hệ mật ElGamal:
– Hệ mật ElGamal dựa trên tính khó giải của bài toán 
logarithm rời rạc trên các trường hữu hạn
Hoàng Thu Phương - Khoa ATTT8
1. Giới thiệu
 Hệ mật Chor-Rivest:
– Hệ mật Chor-Rivest cũng được xem như 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 các đường cong Elliptic:
– Các hệ mật này là biến tướng của các hệ mật khác 
(chẳng hạn như hệ mật ElGamal), chúng làm việc trên 
các đường cong Elliptic chứ không phải là trên các 
trường hữu hạn. Hệ mật này đảm bảo độ mật với số 
khoá nhỏ hơn các hệ mật khoá công khai khác.
Hoàng Thu Phương - Khoa ATTT9
1. Giới thiệu
 Một chú ý quan trọng là một hệ mật khoá công 
khai không bao giờ có thể đảm bảo được độ mật 
tuyệt đối (an toàn vô điều kiện). 
 Ta chỉ nghiên cứu độ mật về mặt tính toán của các 
hệ mật này.
Hoàng Thu Phương - Khoa ATTT10
1. Giới thiệu
 Một số khái niệm trong hệ mật KCK:
– Đặc tính một chiều: Hàm mã khoá công khai ek của 
Bob phải là một hàm dễ tính toán. Song việc tìm hàm 
ngược (hàm giải mã) rất khó khăn (đối với bất kỳ ai 
không phải là Bob)
 Ví dụ: Giả sử n là tích của hai số nguyên tố lớn p và q, giả sử 
b là một số nguyên dương. Khi đó hàm f(x) = xb mod n là một 
hàm một chiều.
– Hàm cửa sập một chiều: thông tin bí mật cho phép 
Bob dễ dàng tìm hàm của ek. 
Hoàng Thu Phương - Khoa ATTT11
2. Một số kiến thức toán học
 Cấu trúc đại số
 Số học modulo
Hoàng Thu Phương - Khoa ATTT12
 Cấu trúc đại số:
– Định nghĩa nhóm. Tập hợp G đó với phép toán . đã 
cho được gọi là nhóm, nếu nó thỏa mãn các tính chất 
sau với mọi phần tử a, b, c thuộc G:
 Tính kết hợp (a.b).c = a.(b.c)
 Có đơn vị e: e.a = a.e = a
 Có nghịch đảo a-1: a.a-1 = e
 Nếu có thêm tính giao hoán a.b = b.a, thì gọi là nhóm Aben 
hay nhóm giao hoán.
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT13
2. Một số kiến thức toán học
– Định nghĩa nhóm xyclic. 
 Định nghĩa lũy thừa như là việc áp dụng lặp phép toán:
Ví dụ: a3 = a.a.a
 Và đơn vị e=a0
 Một nhóm được gọi là xyclic nếu mọi phần tử đều là lũy thừa 
của một phần tử cố định nào đó. Chẳng hạn b = ak đối với a 
cố định và mỗi b trong nhóm. Khi đó a được gọi là phần tử 
sinh của nhóm.
Hoàng Thu Phương - Khoa ATTT14
2. Một số kiến thức toán học
– Vành: Cho một tập R các “số” với hai phép toán được gọi là cộng và 
nhân. Ở đây “số” được hiểu là phần tử của tập hợp và hai phép toán 
trên xác định trên tập hợp đó. Tập với hai phép toán trên được gọi là 
vành, nếu hai phép toán thoả mãn các tính chất sau:
 Với phép cộng, R là nhóm Aben
 Với phép nhân, có:
– tính đóng và 
– tính kết hợp
– tính phân phối đối với phép cộng a(b+c) = ab + ac
 Nếu phép nhân có tính giao hoán thì tạo thành vành giao hoán.
 Nếu phép nhân có nghịch đảo và không có thương 0 (tức là không có hai 
phần khác 0 mà tích của chúng lại bằng 0), thì nó tạo thành miền nguyên
Hoàng Thu Phương - Khoa ATTT15
2. Một số kiến thức toán học
– Trường là một tập hợp F với hai phép toán cộng và nhân, thoả mãn tính chất 
sau: 
 Với phép cộng F là nhóm Aben
 Với phép nhân F trừ phần tử 0 là nhóm Aben.
 F là một vành
Có thể nói là có các phép toán cộng, trừ, nhân, chia số khác 0. Phép trừ được coi 
như là cộng với số đối của phép cộng và phép chia là nhân với số đối của phép 
nhân:
a– b = a + (-b) 
a / b = a.b-1
– Ví dụ: Dễ dàng thấy, với phép cộng và nhân thông thường:
 Tập số nguyên Z là nhóm Aben với phép cộng
 Tập số nguyên Z là vành giao hoán.
 Tập số hữu tỉ Q là trường.
 Tập số thực R là trường.
 Tập số phức C là trường với phép cộng và nhân hai số phức.
Hoàng Thu Phương - Khoa ATTT16
2. Một số kiến thức toán học
 Số học modulo
– Cho số tự nhiên n và số nguyên a. Ta định nghĩa: a 
mod n là phần dư dương khi chia a cho n.
– Định nghĩa quan hệ tương đương trên tập số nguyên 
a ≡ b mod n khi và chỉ khi a và b có phần dư như 
nhau khi chia cho n.
Hoàng Thu Phương - Khoa ATTT17
2. Một số kiến thức toán học
– Ví dụ: 100 mod 11 = 1; 34 mod 11 = 1, nên 100 ≡ 34 mod 11 
– Số b được gọi là đại diện của a, nếu a ≡ b mod n (a = qn + b) và
0 <= b < n.
– Ví dụ: -12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7. Ở đây 2 là đại diện 
của –12, -5, 2 và 9. 
– Trong Modulo 7 ta có các lớp tuơng đương viết trên các hàng như sau:
–
– Các phần tử cùng cột là có quan hệ đồng dư 
với nhau. 
– Tập các đại diện của các số nguyên theo 
Modulo n gồm n phần tử ký hiệu như sau:
Zn = { 0, 1, 2, 3, , n-1 }.
Hoàng Thu Phương - Khoa ATTT18
2. Một số kiến thức toán học
 Ước số 
– Số b không âm được gọi là ước số của a, nếu có số m 
sao cho: a = mb trong đó a, b, m đều nguyên.
– Tức là a chia hết cho b, ký hiệu là b|a 
– Ví dụ: 1, 2, 3, 4, 6, 8, 12, 24 là các ước số của 24
Hoàng Thu Phương - Khoa ATTT19
2. Một số kiến thức toán học
 Các phép toán số học trên Modulo
– Cho trước một số n. Ta muốn thực hiện các phép toán theo Modulo của 
n. Ta có thể thực hiện các phép toán trên các số nguyên như các phép 
cộng, nhân các số nguyên thông thường sau đó rút gọn lại bằng phép lấy 
Modulo hoặc cũng có thể vừa tính toán, kết hợp với rút gọn tại bất cứ 
thời điểm nào:
(a+b) mod n = [a mod n + b mod n] mod n (*)
(a.b) mod n = [a mod n . b mod n] mod n (**)
– Như vậy khi thực hiện các phép toán ta có thể thay các số bằng các số 
tương đương theo Modulo n đó hoặc đơn giản hơn có thể thực hiện các 
phép toán trên các đại diện của nó: Zn = { 0, 1, 2, 3, , n-1 }.
Hoàng Thu Phương - Khoa ATTT20
2. Một số kiến thức toán học
– Zn với các phép toán theo Modulo tạo thành vành giao hoán 
có đơn vị. Các tính chất kết hợp, giao hoán và nghịch đảo 
được suy ra từ các tính chất tương ứng của các số nguyên. 
– Các chú ý về tính chất rút gọn:
 Nếu (a+b)≡(a+c) mod n, thì b≡c mod n
 Nhưng (ab)≡(ac) mod n, thì b≡c mod n chỉ khi nếu a là nguyên tố 
cùng nhau với n
– Ví dụ: Tính (11*19 + 1017) mod 7 = ?
Hoàng Thu Phương - Khoa ATTT21
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT22
2. Một số kiến thức toán học
 Ví dụ: bảng modulo 8 với phép cộng
Hoàng Thu Phương - Khoa ATTT23
2. Một số kiến thức toán học
 Ước số chung lớn nhất.
– Bài toán: Cho hai số nguyên dương a và b. Bài toán tìm 
ước chung lớn nhất của hai số nguyên dương là bài toán 
chung của lý thuyết số. Ta ký hiệu GCD(a,b) là ước số 
chung dương lớn nhất của a và b, tức là số nguyên dương 
vừa là ước của a vừa là ước của b và là số nguyên dương 
lớn nhất có tính chất đó. 
– Ví dụ: GCD(60,24) = 12 ; GCD (6, 15) = 3; 
GCD(8, 21) = 1.
Hoàng Thu Phương - Khoa ATTT24
2. Một số kiến thức toán học
 Nguyên tố cùng nhau: Ta thấy 1 bao giờ cũng là 
ước số chung của hai số nguyên dương bất kỳ. Nếu 
GCD(a, b) = 1, thì a, b đựơc gọi là hai số nguyên 
tố cùng nhau:
– Ví dụ: GCD(8,15) = 1, tức là 8 v à 15 là hai số nguyên 
tố cùng nhau
Hoàng Thu Phương - Khoa ATTT25
2. Một số kiến thức toán học
 Tìm ước chung lớn nhất. Bây giờ chúng ta xét bài toán 
tìm ước số chung lớn nhất của hai số nguyên dương cho 
trước. Dễ dàng chứng minh được tính chất sau:
GCD(a,b) = GCD(b, a mod b) 
 Như vậy để tìm ước số chung của một cặp số cho trước, ta 
đưa về bài toán tìm ước chung của cặp số gồm số nhỏ hơn 
trong hai số đó và phần dư của số lớn khi chia cho số nhỏ 
hơn. Thuật toán Ơcơlít tạo nên vòng lặp, ở mỗi bước ta áp 
dụng tính chất trên cho đến khi phần dư đó còn khác 0. 
Hoàng Thu Phương - Khoa ATTT26
2. Một số kiến thức toán học
 Thuật toán Ơcơlit tìm GCD(a, b)
A=a, B=b
while B>0
R = A mod B
A = B, B = R
return A
Hoàng Thu Phương - Khoa ATTT27
2. Một số kiến thức toán học
 Ví dụ: GCD(1970,1066)
1970 = 1 x 1066 + 904 gcd(1066, 904)
1066 = 1 x 904 + 162 gcd(904, 162)
904 = 5 x 162 + 94 gcd(162, 94)
162 = 1 x 94 + 68 gcd(94, 68)
94 = 1 x 68 + 26 gcd(68, 26)
68 = 2 x 26 + 16 gcd(26, 16)
26 = 1 x 16 + 10 gcd(16, 10)
16 = 1 x 10 + 6 gcd(10, 6)
10 = 1 x 6 + 4 gcd(6, 4)
6 = 1 x 4 + 2 gcd(4, 2)
4 = 2 x 2 + 0 
gcd(1970, 1066) = 2
Hoàng Thu Phương - Khoa ATTT28
2. Một số kiến thức toán học
 Trường Galoa
– Ta muốn đi tìm một trường số có hữu hạn các phần tử, 
tức là một tập hữu hạn các phần tử mà ở đó có thể cộng 
trừ, nhân, chia mà không vượt ra ngoài phạm vi tập hữu 
hạn các phần tử đó. Trường Galoa thuộc lọai đó và đóng 
vai trò quan trọng trong lý thuyết mã. 
– Có thể chứng minh được rằng số các phần tử của trường 
hữu hạn bất kỳ bằng lũy thừa của pm của sô nguyên tố p 
nào đó, ta ký hiệu trường Galoa đó là GL(pm). Thông 
thường ta sử dụng các trường: GL(p) và GL(2m).Sau đây 
chúng ta sẽ xây dựng các trường Galoa đó. 
Hoàng Thu Phương - Khoa ATTT29
2. Một số kiến thức toán học
 Trường Galoa GL(p), với p là số nguyên tố.
– GL(p) gồm tập {0,1,  , p-1}. 
– Với các phép toán cộng và nhân Modulo, như ta đã biết GL(p) tạo 
thành một vành giao hoán. Vì p là số nguyên tố nên mọi số khác 0 
nhỏ hơn p đều nguyên tố cùng nhau với p.
– GL(p) tạo thành trường vì mọi a thuộc {1,  , p-1} đều có phần 
tử nghịch đảo a-1: a . a-1 = 1. Thực vậy vì a và p nguyên tố cùng 
nhau nên theo thuật toán tìm nghịch đảo dưới đây ta sẽ tìm được 
nghịch đảo của a. 
– Như vậy trên GL(p) ta có thể thực hiện các phép toán cộng, trừ, 
nhân, chia.
Hoàng Thu Phương - Khoa ATTT30
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT31
2. Một số kiến thức toán học
 Tìm số nghịch đảo: Bây giờ ta xét bài toán: nếu GCD(m, b) = 1, thì tìm nghịch đảo của b 
theo Modulo m. Ta mở rộng thuật toán Ơcơlit vừa tìm ước chung lớn nhất của m và b, vừa 
tính nghịch đảo trong trường hợp GCD(m, b) = 1. 
 Thuật toán Euclid mở rộng: 
EXTENDED EUCLID(m, b)
1. (A1, A2, A3)=(1, 0, m); 
(B1, B2, B3)=(0, 1, b)
2. if B3 = 0
return A3 = gcd(m, b); no inverse
3. if B3 = 1 
return B3 = gcd(m, b); B2 = b–1 mod m
4. Q = A3 div B3
5. (T1,T2,T3)=(A1 – Q*B1,A2 – Q*B2, A3 – Q*B3)
6. (A1, A2, A3)=(B1, B2, B3)
7. (B1, B2, B3)=(T1, T2, T3)
8. goto 2
Hoàng Thu Phương - Khoa ATTT32
2. Một số kiến thức toán học
 Chứng minh tính đúng đắn của thuật toán Ơcơlit 
mở rộng.
 Áp dụng thuật toán mở rộng với các đầu vào: 
– b = 550; m = 1759
– b = 4864; m = 3458
Hoàng Thu Phương - Khoa ATTT33
2. Một số kiến thức toán học
 GCD(1759, 550) = 1 và 550-1 mod 1759 = 355
Hoàng Thu Phương - Khoa ATTT34
2. Một số kiến thức toán học
 Số học đa thức
– Ta xét tập các đa thức Pn có bậc nhỏ hơn hoặc bằng n:
f(x) = anx
n + an-1x
n-1 + + a1x + a0 = 
– Trên tập các đa thức đó ta có thể có một số cách khác 
nhau thực hiện các phép toán cộng và nhân đa thức

=
n
i
i
i xa
0
Hoàng Thu Phương - Khoa ATTT35
2. Một số kiến thức toán học
– Phép toán đa thức thông thường
 Cộng trừ các hệ số tương ứng
 Nhân mọi hệ số với cùng một số. 
– Ví dụ: f(x) = x3 + x2 + 2 và g(x) = x2 – x + 1
f(x) + g(x) = x3 + 2x2 – x + 3
f(x) – g(x) = x3 + x + 1
f(x) . g(x) = x5 + 3x2 – 2x + 2
Hoàng Thu Phương - Khoa ATTT36
2. Một số kiến thức toán học
– Phép toán đa thức với Modulo hệ số
 Cho số nguyên tố p tùy ý
 Tính các hệ số theo Modulo p. Khi đó tập các hệ số được lấy từ 
trường GL(p). Còn phép nhân đa thức có thể nhận được kết quả là đa 
thức bậc lớn hơn n. 
 Ta thường quan tâm đến Mod 2, tức là mọi hệ số là 0 hoặc 1 
– Ví dụ: f(x) = x3 + x2 và g(x) = x2 + x + 1
 f(x) + g(x) = x3 + x + 1
 f(x) . g(x) = x5 + x2
Hoàng Thu Phương - Khoa ATTT37
2. Một số kiến thức toán học
 Phép toán đa thức với Modulo đa thức
– Cho đa thức g(x) bậc n và các hệ số của các đa thức xét 
trong mục này lầy trong trường Galoa GF(p) với p là số 
nguyên tố. Viết đa thức f(x) dưới dạng: 
f(x) = q(x) g(x) + r(x)
trong đó r(x) là phần dư khi chia f(x) cho g(x). Rõ ràng bậc 
của r(x) sẽ nhỏ hơn bậc của g(x).Ta viết:
r(x) = f(x) mod g(x)
Hoàng Thu Phương - Khoa ATTT38
2. Một số kiến thức toán học
 Nếu không có phần dư, tức là r(x) = 0, ta nói g(x) là ước 
của f(x) hay g(x) chia hết f(x) hay f(x) chia hết cho g(x).
 Trong trường hợp g(x) không có ước ngoài 1 và chính nó, 
thì ta nói g(x) là đa thức nguyên tố hoặc không rút gọn 
được. Ví dụ g(x) = x3 + x + 1 là đa thức nguyên tố.
 Việc tìm ước chung lớn nhất của hai đa thức được trình 
bày trong thuật toán tương tự như Ơcolit như sau:
Hoàng Thu Phương - Khoa ATTT39
2. Một số kiến thức toán học
 Tìm đa thức ước chung lớn nhất GCD(a(x), b(x))
– c(x) = GCD(a(x), b(x)) nếu c(x) là đa thức bậc lớn nhất mà chia 
hết cả a(x), b(x)
– Có thể điều chỉnh thuật toán Euclid’s Algorithm để tìm nó:
EUCLID[a(x), b(x)]
1. A(x) = a(x); B(x) = b(x)
2. if B(x) = 0 return A(x) = gcd[a(x), b(x)]
3. R(x) = A(x) mod B(x)
4. A(x) ¨ B(x)
5. B(x) ¨ R(x)
6. goto 2
Hoàng Thu Phương - Khoa ATTT40
2. Một số kiến thức toán học
 Phép toán đa thức với Modulo đa thức.
– Cho g(x) là đa thức nguyên tố bậc n. Khi đó tập các đa 
thức bậc nhỏ hơn bằng n với các phép toán cộng và 
nhân đa thức theo Modulo của đa thức nguyên tố g(x) 
tạo thành trường hữu hạn, gọi là trường Galoa và ký 
hiệu là GL(pn). 
– Sau đây ta xét trường GF(2n), tức là xét tập các đa thức 
với các hệ số Modulo 2 và bậc nhỏ hơn bằng n và phép 
toán nhân có thể rút gọn theo Modulo của đa thức g(x) 
nguyên tố bậc n
Hoàng Thu Phương - Khoa ATTT41
2. Một số kiến thức toán học
Ví dụ GF(23)
Hoàng Thu Phương - Khoa ATTT42
2. Một số kiến thức toán học
 Ví dụ: Trong GF(23) ta có (x2+1) tương ứng dãy bít 1012
và (x2+x+1) tương ứng với dãy 1112
 Tổng hai đa thức trên là
– (x2+1) + (x2+x+1) = x 
– 101 XOR 111 = 0102
 Tích của hai đa thức là 
– (x+1).(x2+1) = x.(x2+1) + 1.(x2+1) = x3+x+x2+1 = x3+x2+x+1
– 011.101 = (101)<<1 XOR (101)<<0 = 1010 XOR 101 = 11112
Hoàng Thu Phương - Khoa ATTT43
2. Một số kiến thức toán học
 Phép rút gọn theo Modulo là:
– (x3+x2+x+1 ) mod (x3+x+1) = (x3+x2+x+1 ) - (x3+x+1 ) 
= x2
– 1111 mod 1011 = 1111 XOR 1011 = 01002
 Như ... 
nmodax
........................
nmodax
nmodax



Hoàng Thu Phương - Khoa ATTT62
2. Một số kiến thức toán học
 Có thể triển khai Định lý Trung Hoa theo một số 
cách như sau:
– 1. Tính toán theo modulo số lớn:
 Để tính A mod M, với M (M= m1m2..mk) khá lớn và A là biểu 
thức số học nào đó. Trước hết ta cần tính tất cả ai = A mod mi. 
Sau đó sử dụng công thức:
Trong đó: Mi = M/mi
 Áp dụng tính ví dụ: 178 mod 77?
McaA
k
i
ii mod
1
= 
=
( ) kimMMc iiii = 1;mod1
Hoàng Thu Phương - Khoa ATTT63
2. Một số kiến thức toán học
 Áp dụng định lý phần dư Trung hoa, ta coi A = 1718, m 1 = 7, 
m2 = 11. Khi đó M1 = 11, M2 = 7 và
– 11-1 mod 7 = 4-1 mod 7 = 2, suy ra c1 = 11*2 = 22;
– 7-1 mod 11 = 8, suy ra c2 = 7*8 = 56;
– 178 mod 7 = (17 mod 7)8 mod 7 = 38 mod 7 = (32)4 mod 7 = a1 = 2; 
– 178 mod 11 = (17 mod 11)8 mod 11 = 68 mod 11
= (62)4 mod 11 = 34 mod 11 = a2 = 4;
 Vậy 178 mod 77 = (2*22 + 4*56) mod 77
= 268 mod 77 = 37 mod 77 = A = 37;
Hoàng Thu Phương - Khoa ATTT64
2. Một số kiến thức toán học
– 2. Giải hệ phương trình modulo:
 Cho x = ai mod mi, với GCD(mi, mj) = 1, với mọi i khác 
j. Khi đó ta cũng áp dụng Định lý phần dư Trung Hoa để 
tìm x. 
 Áp dụng tính ví dụ:
– Tìm x với: 
Hoàng Thu Phương - Khoa ATTT65
2. Một số kiến thức toán học
 Áp dụng định lý phần dư Trung hoa, ta tính: 
– 7-1 mod 11 = 8 và 11-1 mod 7 = 2. Như vậy:
– x = (5*2*11 + 6*8*7) mod (7*11) = 61 mod 77. 
Hoàng Thu Phương - Khoa ATTT66
2. Một số kiến thức toán học
( ) ( )21 nmodax,nmodax 
).mod( 21 nn ax 
 Định lí: nếu (n1, n2) = 1 thì
có nghiệm duy nhất
Hoàng Thu Phương - Khoa ATTT67
2. Một số kiến thức toán học
 Căn nguyên tố
– Từ Định lý Ole ta có a(n)mod n=1, với a và n là nguyên 
tố cùng nhau. Nếu không có số mũ dương nào nhỏ hơn 
Ф(n), mà có tính chất như vậy đối với a, thì khi đó ta gọi 
a là căn nguyên tố của n. 
– Ví dụ:
 (a) Xét xem a = 2 có phải là căn nguyên tố của 5 không?
 (b) a = 3 có là căn nguyên tố của 8 không?
Hoàng Thu Phương - Khoa ATTT68
2. Một số kiến thức toán học
 (a) Ta có:
– 2 mod 5 = 2; 22mod 5 = 4; 23mod 5 = 3; 24mod 5 = 1.
– Rõ ràng m= 4= Ф(5) là số mũ dương nhỏ nhất có tính 
chất 2m mod 5 = 1, nên 2 là căn nguyên tố của 5. 
 (b) Ta có:
– 3 mod 8 = 3; 32 mod 8 = 1; 33mod 8 = 3; 34 mod 8 = 1
– Rõ ràng m= 2 < 4 = Ф(8) là số mũ dương nhỏ nhất có 
tính chất 3m mod 8 = 1, nên 3 không là căn nguyên tố 
của 8. 
Hoàng Thu Phương - Khoa ATTT69
2. Một số kiến thức toán học
 Logarit rời rạc
– Bài toán ngược của bài toán lũy thừa là tìm logarit rời rạc 
của một sô modulo p, tức là tìm số nguyên x sao cho: 
ax = b mod p. Hay còn được viết là x=logab mod p
– Nếu a là căn nguyên tố của p và p là số nguyên tố, thì 
luôn luôn tồn tại logarit rời rạc, ngược lại thì có thể 
không
– Ví dụ:
 Tìm x = log2 3 mod 13?
 Tìm x = log3 4 mod 13?
Hoàng Thu Phương - Khoa ATTT70
2. Một số kiến thức toán học
 Tìm x = log2 3 mod 13? (Hay: 2
x = 3 mod 13)
– 20 mod 13 = 1;
– 21 mod 13 = 2, 
– 22 mod 13 = 4, 
– 23 mod 13 = 8, 
– 24 mod 13 = 3. 
– Vậy log2 3 mod 13 = 4.
 Tìm x = log3 4 mod 13? (Hay 3
x = 4 mod 13)
– Trong trường hợp này không có lời giải, vì
– 30 mod 13 = 1;
– 31 mod 13 = 3; 
– 32 mod 13 = 9; 
– 33 mod 13 = 1= 30 mod 13 
Hoàng Thu Phương - Khoa ATTT71
2. Một số kiến thức toán học
 Ta nhận thấy, trong khi bài toán lũy thừa là dễ 
dàng, thì bài toán logarit rời rạc là rất khó. Đây 
cũng là một cơ sở của mã công khai
Hoàng Thu Phương - Khoa ATTT72
2. Một số kiến thức toán học
Định nghĩa nhóm nhân của Zn:
Với n nguyên tố thì Z*n = ?
( ) 1n,aZaZ n*n = =
Hoàng Thu Phương - Khoa ATTT73
2. Một số kiến thức toán học
Định lí: n nguyên tố:
- Định lí Euler: Nếu thì
- Nếu n là tích của các số nguyên khác nhau, và nếu 
thì
với mọi số nguyên a
( ) ( )nmod1a n *
nZa 
( )( )nmodsr  ( )nmodaa sr 
Hoàng Thu Phương - Khoa ATTT74
2. Một số kiến thức toán học
ĐN thặng dư bậc 2, thặng dư không bậc 2:
là thặng dư bậc 2 modulo n nếu tồn tại 
sao cho 
Nếu không tồn tại x như thế thì a được gọi là thặng 
dư không bậc 2 modulo n.
- là tập các thặng dư bậc 2 modulo n
- là tập các thặng dư không bậc 2 modulo n
*
nZa 
*
nZx ( )nmodax
2 
nQ
nQ
Hoàng Thu Phương - Khoa ATTT75
2. Một số kiến thức toán học
Định lí số các căn bậc 2: Cho
trong đó pi là các số nguyên tố lẻ phân biệt và 
. Nếu thì a có đúng 2k căn bậc 2 
khác nhau theo modulo n. 
k21 e
k
e
2
e
1 pppn =
1e i nQa 
Hoàng Thu Phương - Khoa ATTT76
2. Một số kiến thức toán học
 Lũy thừa
– Trong các bài toán mã hoá công khai, chúng ta sử dụng 
nhiều phép toán lũy thừa với số mũ lớn. Như vậy cần 
có thuật toán nhanh hiệu quả đối với phép toán này.
 Trước hết ta phân tích số mũ theo cơ số 2, xét biểu diễn nhị 
phân của số mũ
 Sau đó sử dụng thuật toán bình phương và nhân. Khái niệm 
được dựa trên phép lặp cơ sở bình phương và nhân để nhận 
đựơc kết quả mong muốn. 
Hoàng Thu Phương - Khoa ATTT77
2. Một số kiến thức toán học
 Thuật toán nhân bình phương có lặp để lấy lũy thừa trong Zn:
Hoàng Thu Phương - Khoa ATTT78
2. Một số kiến thức toán học
 Ví dụ: Tính 5596 mod 1234 =?
 Vậy 5596 mod 1234 = 1013
- Tính 968 mod 78=?
ik
i 0 1 2 3 4 5 6 7 8 9
ki 0 0 1 0 1 0 1 0 0 1
A 5 25 625 681 1011 369 421 779 947 925
b 1 1 625 625 67 67 1059 1059 1059 1013
Hoàng Thu Phương - Khoa ATTT79
2. Một số kiến thức toán học
 ĐN kí hiệu Legendre: p là một số nguyên tố lẻ, a 
là một số nguyên. Kí hiệu Legendre được xác 
định như sau:
 = 
p
p
Qa1
Qa1
ap0
p
a
Hoàng Thu Phương - Khoa ATTT80
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT81
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT82
2. Một số kiến thức toán học
ĐN kí hiệu Jacobi
Cho là một số nguyên lẻ có phân tích 
Khi đó kí hiệu Jacobi được định nghĩa là:
3n 
k21 e
k
e
2
e
1 pp.pn =
k21 e
k
e
2
e
1 p
a
p
a
p
a
n
a
= 

Hoàng Thu Phương - Khoa ATTT83
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT84
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT85
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT86
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT87
2. Một số kiến thức toán học
 Thuật toán (Tính toán ký hiệu Jacobi (và ký hiệu Legendre)
Hoàng Thu Phương - Khoa ATTT88
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT89
2. Một số kiến thức toán học
 Từ ví dụ ta thấy Q21={1,4,16}; thấy rằng nhưng 121
5
= 
21Q5 
Hoàng Thu Phương - Khoa ATTT90
2. Một số kiến thức toán học
Hoàng Thu Phương - Khoa ATTT91
2. Một số kiến thức toán học 
Số Blum n là số có dạng trong đó p, q là các số 
nguyên tố khác nhau thoả mãn:
Định lí: n là một số Blum, khi đó a có đúng 4 căn 
bậc 2 modulo n và chỉ có duy nhất một căn bậc 2 thuộc Qn
(căn bậc 2 chính a mod n)
q.pn =
4mod3q
4mod3p


nQa 
3. Một số hệ mật khoá công khai
 3.1 Hệ mật RSA
 3.2 Hệ mật Merkle – Hellman
 3.3 Hệ mật McEliece
 3.4 Hệ mật ElGamal
 3.5 Hệ mật Chor- Rivest
 3.6 Hệ mật trên đường cong Elliptic
3.1 Hệ mật RSA
 RSA là mã công khai được sáng tạo bởi Rivest, Shamir & Adleman ở 
MIT (Trường Đại học Công nghệ Massachusetts) vào năm 1977. 
 RSA là mã công khai được biết đến nhiều nhất và sử dụng rộng rãi 
nhất hiện nay.
 RSA dựa trên các phép toán lũy thừa trong trường hữu hạn các số 
nguyên theo modulo nguyên tố. Cụ thể, mã hoá hay giải mã là các 
phép toán luỹ thừa theo modulo số rất lớn. 
 Việc thám mã, tức là tìm khoá riêng khi biết khoá công khai, dựa trên 
bài toán khó là phân tích một số rất lớn đó ra thừa số nguyên tố. Nếu 
không có thông tin gì, thì ta phải lần lượt kiểm tra tính chia hết của số 
đó cho tất cả các số nguyên tố nhỏ hơn căn của nó. Đây là việc làm 
không khả thi!
3.1 Hệ mật RSA
 Người ta chứng minh được rằng, phép lũy thừa 
cần O((log n)3) phép toán, nên có thể coi lũy thừa 
là bài toán dễ. 
 Cần chú ý rằng ở đây ta sử dụng các số rất lớn 
khoảng 1024 bit, tức là cỡ 10350.
 Tính an toàn dựa vào độ khó của bài toán phân 
tích ra thừa số các số lớn. Bài toán phân tích ra 
thừa số yêu cầu O(elogn log logn) phép toán, đây là 
bài toán khó.
3.1 Hệ mật RSA
 Khởi tạo khoá RSA
– Mỗi người sử dụng tạo một cặp khoá công khai – riêng như sau:
 Chọn ngẫu nhiên 2 số nguyên tố lớn p và q
 Tính số làm modulo của hệ thống: N = p.q
– Ta đã biết Ф(N)=(p-1)(q-1) 
– Và có thể dùng Định lý Trung Hoa để giảm bớt tính toán
– Chọn ngẫu nhiên khoá mã e
– Trong đó 1<e< Ф(N), gcd(e,Ф(N))=1 
– Giải phương trình sau để tìm khoá giải mã d sao cho
– e.d=1 mod Ф(N) với 0≤d≤ Ф(N) 
– In khoá mã công khai KU={e,N} 
– Giữ khoá riêng bí mật KR={d,p,q} 
3.1 Hệ mật RSA
 Sử dụng RSA
– Để mã hoá mẩu tin, người gủi:
 Lấy khoá công khai của người nhận KU={e,N}
 Tính C=Me mod N, trong đó 0≤M<N
– Để giải mã hoá bản mã, người sở hữu nhận:
 Sử dụng khóa riêng KR={d,p,q} 
 Tính M=Cd mod N 
– Lưu ý rằng bản tin M < N, do đó khi cần chia khối bản 
rõ.
3.1 Hệ mật RSA
 Cơ sở của RSA
– Theo Định lý Ole
 a(n) mod N = 1 trong đó gcd(a,N)=1
 Ta có N=p.q
 Ф(N)=(p-1)(q-1) 
 e.d=1 mod Ф(N)
 e.d=1+k.Ф(N) đối với một giá trị k nào đó.
– Suy ra 
 Cd = (Me)d = M1+k.(N) = M1.(M(n))k suy ra
 Cd modN = M1.(1)k modN = M1 modN = M modN 
3.1 Hệ mật RSA
 Ví dụ
– Chọn các số nguyên tố: p=17 & q=11.
– Tính n = pq, n = 17×11=187
– Tính Ф(n)=(p–1)(q-1)=16×10=160
– Chọn e : gcd(e,160)=1; Lấy e=7
– Xác định d: de=1 mod 160 và d < 160 
– Giá trị cần tìm là d=23, vì 23×7=161= 10×160+1
– In khoá công khai KU={7,187}
– Giữ khoá riêng bí mật KR={23,17,11}
3.1 Hệ mật RSA
 Ví dụ áp dụng mã RSA trên như sau: 
– Cho mẩu tin M = 88 (vậy 88<187)
– Mã C = 887 mod 187 = 11 
– Giải mã M = 1123 mod 187 = 88 
– Có thể dùng định lý phần dư Trung Hoa để giải mã cho nhanh như sau:
 Tính 1123 mod 11 = 0
 Tính 1123mod 17 = (-6)23 mod 17 = (-6)16(-6)4 (-6)2 (-6) mod 17 = c1= 3 
Vì (-6)2 mod 17 = 2, nên (-6)4 mod 17 = 4, (-6)8 mod 17 = -1,
(-6)16 mod 17 = 1
 11-1 mod 17 = (-6)-1 mod 17 = 14 nên 11(11-1 mod 17) = 11(14 mod 17) = 
c2 = 154
 Vậy M = (3.154) mod 187 = 462 mod 187 = 88
3.1 Hệ mật RSA
 Mã hiệu quả:
– Mã sử dụng lũy thừa của khoá công khai e, nếu giá trị của e nhỏ thì 
tính toán sẽ nhanh, nhưng dễ bị tấn công. Thường chọn e nhỏ hơn 
hoặc bằng 65537 (216-1), tức là độ dài khoá công khai là 16 bit. 
Chẳng hạn trong ví dụ trên ta có thể lựa chọn e = 23 hoặc e = 7. 
– Ta có thể tính mã hoá nhanh, nếu biết n=pq và sử dụng Định lý phần 
dư Trung Hoa với mẩu tin M theo các Modulo p và q khác nhau. Nếu 
khoá công khai e cố định thì cần tin tưởng rằng khi chọn n ta luôn có 
gcd(e,Ф(n)) = 1. Loại bỏ mọi p, q mà làm cho Ф(n) không nguyên tố 
cùng nhau với e. 
3.1 Hệ mật RSA
 Giải mã hiệu quả:
– Có thể sử dụng Định lý phần dư Trung Hoa để tính 
theo mod p và q, sau đó kết hợp lại để tìm ra bản rõ. 
Vì ở đây người sử dụng khoá riêng biết được p và q, 
do đó có thể sử dụng kỹ thuật này.
– Nếu sử dụng định lý phần dư Trung Hoa để giải mã thì 
hiệu quả là nhanh gấp 4 lần so với giải mã tính trực 
tiếp. 
3.1 Hệ mật RSA
 Sinh khoá RSA
– Người sử dụng RSA cần phải xác định ngẫu nhiên 2 số 
nguyên tố rất lớn p, q thông thường khoảng 512 bit.
– Sau khi chọn được một khoá e hoặc d nguyên tố cùng 
nhau với Ф(n), dễ dàng tính được khoá kia chính là số 
nghịch đảo của nó qua thuật toán Euclide mở rộng.
3.1 Hệ mật RSA
 An toàn của RSA
– Trên thực té có nhiều cách tấn công khác nhau đối với 
mã công khai RSA như sau: 
 Tìm kiếm khoá bằng phương pháp vét cạn, phương pháp này 
không khả thi với kích thước đủ lớn của các số 
 Tấn công bằng toán học dựa vào độ khó việc tính Ф(n) bằng 
cách phân tích n thành hai số nguyên tố p và q hoặc tìm cách 
tính trực tiếp Ф(n). 
 Trong quá trình nghiên cứu việc thám mã người ta đề xuất kiểu 
tấn công thời gian trong khi giải mã, tức là căn cứ vào tốc độ mã 
hoá và giải mã các mẩu tin cho trước mà phán đoán các thông 
tin về khoá.
3.1 Hệ mật RSA
 Điểm bất động
Định lí: Nếu các thông báo được mã bằng hệ mật 
RSA với cặp khóa công khai (e,n) với n = p.q thì số 
các thông báo không thể che dấu được là
( )( ) ( )( )1q,1dUCLN11p,1eUCLN1N =
3.2 Hệ mật Merkle – Hellman
 Hệ mật Merkle – Hellman
- Dãy siêu tăng: Dãy số ngdương tmãn 
với
- Bài toán xếp ba lô:Cho tập các giá trị
và một tổng S. Hãy tính các giá trị bi để: 
với
( )n21 a,,a,a 

=
1i
1j
ji aa ni2,i 
n21 M,,M,M 
nn2211 MbMbMbS =  1,0b i 
3.2 Hệ mật Merkle – Hellman
 TT giải btoán xếp ba lô trong trường hợp dãy siêu tăng:
3.2 Hệ mật Merkle – Hellman
- Tạo khoá:
3.2 Hệ mật Merkle – Hellman
 Mã hoá
3. Một số hệ mật khoá công khai (15)
 Giải mã
3.2 Hệ mật Merkle – Hellman
 Chứng minh
3. Một số hệ mật khoá công khai (1)
3.1 Hệ mật RSA (Ron Rivest, Adi Shamir và Len Adleman)
- Tạo khoá:
3. Một số hệ mật khoá công khai (2)
- Mã hoá: Bên mã là B, bên nhận là A
3. Một số hệ mật khoá công khai (3)
Chú ý: 
1. Số mũ vạn năng 
thay cho
2. Điểm bất động
Định lí: Nếu các thông báo được mã bằng hệ mật RSA với 
cặp khóa công khai với 
thì số các thông báo không thể che dấu được là
( )1q,1pBCNN =
( )( )1q1p =
( )n,e q.pn =
( )( ) ( )( )1q,1dUCLN11p,1eUCLN1N =
3. Một số hệ mật khoá công khai (4)
3.2 Hệ mật Rabin
- Tạo khoá 
+ Tạo 2 số nguyên tố lớn, ngẫu nhiên và phân 
biệt p và q có kích thước xấp xỉ nhau.
+ Tính 
+ Khoá công khai là n, khoá bí mật là các cặp số 
(p, q). 
q.pn =
3. Một số hệ mật khoá công khai (5)
- Mã hoá:
+ Nhận khoá công khai của A: n.
+ Biểu thị bản tin dưới dạng một số nguyên m 
nằm trong dải
+ Tính
+ Gửi bản mã c cho A 
 1n,0 
nmodmc 2=
3. Một số hệ mật khoá công khai (6)
- Giải mã:
+ A phải thực hiện các bước sau:Tìm 4 căn bậc 
hai của là m1, m2, m3 hoặc m4
+ Thông báo cho người gửi là một trong 4 giá trị 
m1, m2, m3 hoặc m4. Bằng một cách nào đó A sẽ 
quyết định m là giá trị nào.
nmodc
3. Một số hệ mật khoá công khai (7)
Chú ý: Khi p, q là các số nguyên Blum thì ta có thể 
tính 4 căn bậc 2 của c mod n như sau:
+ Tìm a,b nguyên thoả mãn:
+Tính các giá trị sau:
4 giá trị căn bậc 2 của là x, 
, y và 
1bqap = 
( ) pmodcr 4/1p = ( ) qmodcs 4/1q =
( ) nmodbqrapsx =( ) nmodbqrapsy =
nmodc nmodx 
nmody 
3. Một số hệ mật khoá công khai (8)
3.3 Hệ mật Elgamal
- Tạo khoá:
+ Tạo 1 số nguyên tố p lớn và một phần tử sinh 
của nhóm nhân của các số nguyên mod p. 
+ Chọn một số nguyên ngẫu nhiên a,
và tính 
Khoá công khai là bộ 3 số , khoá bí mật là a.
*
pZ
2pa1 
pmoda 
( )a,,p 
3. Một số hệ mật khoá công khai (9)
- Mã hoá:
+ Nhận khoá công khai của A
+ Biểu thị bản tin dưới dạng một số nguyên m 
trong dải
+ Chọn số nguyên ngẫu nhiên k, 
+ Tính và 
+ Gửi bản mã cho A 
( )a,,p 
 1p,,1,0 
2pk1 
pmodk = ( ) pmodm ka =
( ) = ,c
3. Một số hệ mật khoá công khai (10)
- Giải mã:
+ Sử dụng khoá riêng a để tính 
+ Khôi phục bản rõ bằng cách tính
- Chứng minh:
pmoda1p 
( ) pmoda  
pmodmm. kakaa   
3. Một số hệ mật khoá công khai (17)
3.5 Hệ mật trên đường cong Elipptic
3. Một số hệ mật khoá công khai (18)
3. Một số hệ mật khoá công khai (19)
3. Một số hệ mật khoá công khai (20)