Bài giảng Lý thuyết mật mã - Chương 1: Tổng quan - Đỗ Trọng Tuấn

i dạng một văn bản) từ một người gửi A đến
 một người nhận B.
 . A phải tạo cho văn bản đó một bản mã mật tương ứng.
 . B nhận được bản mã mật và sẽ có cách từ đó khôi phục lại
 văn bản rõ để hiểu được thông tin mà A muốn gửi cho
 mình.
 . A và B phải có một “chìa khóa chung” được gọi là
 “Khóa mật mã”
 17
 1.2. Khái niệm, mô hình của hệ mật
 Khóa mật mã
Bản tin rõ Mật mã hóa Bản tin mật Giải mã mật Bản tin rõ 
(Plaintext) (Encryption) (Ciphertext) (Decryption) (Plaintext)
 18
 1.2. Khái niệm, mô hình của hệ mật
 Thuật toán lập/giải mật mã: là thuật toán biến bản rõ,
 cùng với khóa mật mã, thành bản mã mật và ngược
 lại.
 Trong khoa học mật mã:
  Thuật toán lập/giải mật mã có thể không cần giữ bí mật.
  Giữ tuyệt mật: khóa mật mã
 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à Mật mã học (Cryptology) 
 thám mã
 . Thực hiện bài toán: “Tìm =
 chìa khóa mật mã” Mật mã (Cryptography) + 
 Không thể xây dựng một hệ mật Thám mã (Cryptanalysis)
 (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
 Hệ thống mật mã
 (Cryptosystem)
 Một sơ đồ hệ thống mật mã là một bộ năm
  = (, , , , )
 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ã
 21
 1.2. Khái niệm, mô hình của hệ mật
 Hệ thống mật mã
 (Cryptosystem)
 Một sơ đồ hệ thống mật mã là một bộ năm tham số
  = (, , , , )
  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: (()) = , ∀ ∈ 
 22
 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ó
     =    ()
     =    ()
 23
 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:
   =        =    = 
 24
 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 đó.
 25
 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:
 26
 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.
 27
 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”
 28
 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:
 29
 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:
 30
 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ý:
 31
 1.4. Các bài toán an toàn thông tin
privacy Tính riêng tư keeping information secret from all but those 
or confidentiality hoặc tính bí who are authorized to see it.
 mật
Data integrity Tính toàn vẹn ensuring information has not been altered by 
 dữ liệu unauthorized or unknown means.
Entity Nhận thực thực corroboration of the identity of an entity (e.g., a 
authentication thể hoặc định person, a
or identification danh computer terminal, a credit card, etc.).
Message Nhận thực bản corroborating the source of information; also 
authentication tin 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.
 32
 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 restricting access to resources to privileged 
 nhập entities
Certification Chứng nhận endorsement of information by a trusted entity
timestamping Nhãn thời recording the time of creation or existence of 
 gian 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
 33
 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- Chống sự từ preventing the denial of previous commitments 
repudiation chối or actions
Revocation Thu hồi retraction of certification or authorization
 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.
 35
1.5. Thám mã
 36
 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:
 37
 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:
 38
 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:
 39
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
  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.
 40
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
  Cho hai số nguyên bất kỳ a và b , b > 1
 41
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
  Ước số chung lớn nhất:
  = (, )
 42
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
  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
 43
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.1. SỐ HỌC CÁC SỐ NGUYÊN
  Đị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ệ:
 (, ). (, ) = . 
 44
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.2. Đồng dư và phương trình đồng dư tuyến tính
  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},
 45
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.2. Đồng dư và phương trình đồng dư tuyến tính
  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
 ( )
 46
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.2. Đồng dư và phương trình đồng dư tuyến tính
  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
 ( )
 47
 1.7. Cơ sở toán học của lý thuyết mật mã
1.7.2. Đồng dư và phương trình đồng dư tuyến tính
  Đị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 ( ).
 
 Với  =  .   .  ,  = .
    
 48
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.3. Thặng dư thu gọn và phần tử nguyên thuỷ
 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 
 49
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.3. Thặng dư thu gọn và phần tử nguyên thuỷ
 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}.
 50
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.3. Thặng dư thu gọn và phần tử nguyên thuỷ
 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.
 51
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.3. Thặng dư thu gọn và phần tử nguyên thuỷ
Các tính chất của phần tử nguyên thủy:
 52
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.4. Phương trình đồng dư bậc hai và thặng dư bậc hai
 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   .
 53
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.4. Phương trình đồng dư bậc hai và thặng dư bậc hai
 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ó: =    
 
 54
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.4. Phương trình đồng dư bậc hai và thặng dư bậc hai
 
 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ì
 55
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.5. Xác suất thống kê
 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à
 Công thức Bayes
 56
 1.7. Cơ sở toán học của lý thuyết mật mã
 1.7.6. Tính bí mật hoàn toàn của một hệ 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 ( ) = 
 57