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ự thay thế trong plaintext được thay bằng ký tự khác. 1.2. Ví dụ: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z F T G S M O N A Y P V Q C D Z R W L E X H B K I U J Bảng mã thay thế với quy tắc như trong bảng Ta cần mã thông điệp: “BUI QUANG THANH” Ciphertext sẽ là : “THY WHFDN XAFDA” Khi nhận được ciphertext và dùng bảng mã thay thế để giải mã trở lại tìm ra thông điệp. 17  Tuy nhiên, ở mã thay thế có vấn đề là phép thay thế luôn cố định do đó nếu có đủ các chữ cái và bằng phương pháp thống kê thì người ta có thể đoán được bảng mã thay thế và tìm ra khóa, tức là tìm ra bảng quy tắc thay thế như trên.     2. Mã ma trận (Matrix cipher) Để giải quyết vấn đề của mã thay thế thì chúng ta sẽ dùng mã ma trận. Thông điệp của chúng ta sẽ được chuyển thành dạng ma trận. Với mã ma trận thì thông điệp sẽ được biểu diễn dưới dạng ma trận và khóa ở đây sẽ là ma trận vuông khả nghịch. Và việc mã hóa thông điệp được thực hiện như sau: C = K × M (2.1) Và việc giải mã ta thực hiện M = 1K − × C (2.2) Ma trận khóa K có kích thước d×d khả nghịch trên m] thì ma trận M (plaintext) sẽ có kích thước là d×m; và ma trận C (cipher) sẽ có kích thước d×m. Với hai ma trận vuông bậc d, K≠ K1 trong ( ), mM d ] ; thì không tồn tại 1 1 1K K − −= trong ( ), mM d ] Chứng minh không tồn tại K1 sao cho K≠ K1 trong ( ), mM d ] và 1 11K K− −= trong ( ), mM d ] . Do K≠ K1 trong ( ), mM d ] ⇔ K≠ K1 trong ( ),M d \ ⇔ 1 11K K− −≠ trong ( ),M d \ Nếu 1 11K K − −≠ trong ( ),M d \ mà 18  ( ) ( ) ( ) ( ) 1 1 1 1 1 1 1 1 1 1 1 1 1 mod m mod m mod m mod m M M M d M d M K K K K K K I K K I K K K K K K − − − − − − ≡ ⇔ × ≡ × ⇔ ≡ × ⇔ × ≡ × × ⇔ ≡ ( ) mod m Suy ra vô lý vì K≠ K1 trong ( ), mM d ] „ 3. Mã Hill (Hill cipher) [Theo 10] 3.1. Bảng chữ cái (Alphabet) Bảng chữ cái của tiếng Anh gồm cĩ 26 ký tự viết hoa. Khi chúng ta mã hĩa hay giải mã, chúng ta sẽ đại diện bằng những con số từ 0…25. Và các chữ cái được thể hiện như bảng sau: A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Khi sử dụng Hill cipher thì chiều dài của Alphabet có thể là số nguyên bất kỳ m >1. Trong bảng chữ cái bắt đầu bằng số 0, và đôi khi để phá mã Hill khó hơn thì những chữ cái ánh xạ thành những số bất kỳ trong khoảng từ 0 đến 25; chứ không nhất thiết phải theo thứ tự như bảng trên. 19  3.2. Hill – 2 cipher Ở đây là ví dụ về Hill – 2 cipher, ma trận khóa của ta là ma trận vuông 2 chiều khả nghịch. Thông điệp ta cần mã hóa phải sử dụng bảng Alphabet ở trên. Tuy nhiên thông điệp của ta cần mã hóa không nhất thiết phải chẵn theo chiều ma trận 2 × m; ta thêm vào ba ký tự đặc biệt . ; ? ; ∪ (khoảng trắng) tương ứng là 26; 27; 28; nếu thông điệp không đủ chẵn theo 2× m thì ta thêm các khoảng trắng vào cuối thông điệp để đủ 2 × m. Lúc này ta sẽ có 29 ký tự và xét trên trường 29] lúc này bảng mới là: A B C D E F G H I J K L M N O 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 P Q R S T U V W X Y Z . ? ∪ 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Ví dụ : ma trận khóa K là : 2 3 4 5 K ⎛ ⎞= ⎜ ⎟⎝ ⎠ Ta cần mã thông điệp: “BE” sẽ được biểu diễn dưới dạng ma trận như sau: 1 4 M ⎛ ⎞= ⎜ ⎟⎝ ⎠ Để mã hóa “BE” ta tính tích ma trận khóa và ma trận thông điệp C K M= × 2 3 1 14 4 5 4 24 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠C K M 20  Cuối cùng thì ta xem trong bảng Alphabet thì 14 tương ứng với O và 24 tương ứng với Y. Vậy sau khi mã hóa ta được là “ OY ”. Ta có tương ứng việc B được mã hóa thành O và E được mã hóa thành Y. Nhưng ta xét ví dụ khác mã hóa “BC”. Ta làm tương tự như trên “BC” sẽ được biểu diễn dưới dạng ma trận như sau: / 1 2 M ⎛ ⎞= ⎜ ⎟⎝ ⎠ Để mã hóa “BC” ta tính tích ma trận khóa và ma trận thông điệp / /C K M= × ' / 2 3 1 8 4 5 2 14 C K M ⎛ ⎞⎛ ⎞ ⎛ ⎞= × = =⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠⎝ ⎠ ⎝ ⎠   Cuối cùng thì ta xem trong bảng Alphabet thì 8 tương ứng với I và 14 tương ứng với O. Vậy sau khi mã hóa “BC” ta được là “ IO ”. Ta có tương ứng việc B được mã hóa thành O và M được mã hóa thành Y. Bây giờ ta xét mã hóa thông điệp “QUANG∪THANH”. Thông điệp này sẽ viết dưới dạng ma trận như sau; ta sẽ chia các chữ cái thành các nhóm như sau tương ứng với kích thước 2x2 của khóa: (QU);(AN);(G ∪)(TH);(AN) do chỉ còn lại H không đủ phần tử để tạo nhóm ta thêm ký tự ∪ vào sau thông điệp . Như vậy: nhóm (H ∪) Ma trận M được viết là 16 0 6 19 0 7 20 13 28 7 13 28 M ⎛ ⎞= ⎜ ⎟⎝ ⎠ Để mã hóa thì ta tính tích K M× 2 3 16 0 6 19 0 7 92 39 96 59 39 98 4 5 20 13 28 7 13 28 164 65 164 111 65 168 C K M ⎛ ⎞ ⎛ ⎞ ⎛ ⎞= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ Ở đây có một số tính ra có giá trị lớn hơn 29, khi muốn tìm tương ứng các chữ cái thì ta thực hiện phép chia lấy phần dư (modulo) cho 29(29 ở đây là chiều dài của bảng Alphabet.). Như vậy: 21  92 39 96 59 39 98 5 10 9 1 10 11 mod 29 164 65 164 111 65 168 19 7 19 24 7 23 C ⎛ ⎞ ⎛ ⎞= =⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ Để tìm ciphertext thì ta viết ma trận ta vừa tính được như sau: (5 19 10 7 9 19 1 24 10 7 11 23) Như vậy mã hóa thông điệp “QUANG∪THANH∪” thì ta thu dược cipher text là “FTKHJTBYKHLX” Việc giả mã thì ta tính ma trận khả nghịch của K theo mod 29. 1−= ×M K C 3.3. Thuật toán: Mã hóa với Hill cipher Chúng ta giả sử chiều dài của Alphabet là m > 1. Hill – d cipher, khóa sẽ là ma trận vuông K bậc d với các phần tử trong m] . Thuật toán mã hóa Hill dùng để mã hóa plaintext cho trước được thực hiện qua các bước sau : Mã hóa 1. Người gởi tách plaintext ra thành k nhóm mỗi nhóm là một vectơ có d ký tự(tương ứng với bậc của khóa) và việc tách này được thực hiện từ trái qua phải. Nếu nhóm cuối không đủ d ký tự thì ta sẽ điền thêm ký tự cuối của plaintext cho đến khi nhóm cuối có đủ d ký tự hoặc ta điền vào các ký tự đặc biệt như khoảng trắng. Chuyển các vectơ này thành vectơ cột. 2. Thay thế các ký tự tương ứng thành các chữ số từ 0 đến m – 1 theo bảng Alphabet mà ta đã định nghĩa. 3. Viết k vectơ cột thành ma trận; có số dòng là d và thực hiện phép nhân ma trận khóa K với ma trận M vừa tạo theo modulo m. C = K × M (modulo m) (2.3) 4. Sau khi được tích của hai ma trận thì ta sẽ thu được ma trận C. Từ ma trận C ta sẽ viết lại thành k nhóm, mỗi nhóm gồm có d phần tử(số phần tử 22  của một cột ma trận). Sau đó ta sẽ tương ứng các số trong nhóm thành các ký tự và kết quả là ta sẽ tìm được ciphertext. Giải mã: 1. Khi nhận được ciphertext thì người nhận cũng sẽ tách ciphertext thành k nhóm với mỗi nhóm có d ký tự. 2. Thay thế các ký tự tương ứng thành các chữ số từ 0 đến m – 1 theo bảng Alphabet mà ta định nghĩa. 3. Viết k nhóm thành ma trận có số dòng là d và thực hiện phép nhân với K-1 và tích này tính theo modulo m. M= K-1 × C(modulo m) (2.4) 4. Sau khi có M thì ta viết lại thành k nhóm, mỗi nhóm có d phần tử(một cột của ma trận). Sau đó ta sẽ tương ứng các số trong nhóm thành các ký tự và kết quả là ta sẽ tìm được plaintext; có thể lược bỏ một số ký tự thêm vào như khoảng trắng. Ví dụ : Với Alphabet (của tiếng Anh ) gồm 26 ký tự ta sẽ thêm ba ký tự đặt biệt vào gồm có “. , ? , ∪(khoảng trắng) ” A B C D E F G H I J K L M N O 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 P Q R S T U V W X Y Z . ? ∪ 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Ta cần mã hóa thông điệp WANT ∪HELP. Plaintext là: WANT ∪HELP. 23  17 5 20 23 9 3 11 2 12 K ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ 1. Ta viết plain text của ta thành từng nhóm có chiều dài là 3. Trong trường hợp chiều dài của nhóm cuối không đủ 3 thì ta thêm ký tự khoảng trắng vào sao cho nhóm có chiều dài là 3. WAN T∪H ELP . ∪∪ 2. Ta thay thế các ký tự thành số theo quy tắc của bảng trên 22 0 13 19 28 7 4 11 15 26 28 28 Ta viết plaintext dưới dạng ma trận 22 19 4 26 0 28 11 28 13 7 15 28 M ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ 3. Ta tính ciphertext và bắt đầu gởi đi ( ) 17 5 20 22 19 4 26 25 13 11 1 23 9 3 0 28 11 28 23 14 4 6 mod 29 11 2 12 13 7 15 28 21 1 14 11 C K M ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 4. Ta viết lại dưới dạng vectơ dòng 25 23 21 13 14 1 11 4 14 1 6 11 Dựa vào bảng chữ cái ánh xạ thành số ta được ZXVNOBLEOBGL Như vậy plaintext sau khi được mã hóa thu được như sau ZXVNOBLEOBGL Để giải mã thì ta thực hiện như sau; ta lấy 1K C− × 24  Ta có : 1 16 27 27 25 10 9 15 5 27 K − ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ 1 16 27 27 25 13 11 11 22 19 4 26 25 10 9 23 14 4 6 0 28 11 28 15 5 27 21 1 14 11 13 7 15 28 M K C− ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ Ta tính được ma trận M và tìm được plaintext đã gởi. 4. Không gian khóa 4.1. Định nghĩa không gian khóa Tập hợp tất cả các ma trận vuông cấp d khả nghịch trên m] với m là giá trị xác định trước. Ta ký hiệu là GL(d, m] ) Không gian khóa là tập hợp số ma trận vuông khả nghịch trên m] trừ đi số ma trận khả nghịch nhưng là khóa yếu (ký hiệu là W). Ta ký hiệu tổng số ma trận trong không gian khóa là: S(d,m) ( )S , ( , )d m GL d m W= − 4.2. Khái niệm khóa yếu Xét trên m] • Một khóa K gọi là khóa yếu nếu K2 = Id ; ta gọi là ma trận đối hợp (Involutary matrix) • d dK × là khóa yếu nếu tồn tại véctơ v (d×1) sao cho K v v× = Ta xét các trường hợp khóa yếu: (i) Nếu K là ma trận đối hợp thì khi ta mã hóa plaintext thì thu được ciphertext, sau đó mã hóa ciphertext thì thu được plaintext. C = K × M 25  C/ = K × C = K × K × M = M Ví dụ: Ta xét trên 7] : Khóa 2 2 2 5 K ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; Ta sẽ mã hóa thông điệp 1 2 3 4 5 6 M ⎛ ⎞= ⎜ ⎟⎝ ⎠ Áp dụng Hill cipher 2 2 1 2 3 3 0 4 2 5 4 5 6 1 1 1 C K M ⎛ ⎞⎛ ⎞ ⎛ ⎞= × = =⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠⎝ ⎠ ⎝ ⎠ Khi ta thu được C thì ta sẽ dùng C để mã hóa lần nữa ta sẽ thu được M / 2 2 3 0 4 1 2 3 2 5 1 1 1 4 5 6 C K C M⎛ ⎞ ⎛ ⎞ ⎛ ⎞= × = × = =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ (ii) Nếu ma trận K là khóa yếu như trong trường hợp hai ( K v v× = )ta sẽ có trường hợp: ( )1 dM v v= … sao cho i iK v v× = thì C = K × M = M thì lúc này ta thu được C (ciphertext) cũng chính là M(Message). Ví dụ: Ta xét trên 7] : Khóa 3 1 3 6 K ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; K là khóa yếu vì tồn tại 5 a v a ⎛ ⎞= ⎜ ⎟⎝ ⎠ với 7a∈] thì K v v× = Nếu ta mã hóa 1 2 3 5 3 1 M ⎛ ⎞= ⎜ ⎟⎝ ⎠ thì 3 1 1 2 3 1 2 3 3 6 5 3 1 5 3 1 C K M M⎛ ⎞ ⎛ ⎞ ⎛ ⎞= × = × = =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 5. Khảo sát không gian khóa Ta xét khóa K là ma trận vuông có kích thước d×d trên trường m] Gọi ( , )mGL d ] là tập hợp các ma trận vuông d×d khả nghịch trên m] 26  Đặt ( , )mGL d ] là số ma trận khả nghịch bậc d trên m] 5.1. Xét không gian khóa trên trường p] (p nguyên tố) Gọi ( , )pGL d ] là tập hợp các ma trận vuông dxd khả nghịch trên p] với p là số nguyên tố. Định lý 1: [7, phần 2.1] ( )1 0 ( , ) d d i p i GL d p p − = = −∏] (2.5) Chứng minh: Dòng đầu tiên thì ta có 1dp − cách chọn (ta có d phần tử, mỗi phần tử có p cách chọn; trừ đi 1 là trừ đi trường hợp tất cả các phần tử bằng 0) Ta chọn được hàng 1; hàng thứ hai có dp p− cách chọn sao cho khi thêm hàng thứ hai vào thì hàng 1 và hàng 2 vẫn còn độc lập tuyến tính. Giả sử ta có i hàng độc lập tuyến tính thì số cách chọn khi thêm hàng i+1 vào là d ip p− Tương tự khi ta thêm hàng thứ d vào thì có 1d dp p −− cách chọn do đã có d – 1 hàng độc lập tuyến tính ( )11 0 ( , ) ( 1)( ) ( ) d d d d d d i p i GL d p p p p p p p −− = = − − − = −∏] … „ 5.2. Xét không gian khóa với đặc số nguyên tố p ( nm p= ) Bổ đề 1: [7, phần 2.2] Cho ma trận A vuông d×d; Đặt A = B + p × C với ( )ijB b= - phần dư của phép chia ( )ija và p; ( )ijC c= - phần thương của phép chia ( )ija và p Với ma trận B vuông d×d với các phần tử là các số dư trong phép chia trên và ma trận C vuông d×d với các phần tử là thương trong phép chia trên. 27  A khả nghịch mod np khi và chỉ khi B khả nghịch mod p Chứng minh Ta có: Các phần tử của B là { }0;1; ; 1p−… Các phần tử của C là { }0;1; ; 1np −… Ta có: (mod ) det det (mod ) M A B p A B p≡ ⇒ ≡ do đó gcd(detA,p) = gcd(detB,p) A khả nghịch mod np thì gcd(detA, np ) = 1 ⇒ gcd(detA,p)=1 vậy gcd (detB,p)=1. B khả nghịch mod p B khả nghịch mod p thì gcd (detB, p)=1 ⇒ gcd(detA,p)=1 thì gcd(detA, np ) = 1. A khả nghịch mod np „ Định lý 2: (Theo [7]) ( )2 1( 1) 0 ( , )n d n d d i p i GL d p p p −− = = −∏] (2.6) Chứng minh Áp dụng: A = B + pC Số ma trận B là ( )1 0 d d i i p p − = −∏ và số ma trận C là 2( 1)n dp − Suy ra được ( )2 1( 1) 0 ( , )n d n d d i p i GL d p p p − − = = −∏] „ 28  5.3. Xét không gian khóa trên m] , 0 i z n i i m p = =∏ , ip là nguyên tố Định nghĩa: 1: ( ) ( ) ( ) ( ) với ( ) mod ni i i z dxd m i dxd p n i i i M M A A A A p φ φ φ φ =→⊕ = ⊕ = ] ] (2.7) (φ là phép thặng dư Trung Hoa; ( ) ( )11mod , , mod , , mod i znn ni zA A p A p A pφ → … … ) Bổ đề 2: [7, phần 2.3] φ là đẳng cấu vành. Chứng minh φ là đẳng cấu vành; ta chứng minh φ bảo toàn phép toán + và . Cho A, B là hai ma trận vuông d×d Ta có: ( ) ( )11mod , , mod , , mod i znn ni zA A p A p A pφ = … … ( ) ( )11mod , , mod , , mod i znn ni zB B p B p B pφ = … … ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 mod , , mod , , mod mod , , mod , , mod = mod , , mod , , mod = i z i z i z nn n i z nn n i z nn n i z A B A p A p A p B p B p B p A B p A B p A B p φ φ+ = + + + + … … … … … … ( )A Bφ + ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 . mod , , mod , , mod . mod , , mod , , mod = . mod , , . mod , , . mod = . i z i z i z nn n i z nn n i z nn n i z A B A p A p A p B p B p B p A B p A B p A B p A B φ φ φ = … … … … … … „ 29  Bổ đề 3: Nếu ma trận A khả nghịch mod m nếu và chỉ nếu ( )Aφ khả nghịch Chứng minh: Nếu A khả nghịch mod m thì ( ) ( )1 1( ) ( )A A AA Iφ φ φ φ− −= = . Do φ là đẳng cấu vành nên ( )Aφ khả nghịch Nếu ( )Aφ khả nghịch thì tồn tại B sao cho ( ) ( ) ( ) ( )A B AB Iφ φ φ φ= = Vậy ta có A×B = I do đó A khả nghịch. Định lý 3: [7, 2.3.3] Số lượng ma trận vuông d×d trên ]m là (với 1 21 2 knn n km p p p= … ) ( ) ( )2 11 0 ( , ) i k d n d d j m i i i i j GL d p p p −− = ⎛ ⎞= −⎜ ⎟⎝ ⎠∏ ∏] (2.8) Chứng minh: Gọi A là ma trận vuơng khả nghịch trên m] ; thì ( )Aφ khả nghịch. Do φ là một đẳng cấu vành nên số lượng ma trận vuơng khả nghịch trên m] sẽ bằng với số lượng các vectơ của φ . Ta cĩ: ( ) ( )11 mod , , mod , , mod zi nnn i zA A p A p A pφ → … … Áp dụng định lý 2 thì từng thành phần mod iniA p có ( )2 1( 1) 0 i d n d d j i i j p p p −− = −∏ Vậy số vectơ của φ là: ( ) ( )2 11 0 i k d n d d j i i i i j p p p −− = ⎛ ⎞−⎜ ⎟⎝ ⎠∏ ∏ Ta có: ( ) ( )2 11 0 ( , ) i k d n d d j m i i i i j GL d p p p −− = ⎛ ⎞= −⎜ ⎟⎝ ⎠∏ ∏] „ 30  5.4. Không gian tốt nhất của Alphabet Định nghĩa Đặt tỷ số giữa tổng các ma trận vuông cấp d > 0 khả nghịch với tổng các ma trận vuông trên ]m , với m ≥ 2 là: ( , ) ( , ) ( ) m d d m GL d f d m M × = ]] (2.9) Ý nghĩa của f(d,m) sẽ cho ta con số đánh giá để chọn ra kích thước khóa và không gian Alphbet. Nếu ( ) ( )/ /, ,f d m f d m> thì ta nên chọn d, m tương ứng với d là kích thước khóa và m là lượng trong Alphabet. Bổ đề 4:[7, bổ đề 4.3] Nếu d là số nguyên dương và p là số nguyên tố thì ( ) 2 1 0 1 1 0 0 1 ( , ) ( , ) ( ) 1 = 1 1 d d i p i d d d p d i id d d d d j i i j p pGL d f d p M p p p p p p p − = × − − = = = − = = ⎛ ⎞ ⎛ ⎞ ⎛ ⎞− = − = −⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠⎝ ⎠ ⎝ ⎠ ∏ ∏ ∏ ∏ ] ] (2.10) Định lý 4:[7, định lý 4.4] Nếu d là số nguyên dương và m là số nguyên dương bất kỳ, 0 i k n i i m p = =∏ thì : ( ) 1 1 1, 1 k d j i j i f d m p= = ⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠∏∏ (2.11) 31  ( ) ( ) ( ) 2 2 2 2 2 2 2 2 1 ( 1) 1 0 1 1 0 1 1 0 1 ( , ) ( , ) ( ) = = i i i i i i k d n d d l i i i i lm k n dd d m i i k d n d d d l i i i i i l k n d i i d n d d d l k i i i i l n d i i p p p GL d f d m M p p p p p p p p p p p −− = = × −− = = = −− = = ⎛ ⎞−⎜ ⎟⎝ ⎠= = ⎛ ⎞−⎜ ⎟⎝ ⎠ ⎛ ⎞−⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ ∏ ∏ ∏ ∏ ∏ ∏ ∏∏ ] ] ( ) 2 1 0 1 1 1 1 = 1 d d l k k di i l jd i i j ii p p pp − = = = = ⎛ ⎞−⎜ ⎟ ⎛ ⎞⎜ ⎟ = −⎜ ⎟⎜ ⎟⎜ ⎟ ⎝ ⎠⎜ ⎟⎝ ⎠ ∏∏ ∏∏ (2.12) Nhận xét : Từ (2.12) ta thấy f(d,m) không phụ thuộc vào số mũ của thừa số nguyên tố trong phân tích thừa số nguyên tố của m (tức không phụ thuộc vào in ) Định lý 5:[7, định lý 4.6] Cho d là nguyên dương và p là số nguyên tố thì lim ( , ) 1 p f d p→∞ = (2.13) Chứng minh: Áp dụng bổ đề 4: 1 1lim ( , ) lim 1 lim1 1→∞ →∞ →∞= ⎛ ⎞= − = =⎜ ⎟⎝ ⎠∏ d jp p pj f d p p „ 32  Ta xét Hàm Zeta Riemann như sau: 1 1 1 1 1( ) 1 2 3s s s sk s k ζ ∞ = = = + + +∑ … (2.14) Với ( )1ζ = ∞ (2.15) Công thức tích Euler: (2.16) 1 1 1( ) 11 s k p prime s s k p ζ ∞ = − = = − ∑ ∏ 1 1 1 1 1 1 1 2 1 3 1 5 1s s s s sp prime p p− − − − − =− − − − −∏ " " ( ) 1 1 1 11 1s sp pp p sζ −∞ ∞ − ⎛ ⎞⎛ ⎞− = =⎜ ⎟⎜ ⎟ −⎝ ⎠ ⎝ ⎠∏ ∏   Áp dụng hàm Zeta Riemann và công thức Euler ta sẽ chứng minh lim ( , ) 0 k f d m →∞ = Định lý 6:[7, định lý 4.7] Cho d là số nguyên dương và m là số nguyên dương với 11 k nn km p p= … thì lim ( , ) 0 k f d m →∞ = Chứng minh: Từ định lý 4; (2.12) và ta xét 11= … knn km p p ; với k là số các số nguyên tố trong phân tích thừa số nguyên tố của m; ta có: 1 1 1 1 1lim ( , ) lim 1 1 = lim 1 k d jk k i j i d k jk j i i f d m p p →∞ →∞ = = →∞ = = ⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠ ⎛ ⎞−⎜ ⎟⎜ ⎟⎝ ⎠ ∏∏ ∏∏ (2.17) 33  Ta có: 1 1 1lim 1 ( ) k jk i ip jζ→∞ = ⎛ ⎞− =⎜ ⎟⎝ ⎠∏ (từ công thức tích Euler) Do đó: 1 1 1 1 1 2 1 1lim ( , ) lim 1 lim 1 1 1 1 = ( ) (1) ( ) d k d k j jk k k j i j ii i d d j j f d m p p j jζ ζ ζ →∞ →∞ →∞= = = = = = ⎛ ⎞ ⎛ ⎞= − = −⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ = ∏∏ ∏ ∏ ∏ ∏ (2.18) Theo (2.18) ta có (1)ζ = ∞ do đó 1 1 1lim 1 0 d k jk j i ip→∞ = = ⎛ ⎞− =⎜ ⎟⎜ ⎟⎝ ⎠∏∏ Vậy lim ( , ) 0 k f d m →∞ = nghĩa là k càng lớn thì số ma trận khả nghịch gần bằng 0. „ Ta xét các trường hợp sau: Xét f(10,n) với n là các giá trị trong khoảng 2 đến 29. Hình 2.1 34  Trong hình 2.1; với dấu . thì ta biểu diễn n là số nguyên tố trong khoảng từ 2 đến 29 và dấu + là các trường hợp còn lại trong khoảng từ 2 đến 29. Quan sát hình 2.1, ta thấy các trường hợp số nguyên tố thì f(10,p)luôn lớn hơn các trường hợp còn lại. Xét f(10,n) với n là các giá trị trong khoảng 29 đến 100 Hình 2.2 Với dấu . cho trường hợp f(10,29) và f(10,n) với n là các hợp số trong khoảng từ 30 đến 100. Quan sát hình 2.2 ta thấy f(10,n) và f(10,29) ta thấy f(10,29) luôn nằm trên f(10,n). Vậy khi chọn không gian cho Alphabet thì ta không cần chọn m quá lớn; và ta nên chọn là số nguyên tố. 35  Kết luận: - Không gian bảng chữ cái không cần phải lớn. - Bảng chữ cái nên có số lượng là một số nguyên tố. - Ta chỉ khảo sát và sinh khóa trên trường p]  với p là số nguyên tố. 6. Xét các trường hợp khóa yếu 6.1. Ma trận đối hợp (Involutory matrix) 6.1.1. Xây dựng ma trận đối hợp 6.1.1.1. Ma trận đối hợp trên trường ; 2p p >] Gọi H là ma trận đối hợp n × n trên trường p] , nghĩa là 2 nH I= nên H có thể là: 1. nI 2. nI− 3. r r s s r s I Z J Z I × × ⎛ ⎞= ⎜ ⎟−⎝ ⎠ Với ,0r s n s n+ = < < Định lý 7: (Theo [9]) Điều kiện cần và đủ để ma trận vuông H với kích thước n × n, trên trường ; 2>] p p với 0 < s < n, thì 2 2nH I Q P= − × là ma trận đối hợp với 2Q là ma trận n × s và 2P là ma trận s × n sao cho 2 2 2 sP Q I× = × (với s < n và hạng của 2P bằng s thì luơn tồn tại 2Q sao cho 2 2 2 sP Q I× = × ).Tương tự cho 1 1 nH Q P I= × − với 1Q là ma trận n × r và 1P là ma trận r × n sao cho 1 1 2 rP Q I× = × và r + s = n (với r < n và hạng của 1P bằng r thì luôn tồn tại 1 1 2 rP Q I× = × ) 36  Chứng minh Điều kiện cần. Ta đặt 1H Q J Q−= × × ; với Q là ma trận khả nghịch bất kỳ trên p] Ta đặt ( )/ /1 2Q Q Q= ; với /2Q là ma trận có kích thước n s× Và đặt 11 2 P Q P − ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; với 2P là ma trận có kích thước s n× ( ) 11 / / / /1 2 1 1 2 2 2 n P Q Q Q Q Q P Q P I P − ⎛ ⎞× = × = × + × =⎜ ⎟⎝ ⎠ (2.19) ( ) / /11 / / 1 1 1 21 2 / / 2 2 1 2 2 r r s s r s I ZP P Q P Q Q Q Q Q Z IP P Q P Q ×− × ⎛ ⎞× × ⎛ ⎞⎛ ⎞× = × = =⎜ ⎟ ⎜ ⎟⎜ ⎟ × ×⎝ ⎠ ⎝ ⎠⎝ ⎠ (2.20) ( ) ( ) 11 / / 1 2 2 1/ / / / 1 2 1 1 2 2 2 = r r s s r s I Z P H Q J Q Q Q Z I P P Q Q Q P Q P P ×− × ⎛ ⎞ ⎛ ⎞= × × = × ×⎜ ⎟ ⎜ ⎟− ⎝ ⎠⎝ ⎠ ⎛ ⎞− × = × − ×⎜ ⎟⎝ ⎠ 2.21) Từ (2.19),(2.21) ta có: /2 22nH I Q P= − × × Đặt /2 22Q Q= × Ta có: 2 2nH I Q P= − × Từ (2.20) ta có: /2 2 2 22 2 sP Q P Q I× = × × = × Trường hợp 1 1 nH Q P I= × − ta xét tương tự Điều kiện đủ: H×H=( 2 2nI Q P− × )×( 2 2nI Q P− × )= nI - 2 2Q P× - 2 2Q P× + 2 2Q P× 2 2Q P× × = nI -2 2 2Q P× × + 2 22 sQ I P× × × = nI „ Ví dụ: Ta xây dựng ma trận đối hợp trên 7] : 37  n=3; s=2 2 1 2 3 1 3 5 P ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; 2Q được xây dựng bằng cách giải hệđ 2 1 2 2 2 0 0 2 P X P X ⎧ ⎛ ⎞=⎪ ⎜ ⎟⎪ ⎝ ⎠⎨ ⎛ ⎞⎪ = ⎜ ⎟⎪ ⎝ ⎠⎩ với ( )2 1 2Q X X= Lần lượt giải các hệ ta được 1 6 5 5 a X a a +⎛ ⎞⎜ ⎟= +⎜ ⎟⎜ ⎟⎝ ⎠ với 7a∈] 2 3 2 5 b X b b +⎛ ⎞⎜ ⎟= +⎜ ⎟⎜ ⎟⎝ ⎠ với 7b∈] Với 1; 1a b= = thì 2 0 4 3 0 1 1 Q ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Ma trận đối hợp 1 0 0 0 4 1 0 0 4 5 6 4 2 1 1 2 3 0 1 0 3 0 0 1 0 3 6 2 4 2 5 1 3 5 0 0 1 1 1 0 0 1 2 5 1 5 2 0 H ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟= − = − =⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 6.1.1.2. Ma trận đối hợp trên trường 2] [Theo 9] Gọi H là ma trận đối hợp n × n trên trường F, có đặc số 2, nghĩa là 2 nH I= nên H có thể là: 1. nI 2. 2 2 2 r r s t s r s I Z J Z K × × ⎛ ⎞= ⎜ ⎟⎝ ⎠ 2sK là tổng trực tiếp của s ma trận 1 1 0 1 ⎛ ⎞⎜ ⎟⎝ ⎠ và 12 ;0 2 r s n s n+ = < ≤ 38  Định nghĩa tổng trực tiếp như sau: 0 0 A A B B ⎛ ⎞⊕ = ⎜ ⎟⎝ ⎠ Định lý 8: (Theo [9]) Nếu F là trường có đặc số 2, thì điều kiện cần và đủ để ma trận vuông nxn H là ma trận đối hợp với 10 2 s n< ≤ , 2 2nH I Q P= + × sao cho 2Q là ma trận n×s có hạng là s và ma trận 2P là ma trận s×n và có hạng là s sao cho 2 2 ,0s sP Q× = (do s < n nên luôn tồn tại 2Q sao cho 2 2 ,0s sP Q× = ) Chứng minh Điều kiện đủ: H×H = ( 2 2nI Q P+ × )×( 2 2nI Q P+ × )= nI + 2 2Q P× + 2 2Q P× + 2 2Q P× × 2 2Q P× = = nI +2 2 2Q P× × + 2 2Q P× × 2 2Q P× = nI + 2Q ,0s s× × 2P = nI Điều kiện cần: Ta đặt 11H Q J Q −= × × ; với Q là ma trận khả nghịch bất kỳ trên p] Ta đặt ( )/ /1 2Q Q Q= ; với /2Q là ma trận có kích thước 2n s× Và đặt / 1 1 / 2 P Q P − ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; với /2P là ma trận có kích thước 2s n× Ta có: ( ) /1 / / / / / /11 2 1 1 2 2/ 2 n P Q Q Q Q Q P Q P I P − ⎛ ⎞× = × = × + × =⎜ ⎟⎝ ⎠ (2.22) ( )/ / / / / 21 / /1 1 1 1 21 2/ / / / / 2 22 2 1 2 2 r r s n s r s I ZP P Q P Q Q Q Q Q I Z IP P Q P Q ×− × ⎛ ⎞ ⎛ ⎞× × ⎛ ⎞× = × = = =⎜ ⎟ ⎜ ⎟ ⎜ ⎟× × ⎝ ⎠⎝ ⎠ ⎝ ⎠ (2.23) 39  ( ) ( ) / 21 / / 1 1 1 2 / 2 2 2 / / / 1 1 2 2 / 2 / / / / 1 1 2 2 2 r r s s r s s s I Z P H Q J Q Q Q Z K P P Q Q K P Q P Q K P ×− × ⎛ ⎞⎛ ⎞= × × = × ×⎜ ⎟⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎛ ⎞= × ×⎜ ⎟⎝ ⎠ = × + × × (2.24) Từ (2.22) và (2.24), ta có: ( ) = − × + × × + × − × / / / / 2 2 2 2 2 / / 2 2 2 2 = n s n s s H I Q P Q K P I Q K I P Đặt ( )−= − = …2 2 2 .1 .3 .2 10, ,0, ,0, ,0,s s s sL K I i i u Với 0 là vectơ cột 0 và . ji là vectơ cột thứ j trong ma trận đơn vị. ( )−× = …/2 2 .1 .3 .2 10, ,0, ,0, ,0,s sQ L q q q với . jq là cột thứ j trong ma trận / 2Q ( )/ / /2 2 2 .1 .3 .2 1 2 .1 2. .3 4. .2 1 2 .0, ,0, ,0, ,0,s s s sQ K P q q q P q p q p q p− −× × = × = × + × + + ×… … Với .jp là dòng thứ j trong ma trận / 2P . Như vậy ta chỉ sử dụng cột lẻ trong /2Q và dòng chẵn trong / 2P . Ta đặt ( )× − × = ×/ /2 2 2 2 2 2s sQ K I P Q P Từ (2.23) ta có: 2 2 ,s sP Q Z× = vì dòng chẵn trong là vectơ 0 „ Ví dụ: Xây dựng ma trận đối hợp trên 2] : n=3; s=2 2 1 0 1 1 0 1 P ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; 2 Q được xây dựng bằng cách giải hệđ 40  2 1 2 2 0 0 0 0 P X P X ⎧ ⎛ ⎞=⎪ ⎜ ⎟⎪ ⎝ ⎠⎨ ⎛ ⎞⎪ = ⎜ ⎟⎪ ⎝ ⎠⎩ với ( )2 1 2Q X X= Lần lượt giải các hệ ta được 1 b X a b ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ với 8a∈] 2 d X c d ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ với 8,c d ∈] Với 1; 0, 1; 1a b c d= = = = thì 2 0 1 1 1 0 1 Q ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Ma trận đối hợp 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 H ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟= + = + =⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ Định lý 9: Cho hai ma trận A,B có kích thước lần lượt là r × s và s × r với các phần tử được chọn tùy ý trên vành giao hoán có đơn vị thì ma trận M có kích thước là n×n sao cho n= r+s thì M được xây dựng nhưng sau thì M là ma trận đối hợp: 2 s r BA I B M A ABA I AB −⎛ ⎞= ⎜ ⎟− −⎝ ⎠ (2.25) Định lý 10: (Về ma trận đối hợp) 1. A là ma trận đối hợp nếu và chỉ nếu 1A A−= 2. Nếu A là ma trận đối hợp thì ( )1 2 B I A= + là ma trận lũy đẳng. 41  3. Định thức của ma trận đối hợp A trên trường p] là 1 hoặc p –1 Chứng minh: 1. (⇒ ) A là ma trận đối hợp nên A.A = I . gọi A’ là ma trận nghịch đảo của A thì ta có A.A’=A’.A=I. do đó A=A’= 1A− (⇐) Ta có 1A A−= A. 1A− =I (định nghĩa) Suy ra A.A=I . Vậy A là ma trận đối hợp 2. B.B=( ( )1 2 I A+ )( ( )1 2 I A+ )= ( )21 4 I A+ ( ) ( ) ( )21 1 12 24 4 2I A A I A I A B+ + = + = + = „ Bổ đề 5 (vành ma trận) : Cho n là số nguyên lớn hơn hoặc bằng 1. Thì tập hợp các ma trận n×n có các phần tử trên trường p] với hai phép toán cộng và nhân ma trận tạo thành một vành. Bổ đề 6: A là ma trận đối hợp trên trường p] thì một số ma trận dễ thấy là các dạng sau : 1. In 2. (p–1)In 3. , , r r s s r s I Z J Z I ⎛ ⎞= ⎜ ⎟−⎝ ⎠ với r+s = n và 0 < s < n 42  4. ,21 2 , 2 r r s s r s I Z J Z K ⎛ ⎞= ⎜ ⎟⎝ ⎠ với r+2s = n và 0 < s ≤ 1 2 n và K2s là tổng trực tiếp của s ma trận 1 1 0 1 ⎛ ⎞⎜ ⎟⎝ ⎠ Nhận xét: Ma trận đối hợp trên trường ] p hoặc ]2 là ma trận tam giác trên với 1; p – 1 trên đường chéo chính và 1 hoặc 0 trong tất cả các phần tử phía trên đường chéo chính. Định thức của ma trận đối hợp A là bằng 1 hoặc p – 1 6.1.2. Đếm số ma trận đối hợp [Theo 6] Đếm số ma trận đối hợp (involutory) bậc d×d trên p] Đặt ( ) 0 t t i t i g p p = = −∏ là số ma trận khả nghịch bậc t trên trường p] Trường hợp p > 2 Đặt ( )0 ,N d t là số ma trận X cấp d × d thỏa 2 0X I− = Nếu X là ma trận có det(xI – X) có đa thức đặc trưng mà có t nghiệm là 1 và d – t nghiệm p–1 thì (mod ) M X J p≡ với J được định nghĩa trong 6.1.1.1 với 0 t d≤ ≤ Đặt ( )0 ,S d t là số ma trận X sao cho (mod )MX J p≡ Thì ( ) ( )0 0 0 , , = = ∑d t N d t S d t ; 0 t d≤ ≤ (do ma trận X trong ( )0 ,S d t là khác nhau) 43  Q là ma trận khả nghịch bậc m trên p] sao cho 1−× ×Q J Q ; thì ( )1 mod −× × ≡MQ J Q J p . Nếu 1−× × =Q J Q J thì Q J J Q× = × . Đặt ( )0 ,C d t là số ma trận Q sao cho thỏa Q và J giao hoán. Ta có: ( ) ( )0 0, ,dg C d t S d t= Do Q J J Q× = × nên ( )0 , t d tC d t g g −= Suy ra: ( ) ( )0 0, ,d dt d t g g S d t g gC d t − = = Do đó số ma trận đối hợp trên p] là: ( )0 0 0 1, = =− − = =∑ ∑d dd d t tt d t t d t gN d t g g g g g (2.26) Với ( )1 0 0 ; 1 t t i t i g p p g − = = − =∏ . „ Trường hợp p = 2 [Theo 6] Đặt X là ma trận cấp d×d; X là ma trận thỏa mãn: 2 0X I− = trên 2] . Tương tự trường hợp trên thì (mod ) M tX J p≡ với tJ được định nghĩa trong 6.1.1 phần b. Đặt ( ),eS d t là tổng số ma trận X sao cho (mod )M tX J p≡ với 0 2t d≤ ≤ Ta có: ( ) ( ) 0 , , = = ∑de e t N d t S d t ; 0 2≤ ≤t d (do ma trận X trong ( ),eS d t là khác nhau) Đặt ( ),eC d t là số lượng ma trận khả nghịch Q bậc d trên 2] thỏa mãn t tJ Q Q J× = × . Ta có: ( ) ( ), ,d e eg S d t C d t= Theo [10] ( ) ( )2 3 2, 2t m te t d tC d t g g− −= 44  Suy ra: ( ) (2 3 )2 0 2 2, ⎢ ⎥⎢ ⎥ − −⎣ ⎦ = − = ∑ d t d t e d t t d t N d t g g g (2.27) Với ( )1 0 0 ; 1 t t i t i g p p g − = = − =∏ Ta xét trường hợp f(d,29) với d trong khoảng 2 đến 30 Hình 2.3 Quan sát hình 2.3 ta thấy với khoảng d thay đổi từ 2 đến 30 thì các f(d,29) có xu hướng bằng nhau. Từ (2.26) và (2.5). Ta đặt g(t) tỷ số giữa tổng ma trận đối hợp trong (2.26) và tổng số ma trận khả nghịch trong (2.5);ta xét trên ] p : 0 0 1( ) d d d t t d t td t d t g g g g t g g g = − = − = = ∑ ∑ (2.28) 45  Với ( )1 0 0 ; 1 t t i t i g p p g − = = − =∏ Ý nghĩa của g(t) càng nhỏ thì càng tốt vì lúc đó sẽ có tỷ lệ khóa yếu là ít nhất. Ta xét trường hợp d trong khoảng từ 2 đến 5 Hình 2.4 Quan sát hình 2.4 ta thấy với d=2 lớn thì g(t)= 0.0012, còn d từ 3 trở lên thì g(t) càng tiến về 0. Như vậy khi sinh khóa thì kích thước khóa càng lớn thì tỷ lệ khóa yếu càng ít. 6.2. K là khóa yếu với K×v = v hoặc v×K = v: Ta xét khóa là ma trận vuông d×d khả nghịch trên p] 6.2.1. Xác định khóa yếu bằng định thức Với cách mã hóa: K×v = v thì K được gọi là khóa yếu. 46  ( ) ( ) 11 1 1 1 1 11 1 1 1 1 1 0 1 0 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟× = ⇔⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ − + + =⎧⎪⎨⎪ + + − =⎩ … # % # # # … … … … d d dd d d d d d dd d k k m m k k m m k m k m k m k m (2.29) det(K – I) ≠ 0 thì hệ (2.29) có nghiệm duy nhất là nghiệm tầm thường 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ # det(K – I) = 0 thì hệ (2.29) có vô số nghiệm hoặc vô nghiệm, nhưng do hệ luôn có nghiệm tầm thường nên khi det(K – I) = 0 thì hệ (2.29) vô số nghiệm. Nhưng do trên ] p có hữu hạn phần tử hệ (2.29) cũng có hữu hạn nghiệm. Ví dụ: Trên 11] 2 3 2 7 K ⎛ ⎞= ⎜ ⎟⎝ ⎠ , có det K ≠ 0 nhưng det(K – I) = 0 Véc tơ dạng 1 17 m v m ⎛ ⎞= ⎜ ⎟⎝ ⎠ với 1 11m ∈] thì Kv = v Thì 0 1 2 3 4 5 6 7 8 9 10 , , , , , , , , , , 0 7 3 10 6 2 9 5 1 8 4 v ⎧ ⎫⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞∈⎨ ⎬⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎩ ⎭ Do 11] hữu hạn phần tử nên v cũng thuộc tập nghiệm hữu hạn Nếu thông điệp M mà ta cần mã hóa sau khi chuyển thành dạng ma trận có các cột là các nghiệm trong tập trên thì K×M=M Với 2 9 7 3 8 5 M ⎛ ⎞= ⎜ ⎟⎝ ⎠ Thì khi mã hóa: 47  2 3 2 9 7 2 9 7 2 7 3 8 5 3 8 5 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠C K M Cipher text sẽ bằng plaintext; như vậy khi mã hóa khóa yếu như trên thì người ta sẽ biết được plaintext. Với cách mã hóa: v×K = v thì K được gọi là khóa yếu ( ) ( ) ( ) ( ) 11 1 1 1 1 11 1 1 1 1 1 0 1 0 ⎛ ⎞⎜ ⎟× = ⇔⎜ ⎟⎜ ⎟⎝ ⎠ − + + =⎧⎪⎨⎪ + + − =⎩ … … # % # … … … … … d d d d dd d d d dd d k k m m m m k k k m k m k m k m (2.30) det(KT – I) ≠ 0 thì hệ (2.30) có nghiệm duy nhất là nghiệm tầm thường. det(KT – I) = 0 thì hệ (2.30) có vô số nghiệm hoặc vô nghiệm, nhưng do hệ luôn có nghiệm tầm thường nên khi det(KT – I) = 0 thì hệ (2.30) có vô số nghiệm. Nhưng do trên ] p có hữu hạn phần tử hệ (2.30) cũng có hữu hạn nghiệm. Ta có nhận xét: 1/ Trên trường ] p với m là số nguyên dương thì một khóa K gọi là yếu khi và chỉ khi det ( K – I ) = 0 với cách mã K×v = v. 2/ Trên trường ] p với m là số nguyên dương thì một khóa K gọi là yếu khi và chỉ khi det ( KT – I ) = 0 với cách mã v×K = v 6.2.2. Xác định khóa yếu bằng trị riêng Định nghĩa: Cho A là ma trận vuông d×d và c ∈ p] Đặt { }/n T TcE X AX cX= ∈ =\ c được gọi là trị riêng và cE được gọi là không gian riêng ứng với trị riêng 48  Với mỗi { }\ 0cEα ∈ thì α là vec tơ riêng ứng với trị riêng c Ta đặt ( ) ( )detA nP x cI A= − gọi là đa thức đặc trưng của A Mệnh đề (Mối liên hệ giữa trị riêng và đa thức đặc trưng) Nếu c là trị riêng trên p] của A thì ( )AP c =0 trên p] Suy ra nếu muốn tìm trị riêng thì ta tìm tất cả các nghiệm của ( )AP x trên p] Tính chất của trị riêng và vectơ riêng: 1. Nếu c = 0 thì ma trận A không khả nghịch 2. Nếu A là ma trận tam giác trên và ma trận tam giác dưới, ma trận đường chéo thì trị riêng là nhưng phần tử trên đường chéo chính. 3. A và AT có cùng trị riêng. 4. Transition matrix thì luôn có trị riêng là 1 Trasition matrix có tính chất là tất cả các hàng có tổng là 1 Ví dụ: Xét ma trận có trị riêng là 1 trên 7] 1 2 5 4 4 0 3 2 3 A ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Ta tính trị riêng cho K ( ) 1 2 5 det 4 4 0 3 2 3 − − − − = − − − − − x xI K x x = 49  ( ) ( )( )( ) ( ) ( )( ) ( ) ( ) ( )( )( )3 2 2 4 0 4 0 4 4 = 1 2 5 2 3 3 3 3 2 = 1 4 3 8 3 5 8 3 4 = 4 4 1 4 1 1 2 2 − − − −− + −− − − − − − − − − − − − + − − − + = − − − = − − + x x x x x x x x x x x x x x x x x x x A có trị riêng là 1 Tìm v sao cho K×v = v ⇔ (K – I)×v = 0 á phé biê dơ so câ trê dị 0 2 5 0 1 1 5 0 4 3 0 0 0 2 5 0 3 2 2 0 0 0 0 0 c c p n i p n ng ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ Suy ra b v b b ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Nếu 2 3 2 3 2 3 M ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ 1 2 5 2 3 2 3 4 4 0 2 3 2 3 3 2 3 2 3 2 3 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟× = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ K M Ta có nhận xét: Nếu trị riêng ma trận vuông A có trị riêng là 1 thì tồn tại những vectơ riêng X sao cho × =T TK X X . Muốn tìm được XT thì ta phải giả hệ phương trình tuyến tính. Một khóa là ma trận khả nghịch nhưng không yếu thì ma trận có các giá trị riêng phải khác 1. Ở đây ta có thể xét một trường hợp là loại những ma trận Trasition matrix có tính chất là tất cả các hàng có tổng là 1. Ta xét định thức thì: det(K – I) ≠ 0 và det(KT – I) ≠ 0 50  7. Tóm tắt Mã ma trận bậc d khi ta mã hóa cần khóa là ma trận vuông khả nghịch trên m] , m bất kỳ. Ở đây không gian các chữ cái(Alphabet) là m nên là số nguyên tố và số chiều d của ma trận khóa nên lớn để hạn chế khóa yếu. Trường hợp các khóa yếu thì ta có ma trận đối hợp (involutory matrix) đối với trường hợp này thì khi ta xây dựng ma trận K = L × U thì ta chỉ cần xây dựng ma trận K sao detK ≠ 1 và p – 1 Trường hợp K×v = v thì ta xây dựng ma trận K có det(K – I) ≠ 0. 51  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] (1) 11 1 1 0 0 0 0 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … # % # % # # % … … … tt tt d dt dd l l L l l l l khả nghịch ⇔ ( ) 1 0 mod p = ≠∏d ii i l (3.1) (2) 11 1 1 0 0 0 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … … % # … % % … d tt tt td dd u u u u u U u khả nghịch ⇔ ( ) 1 0 mod p = ≠∏d ii i u (3.2) (3) K L U= × khả nghịch khi và chỉ khi L,U khả nghịch (3.3) (4) K khả nghịch ⇒ P×K cũng khả nghịch với P là ma trận hoán vị Với P là ma trận hoán vị được định nghĩa như sau: ( ) 1 2 nk k k P e e e= … với ik e là các hàng trong ma trận đơn vị. ( )ijP p= với 1 nếu 0 ngược lạiiij j kp ⎧ =⎪= ⎨⎪⎩ (3.4) 52  (5) 11 1 1 1 1 1 0 0 0 0 1 0 1 0 0 + + ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟= × = ×⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ … … … # % % # # … % % # # % % … … … … d tt tt td tt d dt dd u u u u u K L U l l l u (3.5) thì không tồn tại ma trận L1; U1 sao cho L≠L1(L1 là ma trận tam giác trên với đường chéo chính gồm các phần tử 1) và U≠U1 thì L×U=L1×U1 (6) Với ma trận K khả nghịch trên p] thì luôn tồn tại ma trận P, L,U (với ma trận L là ma trận tam giác trên sao cho các đường chéo chính là 1)khả nghịch trên p] sao cho K= P×L×U (theo [5, trang 153]) Chứng minh Chứng minh (5) Không tồn tại ma trận L1, U1 (với L1 là ma trận tam giác dưới có đường chéo chính là 1)sao cho L1≠L và U1≠U mà K = L1 × U1 Chứng minh: Ta xét trên p] ; với 1 1K L U= × . Ta giả sử ta có 2 2K L U= × Lúc này ta có 1 1 2 2L U L U× = × . Do K khả nghịch nên 1 2,U U khả nghịch. Ta có: 1 11 1 2 2 2 1 2 1L U L U L L U U − −× = × ⇔ × = × (3.6) Do 2L là ma trận tam giác dưới nên 1 2L − cũng là ma trận tam giác dưới. Suy ra 1 2 1L L − × là ma trận tam giác dưới. Tương tự thì 1U là ma trận tam giác trên nên 1 1U − là ma trận tam giác trên. Suy ra 12 1U U −× là ma trận tam giác trên. Từ (3.6) thì vế trái là ma trận tam giác dưới và vế phải là ma trận tam giác trên 53  1 12 1 2 1L L U U − −× = × = D (3.7) Với D là ma trận đường chéo. Do 12 1;L L − có các lii là 1 nên D là ma trận đơn vị. Từ (3.7) ta có: 1 12 1 2 1 dL L U U I − −× = × = (3.8) Từ (3.8) thì 2 1 2 1;= =L L U U „ Chứng minh (6) Với K là ma trận vuông cấp d khả nghịch trên p] ; thì K cũng khả nghịch trên\ . Theo [5, trang 153] thì tồn tại ma trận ( ), , ,P L U M d∈ \ sao cho K P L U= × × . Do K khả nghịch trên p] , nên P L U× × cũng khả nghịch trên p] ; suy ra L, U khả nghịch trên p] . Vậy với K khả nghịch trên p] thì tồn tại ma trận L, U khả nghịch trên p] sao cho K P L U= × × „ 2. Xác định cơ sở hình thành thuật giải Ta sinh ra hai ma trận L và U trên p] Với 1 1 1 0 0 1 0 1 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … # % # % # # % … … … tt d dt L l l l 54  11 1 1 0 0 0 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … … % # … % % … d tt tt td dd u u u u u U u Khóa K được tính như sau: 11 1 1 1 1 11 1 1 0 0 0 1 0 1 0 0 + + ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟= × = ×⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … … … # % # % # … % % # # % % … … … … … … # % # … # % # % # … … d tt tt td tt d dt dd tt tj jt d dd u u u u u K L U l l l u k k k k k k (3.9) Với ( ) ( ) ( ) 1 1 2 2 1 1 2 2 1 1 2 2 ⎧ + + + ⎪⎩ … … … i j i j ij ij i j i j ii i j i j ij jj l u l u u i j k l u l u u i j l u l u l u i j (3.10) Ta tính: 11 1 1 1 1 tt tj jt d dd k k k A K I k k k −⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟−= − = ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟−⎝ ⎠ … … # % # … # % # % # … … (3.11) 55  Với ( ) ( ) ( ) 1 1 2 2 1 1 2 2 1 1 2 2 1 ⎧ + + + ⎪⎩ … … … i j i j ij ij i j i j ii i j i j ij jj l u l u u i j a l u l u u i j l u l u l u i j (3.12) Ma trận U phải khả nghịch: 11 1 0 d i u = ≠∏ Để ma trận khóa K không là khóa yếu thì ma trận khóa K phải thỏa là: K không là ma trận đối hợp (Involutory matrix) nghĩa là 11 1 1 và 1 d i u p = ≠ −∏ Đối với trường hợp khóa yếu K v v× = thì ta xét det(K – I) phải khác 0. Với mục (5) trong phần 1 của chương này thì với một bộ (L,U) sẽ có một khóa K nên khi ta xác định tổng số khóa K có thể sinh ra bằng thuật giải thì bằng số lượng ma trận L nhân với số lượng ma trận U. Với mục (6) của phần 1 của chương này thì ta có nhận xét là với K khả nghịch thì ta luôn có K = P × L ×U nên không gian khóa mà ta sinh bằng bộ L×U thì đảm bảo không gian sinh ra gần bằng không gian ma trận vuông khả nghịch. 3. Thuật giải: Ta phải xác định trước p] với p là số nguyên tố; là không gian bảng các chữ cái. Bước 1: Ta sẽ phát sinh ma trận tam giác trên U sao cho U phải thỏa một số tính chất sau: U phải khả nghịch nghĩa là: 1 0 d ii i u = ≠∏ det(K) ≠ 1 và p – 1 nghĩa là: det(U) ≠ 1 và p – 1 ⇔ 1 1 và 1 d ii i u p = ≠ −∏ 56  Bước 2 : Ta sẽ phát sinh ma trận tam giác dưới L sao cho các phần tử trên đường chéo chính bằng 1. Bước 3 : Ta tính khóa K L U= × Bước 4: Tính det(K – I). Nếu det(K – I) = 0 thì ta quay lại bước 2 tính lại ma trận L. Nếu det(K – I) ≠ 0 thì ta tiếp bước 5. Bước 5: Ta sẽ hoán vị khóa K để khóa K trở nên an toàn hơn mớiK P K= × Với P là ma trận hoán vị. 4. Ví dụ: Ta xét trên trường 29] ; ta sẽ sinh khóa có bậc là 4 Bước 1: Ta sinh ma trận tam giác dưới L bất kỳ sao cho các đường chéo chính bằng 1. 1 0 0 0 2 1 0 0 6 4 1 0 5 3 0 1 ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ L Bước 2: Ta phát sinh ma trận tam giác trên U bất kỳ khả nghịch và thỏa: 4 1 0;1;28ii i u = ≠∏ 57  5 2 1 2 0 3 2 5 0 0 1 1 0 0 0 1 U ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Bước 3: Tính khóa K 1 0 0 0 5 2 1 2 5 2 1 2 2 1 0 0 0 3 2 5 10 7 4 9 6 4 1 0 0 0 1 1 1 24 15 4 5 3 0 1 0 0 0 1 25 19 11 26 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ K L U Bước 4: Kiểm tra K có là khóa yếu không? Tính : det (K – I) =18 ≠ 0 Nên K là khóa mà ta chấp nhận được (không yếu) Chấp nhận là khóa và chuyển sang bước 5. Bước 5: Ta có thể hoán vị ma trận khóa vừa phát sinh Ví dụ: 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 P ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Như vậy khóa mới là: mới 0 1 0 0 5 2 1 2 10 7 4 9 0 0 0 1 10 7 4 9 25 19 11 26 1 0 0 0 1 24 15 4 5 2 1 2 0 0 1 0 25 19 11 26 1 24 15 4 K P K ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 58  5. Khảo sát không gian khóa vừa sinh theo thuật giải Ta xét trên p] với p là số nguyên tố Ta sinh khóa K là ma trận vuông khả nghịch d×d Số ma trận khả nghịch trên p] là : ( )1 0 p d i i p p − = −∏ Số ma trận involutory: Trường hợp p > 2 0 d d t t d t g g g= − ⎛ ⎞⎜ ⎟⎝ ⎠∑ Với ( ) ( )2 1 1 0 1 t t t i t i t i i g p p p p −− = = = − = −∏ ∏ và 0 1g = Trường hợp p = 2 (2 3 )2 0 2 2 d t d t d t t d t g g g ⎢ ⎥⎢ ⎥ − −⎣ ⎦ = − ∑ Như vậy số ma trận khóa là số ma trận khả nghịch trên p] trừ đi số ma trận khóa yếu. Ma trận tam giác dưới L và ma trận tam giác trên U bậc d có ( )1 2 d d + có thể khác 0. Theo thuật giải trên thì số ma trận tam giác dưới L là ( )1 2 d d d p + − (3.13) Theo thuật giải trên thì số ma trận U, khi ta xây dựng thì trên đường chéo chính có d – 1 phần tử chọn sao cho khác 0. Phần tử udd sẽ phụ thuộc các phần tử trước sao cho tích các đường chéo chính khác 1. Vậy ta có ( ) 11 dp −− cách chọn phần tử trên đường chéo chính. Các phần tử còn lại chọn bất kỳ nên ta có: 59  ( )1 2 d d d p + − cách chọn. Vậy số ma trận tam giác trên U là: ( ) ( )11 21 d d ddp p + −−− (3.14) Vậy số lượng ma trận khóa K = L × U có thể là: ( ) ( ) ( ) ( ) 21 11 12 21 1d d d dd dd d d dp p p p p+ +− −− − −− = − (3.15) 60  Chương 4: CÁC VẤN ĐỀ LIÊN QUAN ĐẾN Mà HILL Mô tả: Người A và người B trao đổi thông tin cho nhau; sử dụng mã hóa đối xứng và cụ thể là mã ma trận. A và B sẽ có khóa bí mật là ma trận; và áp dụng thuật toán mã hóa theo ma trận để mã hóa thông điệp M và chuyển cho B. B sẽ sử dụng khóa bí mật để giải mã và tính toán được M. 1. Sinh khóa theo pincodes Hình 4.1 Người gửi A sẽ có một pin codes và dùng pin codes để sinh ra khóa bí mật là ma trận K. Người A sẽ dùng khóa K để mã hóa thông điệp C = K × M. Người nhận B cũng có pincodes và cũng dùng pincodes để sinh ra khóa là ma trận K. Và dùng khóa K để tính M = K-1 × C. Thuật toán: sinh hóa từ pincodes và mã hóa bằng mã ma trận Cho trước pincodes S có chiều dài xác định trước. Thông điệp         M  Người gửi          A  Sinh Khóa K Sinh khĩa K   Theo pin codes  Người nhận B         Mã hĩa Thông điệp M  C= K × M Sinh khĩa K   Theo pin codes  Thông điệp         M = K‐1×  C  61  Thuật toán sinh khóa K là tích của ma trận tam giác dưới L và ma trận tam giác trên U có kích thước là d × d Gọi f là hàm băm (hash). Bảng chữ cái (Alphabet) A B C D E F G H I J K L M N O 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 P Q R S T U V W X Y Z . ? ∪ 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Thuật toán: Ta sẽ áp dụng bảng chữ cái để chuyển từ chữ sang số; trong trường hợp là số thì chính là giá trị của số đó; chỉ có trường hợp số 0 ta chuyển thành số 10. Như vậy chỉ có trường hợp duy nhất là A hay a thì chuyển thành 0. Sinh khóa K Bước 1: Dùng hàm băm f để tính giá trị t:=f(S): Ma trận U có ( )1 2 d d + phần tử cần tính toán Ta tính: ( ) ( )1 1: ( ) 2 2* ( ) + +⎡ ⎤ ⎡ ⎤= =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ d d d d length t a length t Nếu 1a > ; thì Lần 1 ta sẽ tính t:=f(S) Lần 2 Ta tính: S:= S+t và tính t:= t + f(S) Và tương tự như như vậy lập lại a lần. Bước 2: Tính ma trận L: 62  Ta sẽ gán các phần tử đường chéo chính: 11 22 33, , , , ddl l l l… các giá trị là 1. for i from 1 to d do L[i][i]:=1; end do; Duyệt chuỗi t sau khi chuyển sang số và gán cho các giá trị cho lij với i > j k:=0; for i from 2 to d do for j from 1 to i do L[i][j]:=t[k]; k:=k+1; end do; end do; Bước 3: Tính ma trận U: Gán các phần tử trên đường chéo chính khác 0 và chọn udd sao cho 1 0 1; 1 d ii dd i u u p − = ⎛ ⎞ ≠ −⎜ ⎟⎝ ⎠∏ Duyệt chuỗi t ngược từ cuối chuỗi sang đầu chuỗi. Gán các phần tử u11;….;ud-1d-1 sao cho các uii đó khác 0. k:==length(t); S:=1; for i:= 1 from d – 1 do 63  U[i][i]:=t[k]; k:=k-1; if U[i][i]=0 then U[i][i]:= U[i][i]+1; end if; S:=S*U[i][i] mod p; end do; U[d][d]:=t[k]; k:=k – 1; if(S*U[d][d]=1) or (S* U[d][d]=p – 1) then U[d][d]:= U[d][d]+1; end if; Gán các phần tử bất kỳ trong t (duyệt ngược chuỗi t)cho uij for j from 1 to d – 1 do for i from j+1 to d do U[i][j]:=t[k]; k:=k – 1; end do; end do; Bước 4: Tính khóa K: K:= L × U; Tính det(K – I); Nếu det(K – I ) = 0 thì lập lại bước 1 với pincodes S:= S +f(S); Ngược lại chuyển sang bước 5. Bước 5: Chuyển thông điệp thành dạng ma trận Chuyển các ký tự trong thông điệp M thành dạng số. 64  Tính ( ):β = −length M d ; Nếu 0β = thì thông điệp sẽ là ma trận dạng d×1 Nếu 0β > thì thêm ( ) ( )⎡ ⎤ −⎢ ⎥⎢ ⎥ length Md length M d khoảng trắng vào cuối M; lúc này ma trận thông điệp dạng ( )⎡ ⎤× ⎢ ⎥⎢ ⎥ length Md d . Nếu 0β < thì thêm β khoảng trắng vào cuối M; thông điệp là ma trận dạng d×1. Tạo thông điệp thành ma trận và chuyển sang số. Bước 6: Tiến hành mã hóa M và gửi cho B: C = K × M; Bước 7: Gởi C (Ciphertext) cho người B; Tại người B có pincodes và sinh ma trận khóa K tương tự các bước 1,2,3,4. Tính nhanh ma trận K-1 (phần 4 Chương 4). Giải mã và tính thông điệp M M = K-1 × C; Tính toán ngược lại thông điệp M: k:=1; for i from 1 to d for j from 1 to d m[k]:= M[i][j]; k:=k+1; od; od; 65  Chuyển ngược từ số sang chữ cái dưa vào bảng Alphabet. Người B đã có được thông điệp của người A 2. Cách tấn công mã Hill gốc Hình 4.2 Trường hợp 1: Ta mã hóa: ta có khóa K là ma trận vuông khả nghịch bậc d; và M là ma trận thông điệp; M có số chiều là d×m nếu thông điệp M không đủ d×m thì ta thêm các khoảng trắng cho đủ d×m. Nhưng trong trường hợp thông điệp M có số m = d thì M là ma trận vuông. Như vậy nếu như ta mã hóa thông điệp M = Id C = K × M = K × Id = K Như vậy khi mã hóa như trên thì ta sẽ tính được khóa K và như vậy khóa K không còn an toàn nữa. Trường hợp 2: Ta có ma trận khóa K có kích thước d×d Ta có d vectơ 1, dp p… (d × 1); các plaintext cần mã hóa thì ta thu được d vectơ các ciphertext 1, dc c… (d × 1). Như vậy ta có: ( ) ( )1 1d dp p K c c× =… … . Thông điệp         M  Người gửi          A  Sinh Khĩa K  Sinh khĩa K   Theo pin codes  Người nhận B         Mã hĩa Thông điệp M    C= K ×  M   Sinh khĩa K   Theo pin codes  Thông điệp         M = K‐1× C         Cipher text  66  Như vậy khóa K được tính dễ dàng: ( ) ( )11 1d dK p p c c−= ×… … 3. Cải tiến thuật giải (sinh khóa từ pincodes và chuỗi ngẫu nhiên) Đối với thông điệp có kích thước nhỏ hơn d×(d – 1) Hình 4.3 Người gửi A và người nhận B có chung pincodes. Thuật toán được cải tiến bằng cách thêm chuỗi ngẫu nhiên u. Tại người gửi A: Bước 1: Sinh chuỗi u ngẫu nhiên; kết hợp pincodes đã có với u thành pincodes mới . Bước 2: Từ pincodes mới sinh ra ma trận khóa K như trong phần 1 chương 4. Bước 3: Tính C = K × M Bước 4: Gửi cho người B : C và u. Tại người nhận B: Bước 1: Tính pincodes mới = pincodes + u Bước 2: Từ pincodes mới tính ma trận khóa K như trong phần 1 chương 4. Bước 3: Giải mã tìm thông điệp M: Sinh chuỗi t bất kỳ; Kết hợp pincodes với t bất kỳ Pin codes mới = pincodes + u Thông điệp         M  Người gửi          A  Sinh Khóa K theo Pin codes mới Người nhận B         Mã hĩa Thông điệp M    C= K ×  M  Chuỗi ngẫu nhiên u   Thông điệp         M = K‐1×  C  Nhận được chuỗi u. Tính Pin codes mới = pincodes + u 67  M = K-1 × C Cải tiến thuật toán ở đây là khóa K dùng để mã hóa luôn thay đổi trong mỗi lần mã hóa. Dù ai đó có tính toán được khóa trong một lần mã hóa và giữa để giải mã thông điệp khi bắt được cipher thì không được vì lần mã hóa tiếp theo khóa K cũng đã thay đổi vì chuỗi u được sinh ra là ngẫu nhiên. Như vậy thì giải quyết được trường hợp 2 trong phần 2 (tấn công mã Hill gốc) do d lần mã hóa các vectơ 1, dp p… với d khóa K khác nhau. Nếu M là ma trận đơn vị thì chỉ biết được khóa K và chuỗi ngẫu nhiên u của lần mã hóa đó mà những lần mã hóa khác thì K và u đã thay đổi; như vậy giải quyết trường hợp 1 trong phần 2 (tấn công mã Hill gốc) Đối với thông điệp có kích thước lớn hơn d×(d – 1) Hình 4.4 Tại người A: Chia thông điệp thành k khối mỗi khối có kích thước d×(d – 1); riêng khối k có thể có kích thước nhỏ hơn d×(d – 1). Thông điệp         M  Sinh chuỗi t bất kỳ; Kết hợp pincodes với ui bất kỳ Pin codes mới thứ i= pincodes + ui Người gửi          A  Sinh Khóa Ki theo Pin codes mới Người nhận B         Mã hĩa Thông điệp M    Ci= Ki ×  Mi  Chuỗi ngẫu nhiên ui   Thông điệp         Mi = Ki ‐1×  Ci  Nhận được chuỗi ui. Tính Pin codes mới thứ i = pincodes + ui M=ΣMi  Thông điệp M được chia thành k khối;k – 1 khối có kích thước d×(d – 1); khối k có thể có kích thước nhỏ hơn d×(d – 1) 68  Người A tiến hành mã hóa từng khối tương tự như trong trường hợp mã hóa thông điệp có kích thước nhỏ hơn d×(d – 1) và gửi cho người B. Tại người B: Người B nhận từng khối và tiến hành giải mã từng khối tương tự như trường hợp ở trên. Sau đó ghép các khối lại sẽ có thông điệp ban đầu. Do ta mã hóa từng khối có kích thước nhỏ hơn d×(d – 1) nên sẽ tránh được trường hợp chọn trước văn bản để mã(choosen plaintext). 4. Tính nhanh ma trận khả nghịch của khóa: 1 1 1K U L− − −= × Theo thuật toán ta sinh ma trận K L U= × K khả nghịch; L là ma trận tam giác dưới khả nghịch và U là ma trận tam giác trên khả nghịch. Ma trận K,L,U là ma trận vuông cấp d × d trên p] . Ta đặt ( )1 .1 .nK k k− = … thì ki là nghiệm của hệ phương trình Thì các .ik (vectơ cột) là nghiệm của hệ . .i iK k I× = với .iI là vectơ cột với vị trí thứ i là 1 còn lại là 0. Mà . . . .i i i iK k I L U k I× = ⇔ × × = Ta đặt: . .i i i iU k Y L Y I× = ⇒ × = Nghĩa là ta giải hệ phương trình sau: . i i i i L Y I U k Y × =⎧⎨ × =⎩ Ta gọi: 1i i di Y Y Y ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ # và ta sẽ giải hệ phương trình: 69  1 1 1 1 0 0 0 1 0 0 1 0 1 0 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟× = ⇔ × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎝ ⎠⎝ ⎠ ⎝ ⎠ … # % # # # … … % # # … i i ii i i d di Y l Y L Y I l Y 1 1 2 21 1 2 1 1 2 2 1 1 11 1 12 2 1 1 2 2 21 1 22 2 2 1 2 1 1 2 1 1 2 2 0 0 0 0 1 1 0 0 0 + + + + + + + + + + + + + + + ==⎧ =⎪ + =⎪⎪ =⎪ + + + =⎪ = −⇔ ⇔⎨ + + + =⎪ = −⎪ + + + + =⎪⎪⎪ + + + =⎩ ## … … … # … i i i i i ii i i i i ii i i i i i i i i i i ii i i i i i i i i i i i i ii i i i i i d i d i di Y Y Y l Y Y Y l Y l Y Y Y l l Y l Y l Y Y Y l l l Y l Y l Y l Y Y l Y l Y Y 1 2 1 + + − = ⎧⎪⎪⎪⎪⎪⎪⎨⎪ −⎪⎪⎪ ⎛ ⎞⎪ = −⎜ ⎟⎪ ⎝ ⎠⎩ ∑ # i i i i d di dj ji j i l Y l Y Ta xét hệ phương trình: 11 12 1 1 22 1 0 0 0 1. 0 0 0 − = ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟× = ⇔ × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎛ ⎞⎜ ⎟⎜ ⎟ ⎜ ⎟ −⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎜ ⎟⎝ ⎠⎝ ⎠∑ … ## # # … % # … # #% # … d i i i ii ii d dd di dj ji j i u u u k u U k Y u k u k l Y 70  ( ) 1 2 1 1 1 ( 1) 1 ( 1)( 1) 1 1 1 1 1 1 1 1 1 1 11 d di di dj ji j idd dd d d d i d i d d di dj ji dj ji d d j i j id d dd d d d ii ij ji j i ii d i i ij ji j i k Y l Y u u k Y u k l Y l Y u u u u k u k u k u k − = − − − − − − = =− − − − − = + − = ⎛ ⎞= = −⎜ ⎟⎝ ⎠ ⎡ ⎤⎛ ⎞⎛ ⎞ ⎛ ⎞⎡ ⎤= − = − − −⎢ ⎥⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟⎣ ⎦ ⎢ ⎥⎝ ⎠ ⎝ ⎠⎝ ⎠⎣ ⎦ ⎡ ⎤⇔ = −⎢ ⎥⎣ ⎦ = − ∑ ∑ ∑ ∑ ∑ # 1 1 2 1 1 1 i i d i ij ji j i u k u k u − = ⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪ ⎛ ⎞⎪ ⎜ ⎟⎪ ⎝ ⎠⎪⎪⎪ ⎛ ⎞⎪ = −⎜ ⎟⎪ ⎝ ⎠⎩ ∑ # Như vậy ta có thể tính nhanh ma trận nghịch đảo của K từ L × U. Với ( )1 .iK k− = với .ik là vectơ cột 2 1 1 1 11 . 1 1 2 1 1 1 1 1 1 11 1 1 d ij ji j i di ij ji j i i i di i ij jii ii j i ii d i d d di dj ji dj ji d d j i j i dd d d dj u k u k u k u k u kk k u k k l Y l Y u u u l Y = = − −− = + − − − −= = − − ⎛ ⎞−⎜ ⎟⎝ ⎠ ⎛ ⎞ ⎛ ⎞⎜ ⎟ −⎜ ⎟⎜ ⎟ ⎝ ⎠⎜ ⎟ ⎡ ⎤⎜ ⎟ −= = ⎢ ⎥⎜ ⎟ ⎣ ⎦⎜ ⎟⎜ ⎟⎜ ⎟ ⎡ ⎤⎛ ⎞⎛ ⎞ ⎛ ⎞⎜ ⎟ − − −⎢ ⎥⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎢ ⎥⎝ ⎠⎣ ⎦ − ∑ ∑ ∑ ∑ ∑ # # # # 1 1d ji j i ddu − = ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠⎝ ⎠∑ 71  KẾT LUẬN VÀ KIẾN NGHỊ Luận văn đã tập trung khảo sát về mã Ma trận; và khảo sát không gian khóa và đưa ra được tỷ số f(d,m) để đánh giá chọn không gian khóa và không gian Alphabet sao cho tốt nhất. Theo luận văn thì không gian Alphabet tốt nhất thì m(kích thước không gian Alphabet) nên là số nguyên tố. Luận văn cũng đã đưa ra thuật giải sinh khóa, với khóa K = L×U an toàn với L là ma trận tam giác dưới với các phần từ trên đường chéo chính bằng 1 và U là ma trận tam giác trên khả nghịch. Luận văn cũng đưa cải tiến cho mã Ma trận là thêm chuỗi ngẫu nhiên u khi mã hóa để khóa K thay đổi trong những lần mã hóa khác nhau. Và đề xuất khi mã hóa thông điệp thì nên chọn thông điệp có kích thước nhỏ hơn d×(d – 1); với d là kích thước khóa. Tuy nhiên trong luận văn cũng còn nhiều thiếu sót và trong thuật toán sinh khóa K = L×U thì không loại bỏ trực tiếp khóa yếu (K×v=v) mà chỉ loại bỏ được (K là ma trận đối hợp.). Kiến nghị tìm điều kiện L, U sao cho khi tính L×U thì loại bỏ trường hợp khóa yếu là det(L×U – I)≠0 72  TÀI LIỆU THAM KHẢO Key word Hill cipher, Matrix Modular, General Matrix. Tiếng Việt: [1] Dương Anh Đức, Trần Minh Triết (2005), Mã hóa và ứng dụng, Nhà xuất bản Đại học Quốc Gia TPHCM, Thành Phố Hồ Chí Minh. [2] Bùi Xuân Hải, Trần Nam Dũng, Trịnh Thanh Đèo, Thái Minh Đường, Trần Ngọc Hội (2001), Đại số tuyến tính, Nhà xuất bản Đại học Quốc Gia TPHCM, Thành Phố Hồ Chí Minh. [3] Hà Huy Khoái (2003), Mã hóa thông tin cơ sở toán học và ứng dụng, Bộ sách toán cao cấp – Viện Toán Học, Hà Nội [4] Nguyễn Đình Thúc, Bùi Doãn Khanh (2006), Mã hóa – Mật mã, Nhà Xuất Bản Lao Động Xã Hội, Thành Phố Hồ Chí Minh. Tiếng Anh: [5] Carl D Meyer (2000), “Matrix Analysis & Applied Linear Algebra”. [6] Hodges, J. (1958), “The Matrix Equation X2 – I = 0 over a Finite Field”, American Math. Monthly, 65, pp. 518 – 520. 73  [7] Jeffrey Overbey, William Traves, and Jerzy Wojdylo (2005), “On the Keyspace of the Hill Cipher”, Cryptologia, 29(1), pp. 59 – 72. [8] Levine, J., and R.R. Korfhage (1964), “Automorphisms of Abelian Groups Induced by Involutory Matrices, General Modulus”, Duke Math J, 31, pp.631 - 654. [9] Levine, J., and H.M. Nahikian (1962), “On the Construction of Involutory Matrices”, American. Math. Monthly, 69,pp. 267 – 272 . [10] Murray Eisenberg (1999), “Hill Cipher and Modular Linear Algebra”, Mimeographed notes, University of Massachusetts, 19 pages . [11] Tran Ngoc Bao, Nguyen Dinh Thuc (2008), “Modular Matrix Cipher and Its application in Authentication Protocol”, The IEEE 9th ACIS International Conference on Software Engineering, Artifical Intelligence, Networking and Parallel/ Distributed Computing, pp 318 – 323. 74  PHỤ LỤC DEMO THUẬT TOÁN CHƯƠNG 4 BẰNG MAPLE // Khai báo thư viện with(StringTools); with(inttrans); with(Maplets); with(linalg); with(LinearAlgebra); //Viết hàm chuyển đổi từ chữ sang số (trường hợp là số thì giữ nguyên; số 0 chuyển thành số 10) chuyensangso := proc (s) if s = "a" or s = "A" then return 0 end if; if s = "b" or s = "B" then return 1 end if; if s = "c" or s = "C" then return 2 end if; if s = "d" or s = "D" then return 3 end if; if s = "e" or s = "E" then return 4 end if; if s = "f" or s = "F" then return 5 end if; if s = "g" or s = "G" then return 6 end if; if s = "h" or s = "H" then return 7 end if; if s = "i" or s = "I" then return 8 end if; if s = "j" or s = "J" then return 9 end if; if s = "k" or s = "K" then return 10 end if; if s = "l" or s = "L" then return 11 end if; if s = "m" or s = "M" then return 12 end if; 75  if s = "n" or s = "N" then return 13 end if; if s = "o" or s = "O" then return 14 end if; if s = "p" or s = "P" then return 15 end if; if s = "q" or s = "Q" then return 16 end if; if s = "r" or s = "R" then return 17 end if; if s = "s" or s = "S" then return 18 end if; if s = "t" or s = "T" then return 19 end if; if s = "u" or s = "U" then return 20 end if; if s = "v" or s = "V" then return 21 end if; if s = "w" or s = "W" then return 22 end if; if s = "x" or s = "X" then return 23 end if; if s = "y" or s = "Y" then return 24 end if; if s = "z" or s = "Z" then return 25 end if; if s = "." then return 26 end if; if s = "?" then return 27 end if; if s = " " then return 28 end if; if s = "1" then return 1 end if; if s = "2" then return 2 end if; if s = "3" then return 3 end if; if s = "4" then return 4 end if; if s = "5" then return 5 end if; if s = "6" then return 6 end if; if s = "7" then return 7 end if; if s = "8" then return 8 end if; if s = "9" then return 9 end if; if s = "0" then return 10 end if; 76  end proc; // Viết hàm chuyển từ số thành chữ(trong ví dụ này chỉ mã hóa chữ không mã hóa số) chuyensangchu := proc (t) if t = 0 then return "A" end if; if t = 1 then return "B" end if; if t = 2 then return "C" end if; if t = 3 then return "D" end if; if t = 4 then return "E" end if; if t = 5 then return "F" end if; if t = 6 then return "G" end if; if t = 7 then return "H" end if; if t = 8 then return "I" end if; if t = 9 then return "J" end if; if t = 10 then return "K" end if; if t = 11 then return "L" end if; if t = 12 then return "M" end if; if t = 13 then return "N" end if; if t = 14 then return "O" end if; if t = 15 then return "P" end if; if t = 16 then return "Q" end if; if t = 17 then return "R" end if; if t = 18 then return "S" end if; if t = 19 then return "T" end if; if t = 20 then return "U" end if; 77  if t = 21 then return "V" end if; if t = 22 then return "W" end if; if t = 23 then return "X" end if; if t = 24 then return "Y" end if; if t = 25 then return "Z" end if; if t = 26 then return "." end if; if t = 27 then return "?" end if; if t = 28 then return " " end if ; end proc; //Sinh chuỗi ngẫu nhiên có chiều dài d sinhchuoingaunhien := proc (d) return Random(d, 'upper') end proc; // Số lần lặp hàm băm pinccodes đủ để tạo ma trận d × d solanlapdesinhchuoitupincodes := proc (d) local temp; temp := iquo(d*(d+1), 64); if temp < 1 then return 1 else temp+1; end if; end proc; // Hàm băm pincodes với số lần được tính ở trên hambampincodestaomatran := proc (d, pincodes) local t, i, S; if solanlapdesinhchuoitupincodes(d) = 1 then return Hash(pincodes) else t := Hash(pincodes); 78  for i to solanlapdesinhchuoitupincodes(d) do S := cat(S, t); t := cat(t, Hash(S)) end do; return t; end if; end proc; //Tạo ma trận tam giác dưới L taomatrantamgiacduoi := proc (d, S, p) local i, j, k, T; T := Matrix(d); for j to d do T[j, j] := 1; end do; k := 1; for i from 2 to d do for j to i-1 do k := k+1; T[i, j] := chuyensangso(S[k]); end do; end do; return T mod p; end proc; L := taomatrantamgiacduoi(10, hambampincodestaomatran(10, "thanhDMZUEVXNZNRUOZYPUSJE"), 31); 79  //Tạo ma trận tam giác trên U taomatrantamgiactren := proc (d, S, p) local i, j, k, U, V, T; U := Matrix(d); k := length(S); T := 1; for i to d-1 do U[i, i] := chuyensangso(S[k]); k := k-1; if U[i, i] = 0 then U[i, i] := U[i, i]+1 end if; T := T*U[i, i] end do; U[d, d] := chuyensangso(S[k]); k := k-1; while T*U[d, d] = 1 or T*U[d, d] = p-1 do U[d, d] := U[d, d]+1 end do; for i to d-1 do for j from i+1 to d do U[i, j] := chuyensangso(S[k]); k := k-1 80  end do end do; return U mod p end proc; U := taomatrantamgiactren(10, hambampincodestaomatran(10, "thanhE"), 29); //Sinh Khóa K Sinhkhoa := proc (d, pincodes, p) local L, U, K; L := taomatrantamgiacduoi(d, hambampincodestaomatran(d, pincodes), p); U := taomatrantamgiactren(d, hambampincodestaomatran(d, pincodes), p); K := `mod`(MatrixMatrixMultiply(L, U), p); while det(K-Indentity(d)) = 0 do pincodes := cat(pincodes, "1"); L := taomatrantamgiacduoi(d, hambampincodestaomatran(d, pincodes), p); U := taomatrantamgiactren(d, hambampincodestaomatran(d, pincodes), p); K := `mod`(MatrixMatrixMultiply(L, U), p); 81  end do; return K end proc; K := Sinhkhoa(10, "thanh", 29);print(); //Người A tiến hành mã hóa và gởi cho B nguoiAgui := proc (Message, d, pincodes) local kq, a, i, M, j, K, p, l, b, X, Messagenew; a := iquo(length(Message), d); b:=0; c:=length(Message) – d; if c<0 then b:=abs(c); else b:=(a+1).d – length(Message); end if; X := Random(b, " "); Messagenew := cat(Message, X); a := iquo(length(Messagenew), d); M := Matrix(d, a); 82  l := 1; p := 29; for i to d do for j to a do M[i, j] := chuyensangso(Messagenew[l]); l := l+1; end do; end do; K := Sinhkhoa(d, pincodes, p); kq := MatrixMatrixMultiply(K, M) mod p; return kq; end proc; X := nguoiAgui("Lop Cao hoc dam bao toan hoc cho may tinh va he thong tinh toan", 10, "thanh"); //Người B giải mã và tìm được thông điệp nguoiBgiaima := proc (Cipher, d, pincodes) local i, j, p, kq, temp, c, k, K; p := 29; K := Sinhkhoa(d, pincodes, p); temp := MatrixMatrixMultiply(MatrixInverse(K), Cipher) mod p; 83  c := coldim(temp); kq := " "; k := 0; for i to d do for j to c do kq := Insert(kq, k, chuyensangchu(temp[i, j])); k := k+1; end do; end do; return kq; end proc; D1 := nguoiBgiaima(X, 10, "thanh"); //Cải tiến thuật toán với thêm một chuỗi ngẫu nhiên u và kết hợp với pincodes tạo thành pincodes mới và dùng pincodes mới sinh khóa, khi gởi ma trận đã mã hóa thì dấu chuỗi ngẫu nhiên u vào cột cuối và hàng cuối của ma trận nguoiAguicaitien := proc (Message, d, pincodes) local kq, a, i, M, j, K, p, l, b, X, Messagenew, u, kqcaitien, pincodesmoi; a := iquo(length(Message), d); b:=0; c:=length(Message) – d; if c<0 then b:=abs(c); else b:=(a+1).d – length(Message); end if; X := Random(b, " "); 84  Messagenew := cat(Message, X); a := iquo(length(Messagenew), d); M := Matrix(d, a); l := 1; p := 29; for i to d do for j to a do M[i, j] := chuyensangso(Messagenew[l]); l := l+1; end do; end do; u := sinhchuoingaunhien(d+a+1); pincodesmoi := cat(pincodes, u); K := Sinhkhoa(d, pincodesmoi, p); kq := MatrixMatrixMultiply(K, M) mod p; kqcaitien := Matrix(d+1, a+1); for i to d do for j to a do kqcaitien[i, j] := kq[i, j]; end do; end do; for i to d do kqcaitien[i, a+1] := chuyensangso(u[i]); end do; kqcaitien[d+1, a+1] := chuyensangso(u[d+1]); for i to a do kqcaitien[d+1, i] := chuyensangso(u[1+i+d]);  end do; return kqcaitien; 85  end proc; Xcaitien1 := nguoiAguicaitien("Lop Cao hoc dam bao toan hoc cho may tinh va he thong tinh toan", 9, "thanh"); //Người B tiến hành mã hóa Xcaitien2 := nguoiAguicaitien("Lop Cao hoc dam bao toan hoc cho may tinh va he thong tinh toan", 9, "thanh"); 86  >   87  //Người B tiến hành giải mã nguoiBgiaima := proc (Cipher, d, pincodes) local i, j, p, kq, temp, c, k, K, u, demu, rC, cC, pincodesmoi, Ciphermoi; p := 29; rC := rowdim(Cipher); cC := coldim(Cipher); demu := 0; u := " "; for i to rC do u := Insert(u, demu, chuyensangchu(Cipher[i, cC])); demu := demu+1 end do; for i to cC-1 do u := Insert(u, demu, chuyensangchu(Cipher[rC, i])); demu := demu+1 end do; demu := length(u); u := Delete(u, demu .. demu); pincodesmoi := cat(pincodes, u); K := Sinhkhoa(d, pincodesmoi, p); Ciphermoi := Matrix(rC-1, cC-1); for i to rC-1 do for j to cC-1 do 88  Ciphermoi[i, j] := Cipher[i, j]; end do; end do; temp := MatrixMatrixMultiply(MatrixInverse(K), Ciphermoi) mod p; c := coldim(temp); kq := " "; k := 0; for i from 1 to d do for j from 1 to c do kq := Insert(kq, k, chuyensangchu(temp[i, j])); k := k+1; end do; end do; return kq; end proc; nguoiBgiaima(Xcaitien2, 9, "thanh"); nguoiBgiaima(Xcaitien1, 9, "thanh"); Xcaitien3 := nguoiAguicaitien("Waiter Why is this key in my soup? What do you think of it? Sir I am very happy replied the waiter I have looked for it everywhere from yesterday. Thank you very much Thank you very much It is lucky that you did not swallow up it.", 9, "thanh"); print(); # input placeholder 89  nguoiBgiaima(Xcaitien3, 9, "thanh");print(); # input placeholder timetinh3 := time()-starttime3;print(); # input placeholder starttime4 := time();print(); # input placeholder Xcaitien4 := nguoiAguicaitien("The association said up to fourty percent of garment export orders for the remaining months of the year are from Japan. Under the Economic Partnership Agreement Vietnam has textile and garment products shipped to Japan will enjoy tax exemptions starting next month. Nguyen Hong Trang general director of lingerie producer Son Kim said the agreement will absolutely bring more orders to local exporters. Trang said her company plans to build a new factory next year to meet the rising demand from Japan. Pham Xuan Hong general director of Saigon three Garment Company said the agreement would benefit Japanese importers who would then offer to pay Vietnamese producers more. Saigon three Garment the largest Vietnamese jeans exporter to Japan said it has even received many orders for the first half of next year. But exporters also said it would be hard to boost shipments to Japan sharply even with the free trade agreement because they have to meet many strict requirements. Hong said his company used to offer a wide range of products. Now it only focuses on making jeans and khaki trousers for the Japanese market as it is the only way to ensure standard and output he said. Son Kim has Trang said exports to Japan are unlikely to advance suddenly since the market has set many strict standard barriers that many Vietnamese companies may find hard to 90  overcome.Japan is one of Vietnam is biggest export markets but Vietnamese products still hold a small share there accounting for only one percent of total Japan is imports according to the Ministry of Industry. About nine percent of Vietnamese export products to Japan would be exempted from tariffs within ten years under the Vietnam Japan Economic Partnership Agreement which the Japanese House of Councilors approved on June twenty four The association said up to fourty percent of garment export orders for the remaining months of the year are from Japan. Under the Economic Partnership Agreement Vietnam has textile and garment products shipped to Japan will enjoy tax exemptions starting next month. Nguyen Hong Trang general director of lingerie producer Son Kim said the agreement will absolutely bring more orders to local exporters. Trang said her company plans to build a new factory next year to meet the rising demand from Japan. Pham Xuan Hong general director of Saigon three Garment Company said the agreement would benefit Japanese importers who would then offer to pay Vietnamese producers more. Saigon three Garment the largest Vietnamese jeans exporter to Japan said it has even received many orders for the first half of next year. But exporters also said it would be hard to boost shipments to Japan sharply even with the free trade agreement because they have to meet many strict requirements. Hong said his company used to offer a wide range of products. Now it only focuses on making jeans and khaki trousers for the Japanese market as it is the only way to ensure standard and output he said. Son Kim has Trang said exports to Japan are unlikely to advance suddenly since the market has set many strict standard barriers that many Vietnamese companies may find hard to overcome.Japan is one of Vietnam is biggest export markets but Vietnamese products still hold a small share there accounting for only one percent of total Japan is imports according to the Ministry of Industry. About nine percent of Vietnamese export products to Japan would be exempted from tariffs within ten years under the Vietnam Japan Economic Partnership Agreement which the Japanese House of Councilors approved on June twenty four", 9, "thanh");print(); # input placeholder 91  nguoiBgiaima(Xcaitien4, 9, "thanh");print(); # input placeholder timetinh4 := time()-starttime4;