35 trang 3 lượt tải

Chuong 03 _04_NMMMH

5

mmhc3

Tác giả:

Profile

Tô Minh Tú

1 giờ trước
Tải xuống
Báo cáo
Danh sách Quiz
Tải xuống
/35
2021/8/16
1
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 1
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin16 August 2021 | Page 2
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 3
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 4
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 5
SV nắm được một số kiến thức cơ bản về lí thuyết số (số học
modulo), cấu trúc đại số được ứng dụng trong mật mã cũng như
một số thuật toán cơ bản liên quan đến tính nghịch đảo theo
modulo, tính các kí hiệu Legendre và Jacobi.
Bài 01. Bổ túc cơ sở toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 6
Cấu trúc toán học
Số học modulo
Bài 01. Bổ túc cơ sở toán học
2021/8/16
2
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 7
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:
Một số kiến thức toán học
1. Tính kết hợp: a.b.c = (a.b).c = a.(b.c)
2. Có phần tử đơn vị e: e.a = a.e = a
3. Có nghịch đảo a
-1
: a.a
-1
= a
-1
.a = 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.
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 8
Cấp của nhóm G chính là số phần tử của G
Cấp của phần tử a trong nhóm G chính là số nguyên dương nhỏ
nhất m thỏa mãn: a
m
= e, trong đó e là phần tử đơn vị của G
Kí hiệu cấp của nhóm G là ord(G) hoặc |G|; cấp của phần tử a là
ord(a) hoặc |a|.
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 9
■ Định nghĩa nhóm xyclic:
□ G được gọi là nhóm xyclic nếu nó chứa một phần tử a sao cho mọi phần
tử của G đều là lũy thừa nguyên nào đó của a
□ a được gọi là phần tử sinh (hay phần tử nguyên thuỷ của nhóm G)
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 10
■ Vành: Cho một tập R phép toán hai ngôi (+, *) được gọi là 1 vành
nếu:
□ Với phép cộng, R là nhóm Aben
□ Với phép nhân, có:
● tính kết hợp: a*b*c = a*(b*c) = (a*b)*c
● tính phân phối đối với phép cộng:
o a*(b+c) = a*b + a*c
o (b+c)*a = b*a + c*a
□ 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
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 11
■ 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:
□ F là một vành
□ Với phép nhân F \{0} là nhóm Aben.
■ 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
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 12
■ Số học modulo
Tính chia hết: Chia số nguyên a cho n được thương là số nguyên q,
a = n.q.
■ a chia hết cho n, n chia hết a hay a là bội số của n, n là ước số của a
và ký hiệu là n|a
Cho 2 số nguyên a và n, n > 1. Thực hiện phép chia a cho n ta sẽ
được 2 số nguyên q và r sao cho:
a = n.q + r, 0 < r < n
■ q được gọi là thương, ký hiệu là a div n
■ r được gọi là số dư, ký hiệu là a mod n
Định nghĩa quan hệ đồng dư 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.
Một số kiến thức toán học
2021/8/16
3
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 13
■ Ví dụ:
□ 100 mod 11 = 1;
□ 34 mod 11 = 1,
100 ≡ 34 mod 11
■ Đại diện của a mod n: Số b được gọi là đại diện của a theo mod n,
nếu
□ a ≡ b mod n (hay a = qn + b) và 0 ≤ b < n.
□ Ví dụ: -12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7.
2 là đại diện của –12, -5, 2 và 9.
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 14
■ Ví dụ:
□ Trong Modulo 7 ta có các lớp tuơng
đương viết trên các hàng như bảng bên
□ 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: Z
n
= { 0, 1, 2, 3, …, n-1 }.
Một số kiến thức toán học
…
-21 -20 -19 -18 -17 -16 -15
-14 -13 -12 -11 -10 -9 -8
-7 -6 -5 -4 -3 -2 -1
0 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
…
-21
-14
-7
0
7
14
21
…
…
1 2 3 4 5 6
-18
-11
-4
3
10
11
24
Các phần tử trong cột đều đồng dư với 0 mod 7Các phần tử trong cột đều đồng dư với 3 mod 7
Các đại diện của các số nguyên mod 7
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 15
■ Ước số
□ Số b không âm được gọi là ước số của a, nếu có số m sao cho: a = m.b
trong đó a, b, m đều nguyên (tức là a chia hết cho b).
□ b là ước của a ta ký hiệu: b|a
□ Ví dụ:
● 1, 2, 3, 4, 6, 8, 12, 24 là các ước số của 24
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 16
Các phép toán số học trên Modulo:
Cho trước số n, thực hiện các phép toán theo modulo n như thế nào?
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 17
(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ó: Z
n
= { 0, 1, 2,
3, …, n-1 }.
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 18
□ Z
n
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 + 10
17
) mod 7 = ?
Một số kiến thức toán học
2021/8/16
4
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 19
■ Giải:
□ Áp dụng các tính chất của modulo, ta có:
● (11 * 19 + 10
17
) mod 7
■ = ((11 * 19) mod 7 + 10
17
mod 7) mod 7
■ = ((11 mod 7 * 19 mod 7) mod 7 + (10 mod 7)
17
) mod 7
■ = ((4 * 5) mod 7 + (((3
2
)
2
)
2
)
2
* 3 mod 7) mod 7
■ = (6 + ((2
2
)
2
)
2
* 3 mod 7) mod 7
■ = (6 + 4 * 3) mod 7 = 4
■ Bài tập: Tính 11
207
mod 13 = ?
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 20
Ước số chung của hai số nguyên a và b
d được gọi là ước số chung của hai số nguyên a và b nếu d|a và d|b.
Ước số chung lớn nhất:
Số nguyên d được gọi là ước số chung lớn nhất của a và b nếu d > 0,
d là ước chung của a và b và mọi ước chung của a và b đều là ước số
của d.
Ký hiệu gcd(a,b) là ước số chung lớn nhất của a và b
■ Ví dụ: gcd(12, 18) = 6, gcd(-18, 27) = 9, gcd(7,15) = 1
■ Với mọi a ta có gcd(a, 0) = a
■ Ta cũng quy ước gcd(0, 0) = 0
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 21
Số nguyên tố:
Số nguyên a > 1 được gọi là số nguyên tố, nếu a không có ước số nào
khác ngoài 1 và chính a.
Nguyên tố cùng nhau:
Hai số a và b được gọi là nguyên tố cùng nhau nếu chúng không có
ước chung nào khác 1, tức là gcd(a,b)=1.
Ví dụ: gcd(8,15) = 1, tức là 8 và 15 là hai số nguyên tố cùng nhau
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 22
Định lý:
Nếu b > 0 và b|a thì gcd(a,b) = b.
Nếu a = b.q + r thì gcd(a,b) = gcd(b,r)
Thuật toán Euclid tìm UCLN:
Một số kiến thức toán học
UCLN(a, b)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 23
Thuật toán Euclide tìm GCD(a, b):
Tính GCD(1970, 1066)?
Một số kiến thức toán học
1. A=a, B=b
2. while B>0
R = A mod B
A = B, B = R
3. Return A
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 24
Một số kiến thức toán học
Giải:
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
2021/8/16
5
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 25
Thuật toán Euclide mở rộng:
Nếu gcd(a,b) = d thì phương trình bất định ax + by = d có nghiệm
nguyên (x,y) và một nghiệm nguyên (x,y) như vậy có thể được tính
bằng thuật toán Euclide mở rộng.
Điều cần và đủ để có nghịch đảo là d = 1 và khi đó x là nghịch đảo của
a mod b và y là nghịch đảo của b mod a
Ta mở rộng thuật toán Euclide:
■ Tìm ước chung lớn nhất của a và b,
■ Tính nghịch đảo trong trường hợp GCD(a, b) = 1.
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 26
Một số kiến thức toán học
Thuật
toán Euclide mở rộng
Input:
Hai số nguyên dương a, b (a b)
Output:
d = gcd(a, b) và số nguyên x, y thỏa mãn ax + by = d
1. If
b = 0 then d a, x 1, y 0 and Return(d, x, y).
2.
,
,
,
3. While
b > 0 do
3.1.
, ,
,
3.2. , ,
,
,
,
4. d
a, x x
2
, y y
2
5. Return(d,
x, y)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 27
Áp dụng thuật toán trên với các đầu vào:
1) a = 1759, b = 550
2) a = 3458, b = 4864
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 28
a = 1759, b = 550
Một số kiến thức toán học
q r x y a b x
2
x
1
y
2
y
1
- - - -
1759
550
1 0 0 1
 550 = 109
 1
= -3
a 550
b
109
0;
1;
1;
-3;


= 3
3
109 1 -3
550 109 0 1 1 -3


= 5
5
109 = 5
 -5
󰇛󰇜= 16
5 -5 16
a 109
b
5
1;
-5;
-3;
16;
109 5 1 -5 -3 16

= 21
21
5 = 4
󰇛󰇜 106
 󰇛󰇜= -339
4 106 -339
a 5
b
4
-5;
106;
16;
-339;
5 4 -5 106 16 -339
= 1
1
4 = 1
 -111
 󰇛󰇜= 355
1 -111 335
a 4
b
1
106;
-111;
-339;
355;
4 1 106 -111 -339 355
= 4
4
1 = 0
 󰇛󰇜 550
󰇛󰇜= -1759
0 550 -1759
a 1
b
0
-111;
;
355;
;
1 0 -111 550 355 -1759
d = 1, x -111, y 355
1759x + 550y = 1
Hay 550
-1
mod 1759 = 355
1759
-1
mod 550 = -111
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 29
Bài tập áp dụng:
Tìm các nghịch đảo sau (nếu có)
■ 127
-1
mod 319 = ?
■ 254
-1
mod 1028 = ?
■ 1031
-1
mod 3713 = ?
■ 508
-1
mod 819 = ?
■ 9773
-1
mod 7079 = ?
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 30
Các số nguyên tố
Như chúng ta đã biết số nguyên tố là các số nguyên dương chỉ có ước
số là 1 và chính nó. Chúng không thể được viết dưới dạng tích của các
số khác.
Các số nguyên tố là trung tâm của lý thuyết số. Số các số nguyên tố là
vô hạn.
Một số kiến thức toán học
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179
181 191 193 197 199
Số nguyên tố < 200
2021/8/16
6
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 31
Một trong những bài toán cơ bản của số học là phân tích ra thừa số
nguyên tố số a, tức là viết nó dưới dạng tích của các số nguyên tố.
Lưu ý rằng phân tích là bài toán khó hơn rất nhiều so với bài toán
nhân các số để nhận được tích.
Người ta đã chứng minh được rằng: mọi số nguyên dương đều có
phân tích duy nhất thành tích các lũy thừa của các số nguyên tố.
Ví dụ: 51 = 3 x 17; 3600 = 2
4
× 3
2
× 5
2
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 32
Ta có thể xác định ước chung lớn nhất bằng cách trong các phân
tích ra thừa số của chúng, tìm các thừa số nguyên tố chung và
lấy bậc lũy thừa nhỏ nhất trong hai phân tích của hai số đó.
Ví dụ:
■ Ta có phân tích: 300 = 2
2
× 3
1
× 5
2
và 18 = 2
1
× 3
2
.
■ Vậy GCD(18, 300) = 2
1
× 3
1
× 5
0
= 6
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 33
Định lý Ferma (Định lý Ferma nhỏ)
a
p-1
mod p = 1 trong đó p là số nguyên tố và a là số nguyên bất kỳ khác bội
của p: GCD(a, p) = 1.
Hay p và a không là bội của p, ta luôn có a
p
= a mod p
Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên
dương nhỏ hơn p.
Ví dụ?
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 34
Ví dụ:
Vì 5 và 7 là các số nguyên tố. 2 và 3 không là bội tương ứng của 7
và 5, nên theo định lý Ferma ta có:
■ 2
7-1
mod 7 = 1 (= 2
6
mod 7 = 64 mod 7= 1)
■ 3
5-1
mod 5 = 1 (= 3
4
mod 5 = 81 mod 5= 1)
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 35
Hàm (n)
Tập Z
n
= {0, 1, 2, . . . , n -1} thường được gọi là thặng dư đầy đủ theo
mod n.
Xét tập
  Tập này được gọi là tập các
thặng dư thu gọn theo mod n
■ Nếu p là số nguyên tố thì

