Tài liệu Truyền và bảo mật thông tin

  • Số trang: 98 |
  • Loại file: PDF |
  • Lượt xem: 373 |
  • Lượt tải: 3
Itteen

Đã đăng 56 tài liệu

Mô tả:

Truyền và bảo mật thông tin
Tài liệu tham khảo 1. TRUYỀN VÀ BẢO MẬT THÔNG TIN Nguyễn Văn Khang – Khoa Tin học, ĐHSP Huế nguyenvankhang@dhsphue.edu.vn 2. 3. 4. 5. 6. 7. 8. Phan Đình Diệu. Lý thuyết mật mã và An toàn thông tin, Đại học Quốc Gia Hà Nội Nguyễn Hữu Tuân, 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 TS. Lê Quy ết Thắng, ThS. Phan Tấn Tài, Ks. Dương Văn Hiếu, Giáo trình lý thuyết thông tin. Douglas R. Stinson. Cryptography Theory and practice. CRC Press. 1995. David J.C. Mackey, Information Theory, Infernce, and Learning Algorithms, CamBridge University Express-2003. G.J.ChaiTin, Algorithmic Information Theory, CamBridge University Express-1992. Sanford Goldman, Information Theory. Truyền và bảo mật thông tin 2 Phần I. Thông tin và truyền thông tin Chương I. MỞ ĐẦU Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 1 Thông tin „ „ „ „ „ Thông tin Thông tin là một khái niệm trừu tượng, khó định nghĩa chính xác. Hai định nghĩa về thông tin tiêu biểu: Thông tin là sự cảm hiểu của con người về thế giới xung quanh thông qua sự tiếp xúc với nó. Thông tin là một hệ thống những tin báo và mệnh lệnh giúp loại trừ sự không chắc chắn (uncertainty) trong trạng thái của nơi nhận tin. Nói ngắn gọn, thông tin là cái mà loại trừ sự không chắc chắn. Định nghĩa đầu chưa nói lên được bản chất của thông tin. Định nghĩa thứ hai nói rõ hơn về bản chất của thông tin và được dùng để định lượng thông tin trong kỹ thuật. Truyền và bảo mật thông tin „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế „ „ „ Thông tin là cái được truyền từ đối tượng này đến đối tượng khác để báo một “điều” gì đó. Thông tin chỉ có ý nghĩa khi “điều” đó bên nhận chưa biết. Thông tin xuất hiện dưới nhiều dạng âm thanh , hình ảnh, ... Những dạng này chỉ là “vỏ bọc” vật chất chứa thông tin. “Vỏ bọc” là phần “xác”, thông tin là phần “hồn”. Ngữ nghĩa của thông tin chỉ có thể hiểu được khi bên nhận hiểu được cách biểu diễn ngữ nghĩa của bên phát. Một trong những phương tiện để diễn đạt thông tin là ngôn ngữ . Có hai trạng thái của thông tin: truyền và lưu trữ . Môi trường truyền/lưu trữ được gọi chung là môi trường chứa tin hay kênh tin. Truyền và bảo mật thông tin 6 Mô hình quá trình truyền tin Lý thuyết thông tin nghiên cứu quá trình xử lý tín hiệu như sau: Đầu vào (input): nhận tín hiệu từ một lĩnh vực cụ thể, tức là tín hiệu xuất hiện theo các ký hiệu (symbol) từ một tập hợp cho trước và theo phân phối xác suất đã biết. Tín hiệu được truyền đi trên kênh truyền (channel) và có thể bị nhiễu cũng theo một phân phối xác suất nào đó. Truyền và bảo mật thông tin „ 5 Mô hình quá trình truyền tin „ „ „ „ „ 7 Kênh truyền có thể được hiểu dưới hai nghĩa: Dưới nghĩa vật lý: kênh truyền là một hệ thống truyền tín hiệu (dây dẫn, mạch, sóng, ...) và gây nhiễu tùy thao chất lượng của hệ thống. Dưới nghĩa toán học: kênh truyền là các phân phối xác suất xác định trên lớp các tín hiệu đang xét ở đầu nhận tín hiệu (output). Truyền và bảo mật thông tin 8 2 Mô hình quá trình truyền tin „ „ Mô hình quá trình truyền tin Nguồn tin (information source): Là một tập hợp các tin mà hệ thống truyền tin dùng để lập các bảng tin hay thông báo (message) để truyền tin. Các tín hiệu như âm thanh, hình ảnh.. Là các hàm liên tục theo thời gian, nguồn tin như thế gọi là nguồn liên tục (continuous source), các tin đó được gọi là tin liên tục (continuous information) và kênh tin được gọi là kênh liên tục (continuous channel). „ „ „ 9 Truyền và bảo mật thông tin Mô hình quá trình truyền tin „ „ Truyền và bảo mật thông tin 10 Mô hình quá trình truyền tin Rời rạc hóa: Thường một trong hai loại: Rời rạc hoá theo trục thời gian, còn được gọi là lấy mẫu (sampling) và rời rạc hoá theo biên độ , còn được gọi là lượng tử hoá (quantize). Lấy mẫu Các tín hiệu như điện tín, các lệnh điều khiển…là rời rạc theo thời gian, nguồn tin như thế gọi là nguồn rời rạc (discrete source), các tin đó được gọi là tin rời rạc (discrete information) và kênh tin được gọi là kênh rời rạc (discrete channel). Các hệ thống liên tục có nhiều nhược điểm như cồng kềnh, không hiệu quả , và chi phí cao. Các hệ thống truyền tin rời rạc có nhiều ưu điểm hơn, khắc phục được những nhược điểm trên của các hệ thống liên tục và đặ c biệt đang ngày càng được phát triển và hoàn thiện dần. Æ Rời rạc hóa các kênh liên tục „ „ Nguồn tin liên tục sau khi được lấy mẫu và lượng tử hoá sẽ trở thành nguồn rời rạc . Chúng ta học chủ yếu các nguồn rời rạc. Lượng tử hóa Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 11 Truyền và bảo mật thông tin 12 3 Lượng tin biết và chưa biết Mô hình quá trình truyền tin „ Lý thuyết thông tin được xét ở đây theo quan điểm của Shannon. Đối tượng nghiên cứu là một hệ thống liên lạc truyền tin (communication system) như sơ đồ dưới đây: „ „ „ „ „ Truyền và bảo mật thông tin 13 Lượng tin biết và chưa biết „ „ „ „ „ Đồng tiền loại 1 (hay đồng tiền thật): đồng chất có 1 mặt có đầu hình. Đồng tiền loại 2 (hay đồng tiền giả ): đồng chất, mỗi mặt đều có 1 đầu hình. Mặc dù người tổ chức chơi có thể “ăn gian” nhưng quá trình trao đổi 2 đồng tiền cho nhau là ngẫu nhiêu Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 14 Lượng tin biết và chưa biết Ta xét ví dụ trò chơi tung một đồng tiền “có đầu hình – không có đầu hình”. Tuy nhiên người tổ chức chơi có thể “ăn gian” bằng cách sử dụng 2 đồng tiền “Thật- Giả” khác nhau sau: „ Một biến ngẫu nhiên (BNN) X luôn mang một lượng tin nào đó. Nếu X chưa xảy ra thì X có một lượng tin chưa biết. Nếu X đã xảy ra thì lượng tin về biến X coi như đã biết hoàn toàn. Nếu biết thông tin của một BNN X thông qua BNN Y đã xảy ra thì ta có thể nói: chúng ta chỉ biết một phần lượng thông tin của X đó trên cơ sở biết Y. 15 „ Ta thử xét một trường hợp sau: nếu người chơi lấy ngẫu nhiên 1 đồng tiền và sau đó thực hiện việc tung đồng tiền đó 2 lần. Qua 2 lần tung đồng tiền, ta đếm được số đầu hình xuất hiện. Dựa vào số đầu hình xuất hiện, ta có thể phán đoán được người tổ chức chơi đã lấy được đồng tiền nào. Truyền và bảo mật thông tin 16 4 Lượng tin biết và chưa biết „ Lượng tin biết và chưa biết Chẳng hạn: Nếu số đầu hình đếm được sau 2 lần tưng là 1 thì đồng tiền đã lấy được là đồng tiền thật. Ngược lại nếu số đầu hình đếm được là 2 thì đồng tiền đã lấy được có thể là thật hay cũng có thể là giả. Như vậy, ta đã nhận được một phần thông tin về loại đồng tiền qua số đầu hình đếm được sau 2 lần tung. Truyền và bảo mật thông tin „ „ Dưới đây là một số bảng phân phối của bài toán trên: Gọi BNN X về loại đồng tiền (X=1 hoặc 2). Khi đó phân phối của X có dạng: 17 Lượng tin biết và chưa biết „ „ Truyền và bảo mật thông tin Bài tập Đặt BNN Y là BNN về số đầu hình đếm được sau 2 lần tung. Khi đó ta có thể xác định được phân phối của Y với điều kiện xảy ra của X trong 2 trường hợp sau: Tìm phân phối của Y? Tính XS X=1 khi Y=2? Nhớ lại: „ „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 18 19 Định lý Bayes Nếu p(y) > 0 thì: Truyền và bảo mật thông tin 20 5 Định lý cơ sở của kỹ thuật truyền tin „ Trong “ A New Basic of Information Theory (1954)”, Feinstein đã đưa ra định lý sau: “Trên một kênh truyền có nhiễu, người ta luôn có thể thực hiện một phương pháp truyền sao cho đạt được sai số nhỏ hơn sai số cho phép (nhỏ bất kỳ) cho trước đối với kênh truyền.” Truyền và bảo mật thông tin „ „ Giả sử, một thông báo được truyền cần truyền được mã hóa thành dãy số nhị phân (0,1). Giả sử 1 bit truyền trên kênh nhiễu với xác suất ¼ Người ta có thể làm giảm sai lầm khi nhận tin bằng cách truyền lặp lại 1 bit với số lẻ lần Ví dụ: truyền lặp lại 3 cho 1 bit cần truyền 21 Minh họa kỹ thuật giảm nhiễu „ Minh họa kỹ thuật giảm nhiễu Truyền và bảo mật thông tin Minh họa kỹ thuật giảm nhiễu Sơ đồ truyền tin: „ „ Chứng minh, với cách truyền này sai số nhỏ hơn ¼: Giả sử Xi xác định giá trị đúng hay sai của bit thứ i: „ „ „ Xi =1 nếu bit thứ i nhận được là sai và Xi =0 nếu bit thứ i nhận được là đúng. Theo giả thiết ban đầu của kênh truyền thì phân phối xác suất của Xi có dạng Bernoulli b(1/4): Xi P „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 22 23 1 3/4 0 1/4 Gọi Y ={X1 + X2 + X3 } là tổng số bit nhận sai sau 3 lần truyền lặp cho 1 bit =>này Y tuân theo phân phối Nhị thức B(p,n), với p=1/4 (xác suất truyền sai một bit) và q =3/4 (xác suất truyền đúng 1 bit) Truyền và bảo mật thông tin 24 6 Chi phí phải trả cho kỹ thuật giảm nhiễu Minh họa kỹ thuật giảm nhiễu „ Truyền và bảo mật thông tin Theo cách thức lặp lại như trên, ta có thể giảm sai lầm bao nhiêu cũng được (lặp càng nhiều thì sai càng ít), nhưng thời gian truyền cũng tăng lên và chi phí truyền cũng sẽ tăng theo. 25 Truyền và bảo mật thông tin 26 Khái niệm về dung lượng kênh truyền „ „ „ Cần phải xác định một thông số cho truyền tin để đảm bảo sai số chấp nhận được và đồng thời tốc độ truyền cũng không quá chậm. Khái niệm “dung lượng” cho phép xác định tốc độ truyền tối đa của mỗi kênh truyền. Do đó, dựa vào dung lượng kênh truyền, người ta có thể chỉ ra tốc độ truyền tin đồng thời với một phương pháp truyền có sai số cho phép. Quá trình truyền tin cần có quá trình sinh mã bằng thiết bị sinh mã (Coding device/ Encoder) và quá trình giải mã nhờ thiết bị giải mã (Decoding device/ Decoder) Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Chương II. ĐỘ ĐO LƯỢNG TIN 27 7 II.1. Entropy „ „ Entropy của một sự kiện Khái niệm entropy Entropy là một đại lượng toán học dùng để đo lượng tin không chắc (hay lượng ngẫu nhiên) của một sự kiện hay của phân phối ngẫu nhiên cho trước. „ „ „ Truyền và bảo mật thông tin 29 „ „ „ „ „ Xét biến ngẫu nhiên X có phân phối: x2 x3 … xM X | x1 P | p1 p2 p3 … pM Nếu gọi Ai là sự kiện X=xi, (i=1,2,3,..) thì Entropy của Ai là: h(Ai)= h(pi) Gọi Y=h(X) là hàm ngẫu nhiên của X và nhận các giá trị là dãy các Entropy của các sự kiện X=xi,tức là Y=h(X)={h(p1), h(p2), …, h(pn)}. Entropy của X chính là kỳ vọng toán học của Y=h(X) có dạng: H(X)=H(p1, p2, p3, …,pn) = p1h(p1)+p2h(p2)+…+pnh(pn). Tổng quát: Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 30 Tiên đề 3 Tính chất của Entropy phân phối Entropy của một phân phối „ Giả sử có một sự kiện A có xác suất xuất hiện là p. Khi đó, ta nói A có một lượng tin không chắc chắn được đo bởi hàm số h(p) với p ⊆ [0,1]. Hàm h(p) được gọi là Entropy nếu nó thoả 2 tiên đề toán học sau: Tiên đề 1: h(p) là hàm liên tục không âm và đơn điệu giảm. Tiên đề 2: nếu A và B là hai sự kiện độc lập nhau, có xác suất xuất hiện lần lượt là pA và pB. Khi đó, p(A,B) = pA.pB nhưng h(A,B) = h(pA) + h(pB). 31 „ „ Nếu một chọn lựa được chia làm 2, Entropy gốc phải bằng tổng của các Entropy thành phần, ví dụ: Khi đó yêu cầu Truyền và bảo mật thông tin 32 8 Định lý hàm Entropy „ Định nghĩa Entropy Chỉ có hàm H dạng sau mới thỏa mản tính chất hàm Entropy n „ H ( X ) = −C ∑ pi log pi „ i =1 „ „ Bổ đề: h(p)=-Clog(p). Entropy của BNN X Entropy của một sự kiện: h(p)=-log(p). (Sử dụng C=1 ) Cơ số logarit tương ứng với đơn vị tính, thông dụng „ „ „ „ „ Nếu ta tính đơn vị bit thì „ Truyền và bảo mật thông tin 33 Ví dụ „ Khi đó: h(p)=-log2(p) và n H ( X ) = − ∑ p i log 2 p i i =1 Truyền và bảo mật thông tin 34 Bài toán về cây tìm kiếm nhị phân Xét BNN X co phân bố như sau: „ „ „ Cơ số 2 thì đơn vị tính là bit. Cơ số 3 thì đơn vị tính là trits. Cơ số e thì đơn vị tính là nats. Cơ số 10 thì đơn vị tính Hartleys. Giả sử, tìm 1 trong 5 người có tên biết trước sẽ xuất hiện theo phân phối sau: Sơ đồ dùng câu hỏi đúng/sai xác định tên: (quy ước viết log thay cho log2) Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 35 Truyền và bảo mật thông tin 36 9 Bài tập Bài toán về cây tìm kiếm nhị phân „ „ „ „ „ „ „ Theo sơ đồ trên: Để tìm x1, x2, x3 với xác suất tương ứng là 0.2, 0.3, 0.2 ta chỉ cần tốn 2 câu hỏi. Để tìm x4, x5 với xác suất tương ứng 0.15, 0.15 thì ta cần 3 câu hỏi. Vậy: Số câu hỏi trung bình là: 2 x (0,2+0,3+0,2) + 3 x (0,15+0,15) = 2.3 Mặt khác: Entropy của X: H(X)= H(0.2, 0.3, 0.2, 0.15, 0.15)=2.27. Vì số câu hỏi trung bình trong trường hợp này xấp xỉ H(X) nên đây là số câu hỏi trung bình tối ưu Truyền và bảo mật thông tin 37 II.2. Các tính chất của Entropy „ Truyền và bảo mật thông tin Các tính chất cơ bản Minh họa tính chất 1: „ Trong trường hợp BNN X có phân bố đều Các tính chất cơ bản „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 38 39 Vậy H(X)=-log(1/M)=logM là hàm đơn điệu tăng Truyền và bảo mật thông tin 40 10 Các tính chất cơ bản của Entropy „ „ „ „ Các tính chất cơ bản của Entropy Minh họa tính chất 3: Xét con xúc sắc 6 mặt với phân bố XS: Minh họa tính chất 2: Trong trường hợp 2 biến ngẫu nhiên X, Y độc lập có phân phối đều với BNN X có M sự kiện và BNN Y có L sự kiện. Gọi f(M), f(L) lần lượt là Entropy của X, của Y. Theo tính chất 2 của Entropy ta có f(ML)=f(M)+f(L) Nếu ta gom sự kiện x1,x2,x3 thành sự kiện x123 (XS 55%) và x5, x6 thành x56 (XS 20%), ta có bảnh phân bố X*: Kiểm tra: H(X) =H(p1+p2+p3, p4 , p5+p6) (BT cho SV) Truyền và bảo mật thông tin 41 Định lý cực đại của entropy Truyền và bảo mật thông tin 42 Định lý cực đại của entropy „ Định lý: H(p1, p2, …,pM)≤ log(M) Trong đó: đẳng thức xảy ra khi và chỉ khi p1=…= pM= 1/M „ Chứng minh „ Bổ đề: cho 2 bộ {p1, p2, …,pM} và {q1, q2,…,qM} là các bộ số dương bất kỳ và „ „ „ Chứng minh bổ đề Theo toán học ta có thể chứng minh ln(x)≤ x-1 với x>0 và đẳng thức đúng khi x=1. Đặt x= qi/pi Suy ra ln(qi/pi)≤ qi/pi –1 (và đẳng thức đúng khi qi=pi với mọi i). Khi đó ta có Đẳng thức xảy ra khi pi=qi với ∀i=1,..,M. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 43 Truyền và bảo mật thông tin 44 11 Định lý cực đại của entropy „ Mặt khác lnx = log2x / log2e Từ (1) và (2)=> „ Đẳng thức xảy ra khi pi=qi với mọi i „ Định lý cực đại của entropy (2) Truyền và bảo mật thông tin „ Đẳng thức xãy ra khi pi=1/M với mọi i đpcm 45 II.3. Entropy của nhiều biến Truyền và bảo mật thông tin 46 Ví dụ Entropy của nhiều biến Định nghĩa: Giả sử X và Y là 2 biến ngẫu nhiên cho trước với pịj = p(X=xi,Y=yj) (∀ i=1,..,M và j=1,…,L). „ Khi đó, Entropy H(X,Y) có dạng: „ „ Chứng minh định lý Lấy qi=1/M, từ bổ đề ta có: „ „ Cho 2 BNN X và Y độc lập nhau và có các phân phối: „ Lập phân phối của P(X,Y) Tổng quát „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 47 H(X,Y) =H(0.125, 0.25, 0.125, 0.125, 0.25, 0.125)=2.5 (Bit) Truyền và bảo mật thông tin 48 12 Entropy có điều kiện „ „ Ví dụ Entropy có điều kiện Entropy của Y với điều kiện X=xi (i=1,..,M) được định nghĩa là: „ Entropy của Y với điều kiện X xảy ra được định nghĩa là: „ Xét biến ngẫu nhiên X và biến ngẫu nhiên Y có tương quan nhau, các phân phối: Entropy của Y/X=1 và Y/X=2 như sau : „ „ „ Truyền và bảo mật thông tin H(Y/X=1)=H(0.25, 0.5 , 0.25)= -0.25 log0.25 –0.5log0.5-0.25 log0.25 =0.5 + 0.5 + 0.5= 1.5 (Bit) H(Y/X=2)= H(0; 0; 1)= 0 (Bit) Entropy của Y khi X xảy ra: H(Y/X)=P(X=1) H(Y/X=1)+ P(X=2) H(Y/X=2)=(0.5x1.5) + (0.5x0)=0.75 (Bit). 49 Truyền và bảo mật thông tin Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độc lập Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độc lập Định lý 1: H(X,Y)≤ H(X)+H(Y) và đẳng thức xảy ra khi X, Y độc lập Hệ quả: „ H(X1, …, Xn) ≤ H(X1)+…+H(Xn) „ H(X1,…Xn; Y1,…,Yn) ≤ H(X1,…Xn)+ H(Y1,…,Yn) Chứng minh định lý 1: Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 51 „ 50 Ta có Truyền và bảo mật thông tin 52 13 Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độc lập „ „ „ „ Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y tương quan Đặt qij =p(xi)p(yj)=> qij >=p(xi, yj) Định lý 2: H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y). Định lý 3: H(Y/X)≤ H(Y) và Dấu đẳng thức xảy ra khi và chỉ khi X và Y độc lập nhau. Đẳng thức xảy ra khi p(xi, yj)=pij =qij =p(xi)p(yj) hay X , Y độc lập nhau (theo bổ đề định lý cực đại). Mặt khác Từ (1) và (2) => H(X,Y)≤ H(X)+H(Y) và đẳng thức xảy ra khi X, Y độc lập (đpcm) Truyền và bảo mật thông tin 53 Chứng minh định lý 2 Truyền và bảo mật thông tin 54 Chứng minh định lý 3 Từ định lý 1: H(X,Y)≤ H(X)+H(Y) Từ định lý 2: H(X,Y)=H(X)+H(Y/X) ⇒H(X)+H(Y/X)≤ H(X)+ H(Y) ⇒H(Y/X) ≤ H(Y). Tương tự ta có: H(X,Y)=H(Y)+H(X/Y) Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 55 Truyền và bảo mật thông tin 56 14 II.4. Đo lượng tin (mesure of information) Bài tập „ „ Ta xét ví dụ trò chơi tung một đồng tiền “có đầu hình – không có đầu hình”. Tuy nhiên người tổ chức chơi có thể “ăn gian” bằng cách sử dụng 2 đồng tiền “Thật- Giả” khác nhau sau: „ „ „ Truyền và bảo mật thông tin 57 Các bảng phân phối của bài toán trên: „ „ „ „ Truyền và bảo mật thông tin 58 Từ các bảng phân phối trên, ta có: „ Entropy của Y: H(Y) = H(0.125, 0.25, 0.625) = 1.3 (bit) „ Entropy của Y khi biết X H(Y/X=1) = H(0.25, 0.5 , 0.25)= 1.5 (bit) H(Y/X=2)= H(0, 0, 1)= 0 H(Y/X)= p(X=1)H(Y/X=1)+ p(X=2)H(Y/X=2) = 0.75 (bit) Ta có thể tính dễ dàng phân phối của Y như sau: „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Mặc dù người tổ chức chơi có thể “ăn gian” nhưng quá trình trao đổi 2 đồng tiền cho nhau là ngẫu nhiêu Nhận xét dựa theo entropy Gọi BNN X về loại đồng tiền (X=1 hoặc 2). Đặt BNN Y là BNN về số đầu hình đếm được sau 2 lần tung Khi đó ta có các bảng phân phối: Truyền và bảo mật thông tin Đồng tiền loại 1 (hay đồng tiền thật): đồng chất có 1 mặt có đầu hình. Đồng tiền loại 2 (hay đồng tiền giả ): đồng chất, mỗi mặt đều có 1 đầu hình. 59 Vậy, H(Y) > H(Y/X) Truyền và bảo mật thông tin 60 15 Định nghĩa lượng tin Ví dụ lượng tin Định nghĩa: Lượng tin (hay thông lượng) của X khi Y xảy ra là lượng chênh lệch giữa lượng không chắc chắn của X và lượng không chắc chắn của X khi Y xảy ra có quan hệ với X. „ Ký hiệu: I(X/Y) = H(X)-H(X/Y) là lượng tin đã biết về X khi Y đã xảy ra. „ Chú ý: ta luôn có I(X/Y) = I(Y/X) „ „ „ Ta có thể hiểu khái niệm này như sau: „ „ X và Y là 2 biến ngẫu nhiên nên chúng có 2 lượng tin không chắc chắn. Nếu X và Y độc lập, thì X xảy ra không ảnh hưởng tới Y nên ta vẫn không biết gì thêm về X và X giữ nguyên lượng không chắc chắn của nó. Trong trường hợp này lượng tin về X khi Y xảy ra là bằng 0. Nếu Y có tương quan với X thì khi Y xảy ra ta biết hoàn toàn về Y và một phần thông tin về X. Phần thông tin đó chính là lượng tin đã biết về X nhưng vẫn chưa biết hết về X. Bài toán ở đây là tính lượng tin đã biết về X khi Y xảy ra. Truyền và bảo mật thông tin 61 Bài tập „ Xét lại ví dụ trên, ta có lượng tin về X khi biết Y là I(X/Y)= I(Y/X)= H(Y) – H(Y/X) = 1.3 – 0.75=0.55 (bit). Truyền và bảo mật thông tin 62 Bài tập Thực hiện một phép thử con xúc sắc đồng chất đồng thời với một đồng tiền cũng đồng chất. Trong đó, con xúc sắc có các mặt điểm từ 1 đến 6, đồng tiền một mặt có đầu hình và mặt kia không có đầu hình. Trước tiên thử con xúc sắc, nếu số điểm ≤ 4 thì tung đồng tiền một lần, ngược lại thì tung đồng tiền hai lần. Tính lượng tin về số điểm con xúc sắc khi biết thông tin về số đầu hình đếm được. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 63 „ Có hai chiếc hộp đựng bi, hộp thứ nhất chứa hai bi đỏ, một bi vàng, một bi xanh. Hộp thứ hai chứa một bi vàng và một bi xanh. Lấy ngẫu nhiên một viên bi trong hộp thứ nhất bỏ vào hộp thứ hai, sau đó lấy ngẫu nhiên một viên bi từ hộp thứ hai. Hãy tính lượng tin về màu viên bi bốc được trong hộp thứ nhất khi biết thông tin về màu sắc viên bi bốc được trong hộp thứ hai. Truyền và bảo mật thông tin 64 16 Bài tập „ An và Bình hẹn gặp nhau. Nếu trời không mưa thì khã năng An đến điểm hẹn là 90% còn Bình là 60%. Nếu trời mưa thì khã năng An đến điểm hẹn là 30% còn Bình là 40%. Giả sử thời tiết chổ An và Bình là như nhau và xác suất mưa sẽ là 60%. Hãy tìm lượng tin về thời tiết khi biết số lượng người đến điểm hẹn Truyền và bảo mật thông tin Chương III. SINH Mà TÁCH ĐƯỢC 65 III.1. Khái niệm về mã tách được III.1. Khái niệm về mã tách được Đặt vấn đề bài toán sinh m㠄 Giả sử nguồn tin X xuất hiện và được ghi lại thông qua một thiết bị đặc biệt. Chẳng hạn như ảnh được ghi lại bằng máy ảnh, âm thanh được ghi lại bằng máy ghi âm, … Qua kênh truyền, những thông tin này cần phải được mã hóa cho phù hợp. Để có thể mã hóa người ta cần một bảng chữ cái gồm các chữ cái quy định trước (chẳng hạn bảng chữ cái la tinh, bảng mã nhị phân, … ). Mỗi giá trị của X sau đó được mã dưới dạng một dãy hữu hạn các chữ cái và ta gọi dãy hữu hạn các chữ cái gán cho một giá trị của x là một từ mã. „ „ „ „ „ „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 67 Ta xét BNN X={x1, x2, …,xn} có phân phối {p1, p2, …, pn} được quan sát liên tục và độc lập. Dãy các giá trị nhận được gọi là thông báo (Message) có dạng xi1xi2…xim. Tập hợp A={a1, a2, …, aD} là tập hợp ký tự mã (Code Characters) hay là bảng chữ cái (Code Alphabet) dùng để sinh mã. Một giá trị xi ∈ X được gán bởi một dãy hữu hạn các ký tự mã được gọi là từ mã (Code word). Tập hợp gồm tất cả các từ mã gán cho tất cả các giá trị của X được gọi là bộ mã hay bảng mã (Code). Các từ mã phải khác nhau từng đôi một. Truyền và bảo mật thông tin 68 17 Khái niệm về bảng mã không tách được III.1. Khái niệm về mã tách được „ Bộ mã được gọi là tách được (Decypherable Coding) nếu như từ một dãy các ký tự mã nhận được liên tục (được mã hóa từ bộ mã này), ta luôn luôn giải mã được với kết quả duy nhất là dãy các giá trị gốc của X. „ „ „ „ „ „ Truyền và bảo mật thông tin 69 „ „ „ Truyền và bảo mật thông tin Xét biến ngẫu nhiên X={x1, x2} có bảng mã tương ứng W={w1=0, w2=01}. Phương pháp giải mã được sử dụng như sau: chỉ giải mã khi nào đã nhận được đoạn mã với độ dài bằng độ dài của từ mã dài nhất. Giả sử dãy mã nhận được là: 0010000101001. Sử dụng phương pháp giải mã trên ta nhận được duy nhất dãy thông báo gốc: x1x2x1x1x1x2x2x1x2. Nhận xét: Bảng mã tách được là bảng mã mà trong đó không tồn lại từ mã này là mã khóa từ mã khác, tuy nhiên vẫn có thể tồn tại từ mã này là tiền tố (phần đầu) của từ mã kia. „ „ Bước khởi tạo: Gán tập hợp S0=W. Bước 1: xác định tập hợp S1 từ S0: „ „ „ „ „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 71 - Khởi tạo S1={} - Với ∀ wi, wj ∈ S0, ta xét: nếu wi=wjA (wj là tiền tố của wi) hoặc wj=wi A (wi là tiền tố của wj) thì thêm A (phần hậu tố) vào S1. Bước k: xác định tập hợp Sk (k≥2) từ tập hợp S0 và Sk-1: - Khởi tạo: Sk={} - Với ∀ wi∈ S0 và ∀ vj ∈Sk-1, ta xét: nếu wi=vjA (vj là tiền tố của wi) hoặc vj=wi A thì thêm A vào Sk. Điều kiện để dừng vòng lặp: „ „ „ Truyền và bảo mật thông tin 70 Giải thuật kiểm tra tính tách được của bảng mã (Sardinas, Patterson và Abramson) Ví dụ bảng mã tách được „ Bảng mã không tách được là bảng mã mà khi mã hóa thông báo Msg ta sẽ nhận được một dãy các từ mã ws, và khi giải mã dãy các từ mã ws thì ta có thể nhận được nhiều thông báo Msg khác nhau. Ví dụ: Xét biến ngẫu nhiên X={x1, x2, x3, x4} có bảng mã W={w1=0, w2=1, w3=01, w4=10}. Giả sử thông báo nguồn có nội dung: x2x3x4x3x2x1. Khi đó dãy mã tương ứng viết từ W: 101100110. Nếu giải mã từ trái qua phải: x2x1x2x2x1x1x2x2x1. Nếu giải mã từ phải qua trái, ưu tiên độ dài lớn : x2x3x4x3x4 Nếu giải mã từ trái qua phải, ưu tiên độ dài lớn x4x2x4x3x4 Nếu Sk={} thì dừng và kết luận bảng mã tách được (k≥1). Nếu tồn tại từ mã wi trong Sk hay Sk ∩S0 ≠ ∅ thì dừng và kết luận bảng mã không tách được. Nếu Sk=St Bảng mã W={w1, w2, …, wM} là bảng mã prefix. Xét bảng mã thỏa M=3, D=2, n1=1, n2=2, n3=3. + Kiểm tra: + Sinh mã cho nút „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 79 78 „ + Chọn mã: • Chọn w1=0 , cắt bỏ các nút con của nút w1. • Chọn w2=10, cắt bỏ các nút con của nút w2. • Chọn w3=111 Truyền và bảo mật thông tin 80 20 III.3. Tính tối ưu của độ dài mã Bảng mã tối ưu tuyệt đối/ tương đối Định lý Shannon „ „ Bảng mã được gọi là tối ưu tuyệt đối khi Bảng mã tối ưu tương đối khi: )Nếu mã tách được không tối ưu thì độ dài của nó sẽ lớn hơn nhiều so với cận dưới, còn nếu mã tách được tối ưu thì độ dài trung bình của nó gần với cận dưới. Truyền và bảo mật thông tin 81 Truyền và bảo mật thông tin Điều kiện nhận biết một bảng mã tối ưu Bảng mã tối ưu tuyệt đối/ tương đối Ví dụ: xét biến ngẫu nhiên X={x1, x2, x3, x4} „ Có phân phối: P={1/2, 1/4, 1/8, 1/8} „ Có bảng mã W={w1=0,w2=10,w3=110, w4=111} „ Độ dài trung bình từ mã: „ Định lý (với D=2): „ „ „ „ „ „ 82 „ Entropy của X: H(X)= H(0.5, 0.25, 0.125, 0.125) = 0.5 +0.5 + 0.375 + 0.375 =1.75 Log2D=1. Ta có: Xác suất pi càng lớn thì độ dài ni của từ mã wi càng nhỏ. Giả sử p1≥ p2 ≥ … ≥ pM thì 2 từ mã tương ứng với 2 giá trị có xác suất nhỏ nhất có độ dài mã bằng nhau: nM-1 =nM. Trong các từ mã có độ dài bằng nhau và cùng bằng nM (dài nhất) thì tồn tại ít nhất 2 từ mã có M-1 ký tự đầu giống nhau và ký tự thứ M khác nhau. Ví dụ, xét bảng mã: W={w1=0, w2=100, w3=101, w4=1101, w5=1110} Bảng mã trên không phải là bảng mã tối ưu vì 2 từ mã w4, w5 có độ dài lớn nhất =4 ký tự nhưng 3 ký tự đầu khác nhau. =>Bảng mã tối ưu tuyệt đối Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 83 Truyền và bảo mật thông tin 84 21 Phương pháp sinh mã Huffman Phương pháp sinh mã Huffman Định lý Huffman „ Giả sử X có phân phối xác suất với thứ tự giảm dần sau: x2 … xM X | x1 P | p1≥ p2 ≥ … ≥ pM „ Giả sử bảng mã của X là W={w1, w2, …, wM-1, wM}. „ Đặt xM-1,M={xM-1, xM} có xác suất là pM-1,M=pM-1+pM. và X* = { x1, x2,…, xM1,M} có phân phối sau: X* | x1 x2 … xM-2 xM-1,M P | p1 p2 … pM-2 pM-1,M „ Giả sử W* ={w*1, w*2, …, w*M-2, w*M-1,M} là bảng mã tối ưu của X*. Khi mã nhận được theo quy tắc sau là mã tối ưu cho X đó: Phương pháp sinh mã Huffman với D=2: „ Giả sử X có phân phối xác suất với thứ tự giảm dần sau: x2 … xM X | x1 P | p1≥ p2 ≥ … ≥ pM „ Khởi tạo: Đặt M0=M „ Bước 1: „ „ „ „ „ „ wi=w*i với 1 ≤ i ≤ M-2 wM-1=w*M-1,M + “0”. wM =w*M-1,M + “1”. „ Truyền và bảo mật thông tin „ „ và Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 86 Bài tập Hãy mã hoá nguồn S = {x1, x2, x3, x4, x5, x6} với các xác suất pi lần lượt là 0,3; 0,25; 0,2; 0,12; 0,08; 0,05 Bài tập: tínhvà so sánh: Lưu vết: wMo-1 = wMo-1, Mo + “0” wMo = wMo-1, Mo + “1” Giảm M0: M0=M0-1, nếu M0<=2 thì kết thúc, nếu không quay lại bước 1 85 Ví dụ phương pháp sinh mã Huffman „ Bước 2: „ Truyền và bảo mật thông tin Đặt xMo-1, Mo={xMo-1,xMo } Sắp xếp lại theo thứ tự giảm dần XS ta được dãy phân phối mới có M01 phần tử p1, p2,…pMo-2, PMo-1, Mo 87 Lập bảng mã nhị phân Huffman cho các phân phối sau: Lập bảng mã nhị phân Huffman dùng để mã hóa đoạn văn bản: “thoi the thi thoi thi the thoi thi thoi the” Truyền và bảo mật thông tin 88 22 IV.1. Kênh truyền rời rạc không nhớ Khái niệm kênh truyền rời rạc không nhớ „ Kênh truyền rời rạc: truyền tuần tự các ký tự độc lập nhau (hay truyền từng ký tự một), „ “Không nhớ” ở đây là chỉ xét mối quan hệ giữa ký tự truyền và ký tự nhận được tương ứng, không xét đến mối quan hệ giữa ký tự nhận được với ký tự nhận được trước đó. Chương IV. KÊNH TRUYỀN Truyền và bảo mật thông tin Mô hình vật lý Mô hình toán học „ „ „ Các qui ước: „ - X: là biến ngẫu nhiên có giá trị cần truyền ở đầu truyền. „ - Y: là biến ngẫu nhiên chứa giá trị có thể nhận được ở đầu nhận. „ - ΓX: là bảng chữ cái sinh mã ở đầu truyền. „ - ΓY: là bảng chữ cái giải mã ở đầu nhận. „ - X, Y, ΓX, ΓY: đều hữu hạn và rời rạc. „ - Truyền rời rạc từng ký tự và nhận cũng rời rạc từng ký tự. „ - Ký tự nhận sau không phụ thuộc vào ký tự nhận trước. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 90 „ „ „ 91 Ta gọi: ΓX={x1, x2, …, xM} là bộ ký tự sinh mã ở đầu truyền (input). ΓY={y1, y2,…,yL} là bộ ký tự giải mã ở đầu nhận (output). Biến ngẫu nhiên X lấy giá trị (đã mã hóa) trên ΓX và có phân phối p(X=xi)=p(xi) với i=1,..,M. Biến ngẫu nhiên Y lấy giá trị (giải mã) trên ΓY và có phân phối xác suất có điều kiện: P(Y=yj|X=xi)=p(yj/xi)=pij với j=1,..,L. Truyền và bảo mật thông tin 92 23 Mô hình toán học „ „ „ Mô hình toán học Gọi A=[pij] là ma trận truyền tin hay mô hình truyền tin của kênh truyền rời rạc không nhớ. Với i=1,…,M , j=1,…,L và pij = p(Y=yj/X=xi) = p(yj/xi) là XS nhận được giá trị yj khi đã truyền giá trị xi. Tính phân phối đầu nhận: „ „ „ „ Tính phân phối đầu nhận: Vậy p(yj)= P’X.Aj Tổng quát: P’Y = P’X.A Trong đó „ „ „ Truyền và bảo mật thông tin 93 Cho ma trận truyền tin: Truyền và bảo mật thông tin „ „ „ Xác suất truyền: p(x1)=0.5 và p(x2)=p(x3)= 0.25. Ta tìm phân phối của Y : „ Ta có: P’X =(0.5, 0.25, 0.25) „ Áp dụng công thức (1) ở trên ta được: „ p(y1) = P’x .A1 = 0.5*0.5+ 0.25*0.3+0.25*0.2 =0.375 „ p(y2) = P’x.A2 = 0.5*0.2+ 0.25*0.5+0.25*0.3= 0.3 „ p(y3) = P’x .A3 = 0.325 ⇒ P’Y =(0.375, 0.3, 0.325) „ „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 94 Xét ma trận truyền tin như trên „ Ta có: „ Truyền và bảo mật thông tin - Aj là cột thứ j của A - P’X = [p(x1), p(x2),…., p(xM)]. - P’Y = [p(y1), p(y2),…., p(yM)]. Lượng tin trên kênh truyền Ví dụ xác định phân phối đầu nhận „ (1) (2) „ „ „ „ 95 P’X =(0.5, 0.25, 0.25) P’Y =(0.375, 0.3, 0.325) Tính các Entropy: H(Y) = H(0.375, 0.3, 0.325) = 1.58 (bit) H(Y/X=x1) = H(0.5, 0.2, 0.3)= 1.49 (bit) H(Y/X=x2) = H(0.3, 0.5, 0.2)= 1.49 (bit) H(Y/X=x3) = H(0.2, 0.3, 0.5)= 1.49 (bit) H(Y/X)=p(x1).H(Y/X=x1)+p(x2).H(Y/X=x2)+p(x3).H(Y/X=x3) = 1.49 (bit) Lượng thông tin truyền trên kênh: I (X/Y)= I (Y/X)= H(Y) H(Y/X) = 0,09 (bit) Truyền và bảo mật thông tin 96 24 IV.2. Các dạng kênh truyền Định nghĩa dung lượng kênh truyền „ „ „ Dựa vào ma trận truyền tin A, ta có thể dễ dàng tính lượng tin trên kênh truyền. I(X/Y)= H(X)-H(Y/X) = H(Y)-H(X/Y) = I(Y/X) Ta có I(X/Y)= H(Y)-H(Y/X), trong đó: „ „ „ „ Kênh truyền không mất tin „ Mô hình: từ tập hợp các giá trị có thể nhận được ở đầu nhận Y={y1, y2, …, yL} được phân thành M nhóm Bi tương ứng với các giá trị xi ở đầu truyền và xác suất để truyền xi với điều kiện đã nhận yj là p(X= xi/Y=yj ∈Bi)=1 ( với M < L ). H(Y)= H(P’X .A) phụ thuộc vào PX. H(Y/X) phụ thuộc vào PX Vậy: I(Y/X) phụ thuộc hoàn toàn vào PX và do đó I(Y/X) có thể đạt Max với PX xác định nào đó. Ta định nghĩa dung lượng kênh truyền (bit) là Truyền và bảo mật thông tin 97 Kênh truyền không mất tin Kênh truyền xác định „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Mô hình: từ tập hợp các giá trị có thể truyền ở đầu truyền được phân thành L nhóm Bj tương ứng với các giá trị có thể nhận được yj ở đầu nhận và xác suất để nhận yj với điều kiện đã truyền xi là p(Y=yj /X=xi ∈Bj )=1 (M>L). Đặc trưng: H(Y/X)=0. Có nghĩa là lượng tin chưa biết về Y khi truyền X bằng 0 hay khi truyền X thì ta biết sẽ nhận được Y. =>C=log2L Đặc trưng: H(X/Y)=0 Æ biết Y thì biết X =>I(X/Y)=H(X)=> C=log2M Truyền và bảo mật thông tin 98 Truyền và bảo mật thông tin 99 Truyền và bảo mật thông tin 100 25 Kênh truyền không nhiễu „ „ „ Kênh truyền không sử dụng được. Mô hình: là sự kết hợp của kênh truyền xác định và kênh truyền không mất thông tin, truyền nào sẽ nhận được đúng ký tự đó. Đầu truyền Đầu nhận Æ x1 x1 x2 Æ x2 … … Æ xM xM Đặc trưng: H(X/Y)=H(Y/X)=0 Dung lượng: C=log2L=log2M Truyền và bảo mật thông tin „ „ „ „ 102 Truyền và bảo mật thông tin Dung lượng kênh truyền đối xứng Mô hình: là kênh truyền mà ma trận truyền tin có đặc điểm sau: „ „ Mô hình: Là kênh truyền mà giá trị đầu nhận luôn độc lập với giá trị đầu truyền, với mọi phân bố xác suất đầu truyền. Đặc trưng: H(X/Y) =H(X); H(Y/X)= H(Y) Dung lượng: C=0 Ví dụ 101 Kênh truyền đối xứng „ „ „ „ Mỗi dòng của ma trận A là một hoán vị của phân phối P={p’1, p’2, …, p’L} Mỗi cột của ma trận A là một hoán vị của Q={q’1, q’2, …, q’M} Xác định C=Max(I(X/Y))=Max(H(Y)-H(Y/X)) H(Y/X)= M M ∑ x H (Y / x ) = H (Y / x ) ∑ x i =1 i i i i =1 L i = H (Y , xi ) = − ∑ p ' j log p ' j j =1 Æ Ví dụ: Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 103 Truyền và bảo mật thông tin 104 26 Kênh truyền đối xứng IV.3. Lược đồ giải mã Chú ý: trường hợp kênh 1 bit với nhiễu β Ma trận truyền tin: „ „ Dung lượng: C =1+(1-β)log(1-β)+βlogβ = 1- H(β, 1-β) „ „ Đặt vấn đề bài toán giải m㠄 Phân tích yêu cầu giải mã: „ Khi truyền giá trị xi, ta sẽ nhận được yj. Đối với kênh truyền không nhiễu thì yj chính là xi. Đối với kênh truyền có nhiễu thì yj có thể khác xi. Do đó ta cần tìm cách giải mã yj về giá trị xi khi kênh truyền có nhiễu. „ Phép phân hoạch các giá trị ở đầu nhận: „ Phép phân hoạch tập các giá trị ở đầu nhập yj ∈ Y là phép phân chia tập Y thành các tập con Bi sao cho: C 1 0.5 1 Truyền và bảo mật thông tin β 105 Ví dụ bài toán giải m㠄 „ „ „ „ „ „ X={0000, 0101, 1110, 1011} Y={0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111} „ „ Nguồn phát tín hiệu (hay thông báo) với vận tốc R (tín hiệu/giây). Tín hiệu được mã hóa từ bộ ký tự mã. Tín hiệu mã hóa được truyền trên kênh với vận tốc V (ký tự/giây) Tín hiệu truyền trên kênh có thể bị nhiễu với xác suất P(e). Trước khi nhận, tín hiệu mã hóa được giải mã theo một phương thức tối ưu và độ chính xác cao nhất có thể có. Giả sử ta có thể phân hoạch tập Y thành các tập con Bi như sau: „ „ „ „ „ 106 Sơ đồ truyền tin Cho tập các từ mã truyền X và tập các dãy n bit nhận được Y như sau „ Truyền và bảo mật thông tin B1={0000, 1000, 0001, 0010} B2={0101, 1101, 0100, 0111} B3={1110, 0110, 1111, 1100} B4={1011, 0011, 1010, 1001} Giả sử nhận yj = 0011 thì giải mã về x4 = 1011 vì yj ∈ B4. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 107 Truyền và bảo mật thông tin 108 27 Sơ đồ truyền tin „ „ Ví dụ Bài toán đặt ra ở đây: tìm giải pháp tạo mã sao cho sai số đầu nhận có xác suất nhỏ hơn ε bất kỳ (ε < P(e)) đồng thời với đồng bộ hóa: vận tốc phát thông báo ở nguồn R và vận tốc truyền tải ≤ V Truyền và bảo mật thông tin 109 Các khái niệm cơ bản: „ „ „ „ „ „ „ „ „ „ Giả sử kênh truyền từng bit với V=1 bit/s, nguồn phát thông báo với tốc độ R=2/5 bit/s (R B1={y1}. „ Bước 2: xét y2, ta tính: p(x1).p(y2/x1)= 1/2 . 1/3 = 1/6; p(x2).p(y2/x2)= 1/4 . 1/6 = 1/24 p(x3).p(y2/x3)= 1/4 . 1/2 = 1/8 Do p(x1).p(y2/x1) lớn nhấtÆ B1=B1 +{y2} => B1={y1, y2}. „ Bước 3: Xét y3, ta tính: p(x1).p(y3/x1)= 1/2 . 1/6 = 1/12 ; p(x2).p(y3/x2)= 1/4 . 1/2 = 1/8 p(x3).p(y3/x3)= 1/4 . 1/3 = 1/12 Do p(x2).p(y3/x2) lớn nhất Æ B2=B2 +{y3} => B2={y3}. „ Kết quả: Phân hoạch: B1={y1, y2}, B2={y3} và B3={}. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Cho ma trận truyền tin A và xác suất ở đầu truyền như sau: Với p(x1)=1/2; p(x2)=p(x3)=1/4. Hãy xây dựng lược đồ giải mã tối ưu. 113 Minh họa xây dựng lược đồ giải mã tối ưu Truyền và bảo mật thông tin Minh họa xây dựng lược đồ giải mã tối ưu Truyền và bảo mật thông tin Minh họa xây dựng lược đồ giải mã tối ưu „ „ „ „ „ „ „ 115 114 Lược đồ giải mã tối ưu Tính các xác suất truyền sai: Xác suất truyền sai từ mã x1: p(e/x1)=∑p(Y=yj ∉B1/X=x1)=p(y3/x1) =1/6 Xác suất truyền sai từ mã x2: p(e/x2)= ∑ p(Y=yj ∉B2/X=x2) = p(y1/x2) + p(y2/x2) =1/3+1/6=1/2 Xác suất truyền sai từ mã x3: p(e/x3)= ∑ p(Y=yj ∉B3/X=x3) = p(y1/x3) + p(y2/x3) + p(y3/x3) =1/6+1/3+1/2=1 Xác suất truyền sai trung bình:p(e)= ∑p(X=xi)p(e/xi) =p(x1).p(e/x1) + p(x2).p(e/x2) + p(x3).p(e/x3) = 1/2.1/6 + 1/4.1/2 + 1/4.1 = 11/24 Xác suất truyền sai lớn nhất:pm(e) = Max{ p(e/x1), p(e/x2), p(e/x3)} = 1 Truyền và bảo mật thông tin 116 29 Bài tập Bài tập Truyền và bảo mật thông tin 117 Truyền và bảo mật thông tin 118 V.1. Số học modulo Định nghĩa: Giả sử a và b là các số nguyên và m là một số nguyên dương. Khi đó ta viết a ≡ b (mod m) nếu a-b chia hết cho m . Mệnh đề a ≡ b (mod m) được gọi là "a đồng dư với b theo modulo m". Số nguyên m được gọi là mudulus „ Giả sử a = q1m + r1 và b = q2m + r2 (0 ≤ r1 ≤ m-1 và 0 ≤ r2 ≤ m-1). „ =>a ≡ b (mod m) Ù r1 = r2 . „ a ≡ b (mod m) Ù a mod m = b mod m. „ Nếu thay a bằng a mod m thì ta nói rằng a được rút gọn theo modulo m. „ Chương V. SỬA LỖI Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 120 30 Số học modulo „ „ „ „ „ Số học modulo - các tính chất Số học đồng dư modulo m: Zm là tập (0, …, m1) với hai phép toán là + và ×. Việc cộng và nhân trong Zm được thực hiện giống như cộng và nhân các số nguyên ngoại trừ một điểm là các kết quả được rút gọn theo modulo m. VD: 11 × 5 trong Z26 ? 11 x 5=55; 55 =2* 26+ 3, vậy 11 x 5 = 3 trong Z26 Truyền và bảo mật thông tin 7. 8. 9. 10. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 3. 4. 5. Truyền và bảo mật thông tin 122 Một số lưu ý Phép nhân là đóng , tức là với ∀ a,b ∈ Zm , ab ∈ Zm . Phép nhân là giao hoán , nghĩa là với ∀ a,b ∈ Zm , ab = ba Phép nhân là kết hợp, nghĩa là với ∀ a,b,c ∈ Zm , (ab)c = a(cb) 1 là phần tử trung hòa của phép nhân, tức là với bất kỳ a ∈ Zm, a×1 = 1×a = a Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với ∀ a,b,c ∈ Zm , (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac) Truyền và bảo mật thông tin 2. 121 Số học modulo - các tính chất 6. Phép cộng là đóng: với ∀ a, b ∈ Zm, a+b ∈ Zm Phép cộng là giao hoán, tức là với ∀ a,b ∈ Zm, a+b = b+a Phép cộng là kết hợp, tức là với ∀ a,b,c ∈ Zm, (a+b)+c = a+(b+c) 0 là phần tử trung hòa của phép cộng, có nghĩa là với ∀ a ∈ Zm, a+0 = 0+a = a Phần tử nghịch đảo của phép cộng của phần tử bất kì (a ∈ Zm ) là m-a, nghĩa là a+(m-a) = (m-a)+a = 0 với ∀a ∈ Zm . 1. 123 a (mod N)= (a+N) (mod N) Ví dụ: -4 (mod 26)=-4+26 (mod 26)=22 (mod 26) „ Các tính chất phép mod „ „ „ „ (a+b) mod N=(a mod N + b mod N) mod N ab mod N=(a mod N)(b mod N) mod N Ví dụ: „ „ (36 +46) mod 26 = (10+20) mod 26=4 310 mod 26= =(33x33x33x3) mod 26 =(27 mod 26)3 .3 mod 26=3 Truyền và bảo mật thông tin 124 31 V.2. Mguyên lý khoảng cách nhỏ nhất hamming Các phép toán Modulo 2 „ „ „ „ „ „ Các phép toán trong Modulo 2 (+,-): 0 + 1 = 1 + 0 = 1; 0 – 1 = 1 – 0 = 1; 1+1=0 1 – 1 = 0; Phép cộng và trừ giống nhau, thường được ký hiệu Truyền và bảo mật thông tin 125 Kênh truyền đối xứng nhị phân và lược đồ giải mã tối ưu „ „ „ 126 Theo lược đồ giải mã tối ưu ta có: khi nhận vj thì giải mã về w*i sao cho: p(w*i/vj) = Max{P(wk/vj)} (∀wi ∈ W) „ Ta có: P(wk/vj) = (p(wk).p(vj/wk)])/p(vj) với (∀wk ∈ W) ⇒ p(wk/vj) → Max ⇔ p(wk).p(vj/wk) → Max. „ Do W có phân phối đều nên: p(wk/vj) → Max ⇔ p(vj/wk) → Max „ Vậy: để tìm w*i sao cho P(w*i/vj) = Max{P(wk/vj)} ta chỉ cần tìm w*i sao cho P(vj/ w*i) = Max{P(vj/ wk)} (chỉ dựa vào ma trân truyền tin A) „ Gọi W = {w1, w2,…,ws} là tập s từ mã truyền, độ dài mỗi từ mã đều bằng n bit. V = {v1, v2,…., vn} là tập các dãy n bit nhận được ở cuối kênh với W có phân phối đều, xác suất để nhận vj khi truyền wi là p(vj/wi) = pij. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin Kênh truyền đối xứng nhị phân và lược đồ giải mã tối ưu Xét kênh truyền đối xứng nhị phân. Giả sử ta truyền các dãy từ mã nhị phân có độ dài n bits với xác suất truyền sai 1 bit là β. Truyền và bảo mật thông tin Khoảng cách Hamming „ Định nghĩa: cho v1 và v2 là 2 dãy nhị phân dài n bit, ta gọi khoảng cách Hamming giữa 2 dãy v1,v2 là số bit tương ứng khác nhau. Ký hiệu: d(v1, v2). „ Ví dụ: v1=10101010 v2=10101111 „ Ta nhận thấy rằng bit thứ 6 và bit thứ 8 giữa giữa v1 và v2 là khác nhau nên số bit tương ứng khác nhau giữa v1 và v2 là 2. Do đó, ta nói khoảng cách Hamming giữa v1 và v2 là 2 hay d(v1, v2) = 2 127 Truyền và bảo mật thông tin 128 32 Quan hệ giữa xác suất giải mã và khoảng cách Hamming „ „ „ „ „ „ „ „ Nguyên lý Hamming Giả sử nhận được v: Xét 2 từ mã w1 và w2 cần chọn để giải mã cho v, độ dài từ mã là n: Gọi d1=d(v, w1), d2=d(v,w2). Xác suất đế nhận v khi truyền w1: p(v/w1)= β d1(1− β)n-d1 Xác suất đế nhận v khi truyền w2: p(v/w2)= β d2(1− β)n-d2 Nếu nhiễu 0 <β < ½ thì (1-β)/β>1 Do đó: P(v/w1)>p(v/w2) ⇔ d1 vj được giải mã về w*i „ Lỗi chỉ phát hiện không điều chỉnh được: Trong trường hợp này tồn tại từ mã w*i và w**i sao cho d(vj, w*i)= d(vj, w**i)=Min d(vj, wk) với ∀wk ∈ W => vj không thể giải mã chính xác. „ Lỗi không phát hiện được: giải mã ra w*i nhưng khác với wi đã truyền. Xét bộ mã W={w1, w2, …, ws} gồm có s từ mã nhị phân dài n bit và 1 số nguyên dương e. 1. Nếu d(wi, wj) ≥ 2e+1 (với ∀ i≠j ) Khi đó: tất cả các dãy nhận được v có số bit lỗi ≤ e thì v có thể tự điều chỉnh (hay tự sửa lỗi). 2. Nếu d(wi, wj) ≥ 2e (với ∀ i≠j ) Khi đó: tất cả các dãy nhận được v có số bit lỗi < e thì v có thể tự điều chỉnh. Tất cả các dãy nhận được có số bit lỗi = e thì ta chỉ phát hiện là v có lỗi và không thể tự điều chỉnh được. 3. Ngược lại; Nếu v có số chữ số bit lỗi ≤ e và có thể tự điều chỉnh thì d(wi, wj)≥ 2e+1 (với ∀ i≠j ). Nếu v có số chữ số bit lỗi ≤ e-1 tự điều chỉnh được và tất cả các tín hiệu với số chữ số bit lỗi ≤ e được phát hiện thì khoảng cách giữa các từ mã luôn thỏa: d(wi,wj) ≥ 2e (với ∀ i≠j ). Truyền và bảo mật thông tin 133 Chứng minh Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 134 Cận Hamming 1. Giả sử: d(wi, wj) ≥ 2e+1 với ∀ i≠j . Nếu w và w’ có cùng khoảng cách đối với dãy v thì d(v,w)=d(v,w’)≥ e+1. Vậy , nếu d(v, w*) ≤ e thì v có thể được giải mã ra w*. 2. Nếu d(wi,wj)≥ 2e với ∀ i≠j, có khả năng có v, w và w’ với số chữ số lỗi là: d(v,w)=d(v,w’)=e (d(v,w)+ d(v,w’) ≥ d(w,w’)≥ 2e). Có thể phát hiện ra các từ mã gần v, nhưng do tồn tại cùng lúc nhiều từ mã gần nhất với v dẫn đến không giải mã được. 3. Tương tự. Truyền và bảo mật thông tin Truyền và bảo mật thông tin „ „ „ 135 Đặt vấn đề: trong tổng số 2n dãy nhị nhân dài n bit có thể chọn ra bao nhiêu dãy để tạo thành một bộ mã có thể tự điều chỉnh được e bit lỗi. Định lý cận Hamming cho chúng ta xác định số từ mã có độ dài n bit với giả thiết: có khả năng tự sửa được e bit lỗi (điều kiện cần tự sửa lỗi). Định lý: Nếu bộ mã W có s từ mã có độ dài n bit có thể tự sửa được e bit lỗi thì Ghi chú: Cn = n!/(i!*(n-i)!); s là số từ mã Truyền và bảo mật thông tin 136 34 Bài tập Chứng minh „ Xét từ mã nhị phân wi có độ dài n bit và có khả năng tự sửa được e bit lỗi. Số dãy vj sai khác với wi từ 0 đến e bit là : „ Với s từ mã, tổng số dãy vj có thể tự sửa lỗi là: „ (2n là tổng số dãy nhị phân dài n bits)Î „ Truyền và bảo mật thông tin „ „ 137 V.4. Mã kiểm tra chẵn lẻ „ „ (Ghi chú: trong một số trường hợp sinh mã theo phương pháp kiểm tra chẵn lẻ, thứ tự các bit kiểm tra và các bit thông tin có thể xen kẻ nhau hay theo một thứ tự khác. Ở đây, ta chọn thứ tự các bit kiểm tra chẵn lẻ và các bit thông tin như trên để dễ tính toán nhưng vẫn mất tính tổng quát. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 138 Mã kiểm tra chẵn lẻ Bộ mã kiểm tra chẵn lẻ là bộ mã gồm s=2k từ mã, trong đó mỗi từ mã có dạng sau: Truyền và bảo mật thông tin Cho n=7 và e=2, hãy áp dụng định lý cận Hamming cho biêt số từ mã tối đa của bộ mã W. 139 „ „ Mỗi đoạn mã thông tin có duy nhất một đoạn mã kiểm tra và được xác định bởi hệ phương trình tuyến tính nhị phân sau: Gọi A=[aij] =Am x n , aij ∈{0,1}, i= 1..m , j= 1..n . Ma trận A được gọi là ma trận kiểm tra chẵn lẻ có hạng là m (hay Rank(A) = m). Lưu ý: ở đây sử dụng phép tính + trong Z2 Truyền và bảo mật thông tin 140 35 Mã kiểm tra chẵn lẻ „ Phương pháp kiểm tra chẵn lẻ Cho w’=r1r2…rn là một từ mã, w là ma trận viết theo cột, khi đó A.w=0: r1 0 a11 a12 … a1n 0 a21 a22 … a2n X r2 = … … … rn 0 am1 am2 …amn Hay: „ „ „ „ „ „ „ „ Truyền và bảo mật thông tin 141 Phương pháp sinh mã kiểm tra chẵn lẻ „ „ Giả sử: cho trước ma trận kiểm tra chẵn lẻ A với Rank(A) = m. Tìm bộ mã chẵn lẻ W={w1, w2, w3,…,ws} Bước 0: Xác định các giá trị n, m, k, s „ „ „ „ „ „ „ Truyền và bảo mật thông tin 142 Ví dụ sinh mã kiểm tra chẵn lẻ „ Xây dựng bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: Độ dài của từ mã n= số cột của ma trận A. Số bit kiểm tra m= số dòng của ma trận A. Số bit thông tin: k = n-m. Số từ mã s=2k Bước i: Tìm các từ mã thứ i (1≤ i ≤ s): „ Gọi w’=r1r2…rn là từ mã truyền (hay dãy n bit truyền) và v’=r1r2…rn là dãy n bit nhận được. Qui ước: v’, w’ (lần lượt là chuyển vị của v và w) được viết theo dòng. Còn v, w được viết theo cột. Nếu A.v = 0 thì v = w, ta gọi v là chẵn (trường hợp nhận đúng) Nếu A.v ≠ 0 thì v ≠ w, ta gọi v là lẻ (trường hợp nhận sai). Ta gọi z = v-w là bộ lỗi giữa v và w. Nghĩa là tại các vị trí z = {0} thì bit nhận được tương ứng là bit đúng và tại các vị trí z = {1} thì bit nhận được tương ứng là bit sai (hay bit lỗi). Ta gọi C = A.z là bộ sửa lỗi (hay bộ điều chỉnh lỗi). Ta có C = A.z = A.(v-w) = A.v-A.w = A.v ⇒ C = A.v = A.z Tính chất của bộ sửa lỗi: dãy n bit nhận được v và bộ lỗi tương ứng có cùng bộ điều chỉnh. „ Gọi kpi là triển khai nhị phân k bit của số i Từ mã cần tìm là: w’i=r1r2..rmkpi Giải hệ phương trình A.wi=0 để tìm m bit kiểm tra ứng với k bit thông tin (kpi) đã biết => từ mã wi Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 143 Bước 0: „ „ „ „ n=6 (= số cột của ma trận A) m=3 (= số dòng của ma trận A) Số bit thông tin k = n – m = 3 => Số từ mã s=2k=8. Truyền và bảo mật thông tin 144 36 Ví dụ sinh mã kiểm tra chẵn lẻ Ví dụ sinh mã kiểm tra chẵn lẻ Bước i: Tìm từ mã thứ i (1≤ i ≤ s): „ w’0=r1r2r3000 (000 là triển khai nhị phân k=3 bit của số i=0) „ w’1=r1r2r3001 (001 là triển khai nhị phân k=3 bit của số i=1) „ w’2=r1r2r3010 „ w’3=r1r2r3011 „ w’4=r1r2r3100 „ w’5=r1r2r3101 „ w’6=r1r2r3110 „ w’7=r1r2r3111 Giải hệ phương trình A.w1=0 Truyền và bảo mật thông tin 145 Truyền và bảo mật thông tin Ví dụ sinh mã kiểm tra chẵn lẻ Ví dụ sinh mã kiểm tra chẵn lẻ Giải hệ phương trình A.w2=0 Giải tương tự cho các trường hợp còn lại ta có: w’0=000000, w’3=110011, w’4=110100, w’5=111101, w’6=001110, w’7=000111. ⇒ W={000000, 001001, 111010, 110011, 110100, 111101, 001110, 000111} Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 146 „ 147 Truyền và bảo mật thông tin 148 37 Quan hệ giữa độ dài mã n, số bit kiểm tra m và số lỗi tự sửa e „ „ Ví dụ tìm m nhỏ nhất từ n và e Điều kiện cần (Cận Hamming): Điều kiện cần để bộ mã chẵn lẻ có độ dài n bit có thể tự sửa được e bit lỗi với k bit thông tin và m bit kiểm tra là: „ „ Điều kiện đủ ( ĐK Vasharmov-Gilbert-Sacks): Điều kiện đủ để bộ mã kiểm tra chẵn lẻ có độ dài n bit với m bit kiểm tra chẵn lẻ có thể tự sửa được e bit lỗi là: „ „ „ „ Truyền và bảo mật thông tin „ Truyền và bảo mật thông tin „ „ „ „ Vậy số bit lỗi lớn nhất có thể tự sửa là e = 1. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 150 Bài tập Giả sử cho trước m=3, k=2. Tìm số bit lỗi lớn nhất có thể tự sửa e? Theo định lý điều kiện đủ (ĐK Vassharmov-GilbertSacks): Truyền và bảo mật thông tin m = 1 ⇒ (*) sai. m = 2 ⇒ (*) sai. m ≥ 3 ⇒ (*) đúng. Vậy số bit kiểm tra tối thiểu cần thiết là m = 3. 149 Ví dụ tìm e lớn nhất từ m và n „ Giả sử biết trước n=7 và e=1. Tìm số bit kiểm tra tối thiểu cần thiết của bộ mã chẵn lẻ. Theo định lý điều kiện cần (Cận Hamming): 151 1. Xây dựng bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: 2. Tìm bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: 3. Xét bộ mã kiểm tra chẵn lẻ độ dài 15 bit có thể tự sửa được 1 bit lỗi trên đường truyền, hãy cho biết số bit kiểm tra chẵn lẻ tối thiểu? 4. Xét bộ mã kiểm tra chẵn lẻ độ dài 8 bit với 4 bit kiểm tra chẵn lẻ. Hãy cho biết số lỗi tự sửa tối đa của bộ mã? Truyền và bảo mật thông tin 152 38 V.5. Phương pháp sinh mã kiểm tra chẵn lẻ nhanh Nhóm cộng tính Đặt vấn đề: „ Như chúng ta đã biết, phương pháp sinh mã kiểm tra chẵn lẻ giúp ta sinh bộ mã kiểm tra chẵn lẻ với số từ mã tương ứng là s=2k „ Với phương pháp này, ta phải xác định từng từ mã một (bằng cách giải hệ phương trình tuyến tính nhị phân). „ Giả sử: k=10 ta phải xác định s=210=1024 từ mã,…Điều này sẽ mất nhiều thời gian nếu k càng lớn. ÆVấn đề đặt ra ở đây là tìm ra một phương pháp sinh bộ mã kiểm tra chẵn lẻ nhanh hơn về mặt thời gian. Phương pháp sinh mã kiểm tra chẵn lẻ dựa theo lý thuyết nhóm sẽ giải quyết vấn đề này. Nhóm G được gọi là một nhóm cộng tính nếu G có các tính chất: - ∀ a, b ∈ G ⇒ a+b ∈ G ( tính chất cộng). - ∀ a, b, c ∈ G ⇒ a + (b + c)= (a + b) + c ( tc kết hợp). - ∃ ∅ ∈ G sao cho ∅ + a = a + ∅ = a, ∀a∈ G - ∀ a ∈ G ∃ -a∈G : a + (-a)=∅ „ Nhóm G là nhóm hoán vị (nhóm Aben) nếu ∀a,b ∈ G=> a + b = b + a. „ Ví dụ: - Tập hợp các số nguyên với phép + thông thường là nhóm Aben. - Tập hợp các số nhị phân có độ dài n bit cùng với phép + trong Modulo 2 tạo thành nhóm Aben. Truyền và bảo mật thông tin 153 Tính chất của bộ mã chẵn lẻ „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 154 Tính chất của bộ mã chẵn lẻ Tính tương đương của bộ mã nhóm cộng tính và bộ từ mã kiểm tra chẵn lẻ được thể hiện qua 2 định lý sau: Định lý 1: tập hợp các từ mã trong bộ mã kiểm tra chẵn lẻ là một nhóm cộng tính. Truyền và bảo mật thông tin „ 155 „ Định lý 2: Nếu tập hợp W là tập các dãy nhị phân với độ dài các dãy cùng bằng n và W là một nhóm Aben với phép cộng Modulo 2 thì W có thể xem như một bộ mã kiểm tra chẵn lẻ được sinh ra từ ma trận A có dạng như sau: Trong đó: - Ma trận A có m dòng và n cột. - Im : là ma trận đơn vị cấp m. - k: là số dãy nhị phân (hay từ mã) độc lập tuyến tính lớn nhất. - n: là độ dài của từ mã và m = n-k: bij: được xác định bằng cách dựa vào hệ phương trình tuyến tính (*) và k từ mã độc lập tuyến tính như sau: w’i=r1r2r3…rm rm+1rm+2…rn. ) , ∀i =1..k Truyền và bảo mật thông tin 156 39 Phương pháp sinh mã kiểm tra chẵn lẻ nhanh Bước khởi tạo: xác định các giá trị n, m, k, s. Bước 1: sinh k từ mã độc lập tuyến tính (đltt). „ Bước 2: cộng tổ hợp các từ mã: + Cộng các tổ hợp của 2 từ mã từ k mã đltt => có từ mã. + Cộng các tổ hợp của 3 từ mã từ k mã đltt từ mã. => có Ck3 … + Cộng các tổ hợp của k từ mã từ k từ mã đltt => có từ mã. Bước 3: Cộng s-1 từ mã đã tìm được để tìm từ mã cuối cùng => = 1 từ mã. Tổng số từ mã s= = 2k từ mã. „ „ „ Truyền và bảo mật thông tin „ „ 157 Ví dụ sinh mã kiểm tra chẵn lẻ nhanh „ „ „ „ „ Truyền và bảo mật thông tin 158 Đặt vấn đề „ Trong một hệ thống liên lạc truyền tin, bên cạnh các yêu cầu thiết bị (như nguồn phát, bộ mã hóa, ênh truyền, bộ giải mã,…) đảm bảo tốt cho việc truyền và nhận dữ liệu thì còn có các khía cạnh khác như phương pháp mã hóa và giải mã sao cho tối ưu là phần rất quan trọng trong hệ thống. „ Vấn đề luôn được đặt ra ở đây là làm thế nào để chỉ ra một phương pháp giải mã tối ưu, có nghĩa hệ thống phải có khả năng phát hiện và sửa lỗi một cách chính xác nhất có thể có khi nhiễu xảy. Bước khởi tạo: n = 6, m = 3, k = 3, s = 2k = 8. Bước 1: Sinh k = 3 từ độc lập truyến tính: w’1=001001, w’2=111010, w’3=110100 Bước 2: Cộng tổ hợp các từ mã. + Cộng các tổ hợp 2 từ mã đltt: w’4=w’1+w’2=110011; w’5=w’1+w’3=111101; w’6=w’2+w’3=001110 + Cộng các tổ hợp 3 từ mã đltt: w’7=w’1+w’2+w’3=000111 Bước 3: xác định từ mã cuối cùng: w’0=w’1+w’2+w’3+w’4+w’5+w’6+w’7=000000 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Có thể sinh k từ mã độc lập tuyến tính bằng cách: Lấy k dãy nhị phân k bit chỉ chứa 1 số 1: L1= 000..001 000..010 L2= … Lk-1= 010..000 Lk= 100..000 Từ đó đi tìm các từ mã dạng r1r2..rmLi V.6. Lược đồ sửa lỗi tối ưu Tìm bộ mã nhóm khi biết trước ma trận kiểm tra: Truyền và bảo mật thông tin Phương pháp sinh mã kiểm tra chẵn lẻ nhanh 159 Truyền và bảo mật thông tin 160 40 Định nghĩa Hiệp hợp „ „ „ Ví dụ Hiệp hợp Gọi W={w1, w2, …,ws} là bộ mã kiểm tra chẵn lẻ. V ={v1, v2, …, } là tập hợp các dãy n bit có thể nhận được ở cuối kênh. Ta gọi một hiệp hợp của W trong V là tập hợp có dạng z + W (z là bộ lỗi) Truyền và bảo mật thông tin Truyền và bảo mật thông tin 162 Ví dụ lược đồ sửa lỗi theo các hiệp hợp „ Bước 1: Lập bảng các hiệp hợp ứng với các bộ lỗi cần thiết - Dòng đầu tiên viết các từ mã wi ∈ W. - Các dòng tiếp theo ứng với cột w0 = 00…00 viết các bộ lỗi z (các bộ lỗi 1 bit, 2 bit,…). - Các dòng ở cột thứ i được xác định bởi z + wi „ Bước 2: Quá trình giải mã :Khi nhận v, ta xác định cột thứ i chứa v và giải mã về wi tương ứng. „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế „ 161 Lược đồ sửa lỗi theo các hiệp hợp Truyền và bảo mật thông tin Xét bộ mã : W={w0=0000, w1=0101, w2=1110, w3=1011}. Các bộ lỗi một bit khác nhau có thể có là z={1000, 0100, 0010, 0001}. ÆCác hiệp hợp ứng với các bộ lỗi 1 bit: w1 w2 w3 w0 0000 0101 1110 1011 Hiệp hợp 1 1000 1101 0110 0011 (với z1=1000) Hiệp hợp 2 0100 0001 1010 1111 (với z2=0100) Hiệp hợp 3 0010 0111 1100 1001 (với z3=0010) Hiệp hợp 4 0001 0100 1111 1010 (với z4=0001) Trong đó: hiệp hợp i = wi + zi „ „ „ 163 Xét ví dụ trước, W={w0=0000, w1=0101, w2=1110, w3=1011}. Lập bảng hiệp hợp w1 w2 w3 w0 0000 0101 1110 1011 Hiệp hợp 1 1000 1101 0110 0011 Hiệp hợp 2 0100 0001 1010 1111 Hiệp hợp 3 0010 0111 1100 1001 Hiệp hợp 4 0001 0100 1111 1010 Quá trình giải mã: + Giả sử nhận v = 0111. Tra trên bảng các Hiệp hợp ta có v ở cột 1Æ v được giải mã về w1 = 0101. + Giả sử nhận v = 1010. Tra trên bảng các Hiệp hợp ta có v ở cột 2 và cột 3 Æ giải mã không chính xác Truyền và bảo mật thông tin 164 41 Ví dụ lược đồ sửa lỗi thông qua bộ lỗi Lược đồ sửa lỗi thông qua bộ lỗi Dựa vào tính chất của bộ sửa lỗi ta có dùng lược đồ giải mã gồm 2 bước sau: „ Bước 1: Lập bảng sửa lỗi: Bộ lỗi (Z) – Bộ sửa lỗi (C=A*Z). „ Bước 2: Quá trình sửa lỗi - Khi nhận được dãy n bit v ∈V, ta xác định bộ điều lỗi C cho v với C=A.v - Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C. - Giải mã w=v+z . Truyền và bảo mật thông tin 165 Ví dụ lược đồ sửa lỗi thông qua bộ lỗi „ + Bộ 0 lỗi + Bộ lối 1 bit Bộ điều chỉnh (C’=A.z) 00000 0000 10000 1000 01000 0100 00100 0010 00010 00001 Bộ mã tương ứng được xác định là: w0=00000, w1=11101 Lược đồ sửa lỗi 2 bit : „ Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 2) Bộ lỗi (z’) Bộ điều chỉnh (C’=A.z) Bộ lỗi 2 bit 10010 1001 01010 0101 0001 00110 0011 1110 00011 1111 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế (4 Bộ ) (Tất cả các bộ 2 lỗi còn lại có trùng bộ điều chỉnh 1 lỗi hoặc trùng nhau) „ Quá trình sửa lỗi Giả sử nhận v=11011, tính C = A.v = 0011 Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C, ta có z0 = 00110 - Giải mã w = v + z0 =11011 + 00110 =11101 = w1 Bước 2: Quá trình sửa lỗi + Giả sử nhận v= 11100, tính C = A.v = 1110 + Tra bảng sửa lỗi để tìm bộ lỗi ứng với C, ta có z0 = 00001 + Giải mã w = v + z0 = 11100 + 00001 = 11101 = w1 (Ghi chú: z’, C’ là các chuyển vị của z, C) „ Truyền và bảo mật thông tin 166 Truyền và bảo mật thông tin Ví dụ lược đồ sửa lỗi thông qua bộ lỗi Bước 1: Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 1) Bộ lỗi (z’) „ 167 Truyền và bảo mật thông tin 168 42 Xác suất truyền đúng „ „ Bài tập Gọi Ni là số bộ lỗi ứng với i lỗi có thể tự sửa, khi đó xác suất truyền đúng và tự điều chỉnh sẽ là: „ Ví dụ: xét trường hợp các ví dụ trên với n= 5 và tự sửa e = 2 bit lỗi. Áp dụng công thức trên ta có: Truyền và bảo mật thông tin - Xây dựng bộ mã kiểm tra chẵn lẻ. - Minh họa lược đồ sửa lỗi thông qua bộ điều chỉnh trong các trường hợp lỗi 1 bit. Tính xác suất truyền đúng cho các trường hợp có thể tự sửa được. 169 V.6. Mã Hamming Mã Hamming là một dạng mã nhóm (mã kiểm tra chẵn lẻ) được xác định từ ma trận kiểm tra chẵn lẻ A có dạng sau: - Cột thứ j của ma trận A là biểu diễn nhị phân m bit (m là số bit kiểm tra chẵn lẻ) của số j theo qui ước biểu diễn nhị phân của số j được viết theo thứ tự từ dưới lên trên (viết theo cột), tương đương với viết từ trái sang phải (viết theo dòng). - Các bit ở vị trí 2i ( i = 0, 1, 2, …) được chọn làm bit kiểm tra. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 170 Ví dụ ma trận kiểm tra Hamming „ Truyền và bảo mật thông tin 1. Cho ma trận kiểm tra chẵn lẻ sau: 171 „ „ „ Biểu diễn nhị phân của số j = 3 có m = 3 bit như sau: Viết theo dòng: 011 (viết từ trái sang phải) Viết theo cột (viết từ dưới lên) : „ Ví dụ 2: ma trận kiểm tra chẵn lẻ với n=6, m=3 có thể viết như sau: Truyền và bảo mật thông tin 172 43 Tính chất mã Hamming Ví dụ ma trận kiểm tra Hamming „ Từ mã Hamming có dạng: w=r1r2r3r4r5r6. Trong đó, r1r2r4 (vị trí 2i, i=0,1,2 …) là các bit kiểm tra và r3r5r6 là các bit thông tin Truyền và bảo mật thông tin 173 Ví dụ minh họa „ „ Truyền và bảo mật thông tin 174 Chú ý, có thể sử dụng phương pháp sinh mã nhanh: „ Số từ mã của bộ mã Hamming là s = 2k= 8 „ Tìm k từ mã độc lập tuyến tính có dạng: w’1=r1r20r401 w’2=r1r20r410 w’3=r1r21r400 „ Giải các hệ phương trình: A.w1=0, A.w2=0, A.w3=0 để tìm w’1, w’2, w’3 „ Các từ mã còn lại được xác định theo phương pháp sinh mã nhanh. Từ A ⇒ k = n – m = 3. Các bit ở các vị trí 1, 2, 4 được chọn làm các bit kiểm tra. „ Số từ mã của bộ mã Hamming là s = 2k= 8 w’0=r1r20r400 w’1=r1r20r401 w’2=r1r20r410 .. w’7=r1r21r411 Giải các hệ phương trình: A.w1=0, A.w2=0, A.w3=0 … W’={000000, 010101, 100110, 110011, 111000, 101101, 011110, 001011} „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Nếu cho trước số bit (m) và số bit lỗi tự sửa (e) thì số bit tối đa của bộ mã Hamming (n) có thể được ước lượng từ bất đẳng thức sau: Ví dụ minh họa Tìm bộ mã Hamming với n = 6 và m =3 Ta có thể viết ngay ma trận kiểm tra chẵn lẻ cho bộ mã Hamming Truyền và bảo mật thông tin „ 175 Truyền và bảo mật thông tin 176 44 Bài tập V.7. Thanh ghi lùi từng bước 1. Viết ma trận kiểm tra chẵn lẻ cho bộ mã Hamming với n = 15. 2. Từ kết quả bài tập 1, hãy tìm k từ mã Hamming độc lập tuyến tính tương ứng. 3. Xét bộ mã Hamming với số bit kiểm tra cho trước là m, khi đó: - Độ dài mã tối thiểu là bao nhiêu? - Độ dài mã tối đa là bao nhiêu? Truyền và bảo mật thông tin „ - Fm-1, Fm-2, …, F1, F0 : các bit lưu trữ dữ liệu nhị phân. - am-1, am-2, …, a1, a0 : các công tắc (switch) dùng để đóng (=1) hay mở ( =0). ⊕ là bộ làm tính cộng mudulo 2 sau mỗi xung đồng hồ với dữ liệu do các bit của thanh ghi gửi về. „ Quá trình dịch chuyển lùi: sau mỗi xung đồng hồ thì dữ liệu trong bit Fi sẽ được chuyển về lưu trữ ở bit Fi-1 177 Biểu diễn toán học của thanh ghi LTB „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 178 Biểu diễn toán học của thanh ghi LTB Gọi x = (x0, x1, …, xm-2, xm-1) là giá trị các bit của thanh ghi tại thời điểm trước khi có nhịp xung đồng hồ. x’ = (x’0, x’1, …, x’m-2, x’m-1) là giá trị các bit của thanh ghi sau khi có nhịp xung đồng hồ. Khi đó ta có: x’0=x1 x’1=x2 x’2=x3 … x’m-2=xm-1 x’m-1=a0x0 + a1x1 + …+ am-1xm-1. Truyền và bảo mật thông tin Biểu diễn vật lý của thanh ghi lùi từng bước(LTB): 179 Hay viết theo dạng ma trận ta có x’ = T.x „ Trong đó: - T: Ma trận vuông cấp m. Dòng cuối của ma trận:là các hệ số: a0, a1, …, am-1. - Gốc trên bên phải: là ma trận đơn vị cấp m-1. „ T được gọi là ma trận đặc trưng của thanh ghi lùi từng bước. „ Truyền và bảo mật thông tin 180 45 Biểu diễn toán học của thanh ghi LTB „ „ Ví dụ thanh ghi lui từng bước Quá trình dịch chuyển lùi từng bước của thanh ghi: Gọi: „ Cho thanh ghi lui từng bước sau: Ta có: m=4, a0=1, a1=0, a2=1, a3=0. ÆMa trận đặc trưng của thanh ghi: „ „ „ „ Giá trị của thanh ghi sau 1 xung đồng hồ là x(1)=T.x(0) Giá trị của thanh ghi sau 2 xung đồng hồ là x(2)=T.x(1)=T2.x(0) Giá trị của thanh ghi sau 3 xung đồng hồ là x(3)=T.x(2)=T3.x(0) Truyền và bảo mật thông tin 181 Chu kỳ của thanh ghi „ „ „ 182 Truyền và bảo mật thông tin Ví dụ tìm chu kỳ của thanh ghi Chu kỳ của thanh ghi là số xung nhịp đồng hồ để thanh ghi lặp lại trạng thái ban đầu. Nghĩa là nếu x(0) ≠0 và ∃ n>0 sao cho x(n)= x(0) thì ta nói n là chu kỳ của thanh ghi. Bởi vì số trạng thái của x(i) là hữu hạn (2m) nên thanh ghi có chu kỳ Lưu ý: viết x(i)=3 (011) tương ứng „ „ Ta có: m=4, a0=1, a1=0, a2=1, a3=0. Nếu khởi tạo x(0)=0001, khi đó: => Chu kỳ=6 Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 183 Truyền và bảo mật thông tin 184 46 Ví dụ tìm chu kỳ của thanh ghi Bài tập Tương tự: + Khi chọn x(0) = 3 thi ta cũng có chu kỳ n = 6. + Khi chọn x(0)= 6 thì ta có chu kỳ n = 3. + Khi chọn x(0)= 0 thì ta có chu kỳ n = 1. „ Truyền và bảo mật thông tin „ 185 Đa thức đặc trưng của thanh ghi LTB „ „ „ „ Đa thức (xn+ 1)>= gm(x) luôn chia hết cho đa thức đặc trưng của thanh ghi gm(x) Ví dụ: xét lại thanh ghi lui từng bước như như ví dụ trước có gm(x)=1+x2+x4, chu kỳ n=6 thực hiện phép chia (x6 + 1):(x4+x2+1) (phép toán Modulo 2) x4+x2+1 x6 +1 6 4 2 x + x +x x2 +1 x4+x2 +1 x4+x2+1 Chú ý: Hai phép toán 0 a0 = 1, a1= 0, a2 = 1, a3 = 0 ÆĐa thức đặc trưng của thanh ghi là: gm(x)=1 + x2 + x4 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 186 Truyền và bảo mật thông tin Quan hệ giữa chu kỳ n, đa thức đăc trưng và đa thức (xn + 1) Định nghĩa: đa thức đặc trưng của thanh ghi lui từng bước có ma trận đặc trưng là T là đa thức có dạng gm(x)=a0 + a1x+ a2x2+ …+am-1xm-1 + xm với a0, a1, a2,…, am-1 là các công tắc của thanh ghi và m là số bit của thanh ghi Ví dụ Truyền và bảo mật thông tin Tìm các chu kỳ của thanh ghi lui từng bước như hình sau: 187 Truyền và bảo mật thông tin và là như nhau 188 47 Thủ tục sinh thanh ghi lùi từng bước Ví dụ sinh thanh ghi lùi từng bước Sinh thanh ghi lùi từng bước với số bit là m và có chu kỳ n: „ Bước 1: xác định đa thức đặc trưng của thanh ghi - Tìm 2 đa thức gm(x)=a0 + a1x+ a2x2+ …+am-1xm-1 + xm và hk(x)=h0 + h1x+ h2x2+ …+hk-1xk-1 + xk sao cho (xn + 1) = gm(x)* hk(x). - Nếu ∃ (xn + 1) = gm(x)* hk(x) thì ta chọn gm(x) làm đa thức đặc trưng và thực hiện bước 2. Ngược lại: không tồn tại thanh ghi theo yêu cầu. „ Bước 2: xác định thanh ghi từ đa thức đặc trưng gm(x)=a0 + a1x+ a2x2+ …+am-1xm-1 + xm Truyền và bảo mật thông tin „ „ „ „ 189 Tìm gm(x) Thiết kế thanh ghi có m=4 bit và chu kỳ n=7 Bước 1: Xác định đa thức đặc trưng của thanh ghi Ta có (x7 + 1)=(1 + x2 + x3)(1 + x2 + x3 + x4) Do m=4 nên chọn g4(x) = (1 + x2 + x3 + x4) làm đa thức đặc trưng của thanh ghi. Truyền và bảo mật thông tin 190 V.8. Mã xoay vòng Giải pt: x7+ 1=(x4+a3x3+a2x2+a1x+a0)(x3+h2x2+h1x+h0 ) h2 +a3 = 0 h1+a3h2+a2 = 0 h0+a3h1+a2h2+a1 = 0 a3h0+a2h1+a1h2+a0 =0 <=> a2h0+a1h1+a0h2 =0 a1h0+a0h1 =0 a0h0 =1 „ „ Định nghĩa mã xoay vòng Mã xoay vòng là mã kiểm tra chẵn lẻ được sinh ra từ ma trận kiểm tra chẵn lẻ ứng với chu kỳ n của thanh ghi lùi từng bước có dạng như: A=[x(0)| Tx(0)|T2x(0) |…|Tn-1x(0) ] „ <=>a3 =1, a2=1, a1=0, a0=1, h2 =1, h1=0, h0=1 Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 191 Truyền và bảo mật thông tin 192 48 Phương pháp sinh nhanh bộ mã xoay vòng Ví dụ 1 „ „ „ Từ thanh ghi : m=4, a0=1, a1=0, a2=1, a3=0 đã xét, có chu kỳ n=6: Khởi tạo x(0)=1 ta có: A=[x(0) x(1) x(2) x(3) x(4) x(5)] Ta có n=6, m=3, k=2 ⇒ s = 2k = 22 = 4 từ mã. Truyền và bảo mật thông tin 193 Bước 1: sinh mã xoay vòng đầu tiên Sinh mã xoay vòng đầu tiên có dạng w1=a0a1a2…am-11000..00 „ k-1 bit 0 „ Bước 2: sinh k -1 từ mã độc lập tuyến tính còn lại: w2= 0a0a1a2…am-1100…0 (dịch vòng w1 sang phải 1 bit). … wk= 000…00a0a1a2…am-11 (dịch vòng wk-1 sang phải 1 bit). „ Bước 3: xác định các từ mã còn lại của bộ mã Các từ mã còn lại gồm (2k – k từ mã) được xác định bằng cách cộng tổ hợp của 2, 3, …, k từ mã từ k từ mã độc lập tuyến tính ở trên. Truyền và bảo mật thông tin 194 Một số đa thức đặc trưng Phần II. Bảo mật thông tin Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 195 49 I.1. An toàn thông tin „ Chương I. „ Giới thiệu về bảo mật thông tin Từ xưa … An toàn bảo mật thông tin đảm bảo bằng „ „ Giao thức, cơ chế Các điều luật Thông tin ngày nay phần lớn được lưu và vận chuyển trên các phương tiện điện tử Æ phương tiện bảo mật: mật mã học „ Truyền và bảo mật thông tin Các phương pháp bảo vệ an toàn thông tin Nội dung an toàn thông tin Các phương pháp bảo vệ an toàn thông tin „ Bảo vệ an toàn thông tin bằng các biện pháp hành chính. „ Bảo vệ an toàn thông tin bằng các biện pháp kỹ thuật (phần cứng). „ Bảo vệ an toàn thông tin bằng các biện pháp thuật toán (phần mềm). Biện pháp hiệu quả nhất và kinh tế nhất hiện nay trên mạng truyền tin và mạng máy tính là biện pháp thuật toán. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 198 199 „ „ „ Tính bí mật: tính kín đáo riêng tư của thông tin Tính xác thực của thông tin, bao gồm xác thực đối tác( bài toán nhận danh), xác thực thông tin trao đổi. Tính trách nhiệm: đảm bảo người gửi thông tin không thể thoái thác trách nhiệm về thông tin mà mình đã gửi. Truyền và bảo mật thông tin 200 50 I.3. Khái niệm hệ mã mật (CryptoSystem) I.2. Mật mã học (cryptology) Bao gồm: „ Mật mã học (cryptography): là khoa học nghiên cứu cách ghi bí mật và xác thực thông tin. „ Thám mã(cryptanalysis): là khoa học nghiên cứu cách phá mã hoặc tạo mã giả. „ „ Định nghĩa 1.1 Một hệ mật là một bộ 5 (P,C,K,E,D) thoả mãn các điều kiện sau: 1. 2. 3. 4. P là một tập hữu hạn các bản rõ có thể. C là một tập hữu hạn các bản mã có thể. K (không gian khoá) là tập hữu hạn các khoá có thể. Đối với mỗi k∈ K có một quy tắc mã ek: P → C và một quy tắc giải mã tương ứng dk ∈ D. Mỗi ek: P → C và dk: C → P là những hàm mà: dk(ek (x)) = x với mọi bản rõ x ∈ P. Truyền và bảo mật thông tin 201 I.4. Mô hình truyền tin cơ bản Truyền và bảo mật thông tin I.5. Luật Kirchoff (1835 - 1903) „ „ „ „ Thông điệp X là bản rõ (Plaintext), được mã hóa với khóa K1 Æ văn bản mã hóa Y (Ciphertext) Quá trình giải mã chuyển YÆX sử dụng khóa K2 Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 202 203 Theo luật Kirchoff (1835 - 1903)(một nguyên tắc cơ bản trong mã hóa) thì: toàn bộ cơ chế mã/giải mã trừ khoá là không bí mật đối với kẻ địch. Khi đối phương không biết được hệ mã mật đang sử dụng thuật toán mã hóa gì thì việ̣c thám mã sẽ rất khó khăn. Nhưng chúng ta không thể tin vào độ an toàn của mật mã chỉ dựa vào giả thiết không chắc chắn đối phương không biết thuật toán đang sử dụng. Truyền và bảo mật thông tin 204 51 I.6. Phân loại các thuật toán mật mã học I.6. Phân loạ i các thuật toán mật mã học Phân loại theo khóa và ứng dụng 1. Hệ mật đối xứng (hay còn gọi là mật mã khóa bí mật): là những hệ mật dung chung một khoá cả trong quá trình mã hoá dữ liệu và giải mã dữ liệu. Do đó khoá phải được giữ bí mật tuyệt đối. 2. Hệ mật mã bất đối xứng (hay còn gọi là mật mã khóa công khai) : Hay còn gọi là hệ mật mã công khai, các hệ mật này dùng một khoá để mã hoá sau đó dùng một khoá khác để giải mã. Các khoá này tạo nên từng cặp chuyển đổi ngược nhau và không có khoá nào có thể suy được từ khoá kia. Khoá dùng để mã hoá có thể công khai nhưng khoá dùng để giải mã phải giữ bí mật. Phân loại theo khóa và ứng dụng: 3. Các thuật toán tạo chữ ký điện tử (Digital Signature Algorithms). Thông thường mỗi hệ chữ ký điện tử có cùng cơ sở lý thuyết với một hệ mã mật khóa công khai nhưng với cách áp dụng khác nhau. 4. Các hàm băm (Hash functions). Các hàm băm là các thuật toán mã hóa không khóa hoặc có khóa và thường được sử dụng trong các hệ chữ ký điện tử hoăc các hệ mã khóa công khai, mã hóa mật khẩu… Truyền và bảo mật thông tin 205 Truyền và bảo mật thông tin 206 I.6. Phân loại các thuật toán mật mã học I.6. Phân loại các thuật toán mật mã học Phân loại theo cách xử lý dữ liệu vào: 1. Các thuật toán mã hóa khối (DES , AES …) xử lý bản rõ dưới các đơn vị cơ bản là các khối có kích thước giống nhau. 2. Các thuật toán mã hóa dòng coi bản rõ là một luồng bit, byte liên tục. Phân loại theo thời gian ra đời: 1. Mật mã cổ điển (là hệ mật mã ra đời trước năm 1970) 2. Mật mã hiện đại (ra đời sau năm 1970) Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 207 Truyền và bảo mật thông tin 208 52 I.7. Quan điểm về độ an toàn của hệ mật „ Có hai quan điểm : Độ an toàn tính toán và độ an toàn không điều kiện „ Độ an toàn tính toán „ Liên quan đến nỗ lực tính toán để phá một hệ mật „ Hệ mật an toàn về tính toán: thuật toán phá tốt nhất cần ít nhất N phép toán, N rất lớn, thực tế không có hệ mật nào thỏa mãn „ Trên thực tế nếu có một phương pháp tốt nhất phá được hệ mật này nhưng yêu cầu thời gian lớn đến mức không chấp nhận được „ Có thể quy về bài toán khó Truyền và bảo mật thông tin „ Hệ mật an toàn không điều kiện nếu nó không thể bị phá ngay cả khi không hạn chế khả năng tính toán ⇒ Độ an toàn không điều kiện của một hệ mật không thể nghiên cứu theo độ phức tạp tính toán mà sẽ dùng lí thuyết xác suất „ Truyền và bảo mật thông tin „ Định nghĩa 1: X và Y là các biến ngẫu nhiên „ p(x): xác suất (xs) để X nhận giá trị x „ p(y): xs để Y nhận giá trị y „ p(x, y): xs đồng thời để X nhận giá trị x và Y nhận giá trị y. „ p(x| y): xs để X nhận giá trị x với điều kiện (đk) Y nhận giá trị y. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế „ „ X và Y được gọi là độc lập nếu p(x, y) = p(x).p(y), với | x є X và | y є Y. Quan hệ giữa xs đồng thời và xs có điều kiện được biểu thị theo công thức sau: p(x,y) = p(x).p(y|x) = p(y).p(x|y) Định lý Bayes „ 211 210 I.9. Quan điểm về độ an toàn của hệ mật Một số kiến thức cơ bản về lí thuyết xác suất „ Độ an toàn không điều kiện 209 I.9. Quan điểm về độ an toàn của hệ mật „ I.7. Quan điểm về độ an toàn của hệ mật Nếu p(y) > 0 thì: Truyền và bảo mật thông tin 212 53 I.7. Quan điểm về độ an toàn của hệ mật „ Hệ quả 1 „ I.7. Quan điểm về độ an toàn của hệ mật „ X và Y là các biến độc lập khi và chỉ khi: p(x|y) = p(x) với mọi x, y. „ Độ mật hoàn thiện „ „ Định ngĩa: Một hệ mật có độ mật hoàn thiện nếu: pP(x|y) = pP(x), với mọi x thuộc P, y thuộc C Trong đó: pP(x): sx tiên nghiệm để bản rõ xuất hiện „ ÆÝ nghĩa: đối phương có bản mã cũng không thu nhận thông tin gì về bản rõ Truyền và bảo mật thông tin Đị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. Æ Để có độ mật hoàn thiện cần có khóa rất dàiÆ chuyển giao khóa khó khăn Æ trong thực tế không có độ an toàn không điều kiện mà chỉ an toàn thực tế, tức là tùy thuộc thông tin và thời gian cần bảo mật 213 Truyền và bảo mật thông tin 214 II.1. Các hệ mã cổ điển Chương II. CÁC HỆ Mà KHÓA BÍ MẬT 1. 2. 3. 4. 5. 6. 7. Hệ mã đẩy Hệ mã thế vị Hệ mã Affine Hệ mã Vigenere Hệ mã Hill Hệ mã hoán vị Các hệ mã dòng Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 216 54 II.1.1. Hệ mã đẩy (Shift Cipher) „ „ „ „ „ „ II.1.1. Hệ mã đẩy (shift Cipher) A 0 Giả sử không gian bản rõ P là các thông điệp tạo ra từ bảng chữ cái A, số phần tử của A: |A|=N Không gian bản mã C≡P Để mã hóa: đánh số thứ tự chữ cái 0..N-1 Không gian khóa K=ZN Mã hóa: Ek(x) = (x + k) mod N. Giải mã: Dk(y) = (y – k) mod N. Truyền và bảo mật thông tin „ „ „ 217 „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế D 3 … L M N … W X Y Z … 11 12 13 … 22 23 24 25 Cho C=QEHECUYEHI thông điệp là tiếng việt không dấu Truyền và bảo mật thông tin 218 II.1.2. Hệ mã thế vị Sử dụng thay thế đơn âm nên Æ phụ thuộc tần suất của xuất hiện của ngôn ngữ tự nhiên(một số chữ cái xuất hiện nhiều hơn các chữ khác) Æ người thám mã có thể sử dụng phương pháp thử các ký tự xuất hiện nhiều. Không gian khóa là N nhỏ (bảng chữ tiếng anh N=26) Æ có thể thám mã bằng phương pháp vét cạn các khóa Truyền và bảo mật thông tin C 2 Ví du : với k=3 (hoàng đế La Mã Julius Caesar đã sử dụng), ḱý tự A được thay bằng D, B thay bằng E , ... , W thay bằng Z , ... , X thay bằng A , Y thay bằng B, Z thay bằng C. Xâu “ANGLES” sẽ được mã hóa thành “DQJOHV” Bài tập: Với k=5, C=QFRGFNYFU, tìm P? „ II.1.1. Hệ mã đẩy (Shift Cipher) „ B 1 219 Cho P =C = Z26; „ K chứa mọi hoán vị có thể của 26 kí hiệu 0,1, . . . ,25 „ Với mỗi phép hoán vị π ∈K , ta định nghĩa: eπ(x) = π(x) và dπ(y) = π-1(y) trong đó π-1 là hoán vị ngược của π. „ Truyền và bảo mật thông tin 220 55 Ví dụ mã thế vị „ „ Ví dụ mã thế vị Ví dụ một phép hoán vị π: Ta có: eπ(D)=A, eπ(J)=Q … „ „ Hàm giải mã là phép hoán vị ngược: dπ(A)=D, dπ(Q)=J … A B C D E F G H I J K L M A B C D E F G H I J K L M X N Y A H P O G Z Q W B T D L R Y V O H E Z X W P t N O P Q R S T U V W X Y Z N O P Q R S T U V W X Y Z S F L R C V M U E K J D I B G F J Q N M U S K A C i Truyền và bảo mật thông tin 221 Không gian khóa mã thế vị „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 222 II.1.3. Hệ mã Affine Số các hoán vị này là 26!, lớn hơn 4 ×1026 là một số rất lớn. Bởi vậy, phép tìm khoá vét cạn không thể thực hiện được, thậm chí bằng máy tính. Tuy nhiên, mã thế vị có thể dễ dàng bị thám bằng các phương pháp dò thử theo tần suất ký tự. Truyền và bảo mật thông tin Truyền và bảo mật thông tin 223 Các định nghĩa „ Giả sử a ∈ Zm, phần tử đảo ứng với phép nhân của a là phần tử a-1∈ Zm sao cho aa-1= a-1a=1 (mod m) „ Định lý về sự tồn tại của phần tử nghịch đảo : Nếu UCLN(a, m) = 1 thì tồn tại duy nhất 1 số b ∈Zm là phân tử nghịch đảo cua a, nghĩa là thỏa mản a.b = (a*b) mod m = 1. „ Tập các số nguyên trong Zm là nguyên tố cùng nhau với m gọi là Zm* „ Số lượng các số nguyên trong Zm là nguyên tố cùng nhau với m ký hiệu là φ(m) (gọi là hàm Euler) Truyền và bảo mật thông tin 224 56 Hệ mã Affine „ „ „ „ Không gian bản rõ và bản mã là hình thành từ bảng chữ cái A. Giả sử |A|=N, khi đó không gian khóa được xác định: K={(a,b): a, b ∈ ZN, UCLN(a, N)=1} Số khóa có thể sử dụng φ(N) *N Mã hóa: „ „ „ Ví dụ hệ mã Affine „ „ „ „ „ „ Đánh thứ tự chữ cái 0, 1, .. N-1 ek(x)=(a*x+b) mod N (ký tự thứ x chuyển thành ký tự thứ (a*x+b) mod N ) „ „ Giải mã: „ „ dk(y)=a-1(y-b) mod N Truyền và bảo mật thông tin 225 Ví dụ hệ mã Affine Giải mã ? „ Bản mã: AXG (tương ứng 0, 23, 6) -1 „ Ta có: 7 = 15 (vì 7*15 mod 26=1) =>Hàm giải mã: dk(y)=15(y-3) =15y-45=15y+7 „ „ Truyền và bảo mật thông tin 226 Bài tập „ „ Xét tập chữ cái tiếng Anh (Z26) Giả sử K = (7,3). Bản rõ: HOT Hàm lập mã: ek(x)=7x+3 Các số tương ứnglà 7, 14 và 19. Bây giờ sẽ mã hoá: Ek(H)= (7 × 7 +3) mod 26 =0 Ek(O)=(7 × 14 + 3) mod 26=23 Ek(T)=(7 × 19 +3) mod 26 =6 =>Bản mã: AXG „ Mối quan hệ giữa các hệ mã đẩy, mã thế vị và mã Affine? (15*0+7) mod 26=7 (15*23+7) mod 26=326 mod 26=14 (15*6+7) mod 26=19 Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 227 Truyền và bảo mật thông tin 228 57 II.1.4. Mật mã Vigenère „ „ „ „ „ „ „ Mật mã Vigenère Lấy tên của nhà mật mã học người Pháp Blaise de Vigenère (1523-1596) Thông điệp sử dụng bảng chữ cái A. Các ký tự được đánh số 0, 1, ... N-1, với N =|A| Không gian khóa K được xác định: Với mỗi số nguyên dương M , khóa có độ dài M là một xâu ký tự có độ dài M , K=k1k2…kM. Để mã hóa một bản rõ P: chia P ra làm các đoạn có độ dài M, chẳng hạn X=x1x2,… xM, khi đó: Ek(X) = (x1 + k1, x2 + k2 , …, xM + kM ) mod N Dk(Y) = (y1 - k1, y2 - k2, …, yM - kM) mod N Truyền và bảo mật thông tin „ „ „ „ „ K = 2 8 15 7 4 17, P = 19 7 8 18 2 17 | 24 15 19 14 18 23 | 18 19 4 12 8 18 | 13 14 19 18 4 2 | 20 17 4. Từ đó: „ „ 229 Bài tập „ Ví dụ „ A là bảng chữ cái tiếng Anh Æ N=26 „ K=“CIPHER”, „ Bản rõ P=“THISCRYPTOSYSTEMISNOTSECURE” „ Ta có: C = 21 15 23 25 6 8 | 0 23 8 21 22 14 | 20 1 19 19 12 9 | 15 22 8 25 8 19 | 22 25 19 C= “VPXZGIAXIVWOUBTTMJPWIZITWZT” Truyền và bảo mật thông tin 230 II.1.5. Hệ mã Hill Với tập các ký tự tiếng Anh, cho K=KHOA Bản mã c=FPSTMOIOXNHRSUVMKAWNR Tìm bản rõ p? „ „ „ „ „ „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 231 Do Lester S.Hill đưa ra năm 1929 Không gian bản rõ và bản mã là bảng chữ cái A. Các chữ cái được đánh số từ 0 đến N-1 (N=|A|) Với mỗi số nguyên M, khóa là một ma trận vuông kích thước M, điều kiện là tồn tại ma trận nghịch đảo của K trên ZN. Để mã hóa, chia bản rõ thành các xâu có độ dài M. Mã hóa: C=P*K Giải mã: P=C*K-1 Truyền và bảo mật thông tin 232 58 Hệ mã Hill Hệ mã Hill Ví dụ: cho hệ ma Hill có M = 2 (khóa là các ma trận vuông cấp 2) và bảng chữ cái là bảng chữ cái tiếng Anh (N = 26). Cho khóa: K= ⎛⎜ 3 3 ⎞⎟ => Bản mã thu được: C = “DPLE”. Để giải mã, cần tính ma trận nghịch đảo K-1 trên Z26 „ Với K= k ⎞ ⎛k ⎜⎜ ⎟ k k định thức: det(K) =⎟⎠ (k11*k22 – k21*k12) mod N ⎝ Điều kiện det(K)-1 tồn tại, khi đó: K-1= det(K)-1 * ⎜2 ⎝ „ „ „ „ 5 ⎟⎠ Hay mã hóa xâu P = “HELP” và giải mã ? Chia P ra làm P1=“HE” (7,4) và P2=“LP” (11,15) ⎛3 ⎜⎜ ⎝2 Với P1 = (7 4) ta có C1 = P1 * K = (7 4) = (7*3+4*2 7*3+4*5 )= (3 15) = (D P) Với P2 = (11 15) ta có C2 = (11,15) =(11 4) = (L E) ⎛3 ⎜⎜ ⎝2 3⎞ ⎟ 5 ⎟⎠ 12 21 22 ⎛ k 22 ⎜⎜ − k ⎝ 21 3⎞ ⎟ 5 ⎟⎠ 233 Truyền và bảo mật thông tin 11 − k12 ⎞ ⎟ k11 ⎟⎠ Truyền và bảo mật thông tin 234 Hệ mã Hill II.1.6. Mã hoán vị Áp dụng: det(K) = (15 - 6) mod 26 = 9. -> det(K)-1 =3 (vì 9*3=1 (mod 26) ) Ý tưởng của MHV là giữ các ký tự của bản rõ không thay đổi nhưng sẽ thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này „ Giả sử không gian bản rõ P là các thông điệp tạo ra từ bảng chữ cái A, số phần tử của A: |A|=N „ Không gian bản mã C≡P „ Cho m là một số nguyên dương xác định nào đó „ Cho K gồm tất cả các hoán vị của {1, . . ., m}. Đối một khoá π ( tức là một hoán vị) ta xác định: „ eπ(x1, . . . , xm ) = (xπ(1), . . . , xπ(m)) „ dπ(x1, . . . , xm ) = (yπ -1(1), . . . , yπ -1(m)) trong đó π-1 là hoán vị ngược của π => K-1= 3* ⎛ 5 23 ⎞ ⎟⎟ = ⎜⎜ ⎝ 24 3 ⎠ ⎛ 3 * 5 3 * 23 ⎞ ⎜⎜ =⎟⎟ ⎝ 3 * 24 3 * 3 ⎠ „ ⎛ 15 17 ⎞ ⎟⎟ ⎜⎜ ⎝ 20 9 ⎠ Quá trình giải mã như khi mã hóa, sử dụng công thức P=C*K-1 Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 235 Truyền và bảo mật thông tin 236 59 Ví dụ mã hoán vị „ II.1.7. Các hệ mã dòng Giải sử m=6 và khóa là hoán vị π =(3, 5, 1, 6, 4, 2): „ 1 2 3 4 5 6 3 5 1 6 4 2 Bản rõ SHESELLSSEASHELLSBYTHESEASHORE Chia 6 nhóm: SHESEL | LSSEAS | HELLSB | YTHESE | ASHORE „ Mỗi nhóm 6 chữ cái được sắp xếp lại theo phép hoán vị π, ta có: EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS ÆBản mã: EESLSHSALSESLSHBLEHSYEETHRAEOS „ Để giả mã, ta làm tương tự, dùng hoán vị ngược π-1: „ „ „ 1 2 3 4 5 6 3 6 1 5 2 4 Truyền và bảo mật thông tin „ 237 Hoạt động hệ mã dòng „ „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 238 Định nghĩa hệ mã dòng Giả sử k ∈K là khoá và x = x1x2… là xâu bản rõ. Hàm fi được dùng để tạo zi (zi là phần tử thứ i của dòng khoá) trong đó fi là một hàm của khoá k và i-1 ký tự đầu tiên của bản rõ: zi = fi (k, x1 ,…, xi -1 ) Phần tử zi của dòng khoá được dùng để mã xi tạo ra yi = eiz(xi). Bởi vậy, để mã hoá xâu bản rõ x1 x2 . . . ta phải tính liên tiếp: z1, y1, z2 , y2 ... Việc giải mã xâu bản mã y1y2… có thể được thực hiện bằng cách tính liên tiếp: z1, x1, z2 , x2 ... Truyền và bảo mật thông tin Trong các hệ mật nghiên cứu ở trên, các phần tử liên tiếp của bản rõ đều được mã hoá bằng cùng một khoá k. Tức xâu bản mã y nhận được có dạng: y = y1y2. . . = ek(x1) ek(x2 ) . . . Các hệ mật thuộc dạng này thường được gọi là các mã khối. Một quan điểm sử dụng khác là mật mã dòng. Ý tưởng cơ bản ở đây là tạo ra một dòng khoá z = z1z2 . . . và dùng nó để mã hoá một xâu bản rõ x = x1x2 . . . theo quy tắc: y = y1y2. . . = ez1(x1)ez2(x2). . . 239 Mật mã dòng là một bộ (P,C,K,L,F,E,D) thoả mãn được các điều kiện sau: P là một tập hữu hạn các bản rõ có thể. 2. C là tập hữu hạn các bản mã có thể. 3. K là tập hữu hạn các khoá có thể (không gian khoá) 4. L là tập hữu hạn các bộ chữ của dòng khoá. 5. F = (f1 f2...) là bộ tạo dòng khoá. Với i ≥ 1 fi : K × P i -1 → L 6. Với mỗi z ∈L có một quy tắc mã ez ∈ E và một quy tắc giải mã tương ứng dz ∈D , ez : P →C và dz : C →P là các hàm thoả mãn dz(ez(x))= x với mọi bản rõ x ∈ P. Ta có thể coi mã khối là một trường hợp đặc biệt của mã dòng trong đó dùng khoá không đổi: Zi = K với mọi i ≥1. 1. Truyền và bảo mật thông tin 240 60 Một số dạng đặc biệt của hệ mã dòng „ „ Ví dụ phương pháp sinh chuổi khóa Mã dòng được gọi là đồng bộ (synchronous) nếu dòng khoá không phụ thuộc vào xâu bản rõ, tức là nếu dòng khoá đựợc tạo ra chỉ là hàm của khoá k. Khi đó ta coi k là một “hạt giống" để mở rộng thành dòng khoá z1z2… Một hệ mã dòng được gọi là tuần hoàn (periodic) với chu kỳ d nếu zi+d= zi với số nguyên i ≥ 1. 1. „ „ „ Truyền và bảo mật thông tin Mã Vigenère với độ dài từ khoá m có thể coi là mã dòng tuần hoàn với chu kỳ m. Trong trường hợp này, khoá là K = (k1, . . . km ). Bản thân K sẽ tạo m phần tử đầu tiên của dòng khoá: zi = ki, 1 ≤ i ≤ m. Sau đó dòng khoá sẽ tự lặp lại. Các hàm mã và giải mã được dùng giống như các hàm mã và giải mã được dùng trong mã đẩy: ez(x) = x+z và dz(y) = yz Các mã dòng thường được mô tả trong bảng chữ nhị phân: P=C=L=Z2. Æ hàm mã và giải mã chỉ là phép cộng Modulo 2: ez(x) = x +z mod 2 và dz(x) = y + z mod 2 241 Truyền và bảo mật thông tin 242 Ví dụ phương pháp sinh chuổi khóa Ví dụ 2. Ví dụ phương pháp sinh chuổi khóa (đồng bộ): „ Giả sử bắt đầu với (k1, . . , km ) và zi = ki, với 1 ≤ i ≤ m; với i>m: Giả sử m=4 và chuổi khóa được sinh theo quy tắc: zi+4=(zi+zi+1) mod 2 „ Nếu dòng khoá bắt đầu khác vector (0,0,0,0) Æ dòng khoá có chu kỳ 15. „ Ví dụ bắt đầu bằng véc tơ (1,0,0,0), dòng khoá sẽ là: 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 m-1 zi+m = ∑ cj zi+j mod 2 j=0 „ trong đó c0, .., cm-1 ∈ Z2 là các hằng số cho trước. • Ở đây khoá K gồm 2m giá trị k1, . . , km, c0, . . , cm-1. • Véc tơ khởi đầu bất kì (k1, . . , km) khác dãy toàn số 0 tạo nên một dòng khoá có chu kỳ 2m -1 Æ một khoá ngắn sẽ tạo nên một dòng khoá có chu kỳ rất lớn Æ hạn chế việc thám mã Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 243 Truyền và bảo mật thông tin 244 61 Thanh ghi hồi tiếp tuyến tính Mã khóa tự sinh - Autokey Thanh ghi hồi tiếp tuyến tính (linear feedback shift register LFSR) để tạo dòng khoá bằng phần cứng: „ Dùng một bộ ghi dịch có m tầng. „ Véc tơ (k1,.., km) dùng để khởi tạo cho thanh ghi dịch. „ Ở mỗi đơn vị thời gian, các phép toán sau sẽ được thực hiện đồng thời: 1. k1 được tính ra dùng làm bit tiếp theo của dòng khoá. 2. k2,.., km sẽ được dịch một tầng về phía trái. 3. Giá trị mới của km sẽ được tính bằng: „ „ „ + m-1 Cho P = C = K = L = Z26 Cho z1 = k và zi = xi-1 (i ≥ 2) Với 0 ≤ z ≤ 25 ta xác định: ez(x) = x + z mod 26 dz(y) = y - z mod 26 (x,y ∈ Z26 ) ∑ cjkj+1 j=0 k1 k2 k3 k4 Hình -LFSR cho chuổi khóa zi+4=zi+zi+1 mod 2 Truyền và bảo mật thông tin 245 Mã khóa tự sinh - Autokey Ví dụ: Giả sử khoá là k = 8 và bản rõ là “rendezvous”. Trước tiên ta biến đổi bản rõ thành dãy các số nguyên: 17 4 13 3 4 25 21 14 20 18 „ Dòng khoá như sau: 8 17 4 13 3 4 25 21 14 20 „ Bây giờ ta cộng các phần tử tương ứng rồi rút gọn theo modulo 26: 25 21 17 16 7 3 20 9 8 12 „ Bản mã ở dạng ký tự là: ZVRQHDUJIM „ Để giải mã biến đổi xâu kí tự thành dãy số: 25 21 17 16 7 3 20 9 8 12 Sau đó tính: „ „ „ 246 II.2. Các hệ mã chuẩn „ „ Truyền và bảo mật thông tin „ „ II.2.1. Hệ DES II.2.2. Các chuẩn mã dữ liệu nâng cao x1 = d8(25) = (25 – 8) mod 26 = 17 x2 = d17(21) = (21 – 17) mod 26 = 4 Cứ tiếp tục như vậy cho các ký tự tiếp theo. Lưu ý: Mã dùng khoá tự sinh là không an toàn do chỉ có 26 khoá. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 247 Truyền và bảo mật thông tin 248 62 II.2.1. Hệ DES „ „ „ „ „ „ Đặc tả DES Hệ DES (Data Encryption Standard – chuẩn mã hóa dữ liệu) Ban đầu được IBM phát triển Lần đầu tiên DES được công bố trong Hồ sơ Liên bang vào ngày 17.3.1975. Sau nhiều cuộc tranh luận công khai, DES đã được chấp nhận chọn làm chuẩn cho các ứng dụng vào 5.1.1977. Được áp dụng rộng rãi trên toàn thế giới Được trộn bởi các phép thế và hoán vị Truyền và bảo mật thông tin „ „ 249 B2: Sau đó tính toán 16 lần lặp theo một hàm xác định. Ta sẽ tính LiRi, 1≤ i ≤ 16 theo quy tắc sau: Li = Ri-1; Ri = Li-1 ⊕ f(Ri-1, ki) „ Trong đó: „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin „ ⊕ là phép cộng modulo 2 (loại trừ) của hai xâu bit f là một hàm sẽ được mô tả ở sau k1, k2, …, k16 là các xâu bit có độ dài 48 được tính như 1 hàm của khóa k (ki chính là một phép chọn hoán vị bit trong k). Truyền và bảo mật thông tin B1: Với bản rõ cho trước x, một xâu bit x0 sẽ được xây dựng bằng cách hoán vị các bit của x theo phép hoán vị cố định ban đầu IP. Ta viết: x0 = IP(x) = L0R0, trong đó L0 gồm 32 bit đầu và R0 là 32 bit cuối. 250 Thuật toán DES „ „ Thuật toán tiến hành theo 3 bước: „ Thuật toán DES „ DES mã hoá một xâu bit x của bản rõ độ dài 64 bit bằng một khoá 56 bit. Bản mã nhận được cũng là một xâu bit có độ dài 64. „ 251 Một vòng của phép mã hóa được mô tả như sau: B3: Áp dụng phép hoán vị ngược IP-1 cho xâu bit R16L16, ta thu được bản mã y. Tức là y = IP-1(R16L16) . Hãy chú ý thứ tự đã đảo của L16 và R16 Truyền và bảo mật thông tin 252 63 Thuật toán DES „ Thuật toán DES Mô tả hàm f: „ „ Hàm f có 2 biến vào: „ „ Xâu bit A có độ dài 32 Xâu bit J có độ dài 48 Hai bit b1b6 xác định biểu diễn nhị phân hàng r của Sj (0≤ r ≤ 3) „ Bốn bit (b2 b3 b4 b5) xác định biểu diễn nhị phân của cột c của Sj (0≤ c ≤ 15). „ Khi đó Sj(Bj) sẽ xác định phần tử Sj(r, c) ; phần tử này viết dưới dạng nhị phân là một xâu bit có độ dài 4 „ Bằng cách tương tự tính các Cj = Sj(Bj) , (1 ≤ j ≤ 8). „ Đầu ra của f là xâu bit có độ dài 32. „ Các bước thực hiện: „ „ „ B1: Biến thứ nhất A được mở rộng thành một xâu bit độ dài 48 theo một hàm mở rộng cố định E. E(A) gồm 32 bit của A (được hoán vị theo cách cố định) với 16 bit xuất hiện hai lần. B2: Tính E(A) ⊕ J và viết kết quả thành một chuỗi 8 xâu 6 bit là B1B2B3B4B5B6B7B8. Truyền và bảo mật thông tin B3: Bước tiếp theo dùng 8 bảng S1S2,…,S8 ( được gọi là các hộp S ). Với mỗi Si là một bảng 4×16 cố định có các hàng là các số nguyên từ 0 đến 15. Với xâu bit có độ dài 6 (kí hiệu Bi = b1 b2 b3 b4 b5 b6), ta tính Sj(Bj) như sau: 253 Thuật toán DES Truyền và bảo mật thông tin 254 Thuật toán DES „ Phép hoán vị ban đầu IP: P „ B4: Xâu bit C = C1 C2 … C8 có độ dài 32 được hoán vị theo phép hoán vị cố định P. Xâu kết quả là P(C) được xác định là f(A, J). Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế „ 255 Bảng này có ý nghĩa là bit thứ 58 của x là bit đầu tiên của IP(x); bit thứ 50 của x là bit thứ 2 của IP(x) Truyền và bảo mật thông tin 256 64 Thuật toán DES „ Thuật toán DES Phép hoán vị ngược IP-1: Truyền và bảo mật thông tin „ 257 Thuật toán DES „ Hàm mở rộng E được xác định theo bảng sau: Truyền và bảo mật thông tin 258 Thuật toán DES Tám hộp S: Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 259 Truyền và bảo mật thông tin 260 65 Thuật toán DES Thuật toán DES „ Truyền và bảo mật thông tin 261 Thuật toán DES „ „ „ Truyền và bảo mật thông tin Trên thực tế k là một xâu bit độ dài 64, trong đó có 56 bit khóa và 8 bit kiểm tra tính chẵn lẻ nhằm phát hiện sai. Các bit ở các vị trí 8, 16, …, 64 được xác định sao cho mỗi byte chứa một số lẻ các số “1”. Bởi vậy, một sai sót đơn lẻ có thể phát hiện được trong mỗi nhóm 8 bit. Các bit kiểm tra bị bỏ qua trong quá trình tính bảng khóa. Các bước tính bảng khóa DES: „ Với một khoá k 64 bit cho trước, ta loại bỏ các bit kiểm tra tính chẵn lẻ và hoán vị các bit còn lại của k theo phép hoán vị cố định PC-1. Ta viết: PC-1(k) = C0D0 „ Với i thay đổi từ 1 đến 16: Ci = LSi(Ci-1) Di = LSi(Di-1) Với LSi là phép chuyển chu trình sang trái 1 hoặc 2 vị trí tùy vào i: „ „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 262 Thuật toán DES Mô tả tính bảng khóa từ khóa k. „ Phép hoán vị P: 263 Đẩy 1 vị trí nếu i=1,2,9 hoặc 16 Đẩy 2 vị trí đối với các trường hợp còn lại Truyền và bảo mật thông tin 264 66 Thuật toán DES Thuật toán DES „ Truyền và bảo mật thông tin 265 Các hoán vị PC-1 và PC-2: Truyền và bảo mật thông tin 266 Giải mã DES Một ví dụ về DES Ta thấy rằng trong quá trình mã hoá tại vòng i: „ Li=Ri-1 „ Ri=Li-1 xor f(Ri-1,Ki) ( Với f(Ri-1,Ki)=P(E(Ri) xor Ki)) Tức là ta cũng có: „ Ri-1 =Li „ Li-1=Ri xor f(Li,Ki) ÆGiải mã từng khối dữ liệu 64 bit trải qua 16 vòng như quá trình mã hoá tuy nhiên có sự thay đổi nhỏ: „ Đầu vào là bản mã, đầu ra là bản rõ „ Các khoá được sinh ra ngược với quá trình mã hoá, tức là sử dụng lần lượt K16, K15,…, K2, K1. Do ở vòng 16, trước khi khối qua hộp IP-1 L16, R16 được hoán đổi nên ở vòng 1 của quá trình giải mã ta cũng phải đổi chỗ hai nửa sau khi khối 64 bit được qua hộp IP, Sau đây là một ví dụ về phép mã DES. Giả sử ta mã bản rõ (ở dạng mã hexa - hệ đếm 16): 0123456789ABCDEF „ Bằng cách dùng khoá 123457799BBCDFF1 „ Khoá ở dạng nhị phân ( không chứa các bít kiểm tra) là 0001001001101001010110111100100110110111101101111 1111000 „ Sử dụng IP, ta thu được L0 và R0 (ở dạng nhị phân) như sau: L0 = 1100110000000000110010011111111 L1 =R0 = 11110000101010101111000010101010 Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 267 „ Truyền và bảo mật thông tin 268 67 Một ví dụ về DES Một ví dụ về DES … E(R0) = 011110100001010101010101011110100001010101010101 K1 = 000110110000001011101111111111000111000001110010 E(R0) ⊕ K1 = 011000010001011110111010100001100110010100100111 S-box outputs = 01011100100000101011010110010111 f(R0,K1) = 00100011010010101010100110111011 L2 = R1 = 11101111010010100110010101000100 E(R1) = K2 = E(R1) ⊕K2 = S-box outputs = f(R1,K2) = L3 = R2 = E(R15) = 001000000110101000000100000110100100000110101000 K16 = 110010110011110110001011000011100001011111110101 E(R15) ⊕ K16 = 111010110101011110001111000101000101011001011101 S-box outputs 10100111100000110010010000101001 f(R15,K16) = 11001000110000000100111110011000 R16 = 00001010010011001101100110010101 011101011110101001010100001100001010101000001001 011110011010111011011001110110111100100111100101 000011000100010010001101111010110110001111101100 11111000110100000011101010101110 00111100101010111000011110100011 11001100000000010111011100001001 Truyền và bảo mật thông tin „ 269 Tranh luận về DES „ „ „ Các hộp S - chứa đựng thành phần phi tuyến của hệ mật là yếu tố quan trong nhất đối với độ mật của hệ thống. Tuy nhiên tiêu chuẩn xây dựng các hộp S không được biết đầy đủ. Một số người đã gợi ý là các hộp S phải chứa các "cửa sập" được dấu kín, cho phép Cục An ninh Quốc gia Mỹ (NSA) giải mã được các thông báo nhưng vẫn giữ được mức độ an toàn của DES. Dĩ nhiên ta không thể bác bỏ được khẳng định này, tuy nhiên không có một chứng cớ nào được đưa ra để chứng tỏ rằng trong thực tế có các cửa sập như vậy. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 270 Tranh luận về DES Khi DES được đề xuất như một chuẩn mật mã, đã có rất nhiều ý kiến phê phán. Một lý do phản đối DES có liên quan đến các hộp S. „ Cuối cùng áp dụng IP-1 vào L16,R16 ta nhận được bản mã hexa là: 85E813540F0AB405 271 „ „ Phản đối xác đáng nhất về DES chính là kích thước của không gian khoá: 256 là quá nhỏ để đảm bảo an toàn thực sự. Nhiều thiết bi chuyên dụng đã được đề xuất nhằm phục vụ cho việc tấn công với bản rõ đã biết. Phép tấn công này chủ yếu thực hiện tìm khoá theo phương pháp vét cạn. 1977, Diffie và Hellman đã gợi ý rằng có thể xây dựng một chíp VLSI (mạch tích hợp mật độ lớn) có khả năng kiểm tra được 106khoá/giây. Ætìm toàn bộ khóa trong khoảng 1 ngày. Ước tính chi phí để tạo một máy như vậy khoảng 2.107$. Truyền và bảo mật thông tin 272 68 Tranh luận về DES „ DES trong thực tế 1993, Michael Wiener đã đưa ra một thiết kế rất cụ thể về máy tìm khoá. Máy này xây dựng trên một chíp tìm khoá, có khả năng thực hiện đồng thời 16 phép mã và tốc độ tới 5×107 khoá/giây. Giá của một khung máy vào khoảng 100.000$ và nó có khả năng tìm ra một khoá của DES trong khoảng 1,5 ngày. Một thiết bị dùng 10 khung máy như vậy có giá chừng 106 $ sẽ giảm thời gian tìm kiếm khoá trung bình xuống còn 3,5 giờ. Hiện nay, người ta rút ngắn thời gian tìm khóa còn khoảng hơn 2h. Truyền và bảo mật thông tin „ 273 Truyền và bảo mật thông tin DES trong thực tế „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 274 Double DES và Triple DES Tới năm 1991 đã có 45 ứng dụng phần cứng và chương trình cơ sở của DES được Uỷ ban tiêu Chuẩn quốc gia Mỹ (NBS) chấp thuận. Một ứng dụng quan trọng của DES là trong giao dịch ngân hàng Mỹ - (ABA) DES được dùng để mã hoá các số định danh cá nhân (PIN) và việc chuyển tài khoản bằng máy thủ quỹ tự động (ATM). DES cũng được Hệ thống chi trả giữa các nhà băng của Ngân hàng hối đoái (CHIPS) dùng để xác thực các giao dụch vào khoản trên 1,5×1012 USA/tuần. DES còn được sử dụng rộng rãi trong các tổ chức chính phủ. Chẳng hạn như bộ năng lượng, Bộ Tư pháp và Hệ thống dự trữ liên bang. Truyền và bảo mật thông tin Có thể thực hiện DES rất hữu hiệu bằng cả phần cứng lẫn phần mềm. Các ứng dụng phần cứng hiện thời có thể đạt được tốc độ mã hoá cực nhanh. Công ty Digital Equipment đã thông báo tại hội nghị CRUPTO'92 rằng họ sẽ chế tạo một chíp có 50 ngàn tranzistor có thể mã hoá với tốc độ 1 Gbít/s bằng cách dùng nhịp có tốc độ 250MHz. Giá của chíp này vào khoảng 300$. „ 275 „ DES bội hai Mã hóa: C = DESK2[DESK1(M)] „ Giải mã: M = DESK1-1[DESK2-1(C)] 56 sự lựa chọn cho ¾ Có 2 khóa K1 và 256 sự lựa chọn cho khóa K2. Bởi vậy có 2112 sự lựa chọn cho cặp khóa (K1, K2) „ Truyền và bảo mật thông tin 276 69 II.2.2. Các chuẩn mã dữ liệu nâng cao (AES) Double DES và Triple DES „ „ DES bội ba „ Mã hóa: „ Giải mã: { „ ]} [ „ C = DES K 1 DES K 2 DES K 1 (M ) { −1 [ ]} M = DES−K11 DESK 2 DES−K11 (C ) ¾ „ Với TDES việc tìm khóa vét cạn yêu cầu khoảng: 2112 = 5,1923.1023 phép tính TDES, bởi vậy thực tế khó có thể thám mã thành công. Truyền và bảo mật thông tin „ „ „ „ „ „ Truyền và bảo mật thông tin „ Tính an toàn, phụ thuộc vào: „ „ chống lại các tấn công đã biết tốc độ nhanh và nén mã trên nhiều CPU Đơn giản trong thiết kế „ Không gian khóa phải đủ lớn để xác suất thành công khi tìm kiếm ngẫu nhiên là rất nhỏ Với các phép trộn thích hợp các hệ mã đối xứng có thể ra một hệ mã mới có tính an toàn cao Vấn đề bảo mật khi truyền khóa cần được xử lý nghiêm túc: „ „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 278 Thảo luận chung về hệ mật mã đối xứng Có 128/192/256 bit khoá và 128 bit khối dữ liệu. Thiết kế để: „ Là mã khối đối xứng khoá riêng. Kích thước khối dữ liệu 128 bit và độ dài khoá là tùy biến: 128, 192 hoặc 256 bit. Chuẩn mã mới phải mạnh và nhanh hơn Triple DES. Mã mới có cơ sở lí thuyết mạnh để thời gian sống của chuẩn khoảng 20-30 năm (cộng thêm thời gian lưu trữ). Khi đưa ra thành chuẩn yêu cầu cung cấp chi tiết thiết kế và đặc tả đầy đủ. Đảm bảo rằng chuẩn mã mới cài đặt hiệu quả trên cả C và Java. 277 Chuẩn mã nâng cao AES – Rijndael: có các đặc trưng sau: „ Rõ ràng cần phải thay thế DES, vì có những tấn công về mặt lý thuyết có thể bẻ được nó. Do đó Viện chuẩn quốc gia Hoa kỳ US NIST ra lời kêu gọi tìm kiếm chuẩn mã mới vào năm 1997. Sau đó có 15 đề cử được chấp nhận vào tháng 6 năm 1998. Và được rút gọn còn 5 ứng cử viên vào tháng 6 năm 1999. Đến tháng 10 năm 2000, mã Rijndael được chọn làm chuẩn mã nâng cao và được xuất bản là chuẩn FIPS PUB 197 vào 11/2001. Yêu cầu của AES „ Các chuẩn mã dữ liệu nâng cao „ Nguồn gốc AES (Advanced Encryption Standards) : 279 Sử dụng kênh an toàn Sử dụng nghi thức Truyền và bảo mật thông tin 280 70 Thảo luận chung về hệ mật mã đối xứng „ Thảo luận chung về hệ mật mã đối xứng Ví dụ, với các hệ mã giao hoán, có thể sử dụng nghi thức sau, giả sử A cần truyền thồn diệp w cho B, mỗi bên sử dụng hệ mã riêng: „ „ „ „ „ „ A gửi eA(w) cho B B gửi eB(eA(w)) cho A A gửi dA(eB(eA(w))=dA(eA(eB(w))= eB(w) cho B B giải mã dB(eBw) = w „ „ „ A eB eA Thám mã: Phương pháp thám mã tùy thuộc vào từng hệ mã. Có thể kết hợp các đặc trưng thống kê và bản rõ Về nguyên tắc, có thể bẻ khóa các hệ mã đối xứng với thời gian và phương pháp thích hợp Cài đặt: hầu hết có thể cài đặt tương đối dễ với tốc độ thực thi cao B Truyền và bảo mật thông tin 281 II.1. Tổng quan về các hệ mã khóa công khai II.2. Hệ mật Merkle – Hellman II.3. Hệ mật RSA II.4. Tổng kết Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 282 II.1. Tổng quan về các hệ mã khóa công khai Chương III. Hệ mã khóa công khai Truyền và bảo mật thông tin Truyền và bảo mật thông tin „ „ 283 Hệ thống bảo mật đối xứng: dễ dàng xác định một khóa khi biết khóa kiaÆ không đảm bảo bảo mật nếu xác suất khóa gửi bị lộ cao. Ý tưởng hệ mật mã công khai thuộc về Diffie và Hellman(1975): Việc biết ek không làm lộ dk: người thám mã biết ek (về nguyên tắc có thể biết hàm ngược của ek – tức là dk), tuy nhiên việc tính dk là bất trị, ít ra là đối với hầu hết các khóa. Hàm ek như trên gọi là hàm một phía Truyền và bảo mật thông tin 284 71 II.1. Tổng quan về các hệ mã khóa công khai II.1. Tổng quan về các hệ mã khóa công khai Mô hình hệ mật mã công khai Các điều kiện cho hệ bảo mật không đối xứng: p E c p D Khóa công khai kp Khóa bí mật ks Bộ sinh khóa Truyền và bảo mật thông tin 285 Truyền và bảo mật thông tin 286 II.1. Hệ mật Merkle – Hellman Các điều kiện cho hệ bảo mật không đối xứng: 4. Nếu biết khóa công khai kp , muốn tìm ra khóa bí mật ks hay “điều kiện ban đầu” thì gặp vấn đề khó không thực hiện được 5. Nếu biết kp và bản mã c cũng khó có thể tính ra bản rõ p Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 2. 3. II.1. Tổng quan về các hệ mã khóa công khai Truyền và bảo mật thông tin Từ điều kiện ban đầu, việc tính Kp và Ks, là (tại máy nhận B) dễ dàng (khoảng thời gian đa thức) Người gửi A, với khóa công khai Kp và bản thông báo p, có thể dễ dàng tính bản mã: c=Ekp(p) Máy nhận B sử dụng bảng mã c và khóa ks có thể tái tạo bản thông báo: p=Dks(c) cũng với thời gian đa thức 1. Kênh không an toàn 287 „ Bài toán xếp ba lô (Knapsack): „ „ Cho trước các tập các giá trị a1, …, an với ai >0 (các vật cần gói), và tổng đích T (khả năng chứa của ba lô). Liệu có tồn tại một vector “lựa chọn” V = [v1, …, vn], với vi ∈ {0, 1}, trong đó: „ „ vi = 1 ⇔ ai được chọn cho tổng (hay vật được chọn xếp vào ba lô) vi = 0 ⇔ ai không được chọn cho tổng (hay vật không được chọn xếp vào ba lô) sao cho: n ∑ (a i =1 i ∗ vi ) = T Truyền và bảo mật thông tin 288 72 II.2. Hệ mật Merkle – Hellman „ II.2. Hệ mật Merkle – Hellman Giới thiệu về các ba lô của Merkle – Hellman „ Ý tưởng chính đằng sau sơ đồ ba lô Merkle – Hellman là để mã một thông báo nhị phân như một lời giải cho bài toán ba lô „ Chi tiết về phương pháp Merkle – Hellman „ Bài toán ba lô tổng quát: „ „ „ Ba lô được biểu diễn như một vecto các số hạng nguyên, trong đó thứ tự của các số hạng là rất quan trọng. Thực sự có 2 ba lô, một “ba lô dễ” và một “ba lô khó” Truyền và bảo mật thông tin 289 II.2. Hệ mật Merkle – Hellman „ „ „ Truyền và bảo mật thông tin „ Loại 73; Thử 17, tổng mới (53 – 17) = 36. Loại 38, nhưng 4+11+1<36. Kết luận 17 không là số hạng trong lời giải Thử 38, tổng mới (53 – 38) = 15. Thấy tổng các số hạng còn lại là 4+11=15. Vậy lời giải là 38 + 4 + 11. „ „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 290 II.2. Hệ mật Merkle – Hellman Ví dụ: T = 53, dãy số nguyên (17, 38, 73, 4, 11, 1) „ Cho tập giá trị a1, a2, …, an và một tổng T. Tính giá trị vi để cho: T = v1a1 + v2a2 + … + vnan với vi ∈ {0,1} 291 Lời giải của bài toán được tiến hành theo thứ tự, ta xét mỗi số nguyên có thể góp phần vào tổng và đã rút gọn bài toán tương ứng. Khi một lời giải không đưa ra tổng mong muốn, ta quay lại, loại bỏ các phỏng đoán gần và thử lần lượt. Với dãy nhiều số nguyên, rất khó tìm lời giải, đặc biệt khi tất cả chúng đều lớn như nhau đến mức ta không thể loại trực tiếp được số nào. Truyền và bảo mật thông tin 292 73 II.2. Hệ mật Merkle – Hellman „ II.2. Hệ mật Merkle – Hellman Các ba lô siêu tăng: „ Giả sử bài toán có thêm một hạn chế phụ: Các số nguyên của S phải lập thành một dãy siêu tăng, nghĩa là một số nguyên phải lớn hơn tổng của tất cả các số đứng trước nó. Khi đó mỗi số nguyên ak sẽ có dạng: ak > „ „ k −1 ∑ j =1 a j Ví dụ: {1, 4, 11, 17, 38, 73} là một dãy siêu tăng Truyền và bảo mật thông tin 293 II.2. Hệ mật Merkle – Hellman „ „ Nếu ta hạn chế bài toán ba lô thành các dãy siêu tăng, ta có thể dễ dàng nói một số hạng có trong tổng không. Nếu tổng nằm giữa ak và ak+1 thì nó phải bao hàm ak như một số hạng. Ngược lại nếu tổng nhỏ hơn ak thì nó không thể bao hàm ak như một số hạng. Truyền và bảo mật thông tin II.2. Hệ mật Merkle – Hellman Ví dụ: cho dãy {1, 4, 11, 17, 38, 73}. Giải bài toán với các tổng đích T = 96, T = 95 „ Kĩ thuật mã hóa: „ Các nguyên tắc của số học modulo: „ „ „ Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 294 295 Trong số học thông thường, việc cộng hay nhân một dãy siêu tăng vẫn duy trì bản chất siêu tăng của nó, nên kết quả vẫn là một dãy siêu tăng. Trong số học modulo n, tính chất siêu tăng của một dãy có thể bị phá. Với những kết quả rút ra từ số học modulo. Diffie Hellman đã tìm ra cách phá bản chất siêu tăng của dãy số nguyên, bằng cách nhân tất cả các số nguyên với một hằng số w và lấy kết quả mod n, trong đó gcd(n, w) = 1. Truyền và bảo mật thông tin 296 74 II.2. Hệ mật Merkle – Hellman „ II.2. Hệ mật Merkle – Hellman Biến đổi một ba lô siêu tăng: „ „ „ Để thực hiện thuật toán mã hóa Merkle – Hellman, ta cần một ba lô siêu tăng mà có thể biến đổi thành một ba lô khó. Cách làm như sau: „ „ „ „ • Dãy siêu tăng vừa được chọn được gọi là “ba lô dễ”. „ „ „ „ Với ba lô siêu tăng [1, 2, 4, 9], W = 15, M =17. Ta thu được dãy [15, 13, 9, 16] Khi đó: „ Khóa công khai là tập các số [a1, a2, …, an] Khóa bí mật là (π, M, W,(M1, …, Mn)) Ta sẽ dùng cả hai ba lô khó và dễ trong phép mã hóa. 298 Truyền và bảo mật thông tin II.2. Hệ mật Merkle – Hellman Mã hóa: „ Ví dụ: 297 Thuật toán mã công khai Merkle – Hellman: „ „ „ II.2. Hệ mật Merkle – Hellman „ Sau khi chọn một ba lô dễ là dãy siêu tăng [M1, M2, …, Mn] và một modulo M: M > 2* Mn Chọn một số nhân W (1 ≤ W ≤ M – 1) sao cho UCLN(W, M) = 1. Chọn một phép hoán vị ngẫu nhiên π của các số nguyên {1, 2, …, n} Tính các giá trị ai = W*Mπ(i) mod M, với i = 1, 2, …, n. Khi đó [a1, a2, …, an] là một “ba lô khó” „ •Thể hiện bất kì của bài toán ba lô được lập từ ba lô đó có một lời giải rất dễ tìm! „ „ Chọn số nguyên ban đầu.Chọn số nguyên thứ 2 lớn hơn số nguyên ban đầu.Chọn số nguyên thứ 3 lớn hơn tổng của 2 số đầu. Tiếp tục quá trình này bằng cách chọn các số nguyên mới lớn hơn tổng của tất cả các số nguyên đã chọn. Truyền và bảo mật thông tin Thuật toán tạo khóa: „ Giải mã: „ Nhận khóa công khai của bên nhận A là [a1, …,an] Biểu thị bản tin m như một chuỗi nhị phân có độ dài n. Nghĩa là ta chia thông báo m thành các khối n bit. Tính số nguyên c = m1a1 + … + mnan Gửi bản mã c cho bên nhận A. „ Tính d = W-1c mod M Sử dụng thuật giải xếp ba lô trong trường hợp dãy siêu tăng để tìm các số nguyên r1, r2, …, rn, ri ∈ {0, 1} sao cho: d = r1M1 + r2M2 + … + rnMn „ „ Các bit của bản rõ là mi = rπ(i), với i = 1, 2, …, n Chứng minh? e.d=1+k.Ф(N) đối với một giá trị k nào đó. „ Nếu UCLN(M,p) =1 ta có: Med-1 =1(mod p) => Med = M (mod p) , nếu UCLN(M,p) =p ta cũng có Med = M (mod p) =0 (mod p) Tương tự: Med = M (mod q) Vì p, q là SNT nên Med = M (mod pq)= M (mod N) =M =>Cd mod N =M Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Lưu ý rằng bản tin M < N, do đó khi cần chia khối bản rõ. Truyền và bảo mật thông tin „ ap-1 mod p = 1 với p là SNT, UCLN(a,p)=1 „ Sử dụng khóa riêng KR={d} Tính M=Cd mod N 314 Chú ý (Số mũ vạn năng). Theo Định lý Ferma „ Lấy khoá công khai của người nhận KU={e,N} Tính C=Me mod N, trong đó 0≤M1 thì a-1 (mod N) không tồn tại. Ngược lại return(x). Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 319 Truyền và bảo mật thông tin 320 80 II.3.6. Một số thuật toán ứng dụng trong RSA „ Thuật toán nhân và bình phương có lặp để lấy luỹ thừa trong ZN. Thuật toán nhân và bình phương có lặp để lấy luỹ thừa trong ZN. Truyền và bảo mật thông tin 321 II.3.6. Một số thuật toán ứng dụng trong RSA „ „ Giả sử cần phải tìm một số nguyên tố rất lớn. Lấy ngẫu nhiên một số đủ lớn, ta cần phải kiểm tra xem số đó có phải là số nguyên tố không? „ „ „ „ Mà mọi số nguyên tố phải thỏa mãn Nhưng có một số số không nguyên tố, gọi là giả nguyên tố cũng thoả mãn tính chất đó Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Cụ thể là phép kiểm tra dựa trên Định lý Ferma như sau: „ Cách 1: Thử bằng phép chia Cách 2: sử dụng các phép kiểm tra tính nguyên tố thống kê dựa trên các tính chất: „ 322 II.3.6. Một số thuật toán ứng dụng trong RSA Kiểm tra tính nguyên tố „ Truyền và bảo mật thông tin 323 Nếu số n cần kiểm tra tính nguyên tố là số nguyên tố, thì nó sẽ thoã mãn định lý Ferma đối với mọi số a nhỏ hơn nó an-1 mod n = 1. Như vậy, lấy ngẫu nhiên số a và kiểm tra xem nó có tính chất trên không. Nếu có thì n có thể là số nguyên tố, nếu cần độ tin cậy lớn hơn, thì ta kiểm tra liên tiếp nhiều lần như vậy với các số ngẫu nhiên a được chọn. Sau mỗi lần qua được phép thử, xác suất để n là số nguyên tố lại tăng lên Truyền và bảo mật thông tin 324 81 II.3.7. Một số thuật toán ứng dụng trong RSA „ II.3.6. Một số thuật toán ứng dụng trong RSA Chú ý rằng: „ „ „ nếu bi mod n = 1, thì: b2i mod n = (1)2 mod n = 1 và nếu bi mod n = n – 1, thì: b2i mod n = (n - 1)2 mod n = (n2 – 2n +1) mod n=1 Truyền và bảo mật thông tin „ 325 II.3.6. Một số thuật toán ứng dụng trong RSA „ „ TEST (n) is: 1. Tìm các số nguyên k, q, k > 0, q lẻ, và (n–1)= 2k.q 2. Chọn ngẫu nhiên số nguyên a, 1 0.99999. Truyền và bảo mật thông tin 328 82 II.3.6. Một số thuật toán ứng dụng trong RSA „ II.3.6. Một số thuật toán ứng dụng trong RSA Định lí phần dư Trung Hoa Nếu n1, …, nk nguyên tố cùng nhau từng đôi một thì x ≡ a 1 (mod n 1 ) hệ sau: x ≡ a 2 (mod n 2 ) .......... x ≡ a .......... k (mod .... n k „ Có thể triển khai Định lý Trung Hoa theo một số cách như sau: „ 1. Tính toán theo modulo số lớn: „ ) Để tính A mod M, với M (M= m1m2..mk) khá lớn và A là biểu thức số học nào đó. Trước hết ta cần tính tất cả ai = A mod mi. Sau đó sử dụng công thức: Có nghiệm duy nhất theo modulo N = n1…nk: k x = ∑ ( N / ni ) yi xi (mod N ) „ Với yi=(N/ni)-1 (mod ni) ( i =1 Truyền và bảo mật thông tin „ 329 „ „ „ „ 330 Mã hiệu quả: „ „ Vậy 178 mod 77 = (2*22 + 4*56) mod 77 = 268 mod 77 = 37 mod 77 = A = 37; Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin „ 11-1 mod 7 = 4-1 mod 7 = 2, suy ra c1 = 11*2 = 22; 7-1 mod 11 = 8, suy ra c2 = 7*8 = 56; 178 mod 7 = (17 mod 7)8 mod 7 = 38 mod 7 = (32)4 mod 7 = a1 = 2; 178 mod 11 = (17 mod 11)8 mod 11 = 68 mod 11 = (62)4 mod 11 = 34 mod 11 = a2 = 4; Truyền và bảo mật thông tin 1≤ i ≤ k II.3.7. Hiệu quả và an toàn Ví dụ 178 mod 77=? Áp dụng định lý phần dư Trung hoa, ta coi A = 1718, m1 = 7, m2 = 11. Khi đó M1 = 11, M2 = 7 và „ ) c i = M i × M i−1 mod m i ; II.3.6. Một số thuật toán ứng dụng trong RSA „ ⎛ k ⎞ A = ⎜ ∑ a i c i ⎟ mod M ⎝ i =1 ⎠ Trong đó: Mi = M/mi 331 Mã sử dụng lũy thừa của khoá công khai e, nếu giá trị của e nhỏ thì tính toán sẽ nhanh, nhưng dễ bị tấn công. Thường chọn e nhỏ hơn hoặc bằng 65537 (216-1), tức là độ dài khoá công khai là 16 bit. Chẳng hạn trong ví dụ trên ta có thể lựa chọn e = 23 hoặc e = 7. Ta có thể tính mã hoá nhanh, nếu biết n=pq và sử dụng Định lý phần dư Trung Hoa với mẩu tin M theo các Modulo p và q khác nhau. Nếu khoá công khai e cố định thì cần tin tưởng rằng khi chọn n ta luôn có gcd(e,Ф(n)) = 1. Loại bỏ mọi p, q mà làm cho Ф(n) không nguyên tố cùng nhau với e. Truyền và bảo mật thông tin 332 83 II.3.7. Hiệu quả và an toàn „ II.3.7. Hiệu quả và an toàn Giải mã hiệu quả: „ „ „ Có thể sử dụng Định lý phần dư Trung Hoa để tính theo mod p và q, sau đó kết hợp lại để tìm ra bản rõ. Vì ở đây người sử dụng khoá riêng biết được p và q, do đó có thể sử dụng kỹ thuật này. Nếu sử dụng định lý phần dư Trung Hoa để giải mã thì hiệu quả là nhanh gấp 4 lần so với giải mã tính trực tiếp. Truyền và bảo mật thông tin „ „ „ „ Tìm kiếm khoá bằng phương pháp vét cạn, phương pháp này không khả thi với kích thước đủ lớn của các số Tấn công bằng toán học dựa vào độ khó việc tính Ф(n) bằng cách phân tích n thành hai số nguyên tố p và q hoặc tìm cách tính trực tiếp Ф(n). Trong quá trình nghiên cứu việc thám mã người ta đề xuất kiểu tấn công thời gian trong khi giải mã, tức là căn cứ vào tốc độ mã hoá và giải mã các mẩu tin cho trước mà phán đoán các thông tin về khoá. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin „ Trên thực tế có nhiều cách tấn công khác nhau đối với mã công khai RSA như sau: „ „ Người sử dụng RSA cần phải xác định ngẫu nhiên 2 số nguyên tố rất lớn p, q thông thường khoảng 512 bit. Sau khi chọn được một khoá e hoặc d nguyên tố cùng nhau với Ф(n), dễ dàng tính được khoá kia chính là số nghịch đảo của nó qua thuật toán Euclide mở rộng. 334 II.2.8. Điểm bất động An toàn của RSA „ „ 333 II.3.7. Hiệu quả và an toàn Sinh khoá RSA 335 „ „ Giả sử rằng cặp khóa công khai là .(e,n)=(17,35) Giả sử thông báo có giá trị M= 8. Ta có C=.817 mod 35= 8 Như vậy mã hóa của thông báo vẫn là thông báo ban đầu. Nói một cách khác với khóa mã là 17 thì thông tin không được che dấu. Rõ ràng là phải tránh được tình trạng này định lý sau cho ta tính được số bản tin không thể che dấu được với một lựa chọn cho trước của . Truyền và bảo mật thông tin 336 84 II.3.8. Điểm bất động Bài tập hệ mật RSA Định lí: Nếu các thông báo được mã bằng hệ mật RSA với cặp khóa công khai (e,N) với N = p.q thì số các thông báo không thể che dấu được là σM=(1+UCLN(e-1, p-1))(1+UCLN(e-1, q-1) VD: p=5, q=7, e=2 -> σM =4 Các thông báo không bị che dấu là {0,1,15,21} Truyền và bảo mật thông tin „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế „ Cho p = 17, q = 19 „ „ „ Tính n? Cho e = 23, tìm d? Hãy mã hóa và giải mã cho các số 68, 12 Truyền và bảo mật thông tin 338 II.4. Hệ mật ElGamal Định nghĩa: cho a ∈ZN, bậc t của a (ký hiệu là ord(a)) là số nguyên dương nhỏ nhật sao cho at=1 (mod N) Nếu a ∈ZN* và có bậc φ(N) thì ta gọi a là phần tử sinh hay phần tử nguyên thủy của tập ZN. Theo định lý Euler, nếu a ∈ZN* thì aφ(N)=1 (mod N), => t là ước số của φ(N) Truyền và bảo mật thông tin Bài tập áp dụng: 337 II.4. Hệ mật ElGamal „ „ „ Hệ mật ElGamal dựa vào bài toán logarit rời rạc „ Bài toán logarit rời rạc trên trường Zp: „ 339 I = (p, α, β), trong đó p là số nguyên tố, α ∈ Zp* là phần tử nguyên thủy, β ∈ Zp*, tìm số nguyên a duy nhất, 0 ≤ a ≤ p – 2 để αa ≡ β mod p, chúng ta kí hiệu số nguyên a là logαβ Truyền và bảo mật thông tin 340 85 II.4. Hệ mật ElGamal „ „ „ 3.5 Hệ mật ElGamal Để ngăn cản các tấn công đã biết thì số nguyên tố p phải là số có ít nhất 150 chữ số và p-1 chứa ít nhất một thừa số nguyên tố lớn. Thực tế, không có thuật toán thời gian đa thức có thể giải được bài toán này. Tính thiết thực của bài toán logarit rời rạc trong mật mã? „ „ „ „ „ „ „ „ „ „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 342 Thuật toán giải mã: để khôi phục bản rõ m từ c, A phải thực hiện các bước sau: Sử dụng khóa riêng a để tính γp-1-a mod p (chú ý γ p-1-a = γ -a γ p-1= γ -a = γ -ak) (Nhớ lại: ĐL Ferma: γ p-1 mod p=1 với p là SNT) -a „ Khôi phục bản rõ bằng cách tính (γ )δ mod p. „ Nhận khoá công khai (p, α, αa) của A. Biểu thị bản tin dưới dạng một số nguyên m trong dãy {0, 1, …, p – 1} Chọn số nguyên ngẫu nhiên k, 1 ≤ k ≤ p – 2 Tính γ = αk mod p và δ = m(αa)k mod p . Gửi bản mã c = (γ, δ) cho A. Truyền và bảo mật thông tin Truyền và bảo mật thông tin 3.5 Hệ mật ElGamal Thuật toán mã hoá: B mã hoá một thông tin báo m để gửi cho A bản mã cần gửi. B phải thực hiện các bước sau: „ Tạo 1 số nguyên tố p lớn và một phần tử sinh α của nhóm nhân Zp* của các số nguyên mod p. Chọn một số nguyên ngẫu nhiên a, 1 ≤ a ≤ p – 2 và tính αa mod p Khoá công khai là bộ 3 số (p, α, αa), khoá bí mật là a. 341 3.5 Hệ mật ElGamal „ Thuật toán tạo khoá: Tạo 1 khoá công khai và một khoá bí mật tương ứng : Là sự khó giải nhưng phép toán ngược của hàm mũ lại có thể tính hiệu quả nhờ phương pháp nhân bình phương có lặp (square-and-multiply method). Nói một cách khác, phép mũ mod p là hàm một chiều với các số nguyên tố p thích hợp. Truyền và bảo mật thông tin „ Hệ mật ElGamal „ Chứng minh? Thuật toán trên cho phép A thu được bản rõ vì: γ-aδ ≡ α-ak.mαak ≡ m mod p (δ = m(αa)k) „ 343 Truyền và bảo mật thông tin 344 86 3.5 Hệ mật ElGamal II.4. Tổng kết Ví dụ: cho p = 17 „ Xác định các phần tử nguyên thủy của Z*17 „ Giả sử Kỹ thuật cửa sập (Trap Door) để xây dụng hàm 1 phía trong các hệ mã khóa công khai : i. Xuất phát từ bài toán bất trị Q ii. Xét một bài toán con dễ Q1 của Q. iii. Xáo trộn Q1 sao cho bài toán thu được Q1’ có vẻ giống bài toán Q. Q1 như 1 khóa lập mã công khai iv. Giữ bí mật thông tin làm sao khôi phục Q1 từ Q1’. Thông tin này được xem là cửa sập. a „ Chọn a=3, α=2, α mod 17 = 8 ÆKhóa công khai (p, α, αa) = (17, 2, 8). Khóa bí mật a = 3 „ „ Tính bản mã với bản rõ m = 7, chọn ngẫu nhiên k = 4.: γ = αk mod p =16 δ = mαak mod p = 7*23*4 mod 17= 10 ÆBản mã c=(16,10) Giải mã: (γp-1-a)δ mod p=1617-1-3*10 mod 17 = 7 Truyền và bảo mật thông tin 345 II.4. Tổng kết „ „ Các thuật toán khoá công khai dùng 2 khoá với các đặc trưng sau: „ „ „ Không có khả năng tính toán để tìm khoá giải mã nếu chỉ biết thuật toán mã và khoá dùng để mã. Có thể dễ dàng mã hoá hoặc giải mã mẩu tin nếu biết khoá tương ứng Trong một số sơ đồ: một khoá bất kỳ trong hai khoá có thể dùng để mã, còn khoá kia dùng để giải mã. Chúng có vai trò đối ngược nhau. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 346 II.4. Tổng kết Các đặc trưng của khoá công khai „ Truyền và bảo mật thông tin „ 347 Mặc dù an toàn nhưng các hệ mã khóa công khai đòi hỏi tài nguyên lớn khi thực thi: thời gian và bộ nhớÆ Trong thực tế các hệ mã này thường chỉ được sử dụng trong những công đoạn quan trọng như: chứng thực, tạo chữ ký, cất giữ mật khẩu, mã hóa khóa … Với những ứng dụng cụ thể, đòi hỏi phải có các nghi thức và quy trình bảo mật thích hợp Truyền và bảo mật thông tin 348 87 II.4. Tổng kết „ „ II.4. Tổng kết Khoá công khai ra đời hỗ trợ thêm để giải quyết một số bài toán an toàn, chứ không phải thay thế khoá riêng. Cả hai khoá cùng tồn tại, phát triển và bổ sung cho nhau Khi cần gửi thông tin qua mạng, người ta thường mã hóa chúng bằng một thuật toán đối xứng. Khóa bí mật của hệ mã này được mã bằng một hệ mật mã khóa công khai để truyền qua cho người nhận Truyền và bảo mật thông tin 349 II.4. Tổng kết „ „ „ „ Người ta muốn giải quyết hai vấn đề sau về khoá nảy sinh trong thực tế: „ Nếu chỉ dùng khoá đối xứng, thì không có giải pháp cho hai bài toán trên. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 350 Ứng dụng khoá công khai „ Phân phối khoá - làm sao có thể phân phối khóa an toàn mà không cần trung tâm phân phối khoá tin cậy Chữ ký điện tử - làm sao có thể kiểm chứng được rằng mẩu tin gửi đến nguyên vẹn từ đúng người đứng tên gửi. Truyền và bảo mật thông tin Truyền và bảo mật thông tin II.4. Tổng kết Tại sao lại phải dùng mã khoá công khai? „ Ví dụ kết hợp 2 loại mật mã: „ Đối tượng cần truyền tin A gửi tín hiệu yêu cầu nhận tin tới đối tượng B „ Đối tượng B chấp nhận và gửi khoá công khai KPB cho đối tượng A „ Đối tượng A sinh ra khoá bí mật K, mã hoá thành EKpB(K), rồi gửi cho B „ Đối tượng B nhận EKPB (K), dùng KSBgiải mã lại thành K, và gửi sẵn sàng nhận tin cho A „ Đối tượng A chuẩn bị gói tin P, mã hoá thành K(P), rồi gửi cho B „ Đối tượng B nhận gói K(P), giải mã thành P, và lưu lại cho mình Có thể phân loại các ứng dụng của khoá công khai thành 3 loại khác nhau: „ „ „ 351 Mã/giải mã – cung cấp bảo mật. Đây là ứng dụng bảo mật truyền thống giống như ta vẫn thường dùng với khoá đối xứng. Chữ ký điện tử - cung cấp xác thực. Một trong các ứng dụng mới của khoá công khai mà khoá đối xứng không thể thực hiện được, đó là khoá công khai có đủ cơ sở để xác nhận người gửi và có thể là một lựa chọn để tạo chữ ký điện tử của người gửi. Một số thuật toán mã công khai phù hợp với mọi ứng dụng, còn một số khác chuyên dùng cho ứng dụng cụ thể. Truyền và bảo mật thông tin 352 88 Chương IV. Chữ ký điện tử và các hàm băm „ „ IV.1. Chữ ký điện tử IV.1. Chữ ký điện tử IV.2. Các hàm băm Truyền và bảo mật thông tin IV.1.1. Khái niệm về chữ ký điện tử IV.1.2. Sơ đồ chữ ký RSA IV.1.3. Sơ đồ chữ ký Elgamal IV.1.4. Chuẩn chữ kí số (DSS) 353 IV.1.1. Khái niệm về chữ ký điện tử „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 354 IV.1.1. Khái niệm về chữ ký điện tử Sơ đồ chữ ký điện tử (CKĐT) là phương pháp kí một bức điện lưu dưới dang điện tử. Chẳng hạn một bức điện có ký hiệu được truyền trên mạng máy tinh. Là một cơ chế xác thực hóa cho phép đính kèm một mã số vào thông điệp tương tự như là việc kí một chữ ký lên môt văn bản bình thường. Truyền và bảo mật thông tin Truyền và bảo mật thông tin 355 „ Khác biệt giữa CKĐT và chữ ký thường: Chữ ký thường Chữ ký điện tử Là một phần vật lý của tài liệu Không gắn theo kiểu vật lý, là sự mã hóa, “không nhìn thấy” Kiểm tra bằng cách so sánh Kiểm tra nhờ thuật toán xác thực nó với các chữ kí xác thực công khai, sơ đồ chữ ký an toàn khácÆ dễ giả mạo ngăn chặn được giả mạo Bản copy thường khác với bản gốc Bản copy đồng nhất với bản gốc Æ bị dùng lại Æ khắc phục bằng cách dán nhãn thời gian Truyền và bảo mật thông tin 356 89 IV.1.1. Khái niệm về chữ ký điện tử IV.1.1. Khái niệm về chữ ký điện tử Một sơ đồ chữ kí số thường chứa hai thành phần: Thuật toán kí và thuật toán xác minh. Chữ kí sig(x) nhận được có thể kiểm tra bằng thuật toán xác minh công khai ver. Định nghĩa „ Một sơ đồ chữ kí số là bộ 5( P,A, K,S,V) thoả mãn các điều kiện dưới đây: „ „ Truyền và bảo mật thông tin 1. 2. 3. 4. 357 „ „ „ sigk và verk là các hàm thời gian đa thức. Verk là hàm công khai sigk là mật. Không thể dể dàng tính toán để giả mạo chữ kí Một sơ đồ chữ kí không thể an toàn vô điều kiện có thể kiểm tra tất cả các chữ số y có thể có trên bức điện x nhờ dùng thuât toán ver công khai cho đến khi tìm thấy một chữ kí đúng. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 358 IV.1.2. Sơ đồ chữ ký RSA IV.1.1. Khái niệm về chữ ký điện tử „ P là tập hữu hạn các bức điện có thể. A là tập hữu hạn các chữ kí có thể. K không gian khoá là tập hữu hạn các khoá có thể. Với mỗi k thuộc K tồn tại một thuật toán kí sigk ∈ S và là một thuật toán xác minh verk∈ V. Mỗi sigk : P → A và verk: P×A →{true,false} là những hàm sao cho mỗi bức điện x∈ P và mối chữ kí y∈ A thoả mãn phương trình dưới đây: True nếu y=sigk(x) verk(x,y)= False nếu y ≠ sigk(x) „ „ 359 Độ an toàn rất cao, dựa vào ưu điểm của hệ mã RSA, Đảo ngược hàm mã và giải mã Truyền và bảo mật thông tin 360 90 IV.1.2. Sơ đồ chữ ký RSA IV.1.2. Sơ đồ chữ ký RSA Sơ đồ chữ ký RSA Cho n= pq, p và q là các số nguyên tố. Cho P =A= Zn và định nghĩa: K= {(n,p,q,a,b):n=pq,p và q là nguyên tố, ab ≡1(mod φ(n)) }. Các giá trị n và b là công khai, còn p, q, a là bí mật Ta định nghĩa : và „ „ „ sigk(x)= xa mod n verk(x,y)= true ⇔ x ≡yb (mod n) với x,y ∈Zn Truyền và bảo mật thông tin „ 361 IV.1.2. Sơ đồ chữ ký RSA Nếu đầu tiên A mã x rồi sau đó mới kí lên bản mã thì sao?. Tức là: „ A tính: z=eB(x) và y= sigA(z). „ A sẽ truyền cặp (z,y) tới B. „ B sẽ dùng verA xác minh chữ ký và dùng dB giải mã z, nhận x Æ Một vấn đề tiểm ẩn trong biện pháp này là nếu C nhận được cặp (z,y) có thể thay chữ kí y của A bằng chữ kí của mình: y’ = sigC(z)=sigC(eB(x)). Khi đó nếu C truyền(z, y’ ) đến B thì chữ kí C được B xác minh bằng verC và B có thể suy ra rằng, bản rõ x xuất phát từ C. „ Do khó khăn này, hầu hết người sử dụng được khuyến nghị nên kí trước khi mã. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế A tính y= sigA(x) và sau đó mã cả x và y bằng hàm mã khoá công khai eB của B, B nhận được z = eB(x,y), dùng hàm dB giải mã z để nhận được (x,y). Sau đó kiểm tra xem verA(x,y) có bằng True hay không. Truyền và bảo mật thông tin 362 IV.1.3. Sơ đồ chữ ký Elgamal „ Truyền và bảo mật thông tin Chữ ký thường dùng kết hợp với hàm mã hóa công khai: Giả sử rằng, A muốn gửi thông điệp đã mã hóa và ký đến B: 363 „ „ Sơ đồ chữ kí Elgamal đã từng dưới thiệu trong bài báo năm 1985. Bản cả tiến của sơ đồ này đã được Viện Tiêu chuẩn và Công Nghệ Quốc Gia Mỹ (NIST) chấp nhận làm chữ kí số. Sơ đồ Elgamal (E.) được thiết kế với mục đích dành riêng cho chữ kí số, khác sơ đồ RSA dùng cho cả hệ thống mã khoá công khai lẫn chữ kí số. Đối với sơ đồ E, có nhiều chữ kí hợp lệ trên bức điện cho trươc bất kỳ. Thuật toán xác minh phải cố khả năng chấp nhận bất kì chữ kí hợp lệ khi xác thực. Truyền và bảo mật thông tin 364 91 IV.1.3. Sơ đồ chữ ký Elgamal „ „ „ IV.1.3. Sơ đồ chữ ký Elgamal Định nghĩa: cho a ∈ZN, bậc t của a (ký hiệu là ord(a)) là số nguyên dương nhỏ nhật sao cho at=1 (mod N) Nếu a ∈ZN* và có bậc φ(N) thì ta gọi a là phần tử sinh hay phần tử nguyên thủy của tập ZN. Theo định lý Euler, nếu a ∈ZN* thì aφ(N)=1 (mod N), => t là ước số của φ(N) Truyền và bảo mật thông tin Sơ đồ chữ ký Elgamal: Cho p là số nguyên tố sao cho bài toán logarit rời rạc trên Zp là khó và giả sử α ∈ Zn là phần tử nguyên thủy, P = Zp* , A = Zp* × Zp-1 và định nghĩa : K ={(p,α ,a,β ): β ≡ αa (mod p)}. Giá trị p,α ,β là công khai, còn a là mật. „ Với K = (p,α ,a,β ) và một số ngẫu nhiên (bí mật) k∈ Zp-1. và định nghĩa : Sigk(x,y) =(γ ,δ), trong đó γ = αk mod p và δ =(x-aγ) k-1 mod (p-1). * „ Với x,γ ∈ Zp và δ ∈ Zp-1 , ta định nghĩa : Ver(x,γ ,δ ) = True ⇔ βγ γδ ≡ αx (mod p). 365 IV.1.3. Sơ đồ chữ ký Elgamal „ „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 366 IV.1.3. Sơ đồ chữ ký Elgamal Nếu chữ kí được thiết lập đúng khi xác minh sẽ thành công vì : βγ γδ ≡ αaγ αk δ (mod p)= α aγ +k δ (mod p) Mặt khác ta có: a γ+ k δ = a γ+ (k(x-aγ) k-1 mod (p-1)) = a γ + (x - a γ) mod (p-1) = a γ + x mod (p-1) - a γ mod (p-1) = x (mod p-1) => a γ+ k δ =t(p-1)+x (với t là một số nguyên nào đó) => α aγ +k δ (mod p) = α t(p-1) α x (mod p) = α x (mod p) (Do αp-1 mod p=1 khi p là SNT - Định lý Ferma) Vì vậy: βγ γδ = α aγ +k δ (mod p) ≡ αx(mod p) Truyền và bảo mật thông tin Truyền và bảo mật thông tin 367 Ví dụ „ Giả sử cho p = 467, α =2,a = 127; khi đó: β = αa mod p = 2127 mod 467=132 „ Bức điện x = 100, chọn số ngẫu nhiên k =213 (chú ý là UCLN(213,466) =1 và 213-1 mod 466 = 431. Khi đó γ =2213 mod 467 = 29 và δ =(100-127 × 29) 431 mod 466 = 51. „ Bất kỳ ai cũng có thể xác minh chữ kí bằng các kiểm tra : 13229 2951 ≡ 189 (mod 467) và 2100 ≡ 189 (mod 467) „ Vì thế chữ kí là hợp lệ. Truyền và bảo mật thông tin 368 92 IV.1.3. Sơ đồ chữ ký Elgamal „ IV.1.3. Sơ đồ chữ ký Elgamal Xét độ mật của sơ đồ chữ kí E. Giả sử, C thử giả mạo chữ kí trên bức điện x cho trước không biết a. Nếu C chọn γ và sau đó thử tìm giá trị δ tương ứng, anh ta phải tính logarithm rời rạc logγ αxβ-γ. Mặt khác, nếu đầu tiên ta chọn δ và sau đó thử tìm γ và thử giải phương trình: βγ γδ ≡ αx(mod p). để tìm γ. Đây là bài toán chưa có lời giải nào: Tuy nhiên, dường như nó chưa được gắn với đến bài toán đã nghiên cứu kĩ nào nên vẫn có khả năng có cách nào đó để tính δ và γ đồng thời để (δ, γ) là một chữ kí. Hiện thời không ai tìm được cách giải song củng ai không khẳng định được rằng nó không thể giải được. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Tuy nhiên, có một cách để C có thể kí lên bức điện ngẫu nhiên bằng việc chọn γ, δ và x đồng thời: giả thiết i và j là các số nguyên 0 ≤ i ≤ p-2, 0 ≤ j ≤ p-2 và UCLN(j,p-2) = 1. Khi đó C thực hiện các tính toán sau: γ = αi βj mod p δ = -γ j-1 mod (p-1) x = -γ i j-1 mod (p-1) trong đó j-1 được tính theo modulo (p-1) (ở đây đòi hỏi j nguyên tố cùng nhau với p-1). Truyền và bảo mật thông tin 370 IV.1.3. Sơ đồ chữ ký Elgamal Xem (δ, γ) là giá trị chữ ký cho bức điện x. Việc xác minh sẽ hợp lệ: Truyền và bảo mật thông tin „ 369 IV.1.3. Sơ đồ chữ ký Elgamal „ „ 371 „ Vấn đề khác: có thể giả mạo chữ ký bằng cách sử dụng chữ ký trước đó ký cho nhiều bức khác: Nếu có cặp (δ, γ) và x, lấy h, i và j là các số nguyên, trong đó 0≤ i, j, h ≤ p-2 và UCLN (h γ - j δ, p-1) = 1. Tính: „ Cặp (λ, μ) là chữ ký cho bức điện x’ „ Truyền và bảo mật thông tin 372 93 IV.1.4. Chuẩn chữ kí số (DSS) „ IV.1.4. Chuẩn chữ kí số Chuẩn chữ kí số(Digital Signature StandardDSS) là phiên bản cải tiến của sơ đồ chữ kí Elgamal. Nó được công bố trong Hồ Sơ trong liên bang vào ngày 19/5/94 và được làm chuẩn voà 1/12/94 tuy đã được đề xuất từ 8/91. „ „ „ „ Truyền và bảo mật thông tin 373 IV.1.4. Chuẩn chữ kí số „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 374 IV.1.4. Chuẩn chữ kí số Ví dụ: „ Giả sử p=29 q =7, p = 4q+1. „ 3 ∈ Zp* nên ta có thể lấy: α = 34 mod 29 =23 „ Chọn a =5, khi đó : β = αa mod p=235 mod 29=25 „ Ký bức điện x = 6: Chú ý: p-1=qt, với t là số nguyên Để chọn α, ta có thể chọn g bất kỳ ∈ Zp* và tính α =gt bởi vì khi đó: αq (mod p) =gtq (mod p) = g(p-1) (mod p) = 1 (mod p) (ĐL Ferma) Truyền và bảo mật thông tin Giả sử p là số nguyên tố 512 bít sao cho bài toán logarithm rời rạc trong Zp khong Giải được, cho q là số nguyên tố 160 bít là ước của (p-1). Giả thiết α ∈ Zp là căn bậc q của 1 modulo p (αq≡1 (mod p). Cho P =Zp . A = Zq× Zq và định nghĩa : K = {(p,q,α ,a,β ) : β ≡ αa (mod p)} các số p, q, α và β là công khai, còn a mật. Với K = (p,q,α ,a,β )và với một số ngẫu nhiên (mật) k ,1 ≤ k ≤ q-1, ta định nghĩa: sig (x,k) = (γ ,δ) γ =(αk mod p) mod q trong đó δ = (x +aγ )k-1 mod q và Với x ∈ Zp và γ ,δ ∈ Zq , qua trình xác minh sẽ hoàn toàn sau các tính toán : e1= xδ-1 mod q e2= γδ-1 mod q ver (x, γ, δ) = true ⇔( αe1βe2 mod p) mod q = γ „ Chọn số ngẫu nhiên k =3=> k-1=5 : khi đó: γ =(αk mod p) mod q =(233 mod 29) mod 7=2 „ và δ = (x +aγ )k-1 mod q =(6+5*2)*5 mod 7=3 „ 375 Chữ kí (2, 3) trên bức điện 6 được xác minh bằng các tính toán sau: δ-1 = 5 e1= xδ-1 mod q=6*5 mod 7=2 e2= γδ-1 mod q=2*5 mod 7=3 ( αe1βe2 mod p) mod q=232*253 mod 29 mod 7=2 (= γ ) Truyền và bảo mật thông tin 376 94 Mô hình ứng dụng CKĐT IV.2. Các hàm băm IV.2.1. Khái niệmhàm băm IV.2.2. Tính chất hàm băm IV.2.3. Một số hàm băm nổi tiếng IV.2.4. Ứng dụng các hàm băm Truyền và bảo mật thông tin 377 Truyền và bảo mật thông tin 378 IV.2.1. Khái niệm hàm băm IV.2.1. Khái niệm hàm băm Đặt vấn đề „ Với các sơ đồ ký số, chỉ cho phép ký các bức thông điệp (thông tin) có kích thước nhỏ. „ Đối với thông điệp lớn (chẳng hạn vài chục MB)? Có giải pháp đơn giản là chặt bản thông điệp ra nhiều đoạn nhỏ (chẳng hạn 160 bit) rồi ký lên từng đoạn. Biện pháp này sẽ gặp những vấn đề gì? Các vấn đề mắc phải: „ Thứ nhất: kích thước thông điệp sẽ lớn lên (nếu sử dụng DSS thì riêng kích thước chữ ký gấp đôi thông điệp). „ Thứ hai: với các chữ ký “an toàn” thì tốc độ chậm vì chúng dùng nhiều phép tính số học phức tạp như số mũ modulo. „ Thứ ba : vấn đề nghiêm trọng hơn đó là kết quả sau khi ký, nội dung của thông điệp có thể bị xáo trộn các đoạn với nhau, hoặc một số đoạn trong chúng có thể bị mất mát, trong khi người nhận cần phải xác minh lại thông điệp. Ta cần phải bảo vệ tính toàn vẹn của thông điệp. Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 379 Truyền và bảo mật thông tin 380 95 IV.2.1. Khái niệm hàm băm IV.2.1. Khái niệm hàm băm Giải pháp cho các vấn đề vướng mắc đến chữ ký số là dùng hàm băm (Hash) để trợ giúp cho việc ký số. Các thuật toán băm với đầu vào là các bức thông điệp có dung lượng, kích thước tùy ý (vài KB đến vài chục MB thậm chí hơn nữa) – các bức thông điệp có thể là dạng văn bản, hình ảnh, âm thanh, file ứng dụng v.v… - và với các thuật toán băm: MD2, MD4, MD5, SHA cho các bản băm đầu ra có kích thước cố định (128 bit với dòng MD, 160 bit với SHA) được gọi là cốt của bức điện (message digest). Định nghĩa „ Hàm băm là các thuật toán không sử dụng khóa để mã hóa (ở đây ta dùng thuật ngữ “băm” thay cho “mã hóa”), nó có nhiệm vụ “lọc” (băm) thông điệp được đưa vào theo một thuật toán h một chiều nào đó, rồi đưa ra một bản băm – văn bản đại diện – có kích thước cố định. Do đó người nhận không biết được nội dung hay độ dài ban đầu của thông điệp đã được băm bằng hàm băm. „ Giá trị của hàm băm là duy nhất, và không thể suy ngược lại được nội dung thông điệp từ giá trị băm này. 381 Truyền và bảo mật thông tin Truyền và bảo mật thông tin IV.2.1. Khái niệm hàm băm IV.2.1. Khái niệm hàm băm Kết hợp CKĐT với hàm băm: Kết hợp CKĐT với hàm băm: „ Giả sử A muốn gửi cho B thông điệp x. A thực hiện các bước sau: 1. x 382 z=h(x) y=sigA(z) y A Kênh không an toàn x true 2. verA(z,y) z=h(x) Truyền và bảo mật thông tin Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 3. false „ Khi B nhận được (x, y). B thực hiện các bước sau: 1. 2. B 383 A băm thông điệp x, thu được bản đại diện z = h(x) – có kích thước cố định 128 bit hoặc 160 bit. A ký số trên bản đại diện z bằng khóa bí mật của mình, thu được bản ký số y = sigA(z). A gửi (x, y) cho B B dùng thuật toán băm – tương ứng với thuật toán băm mà A dùng – để băm thông điệp x đi kèm, nhận được z=h(x). B kiểm tra chữ ký số để xác minh xem thông điệp mà mình nhận được có phải được gửi từ A hay ko bằng cách sử dùng hàm verA(z,y) Truyền và bảo mật thông tin 384 96 IV.2.2. Tính chất hàm băm „ „ „ „ „ IV.2.2. Tính chất hàm băm Tính chất 1: Hàm băm không va chạm yếu Không gian hàm băm nhỏ hơn không gian thông điệpÆ có sự đụng độ: tồn tại 2 thông điệp x, x’, x≠x’ mà h(x)=h(x’) Do đó có thể tấn công: Người A gửi cho B (x, y) với y = sigA(h(x)). Nhưng trên đường truyền, tin bị lấy trộm. Tên trộm, bằng cách nào đó tìm được một bản thông điệp x’ có h(x’) = h(x) mà x’ ≠ x. Sau đó, hắn đưa x’ thay thế x rồi truyền tiếp cho người B. Người B nhận được và vẫn xác thực được thông tin đúng đắn. Để tránh tấn công trên, hàm băm phải không va chạm yếu Truyền và bảo mật thông tin 385 IV.2.2. Tính chất hàm băm „ „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Tính chất 1: Hàm băm không va chạm yếu: Hàm băm h là không va chạm yếu nếu khi cho trước một bức điện x, không thể tiến hành về mặt tính toán để tìm ra một bức điện x’ ≠ x mà h(x’) = h(x). Truyền và bảo mật thông tin 386 IV.2.2. Tính chất hàm băm Tính chất 2: Hàm băm không va chạm mạnh: Xét một kiểu tấn công: Đầu tiên, tên giả mạo tìm ra được hai bức thông điệp x’ và x (x’ ≠ x) mà có h(x’) = h(x) (ta coi bức thông điệp x là hợp lệ, còn x’ là giả mạo). Tiếp theo, hắn đưa cho ông A và thuyết phục ông này kí vào bản tóm lược h(x) để nhận được y. Khi đó (x’, y) là bức điện giả mạo nhưng hợp lệ. Để tránh kiểu tấn công này, hàm h phải thỏa mãn tính không va chạm mạnh: Hàm băm h là không va chạm mạnh nếu không có khả năng tính toán để tìm ra hai bức thông điệp x và x’ mà x ≠ x’ và h(x) = h(x’). Truyền và bảo mật thông tin „ 387 „ „ Tính chất 3: Hàm băm một chiều: Việc giả mạo các chữ kí trên bản tóm lược thông báo z ngẫu nhiên thường xảy ra với sơ đồ chữ kí. Giả sử tên gải mạo tính chữ kí trên bản tóm lược thông báo z ngẫu nhiên như vậy. Sau đó anh ta tìm x sao cho z= h(x). Nếu làm được như vậy thì (x,y) là bức điện giả mạo hợp lệ. Để tránh được tấn công này, h cần thoả mãn tính chất một chiều: Hàm Hash h là một chiều nếu khi cho trước một bản tóm lược thông báo z, không thể thực hiện về mặt tính toán để tìm bức điện x sao cho h(x) = z. Truyền và bảo mật thông tin 388 97 IV.2.3.1. Hàm băm MD5 (Message Digest) IV.2.3. Một số hàm băm nổi tiếng „ IV.2.3.1. Hàm băm MD5 IV.2.3.2. Hàm băm SHA „ „ „ „ Truyền và bảo mật thông tin 389 IV.2.3.2. Hàm băm SHA (Secure Hash Algorithm) „ „ „ „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế Truyền và bảo mật thông tin 390 IV.2.4. Ứng dụng các hàm băm Được công bố trong Hồ sơ Liên bang năm 1992 và được chấp nhận làm tiêu chuẩn vào năm 1993 do Viện Tiêu Chuẩn và Công Nghệ Quốc Gia (NIST) Được thiết kế dựa trên những nguyên tắc của MD4/MD5 nhưng phức tạp hơn Kết quả đầu ra có độ dài 160 bit. Tốt hơn MD5 Truyền và bảo mật thông tin Ronald Rivest là người đã phát minh ra các hàm băm MD2, MD4 (1990) và MD5 (1991). Hàm MD5 là bản cải tiến được dùng rộng rãi nhất, là nguyên tắc chung cho nhiều hàm băm khác Đầu ra MD là 128 bit, MD5 được xem là an toàn Tuy nhiên, với sự phát triển của thuật toán thám mã hiện nay, các hàm băm 128 bit được khuyến nghị là không nên dùng cho các hệ thống mới „ „ Úng dụng chính của các hàm băm là sử dụng với CKĐT Xác thực tính nguyên vẹn của dữ liệu trên đường truyền: „ „ „ 391 Truyền cả dữ liệu lẫn giá trị băm, Khi nhận được dữ liệu, sử dụng hàm băm tính kết quả và so sánh với giá trị băm nhận được Xác thực người dùng: lưu tên tài khoản và giá trị băm của mật khẩu. Để kiểm tra xem người đăng nhập hợp lệ: băm mật khẩu nhập vào và so sánh với giá trị mật khẩu lưu trong hệ thống. Truyền và bảo mật thông tin 392 98
- Xem thêm -