Chưa có bài trả lời

[thuvientoanhoc]

Phép hoán vị, chỉnh hợp, tổ hợp có nhiều ứng dụng trong toán học. Bài này giới thiệu một ứng dụng đơn giản của phép hoán vị để mã hoá giữ được bí mật khi chuyển tin.
Theo định nghĩa thì số hoán vị của n số tự nhiên đầu tiên (kí hiệu Pn) được sát định bởi công thức:
Pn=n!=1*2*3*...*(n-1)*n
Tích số trên chính là số các cách sắp xếp khác nhau của n số tự nhiên đầu tiên, mỗi cách sắp xếp là một hoán vị. Ví dụ với n = 3 ta có 3! = 1*2*3 = 6 cách sắp xếp (đổi chỗ) bộ ba số (1 2 3) như sau : (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 2 1), (3 1 2).
Cách đầu tiên là giữ nguyên vị trí ban đầu (phép hoán vị đồng nhất hoặc phép thế đồng nhất).
2. Người ta có thể dùng 5 phép hoá vị trên của 3 ký tự (trừ hoán vị đồng nhất) làm khoá mã để mã hoá bản tin nhằm giữ bí mật bản tin này, không cho người ngoài cuộc biết.
Ví dụ : Hùng muốn gửi cho Dũng bản tin T sau đây:
T = TRAM NAM TRONG COI NGUOI TA và dùng hoá vị (2 3 1) làm khoá mã:
Để tránh nhầm lẫn, người ta viết lại bản tin thành từng nhóm 3 ký tự tương ứng như ở dưới đây, được bản tin
R = TRA MNA MTR ONG COI NGU OIT AXX
R = 123 123 123 123 123 123 123 123
(2 chữ XX được thêm vào cuối bản tin cho đủ nhóm 3). Sau đó đổi chỗ các ký tự theo khoá mã là hoán vị (2 3 1) sẽ thu được bản mã
M = RAT NAM TRM NGO OIC GUN ITO XXA
M = 123 123 123 123 123 123 123 123
Nếu hoán vị khác làm khoá mã thì cùng bản tin trên ta sẽ thu được bản mã khác. Không biết khoá mã thì không đọc được bản mã này.
3. Bằng cách nào đó Hùng đã báo cho Dũng biết khoá đã dùng để mã hoá tin, do đó khi nhận được bản mã, Dũng phải dùng khoá dịch mã (ngược lại với khoá mã ) để chuyển bản mã M thành tin T. Từ khoá mã (2 3 1), Dũng tìm được khoá dịch mã như sau:
Khoá mã:
1 2 3 <=> 2 3 1
Khoá dịch mã:
1 2 3 <=> 3 1 2
Đặt hoán vị (3 2 1) vào bản mã M rồi thực hiện phép đổi chỗ thẻo khoá dịch mã (1 thành 3, 2 thành 1, 3 thành 2) ta thu được bản tin R rồi thực hiện ngắt chữ thì được bản tin T.
M = RAT NAM TRM NGO OIC GUN ITO XXA
312 312 312 312 312 312 312 312
R = TRA MNA MTR ONG COI NGU OIT AXX
T = TRAM NAM TRONG COI NGUOI TA XX

Dũng đã đọc được bản tin mà Hùng đã gửi cho.
Nếu n lớn hơn thì số hoán vị khác nhau càng lớn, tức là số khoá để lựa chọn càng nhiều, do đó độ phức tạp của bản mã càng cao, cũng có nghĩa là độ bảo mất bản tin càng cao hơn.
Ngày nay, có máy vi tính, người ta đã ứng dụng phép hoán vị để lập ra các khoá mã rất phức tạp, có độ bảo mật cao, ví dụ như hệ thống mã với khoá mã công khai (Public Key Cryptosystem)
------------
Thu vien Toan hoc
http://thuvientoanhoc.com
http://mathlib.info