Kí hiệu (n) (hàm Euler) là số phần tử lớn hơn 0, nhỏ hơn n và nguyên
tố cùng nhau với n
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 36
Các tính chất của hàm (n):
Dễ dàng thấy, nếu p là số nguyên tố Ф(p) = p-1
Nếu gcd(m, n) = 1, thì: Ф(m.n) = Ф(m).Ф(n)
Nếu n = p
1
e1
… p
k
ek
là phân tích ra thừa số nguyên tố của n thì:
Một số kiến thức toán học
k
ppp
nn
1
1...
1
1
1
1)(
21
2021/8/16
7
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 37
Ví dụ:
Tính (37); (25); (18); (21)?
Một số kiến thức toán học
(37) = 37 – 1 = 36
(18) = (2). (9) = 1. (3
2
) = 6
(25) = (5
2
) = 20
(21) = (3). (7) = 2.6 = 12
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 38
Định lý Ole: Định lý Ole là tổng quát hoá của Định lý Ferma
a
(n)
mod n= 1
với mọi cặp số nguyên dương nguyên tố cùng nhau a và n:
gcd(a,n)=1.
Ví dụ:
■ a = 3; n = 10; Ф(10)=4; Vì vậy 3
4
= 81 = 1 mod 10
■ a = 2; n =11; Ф(11)=10; Do đó 2
10
= 1024 = 1 mod 11
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 39
Định nghĩa:
Nhóm nhân của Z
n
là Z
n
*
= {a Z
n
| (a, n) =1}
Cấp của Z
n
*
là số các phần tử trong Z
n
*
. KH: | Z
n
*
|
Theo định nghĩa hàm phi Euler ta có: | Z
n
*
| = (n)
Định lý Euler:
Nếu a Z
n
*
thì a
(n)
≡ 1 mod n
Nếu n là tích các số nguyên khác nhau và nếu r ≡ s mod (n) thì a
r
≡ a
s
mod
n; a
Định nghĩa cấp của phần tử:
Cho a Z
n
*
. Cấp a kí hiệu ord(a) là số nguyên dương nhỏ nhất t sao cho: a
t
≡ 1 mod n (t>0)
Lưu ý: Cho a Z
n
*
, ord(a) = t và a
s
≡ 1 mod n khi đó t là ước của s. Đặc biệt
t|(n)
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 40
Ví dụ:
Tính cấp của các phần tử trong Z
20
*
?
■ Ta có n = 20 = 2
2
.5; (20) = 8 = |Z
20
*
|
■ Z
20
*
= {1, 3, 7, 9, 11, 13, 17, 19}
Một số kiến thức toán học
a Z
20
*
1 3 7 9 11 13 17 19
Ord(a) 1 4 4 2 2 4 4 2
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 41
Định nghĩa phần tử sinh:
Z
n
* được gọi là phần tử sinh của Z
n
* nếu:
Z
n
* = {
i
mod n| 0 ≤ i ≤ (n) – 1}
Cho Z
n
*
. Nếu cấp của = (n) thì được gọi là phần tử sinh của Z
n
*
(hay còn được gọi là phần tử nguyên thuỷ).
Nếu Z
n
*
có phần tử sinh thì Z
n
*
được gọi là nhóm xyclic
Z
20
*
có phần tử sinh không?
■ Z
20
*không có phần tử sinh vì (20) = | Z
20
*| = 8 nhưng max(ord(a)) = 4 8,
với a Z
20
*
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 42
Một số kiến thức toán học
Z
n
*
là phần tử sinh Z
n
*
nếu và chỉ nếu
(n)/pi
1 mod n đối với mỗi
nguyên tố của (n)
Giả sử là một phần tử sinh của Z
n
*. Khi đó: b =
i
mod n cũng là
phần tử sinh của Z
n
* nếu và chỉ nếu gcd(i, (n)) = 1.
Nếu Z
n
*
là xyclic thì số phần tử sinh là ((n))
Nếu là một phần tử sinh của Z
n
*
thì:
Z
n
*
= {
i
mod n| 1 ≤ i ≤ (n) – 1}
Z
n
*
có phần tử sinh nếu và chỉ nếu n = 2, 4, p
k
hoặc 2.p
k
.
Trong đó p là số nguyên tố lẻ và k 1.
Tính chất
phần tử
sinh
2021/8/16
8
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 43
Ví dụ:
(1) Z
25
*
là nhóm xyclic và có phần tử sinh = 2. Tìm các phần tử sinh còn
lại của Z
25
*
.
(2) Tìm phần tử sinh của Z
37
*
. Từ phần tử sinh vừa tìm được tìm tất cả
các phần tử sinh còn lại của Z
37
*
.
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 44
Giải:
(1) Tập các phần tử sinh của Z
25
*
= {2, 3, 8, 12, 13, 17, 22, 23}
(2)
■ Ta có (37) = 36; p – 1 = 36 = 2
2
. 3
2
■ Tìm phần tử sinh nhỏ nhất thoả mãn:
■ Xét x = 2 thấy 2
18
mod 37 = 36 1 và 2
12
mod 37 = 26 1. Thoả mãn (*). Vậy 2
là phần tử sinh của Z
37
*
.
■ Các giá trị i thoả mãn (i, (37)) = 1 là {1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35}.
Ta lần lượt tính các giá trị 2
i
mod 37 ta thu được tập các giá trị phần tử sinh
của Z
37
*
là {2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35}
Một số kiến thức toán học
x
36/2
mod 37 1
x
36/3
mod 37 1
với x Z
37
*
(*)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 45
BTVN:
Tìm tất cả các phần tử sinh của Z
59
*
, Z
41
*
.
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 46
Một số kiến thức toán học
Định lí phần dư Trung Hoa
n
1
, …, n
k
nguyên tố cùng nhau từng đôi một thì hệ sau có nghiệm duy
nhất theo modulo n = n
1
…n
k
kk
22
11
nmodax
........................
nmodax
nmodax
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 47
Giải hệ phương trình modulo:
Cho:
x ≡ a
1
mod n
1
x ≡ a
2
mod n
2
...
x ≡ a
k
mod n
k
Với GCD(n
i
, n
j
) = 1, i j. Khi đó ta cũng áp dụng Định lý phần dư
Trung Hoa để tìm x.
Nghiệm x của hệ phương trình được tính như sau:
Trong đó: N = n
1
...n
k
. N
i
= N/n
i
. M
i
= N
i
-1
mod n
i
.
Một số kiến thức toán học
NMNax
k
i
iii
mod
1
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 48
Ví dụ giải hệ phương trình:
x ≡ 10 mod 11
x ≡ 19 mod 21
x ≡ 20 mod 26
x ≡ 7 mod 9
x ≡ 4 mod 10
x ≡ 15 mod 23
Một số kiến thức toán học
X ≡ 670 mod 6006
X ≡ 1924 mod 2070
2021/8/16
9
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 49
Định lý:
Nếu (n
1
, n
2
) = 1 thì cặp phương trình đồng dư:
x ≡ a mod n
1
x ≡ a mod n
2
Có nghiệm duy nhất x ≡ a mod n
1
.n
2
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 50
Định nghĩa thặng dư bậc hai và bất thặng dư bậc hai:
Cho a Z
n
*
, a được gọi là thặng dư bậc hai theo modulo n (hay
bình phương modulo n) nếu x Z
n
*
: x
2
a mod n. Nếu không
tồn tại x như vậy thì a được gọi là bất thặng dư bậc hai mod n.
Tập tất cả các thặng dư bậc hai modulo n được KH:
.
Tập tất cả các bất thặng dư bậc hai modulo n được KH:
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 51
Định lý:
Cho p là nguyên tố lẻ và là phần tử sinh của Z
p
*
. Khi đó a Z
p
*
là
một thặng dư bậc hai modulo p nếu và chỉ nếu a =
i
mod p với i là số
nguyên chẵn
Hệ quả:

;

Ví dụ:
Cho = 3 là phần tử sinh của Z
*
17
.
Tìm

,

Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 52
Định lý:
Cho n = p.q, với p, q là hai số nguyên tố, p ≠ q. Khi đó a Z
*
p
là
thặng dư bậc hai theo modulo n nếu và chỉ nếu a Q
p
và a Q
q
.
Hệ quả:
 󰇛󰇜
;
 󰇛󰇜
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 53
Định nghĩa căn bậc hai của một số modulo n:
Cho a Q
n
. Nếu x Z
*
n
. thỏa mãn x
2
= a mod n thì x được gọi là căn
bậc hai của a mod n.
Định lý về số căn bậc hai của một số modulo n:
Cho
, trong đó p
i
là các số nguyên tố lẻ phân biệt và
e
i
1. Nếu a Q
n
thì có đúng 2
k
căn bậc hai khác nhau theo modulo n
Ví dụ: Tìm các căn bậc hai của 4 mod 15? 1 mod 15?
Căn bậc hai của 4 mod 15 là: 2, 13, 7, 8
Căn bậc hai của 4 mod 15 là: 1, 14, 4, 11
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 54
Ký hiệu Legendre và Jacobi:
Định nghĩa: p là số nguyên tố lẻ, a là số nguyên. KH Legendre
được xác định như sau:
Các tính chất ký hiệu Legendre: SGK (T112)
Một số kiến thức toán học
2021/8/16
10
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 55
Định nghĩa:
Cho n 3 là các số nguyên lẻ có phân tích:
Khi đó KH Jacobi
được định nghĩa là:
Ta thấy rằng nếu n là số nguyên tố thì KH Jacobi chính là kí hiệu Legendre.
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 56
Nếu n là số nguyên lẻ và
m
1
m
2
mod n thì:
Nếu n là số
nguyên lẻ thì:

󰉦 
󰉦 
Trường hợp còn lại
Giả sử m và n là
số nguyên lẻ thì:
󰉦 
Nếu n là số
nguyên lẻ thì:
Đặc biệt nếu m = 2
k
.t
(t là số lẻ) thì :
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 57
Bài tập áp dụng:
Tính ký hiệu Jacobi:
■ A)


■ B)


Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 58
Giải:
A)
Một số kiến thức toán học
4
(4) (1) (3)
3
(2) (4)
(1) (3)
4
3
7411 9283 1872 2 117
.
9283 7411 7411 7411 7411
117 7411 40 2 5
(1) . .
7411 117 117 117 117
5 117 2
( 1) .
117 5 5

1



Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 59
B) Ta có:
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 60
Số nguyên Blum:
Là một hợp số có dạng n = p.q trong đó p, q là các số nguyên tố khác
nhau thỏa mãn: p 3 mod 4, q 3 mod 4.
Định lý:
Cho n = p.q là một số nguyên Blum và cho a Q
n
. Khi đó a có đúng 4
căn bậc hai modulo và chỉ có một số nằm trong Q
n
.
Căn bậc hai chính:
n là số nguyên Blum và a Q
n
. Căn bậc hai duy nhất của a nằm trong
Q
n
được gọi là căn bậc hai chính của a mod n
Bài 02. Một số kiến thức toán học
2021/8/16
11
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 61
Ví dụ: n = 21; Q
21
= {1, 4, 16}
4 căn bậc hai của 4 mod 21 là: 2; 5; 16; 19. Trong đó 16 Q
21
. Do
vậy 16 là căn bậc hai chính của 4 mod 21
4 căn bậc hai của 1 mod 21 là: 1; 8; 13; 20. Trong đó 1 Q
21
. Do
vậy 1 là căn bậc hai chính của 1 mod 21
4 căn bậc hai của 16 mod 21 là: 4; 10; 11; 17. Trong đó 4 Q
21
. Do
vậy 4 là căn bậc hai chính của 16 mod 21
Một số kiến thức toán học
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 62
Một số thuật toán tìm căn bậc hai theo modulo n:
Một số kiến thức toán học
Thuật toán 1:
Tìm căn bậc hai của a mod p (p 3 mod 4)
Input: Số nguyên tố lẻ p; p 3 mod 4 và a Q
p
Output: 2 căn bậc hai của a mod p
1. Tính r = a
(p+1)/4
mod p
2. Return (r, -r)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 63
Một số kiến thức toán học
Thuật toán 2:
Tìm căn bậc hai của a mod p (p 5 mod 8)
Input: Số nguyên tố lẻ p; p 5 mod 8 và a Q
p
Output: 2 căn bậc hai của a mod p
1. Tính d = a
(p-1)/4
mod p
2. Nếu d = 1 thì tính r = a
(p+3)/8
mod p
3. Nếu d = p – 1 thì tính r = 2a.(4a)
(p-5)/8
mod p
4. Return (r, -r)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 64
Một số kiến thức toán học
Thuật toán 3:
Tìm căn bậc hai của c mod n (n = p.q và p 3 mod 4;
p 3 mod 4)
Input: Số nguyên n; p, q và c Q
n
Output: 4 căn bậc hai của c mod n
1. Dùng thuật toán Euclide mở rộng tìm a, b: ap + bq = 1
2. Tính:
r = c
(p+1)/4
mod p
s = c
(q+1)/4
mod q
x = (aps + bqr) mod n
y = (aps - bqr) mod n
3. Return (, )
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 65
Thuật toán 4:
Tìm căn bậc hai của a mod p, p là số nguyên tố
Input: Số nguyên tố lẻ, số nguyên a, 1 a p – 1
Output: 2 căn bậc hai của a mod p nếu a Q
p
1. Tính kí hiệu
nếu
= -1 thì Return “a không có căn bậc hai theo mod p
2. Chọn số nguyên b: 1 b p – 1 sao cho:
= -1 (tức b Q
p
)
3. Phân tích: p – 1 = 2
s
. t (t là số lẻ)
4. Tính a
-1
mod p
5. Đặt c b
t
mod p; r a
(t+1)/2
mod p
6. For i from 1 to s – 1 do
6.1. Tính


