Luận văn Khảo sát mã ma trận, phân tích độ an toàn, hiệu năng và cải tiến

1  ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN BÙI QUANG THÀNH KHẢO SÁT Mà MA TRẬN, PHÂN TÍCH ĐỘ AN TOÀN, HIỆU NĂNG VÀ CẢI TIẾN Chuyên ngành: ĐẢM BẢO TOÁN HỌC CHO MÁY TÍNH VÀ HỆ THỐNG TÍNH TOÁN Mã số: 60 46 35 LUẬN VĂN THẠC SĨ: TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC : TS. NGUYỄN ĐÌNH THÚC Thành Phố Hồ Chí Minh – Năm 2009 2  LỜI CÁM ƠN Lời đầu tiên. tôi xin gởi lời cám ơn đến tất cả các thầy cô ở Khoa Toán - Tin Học đã tận tụy truyền đạt các kiến thức cho chúng tôi trong suốt thời gian học tại trường. Tôi xin gởi lời cám ơn sâu sắc đến TS. Nguyễn Đình Thúc; thầy đã tận tình hướng dẫn chúng tôi trong thời gian học cũng như trong suốt thời gian tôi làm bài luận văn với thầy; thầy đã tận tình hướng dẫn, giúp đỡ và động viên để tôi hoàn thành luận văn. Tôi cũng cám ơn đến tất cả các anh chị học viên cao học các khóa đã giúp đỡ tôi trong suốt khóa học cũng như trong thời gian làm luận văn. Tôi xin gởi lời cám ơn đến toàn thể cán bộ viên chức Khoa Dược Đại học Y Dược TPHCM, nơi tôi đang công tác. Cơ quan đã tạo mọi điều kiện thuận lợi để tôi hoàn thành luận văn và khóa học. Cuối cùng tôi xin gởi lời cám ơn đến tất cả những người thân của tôi, gồm ba, mẹ và em tôi. Gia đình đã là nguồn động viên về mặt tinh thần cũng như là vật chất để tôi hoàn thành khóa học. Tôi mong nhận được sự góp ý, chỉ dẫn của quý thầy cô và các bạn để luận văn được hoàn thiện hơn. Thành phố Hồ Chí Minh, tháng 09 năm 2009 Học viên cao học Bùi Quang Thành 3  MỤC LỤC Trang Trang phụ bìa ....................................................................................................... 1 Lời cảm ơn ............................................................................................................ 2 Mục lục ................................................................................................................. 3 Tóm tắt ................................................................................................................. 6 Các ký hiệu .......................................................................................................... 8 Chương 1: Các khái niệm cơ bản 1. Tổng quan ............................................................................................ 9 2. Mật mã học (Cryptography) ................................................................ 9 2.1. Mật mã học ................................................................................... 9 2.2. Hệ thống mã hóa (Cryptosystem) ............................................... 10 2.3. Mã hóa đối xứng .......................................................................... 11 3. Kiến thức lý thuyết số ......................................................................... 11 3.1. Modulo .......................................................................................... 11 3.1.1. Định nghĩa .......................................................................... 11 3.1.2. Một số tính chất ................................................................... 11 3.1.3. Định lý Fermat nhỏ ............................................................. 12 3.2. m] ................................................................................................. 12 3.2.1. Định nghĩa ........................................................................... 12 3.2.2. Phép toán trên m] .............................................................. 12 3.2.3. Các tính chất của m] .......................................................... 12 4  3.2.4. Định lý m] là trường khi m là số nguyên tố. ..................... 13 4. Modulo ma trận .................................................................................. 13 4.1. Định nghĩa ................................................................................... 13 4.2. Tính chất ....................................................................................... 14 Chương 2: Mã ma trận/Mã hill – Khảo sát không gian khóa 1. Mã thay thế (Substitution ciphers) ...................................................... 16 1.1. Định nghĩa .................................................................................... 16 1.2. Ví dụ ............................................................................................. 16 2. Mã ma trận (Matrix cipher) ................................................................. 17 3. Mã Hill (Hill cipher) ............................................................................ 18 3.1. Bảng chữ cái (Alphabet) ............................................................... 18 3.2. Hill – 2 cipher ............................................................................... 19 3.3. Thuật toán: Mã hóa với Hill cipher ............................................. 21 4. Không gian khóa ................................................................................. 24 4.1. Định nghĩa không gian khóa ......................................................... 24 4.2. Khái niệm khóa yếu .................................................................... 24 5. Khảo sát không gian khóa ................................................................... 25 Ta xét khóa K là ma trận vuông có kích thước d×d trên trường m] 5.1. Xét không gian khóa trên trường p] (p nguyên tố) ..................... 25 5.2. Xét không gian khóa là với đặc số nguyên tố p ( = nm p )............ 26 5.3. Xét không gian khóa trên miền m] , 0 i z n i i m p = =∏ , ip nguyên tố .. 28 5.4. Không gian tốt nhất của Alphabet .............................................. 30 6. Xét các trường hợp khóa yếu ............................................................... 35 6.1. Ma trận đối hợp (Involutory matrix) ............................................ 35 5  6.1.1. Xây dựng ma trận đối hợp................................................... 35 6.1.1.1. Ma trận đối hợp trên trường ; 2p p >] ...................... 35 6.1.1.2. Ma trận đối hợp trên trường 2] .................................. 37 6.1.2. Đếm số ma trận đối hợp ...................................................... 42 6.2. K là khóa yếu với Kv = v hoặc vK = v ......................................... 45 6.2.1. Xác định khóa yếu bằng định thức...................................... 45 6.2.2. Xác định khóa yếu bằng trị riêng ....................................... 47 7. Tóm tắt ................................................................................................ 50 Chương 3: Xây dựng thuật giải sinh khóa cho mã Hill 1. Định lý sinh khóa trên p] ................................................................... 51 2. Xác định cơ sở hình thành thuật giải ................................................... 53 3. Thuật giải ............................................................................................ 55 4. Ví dụ .................................................................................................... 56 5. Khảo sát không gian khóa vừa sinh theo thuật giải ........................... 58 Chương 4: Các vấn đề liên quan đến mã Hill 1. Sinh khóa theo pincodes ..................................................................... 60 2. Cách tấn công mã Hill gốc .................................................................. 65 3. Cải tiến thuật giải (sinh khóa từ pincodes và chuỗi ngẫu nhiên) ....... 66 4. Tính nhanh ma trận khả nghịch của khóa: K-1 = U-1L-1 ....................... 68 Kết luận và kiến nghị ........................................................................................... 71 Tài liệu tham khảo ............................................................................................... 72 Phụ lục Code demo thuật toán chương 4 .............................................................. 74 6  TÓM TẮT Tìm hiểu mã đối xứng; mã Hill dùng khóa là ma trận khả nghịch. Tìm hiểu không gian khóa của mã Hill và chỉ ra là ta nên chọn khóa trên p] , với p nguyên tố thì không gian khóa là tốt nhất. Khảo sát các trường hợp khóa yếu của mã Hill để loại bỏ khi xây dựng thuật toán sinh khóa an toàn. Xây dựng thuật toán sinh khóa là an toàn nghĩa là đã loại những trường hợp khóa yếu đã nêu ở trên. Áp dụng sinh khóa theo pincodes và cải tiến thuật toán khi sinh khóa theo pincodes. Chương 1: Các khái niệm cơ bản Tóm tắt: Nêu các khái niệm về mã hóa, mã đối xứng. Nêu các kiến thức lý thuyết số, các tính chất trên trường hữu hạn p] Nêu định nghĩa modulo ma trận. Chương 2: Hệ mã Hill/mã ma trận – Khảo sát không gian khóa của Tóm tắt: Tìm hiểu thuật toán xây dựng mã Hill. Khảo sát không gian khóa của mã Hill, tìm hiểu khóa yếu. Xác định không gian khóa tốt nhất. Xác định các trường hợp khóa yếu để loại bỏ khi xây dựng thuật toán tìm khóa an toàn cho mã Hill. 7  Chương 3: Xây dựng thuật giải sinh khóa cho mã Hill Tóm tắt: Định lý sinh khóa trên p] và xác định cơ sở xây dựng thuật toán sinh khóa Xác định thuật giải sinh khóa an toàn Khảo sát không gian khóa vừa sinh từ thuật giải (không gian khóa đủ lớn?). Chương 4: Các vấn đề liên quan đến mã Hill Tóm tắt: Sinh khóa dựa trên pincodes . Người A và người B dùng chung pincodes để sinh ra khóa và áp dụng thuật toán mã Hill để trao đổi. Nêu các vấn đề yếu của mã Hill. Cải tiến thuật toán mã Hill. Đối với chuỗi thông điệp có kích thước nhỏ hơn d×d – 1 Người A và người B trao có chung pincodes; khi sinh khóa, người A tạo ngẫu nhiên chuỗi u; người A dùng pincodes kết hợp với chuỗi u tạo thành pincodes mới và sinh khóa K dựa trên pincodes mới; áp dụng thuật toán mã Hill để mã hóa thông điệp. Sau đó gửi cho B phần thông điệp đã mã hóa và chuỗi u. Người B có pincodes và chuỗi u; kết hợp pincodes với chuỗi u để tính khóa K và K-1 sau đó áp dụng thuật toán Hill tính thông điệp. Đối với chuỗi thông điệp có kích thước lớn hơn d×d – 1 Người A sẽ chia thông điệp thành k nhóm mỗi nhóm có kích thước d×d – 1(nhóm k có thể có kích thước nhỏ hơn d×d – 1). Người A lần lượt mã hóa từng nhóm và gởi sang người B tương tự như trên(thông điệp có kích thước nhỏ hơn d×d – 1) và người B giải mã và ghép từng nhóm lại thành thông điệp gốc.Tính toán nhanh ma trận khả nghịch khi xây dựng bằng thuật toán trong chương 3. 8  CÁC KÝ HIỆU ≡ Modulo M≡ Modulo ma trận ⎢ ⎥⎣ ⎦ Phần nguyên của một số ⎡ ⎤⎢ ⎥ Phần nguyên trên của một số  gcd(a,b) Ước số chung lớn nhất của a và b In Ma trận đơn vị n × n Zr×s Ma trận 0 có kích thước r × s P Ma trận hoán vị (hoán vị các hàng trong ma trận đơn vị) L Ma trận tam giác dưới U Ma trận tam giác trên GL (n,F) Không gian ma trận khả nghịch cấp n trên trường F p] Trường p] với p là số nguyên tố ( ),M d F Không gian ma trận vuông trên trường F 9  Chương 1: CÁC KHÁI NIỆM CƠ BẢN 1. Tổng quan Ngày nay do thông tin ngày càng phát triển, việc bảo vệ thông tin khi gởi và nhận càng trở nên quan trọng. Bên cạnh tính toàn vẹn thông tin và xác thực các đối tác trong liên lạc và xác thực nội dung thông tin trong liên lạc, thì việc xuất hiện nhiều công cụ cũng như nhiều thuật toán để giải quyết vấn đề bảo mật thông tin cũng phong phú. Việc tìm hiểu và phát triển thuật toán Hill cũng nhằm vào mục đích đó. Việc tìm hiểu về không gian khóa : phân phối, kích thước khóa; và việc phát sinh một khóa sao cho tốt là vấn đề quan trọng và góp phần làm hoàn thiện thuật toán mã hóa Hill. 2. Mật mã học (cryptography) 2.1 Mật mã học Mật mã học - Cryptography (hay crypto)- là ngành khoa học ứng dụng toán học vào việc biến đổi thông tin sang một dạng khác với mục đích che dấu nội dung, ý nghĩa thông tin gốc. Đây là một ngành quan trọng và có nhiều ứng dụng trong đời sống xã hội. Ngày nay, các ứng dụng mã hóa và bảo mật thông tin đang được sử dụng ngày càng phổ biến hơn trong các lĩnh vực khác nhau trên thế giới, từ các lĩnh vực an ninh, quân sự, quốc phòng…, cho đến các lĩnh vực dân sự như thương mại điện tử, ngân hàng…[1] 10  Mật mã học nghiên cứu về việc giấu thông tin. Cụ thể hơn, mật mã học là ngành học nghiên cứu về những cách chuyển đổi thông tin từ dạng "có thể hiểu được sang dạng "không thể hiểu được" và ngược lại. Mật mã học giúp đảm bảo những tính chất sau: ƒ Tính bí mật (confidentiality): thông tin chỉ được tiết lộ cho những ai được phép. ƒ Tính toàn vẹn (integrity): thông tin không thể bị thay đổi mà không bị phát hiện. ƒ Tính xác thực (authentication): người gửi (hoặc người nhận) có thể chứng minh đúng họ. ƒ Tính không chối bỏ (non-repudiation): người gửi hoặc nhận sau này không thể chối bỏ việc đã gửi hoặc nhận thông tin. ƒ Encrypt (encipher): mã hóa – quá trình biến đổi thông tin từ dạng ban đầu - có thể hiểu được sang dạng không thể hiểu được, với mục đích giữ bí mật thông tin đó. ƒ Decrypt (decipher): giải mã – quá trình ngược lại với mã hóa, khôi phục lại thông tin ban đầu từ thông tin đã được mã hóa. ƒ Plaintext (cleartext): dữ liệu gốc (chưa được mã hóa). ƒ Ciphertext: dữ liệu đã được mã hóa. 2.2. Hệ thống mã hóa (Cryptosystem) Định nghĩa 1: [Theo 1] Hệ thống mã hóa (cryptosystem) là một bộ năm (P, C, K, E, D) thỏa mãn các điều kiện sau: 1. Tập nguồn P là tập hữu hạn tất cả các mẩu tin nguồn cần mã hóa có thể có. 11  2. Tập đích C là tập hữu hạn tất cả các mẩu tin có thể có sau khi mã hóa. 3. Tập khóa K là tập hữu hạn các khóa có thể được sử dụng. 4. E và D lần lượt là tập luật mã hóa và giải mã. Với mỗi khóa k ∈ K , tồn tại luật mã hóa ke E∈ và luật giải mã kd D∈ tương ứng. Luật mã hóa: :ke P C→ và luật giải mã : :kd C P→ là hai ánh xạ thỏa mãn ( )( ) ,k kd e x x x P= ∀ ∈ 2.3. Mã hóa đối xứng Mã hóa đối xứng là quá trình mã hóa và giải mã một thông điệp sử dụng cùng một mã khóa gọi là khóa bí mật (secret key) hay khóa đối xứng (symmetric key). Do đó, vấn đề bảo mật thông tin đã mã hóa hoàn toàn phụ thuộc vào việc giữ bí mật nội dung của khóa đã được sử dụng.[1] 3. Kiến thức lý thuyết số 3.1. Modulo 3.1.1. Định nghĩa: (mod )a b m≡ có nghĩa là a – b là bội số của m Hay a – b = k. m 3.1.2. Một số tính chất: (mod )a a m≡ Nếu (mod )a b m≡ thì (mod )b a m≡ Nếu (mod )a b m≡ và (mod )b c m≡ thì (mod )a c m≡ Nếu (mod )a c m≡ và (mod )b d m≡ thì (mod )a b c d m+ ≡ + Nếu (mod )a c m≡ và (mod )b d m≡ thì (mod )a b c d m× ≡ × 12  3.1.3. Định lý Fermat nhỏ [Theo 4] Với p là số nguyên tố dương, với mọi số nguyên a không là bội của p thì ta luôn có ( )1 1 modpa p− ≡ . Vì p là số nguyên tố và a không là bội của p ; thì tương đương ( ) ( )11 mod 1 mod−≡ ⇔ ≡pa p a p 3.2. ]m 3.2.1. Định nghĩa: ]m được định nghĩa là tập hợp { }0;1; ; 1m −… , được trang bị phép cộng (ký hiệu +) và phép nhân (ký hiệu là ×). Phép cộng và phép nhân trong m] được thực hiện tương tự như trong ] , ngoại trừ kết quả tính theo modulo m. 3.2.2. Phép toán trên m] Phép + : , ma b∈] , ma b+ ∈] , mod a b m+ Phép × : , ma b∈] , ma b× ∈] , mod a b m× 3.2.3. Các tính chất của m] 1. Cho mọi , ma b∈] thì ma b+ ∈] 2. Cho mọi , , ma b c∈] , ( ) ( )a b c a b c+ + = + + 3. Cho mọi , , ma b c∈] , a b b a+ = + 4. Với mọi ma∈] , 0 0a a a+ = + = 5. Với mọi ma∈] , tồn tại duy nhất x sao cho 0a x x a+ = + = 6. Cho mọi , ma b∈] thì ma b× ∈] 7. Cho mọi , , ma b c∈] , ( ) ( )a b c a b c× × = × × 13  8. Cho mọi , ma b∈] , . .a b b a= 9. Với mọi ma∈] , .1 1.a a a= = 10. Cho mọi , , ma b c∈] , ( )a b c a b a c× + = × + × 11. Trong m] thì 1 0≠ 12. Nếu m] mà thỏa tính chất này thì m] sẽ là một trường. Với mọi ma∈] , tồn tại duy nhất x sao cho 1a x x a× = × = 3.2.4. Định lý m] là trường khi m là số nguyên tố: m] là trường khi và chỉ khi m là số nguyên tố. Chứng minh : Với mọi ma∈] , do m là số nguyên tố nên ( )gcd , 1a m = (gcd(a,m) : ước chung lớn nhất của a và m) Do đó tồn tại , mu v∈] sao cho : 1a u m v× + × = Lấy modulo m hai vế ta được : 1a u u a× = × = Thỏa tính chất 12 nên m] là trường khi và chỉ khi m là số nguyên tố. Mở rộng : Trên trường p] với p là số nguyên tố Với ( )1, 0, 1 modppa a a p−∀ ∈ ≠ ≡] 4. Modulo ma trận [Theo 6] 4.1. Định nghĩa Cho ma trận A, B ∈ ( )rxsM ] ; ta định nghĩa (mod ) M A B m≡ nghĩa là các phần tử (mod )ij ija b m≡ 14  Ví dụ: m = 7 2 3 4 5 ⎛ ⎞= ⎜ ⎟⎝ ⎠A 9 10 25 12 ⎛ ⎞= ⎜ ⎟⎝ ⎠B Thì (mod 7)≡MA B 4.2. Tính chất 1. Nếu (mod ) M A B m≡ và (mod )MC D m≡ thì (mod )MA C B D m± ≡ ± 2. Nếu (mod ) M A B m≡ và (mod )MC D m≡ thì (mod )MA C B D m× ≡ × 3. Nếu (mod ) M A B m≡ và (mod )mα β≡ thì (mod )MA B mα β× ≡ × 4. Nếu A, B là những ma trận vuông thì (mod ) M A B m≡ thì det det (mod )A B m≡ Chứng minh (1) ta có : A C± nghĩa là ( )ij ija c± ; B D± nghĩa là ( )ij ijb d± Mà ta có (mod ) (mod ) M ij ijA B m a b m≡ ⇔ ≡ (mod ) (mod ) M ij ijC D m c d m≡ ⇔ ≡ Theo tính chất ta co:ù (mod )ij ij ij ija c b d m± ≡ ± Theo định nghĩa thì (mod ) M A C B D m± ≡ ± (2);(3) áp dụng tính chất modulo chứng minh tương tự (1)   (4) ( )mod mMA B≡ nghĩa là mod = mod ij ija m b m Ta có: ( ) 1 21 2det s d s S A sign a a aσ σ σ σ σ ∈ = ∑ … 15  ( ) ( )( ) ( )( )( ) ( )( ) 1 2 1 2 1 2 1 2 1 2 1 2 det mod mod = mod mod = mod mod mod mod mod s d s d s d s S s S s S A m sign a a a m sign a a a m m sign a m a m a m m m σ σ σ σ σ σ σ σ σ σ σ σ σ σ σ ∈ ∈ ∈ ⎛ ⎞= ⎜ ⎟⎜ ⎟⎝ ⎠ ⎛ ⎞⎜ ⎟⎜ ⎟⎝ ⎠ ⎛ ⎞⎜ ⎟⎜ ⎟⎝ ⎠ ∑ ∑ ∑ … … … ( )( )( ) ( )( ) ( )( ) ( ) 1 2 1 2 1 2 1 2 1 2 1 2 = mod mod mod mod mod = mod mod = mod s d s d s d s S s S s S sign b m b m b m m m sign b b b m m sign b b b m σ σ σ σ σ σ σ σ σ σ σ σ σ σ σ ∈ ∈ ∈ ⎛ ⎞⎜ ⎟⎜ ⎟⎝ ⎠ ⎛ ⎞⎜ ⎟⎜ ⎟⎝ ⎠ ⎛ ⎞⎜ ⎟⎜ ⎟⎝ ⎠ ∑ ∑ ∑ … … … = det mod B m „ 16  Chương 2: Mà MA TRẬN/Mà HILL–KHẢO SÁT KHÔNG GIAN KHÓA Plaintext: thông điệp cho trước. Key: khóa bí mật gồm các biến đổi có ý nghĩa đặc biệt. Inverse key: phép biến đổi toán theo thứ tự ngược để tìm lại plaintext gốc. Ciphertext: dùng key biến đổi plaintext và một số ký tự khác thành những ký tự mới 1. Mã thay thế (Substitution ciphers) 1.1. Định nghĩa [10] Mã thay thế đơn giản là việc sắp xếp lại những ký tự của của plaintext đã cho. Với mã thay thế những ký tự tha