Bài 2: Cơ sở toán học – Lý thuyết thông tin và độ phức tạp trong

0
22
An toàn và bảo mật thông tin mở đầu
An toàn và bảo mật thông tin mở đầu

Như ở bài trước chúng ta đã hiểu phương pháp an toàn thông tin bằng mật mã. Để hiểu được những thuật toán được sử dụng trong mật mã học, trong chữ ký số cũng như các giao thức mật mã, ta cần hiểu những nền tảng cơ bản về toán học, lý thuyết thông tin, … được sử dụng trong mật mã học.

Ở bài này sẽ chia chủ yếu làm 2 phần:

  • Lý thuyết về thông tin, độ phức tạp của thuật toán, độ an toàn của thuật toán.
  • Một số kiến thức toán học như: phép chia lấy dư (modulo), số nguyên tố, phần dư trung hoa, …

Ở bài này sẽ trình bày một số lý thuyết rườm rà mà trong tài liệu nói khá rõ nhưng mình lười soạn lại.

Lý thuyết thông tin

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ố bít nhỏ nhất cần thiết để mã hoá tất cả những nghĩa có thể 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 bits thông tin, bởi vì thông tin ngày có thể mã hoá với 3 bít dữ liệu: 000 = Sunday; 001 = Monday; 010 = Tuesday; 011 = Wednesday; 100 = Thursday; 101 = Friday; 110 = Saturday; 111 is unused

Nếu thông tin này được biểu diễn bởi chuỗi ký tự ASCII tương ứng, nó sẽ chiếm nhiều không gian nhớ hơn, nhưng cũng không chứa nhiều thông tin hơn. Tương tự như trường gioi_tinh của một cơ sở dữ liệu chỉ chứa 1 bits thông tin, nó có thể lưu trữ như một trong hai xâu ký tự ASCII : Nam, Nữ.

Xem thêm tại: https://vi.wikipedia.org/wiki/Lý_thuyết_thông_tin

Tính an toàn của hệ thống mã hoá

Shannon định nghĩa rất rõ ràng, tỉ mỉ các mô hình toán học để đánh giá độ an toàn của các hệ mã mật sử dụng. Shannon phát triển lý thuyết cho rằng, hệ thống mã hoá chỉ an toàn tuyệt đối nếu số khoá có thể sử dụng ít nhất phải bằng số thông báo có thể. Hiểu theo một nghĩa khác, khoá tối thiểu cảu hệ mật phải dài bằng thông báo của hệ mật đó.

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à.

  • Kỹ thuật lộn xộn (Confusion): che dấu mối quan hệ giữa bản rõ và gốc. Kỹ thuật này làm thất bại các cố gắng nghiên cứu bản mã để tìm kiếm thông tin dư thừa và thống kê mẫu. Phương pháp dễ nhất để thực hiện điều này là thông qua kỹ thuật thay thế. Một hệ mã hoá thay thế đơn giản, chẳng hạn hệ mã dịch vòng Caesar, dựa trên nền tảng của sự thay thế các chữ cái của bản rõ, nghĩa là chữ cái này được thay thế bằng chữ cái khác.
  • Kỹ thuật rườm rà (Diffusion): làm mất đi sự dư thừa của bản rõ bằng cách tăng sự phụ bản mã vào bản rõ (và khóa). Công việc tìm kiếm sự dư thừa của người thám mã sẽ rất mất thời gian và phức tạp. Cách đơn giản nhất tạo ra sự rườm rà là thông qua việc đổi chỗ (hay còn gọi là kỹ thuật hoán vị).

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.

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ã hoá khác nhau.

Lý thuyết thông tin đã cho chúng ta biết rằng một thuật toán mã hoá 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ã mật.

Độ an toàn tính toán

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 đó.

Độ an toàn không điều kiện

Định lý Shannon

Giả sử (P, C, K, E, D) là một hệ mật, khi đó hệ mật đạt được độ mật hoàn thiện khi và chỉ khi |K| ≥ |C|. Trong trường hợp |K| = |C| = |P|, hệ mật đạt độ mật hoàn thiện khi và chỉ khi mỗi khoá K được dùng với xác suất bằng nhau, bằng 1/|K| và với mỗi x ∈ P, mỗi y ∈ C có một khoá K duy nhất sao cho eK(x) = y. [5]

Tài liệu tham khảo:

  • [1] Giáo trình An toàn và bảo mật thông tin, Trường Đại học Hàng hải – Hải Phòng, 2008.
  • [2] Tài liệu tự biên soạn và sưu tầm.

Nguồn: Nam. Name. Vn