mod p
6.2. Nếu d - 1 mod p thì đặt r r. c mod p
6.3. c c
2
mod p
7. Return (r, -r)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 66
Thuật toán nhân bình phương có lặp
Một số kiến thức toán học
Input
Output
a Z
n
và số nguyên k, 0 ≤ k < n có biểu diễn nhị
phân:

a
k
mod n
2021/8/16
12
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 67
Một số kiến thức toán học
(1). Đặt b 1
Nếu k = 0 thì
Return (b)
(2). Đặt A a
(3). Nếu k
0
= 1
thì đặt b a
(4). For i from 1 to t do
4.1. Đặt A A
2
mod n
4.2. Nếu k
i
= 1 thì b A.b mod n
(5). Return (b)
Bài tập áp dụng:
- 5
596
mod 1234 = ?
- 25
705
mod 3542 = ?
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 68
Bài toán logarit rời rạc:
Giả sử cho g là phần tử sinh của nhóm nhân Z
p
*
tức là với a ≠ 0 bất kỳ
thuộc Z
p
*
ta có thể tìm được một số nguyên x duy nhất thỏa mãn: a = g
x
.
Ta có thể viết x = log
g
a
Bài toán logarit rời rạc chính là bài toán tìm x khi biết a.
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 69
Ví dụ: Z
19
*
có phần tử sinh là 2. Hãy tính log
2
x với mọi x Z
19
*
.
Ta có bảng tính:
Log
2
7 = log
2
2
6
= 6.log
2
2 = 6; log
2
15 = log
2
2
11
= 11.log
2
2 = 11;
Giới thiệu một số hệ mật KCK
1
mod 19 = 2
7
mod 19 = 14
13
mod 19 = 3
2
mod 19 = 4
8
mod 19 = 9
14
mod 19 = 6
3
mod 19 = 8
9
mod 19 = 18
15
mod 19 = 12
4
mod 19 = 16
10
mod 19 = 17
16
mod 19 = 5
5
mod 19 = 13
11
mod 19 = 15
17
mod 19 = 10
6
mod 19 = 7
12
mod 19 = 11
18
mod 19 = 1
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 70
Log
2
x với mọi x Z
19
*
.
Giới thiệu một số hệ mật KCK
x 1 2 3 4 5 6 7 8 9
log
2
x
x 10 11 12 13 14 15 16 17 18
log
2
x
x 1 2 3 4 5 6 7 8 9
log
2
x
18 1 13 2 16 14 6 3 8
x 10 11 12 13 14 15 16 17 18
log
2
x
17 12 15 5 7 11 4 10 9
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 71
Giới thiệu một số hệ mật KCK
Thuật toán:
Bước lớn bước nhỏ
Tìm log
trên Z
n
*
, với là phần tử sinh của Z
n
*
Input: , , n
Output: log
trên Z
n
*
1. Tính 
2. Lập bảng (j,
j
mod n) với
3. Tính .(
-m
)
i
mod n với
4. Tra bảng (j,
j
) cho tới khi thỏa mãn .(
-m
)
i
=
j
5. Khi đó: log
= m.i + j
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 72
Bài tập áp dụng:
Cho = 31 là phần tử sinh của Z
61
*
. Hãy tìm log
31
45 trên Z
61
*
.
Cho = 17 là phần tử sinh của Z
97
*
. Hãy tìm log
17
15 trên Z
97
*
.
Giới thiệu một số hệ mật KCK
2021/8/16
13
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 73
Giải: Tìm log
31
45 trên

Ta có: 󰇛󰇜 
Ta lập bảng (j, 31
j
) với
Ta có 31
-1
mod 61 = 2 31
-8
mod 61 = 2
8
mod 61 = 12. Lập bảng tính
.(
-m
)
i
mod n = 45. 12
i
mod 61 với
Giới thiệu một số hệ mật KCK
j 0 1 2 3 4 5 6 7
31
j
mod 61 1 31 46 23 42 21 41 51
i 0 1 2 3 4 5 6 7
45. 12
j
mod 61
45 52 14 46 3 36 5 60
Log
31
45 = mi + j
= 8.3 + 2 = 26
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 74
Giải: Tìm log
17
15 trên

Ta có: 󰇛󰇜  
Ta lập bảng (j, 17
j
) với
Ta có 17
-1
mod 97 = 40 17
-10
mod 97 = 40
10
mod 97 = 3. Lập bảng tính
.(
-m
)
i
mod n = 15. 3
i
mod 97 với
Giới thiệu một số hệ mật KCK
j 0 1 2 3 4 5 6 7 8 9
17
j
mod 61 1 17 95 63 4 68 89 58 16 78
i 0 1 2 3 4 5 6 7 8 9
15. 3
j
mod 97
15
45
38
17
51
56
71
19
57
74
Log
17
15 = mi + j
= 10.3 + 1 = 31
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 75
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 76
1) Dùng thuật toán Euclide tìm phần tử nghịch đảo:
357
-1
mod 1137
213
-1
mod 1577
2) Giải hệ phương trình:
 
 
 
3) Tính (490); (768)
Bài 03. Bài tập áp dụng
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 77
4) Dùng thuật toán Euclide mở rộng tìm UCLN của 1573, 308.
Tìm cặp x, y thỏa mãn: 1573x+308y = UCLN(1573, 308)
5) Tính KH Jacobi:


;


;


;

6) Áp dụng thuật toán tính căn bậc 2 ở phần trước tính:
Căn bậc hai của 47 mod 97
Căn bậc hai của 43 mod 57
Căn bậc hai của 184 mod 211; 44 mod 211
Căn bậc hai của 40 mod 53; 29 mod 53
Bài 03. Bài tập áp dụng
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 78
Chữa bài tập
Bài 03. Bài tập áp dụng
2021/8/16
14
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 79
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 80
Sự khác biệt hệ mật KBM so với KCK?
KCK giải quyết được những vấn đề nào mà KBM không làm
được?
Phân tích đánh giá độ an toàn của các hệ mật KCK theo lớp các
bài toán như phân tích thừa số, logarit rời rạc, bài toán xếp ba
lô?
Các hệ mật KCK: RSA, Rabin, ElGamal, Merkle – Hellman?
Bài 04. Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 81
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…
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 82
Hệ mật RSA:
Độ an toàn 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 đủ).
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 83
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
Hệ mật trên các đường cong Elliptic:
Các hệ mật này là biến thể 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.
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 84
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
Giới thiệu một số hệ mật KCK
2021/8/16
15
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 85
Một số khái niệm trong hệ mật KCK:
Hàm một chiều:
■ Ví dụ: trộn sơn
Giới thiệu một số hệ mật KCK
Trộn 3 loại
sơn
Hàm
1
chiều
Hỗn hợp sơn thu
được sau khi trộn
Tách lại 3 loại
sơn ban đầu?
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 86
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 e
k
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 = p.q, trong đó p, q là các số nguyên tố lớn, giả sử b là một số nguyên
dương.
● Khi đó hàm f(x) = x
b
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 e
k
.
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 87
Bài toán phân tích thừa số:
Cho trước một số N, tìm p, q là các số nguyên tố: N = p q
Ta thấy rằng tính xuôi: p q = N rất dễ dàng, tính ngược tìm p, q từ N là
rất khó khăn
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 88
Ví dụ: Cho N = 408.508.091, tìm số nguyên tố p, q: p q =
408.508.091
Với máy tính cầm tay mất bao lâu để có được p, q?
■ Kiểm tra mỗi số nguyên tố xem có là ước của N hay không? Ví dụ: 3, 5, …,
cho tới p = 18.313 (số nguyên tố thứ 2000) thì thấy 18.313 thực sự là
thừa số của 408.508.091, như vậy dễ dàng xác định được số q = 22.307.
■ Một máy tính kiểm tra 4 số nguyên tố/1 phút mất 500 phút hơn 8
giờ để tìm ra p, q
Nếu biết trước giá trị p = 18.313 và q = 22.307 mất chưa tới 10s để
tính ra N
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 89
Thời gian cần thiết để phân tích số nguyên n ra thừa số
nguyên tố bằng thuật toán nhanh nhất hiện nay:
Giới thiệu một số hệ mật KCK
Số chữ số thập phân Số phép tính bít Thời gian
50 1,4. 10
10
3,9 giờ
75
9. 10
12
104 ngày
100
2,3. 10
15
74 năm
200
1,2. 10
23
3,8.10
9
năm
300
1,5. 10
29
4,9.10
15
năm
500
1,3. 10
39
4,2.10
25
năm
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 90
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.
Giới thiệu một số hệ mật KCK
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.
2021/8/16
16
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 91
Sơ đồ chung của hệ mật khóa công khai được cho bởi
(P, C, K, E, D) (1)
Mỗi khóa k K gồm có 2 thành phần k = (k
e
, k
d
), k
e
là khóa công khai dành
cho việc mã hóa, còn k
d
là khóa bí mật dành cho việc giải mã.
Để xây dựng hệ mật RSA
Chọn trước 2 số nguyên tố lớn p và q, tính n = p.q
Chọn một số e sao cho gcd(e, (n))= 1 và tính số d sao cho: e.d 1 mod (n)
Mỗi cặp khóa k = (k
e
, k
d
), với k
e
= (n,e), k
d
= d là một cặp khóa cho mỗi
người dùng cụ thể
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 92
Sơ đồ chung của hệ mật RSA theo danh sách (1):
P = C = Z
n
, trong đó n là tích của 2 số nguyên tố
K = {k=(k
e
, k
d
) với k
e
= (n, e); k
d
= d sao cho gcd(e, (n)) = 1, e.d 1 mod (n)}
Hàm mã hóa E và giải mã D được xác định bởi:
 
 
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 93
Lưu ý:
KCK: K
E
= (n, e)
KBM: K
D
= d
Giới thiệu một số hệ mật KCK
Chọn p và q
Tính n = p q
Tính (n)
Chọn khóa e
Tính khóa d x = y
d
mod n
y = x
e
mod n
Bản rõ
Bản rõ
Bản mã
n là số
cực lớn
Số nguyên
tố lớn
(p – 1)(q – 1)
gcd(e, (n)) = 1
e
-1
mod (n)) =
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 94
Ví dụ: Cho hệ mật RSA với p = 37, q = 41 và số mũ mã hoá e = 211.
Hãy tính số mũ giải mã d.
Hãy mã hoá bản tin m = 47 và giải mã bản mã vừa thu được.
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 95
Giải:
Ta có: n = p.q = 37. 41 = 1517
(n) = 36. 40 = 1440.
Ta có: ed 1 mod (n)
Tính d = e
-1
mod (n)
tính 211
-1
mod 1440 =?
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 96
Giới thiệu một số hệ mật KCK
Số mũ giải mã:
d = - 389 mod 1440
d = 1051
Tính 211
-1
mod 1440?
q r x y a b x
2
x
1
y
2
y
1
- - - -
1440
211
1 0 0 1
q r x y a b x
2
x
1
y
2
y
1
- - - -
1440
211
1 0 0 1
6
174
1 -6
211
174
0 1 1 -6
1 37 -1 7
174
37 1 -1 -6 7
4 26 5 -34 37 26 -1 5 7 -34
1 11 -6 41 26 11 5 -6 -34 41
2 4 17
-116
11 4 -6 17 41
-116
2 3 -40
273
4 3 17 -40
-116
273
1 1 57
-389
3 1 -40 57
273
-389
1 0 -97
662
1 0 57 -97
-389
662
2021/8/16
17
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 97
Để mã hóa bản tin m = 47 ta tính c = m
e
mod n = 47
211
mod 1517
Phân tích 211 = 2
7
+ 2
6
+ 2
4
+ 2
1
+ 2
0
. Áp dụng phương pháp nhân bình
phương có lặp ta có bảng tính sau:
Vậy bản mã thu được là c = 47
211
mod 1517 = 602
Giới thiệu một số hệ mật KCK
i 0 1 2 3 4 5 6 7
k
i
1 1 0 0 1 0 1 1
A 47
692
1009
174
1453
1062
713
174
b 47
667
667
667
1305
1305
544
602
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 98
Để giải mã bản mã c = 602, ta tính m = c
d
mod n = 602
1051
mod 1517
Ta phân tích: 1051 = 2
10
+ 2
4
+ 2
3
+ 2
1
+ 2
0
. Áp dụng phương pháp nhân
bình phương có lặp ta có bảng tính sau:
Vậy bản rõ m = 602
1051
mod 1517 = 47
Giới thiệu một số hệ mật KCK
i 0 1 2 3 4 5 6 7 8 9 10
k
i
1 1 0 1 1 0 0 0 0 0 1
A
602
1358
1009
174
1453
1062
713
174
1453
1062
713
b
602
1370
1370
211
149
149
149
149
149
149 47
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 99
Độ an toàn của hệ mật RSA
Giới thiệu một số hệ mật KCK
Dữ liệu
• Bản mã
• Bản rõ
Khóa
• Mã hóa
• Giải mã
Phép mã
Phân tích thừa số nguyên tố
Dùng chung modulo n
Dùng số mũ e bé
Sử dụng số Φ(n)
Lặp mã
Sử dụng bản rõ đặc biêt
• Tạo số p, q
• Tạo cặp khóa
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 100
Một số vấn đề khác của 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 giấu được là
N = (1 + UCLN(e – 1, p – 1))(1 + UCLN(d – 1, q – 1))
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 101
Độ dài khóa:
Ứng dụng của RSA: ngân hàng, TMĐT, các giao thức công nghệ
thông tin, chính phủ điện tử, gửi nhận văn bản,…
Giới thiệu một số hệ mật KCK
Năm Độ dài nên sử dụng
2010 1024 bits
2030 2048 bits
2031 3072 bits
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 102
Hệ mật Rabin:
Sơ đồ chung của hệ mật Rabin
■ Z
n
;
■ K = {k=(k
e
, k
d
): k
e
= n, k
d
= (p, q), n = p.q}
■ Hàm mã hóa e và giải mã d được xác định như sau:
● Với mỗi x P, để lập mã cho x ta tính y =


