56 trang 10 lượt tải

Bài giảng Chương 3: Lý thuyết số và ứng dụng trong mật mã môn Logic ứng dụng trong kinh doanh | Trường Đại học ngân hàng Thành phố Hồ Chí Minh

20

Bài giảng Chương 3: Lý thuyết số và ứng dụng trong mật mã môn Logic ứng dụng trong kinh doanh | Trường Đại học ngân hàng Thành phố Hồ Chí Minh. Tài liệu được sưu tầm giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem.

Môn: Hệ thống thông tin quản lý (HTTT) 8 tài liệu

Trường: Trường Đại học ngân hàng Thành phố Hồ Chí Minh 337 tài liệu

Tác giả:

Profile

Uyen Vo Ngoc Nha

1 tuần trước
Tải xuống
Báo cáo
Danh sách Quiz
Tải xuống
/56
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 1 / 56
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 2 / 56
Nội dung bài giảng
1. Lý thuyết số căn bản
1.1. Phép chia số nguyên
1.2. Biểu diễn nguyên
1.3. Số nguyên tố, ước chung lớn nhất, bội chung nhỏ nhất
1.4. Các phép toán trên trường hữu hạn
1.5. Định lý phần dư Trung Quốc
1.6. Định lý Fermat nhỏ
2. Ứng dụng lý thuyết số trong mật mã
2.1. Giới thiệu mật mã
2.2. Các hệ mã cổ điển
2.3. Hệ mã công khai RSA
2.4. Ứng dụng mật mã
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 3 / 56
1. Lý thuyết số căn bản
1.1. Phép chia số nguyên
Question: Six children find a bag containing 25 marbles. How
should they share them?
Answer: The answer is that each child should get 4 marbles, and
there will be 1 left over. The problem is to divide 25 by 6. The
quotient is 4 and the remainder is 1.
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 4 / 56
Division
Let a, b ∈ Z with b > 0. There exist integers q and r such that
a = q · b + r and 0 ≤ r < b
Moreover, there is only one such pair of integers (q, r) that satisfies these
conditions.
The integer q is called the quotient,
The integer r is called the remainder.
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 5 / 56
Example: Let a = 23 and b = 10. Then the quotient is q = 2 and
the remainder r = 3 because
23 = 2 · 10 + 3 and 0 ≤ 3 < 10.
Example: Let a = −37 and b = 5. Then the quotient is q = −8 and
the remainder r = 3 because
−37 = −8 · 5 + 3 and 0 ≤ 3 < 5.
Example: Let a = −43 and b = 4. What are q and r?
Solution: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 6 / 56
The operations div and mod
Let a, b ∈ Z with b > 0. We know that there exists a unique pair of
numbers q and r such that
a = q · b + r and 0 ≤ r < b
We define two operations div and mod by
a div b = q and a mod b = r
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 7 / 56
Example:
11 div 3 = 3 and 11 mod 3 = 2
23 div 10 = 2 and 23 mod 10 = 3
Example:
−37 div 5 = −8 and − 37 mod 5 = 3
Example: Let a = −43 and b = 4. Compute
(a div b) = ? and (a mod b) = ?
Solution: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 8 / 56
The equivallent relation (mod n)
Let a, b ∈ Z with n > 0. We define that
a ≡ b (mod n) ⇐⇒ a mod n = b mod n
Example: We get that
53 ≡ 23 (mod 10)
since 53 mod 10 = 3 and 23 mod 10 = 3
Example: We get that
−37 ≡ 8 (mod 5)
since −37 mod 5 = 3 and 8 mod 5 = 3
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 9 / 56
Theorem
Let a, b, c, d ∈ Z with n > 0. If
a ≡ b (mod n) and c ≡ d (mod n)
then
a + c ≡ b + d (mod n) and ac ≡ bd (mod n)
Example: From that
x ≡ 10 (mod 3) and y ≡ 4 (mod 3)
It implies that
x + y ≡ 10 + 4
| {z }
14
≡ 2 (mod 3) and x · y ≡ 10 · 4
|{z}
40
≡ 1 (mod 3)
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 10 / 56
Example: Let x ≡ 17 (mod 7) and y ≡ −5 (mod 7).
Compute
(a) x + y ≡ ? (mod 7)
(b) 2x + 3y ≡ ? (mod 7)
(c) xy ≡ ? (mod 7)
(d) x
3
+3xy +2y
2
≡ ? (mod 7)
Solution: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 11 / 56
1.2. Biểu diễn nguyên
Theorem
Let b be an integer greater than 1. Then if n is a positive integer, it can
be expressed uniquely in the form
n = a
k
b
k
+ a
k−1
b
k−1
+ · · · + a
1
b + a
0
where k is a nonnegative integer, a
0
, a
1
, . . . , a
k
are nonnegative integers
less than b, and a
k
6= 0.
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 12 / 56
Example: Let b = 10 and n = 165
165 = 1 · 10
2
+ 6 · 10 + 5
Example: Let b = 8 and n = 165
165 = 2 · 8
2
+ 4 · 8 + 5
Example: Let b = 2 and n = 241
241 = 1 · 2
7
+ 1 · 2
6
+ 1 · 2
5
+ 1 · 2
4
+ 0 · 2
3
+ 0 · 2
2
+ 0 · 2 + 1
Example: Let b = 16 and n = 175627
175627 = 2 · 16
4
+ 10 · 16
3
+ 14 · 16
2
+ 0 · 16 + 11
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 13 / 56
The base b expansion of n
The representation of n given in the form
n = a
k
b
k
+ a
k−1
b
k−1
+ · · · + a
1
b + a
0
,
is called the base b expansion of n, and denoted by (a
k
a
k−1
. . . a
0
)
b
Some kinds of expansion
Decimal expansion: with base 10
Binary expansion: with base 2
Octal expansion: with base 8
Hexadecimal expansion: with base 16. The hexadecimal digits are
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C , D, E , F , where the letters A = 10,
B = 11, C = 12, D = 13, E = 14, F = 15
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 14 / 56
Example: Let b = 10 and n = 165
165 = 1 · 10
2
+ 6 · 10 + 5 = (165)
10
Example: Let b = 8 and n = 165
165 = 2 · 8
2
+ 4 · 8 + 5 = (245)
8
Example: Let b = 2 and n = 241
241 = 1 · 2
7
+ 1 · 2
6
+ 1 · 2
5
+ 1 · 2
4
+ 1 = (1111 0001)
2
Example: Let b = 16 and n = 175627
175627 = 2 · 16
4
+ 10
|{z}
A
·16
3
+ 14
|{z}
E
·16
2
+ 0 · 16 + 11
|{z}
B
= (2AE 0B)
16
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 15 / 56
Example: Find the decimal expansion of (1 0101 1111)
2
Solution: We have
(1 0101 1111)
2
= 1 · 2
8
+ 0 · 2
7
+ 1 · 2
6
+ 1 · 2
5
+ 1 · 2
4
+ 1 · 2
3
+ 1 · 2
2
+ 1 · 2 + 1
= 351
Example: Find the decimal expansion of (7016)
8
Solution: We have
(7016)
8
= 7 · 8
3
+ 0 · 8
2
+ 1 · 8 + 6 = 3598
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 16 / 56
Example: Find the decimal expansion of (2AE 0B)
16
Solution: We have
(2AE 0B)
16
= 2 · 16
4
+ 10
|{z}
A
·16
3
+ 14
|{z}
E
·16
2
+ 0 · 16 + 11
|{z}
B
= 175627
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 17 / 56
Example: (a) Find the decimal expansion of (1010 0111)
2
(b) Find the decimal expansion of (7243)
8
(c) Find the decimal expansion of (8FC5A)
16
Solution: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 18 / 56
Example: Find the octal expansion of (12345)
10
?
Solution: First, divide 12345 by 8 to obtain
12345 = 8 · 1543 + 1
Successively dividing quotients by 8 gives
1543 = 8 · 192 + 7
192 = 8 · 24 + 0
24 = 8 · 3 + 0
3 = 8 · 0 + 3
The successive remainders that we have found, 1, 7, 0, 0, and 3, are the
digits from the right to the left of 12345 in base 8. Hence,
(12345)
10
= (30071)
8
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 19 / 56
Example: Find the hexadecimal expansion of (177130)
10
?
Solution: Divide successively 177130 by 16
177130 = 16 · 11070 + 10
11070 = 16 · 619 + 14
619 = 16 · 43 + 3
43 = 16 · 2 + 11
2 = 16 · 0 + 2
Hence,
(177130)
10
= (2B3EA)
16
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 20 / 56

