Lí thuyết mật mã - Chương 1: Tổng quan

Cung cấp kiến thức cơ bản về mật mã đảm bảo an toàn và bảo mật

thông tin:

 Các phương pháp mật mã khóa đối xứng; Phương pháp mật mã

khóa công khai;

 Các hệ mật dòng và vấn đề tạo dãy giả ngẫu nhiên;

 Lược đồ chữ ký số Elgamal và chuẩn chữ ký số ECDSA;

 Độ phức tạp xử lý và độ phức tạp dữ liệu của một tấn công cụ thể

vào hệ thống mật mã;

 Đặc trưng an toàn của phương thức mã hóa;

 Thám mã tuyến tính, thám mã vi sai và các vấn đề về xây dựng hệ

mã bảo mật cho các ứng dụng.

Lí thuyết mật mã - Chương 1: Tổng quan trang 1

Trang 1

Lí thuyết mật mã - Chương 1: Tổng quan trang 2

Trang 2

Lí thuyết mật mã - Chương 1: Tổng quan trang 3

Trang 3

Lí thuyết mật mã - Chương 1: Tổng quan trang 4

Trang 4

Lí thuyết mật mã - Chương 1: Tổng quan trang 5

Trang 5

Lí thuyết mật mã - Chương 1: Tổng quan trang 6

Trang 6

Lí thuyết mật mã - Chương 1: Tổng quan trang 7

Trang 7

Lí thuyết mật mã - Chương 1: Tổng quan trang 8

Trang 8

Lí thuyết mật mã - Chương 1: Tổng quan trang 9

Trang 9

Lí thuyết mật mã - Chương 1: Tổng quan trang 10

Trang 10

Tải về để xem bản đầy đủ

pdf 57 trang minhkhanh 8580
Bạn đang xem 10 trang mẫu của tài liệu "Lí thuyết mật mã - Chương 1: Tổng quan", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Lí thuyết mật mã - Chương 1: Tổng quan

Lí thuyết mật mã - Chương 1: Tổng quan
BỘ MÔN ĐIỆN TỬ HÀNG KHÔNG VŨ TRỤ
3/21/2016 1
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN ĐIỆN TỬ - VIỄN THÔNG 
Môn học:
LÝ THUYẾT MẬT MÃ
Giảng viên: PGS.TS Đỗ Trọng Tuấn
Email: dotrongtuan@gmail.com
Mục tiêu học phần
Cung cấp kiến thức cơ bản về mật mã đảm bảo an toàn và bảo mật
thông tin:
 Các phương pháp mật mã khóa đối xứng; Phương pháp mật mã
khóa công khai;
 Các hệ mật dòng và vấn đề tạo dãy giả ngẫu nhiên;
 Lược đồ chữ ký số Elgamal và chuẩn chữ ký số ECDSA;
 Độ phức tạp xử lý và độ phức tạp dữ liệu của một tấn công cụ thể
vào hệ thống mật mã;
 Đặc trưng an toàn của phương thức mã hóa;
 Thám mã tuyến tính, thám mã vi sai và các vấn đề về xây dựng hệ
