MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon
tải về 1.46 Mb.
|
- Điều hướng trang này:
- Đ ị nh ngh ĩ a Entropy thông tin
- Định nghĩa mật mã đối xứng Đ ị nh ngh ĩ a
- Đ ị nh ngh ĩ a m ậ t mã kh ố i
- Đ ị nh ngh ĩ a mã dòng.
- Các lệnh dùng để xây dựng thuật toán mật mã đối xứng
- Lệnh hoбn đổi Đ ị nh ngh ĩ a
- Tiкu chu ẩ n xвy d ự ng nкn l ệ nh hoбn đ ổ i
- L ệ nh thay th ế . Đ ị nh ngh ĩ a
- Tiкu chн đ ể xвy d ự ng nкn l ệ nh thay th ế
- Mạng hoán vị thay thế
- Lệnh Gamma dành cho mã dòng
| Chương 7
MẬT MÃ KHÓA ĐỐI XỨNG
Nhiều người cho rằng kỷ nguyên của mật mã học hiện đại được bắt đầu với Claude Shannon, người được coi là cha đẻ của mật mã toán học. Năm 1949 ông đã công bố bài Lý thuyết về truyền thông trong các hệ thống bảo mật (Communication Theory of Secrecy Systems) trên tập san Bell System Technical Journal - Tập san kỹ thuật của hệ thống Bell - và một thời gian ngắn sau đó, trong cuốn Mathematical Theory of Communication - Lý thuyết toán học trong truyền thông - cùng với tác giả Warren Weaver. Những công trình này, cùng với những công trình nghiên cứu khác của ông về lý thuyết về tin học và truyền thông (information and communication theory), đã thiết lập một nền tảng lý thuyết cơ bản cho mật mã học và thám mã học. Với ảnh hưởng đó, mật mã học hầu như bị thâu tóm bởi các cơ quan truyền thông mật của chính phủ, chẳng hạn như NSA, và biến mất khỏi tầm hiểu biết của công chúng. Rất ít các công trình được tiếp tục công bố, cho đến thời kỳ giữa thập niên 1970, khi mọi sự được thay đổi. Claude Shannon xem xét mô hình 7.1, ở đây nguồn bản tin sinh ra bản rõ X, nguồn khóa tạo ra khóa K, khóa K được truyền qua kênh mật từ nơi truyền đến nơi nhận. Quá trình mã hóa biến đổi bản rõ X nhờ khóa thành bản mã Y: Quá trình giải mã, biến đổi bản mã nhận được Y thành bản rõ X cũng nhờ khóa K: Tội phạm (hay thám mã) sẽ tìm cách nhận được bản rõ và khóa trên cơ sỡ bản mã. Claude Shannon xem xét các câu hỏi lý thuyết và thực hành mật. Để nhận được lý thuyết mật Shannon hình thành các câu hỏi sau:
Để trả lời câu hỏi của Shannon chúng ta đưa vào định nghĩa “tuyệt mật” với sự hổ trợ các điều kiện sau: Bản mã thu được không đêm đến cho thám mã bất kỳ thông tin nào. Theo định lэ Bayes 
Hình 7.1. Mô hình truyền tin Shannon Với P(X) là xác suất xuất hiện bản tin X; Để chống lại phương phбp phвn tнch thống kк bản mг (đвy lа một cбch thбm mг) Shannon đề ra hai phương phбp: khuyết tбn vа pha trộn.
Lý thuyết về thông tin sẽ trình bày đầy đủ hơn về Entropy, ở đây chúng tôi chỉ đưa ra cái cơ bản. Claude E. Shannon đã xây dựng định nghĩa về entropy để thoả mãn các giả định sau:
Shannon cũng chỉ ra rằng bất cứ định nghĩa nào của entropy, cho một tín hiệu có thể nhận các giá trị rời rạc, thoả mãn các giả định của ông thì đều có dạng:
Với K là một hằng số, chỉ phụ thuộc vào đơn vị đo; n là tổng số các giá trị có thể nhận của tín hiệu; i là giá trị rời rạc thứ i; p(i) là xác suất xuất hiện của giá trị i; Nếu một sự kiện ngẫu nhiên rời rạc x, có thể nhận các giá trị là 1..n, thì entropy của nó là:
với p(i) là xác suất xảy ra của giá trị i. Entropy thông tin trong trường hợp phần tử tín hiệu ngẫu nhiên rời rạc còn được gọi là entropy Shannon.
Định nghĩa. Mật mã đối xứng là hệ mật mà quá trình mã hóa và quá trình giải mã dùng chung một khóa mật, và việc bảo mật bản tin phụ thuộc vào quá trình lưu khóa mật. Sơ đồ tổng quát của hệ mã đối xứng được miêu tả ở hình 7.2. Hình 7.2. Sơ đồ mật mã đối xứng ở đây bản tin nguồn X là thông tin cần mã để bảo mật, trước khi chuyển đến nơi nhận nó phải được mã hóa bằng hàm mã hóa E, hàm mã hóa E là tổng hợp các phép biến đổi với sự tham gia của khóa mật K; qua biến đổi của hàm E chúng ta thu được bản mã Y; bản mã Y truyền qua kênh thông tin đến nơi người cần nhận, ở nơi nhận với sự giúp đở của quá trình giải mã và khóa mật K, sẽ giải bản mã Y thành bản tin X ban đầu. Chъ э, nếu như khуa K khфng đъng, hoặc bản mг Y bị biến đổi trong quб trмnh truyền thм quб trмnh giải mг khфng thể thu được bản tin ban đầu X. Như đã nói, mật mã đối xứng được chia ra làm hai phần, mật mã khối và mật mã dòng. Chúng ta xem định nghĩa về chúng.
ở đây F là hàm mã hóa hay giải mã. Định nghĩa mã dòng. Là một hệ mã đối xứng, trong đó từng ký tự của bản rõ được biến đổi thành ký tự của bản mã phụ thuộc không chỉ vào khóa sử dụng mà còn vào vị trí của nó trong bản rõ. Mã khối thì chia bản rõ ra các khối bằng nhau rồi thực hiện mã, nên sẽ có một số khối giống nhau mã cùng một khóa, ở mã dòng thì không như vậy.
Hầu như tất cả các hệ mật đối xứng đảm bảo bảo mật thông tin thường được xây dựng trên cơ sở các lệnh cơ sở sau:
Định nghĩa. Đвy lа phương phбp biến đổi mật mг đơn giản, lа một phйp hoбn đổi cбc vị trн của cбc kн tự trong bản rх theo một quy luật nаo đу. Chъng ta cу thể biểu diễn chъng bằng toбn học như sau: Hoбn đổi ,
ở đвy hang đầu tiкn lа vị trн kэ tự của bản rх, hang thứ 2 lа cбc vị trн mа kэ tự ban đầu cần hoбn đổi tương ứng, Vн dụ:
Tập hợp tất cả cбc lệnh hoбn đổi Cу nhiều cбch biểu diễn lệnh hoбn vị. Vн dụ như từ vн dụ trкn ta cу cбc cбch biểu diễn sau:
Chъng ta thấy lệnh hoбn đổi như một hаm, tham số của nу lа số nguyкn, hаm nаy cу thể kэ hiệu Tiкu chuẩn xвy dựng nкn lệnh hoбn đổi: Chъng ta phải xвy dựng lệnh hoбn đổi sao cho đạt được độ phбt tбn tốt, nhằm tăng hiệu ứng thбc lũ.
Định nghĩa.Trong mật mг, lệnh thay thế cу thể hiểu lа một qъa trмnh thay một số phần tử nаy bằng một số phần tử khбc, hay nуi cбch khбc lа thay thế một kэ tự hay một nhуm kэ tự của bản tin bằng một kэ tự hay một nhуm kэ tự khбc. Theo toбn học thм chъng ta cу thể định nghĩa như sau: Lệnh thay thế S lа một бnh xạ s: Đối với Với Vн dụ lệnh thay thế 2 bit nаy thаnh 2 bнt khбc:
Tuy nhiкn một số phйp thay thế cу thể biểu diễn ở dạng khбc như đồ thị, dщng hаm số…vv. Tiкu chн để xвy dựng nкn lệnh thay thế: Khi sử dụng lệnh thay thế phải cу được cбc tнnh chất: Bậc đại số cao, cу độ phi tuyến tнnh lớn, tạo ra tнnh tнnh pha trộn bнt vа phбt tбn bнt tốt.
Kết hợp lệnh hoán vị và lệnh thay thế, có thể xây dựng nên mạng hoán vị thay thế. Đây là cấu trúc xen kẻ nhiều lớp mỗi lớp kết hợp phép thay thế và phép hoán vị. Với mạng thay thế hoán vị, có thể tạo cho thuật toán có độ phân tán vào xáo trộn rất tố. Chúng ta tìm ví dụ mạng hoán vị thay thế được miêu tả ở hình 7.3, đầu vào là 32 bít qua mạng chuyển vị 4 lớp, mỗi lớp gồm 8 bảng thay thế 4 bít cho 4 bít, các bảng này có thể khác nhau, sau phép thế là phép hoán vị.
Hình 7.3.Mạng hoán vị thay thế S_BOX 32/22 Để tạo ra mạng hoán vị, chúng ta cần tính toán đến hiệu quả thác lũ để chọn ra cách xây dựng như ý.
Nguyên lý cơ bản của mã dòng là tạo ra chuỗi khóa, cũng thường hay gọi là tạo ra khóa dòng hay khóa dịch hay gamma được cho bằng chuỗi bít … Chuỗi bít này sẽ cộng với chuỗi bít bản rõ để nhận được chuỗi bản mã:
Ở bкn nhận bản mг sẽ cộng bản mг với cщng chuỗi khуa đу để khфi phục lại bản mг ban đầu:
Sự vững chắc của hệ mг phụ thuộc hoаn toаn vаo cấu trъc bкn trong sinh ra chuỗi khуa. Nếu việc sinh ra khфng tạo ra chuỗi với chu kỳ lớn thм hệ sẽ khфng vững chắc. Cу thể biểu diễn bằng sơ đồ sau quб trмnh mг vа giải mг tương ứng ở hмnh 7.4 vа 7.5.
|