Bài giảng An toàn và bảo mật dữ liệu trong hệ thống thông tin - Chương 2: Cơ sở lý thuyết số học - Trương Tấn Khoa
CHƯƠNG 2:
CƠ SỞ LÝ THUYẾT SỐ HỌC
1
Chương 2:
Cơ sở lý thuyết số học
2.1. Lý thuyết thông tin
Những khá i niệm mở đầu của lý thuyết thô ng tin được
đưa ra lần đầu tiên vào năm 1948 bởi Claude Elwood
Shannon (một nhà khoa học được coi là cha đẻ của lý
thuyết thô ng tin).
Kỹ thuật lộn xộn và rườm rà (Confusion and Diffusion)
Theo Shannon, có hai kỹ thuật cơ bản để che dấu sự
dư thừa thô ng tin trong thô ng bá o gốc, đó là:
sự lộn xộn và sự rườm rà
2
Chương 2:
Cơ sở lý thuyết số học
Thô ng thường cá c hệ mã hiện đại thường kết hợp cả hai
kỹ thuật thay thế và hoá n vị để tạo ra cá c thuật toá n mã
hó a có độ an toàn cao hơn
3
Chương 2:
Cơ sở lý thuyết số học
2.1.1. Entropy
⚫ Lý thuyết thô ng tin định nghĩa khối lượng thô ng tin
trong một thô ng bá o là số bit nhỏ nhất cần thiết để mã
hó a tất cả những nghĩa của thô ng bá o đó.
Ví dụ: trường ngay_thang trong một cơ sở dữ liệu chứa
khô ng quá 3 bit thô ng tin, bởi vì thô ng tin ngày có thể mã
hó a với 3 bit dữ liệu:
000 = Sunday
001 = Monday
010 = Tuesday
011 = Wednesday
100 = Thursday
101 = Friday
110 = Saturday
111 is unused
4
Chương 2:
Cơ sở lý thuyết số học
2.2. Lý thuyết độ phức tạp
⚫ Lý thuyết độ phức tạp cung cấp một phương phá p để phâ n
tí ch độ phức tạp tí nh toá n của thuật toá n và cá c kỹ thuật mã
hó a khá c nhau. Nó so sá nh cá c thuật toá n mã hó a, kỹ thuật
và phá t hiện ra độ an toàn của cá c thuật toá n đó.
⚫ Lý thuyết thô ng tin đã cho chúng ta biết rằng một thuật toá n
mã hó a có thể bị bại lộ.
⚫ Cò n lý thuyết độ phức tạp cho biết khả năng bị thá m mã của
một hệ mật mã
⚫ Độ phức tạp thời gian của thuật toá n là một hàm của kí ch
thước dữ liệu input của thuật toá n đó. Thuật toá n có độ phức
tạp thời gian f(n) đối với mọi n và kí ch thước input n, nghĩa là
số bước thực hiện của thuật toá n lớn hơn f(n) bước.
5
Chương 2:
Cơ sở lý thuyết số học
2.2.1. Độ an toàn tính toán
Định nghĩa:
Một hệ mật được gọi là an toàn về mặt tí nh toá n nếu có
một thuật toá n tốt nhất để phá nó thì cần í t nhất N phé p
toá n, với N là một số rất lớn nào đó.
6
Chương 2:
Cơ sở lý thuyết số học
2.2.2. Độ an toàn không điều kiện
Một hệ mật được coi là an toàn khô ng điều kiện khi nó
khô ng thể bị phá ngay cả với khả năng tí nh toá n khô ng hạn
chế.
Rõ ràng là độ an toàn khô ng điều kiện khô ng thể nghiên
cứu theo quan điểm độ phức tạp tí nh toá n vì thời gian tí nh
toá n là khô ng hạn chế. Vì vậy, ở đây lý thuyết xá c suất sẽ
được đề cập để nghiên cứu về “an toàn khô ng điều kiện”.
7
Chương 2:
Cơ sở lý thuyết số học
2.3. Số nguyên tố, Đồng dư và Thặng dư
a. Số nguyên tố
Định nghĩa 1 (Số nguyên tố) Một số nguyên tố p ≥ 2 được
gọi là số nguyên tố nếu nó chỉ chia hết cho 1 và p. Ngược
lại là hợp số.
Cá c số nguyên tố từ 2 đến 100:
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ố 2 là số nguyên tố nhỏ nhất và cũng là số nguyên tố
chẵn duy nhất.
8
Chương 2:
Cơ sở lý thuyết số học
2.3. Số nguyên tố, Đồng dư và Thặng dư
# Bảng số nguyên tố - sàng Eratosthene
Sàn Eratosthenes là một giải thuật cổ xưa để lập bảng tất
cả cá c số nguyên tố nhỏ hơn một số n cho trước
Giải thuật dựa trên tí nh chất: mọi hợp số n đều có ước
nguyên tố khô ng vượt quá căn của chí nh nó (sqrt(n))
Giải thuật đầu tiên xó a số 1 ra khỏi tập cá c số nguyên tố. Số tiếp
theo số 1 là số 2, là số nguyên tố. Bắt đầu từ số 2 xó a tất cả cá c
bội của 2 ra khỏi bảng. Số đầu tiên khô ng bị xó a sau số 2 (số 3)
là số nguyên tố. Tiếp theo lại xó a cá c bội của 3 … Giải thuật tiếp
tục cho đến khi gặp số nguyên tố lớn hơn hoặc bằng sqrt(n) thì
dừng lại. Tất cả cá c số chưa bị xó a là số nguyên tố.
9
Chương 2:
Cơ sở lý thuyết số học
2.3. Số nguyên tố, Đồng dư và Thặng dư
b. Modulo số học – đồng dư
Định nghĩa 2 (Modulo số học – đồng dư): Nếu a và b là hai
số nguyên, khi đó a được gọi là đồng dư với b theo modulo n,
ký hiệu:
a ≡ b (mod n)
nếu (a-b) chia hết n, và n được gọi là modulus của đồng dư.
Ví dụ:
(i) 24 ≡ 9 (mod 5) vì 24 – 9 = 3x5
(ii) -11 ≡ 17 (mod 7) vì -11 – 17 = -4x7
(iii) 42 ≡ 6 (mod 9) vì 42 – 6 = 4x9
(iv) -42 ≡ (mod 9)
3?
10
Chương 2:
Cơ sở lý thuyết số học
2.3. Số nguyên tố, Đồng dư và Thặng dư
Tì m giá trị dư của cá c số sau:
-13 mod 5
-18 mod 7
-49 mod 8
-123 mod 16
-213 mod 13
11
Chương 2:
Cơ sở lý thuyết số học
Tính chất của modulo số học
- Modulo số học cũng giống như số học bì nh thường, bao
gồm cá c phé p giao hoá n, kết hợp, phâ n phối. Mặt khá c giảm
mỗi giá trị trung gian trong suốt quá trì nh tí nh toá n.
(a+b) mod n = ((a mod n) + (b mod n)) mod n
(a-b) mod n = ((a mod n) - (b mod n)) mod n
(axb) mod n = ((a mod n) x (b mod n)) mod n
(ax(b+c)) mod n = (((axb) mod n) + ((axc) mod n)) mod n
- Cá c phé p tí nh trong cá c hệ mã mật hầu hết đều thực hiện
đối với một modulo N nào đó
12
Chương 2:
Cơ sở lý thuyết số học
3. Vành 풁푵
- Tập cá c số nguyên 푍푁= {0, 1, …, N-1} trong đó N là một số
tự nhiên dương với 2 phé p toá n cộng (+) và nhâ n (.) được
định nghĩa như sau:
Phé p cộng:
∀a, b ∈ 푍푁: a+b = (a+b) mod N
Phé p nhâ n:
∀a, b ∈ 푍푁: a.b = (a*b) mod N
- Theo tí nh chất của modulo số học chúng ta dễ dàng nhận
thấy 푍푁 là một vành giao hoá n và kết hợp. Hầu hết cá c phé p
tí nh toá n trong cá c hệ mã mật đều được thực hiện trên một
vành 푍푁 nào đó.
13
Chương 2:
Cơ sở lý thuyết số học
3. Vành 풁푵
- Trên vành 푍푁
số 0 là phần tử trung hò a vì : a + 0 = 0 + a = a, ∀a ∈ 푍푁
số 1 được gọi là phần tử đơn vị vì a.1 = 1.a = a, ∀a ∈ 푍푁
- Ví dụ N=9
푍9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}
6 + 8 = 14 ≡ 5 (mod 9)
6 x 8 = 48 ≡ 3 (mod 9)
14
Chương 2:
Cơ sở lý thuyết số học
4. Phần tử nghịch đảo trên vành 풁푵
Định nghĩa 5 (nghịch đảo) Cho a ∈ 푍푁, số nghịch đảo theo
modulo n là một số nguyên x ∈ 푍푁, nếu a.x ≡ 1 (mod n). Nếu
tồn tại x như vậy, thì nó là duy nhất và a được gọi là khả
nghịch, nghịch đảo của a được ký hiệu là 푎−1
Tí nh chất a ∈ 푍푁, a là khả nghịch khi và chỉ khi
gcd(a, n) = 1
Ví dụ: Cá c phần tử khả nghịch trong 푍9 là 1, 2, 4, 5, 7 và 8
chẳng hạn:
4−1 = 7 vì 4.7 ≡ 1 mod 9
15
Ví dụ 2: Tìm các phần tử khả nghịch của 푍26
Chương 2:
Cơ sở lý thuyết số học
Tìm phần tử nghịch đảo của a
1. A = 3 trong 푍7
2. A = 8 trong 푍8
3. A = 6 trong 푍13
4. A = 23 trong 푍40
5. A = 19 trong 푍88
6. A = 17 trong 푍88
16
Chương 2:
Cơ sở lý thuyết số học
Một số thuật toán cơ sở hay sử dụng trong mã hóa
Thuật toán Thuật toán Euclide, tính ước số chung lớn nhất
của hai số
INPUT: Hai số nguyên không âm a và b sao cho a ≥ b.
OUTPUT: Ước số chung lớn nhất của a và b.
1. Trong khi b ≠ 0, thực hiện
1.1 Đặt r ← a mod b, a ← b, b ← r
2. Kết quả(a)
17
Chương 2:
Cơ sở lý thuyết số học
Ví dụ (Euclidean algorithm) Tí nh gcd(4864, 3458) = 38:
4864 = 1.3458 + 1406
3458 = 2.1406 + 646
1406 = 2.646 + 114
646 = 5.114 + 76
114 = 1.76 + 38
76 = 2.38 + 0
18
Chương 2:
Cơ sở lý thuyết số học
Thuật toá n Euclidean có thể được mở rộng để khô ng chỉ tí nh
được ước số chung d của hai số nguyên a và b, mà cò n có thể
tí nh được hai số nguyên x, y thỏa mã n ax + by = d
Thuật toá n Euclidean mở rộng (tì m USCLN hoặc tì m x, y thỏa mã n ax
+ by = d):
INPUT: Hai số nguyên khô ng â m a và b với a ≥ b
OUTPUT: d = gcd(a, b) và hai số x, y thỏa mã n ax+by=d
1. Nếu b = 0, đặt d←a, x←1, y←0, Kết quả (d, x, y)
2. Đặt 푥2←1, 푥1←0, 푦2←0, 푦1←1
3. Trong khi còn b>0, thực hiện:
3.1 q←⎿a/b⏌, r←a-q.b, x ←푥2-q. 푥1, y ←푦2-q. 푦1
3.2 a←b, b←r, 푥2← 푥1, 푥1 ← x, 푦2←푦1, 푦1←y
4. Đặt d←a, x←푥2, y←푦2. Kết quả (d, x, y)
19
Chương 2:
Cơ sở lý thuy
Ví dụ Bảng dưới đây mô
Euclidean mở rộng với đầu vào là a=4864, b = 3458 nhận được kết
quả gcd(4864, 3458)=38 và (4864)(?) + (3458)(?) = 38
q
-
r
-
x
-
y
-
a
b
푥2
푥1
0
푦2
0
푦1
1
4864 3458 1
1 1406 1
-1 3458 1406 0
1
1
-1
3
2
2
5
1
2
646
114
76
38
0
-2
5
3 1406 646
1
-2
-2
5
-1
3
-7
38
646 114
-7
38
-45
-27
32
114
76
76
38
0
5
-27
32
-7
38
-45
-27
32
-91 128 38
-91 -45 128
20
Tải về để xem bản đầy đủ
34 trang
24220
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng An toàn và bảo mật dữ liệu trong hệ thống thông tin - Chương 2: Cơ sở lý thuyết số học - Trương Tấn Khoa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_an_toan_va_bao_mat_du_lieu_trong_he_thong_thong_ti.pdf