mã bảo mật cho các ứng dụng.
2
Nội Dung
1. Chương 1. Tổng quan
2. Chương 2. Mật mã khóa đối xứng
3. Chương 3. Mật mã khóa công khai
4. Chương 4. Hàm băm và chữ ký số
5. Chương 5. Dãy giả ngẫu nhiên và hệ mật dòng
6. Chương 6. Kỹ thuật quản lý khóa
3/21/2016 3
Tài liệu tham khảo
1. A. J. Menezes, P. C. Van Oorschot, S. A. Vanstone, Handbook
of applied cryptography, CRC Press 1998.
2. B. Schneier, Applied Cryptography. John Wiley Press 1996.
3. M. R. A. Huth, Secure Communicating Systems, Cambridge
University Press 2001.
4. W. Stallings, Network Security Essentials, Applications and
Standards, Prentice Hall. 2000.
4
Nhiệm vụ của Sinh viên
1. Chấp hành nội quy lớp học
2. Thực hiện đầy đủ bài tập
3. Nắm vững ngôn ngữ lập trình Matlab
5
Chương 1. Tổng quan
1.1. Giới thiệu sơ lược lịch sử khoa học mật mã
1.2. Khái niệm, mô hình của hệ mật
1.3. Một số hệ mật ban đầu
1.4. Các bài toán an toàn thông tin
1.5. Thám mã 
1.6. Tính an toàn của các hệ mật mã
1.7. Cơ sở toán học của hệ mật mã
1.8. Tính bí mật của các hệ mật
6
1.1. Giới thiệu sơ lược lịch sử khoa học 
mật mã
• Người Ai Cập cổ đại bắt đầu sử dụng mật mã hạn chế khoảng
4000 năm về trước.
• Thuật ngữ “mật mã - cryptography ” dịch từ tiếng Hy Lạp có
nghĩa là “chữ viết bí mật” (Kryptósgráfo “hidden” và grafo “to
write” or legein “to speak”).
• Sự phổ biến của máy tính và hệ thống thông tin liên lạc trong
những năm 1960 đã tạo ra nhu cầu từ khu vực tư nhân bảo vệ
thông tin dưới dạng số và cung cấp dịch vụ an ninh thông tin.
• DES: Tiêu chuẩn bảo mật dữ liệu được Feistel bắt đầu từ năm
1970 tại IBM và chấp thuận vào năm 1977 là một tiêu chuẩn xử
lý thông tin liên bang Hoa Kỳ để bảo mật thông tin không được
phân loại. DES là cơ chế mã hóa nổi tiếng nhất trong lịch sử.
7
1.1. Giới thiệu sơ lược lịch sử khoa học 
mật mã
• Diffie và Hellman xuất bản bài báo New Directions in
Cryptography năm 1976: Mật mã khóa công cộng public-key
cryptography; cơ chế trao đổi khóa mới; các tác giả chưa đề nghị
phương án thực tế.
• Năm 1978 thuật toán mật mã và chữ ký khóa công khai đầu tiên,
RSA, ra đời.
• Trước đó, vào năm 1973, Clifford Cocks, một nhà toán học người
Anh đã mô tả một thuật toán tương tự. Với khả năng tính toán tại
thời điểm đó thì thuật toán này không khả thi và chưa bao giờ
được thực nghiệm. Tuy nhiên, phát minh này chỉ được công bố
vào năm 1997 vì được xếp vào loại tuyệt mật.
• Năm 1985 ElGamal phát triển một lớp thuật toán khóa công cộng
khác dựa trên bài toán logarit rời rạc.
8
1.1. Giới thiệu sơ lược lịch sử khoa học 
mật mã
• Đóng góp quan trọng trong khóa công cộng là chữ ký số . Năm
1991 tiêu chuẩn chữ ký số đầu tiên ISO/IEC 9796 dựa trên thuật
toán RSA
• Năm 1994 chính phủ Mỹ xuất bản Digital Signature Standard
dựa trên cơ chế ElGamal.
• Hàng thế kỷ qua, mật mã là nghệ thuật viết mã và giải mã
• Trước: Chủ yếu trong thông tin quân sự và tình báo
9
1.1. Giới thiệu sơ lược lịch sử khoa học 
mật mã
• Ngày nay, các ứng dụng mã hóa và bảo mật thông tin đang được sử
dụng ngày càng phổ biến trong các lĩnh vực khác nhau trên thế giới, từ
các lĩnh vực an ninh, quân sự, quốc phòng, cho đến các lĩnh vực dân
sự như thương mại điện tử, ngân hàng.
• Trong đời sống – xã hội: Các ứng dụng mã hóa thông tin cá nhân, trao
đổi thông tin kinh doanh, thực hiện các giao dịch điện tử qua mạng... đã
trở nên gần gũi và quen thuộc với mọi người.
• Ứng dụng của khoa học mật mã không chỉ đơn thuần là mã hóa và giải
mã thông tin mà còn bao gồm nhiều vấn đề khác nhau cần được nghiên
cứu và giải quyết như chứng thực nguồn gốc nội dung thông tin (kỹ
thuật chữ ký điện tử), chứng nhận tính xác thực về người sở hữu mã
khóa (chứng nhận khóa công cộng), các quy trình giúp trao đổi thông
tin và thực hiện giao dịch điện tử an toàn trên mạng...
• Những kết quả nghiên cứu về mật mã cũng đã được đưa vào trong các
hệ thống phức tạp hơn, kết hợp với những kỹ thuật khác để đáp ứng yêu
cầu đa dạng của các hệ thống ứng dụng khác nhau trong thực tế.
10
1.1. Giới thiệu sơ lược lịch sử khoa học 
mật mã
• Ngày nay, các ứng dụng mã hóa và bảo mật thông tin đang được sử
dụng ngày càng phổ biến trong các lĩnh vực khác nhau trên thế giới, từ
các lĩnh vực an ninh, quân sự, quốc phòng, cho đến các lĩnh vực dân
sự như thương mại điện tử, ngân hàng.
• Trong đời sống – xã hội: Các ứng dụng mã hóa thông tin cá nhân, trao
đổi thông tin kinh doanh, thực hiện các giao dịch điện tử qua mạng... đã
trở nên gần gũi và quen thuộc với mọi người.
• Ứng dụng của khoa học mật mã không chỉ đơn thuần là mã hóa và giải
mã thông tin mà còn bao gồm nhiều vấn đề khác nhau cần được nghiên
cứu và giải quyết như chứng thực nguồn gốc nội dung thông tin (kỹ
thuật chữ ký điện tử), chứng nhận tính xác thực về người sở hữu mã
khóa (chứng nhận khóa công cộng), các quy trình giúp trao đổi thông
tin và thực hiện giao dịch điện tử an toàn trên mạng...
• Những kết quả nghiên cứu về mật mã cũng đã được đưa vào trong các
hệ thống phức tạp hơn, kết hợp với những kỹ thuật khác để đáp ứng yêu
cầu đa dạng của các hệ thống ứng dụng khác nhau trong thực tế.
11
Herodotos xứ Halikarnasseus, là một nhà sử học người Hy Lạp 
sống ở thế kỷ 5 trước Công nguyên (khoảng 484 TCN - 425 
TCN), ông được coi là "người cha của môn sử học" trong văn 
hóa phương Tây.
12
 ... 
19
1.2. Khái niệm, mô hình của hệ mật
 Ngược lại của mật mã là
thám mã
 Thực hiện bài toán: “Tìm
chìa khóa mật mã”
 Không thể xây dựng một hệ mật
(Cryptosystem) tốt nếu không
hiểu biết sâu về thám mã.
 Một giải pháp mật mã là bảo đảm
bí mật, nếu mọi thuật toán thám
mã, nếu có, đều phải được thực
hiện với độ phức tạp tính toán
cực lớn.
20
1.2. Khái niệm, mô hình của hệ mật
Mật mã học (Cryptology) 
=
Mật mã (Cryptography) + 
Thám mã (Cryptanalysis)
 Một sơ đồ hệ thống mật mã là một bộ năm
21
1.2. Khái niệm, mô hình của hệ mật
Hệ thống mật mã
(Cryptosystem)
 = (, , , , )
Thỏa mãn các điều kiện sau đây:
 Tập nguồn P là tập hữu hạn tất cả các bản tin nguồn cần mã hóa có thể có.
 C là một tập hữu hạn các ký tự bản mã
 K là tập hữu hạn các khóa có thể được sử dụng
 E là một ánh xạ từ KxP vào C, được gọi là phép lập mật mã
 D là một ánh xạ từ KxC vào P , được gọi là phép giải mã
 Một sơ đồ hệ thống mật mã là một bộ năm tham số
22
1.2. Khái niệm, mô hình của hệ mật
Hệ thống mật mã
(Cryptosystem)
 = (, , , , )
 Với mỗi khóa  ∈  , tồn tại luật mật mã  ∈  và luật giải mật mã
 ∈  tương ứng.
 Luật mật mã :  →  và luật giải mật mã :  →  là hai ánh xạ
thỏa mãn: (()) = , ∀ ∈ 
23
1.3. Một số hệ mật ban đầu
 Mã theo khối (Block cipher)
 Độ dài khối (k)
 Không gian khóa  được mở rộng từ  → 
 Mỗi  =    ∈ 
, các thuật toán  và  được mở rộng: 
: 
 →  và : 
 →  như sau:
Với mọi    ∈ 
 và    ∈ 
 ta có
    =    ()
    =    ()
24
1.3. Một số hệ mật ban đầu
Mã theo dòng (Stream cipher)
 Đầu tiên xác định 1 dòng khóa:  =    ∈ 
∗ nào đó
 Bản mã tương ứng với mọi bản rõ  =    ∈ 
∗ với 
dòng khóa  được xác định:
  =     =     ()
 Giải mã  =   ta được:
  =        =    = 
25
1.3. Một số hệ mật ban đầu
Mã theo dòng (Stream cipher)
 Trong các ứng dụng thực tế, người ta thường dùng cách mã
theo dòng có sơ đồ mật mã gốc là sơ đồ Vernam với:
 =  =  = {0,1}
 Các hàm lập mã và giải mã được xác định bởi:
  =  + mod (2)
  =  + mod 2
 = 0 ℎặ 1
 Dòng khóa là dãy bit ngẫu nhiên được sinh ra bởi một bộ 
tạo dãy bit ngẫu nhiên nào đó.
26
1.3. Một số hệ mật ban đầu
Mật mã khóa đối xứng
 Trong một giao dịch truyền tin bảo mật:
Người A gửi cho người B bản tin bảo mật với quy ước trước một 
khóa chung .
• A dùng  để lập mật mã
• B dùng  đề giải mã bản mật
 Nhận xét:
27
1.3. Một số hệ mật ban đầu
Mật mã khóa công khai
 Trong khoa học mật mã, về nguyên tắc hai hàm lập mã và
giải mã là khác nhau, không nhất thiết phải phụ thuộc cùng
một khóa.
28
1.3. Một số hệ mật ban đầu
Mật mã khóa công khai
Hệ mật mã với cách sử dụng đó là
“Mật mã phi đối xứng”
Nhận xét:
Hệ mật mã với cách sử dụng đó là
“Hệ Mật mã khóa công khai”
29
1.4. Các bài toán an toàn thông tin
Bảo mật:
Toàn vẹn thông tin
Nhận thực một thực thể:
Nhận thực một thông báo:
30
1.4. Các bài toán an toàn thông tin
 Ủy quyền:
 Cấp chứng chỉ:
 Báo nhận:
 Làm chứng:
31
1.4. Các bài toán an toàn thông tin
Không chối bỏ được:
Ẩn danh:
Thu hồi:
Chữ ký:
32
1.4. Các bài toán an toàn thông tin
privacy
or confidentiality
Tính riêng tư
hoặc tính bí
mật
keeping information secret from all but those 
who are authorized to see it.
Data integrity Tính toàn vẹn
dữ liệu
ensuring information has not been altered by 
unauthorized or unknown means.
Entity 
authentication
or identification
Nhận thực thực
thể hoặc định
danh
corroboration of the identity of an entity (e.g., a 
person, a
computer terminal, a credit card, etc.).
Message
authentication
Nhận thực bản
tin
corroborating the source of information; also 
known as data
origin authentication.
Signature Chữ ký a means to bind information to an entity
Authorization Tác quyền conveyance, to another entity, of official sanction 
to do or be
something.
33
1.4. Các bài toán an toàn thông tin
Validation Tính hợp lệ a means to provide timeliness of authorization to 
use or manipulate information or resources.
Access control Điều khiển truy
nhập
restricting access to resources to privileged 
entities
Certification Chứng nhận endorsement of information by a trusted entity
timestamping Nhãn thời
gian
recording the time of creation or existence of 
information
Witnessing Chứng thực verifying the creation or existence of 
information by an entity other than the 
creator
Receipt Biên nhận acknowledgement that information has been 
received
Confirmation Xác nhận acknowledgement that services have been 
provided
1.4. Các bài toán an toàn thông tin
Ownership Quyền sơ hữu a means to provide an entity with the legal 
right to use or
transfer a resource to others
Anonymity Nặc danh concealing the identity of an entity involved in 
some process
Non-
repudiation
Chống sự từ
chối
preventing the denial of previous commitments 
or actions
Revocation Thu hồi retraction of certification or authorization
35
1.5. Thám mã
 Mật mã học hiện đại – Modern Cryptography: Là ngành khoa học
nghiên cứu các kỹ thuật đảm bảo an toàn thông tin, giao dịch và các
tính toán phân bố.
 Thám mã (Cryptanalysis): Là ngành khoa học nghiên cứu các điểm
yếu của hệ mật từ đó đưa ra phương pháp tấn công hệ mật đó.
 Mật mã và thám mã là hai lĩnh vực đối lập nhau nhưng gắn bó mật
thiết với nhau.
 Không thể xây dựng một hệ mật (Cryptosystem) tốt nếu không hiểu
biết sâu về thám mã.
 Một giải pháp mật mã là bảo đảm bí mật, nếu mọi thuật toán thám
mã, nếu có, đều phải được thực hiện với độ phức tạp tính toán cực
lớn.
36
1.5. Thám mã
37
1.5. Thám mã
 Các bài toán thám mã:
 Thám mã chỉ biết bản mã :
 Thám mã khi biết cả bản rõ:
 Thám mã khi có bản rõ được chọn:
 Thám mã khi có bản mã được chọn:
38
1.6. Tính an toàn của các hệ mật mã
 Tính an toàn của một hệ thống mật mã phụ thuộc vào độ
khó khăn của bài toán thám mã khi sử dụng hệ mật mã
đó.
 Tính an toàn theo nghĩa được chứng minh hay tính toán
được sử dụng nhiều trong việc nghiên cứu các hệ thống
mật mã hiện đại, đặc biệt là các hệ thống mật mã khóa
công khai.
 Các vấn đề an toàn của hệ mật mã bao gồm:
39
1.6. Tính an toàn của các hệ mật mã
 An toàn vô điều kiện:
 An toàn được chứng minh:
 An toàn tính toán:
40
1.7. Cơ sở toán học của lý thuyết mật mã
 Z là tập hợp các số nguyên: Z = {.....,-2,-1,0,1,2,....}
 Z+ là tập hợp các số nguyên không âm, Z+= {0,1,2,.....}
 Tập hợp Z là đóng kín đối với các phép cộng, trừ và nhân,
nhưng không đóng kín đối với phép chia.
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
41
1.7. Cơ sở toán học của lý thuyết mật mã
 Cho hai số nguyên bất kỳ a và b , b > 1
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
42
1.7. Cơ sở toán học của lý thuyết mật mã
 Ước số chung lớn nhất:
 = (, )
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
43
1.7. Cơ sở toán học của lý thuyết mật mã
 số nguyên tố:
Một số nguyên a > 1 được gọi là số nguyên tố, nếu a không có ước số
nào ngoài 1 và chính a; và được gọi là hợp số, nếu không phải là số
nguyên tố.
 Hai số a và b được gọi là nguyên tố với nhau.
 Một số nguyên n > 1 bất kỳ đều có thể viết dưới dạng:
Trong đó  ,  ,  ,  là các số nguyên tố khác nhau, ,  ,  , 
làcác số mũ nguyên dương.
 Đây là dạng khai triển chính tắc của n
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
44
1.7. Cơ sở toán học của lý thuyết mật mã
 Định lý (1.7.1.1): Nếu b > 0 và b a thì gcd(a ,b) = b; Nếu a
= bq + r thì gcd(a,b) = gcd(b,r).
 Bội số chung bé nhất: m là bội số chung của a và b, và mọi
bội số chung của a và b đều là bội của m. m = lcm(a ,b)
 Với hai số nguyên dương a và b bất kỳ ta có quan hệ:
(, ).(, ) = .
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
45
1.7. Cơ sở toán học của lý thuyết mật mã
 Hai số nguyên a và b là đồng dư với nhau theo môđun n, và
viết a ≡ b (mod n), nếu (a−b) chia hết cho n.
 Hai số nguyên thuộc cùng một lớp tương đương khi và chỉ khi
chúng cho cùng một số dư nếu chia cho n.
 Mỗi lớp tương đương được đại diện bởi một số duy nhất trong
tập hợp: Zn = {0, 1, 2, 3,...., n -1} là số dư chung khi chia các
số trong lớp đó cho n.
 Ví dụ: với Z25 = {0, 1, 2, ..., 24},
1.7.2. Đồng dư và phương trình đồng dư tuyến tính
46
1.7. Cơ sở toán học của lý thuyết mật mã
 Cho a ∈ Zn . Một số nguyên x ∈ Zn được gọi là nghịch đảo
của a theo mod n , nếu a.x ≡ 1 (modn).
 Nếu có số x như vậy thì ta nói a là khả nghịch, và ký hiệu x là
a-1modn
 Phép chia trong Zn được định nghĩa như sau:
:  ( ) = .  ( )
 Phép chia chỉ thực hiện được khi b là khả nghịch theo
( )
1.7.2. Đồng dư và phương trình đồng dư tuyến tính
47
1.7. Cơ sở toán học của lý thuyết mật mã
 Phương trình đồng dư tuyến tính: là phương trình có
dạng
. ≡ ( )
trong đó a, b, n là các số nguyên, n > 0, x là ẩn số.
 Phương trình đó có nghiệm khi và chỉ khi  =
gcd (,  ), và khi đó nó có đúng  nghiệm theo
( )
1.7.2. Đồng dư và phương trình đồng dư tuyến tính
48
1.7. Cơ sở toán học của lý thuyết mật mã
 Định lý: Giả sử các số nguyên , ,  .,  là từng cặp nguyên tố
với nhau. Khi đó, hệ phương trình đồng dư tuyến tính sau có một
nghiệm duy nhất theo ( ).
1.7.2. Đồng dư và phương trình đồng dư tuyến tính
Với  = .  . ,  =


.
49
1.7. Cơ sở toán học của lý thuyết mật mã
 Tập  = { 0,1,2,  ,  − 1} thường được gọi là tập các
thặng dư đầy đủ theo modn, vì mọi số nguyên bất kỳ đều có
thể tìm được trong Zn một số đồng dư với mình (theo  
).
 Tập  là đóng đối với các phép tính cộng, trừ và nhân theo
 , nhưng không đóng đối với phép chia, vì phép chia cho
 theo   chỉ có thể thực hiện được khi  và  nguyên tố
với nhau, tức khi gcd (  ,  ) = 1.
 Tập các thặng dư thu gọn theo   được định nghĩa là tập

∗ = { ∈ : gcd ( , ) = 1} , tức 
∗ là tập con của 
bao gồm tất cả các phần tử nguyên tố với 
1.7.3. Thặng dư thu gọn và phần tử nguyên thuỷ
50
1.7. Cơ sở toán học của lý thuyết mật mã
 Tập  = { 0,1,2,  ,  − 1} thường được gọi là tập các thặng dư
đầy đủ theo  , vì mọi số nguyên bất kỳ đều có thể tìm được
trong Zn một số đồng dư với mình (theo   ).
 Tập  là đóng đối với các phép tính cộng, trừ và nhân theo  ,
nhưng không đóng đối với phép chia, vì phép chia cho  theo
  chỉ có thể thực hiện được khi  và  nguyên tố với nhau, tức
khi gcd (  ,  ) = 1.
 Tập các thặng dư thu gọn theo   được định nghĩa là tập 
∗ =
 { ∈ : gcd ( , ) = 1} , tức 
∗ là tập con của  bao gồm tất
cả các phần tử nguyên tố với 
 Nếu  là một số nguyên tố thì 
∗ = {1,2,  ,  − 1}.
1.7.3. Thặng dư thu gọn và phần tử nguyên thuỷ
51
1.7. Cơ sở toán học của lý thuyết mật mã
 Số các phần tử trong một nhóm là cấp () của nhóm đó.
 Một phần tử  ∈ 
∗ có cấp  , nếu m là số nguyên dương bé nhất
sao cho  = 1 trong 
∗
 Nhóm 
∗ có cấp () , và nếu  là số nguyên tố thì nhóm 
∗ có
cấp  − 1. khi đó ∀ ∈ 
∗ ∶   ≡ 1( )
 Nếu  có cấp  − 1, tức  − 1 là số mũ bé nhất thoả mãn công
thức trên, thì các phần tử , ,  .,   đều khác nhau và theo
 , chúng lập thành 
∗ là một nhóm cyclic và  là một phần tử
sinh, hay phần tử nguyên thuỷ của nhóm.
1.7.3. Thặng dư thu gọn và phần tử nguyên thuỷ
52
1.7. Cơ sở toán học của lý thuyết mật mã
Các tính chất của phần tử nguyên thủy:
1.7.3. Thặng dư thu gọn và phần tử nguyên thuỷ
53
1.7. Cơ sở toán học của lý thuyết mật mã
 Phương trình đồng dư bậc 2 là phương trình có dạng:
 ≡ ( )
trong đó  là một số nguyên dương,  là số nguyên với
gcd (, ) = 1,và  là ẩn số.
 Nếu phương trình có nghiệm thì  là thặng dư bậc 2 ( )
 Nếu phương trình vô nghiệm thì  là bất thặng dư bậc 2 ( )
 Tập các số nguyên nguyên tố với  được phân hoạch thành hai
tập con: tập  các thặng dư bậc hai   , và tập  các bất
thặng dư mod n
 Tiêu chuẩn Euler: Số  là thặng dư bậc hai ( ) nếu và
chỉ nếu 
 
 .
1.7.4. Phương trình đồng dư bậc hai và thặng dư bậc hai
54
1.7. Cơ sở toán học của lý thuyết mật mã
 Ký hiệu Legendre:  là một số nguyên tố lẻ, ∀ > 0, ký hiệu
 


được định nghĩa như sau:


= 
0, ℎ  ≡ 0( )
1, ℎ  ∈ 
− 1, ℎ  ∉  
  là thặng dư bậc hai   khi và chỉ khi


= 1
 Với mọi a ≥ 0, ta có:


= 
 
  
1.7.4. Phương trình đồng dư bậc hai và thặng dư bậc hai
55
1.7. Cơ sở toán học của lý thuyết mật mã
 Ký hiệu Jacobi: ∀ là một số nguyên lẻ, ∀ > 0, ký hiệu Jacobi


được
định nghĩa như sau: Giả sử  có khai triển chính tắc thành thừa số nguyên
tố là  = 
.
  
 thì


=



.






 Tính chất:
 Nếu  ≡    thì


=





= 
1 ℎ  ≡ ±1( 8)
− 1ℎ  ≡ ±3( 8)

.

=




 Nếu m và n đều là số lẻ, thì
1.7.4. Phương trình đồng dư bậc hai và thặng dư bậc hai
56
1.7. Cơ sở toán học của lý thuyết mật mã
 Không gian các sự kiện sơ cấp (hay không gian mẫu) Ω = {,   }
 Phân bố xác suất  trên Ω được định nghĩa là một tập các số thực không âm
 = { , ,  , }có tổng ∑ = 1.
 Số  được coi là xác suất của sự kiện sơ cấp .
 Tập con  ⊆ Ω được gọi là một sự kiện. Xác suất của sự kiện  được định
nghĩa bởi   = ∑ ()∈
 Cho  và  là hai sự kiện, với   > 0, xác suất có điều kiện của 
khi có  , (|) được định nghĩa là
1.7.5. Xác suất thống kê
Công thức Bayes
57
1.7. Cơ sở toán học của lý thuyết mật mã
 Giả sử  = ( ,  ,  ,  , ) là một hệ mật mã với điều kiện || = | | =
| | , tức các tập  ,  ,  có số các phần tử bằng nhau. Khi đó, hệ là bí mật
hoàn toàn nếu và chỉ nếu mỗi khoá  ∈  được dùng với xác suất bằng
nhau là 1/|| , và với mọi  ∈  ,  ∈  có một khoá duy nhất  ∈  sao
cho ( ) = 
1.7.6. Tính bí mật hoàn toàn của một hệ mật mã

File đính kèm:

  • pdfli_thuyet_mat_ma_chuong_1_tong_quan.pdf