● Hàm giải mã: x =
trong đó
là hàm tính căn bậc hai của y
mod n với các đầu vào (y, p, q)
Giới thiệu một số hệ mật KCK
2021/8/16
18
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 103
Ví dụ:
Tạo khóa:
■ Chọn các số nguyên tố p = 19; q = 23
■ Tính n = p.q = 437
■ Khóa công khai là 437, khóa bí mật là (19 , 23)
Ta có bản tin x = 101001001 (lặp 3 bit cuối).
Thực hiện mã hóa bản tin x và giải mã bản mã thu được.
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 104
Giải:
Ta có x = 101001001
2
= 329
10
Bản mã y = x
2
mod n = 329
2
mod 437 = 302
Để giải mã y ta tìm căn bậc hai của 302 mod 437
■ Trước hết ta tìm (a, b): 19a + 23b = 1
Giới thiệu một số hệ mật KCK
q r x y a b x
2
x
1
y
2
y
1
- - - - 23 19 1 0 0 1
1 4 1 -1 19 4 0 1 1 -1
4 3 -4 5 4 3 1 -4 -1 5
1 1 5 -6 3 1 -4 5 5 -6
3 0 -19 23 1 0 5 -19 -6 23
a = - 6; b = 5
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 105
Tính r = 302
5
mod 19 = 6; s = 302
6
mod 23 = 16
Tính:
x = (aps + bqr) mod n = (-6).19.16 + 5.23.6 mod 437 = -260 = 177 mod 437
y = (aps - bqr) mod n = (-6).19.16 - 5.23.6 mod 437 = -329 = 108 mod 437
4 nghiệm căn bậc hai 302 mod 437 là (177; 260, 108, 329)
Dãy nhị phân tương ứng:
x
1
= 177 = 10110001; x
2
= 260 = 100000100;
x
3
= 108 = 1101100; x
4
= 329 = 101001 001;
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 106
Đánh giá hiệu quả
Thuật toán mã hoá Rabin là một thuật toán cực nhanh vì nó chỉ cần thực
hiện một phép bình phương modulo đơn giản.
Trong khi đó, chẳng hạn với thuật toán RSA có e = 3 phải cần tới một
phép nhân modulo và một phép bình phương modulo.
Thuật toán giải mã Rabin có chậm hơn thuật toán mã hoá, tuy nhiên về
mặt tốc độ nó cung tương đương với thuật toán giải mã RSA.
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 107
Độ an toàn của hệ mật Rabin:
Tấn công bản rõ có lựa chọn: an toàn
Không hoàn toàn an toàn với tấn công bản mã có lựa chọn.
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 108
Hệ mật ElGamal:
Sơ đồ chung của hệ mật Elgamal:
■
;
với p là số nguyên tố
■ K = {k=(k
e
, k
d
): k
e
= (p, , ), k
d
= a [1, p – 2], =
a
mod p} ở đây là
một phần tử nguyên thủy của
■ Hàm mã hóa e và giải mã d được xác định như sau:
● Với mỗi x P, để lập mã cho x ta chọn thêm một số ngẫu nhiên k Z
p-1
rồi tính

với
,


● Hàm giải mã:


Giới thiệu một số hệ mật KCK
2021/8/16
19
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 109
Ví dụ: Sử dụng hệ mật Elgamal với số nguyên tố p = 211, phần tử
sinh = 39 của Z
*
211
. Giả sử người dùng A chọn khóa bí mật a =
113.
Hãy tìm khoá công khai của A?
Giả sử chọn số ngẫu nhiên k = 23, hãy thực hiện mã hoá bản tin x = 34
với khoá công khai của A, và giả mã bản mã vừa thu được.
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 110
Giải:
Ta tính
a
mod 211 = 39
113
mod 211. Ta phân tích 113 = 2
6
+ 2
5
+ 2
4
+ 2
0
.
Áp dụng phương pháp nhân và bình phương có lặp ta có bảng giá trị sau:
Vậy KCK của A là (p, ,
a
) = (211, 39, 108)
Giới thiệu một số hệ mật KCK
i 0 1 2 3 4 5 6
k
i
1 0 0 0 1 1 1
A 39 44 37 103 59 105 53
b 39 39 39 39 191 10 108
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 111
Tính y
1
=
k
mod p = 39
23
mod 211. Phân tích 23 = 2
4
+ 2
2
+ 2
1
+ 2
0
.
Áp dụng phương pháp nhân bình phương có lặp ta có bảng tính
sau:
Vậy: y
1
= 145
Giới thiệu một số hệ mật KCK
i 0 1 2 3 4
k
i
1 1 1 0 1
A 39 44 37 103 59
b 39 28 192 192 145
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 112
Tính y
2
= x.(
a
)
k
mod 211 = 34.(108)
23
mod 211. Trước hết ta tính
(108)
23
mod 211 =?. Áp dụng phương pháp nhân bình phương có
lặp ta có bảng sau:
Khi đó = m(
a
)
k
mod 211 = 34. 91 mod 211 = 140
Vậy bản mã y = (y
1
, y
2
) = (145, 140)
Giới thiệu một số hệ mật KCK
i 0 1 2 3 4
k
i
1 1 1 0 1
A 108 59 105 53 66
b 108 42 190 190 91
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 113
Giải mã y = (y
1
, y
2
) = (145, 140).
Ta tính

 y
1
p-1-a
mod 211 = 145
211-1-113
mod 211 = 145
97
mod 211. Ta phân tích 97 = 2
6
+ 2
5
+ 2
0
Khôi phục bản rõ x bằng cách tính x = y
2.
y
1
p-1-a
= 140. 160 mod 211 = 34
Giới thiệu một số hệ mật KCK
i 0 1 2 3 4 5 6
k
i
1 0 0 0 0 1 1
A
145 136 139 120 52 172 44
b
145 145 145 145 145 42 160
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 114
Bài toán xếp ba lô và hệ mật Merkle – Hellman:
Bài toán ba lô tổng quát:
Ví dụ:
■ Cho S = 53, dãy số nguyên (17, 38, 73, 4, 11, 1)
Giới thiệu một số hệ mật KCK
Cho tập giá trị a
1
, a
2
, …, a
n
và một tổng S. Tính
giá trị v
i
để cho:
S = v
1
a
1
+ v
2
a
2
+ … + v
n
a
n
với v
i
{0,1}
2021/8/16
20
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 115
Với S = 53, dãy số nguyên (17, 38, 73, 4, 11, 1)
Giới thiệu một số hệ mật KCK
Loại 73, vì 73 > 53
Thử 17, S = 53 – 17 = 36, Loại 38,
nhưng 4 + 11 + 1 < 36. Vậy 17 không
có trong lời giải
Thử 38, S = 53 – 38 = 15, thấy tổng số hạng còn lại 4 + 11 = 15.
Vậy lời giải: S = 53 = 38 + 4 + 11
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 116
Cách giải bài toán:
Lời giải của bài toán
được tiến hành theo
thứ tự, ta xét mỗi số
nguyên có thể góp
phần vào tổng và
đã rút gọn bài toán
tương ứng.
Khi một lời giải
không đưa ra tổng
mong muốn, ta
quay lại, loại bỏ
các phỏng đoán
gần và thử lần
lượt.
Với dãy nhiều số
nguyên, rất khó tìm
lời giải, đặc biệt khi
tất cả chúng đều
lớn như nhau đến
mức ta không thể
loại trực tiếp được
số nào.
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 117
Dãy siêu tăng:
Cho dãy số nguyên dương (a
1
, …, a
n
), dãy này được gọi là dãy siêu tăng
nếu:


 
Ví dụ: {1, 4, 11, 17, 38, 73} là một dãy siêu tăng
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 118
Nếu ta hạn chế bài toán ba lô thành các dãy siêu tăng, ta có thể
dễ dàng nói một số hạng có trong tổng không.
Nếu tổng nằm giữa a
k
và a
k+1
thì nó phải bao hàm a
k
như một số
hạng. Ngược lại nếu tổng nhỏ hơn a
k
thì nó không thể bao hàm
a
k
như một số hạng.
Ví dụ:
Cho dãy {1, 4, 11, 17, 38, 73}.
Giải bài toán với các tổng đích S = 96, S = 95
Giới thiệu một số hệ mật KCK
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 119
Giới thiệu một số hệ mật KCK
S = 96 73? Yes 1
96
-
73 = 23
38? No 0
23 17? Yes 1
23
–
17 = 6
11? No 0
6 4? Yes 1
6 – 4 = 2 1? Yes 1
2 – 1 = 1 Không có lời giải
S = 95 73? Yes 1
95
-
73 = 22
38? No 0
22 17? Yes 1
22
–
17 = 5
11? No 0
5 4? Yes 1
5 – 4 = 1 1? Yes 1
1 – 1 = 0 Có lời giải
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 120
Thuật giải bài toán xếp ba lô trong trường hợp dãy siêu tăng:
Giới thiệu một số hệ mật KCK
Thuật giải Ba lô
siêu tăng

Preview text:

2021/8/16
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 1 16 August 2021 | Page 2
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 3
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 4
Bài 01. Bổ túc cơ sở toán học
Bài 01. Bổ túc cơ sở toán học
 SV nắm được một số kiến thức cơ bản về lí thuyết số (số học
Cấu trúc toán học
modulo), cấu trúc đại số được ứng dụng trong mật mã cũng như  Số học modulo
một số thuật toán cơ bản liên quan đến tính nghịch đảo theo
modulo, tính các kí hiệu Legendre và Jacobi.
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 5
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 6 1 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học
Cấu trúc đại số:
 Cấp của nhóm G chính là số phần tử của G 
Đị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
 Cấp của phần tử a trong nhóm G chính là số nguyên dương nhỏ thuộc G:
nhất m thỏa mãn: am = e, trong đó e là phần tử đơn vị của G
1. Tính kết hợp: a.b.c = (a.b).c = a.(b.c)
 Kí hiệu cấp của nhóm G là ord(G) hoặc |G|; cấp của phần tử a là
2. Có phần tử đơn vị e: e.a = a.e = a ord(a) hoặc |a|.
3. Có nghịch đảo a-1: a.a-1 = a-1.a = 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.
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 7
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 8
Một số kiến thức toán học
Một số kiến thức toán học
■ Vành: Cho một tập R   phép toán hai ngôi (+, *) được gọi là 1 vành
■ Định nghĩa nhóm xyclic: nếu:
□ G được gọi là nhóm xyclic nếu nó chứa một phần tử a sao cho mọi phần
□ Với phép cộng, R là nhóm Aben
tử của G đều là lũy thừa nguyên nào đó của a □ Với phép nhân, có:
● tính kết hợp: a*b*c = a*(b*c) = (a*b)*c
□ a được gọi là phần tử sinh (hay phần tử nguyên thuỷ của nhóm G)
● tính phân phối đối với phép cộng: o a*(b+c) = a*b + a*c o (b+c)*a = b*a + c*a
□ 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
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin 16 August 2021 | Page 9
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 10
Một số kiến thức toán học
Một số kiến thức toán học ■ Số học modulo
■ 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: 
Tính chia hết: Chia số nguyên a cho n được thương là số nguyên q, a = n.q. □ F là một vành ■
a chia hết cho n, n chia hết a hay a là bội số của n, n là ước số của a
□ Với phép nhân F \{0} là nhóm Aben.
và ký hiệu là n|a
■ Có thể nói là có các phép toán cộng, trừ, nhân, chia số khác 0. 
Cho 2 số nguyên a và n, n > 1. Thực hiện phép chia a cho n ta sẽ
Phép trừ được coi như là cộng với số đối của phép cộng và phép
được 2 số nguyên q và r sao cho:
chia là nhân với số đối của phép nhân:
a = n.q + r, 0 < r < n  a - b = a + (-b) ■
q được gọi là thương, ký hiệu là a div n  a / b = a.b-1 ■
r được gọi là số dư, ký hiệu là a mod n
Định nghĩa quan hệ đồng dư 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.
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 11
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 12 2 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học ■ Ví dụ: ■ Ví dụ: □ 100 mod 11 = 1;
□ Trong Modulo 7 ta có các lớp tuơng … □ 34 mod 11 = 1,
đương viết trên các hàng như bảng bên
-21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8   100 ≡ 34 mod 11
□ Các phần tử cùng cột là có quan hệ -7 -6 -5 -4 -3 -2 -1
■ Đại diện của a mod n: Số b được gọi là đại diện của a theo mod n, đồng dư với nhau. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 nếu
□ Tập các đại diện của các số nguyên 14 15 16 17 11 18 19 20 21 22 23 24 25 26 27
□ a ≡ b mod n (hay a = qn + b) và 0 ≤ b < n.
theo Modulo n gồm n phần tử ký hiệu …
□ Ví dụ: -12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7.
như sau: Z = { 0, 1, 2, 3, …, n n -1 }.
 2 là đại diện của –12, -5, 2 và 9. Cá C c á cp h đ ầ ạin dtiử ệ t n r o c n ủ g a c c ộ Cá á t c c đ s ề pố u hn ầ đ n g ồ t u n y g ử t ê nd r ư on m v g o ớ c d i ộ7 0 t m đề o u d đ 7 ồng dư với 3 mod 7
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 13
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 14
Một số kiến thức toán học
Một số kiến thức toán học
Các phép toán số học trên Modulo: ■ Ước số
Cho trước số n, thực hiện các phép toán theo modulo n như thế nào?
□ Số b không âm được gọi là ước số của a, nếu có số m sao cho: a = m.b
trong đó a, b, m đều nguyên (tức là a chia hết cho b).
□ b là ước của a ta ký hiệu: b|a □ Ví dụ:
● 1, 2, 3, 4, 6, 8, 12, 24 là các ước số của 24
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 15
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 16
Một số kiến thức toán học
Một số kiến thức toán học □ Z
với các phép toán theo Modulo tạo thành vành giao hoán có đơn vị. Các
(a+b) mod n = [a mod n + b mod n] mod n (*) n
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
(a.b) mod n = [a mod n . b mod n] mod n (**)
ứng của các số nguyê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 chú ý về tính chất rút gọn:
các số tương đương theo Modulo n đó hoặc đơn giản hơn có thể
● Nếu (a+b) ≡ (a+c) mod n, thì b ≡ c mod n
thực hiện các phép toán trên các đại diện của nó: Zn = { 0, 1, 2,
● Nhưng (ab) ≡ (ac) mod n, thì b ≡ c mod n chỉ khi nếu a là nguyên tố cùng 3, …, n-1 }. nhau với n
□ Ví dụ: Tính (11*19 + 1017) mod 7 = ?
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 17
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 18 3 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học ■ Giải:
Ước số chung của hai số nguyên a và b
□ Áp dụng các tính chất của modulo, ta có: 
d được gọi là ước số chung của hai số nguyên a và b nếu d|a và d|b. ● (11 * 19 + 1017) mod 7
Ước số chung lớn nhất: ■
= ((11 * 19) mod 7 + 1017 mod 7) mod 7 
Số nguyên d được gọi là ước số chung lớn nhất của a và b nếu d > 0, ■
= ((11 mod 7 * 19 mod 7) mod 7 + (10 mod 7)17) mod 7
d là ước chung của a và b và mọi ước chung của a và b đều là ước số ■
= ((4 * 5) mod 7 + (((32)2)2)2 * 3 mod 7) mod 7 của d. ■
= (6 + ((22)2)2 * 3 mod 7) mod 7 
Ký hiệu gcd(a,b) là ước số chung lớn nhất của a và b ■ = (6 + 4 * 3) mod 7 = 4 ■
Ví dụ: gcd(12, 18) = 6, gcd(-18, 27) = 9, gcd(7,15) = 1
■ Bài tập: Tính 11207 mod 13 = ? ■
Với mọi a ta có gcd(a, 0) = a ■
Ta cũng quy ước gcd(0, 0) = 0
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 19
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 20
Một số kiến thức toán học
Một số kiến thức toán học  Định lý:Số nguyên tố:
Nếu b > 0 và b|a thì gcd(a,b) = b. 
Số nguyên a > 1 được gọi là số nguyên tố, nếu a không có ước số nào 
Nếu a = b.q + r thì gcd(a,b) = gcd(b,r) khác ngoài 1 và chính a.
Thuật toán Euclid tìm UCLN:
Nguyên tố cùng nhau:
Hai số a và b được gọi là nguyên tố cùng nhau nếu chúng không có
ước chung nào khác 1, tức là gcd(a,b)=1. UCLN(a, b)
Ví dụ: gcd(8,15) = 1, tức là 8 và 15 là hai số nguyên tố cùng nhau
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 21
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 22
Một số kiến thức toán học
Một số kiến thức toán học
Thuật toán Euclide tìm GCD(a, b):Giải: 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94 gcd(162, 94) 1. A=a, B=b 162 = 1 x 94 + 68 gcd(94, 68) 2. while B>0 94 = 1 x 68 + 26 gcd(68, 26) R = A mod B 68 = 2 x 26 + 16 gcd(26, 16) 26 = 1 x 16 + 10 gcd(16, 10) A = B, B = R 16 = 1 x 10 + 6 gcd(10, 6) 3. Return A 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
Tính GCD(1970, 1066)?
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 23
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 24 4 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học
Thuật toán Euclide mở rộng:
Thuật toán Euclide mở rộng
Nếu gcd(a,b) = d thì phương trình bất định ax + by = d có nghiệm
Input: Hai số nguyên dương a, b (a  b)
nguyên (x,y) và một nghiệm nguyên (x,y) như vậy có thể được tính
Output: d = gcd(a, b) và số nguyên x, y thỏa mãn ax + by = d
bằng thuật toán Euclide mở rộng.
1. If b = 0 then d  a, x  1, y  0 and Return(d, x, y). 2. 𝑥 
Điều cần và đủ để có nghịch đảo là d = 1 và khi đó x là nghịch đảo của
2 ← 1, 𝑥1 ← 0, 𝑦2 ← 0, 𝑦1 ← 1
a mod b và y là nghịch đảo của b mod a 3. While b > 0 do 3.1. 𝑞 ← Τ 𝑎 
Ta mở rộng thuật toán Euclide:
𝑏 , 𝑟 ← 𝑎 − 𝑞𝑏, 𝑥 ← 𝑥2 − 𝑞𝑥1, 𝑦 ← 𝑦2 − 𝑞𝑦1
3.2. 𝑎 ← 𝑏, 𝑏 ← 𝑟, 𝑥 ■
Tìm ước chung lớn nhất của a và b,
2 ← 𝑥1, 𝑥1 ← 𝑥, 𝑦2 ← 𝑦1, 𝑦1 ← 𝑦 ■
Tính nghịch đảo trong trường hợp GCD(a, b) = 1. 4. d  a, x  x2, y  y2 5. Return(d, x, y)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 25
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 26
Một số kiến thức toán học
Một số kiến thức toán học  a = 1759, b = 550
Áp dụng thuật toán trên với các đầu vào: q r x y a b x2 x1 y2 y1  1) a = 1759, b = 550 - - - - 1759 550 1 0 0 1 𝑞 ← Τ 54 Τ 1759 Τ 550 109 41 5550 109 = = 14 = = 21 3 5    2) a = 3458, b = 4864 𝑟 𝑟d ← ← = 1759 1550 109 5 4, − − x 1 4. . 1 − − −4- = 1 3 50. 21 1 .5 15 = 1 1, 5 0 y0 9 = 1 = 5 = 4 09 355 3 109 1 -3 550 109 0 1 1 -3 𝑥 𝑥𝑥 ← ← ← 10 1 − − − 5 106 3 − − . 540 . 21. 1.( = (− − 1-5 5 106) 111 = =) - 106 111 =550 𝑦 𝑦𝑦 ← ← ← 01 − − − 3 16 339 3 − . 5 −1 .1(.4 = − 21.. (( - ( − 3 3) = 1 16 355) 339 ) )6 = = --339 = 355 1759 5 5 -5 16 109 5 1 -5 -3 16 a 17 ← a 59 550 109 5 4 1 x + 550y = 1 b Ha  y 550-1 mod 1759 = 355 b b 109 5 10 21 4 106 -339 4 5 4 -5 106 16 -339 𝑥 1759-1mod 550 = -111 2 𝑥 ← 0 1-; 0 1 𝑥 2 ← -5; 6 1 1 𝑥𝑥; 1; ← 𝑥 1 𝑥11; -5; 1 ← 106; ← - ← 111; 550 ; 1 -111 335 4 1 106 -111 -339 355 𝑦 1 2 𝑦 ← 1 - ; 3 3 𝑦 ; 5 2 ← 16; 3 1 𝑦 9 5;1 𝑦; ← 𝑦 𝑦 1 1 - ← 3; 16; 1 ← - ←339; ← 355; −1759; 4
0 550 -1759 1 0 -111 550 355 -1759
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 27
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 28
Một số kiến thức toán học
Một số kiến thức toán học
Bài tập áp dụng:
Các số nguyên tố
Tìm các nghịch đảo sau (nếu có) 
Như chúng ta đã biết số nguyên tố là các số nguyên dương chỉ có ước ■ 127-1 mod 319 = ?
số là 1 và chính nó. Chúng không thể được viết dưới dạng tích của các ■ 254-1 mod 1028 = ? số khác. ■ 1031-1 mod 3713 = ? 
Các số nguyên tố là trung tâm của lý thuyết số. Số các số nguyên tố là ■ 508-1 mod 819 = ? vô hạn. ■ 9773-1 mod 7079 = ?
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Số nguyên tố < 200
101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 29
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 30 5 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học
 Một trong những bài toán cơ bản của số học là phân tích ra thừa số
 Ta có thể xác định ước chung lớn nhất bằng cách trong các phân
nguyên tố số a, tức là viết nó dưới dạng tích của các số nguyên tố.
tích ra thừa số của chúng, tìm các thừa số nguyên tố chung và
 Lưu ý rằng phân tích là bài toán khó hơn rất nhiều so với bài toán
lấy bậc lũy thừa nhỏ nhất trong hai phân tích của hai số đó.
nhân các số để nhận được tích.  Ví dụ:
 Người ta đã chứng minh được rằng: mọi số nguyên dương đều có ■
Ta có phân tích: 300 = 22 × 31 × 52 và 18 = 21 × 32.
phân tích duy nhất thành tích các lũy thừa của các số nguyên tố. ■
Vậy GCD(18, 300) = 21 × 31 × 50 = 6 
Ví dụ: 51 = 3 x 17; 3600 = 24 × 32 × 52
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 31
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 32
Một số kiến thức toán học
Một số kiến thức toán học
Định lý Ferma (Định lý Ferma nhỏ) Ví dụ:
ap-1 mod p = 1 trong đó p là số nguyên tố và a là số nguyên bất kỳ khác bội 
Vì 5 và 7 là các số nguyên tố. 2 và 3 không là bội tương ứng của 7 của p: GCD(a, p) = 1.
và 5, nên theo định lý Ferma ta có: 
Hay p và a không là bội của p, ta luôn có ap = a mod p ■
27-1 mod 7 = 1 (= 26 mod 7 = 64 mod 7= 1) ■
35-1 mod 5 = 1 (= 34 mod 5 = 81 mod 5= 1) 
Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên dương nhỏ hơn p.  Ví dụ?
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 33
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 34
Một số kiến thức toán học
Một số kiến thức toán học  Hàm (n)
Các tính chất của hàm (n):
Tập Zn = {0, 1, 2, . . . , n -1} thường được gọi là thặng dư đầy đủ theo
Dễ dàng thấy, nếu p là số nguyên tố Ф(p) = p-1 mod n. 
Nếu gcd(m, n) = 1, thì: Ф(m.n) = Ф(m).Ф(n) ∗ e1 ek  Xét tập 𝑍𝑛 = 𝑎
𝑍𝑛: gcd 𝑎, 𝑛 = 1 . Tập này được gọi là tập các
Nếu n = p1 … pk là phân tích ra thừa số nguyên tố của n thì:
thặng dư thu gọn theo mod n ∗  1   1   1  ■
Nếu p là số nguyên tố thì 𝑍𝑝 = 1, 2, … , 𝑝 − 1 (n)   n 1 1   ... 1    p1   p2   pk  
Kí hiệu (n) (hàm Euler) là số phần tử lớn hơn 0, nhỏ hơn n và nguyên tố cùng nhau với n
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 35
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 36 6 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học
Định lý Ole: Định lý Ole là tổng quát hoá của Định lý Ferma  Ví dụ: a (n) mod n= 1 
Tính (37); (25); (18); (21)?
với mọi cặp số nguyên dương nguyên tố cùng nhau a và n:  gcd(a,n)=1. (37) = 37 – 1 = 36Ví dụ:
(25) = (52) = 20 ■
a = 3; n = 10; Ф(10)=4; Vì vậy 34 = 81 = 1 mod 10
(18) = (2). (9) = 1. (32) = 6 ■
a = 2; n =11; Ф(11)=10; Do đó 210 = 1024 = 1 mod 11
(21) = (3). (7) = 2.6 = 12
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 37
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 38
Một số kiến thức toán học
Một số kiến thức toán học  Định nghĩa:Ví dụ:  Nhóm nhân của Z *
n là Zn = {a  Zn| (a, n) =1}  Cấp của Z * * * *
n là số các phần tử trong Zn . KH: | Zn | 
Tính cấp của các phần tử trong Z20 ? 
Theo định nghĩa hàm phi Euler ta có: | Z * n | = (n) ■
Ta có n = 20 = 22.5; (20) = 8 = |Z *|  Định lý Euler: 20 *  Nếu a  Z * = {1, 3, 7, 9, 11, 13, 17, 19} n thì a(n) ≡ 1 mod n ■ Z20 
Nếu n là tích các số nguyên khác nhau và nếu r ≡ s mod (n) thì ar ≡ as mod n; a
Định nghĩa cấp của phần tử: a Z * 1 3 7 9 11 13 17 19 20  Cho a  Z *
n . Cấp a kí hiệu ord(a) là số nguyên dương nhỏ nhất t sao cho: at ≡ 1 mod n (t>0) Ord(a) 1 4 4 2 2 4 4 2  Lưu ý: Cho a  Z *
n , ord(a) = t và as ≡ 1 mod n khi đó t là ước của s. Đặc biệt t|(n)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 39
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 40
Một số kiến thức toán học
Một số kiến thức toán học
Định nghĩa phần tử sinh: Tính chất Z *
n có phần tử sinh nếu và chỉ nếu n = 2, 4, pk hoặc 2.pk. 
  Zn* được gọi là phần tử sinh của Zn* nếu: phần tử
Trong đó p là số nguyên tố lẻ và k  1. Z sinh
n* = {i mod n| 0 ≤ i ≤ (n) – 1} * * *
Nếu  là một phần tử sinh của Z thì:  Cho   Z n
n . Nếu cấp của  = (n) thì  được gọi là phần tử sinh của Zn Z *
n = {i mod n| 1 ≤ i ≤ (n) – 1}
(hay còn được gọi là phần tử nguyên thuỷ). * *  Nếu Z
Giả sử  là một phần tử sinh của Z
n có phần tử sinh thì Zn được gọi là nhóm xyclic
n*. Khi đó: b = i mod n cũng là phần tử sinh của Z *
n* nếu và chỉ nếu gcd(i, (n)) = 1. 
Z20 có phần tử sinh không? Nếu Z *
n là xyclic thì số phần tử sinh là ((n)) ■
Z20* không có phần tử sinh vì (20) = | Z20* | = 8 nhưng max(ord(a)) = 4  8, với a  Z   * * 20*
Zn là phần tử sinh Zn nếu và chỉ nếu (n)/pi  1 mod n đối với mỗi nguyên tố của (n)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 41
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 42 7 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học  Giải:Ví dụ: * 
(1) Tập các phần tử sinh của Z
= {2, 3, 8, 12, 13, 17, 22, 23} (1) Z * 25
25 là nhóm xyclic và có phần tử sinh  = 2. Tìm các phần tử sinh còn  (2) lại của Z * 25 . ■
Ta có (37) = 36; p – 1 = 36 = 22. 32
(2) Tìm phần tử sinh của Z * ■
Tìm phần tử sinh nhỏ nhất thoả mãn:
37 . Từ phần tử sinh vừa tìm được tìm tất cả x36/2 mod 37  1
các phần tử sinh còn lại của Z * với x  Z * (*) 37 . x36/3 mod 37  1 37 ■
Xét x = 2 thấy 218 mod 37 = 36  1 và 212 mod 37 = 26  1. Thoả mãn (*). Vậy 2 là phần tử sinh của Z * 37 . ■
Các giá trị i thoả mãn (i, (37)) = 1 là {1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35}.
Ta lần lượt tính các giá trị 2i mod 37 ta thu được tập các giá trị phần tử sinh của Z *
37 là {2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35}
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 43
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 44
Một số kiến thức toán học
Một số kiến thức toán học
Định lí phần dư Trung HoaBTVN: * * n 
Tìm tất cả các phần tử sinh của Z
1, …, nk nguyên tố cùng nhau từng đôi một thì hệ sau có nghiệm duy 59 , Z41 . nhất theo modulo n = n1…nk x  a mod n 1  1  x  a mod n 2  2  ......... ......... .... . x  a mod n k  k 
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 45
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 46
Một số kiến thức toán học
Một số kiến thức toán học
Giải hệ phương trình modulo:
Ví dụ giải hệ phương trình:  Cho : x ≡ a  x ≡ 10 mod 11 1 mod n1 x ≡ a2 mod n2 x ≡ 19 mod 21 X ≡ 670 mod 6006 ... x ≡ ak mod nk x ≡ 20 mod 26 
Với GCD(ni, nj) = 1,  i  j. Khi đó ta cũng áp dụng Định lý phần dư Trung Hoa để tìm x. 
Nghiệm x của hệ phương trình được tính như sau: k    x ≡ 7 mod 9
x    a N M  mod N i i i  x ≡ 4 mod 10 i 1   -1 
Trong đó: N = n1...nk. Ni = N/ni. Mi = Ni mod ni. x ≡ 15 mod 23 X ≡ 1924 mod 2070
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 47
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 48 8 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học  Định lý:
Định nghĩa thặng dư bậc hai và bất thặng dư bậc hai:  Nếu (n *
1, n2) = 1 thì cặp phương trình đồng dư: 
Cho a  Zn , a được gọi là thặng dư bậc hai theo modulo n (hay x ≡ a mod n * 1
bình phương modulo n) nếu  x  Zn : x2  a mod n. Nếu không x ≡ a mod n2
tồn tại x như vậy thì a được gọi là bất thặng dư bậc hai mod n.
Có nghiệm duy nhất x ≡ a mod n1.n2 
Tập tất cả các thặng dư bậc hai modulo n được KH: 𝑄𝑛. 
Tập tất cả các bất thặng dư bậc hai modulo n được KH: ത 𝑄𝑛
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 49
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 50
Một số kiến thức toán học
Một số kiến thức toán học  Định lý:Định lý: * * 
Cho p là nguyên tố lẻ và  là phần tử sinh của Zp . Khi đó a  Zp là 
Cho n = p.q, với p, q là hai số nguyên tố, p ≠ q. Khi đó a  Z*p là
một thặng dư bậc hai modulo p nếu và chỉ nếu a = i mod p với i là số
thặng dư bậc hai theo modulo n nếu và chỉ nếu a  Qp và a  Qq. nguyên chẵn  Hệ quả: 𝑝−1 𝑝−1
Hệ quả: 𝑄𝑝 = ; ത 𝑄 2 𝑝 = 2 𝑝−1 (𝑞−1) 3 𝑝−1 (𝑞−1) 𝑄𝑛 = ; ത 𝑄 4 𝑝 = 4  Ví dụ:
Cho  = 3 là phần tử sinh của Z*17.  Tìm 𝑄17, ത 𝑄17
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 51
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 52
Một số kiến thức toán học
Một số kiến thức toán học
Định nghĩa căn bậc hai của một số modulo n:
Ký hiệu Legendre và Jacobi: 𝑎 
Cho a  Qn. Nếu x  Z*n. thỏa mãn x2 = a mod n thì x được gọi là căn 
Định nghĩa: p là số nguyên tố lẻ, a là số nguyên. KH Legendre 𝑝 bậc hai của a mod n.
được xác định như sau:
Định lý về số căn bậc hai của một số modulo n: 𝑒1 𝑒2 𝑒𝑘 
Cho 𝑛 = 𝑝 . 𝑝 … 𝑝 1 2 , trong đó p 𝑘
i là các số nguyên tố lẻ phân biệt và e  i
1. Nếu a  Qn thì có đúng 2k căn bậc hai khác nhau theo modulo n 
Các tính chất ký hiệu Legendre: SGK (T112)
Ví dụ: Tìm các căn bậc hai của 4 mod 15? 1 mod 15?
Căn bậc hai của 4 mod 15 là: 2, 13, 7, 8 
Căn bậc hai của 4 mod 15 là: 1, 14, 4, 11
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 53
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 54 9 2021/8/16
Một số kiến thức toán học
Nếu n là số nguyên lẻ và 𝐦𝟏 𝐦  𝟐 m 1 m2 mod n thì: 𝐧 𝐧  Định nghĩa: Nếu n là số 𝟐 𝟏
𝒏ế𝒖 𝒏  𝟏 𝒎𝒐𝒅 𝟖 
Cho n  3 là các số nguyên lẻ có phân tích: = nguyên lẻ thì: 𝐧 −𝟏
𝒏ế𝒖 𝒏  𝟑 𝒎𝒐𝒅 𝟖
𝑛 = 𝑝𝑒1. 𝑝𝑒2 … 𝑝𝑒𝑘 1 2 𝑘 Nếu n là số 𝐦𝟏. 𝐦𝟐 𝐦𝟏 𝐦𝟐 𝑎  Khi đó KH Jacobi được định nghĩa là: nguyên lẻ thì: 𝐧 𝐧 𝐧 𝑛 𝒌
Đặc biệt nếu m = 2k.t 𝒎 𝟐 𝐭 𝑎 𝑎 𝑒1 𝑎 𝑒2 𝑎 𝑒𝑘 
(t là số lẻ) thì : = . … 𝐧 𝒏 𝐧 𝑛 𝑝1 𝑝2 𝑝𝑘 𝒏
Ta thấy rằng nếu n là số nguyên tố thì KH Jacobi chính là kí hiệu Legendre.
Giả sử m và n là 𝒎
− 𝒎 𝒏ế𝒖 𝒎,𝒏  𝟑𝒎𝒐𝒅 𝟒 số nguyên lẻ thì: = 𝐧 𝒏 Trường hợp còn lại 𝒎
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 55
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 56
Một số kiến thức toán học
Một số kiến thức toán học
Bài tập áp dụng: Giải:  Tính ký hiệu Jacobi:  A) 4 (4) (1) (3)  7411  9283  1872   2   117     .              7411  9283   7411  7411  7411  7411 ■ A) 9283 3 (2) (4) (1) (3)           6278 117 7411 40 2 5 4  (1) .     .   ■ B)           9975  7411  117  117  117  117   5  117   2  3   ( 1  ) .        1    117   5   5 
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 57
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 58
Một số kiến thức toán học
Bài 02. Một số kiến thức toán học  Số nguyên Blum: B) Ta có:
Là một hợp số có dạng n = p.q trong đó p, q là các số nguyên tố khác
nhau thỏa mãn: p  3 mod 4, q  3 mod 4.  Định lý:
Cho n = p.q là một số nguyên Blum và cho a  Qn. Khi đó a có đúng 4
căn bậc hai modulo và chỉ có một số nằm trong Qn.
Căn bậc hai chính:
n là số nguyên Blum và a  Qn. Căn bậc hai duy nhất của a nằm trong
Qn được gọi là căn bậc hai chính của a mod n
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 59
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 60 10 2021/8/16
Một số kiến thức toán học
Một số kiến thức toán học
Ví dụ: n = 21; Q21 = {1, 4, 16}
Một số thuật toán tìm căn bậc hai theo modulo n:
4 căn bậc hai của 4 mod 21 là: 2; 5; 16; 19. Trong đó 16  Q21. Do
vậy 16 là căn bậc hai chính của 4 mod 21
Tìm căn bậc hai của a mod p (p  3 mod 4)
Thuật toán 1: Input: Số nguyên tố lẻ p; p  3 mod 4 và a  Qp 
4 căn bậc hai của 1 mod 21 là: 1; 8; 13; 20. Trong đó 1  Q21. Do
Output: 2 căn bậc hai của a mod p
vậy 1 là căn bậc hai chính của 1 mod 21 1. Tính r = a(p+1)/4 mod p 
4 căn bậc hai của 16 mod 21 là: 4; 10; 11; 17. Trong đó 4  Q21. Do 2. Return (r, -r)
vậy 4 là căn bậc hai chính của 16 mod 21
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 61
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 62
Một số kiến thức toán học
Một số kiến thức toán học
Tìm căn bậc hai của c mod n (n = p.q và p  3 mod 4;
Tìm căn bậc hai của a mod p (p  5 mod 8) Thuật toán 2: p  3 mod 4)
Input: Số nguyên tố lẻ p; p  5 mod 8 và a  Q Thuật toán 3: p
Input: Số nguyên n; p, q và c  Q
Output: 2 căn bậc hai của a mod p n
Output: 4 căn bậc hai của c mod n 1. Tính d = a(p-1)/4 mod p
1. Dùng thuật toán Euclide mở rộng tìm a, b: ap + bq = 1
2. Nếu d = 1 thì tính r = a(p+3)/8 mod p 2. Tính:
3. Nếu d = p – 1 thì tính r = 2a.(4a)(p-5)/8 mod p r = c(p+1)/4 mod p 4. Return (r, -r) s = c(q+1)/4 mod q x = (aps + bqr) mod n y = (aps - bqr) mod n 3. Return (±𝑥, ±𝑦)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 63
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 64
Tìm căn bậc hai của a mod p, p là số nguyên tố
Một số kiến thức toán học
Thuật toán 4: Input: Số nguyên tố lẻ, số nguyên a, 1  a  p – 1
Output: 2 căn bậc hai của a mod p nếu a  Qp
Thuật toán nhân bình phương có lặp 𝑎 𝑎 1. Tính kí hiệu nếu
= -1 thì Return “a không có căn bậc hai theo mod p 𝑝 𝑝 𝑏 a Z
2. Chọn số nguyên b: 1  b  p – 1 sao cho: = -1 (tức b Q
n và số nguyên k, 0 ≤ k < n có biểu diễn nhị 𝒕 𝑝 p) Input phân:
3. Phân tích: p – 1 = 2s . t (t là số lẻ) 𝒌 = ෍ 𝒌𝒊𝟐𝒊 4. Tính a-1 mod p 𝒊=𝟎
5. Đặt c  bt mod p; r  a(t+1)/2 mod p 6. For i from 1 to s – 1 do
6.1. Tính 𝑑 = 𝑟2. 𝑎−1 2𝑠−𝑖−1mod p Output ak mod n
6.2. Nếu d  - 1 mod p thì đặt r  r. c mod p 6.3. c  c2 mod p 7. Return (r, -r)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 65
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 66 11 2021/8/16
Một số kiến thức toán học
Giới thiệu một số hệ mật KCK (1). Đặt b  1 Nếu k = 0 thì
Bài toán logarit rời rạc: Return (b) * (2). Đặt A  a 
Giả sử cho g là phần tử sinh của nhóm nhân Zp tức là với a ≠ 0 bất kỳ
thuộc Z * ta có thể tìm được một số nguyên x duy nhất thỏa mãn: a = gx. (3). Nếu k p 0 = 1 thì đặt b  a Bài tập áp dụng:  Ta có thể viết x = logga - 5596 mod 1234 = ? 
Bài toán logarit rời rạc chính là bài toán tìm x khi biết a. - 25705 mod 3542 = ? (4). For i from 1 to t do 4.1. Đặt A  A2 mod n (5). Return (b)
4.2. Nếu ki = 1 thì b  A.b mod n
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 67
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 68
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK  Ví dụ: Z * * *
19 có phần tử sinh là 2. Hãy tính log2x với mọi x Z19 .
Log2x với mọi x Z19 .  Ta có bảng tính: x 1 2 3 4 5 6 7 8 9 21 mod 19 = 2 27 mod 19 = 14 213 mod 19 = 3 22 mod 19 = 4 28 mod 19 = 9 214 mod 19 = 6 log o x 2 18 1 13 2 16 14 6 3 8 2 23 mod 19 = 8 29 mod 19 = 18 215 mod 19 = 12 24 mod 19 = 16 210 mod 19 = 17 216 mod 19 = 5 25 mod 19 = 13 211 mod 19 = 15 217 mod 19 = 10 x 10 11 12 13 14 15 16 17 18 26 mod 19 = 7 212 mod 19 = 11 218 mod 19 = 1 log o x 2 17 12 15 5 7 11 4 10 9 2 
Log27 = log226 = 6.log22 = 6; log215 = log2211 = 11.log22 = 11;
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 69
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 70
Giới thiệu một số hệ mật
Giới thiệu một số hệ mật KCK * KCK * Thuật toán:
Tìm log trên Zn , với  là phần tử sinh của Zn Input: , , n
Bước lớn bước nhỏ Output: log *  trên Z
Bài tập áp dụng: n * * 
Cho  = 31 là phần tử sinh của Z61 . Hãy tìm log3145 trên Z61 . * * 
Cho  = 17 là phần tử sinh của Z . Hãy tìm log . 1. Tính 𝑚 = 𝑜𝑟𝑑  97 1715 trên Z97
2. Lập bảng (j, j mod n) với 𝑗 = 0𝑚 − 1
3. Tính .(-m)i mod n với 𝑖 = 0𝑚 − 1
4. Tra bảng (j, j) cho tới khi thỏa mãn .(-m)i = j
5. Khi đó: log = m.i + j
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 71
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 72 12 2021/8/16
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK ∗ ∗
Giải: Tìm log31 45 trên 𝑍61
Giải: Tìm log17 15 trên 𝑍97 Log Log  Ta có: 𝑚 = 𝑜𝑟𝑑(31) = 60 = 8 31 45 = mi + j  Ta có: 𝑚 = 𝑜𝑟𝑑(17) = 96 = 10 17 15 = mi + j = 8.3 + 2 = 26 = 10.3 + 1 = 31
Ta lập bảng (j, 31j) với 𝑗 = 07 
Ta lập bảng (j, 17j) với 𝑗 = 09 j 0 1 2 3 4 5 6 7 j 0 1 2 3 4 5 6 7 8 9 31j mod 61 1 31 46 23 42 21 41 51 17j mod 61 1 17 95 63 4 68 89 58 16 78 
Ta có 31-1 mod 61 = 2  31-8 mod 61 = 28 mod 61 = 12. Lập bảng tính 
Ta có 17-1 mod 97 = 40  17-10 mod 97 = 4010 mod 97 = 3. Lập bảng tính
.(-m)i mod n = 45. 12i mod 61 với 𝑖 = 07
.(-m)i mod n = 15. 3i mod 97 với 𝑖 = 09 i 0 1 2 3 4 5 6 7 i 0 1 2 3 4 5 6 7 8 9 45. 12j mod 61 45 52 14 46 3 36 5 60 15. 3j mod 97 15 45 38 17 51 56 71 19 57 74
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 73
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 74 Bài 03. Bài tập áp dụng
1) Dùng thuật toán Euclide tìm phần tử nghịch đảo:  357-1 mod 1137  213-1 mod 1577
2) Giải hệ phương trình: 5𝑥 13 𝑚𝑜𝑑 17  4𝑥 39 𝑚𝑜𝑑 53 7𝑥 9 𝑚𝑜𝑑 19
3) Tính (490); (768)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 75
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 76 Bài 03. Bài tập áp dụng Bài 03. Bài tập áp dụng
4) Dùng thuật toán Euclide mở rộng tìm UCLN của 1573, 308.  Chữa bài tập
Tìm cặp x, y thỏa mãn: 1573x+308y = UCLN(1573, 308)  5) Tính KH Jacobi:
29 ; 21 ; 47 ; 5 199 211 97 97
6) Áp dụng thuật toán tính căn bậc 2 ở phần trước tính:  Căn bậc hai của 47 mod 97  Căn bậc hai của 43 mod 57 
Căn bậc hai của 184 mod 211; 44 mod 211 
Căn bậc hai của 40 mod 53; 29 mod 53
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 77
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 78 13 2021/8/16
Bài 04. Giới thiệu một số hệ mật KCK
 Sự khác biệt hệ mật KBM so với KCK?
 KCK giải quyết được những vấn đề nào mà KBM không làm được?
 Phân tích đánh giá độ an toàn của các hệ mật KCK theo lớp các
bài toán như phân tích thừa số, logarit rời rạc, bài toán xếp ba lô?
 Các hệ mật KCK: RSA, Rabin, ElGamal, Merkle – Hellman?
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 79
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 80
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK  Giới thiệu:Hệ mật RSA:
Trong hệ mật khóa đối xứng thì khóa phải được chia sẻ giữa hai bên 
Độ an toàn của hệ RSA dựa trên độ khó của việc phân tích ra thừa số
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ế nguyên lớn
điều này rất khó đảm bảo.
Hệ mật xếp ba lô Merkle - Hellman:
Ý tưởng về một hệ mật khoá công khai được Diffie và Hellman đưa ra 
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 vào năm 1976
tập con (bài toán này là bài toán NP đầy đủ). 
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…
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 81
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 82
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK  Hệ mật ElGamal:
 Một chú ý quan trọng là một hệ mật khoá công khai không bao 
Hệ mật ElGamal dựa trên tính khó giải của bài toán logarithm rời rạc
giờ có thể đảm bảo được độ mật tuyệt đối (an toàn vô điều
trên các trường hữu hạn kiện).
Hệ mật trên các đường cong Elliptic:
 Ta chỉ nghiên cứu độ mật về mặt tính toán của các hệ mật này 
Các hệ mật này là biến thể 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.
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 83
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 84 14 2021/8/16
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Một số khái niệm trong hệ mật KCK: Trộn 3 loại
Một số khái niệm trong hệ mật KCK: s T ơn ách lại 3 loại  Hàm một chiều: sơn ban đầu? 
Đặc tính một chiều: Hàm mã khoá công khai ek của Bob phải là một ■ Ví dụ: trộn sơn
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) Hàm ■ Ví dụ: 1 ●
Giả sử n = p.q, trong đó p, q là các số nguyên tố lớn, giả sử b là một số nguyên chiều dương. Hỗn hợp sơn thu ●
Khi đó hàm f(x) = xb mod n là một hàm một chiều. được sau khi trộn 
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.
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 85
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 86
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Bài toán phân tích thừa số:
Ví dụ: Cho N = 408.508.091, tìm số nguyên tố p, q: p q =
Cho trước một số N, tìm p, q là các số nguyên tố: N = p  q 408.508.091
Ta thấy rằng tính xuôi: p  q = N rất dễ dàng, tính ngược tìm p, q từ N là 
Với máy tính cầm tay  mất bao lâu để có được p, q? rất khó khăn ■
Kiểm tra mỗi số nguyên tố xem có là ước của N hay không? Ví dụ: 3, 5, …,
cho tới p = 18.313 (số nguyên tố thứ 2000) thì thấy 18.313 thực sự là
thừa số của 408.508.091, như vậy dễ dàng xác định được số q = 22.307. ■
Một máy tính kiểm tra 4 số nguyên tố/1 phút  mất 500 phút  hơn 8
giờ để tìm ra p, q 
Nếu biết trước giá trị p = 18.313 và q = 22.307  mất chưa tới 10s để tính ra N
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 87
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 88
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Thời gian cần thiết để phân tích số nguyên n ra thừa số Hệ mật RSA:
nguyên tố bằng thuật toán nhanh nhất hiện nay:
RSA là mã công khai được sáng tạo
Số chữ số thập phân Số phép tính bít Thời gian
bởi Rivest, Shamir & Adleman ở MIT 50 1,4. 1010 3,9 giờ 75 9. 1012 104 ngày
(Trường Đại học Công nghệ
Massachusetts) vào năm 1977. 100 2,3. 1015 74 năm 200 1,2. 1023 3,8.109 năm 
RSA là mã công khai được biết đến nhiều nhất và sử dụng rộng rãi 300 1,5. 1029 4,9.1015 năm nhất hiện nay. 500 1,3. 1039 4,2.1025năm
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 89
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 90 15 2021/8/16
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Sơ đồ chung của hệ mật khóa công khai được cho bởi
Sơ đồ chung của hệ mật RSA theo danh sách (1): (P, C, K, E, D) (1)
P = C = Zn, trong đó n là tích của 2 số nguyên tố
 Mỗi khóa k  K gồm có 2 thành phần k = (ke, kd), ke là khóa công khai dành
K = {k=(ke, kd) với ke = (n, e); kd = d sao cho gcd(e, (n)) = 1, e.d  1 mod (n)}
cho việc mã hóa, còn kd là khóa bí mật dành cho việc giải mã.
Hàm mã hóa E và giải mã D được xác định bởi:
Để xây dựng hệ mật RSA
𝑦 = 𝐸𝑘 𝑥 = 𝑥𝑒 𝑚𝑜𝑑 𝑛 ∀𝑥 ∈ 𝑃 𝑒
 Chọn trước 2 số nguyên tố lớn p và q, tính n = p.q
𝑥 = 𝐷𝑘 𝑦 = 𝑦𝑑 𝑚𝑜𝑑 𝑛 ∀𝑦 ∈ 𝐶 𝑑
 Chọn một số e sao cho gcd(e, (n))= 1 và tính số d sao cho: e.d 1 mod (n)
 Mỗi cặp khóa k = (ke, kd), với ke = (n,e), kd = d là một cặp khóa cho mỗi người dùng cụ thể
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 91
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 92
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK  Lưu ý: Chọn p và q Số nguyên
Ví dụ: Cho hệ mật RSA với p = 37, q = 41 và số mũ mã hoá e = 211.  KCK: K n là số tố lớn E = (n, e) 
Hãy tính số mũ giải mã d. cực lớn  KBM: K
Tính n = p q D = d 
Hãy mã hoá bản tin m = 47 và giải mã bản mã vừa thu được. (p – 1)(q – 1) Tính (n) Bản rõ gcd(e, (n)) = 1 Chọn khóa e y = xe mod n Bản mã e-1 mod (n)) = Tính khóa d x = yd mod n Bản rõ
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 93
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 94
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK Tính 211-1 mod 1440? q r x y a b x2 x x 2 1 x y 1 2 y 2 1Giải: - - - - 1440 211 1 0 0 1 Số mũ giải mã: 
Ta có: n = p.q = 37. 41 = 1517 d = - 389 mod 1440 6 174 1 -6 211 174 0 1 1 -6  (n) = 36. 40 = 1440.  d = 1051 1 37 -1 7 174 37 1 -1 -6 7  Ta có: ed  1 mod (n) 4 26 5 -34 37 26 -1 5 7 -34  Tính d = e-1 mod (n) 1 11 -6 41 26 11 5 -6 -34 41  tính 211-1 mod 1440 =? 2 4 17 -116 11 4 -6 17 41 -116 2 3 -40 273 4 3 17 -40 -116 273 1 1 57 -389 3 1 -40 57 273 -389 1 0 -97 662 1 0 57 -97 -389 662
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 95
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 96 16 2021/8/16
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Để mã hóa bản tin m = 47 ta tính c = me mod n = 47211 mod 1517
Để giải mã bản mã c = 602, ta tính m = cd mod n = 6021051 mod 1517
Phân tích 211 = 27 + 26 + 24 + 21 + 20. Áp dụng phương pháp nhân bình 
Ta phân tích: 1051 = 210 + 24 + 23 + 21 + 20. Áp dụng phương pháp nhân
phương có lặp ta có bảng tính sau:
bình phương có lặp ta có bảng tính sau: i 0 1 2 3 4 5 6 7 i 0 1 2 3 4 5 6 7 8 9 10 ki 1 1 0 0 1 0 1 1 ki 1 1 0 1 1 0 0 0 0 0 1 A 47 692 1009 174 1453 1062 713 174 A
602 1358 1009 174 1453 1062 713 174 1453 1062 713 b 47 667 667 667 1305 1305 544 602 b
602 1370 1370 211 149 149 149 149 149 149 47
Vậy bản mã thu được là c = 47211 mod 1517 = 602
Vậy bản rõ m = 6021051 mod 1517 = 47
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 97
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 98
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Độ an toàn của hệ mật RSA
Một số vấn đề khác của RSA:Điểm bất động: • Bản mã ■
Đị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 Dữ liệu
Sử dụng bản rõ đặc biêt • Bản rõ
khai (e,n) với n = p.q thì số các thông báo không thể che giấu được là Dùng chung modulo n
N = (1 + UCLN(e – 1, p – 1))(1 + UCLN(d – 1, q – 1)) • Mã hóa Dùng số mũ e bé Phép mã • Giải mã Sử dụng số Φ(n) Lặp mã • Tạo số p, q
Phân tích thừa số nguyên tố Khóa • Tạo cặp khóa
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 99
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 100
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK  Độ dài khóa:Hệ mật Rabin: Năm
Độ dài nên sử dụng
Sơ đồ chung của hệ mật Rabin 2010 1024 bits ■ 𝑃 =Zn ; 𝐶 = 𝑍𝑛 2030 2048 bits ■
K = {k=(ke, kd): ke = n, kd = (p, q), n = p.q} 2031 3072 bits ■
Hàm mã hóa e và giải mã d được xác định như sau: ●
Với mỗi x  P, để lập mã cho x ta tính y = 𝑒𝑘 𝑥, 𝑘 = 𝑥2𝑚𝑜𝑑 𝑛 𝑒
Ứng dụng của RSA: ngân hàng, TMĐT, các giao thức công nghệ ●
Hàm giải mã: x = 𝑑𝑘 𝑦 trong đó 𝑑
𝑦 là hàm tính căn bậc hai của y 𝑑 𝑘𝑑
thông tin, chính phủ điện tử, gửi nhận văn bản,…
mod n với các đầu vào (y, p, q)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 101
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 102 17 2021/8/16
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK  Giải:Ví dụ:  Ta có x = 1010010012 = 32910  Tạo khóa: 
Bản mã y = x2 mod n = 3292 mod 437 = 302 ■
Chọn các số nguyên tố p = 19; q = 23 
Để giải mã y ta tìm căn bậc hai của 302 mod 437 ■ Tính n = p.q = 437 ■
Trước hết ta tìm (a, b): 19a + 23b = 1 ■
 Khóa công khai là 437, khóa bí mật là (19 , 23) q r x y a b x2 x1 y2 y1
Ta có bản tin x = 101001001 (lặp 3 bit cuối). - - - - 23 19 1 0 0 1 
Thực hiện mã hóa bản tin x và giải mã bản mã thu được. 1 4 1 -1 19 4 0 1 1 -1  a = - 6; b = 5 4 3 -4 5 4 3 1 -4 -1 5 1 1 5 -6 3 1 -4 5 5 -6 3 0 -19 23 1 0 5 -19 -6 23
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 103
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 104
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Tính r = 3025 mod 19 = 6; s = 3026 mod 23 = 16
Đánh giá hiệu quảTính:
Thuật toán mã hoá Rabin là một thuật toán cực nhanh vì nó chỉ cần thực 
x = (aps + bqr) mod n = (-6).19.16 + 5.23.6 mod 437 = -260 = 177 mod 437
hiện một phép bình phương modulo đơn giản. 
y = (aps - bqr) mod n = (-6).19.16 - 5.23.6 mod 437 = -329 = 108 mod 437 
Trong khi đó, chẳng hạn với thuật toán RSA có e = 3 phải cần tới một
4 nghiệm căn bậc hai 302 mod 437 là (177; 260, 108, 329)
phép nhân modulo và một phép bình phương modulo.
Dãy nhị phân tương ứng:
Thuật toán giải mã Rabin có chậm hơn thuật toán mã hoá, tuy nhiên về
mặt tốc độ nó cung tương đương với thuật toán giải mã RSA.  x1 = 177 = 10110001; x2 = 260 = 100000100;  x3 = 108 = 1101100; x4 = 329 = 101001 001;
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 105
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 106
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Độ an toàn của hệ mật Rabin:Hệ mật ElGamal:
Tấn công bản rõ có lựa chọn: an toàn 
Sơ đồ chung của hệ mật Elgamal: 
Không hoàn toàn an toàn với tấn công bản mã có lựa chọn. ∗ ∗ ∗ ■
𝑃 = 𝑍𝑝; 𝐶 = 𝑍𝑝 × 𝑍𝑝 với p là số nguyên tố ■
K = {k=(ke, kd): ke = (p, , ), kd = a  [1, p – 2],  = a mod p} ở đây  là
một phần tử nguyên thủy của 𝑍∗𝑝 ■
Hàm mã hóa e và giải mã d được xác định như sau: ●
Với mỗi x  P, để lập mã cho x ta chọn thêm một số ngẫu nhiên k  Zp-1
rồi tính 𝑒𝑘 𝑥, 𝑘 = 𝑦 𝑒
1, 𝑦2 với 𝑦1 = 𝑘 𝑚𝑜𝑑 𝑝, 𝑦2 = 𝑥. 𝑘 𝑚𝑜𝑑 𝑝 𝑎 −1 ●
Hàm giải mã: 𝑥 = 𝑑𝑘 𝑦 = 𝑑 𝑦 𝑚𝑜𝑑 𝑝 𝑑 𝑘𝑑 1, 𝑦2 = 𝑦2 𝑦1
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 107
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 108 18 2021/8/16
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Ví dụ: Sử dụng hệ mật Elgamal với số nguyên tố p = 211, phần tử  Giải: sinh  = 39 của Z* 
Ta tính a mod 211 = 39113 mod 211. Ta phân tích 113 = 26 + 25 + 24 + 20.
211. Giả sử người dùng A chọn khóa bí mật a = 113.
Áp dụng phương pháp nhân và bình phương có lặp ta có bảng giá trị sau: 
Hãy tìm khoá công khai của A? i 0 1 2 3 4 5 6
Giả sử chọn số ngẫu nhiên k = 23, hãy thực hiện mã hoá bản tin x = 34 ki 1 0 0 0 1 1 1
với khoá công khai của A, và giả mã bản mã vừa thu được. A 39 44 37 103 59 105 53 b 39 39 39 39 191 10 108
Vậy KCK của A là (p, , a) = (211, 39, 108)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 109
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 110
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
 Tính y2 = x.(a)k mod 211 = 34.(108)23 mod 211. Trước hết ta tính
 Tính y1 = k mod p = 3923 mod 211. Phân tích 23 = 24 + 22 + 21 + 20.
(108)23 mod 211 =?. Áp dụng phương pháp nhân bình phương có
Áp dụng phương pháp nhân bình phương có lặp ta có bảng tính lặp ta có bảng sau: sau: i 0 1 2 3 4 i 0 1 2 3 4 k k i 1 1 1 0 1 i 1 1 1 0 1 A 39 44 37 103 59 A 108 59 105 53 66 b 39 28 192 192 145 b 108 42 190 190 91
 Khi đó  = m(a)k mod 211 = 34. 91 mod 211 = 140  Vậy: y1 = 145
 Vậy bản mã y = (y1, y2) = (145, 140)
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 111
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 112
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK
Giải mã y = (y1, y2) = (145, 140).
Bài toán xếp ba lô và hệ mật Merkle – Hellman: 𝑎 −1 p-1-a  Ta tính 𝑦1 𝑚𝑜𝑑 𝑝 = y1
mod 211 = 145211-1-113 mod 211 = 14597 
Bài toán ba lô tổng quát:
mod 211. Ta phân tích 97 = 26 + 25 + 20
Cho tập giá trị a1, a2, …, an và một tổng S. Tính i 0 1 2 3 4 5 6 giá trị vi để cho:  k 1 0 0 0 0 1 1
S = v1a1 + v2a2 + … + vnan với vi {0,1} i A 145 136 139 120 52 172 44  Ví dụ: b 145 145 145 145 145 42 160 ■
Cho S = 53, dãy số nguyên (17, 38, 73, 4, 11, 1) p-1-a
Khôi phục bản rõ x bằng cách tính x = y2. y1 = 140. 160 mod 211 = 34
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 113
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 114 19 2021/8/16
Giới thiệu một số hệ mật KCK
Cách giải bài toán:
Với S = 53, dãy số nguyên (17, 38, 73, 4, 11, 1) Loại 73, vì 73 > 53 Lời giải của bài toán Khi một lời giải Với dãy nhiều số được tiến hành theo không đưa ra tổng nguyên, rất khó tìm
lời giải, đặc biệt khi
Thử 17, S = 53 – 17 = 36, Loại 38,
thứ tự, ta xét mỗi số mong muốn, ta nguyên có thể góp quay lại, loại bỏ tất cả chúng đều
nhưng 4 + 11 + 1 < 36. Vậy 17 không phần vào tổng và các phỏng đoán lớn như nhau đến có trong lời giải đã rút gọn bài toán gần và thử lần mức ta không thể tương ứng. lượt. loại trực tiếp được số nào.
Thử 38, S = 53 – 38 = 15, thấy tổng số hạng còn lại 4 + 11 = 15.
Vậy lời giải: S = 53 = 38 + 4 + 11
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 115
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 116
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK  Dãy siêu tăng:
 Nếu ta hạn chế bài toán ba lô thành các dãy siêu tăng, ta có thể 
Cho dãy số nguyên dương (a1, …, an), dãy này được gọi là dãy siêu tăng
dễ dàng nói một số hạng có trong tổng không. nếu:
 Nếu tổng nằm giữa ak và ak+1 thì nó phải bao hàm ak như một số 𝑖−1
hạng. Ngược lại nếu tổng nhỏ hơn ak thì nó không thể bao hàm 𝑎𝑖 > ෍ 𝑎𝑗 ∀𝑖; 𝑖 = 2, 𝑛 ak như một số hạng. 𝑗=1  Ví dụ:
Ví dụ: {1, 4, 11, 17, 38, 73} là một dãy siêu tăng 
Cho dãy {1, 4, 11, 17, 38, 73}. 
Giải bài toán với các tổng đích S = 96, S = 95
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 117
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 118
Giới thiệu một số hệ mật KCK
Giới thiệu một số hệ mật KCK S = 96 73? Yes 1 S = 95 73? Yes 1
Thuật giải bài toán xếp ba lô trong trường hợp dãy siêu tăng: 96 -73 = 23 38? No 0 95 -73 = 22 38? No 0 23 17? Yes 1 22 17? Yes 1 23 – 17 = 6 11? No 0 22 – 17 = 5 11? No 0 Thuật giải Ba lô 6 4? Yes 1 5 4? Yes 1 siêu tăng 6 – 4 = 2 1? Yes 1 5 – 4 = 1 1? Yes 1 2 – 1 = 1 Không có lời giải 1 – 1 = 0 Có lời giải
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 119
Bộ môn Khoa Học An Toàn Thông Tin – Khoa An Toàn Thông Tin
16 August 2021 | Page 120 20

Tài liệu liên quan: