MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon



tải về 1.46 Mb.
trang1/5
Chuyển đổi dữ liệu30.08.2016
Kích1.46 Mb.
  1   2   3   4   5
Chương 7

MẬT MÃ KHÓA ĐỐI XỨNG


  1. Lý thuyết cơ bản của Shannon

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 bo 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 hc 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:



  1. Hệ thống ổn định ở mức độ nào, nếu như thám mã không giới hạn thời gian và có tất cả các thiết bị cần thiết đối với việc phân tích bản mã?

  2. Bản mã liệu có một nghiệm duy nhất hay không?

  3. Với lượng thông tin bản mã bao nhiêu mà thám mã cần thu nhặt để nghiệm trở nên duy nhất?

Để 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; xác suất điều kiện, xuất hiện bản mã Y với điều kiện bản tin X đã được chọn, có nghĩa là tổng xác suất của tất cả các khóa, mà các khóa này chuyển bản tin X tương ứng với bản mã Y; P(Y)-xác suất nhận được bản mã Y; là xác suất nhận được bản rõ X với điều kiện nhặt được bản mã Y. Để “tuyệt mật” thì giá trị của cần phải bằng nhau với tất cả giá trị của X và Y.

Để 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.

Đnh ngha Entropy thông tin. Entropy thông tin mô tả mức độ hỗn lon trong một tín hiệu lấy từ một sự kiện ngẫu nhiên. Nói cách khác, entropy cũng chỉ ra có bao nhiêu thông tin trong tín hiệu, với thông tin là các phần không hỗn loạn ngẫu nhiên của tín hiệu.

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:

  1. Entropy phải t lệ thuận liên tc với các xác suất xuất hiện của các phần tử ngẫu nhiên trong tín hiệu. Thay đổi nhỏ trong xác suất phải dẫn đến thay đổi nhỏ trong entropy.

  2. Nếu các phần tử ngẫu nhiên đều có xác suất xuất hiện bằng nhau, việc tăng số lượng phần tử ngẫu nhiên phải làm tăng entropy.

  3. Có thể tạo các chuỗi tín hiệu theo nhiều bước, và entropy tổng cộng phải bằng tổng có trọng số của entropy của từng bước.

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


  1. Định nghĩa mật mã đối xứng

Đnh ngha. 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.

Đnh ngha mật mã khối. Mã khối là tổ hợp lệnh toán học (hoán vị, thay thế,…) biến đổi dãy N bit thành một dãy N bit với sự tham gia của khóa mật k từ không gian khóa K, có thể viết dưới dạng

,

ở đây F là hàm mã hóa hay giải mã.



Đnh ngha 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.

  1. Các lệnh dùng để xây dựng thuật toán mật mã đối xứng

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:

      1. Lệnh hoбn đổi

Đnh ngha. Đв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 của tập hữu hạn , với gồm n phần tử, lа một đơn бnh từ tậpvаo tập,, lệnh hoбn đổi cу dạng sau:



,

ở đв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,khi ), tức lа vị trн thứ đổi cho vị trн thứ , vị trн thứ đổi cho vị trн thứ tương tự như thế. Giб trị n gọi lа chiều dаi hoбn đổi.

Vн dụ:

.

Tập hợp tất cả cбc lệnh hoбn đổi kэ hiệu lа , vа rх rаng rằng .

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 ,với .



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

      1. Lệnh thay thế.

Đnh ngha.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:, với lа tập hữu hạn vа với , tồn tại duy nhất một phần tử .

Đối với lệnh hoбn đổi cу dạng:

,

Với . Cбc giб trị khфng bắt buộc lа khбc nhau.

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.

      1. Mạng hoán vị thay thế

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ư ý.


      1. Lệnh Gamma dành cho mã dòng

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.
Hình 7.4. Quá trình mã hóa gamma
Hình 7.5. Quá trình giải mã gamma


  1. : files -> FileMonHoc
    FileMonHoc -> NGÂn hàng câu hỏi lập trình cơ BẢn nhóm câu hỏI 2 ĐIỂM
    FileMonHoc -> CHƯƠng 2 giới thiệu về LÝ thuyết số
    FileMonHoc -> CÁc hệ MẬt khoá CÔng khai kháC
    FileMonHoc -> BỘ MÔn duyệt chủ nhiệm Bộ môn
    FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
    FileMonHoc -> Chủ nhiệm Bộ môn Ngô Thành Long ĐỀ CƯƠng chi tiết bài giảNG
    FileMonHoc -> Chủ nhiệm Bộ môn Phan Nguyên Hải ĐỀ CƯƠng chi tiết bài giảNG
    FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
    FileMonHoc -> Khoa công nghệ thông tin bài giảng LẬp trình cơ BẢn biên soạn
    FileMonHoc -> Khoa cntt cộng hòa xã HỘi chủ nghĩa việt nam


  1   2   3   4   5


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2019
được sử dụng cho việc quản lý

    Quê hương