Tài liệu khác của Trường Đại học ngân hàng Thành phố Hồ Chí Minh

Preview text:

CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 1 / 56
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 2 / 56 Nội dung bài giảng
1. Lý thuyết số căn bản 1.1. Phép chia số nguyên 1.2. Biểu diễn nguyên
1.3. Số nguyên tố, ước chung lớn nhất, bội chung nhỏ nhất
1.4. Các phép toán trên trường hữu hạn
1.5. Định lý phần dư Trung Quốc 1.6. Định lý Fermat nhỏ
2. Ứng dụng lý thuyết số trong mật mã 2.1. Giới thiệu mật mã
2.2. Các hệ mã cổ điển 2.3. Hệ mã công khai RSA 2.4. Ứng dụng mật mã
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 3 / 56
1. Lý thuyết số căn bản 1.1. Phép chia số nguyên Question:
Six children find a bag containing 25 marbles. How should they share them? Answer:
The answer is that each child should get 4 marbles, and
there will be 1 left over. The problem is to divide 25 by 6. The
quotient is 4 and the remainder is 1.
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 4 / 56 Division
Let a, b ∈ Z with b > 0. There exist integers q and r such that a = q · b + r and 0 ≤ r < b
Moreover, there is only one such pair of integers (q, r ) that satisfies these conditions.
The integer q is called the quotient,
The integer r is called the remainder.
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 5 / 56 Example:
Let a = 23 and b = 10. Then the quotient is q = 2 and the remainder r = 3 because 23 = 2 · 10 + 3 and 0 ≤ 3 < 10. Example:
Let a = −37 and b = 5. Then the quotient is q = −8 and the remainder r = 3 because −37 = −8 · 5 + 3 and 0 ≤ 3 < 5. Example:
Let a = −43 and b = 4. What are q and r ? Solution:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CHƯƠNG .3.-. . LÝ . . . . . . THUYẾT . . . SỐ .V . À . . . ỨNG . . . . DỤNG . . . . . . TRONG . . MẬ .T . .
MÃ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6/56
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The operations div and mod
Let a, b ∈ Z with b > 0. We know that there exists a unique pair of numbers q and r such that a = q · b + r and 0 ≤ r < b
We define two operations div and mod by a div b = q and a mod b = r
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 7 / 56 Example: 11 div 3 = 3 and 11 mod 3 = 2 23 div 10 = 2 and 23 mod 10 = 3 Example: −37 div 5 = −8 and − 37 mod 5 = 3 Example:
Let a = −43 and b = 4. Compute (a div b) = ? and (a mod b) = ? Solution:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 8 / 56
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The equivallent relation (mod n)
Let a, b ∈ Z with n > 0. We define that a ≡ b (mod n) ⇐⇒ a mod n = b mod n Example: We get that 53 ≡ 23 (mod 10) since 53 mod 10 = 3 and 23 mod 10 = 3 Example: We get that −37 ≡ 8 (mod 5) since −37 mod 5 = 3 and 8 mod 5 = 3
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 9 / 56 Theorem
Let a, b, c, d ∈ Z with n > 0. If a ≡ b (mod n) and c ≡ d (mod n) then a + c ≡ b + d (mod n) and ac ≡ bd (mod n) Example: From that x ≡ 10 (mod 3) and y ≡ 4 (mod 3) It implies that x + y ≡ 10 + 4 ≡ 2 (mod 3) and
x · y ≡ 10 · 4 ≡ 1 (mod 3) | {z } | {z } 14 40
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 10 / 56 Example: Let x ≡ 17 (mod 7) and y ≡ −5 (mod 7). Compute (a) x + y ≡ ? (mod 7) (c) xy ≡ ? (mod 7) (b) 2x + 3y ≡ ? (mod 7)
(d) x 3 +3xy +2y 2 ≡ ? (mod 7) Solution:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CHƯƠNG .3.-. . LÝ . . . . . . THUYẾT . . . SỐ . V . À . . . ỨNG . . . . DỤNG . . . . . . TRONG . . MẬ . T . .
MÃ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 / 56
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Biểu diễn nguyên Theorem
Let b be an integer greater than 1. Then if n is a positive integer, it can
be expressed uniquely in the form
n = ak bk + ak−1bk−1 + · · · + a1b + a0
where k is a nonnegative integer, a0, a1, . . . , ak are nonnegative integers less than b, and ak 6= 0.
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 12 / 56 Example: Let b = 10 and n = 165 165 = 1 · 102 + 6 · 10 + 5 Example: Let b = 8 and n = 165 165 = 2 · 82 + 4 · 8 + 5 Example: Let b = 2 and n = 241
241 = 1 · 27 + 1 · 26 + 1 · 25 + 1 · 24 + 0 · 23 + 0 · 22 + 0 · 2 + 1 Example: Let b = 16 and n = 175627
175627 = 2 · 164 + 10 · 163 + 14 · 162 + 0 · 16 + 11
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 13 / 56 The base b expansion of n
The representation of n given in the form
n = ak bk + ak−1bk−1 + · · · + a1b + a0,
is called the base b expansion of n, and denoted by (ak ak−1 . . . a0)b Some kinds of expansion
Decimal expansion: with base 10 Binary expansion: with base 2 Octal expansion: with base 8
Hexadecimal expansion: with base 16. The hexadecimal digits are
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C , D, E , F , where the letters A = 10,
B = 11, C = 12, D = 13, E = 14, F = 15
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 14 / 56 Example: Let b = 10 and n = 165
165 = 1 · 102 + 6 · 10 + 5 = (165)10 Example: Let b = 8 and n = 165
165 = 2 · 82 + 4 · 8 + 5 = (245)8 Example: Let b = 2 and n = 241
241 = 1 · 27 + 1 · 26 + 1 · 25 + 1 · 24 + 1 = (1111 0001)2 Example: Let b = 16 and n = 175627
175627 = 2 · 164 + 10 ·163 + 14 ·162 + 0 · 16 + 11 = (2AE 0B)16 |{z} |{z} |{z} A E B
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 15 / 56 Example:
Find the decimal expansion of (1 0101 1111)2 Solution: We have
(1 0101 1111)2 = 1 · 28 + 0 · 27 + 1 · 26 + 1 · 25
+ 1 · 24 + 1 · 23 + 1 · 22 + 1 · 2 + 1 = 351 Example:
Find the decimal expansion of (7016)8 Solution: We have
(7016)8 = 7 · 83 + 0 · 82 + 1 · 8 + 6 = 3598
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 16 / 56 Example:
Find the decimal expansion of (2AE 0B)16 Solution: We have
(2AE 0B)16 = 2 · 164 + 10 ·163 + 14 ·162 + 0 · 16 + 11 = 175627 |{z} |{z} |{z} A E B
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 17 / 56 Example:
(a) Find the decimal expansion of (1010 0111)2
(b) Find the decimal expansion of (7243)8
(c) Find the decimal expansion of (8FC 5A)16 Solution:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CHƯƠNG .3.-. . LÝ . . . . . . THUYẾT . . . SỐ . V . À . . . ỨNG . . . . DỤNG . . . . . . TRONG . . MẬ . T . .
MÃ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 / 56
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example:
Find the octal expansion of (12345)10? Solution:
First, divide 12345 by 8 to obtain 12345 = 8 · 1543 + 1
Successively dividing quotients by 8 gives 1543 = 8 · 192 + 7 192 = 8 · 24 + 0 24 = 8 · 3 + 0 3 = 8 · 0 + 3
The successive remainders that we have found, 1, 7, 0, 0, and 3, are the
digits from the right to the left of 12345 in base 8. Hence, (12345)10 = (30071)8
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 19 / 56 Example:
Find the hexadecimal expansion of (177130)10? Solution:
Divide successively 177130 by 16 177130 = 16 · 11070 + 10 11070 = 16 · 619 + 14 619 = 16 · 43 + 3 43 = 16 · 2 + 11 2 = 16 · 0 + 2 Hence, (177130)10 = (2B3EA)16
CHƯƠNG 3 - LÝ THUYẾT SỐ VÀ ỨNG DỤNG TRONG MẬT MÃ 20 / 56

Tài liệu liên quan: