intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Giáo trình Bảo mật thông tin: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định

Chia sẻ: Ermintrudetran Ermintrudetran | Ngày: | Loại File: PDF | Số trang:88

Thêm vào BST
Báo xấu
47
lượt xem 10
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình Bảo mật thông tin: Phần 1 cung cấp cho người học những kiến thức như: Giới thiệu chung về mật mã, Mật mã cổ điển, Chuẩn mã dữ liệu. Mời các bạn cùng tham khảo để nắm chi tiết nội dung giáo trình!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Bảo mật thông tin: Phần 1 - ĐH Sư phạm kỹ thuật Nam Định

  1. Giáo trình Bảo mật thông tin MỤC LỤC LỜI NÓI ĐẦU .................................................................................................................5 CHƢƠNG 1: GIỚI THIỆU CHUNG VỀ MẬT MÃ ......................................................6 1.1. Sơ lƣợc về lịch sử mật mã ....................................................................................6 1.1.1. Mật mã cổ điển ................................................................................................7 1.1.2. Mật mã hiện đại ...............................................................................................7 1.2. Các hệ thống mật mã ............................................................................................8 1.2.1. Sơ đồ hệ thống mật mã ....................................................................................8 1.2.2. Yêu cầu của một hệ mật mã ............................................................................9 1.2.3. Mã khối và mã dòng ........................................................................................9 1.3. Mật mã khóa đối xứng và mật mã khóa công khai ............................................10 1.3.1. Hệ mật mã khóa đối xứng .............................................................................10 1.3.2. Hệ mật mã khóa công khai ............................................................................11 1.4. Các bài toán trong an toàn thông tin ..................................................................12 1.5. Thám mã và tính an toàn của các hệ mật mã .....................................................13 1.5.1. Vấn đề thám mã .............................................................................................13 1.5.2. Tính an toàn của một hệ mật mã ...................................................................14 CHƢƠNG 2: MẬT MÃ CỔ ĐIỂN ..............................................................................16 2.1. Giới thiệu ............................................................................................................16 2.2. Cơ sở toán học ....................................................................................................17 2.2.1. Tính chia hết của các số nguyên....................................................................17 2.2.2. Thuật toán Euclide và thuật toán Euclid mở rộng .........................................18 2.2.3. Quan hệ đồng dƣ và số học modulo m ..........................................................21 2.2.4. Phƣơng trình đồng dƣ ....................................................................................24 2.2.5. Các lớp thặng dƣ ...........................................................................................25 2.2.6. Hàm Euler......................................................................................................26 2.3. Một số hệ mật mã đơn giản ................................................................................26 2.3.1. Hệ mật mã dịch chuyển (Shift cipher) ..........................................................26 2.3.2. Hệ mật mã thay thế (substitution cipher). .....................................................28 2.3.3. Hệ mật mã Affine ..........................................................................................29 2.3.4. Hệ mật mã Vigenere ......................................................................................31 2.3.5. Hệ mật mã Hill ..............................................................................................32 2.3.6. Hệ mật mã hoán vị.........................................................................................36 1
  2. Giáo trình Bảo mật thông tin 2.3.7. Các hệ mật mã dòng ...................................................................................... 37 2.4. Mã thám các hệ mật mã cổ điển......................................................................... 40 2.4.1. Thám hệ mật mã Affine ................................................................................ 42 2.4.2. Thám hệ mật mã thay thế .............................................................................. 43 2.4.3. Tấn công với bản rõ đã biết trên hệ mật mã Hill. ......................................... 45 2.4.4. Thám mã đối với hệ mật mã Vigenère. ......................................................... 46 2.4.5. Thám mã hệ mã dòng xây dựng trên LFSR .................................................. 51 BÀI TẬP........................................................................................................................ 54 CHƢƠNG 3: CHUẨN MÃ DỮ LIỆU .......................................................................... 58 3.1. Giới thiệu hệ mật mã chuẩn ............................................................................... 58 3.2. Hệ mật mã DES ................................................................................................. 59 3.2.1. Mô tả DES ..................................................................................................... 59 3.2.2. Cách hoán vị bit ............................................................................................ 61 3.2.3. Cách tính bảng khoá từ khoá ban đầu K ....................................................... 62 3.2.4. Cách tính hàm f (Feistel Function) ............................................................... 67 3.2.5. DES trong thực tế .......................................................................................... 76 3.2.6. Phép tối ƣu hoá thời gian - bộ nhớ ................................................................ 76 3.2.7. Độ an toàn và việc thám mã đối với DES ..................................................... 79 3.3. Hệ mật IDEA ..................................................................................................... 82 3.3.1. Khái quát chung về hệ mật IDEA ................................................................. 82 3.3.2. Một số phép toán ........................................................................................... 82 3.3.3. Mô tả thuật toán IDEA .................................................................................. 83 3.3.4. Những đặc tính quan trọng ............................................................................ 88 CHƢƠNG 4: CÁC HỆ MẬT MÃ KHOÁ CÔNG KHAI............................................. 89 4.1. Giới thiệu về mật mã khoá công khai ................................................................ 89 4.1.1. Một số bài toán cơ bản .................................................................................. 90 4.1.2. Một số hệ mật mã khoá công khai quan trọng : ............................................ 93 4.1.3. Hàm cửa sập một chiều ................................................................................. 93 4.1.4. Định nghĩa hệ mật mã khóa công khai .......................................................... 95 4.2. Kiểm tra tính nguyên tố theo xác suất ............................................................... 95 4.2.1. Một số khái niệm và định nghĩa .................................................................... 96 4.2.2. Thuật toán kiểm tra số nguyên tố theo xác suất .......................................... 100 4.3. Một số kiến thức toán học ................................................................................ 101 4.3.1. Định lý phần dƣ China ................................................................................ 101 4.3.2. Một số định lý số học .................................................................................. 102 2
  3. Giáo trình Bảo mật thông tin 4.3.3. Phần tử nguyên thủy ....................................................................................104 4.3.4. Tính đồng dƣ của lũy thừa lớn (xe mod n) ..................................................105 4.4. Hệ mật mã RSA ...............................................................................................107 4.4.1 Định nghĩa ....................................................................................................107 4.4.2. Thực hiện hệ mật mã RSA ..........................................................................108 4.4.3. Tính bảo mật của hệ mật mã RSA...............................................................108 4.4.4. Các phƣơng pháp tấn công hệ mật mã RSA ...............................................109 4.5. Hệ mật mã Rabin ..............................................................................................116 4.5.1. Định nghĩa ...................................................................................................116 4.5.2. Tính an toàn của hệ mật mã Rabin. .............................................................118 4.6. Các thuật toán phân tích thừa số nguyên tố .....................................................119 4.6.1. Phƣơng pháp p-1 .........................................................................................119 4.6.2. Thuật toán Dixon và sàng bậc hai ..............................................................120 4.6.3. Các thuật toán phân tích trên thực tế. ..........................................................122 4.7. Hệ mật mã Elgamal và các giải thuật rời rạc ...................................................123 4.7.1. Hệ mật Elgamal ...........................................................................................123 4.7.2. Tính an toàn của hệ mật mã ElGamal. ........................................................124 4.7.3. Các thuật toán cho bài toán Logarithm rời rạc ............................................125 4.8. Các hệ mật dựa trên các bài toán NP đầy đủ....................................................129 4.8.1. Khái niệm độ phức tạp tính toán .................................................................129 4.8.2. Nguyên tắc chung xây dựng các hệ mật dựa trên các bài toán NP đầy đủ 129 4.8.3. Hệ mật xếp ba lô Merkle – Hellman ..........................................................130 4.8.4. Hệ mật McEliece .........................................................................................132 BÀI TẬP ......................................................................................................................138 CHƢƠNG 5: CHỮ KÝ ĐIỆN TỬ HÀM HASH VÀ PHÂN PHỐI KHOÁ ..............142 5.1. Các sơ đồ chữ ký điện tử ..................................................................................142 5.1.1. Khái niệm sơ đồ chữ ký số ..........................................................................143 5.1.2. Phân loại chữ ký số .....................................................................................144 5.1.3. Sơ đồ chữ ký RSA (đề xuất năm 1978).......................................................145 5.1.4. Sơ đồ chữ ký Elgamal .................................................................................146 5.1.5. Chuẩn chữ ký điện tử ..................................................................................150 5.1.6. Chữ ký một lần ............................................................................................151 5.1.7. Các chữ ký không chối đƣợc .......................................................................153 5.2. Các hàm Hash...................................................................................................155 5.2.1. Các chữ ký và các hàm Hash.......................................................................155 3
  4. Giáo trình Bảo mật thông tin 5.2.2. Hàm Hash không va chạm .......................................................................... 156 5.2.3. Hàm Hash logarithm rời rạc ........................................................................ 157 5.2.4. Các hàm Hash mở rộng ............................................................................... 159 5.2.5. Hàm Hash MD4 .......................................................................................... 159 5.3. Phân phối và thoả thuận về khoá ..................................................................... 165 5.3.1. Giới thiệu..................................................................................................... 165 5.3.2. Phân phối khoá trƣớc .................................................................................. 167 5.3.3. Kerboros ...................................................................................................... 170 5.3.4. Trao đổi khoá Diffie - Hellman................................................................... 171 BÀI TẬP...................................................................................................................... 177 4
  5. Giáo trình Bảo mật thông tin LỜI NÓI ĐẦU Từ khi con ngƣời có nhu cầu trao đổi thông tin với nhau thì nhu cầu giữ bí mật thông tin cũng xuất hiện. Trong thời đại ngày nay, với sự phát triển của khoa học kỹ thuật, các phƣơng tiện truyền thông ngày càng đa dạng, việc trao đổi thông tin càng trở nên dễ dàng thì việc giữ bí mật thông tin càng khó khăn. Các trao đổi thông tin qua mạng Intenet, các hình ảnh trên mặt đất, các cuộc đàm thoại hữu tuyến và vô tuyến… đều có thể dễ dàng thu đƣợc nhờ các thiết bị điện tử trên mặt đất hoặc từ vệ tinh nên an toàn thông tin đã trở thành nhu cầu bắt buộc cho mọi hệ thống ứng dụng. Từ thời xa xƣa, con ngƣời đã nghĩ ra cách che dấu thông tin bằng cách biến đổi thông tin đó thành dạng thông tin khác mà ngƣời ngoài cuộc không hiểu đƣợc, đồng thời có cách khôi phục lại nguyên dạng ban đầu để ngƣời trong cuộc hiểu đƣợc. Phƣơng pháp thực hiện nhƣ vậy gọi là mã hóa dữ liệu, sau này phát triển thành ngành khoa học gọi là mật mã học. Đây cũng là kỹ thuật lâu đời nhất trong việc đảm bảo an toàn thông tin. Ngày nay, cùng với sự phát triển của các ngành khoa học, các kỹ thuật mã hóa cũng ngày càng đa dạng và tinh vi hơn. Công nghệ mã hóa thông tin đã thu hút rất nhiều sự quan tâm của các nhà khoa học trên thế giới. Từ chỗ chỉ đƣợc sử dụng trong lĩnh vực chính trị, quân sự, mã hóa dữ liệu đã đƣợc đƣa vào sử dụng trong mọi lĩnh vực. Hiện nay có rất nhiều kỹ thuật mật mã khác nhau, mỗi kỹ thuật có những ƣu nhƣợc điểm riêng. Để đáp ứng nhu cầu học tập và tìm hiểu của sinh viên ngành Công nghệ thông tin, giáo trình Bảo mật thông tin đƣợc biên soạn giúp sinh viên có cái nhìn tổng quan về lĩnh vực an toàn và bảo mật thông tin, tiếp cận một số phƣơng pháp mã hóa dữ liệu, làm cơ sở cho những nghiên cứu mở rộng tiếp theo. Giáo trình gồm 5 chƣơng: Chƣơng 1 giới thiệu tổng quan về mật mã, chƣơng 2 tóm tắt sơ lƣợc về mã hóa cổ điển, chƣơng 3 trình bày về chuẩn mã dữ liệu, chƣơng 4 nêu một số hệ mật mã khóa công khai, chƣơng 5 giới thiệu một số sơ đồ chữ ký điện tử, hàm Hash và phân phối khóa. Giáo trình đƣợc biên soạn theo khung chƣơng trình môn học Bảo mật thông tin, nội dung dựa trên cơ sở cuốn “Cryptography: Theory and Practice” của Douglas Stinson, ngƣời dịch Nguyễn Bình. Với mục đích trang bị các kiến thức cơ sở giúp sinh viên tiếp cận với phƣơng pháp bảo vệ dữ liệu bằng cách mã hóa, giáo trình đã trình bày tóm tắt các phần lý thuyết toán học cơ bản đƣợc áp dụng trong các hệ mật mã, đƣa ra những ví dụ minh họa cụ thể, cuối mỗi chƣơng đều có bài tập. Do lần đầu biên soạn nên không tránh khỏi những sai sót và lỗi in ấn nhất định. Tác giả xin vui lòng tiếp nhận mọi sự đóng góp giúp cho giáo trình “Bảo mật thông tin” ngày càng tốt hơn. 5
  6. Giáo trình Bảo mật thông tin CHƢƠNG 1: GIỚI THIỆU CHUNG VỀ MẬT MÃ 1.1. Sơ lƣợc về lịch sử mật mã Nhu cầu sử dụng mật mã xuất hiện từ rất sớm, từ khi con ngƣời biết trao đổi và truyền thông tin cho nhau, đặc biệt khi các thông tin đó đƣợc thể hiện dƣới hình thức ngôn ngữ, thƣ từ. Các hình thức mật mã sơ khai đã đƣợc tìm thấy từ khoảng bốn nghìn năm trƣớc trong nền văn minh Aicập cổ đại. Trải qua hàng nghìn năm lịch sử, mật mã đã đƣợc sử dụng rộng rãi trên khắp thế giới để giữ bí mật cho việc giao lƣu thông tin trong nhiều lĩnh vực hoạt động của con ngƣời và các quốc gia, đặc biệt trong các lĩnh vực chính trị, quân sự, ngoại giao. Mật mã học là khoa học nghiên cứu mật mã: Tạo mã và Phân tích mã. Phân tích mã là kỹ thuật phân tích mật mã, kiểm tra tính bảo mật của nó hoặc phá vỡ bí mật của nó. Phân tích mã còn đƣợc gọi là Thám mã. Một số khái niệm - Mã hóa là quá trình chuyển thông tin có thể đọc đƣợc (gọi là bản rõ) thành thông tin khó có thể đọc đƣợc (gọi là bản mã) - Giải mã là quá trình chuyển đổi thông tin từ bản mã thành bản rõ - Thuật toán mã hóa hay giải mã là thủ tục tính toán để thực hiện mã hóa hay giải mã - Khóa mã hóa là một giá trị làm cho thuật toán mã hóa đƣợc thực hiện theo cách riêng biệt. Phạm vi có thể có của khóa đƣợc gọi là Không gian khóa - Hệ mã hóa là tập các thuật toán, các khóa Mật mã học có một lịch sử phát triển dài và phức tạp, tuy nhiên có thể chia thành hai giai đoạn chính Mật mã cổ điển : là các hệ mật mã ra đời trƣớc năm 1949 chủ yếu dùng để che giấu dữ liệu. Trong giai đoạn này mật mã học đƣợc coi là một nghệ thuật nhiều hơn là một môn khoa học mặc dù đã đƣợc ứng dụng trong thực tế. Mật mã hiện đại : Lịch sử mật mã học đƣợc đánh dấu vào năm 1949 khi Claude Shannon đƣa ra lý thuyết thông tin. Mật mã hiện đại ngoài khả năng che giấu thông tin còn dùng để thực hiện ký số, tạo đại diện thông điệp, giao thức bảo toàn dữ liệu, giao thức xác định thực thể,… Kể từ đó một loạt các nghiên cứu quan trọng của ngành mật mã học đƣợc thực hiện nhƣ nghiên cứu về mã khối, sự ra đời của các hệ mật khóa công khai và chữ ký điện tử. 6
  7. Giáo trình Bảo mật thông tin 1.1.1. Mật mã cổ điển Trong phần lớn thời gian phát triển của mình, lịch sử mật mã học chính là lịch sử của những phƣơng pháp mật mã học cổ điển chỉ cần bút và giấy. Khi các thông báo, thƣ từ đƣợc truyền đi và trao đổi với nhau thƣờng là các văn bản, tức là có dạng các dãy ký tự trong một ngôn ngữ nào đó, các thuật toán lập mã thƣờng cũng đơn giản là thuật toán xáo trộn, thay đổi các ký tự đƣợc xác định bởi các phép chuyển dịch, thay thế hay hoán vị các ký tự trong bảng ký tự của ngôn ngữ tƣơng ứng. Các cách mã hóa này rất dễ bị dò ra bằng phƣơng pháp phân tích tần suất. Mật mã cổ điển vẫn đƣợc phổ biến đến ngày nay chủ yếu thông qua việc giải các ô đố chữ. Vào đầu thế kỷ 20, với sự tiến bộ của kỹ thuật tính toán và truyền thông, ngành mật mã cũng có những tiến bộ to lớn. Một số thiết bị cơ khí đã đƣợc phát minh để thực hiện mã hóa, nổi tiếng nhất là máy Enigma đƣợc ngƣời Đức sử dụng trong đại chiến thế giới. Mật mã đƣợc thực hiện bằng các máy móc đã tăng độ phức tạp lên đáng kể đối với công việc phân tích mã. Sau thế chiến thứ II trở đi, cả hai ngành, mật mã học và phân tích mã ngày càng sử dụng nhiều các cơ sở toán học. Tuy thế, chỉ đến khi máy tính và các phƣơng tiện truyền thông Internet trở nên phổ biến, ngƣời ta mới có thể mang tính hữu dụng của mật mã học vào trong những thói quen sử dụng hằng ngày của mọi ngƣời, thay vì chỉ đƣợc dùng bởi chính quyền các quốc gia hay các hoạt động kinh doanh lớn trƣớc đó. 1.1.2. Mật mã hiện đại Sau chiến tranh thế giới thứ II, chính phủ, quân đội và một số công ty lớn của Mỹ ráo riết tiến hành xây dựng các công cụ mã hóa. Đầu những năm 1970 là sự phát triển của các thuật toán mã hóa khối, đầu tiên là Lucipher sau này phát triển thành DES. DES sau đó đã có một sự phát triển rực rỡ cho tới đầu những năm 90. Bƣớc ngoặt có tính cách mạng trong lịch sử khoa học mật mã hiện đại xẩy ra vào năm 1976 khi hai tác giả Diffie và Hellman đƣa ra khái niệm về mật mã khóa công khai và một phƣơng pháp trao đổi công khai để tạo ra một khóa bí mật chung mà tính an toàn đƣợc bảo đảm bởi độ khó của một bài toán toán học (cụ thể là bài toán tính "logarithm rời rạc"). Hai năm sau, năm 1978, Rivest, Shamir và Adleman tìm ra một hệ mật mã khóa công khai và một sơ đồ chữ ký điện tử hoàn toàn có thể ứng dụng trong thực tiễn, tính bảo mật và an toàn của chúng đƣợc bảo đảm bằng độ phức tạp của một bài toán số học nổi tiếng là bài toán phân tích số nguyên thành các thừa số nguyên tố. Sau phát minh ra hệ mật mã đó (nay thƣờng gọi là hệ RSA), việc nghiên cứu để 7
  8. Giáo trình Bảo mật thông tin phát minh ra các hệ mật mã khóa công khai khác và ứng dụng các hệ mật mã khóa công khai vào các bài toán khác nhau của an toàn thông tin đã đƣợc tiến hành rộng rãi, lý thuyết mật mã và an toàn thông tin trở thành một lĩnh vực khoa học đƣợc phát triển nhanh trong vài ba thập niên cuối của thế kỷ 20, lôi cuốn theo sự phát triển của một số bộ môn của toán học và tin học. 1.2. Các hệ thống mật mã 1.2.1. Sơ đồ hệ thống mật mã Trong mọi hoạt động của con ngƣời, nhu cầu trao đổi thông tin mật giữa những thành viên thuộc một nhóm nào đó với nhau là hết sức cần thiết. Trong thời đại ngày nay, với sự phát triển của các phƣơng tiện truyền thông và Internet, việc giữ bí mật ngày càng trở nên khó khăn. Một trong những phƣơng pháp thông dụng để giữ bí mật thông tin là mã hóa chúng bằng một hệ mật mã nào đó trƣớc khi truyền đi. Giả sử một ngƣời gửi A muốn gửi đến một ngƣời nhận B một văn bản p. Để bảo mật, A lập cho p một bản mật mã c và gửi c cho B, B nhận đƣợc c sẽ "giải mã" c để thu đƣợc văn bản p nhƣ A định gửi. Để A biến p thành c và B biến ngƣợc lại c thành p, A và B phải thỏa thuận trƣớc với nhau các thuật toán lập mã, giải mã và một khóa mật mã chung K để thực hiện các thuật toán đó. Ngƣời ngoài không biết các thông tin này (đặc biệt không biết khóa K), cho dù có lấy trộm đƣợc c trên kênh truyền thông công cộng cũng không thể tìm đƣợc văn bản p mà hai ngƣời A, B muốn gửi cho nhau. Sau đây là một định nghĩa hình thức về sơ đồ mật mã và cách thức thực hiện để lập mật mã và giải mật mã. Định nghĩa Một hệ mật mã là một bộ gồm 5 thành phần (P, C, K, E, D), trong đó 8
  9. Giáo trình Bảo mật thông tin  P (Plaintext) là một tập hữu hạn các bản rõ  C (Ciphertext) là một tập hữu hạn các bản mã  K (Key) là tập hữu hạn các khoá  E (Encryption) là tập các quy tắc mã hóa  D (Decryption) là tập hợp các quy tắc giải mã Với mỗi k K có một quy tắc mã ek: P  C và một quy tắc giải mã tƣơng ứng dk  D. Mỗi ek và dk là những hàm thỏa mãn dk(ek (x)) = x với mọi bản rõ x  P. Trong định nghĩa này, phép lập mật mã và giải mã đƣợc định nghĩa cho từng ký tự của bản rõ hoặc bản mã. Trong thực tế, bản rõ của một thông báo thƣờng là một dãy các ký tự bản rõ, tức là phần tử của tập P* và bản mật mã cũng là một dãy các ký tự bản mã, tức là phần tử của tập C* 1.2.2. Yêu cầu của một hệ mật mã Độ tin cậy: cung cấp sự bí mật cho các thông báo và dữ liệu đƣợc lƣu bằng việc sử dụng các kỹ thuật mã hoá. Tính toàn vẹn: cung cấp sự bảo đảm với tất cả các bên rằng thông báo không bị thay đổi từ khi gửi cho đến khi ngƣời nhận mở nó. Tính không chối bỏ: cung cấp một cách xác thực rằng tài liệu đã đến từ ai đó ngay cả khi họ cố gắng chối bỏ nó. Tính xác thực: cung cấp hai dịch vụ: - Nhận dạng nguồn gốc của thông báo và cung cấp sự bảo đảm rằng nó là đúng sự thực. - Kiểm tra đặc tính của ngƣời đang đăng nhập một hệ thống. Tiếp tục kiểm tra đặc tính của họ trong trƣờng hợp ai đó cố gắng kết nối và giả mạo là ngƣời sử dụng. 1.2.3. Mã khối và mã dòng Trong mật mã học, mã hoá khối là những thuật toán mã hoá đối xứng hoạt động trên những khối thông tin có độ dài xác định (block) với những chuyển đổi xác định. Chẳng hạn một thuật toán mã hoá khối có thể xử lý khối 128 bít đầu vào và biến nó thành khối 128 bít ở đầu ra. Quá trình chuyển đổi còn sử dụng thêm một tham số nữa: khoá bí mật để cá biệt hoá quá trình. Việc giải mã cũng diễn ra tƣơng ứng: xử lý khối mã hoá 128 bít cùng với khoá để trả về khối 128 bít bản rõ ban đầu. Để mã hoá những khối văn bản có độ dài vƣợt quá độ dài của khối, ngƣời ta sử dụng thuật toán theo một chế độ mã hoá khối nào đó. 9
  10. Giáo trình Bảo mật thông tin Thực hiện mã theo khối (block cipher): Trƣớc hết ta xác định một độ dài khối (chẳng hạn là m), tiếp đó mở rộng không gian khóa từ K thành Km , với mỗi K =K1...Km  Km, mở rộng eK và dK thành các thuật toán eK : Pm Cm và dK : CmPm nhƣ sau: với mọi x1...xk Pm và y1...yk  Cm eK(x1, …, xm) = eK1(x1)…eKm(xm) dK(y1, …, ym) = dK1(y1)…dKm(ym) Giả sử bản rõ mà ta muốn lập mật mã là dãy ký tự X P*. Cắt X thành từng khối, mỗi khối có độ dài m, nếu khối cuối cùng có độ dài nhỏ hơn m thì bổ sung vào phần cuối của khối một số ký tự qui ƣớc nào đó để nó cũng có độ dài m. Do đó có thể giả thiết X = X1....Xm, trong đó mỗi X1,...,Xm là một khối có độ dài m, định nghĩa bản mật mã của X là: eK(X) = eK(X1....Xm ) = eK(X1)....eK(Xm). Đặt Y = eK(X1)....eK(Xm), có thể viết Y = Y1....Ym với Yi =eK(Xi), và do đó có dK(Y) = dK(Y1)...dK(Ym) = X1...Xm = X. Cách mã theo khối đơn giản và thông dụng nhất là khi chọn độ dài khối k =1. Khi đó với mọi bản rõ X = x1...xm  P* ta có eK(X) = eK(x1....xm ) = eK(x1)....eK(xm) Với cách mã theo dòng (stream cipher), trƣớc hết phải xác định một dòng khóa, tức là một phần tử K = K1...Km  K*, với dòng khóa đó ta xác định mọi bản rõ X = x1...xm  P* có bản mã tƣơng ứng là eK(X) = eK(x1,x2, …,xm) = eK1(x1)eK2(x2)… eKm(xm) Giải mã Y = eK(X) ta đƣợc dK(Y) = dK1(eK1(x1))…dKm(eKm(xm) = x1 … xm = X Để sử dụng cách lập mật mã theo dòng, ngoài sơ đồ mật mã gốc còn phải có một dòng khóa, tức là một dãy có độ dài tùy ý các ký tự khóa. Đó thƣờng là các dãy các ký tự khóa đƣợc sinh ra bởi một bộ "tạo dãy ngẫu nhiên" nào đó xuất phát từ một "mầm" chọn trƣớc. Trong các ứng dụng thực tế, ngƣời ta thƣờng dùng cách mã theo dòng có sơ đồ mật mã gốc là sơ đồ Vernam với P = C = K = {0,1} và các hàm lập mã và giải mã đƣợc xác định bởi eK(x) = x + K mod 2, dK(y) = y +K mod 2 (K = 0 hoặc 1) dòng khóa đƣợc sinh ra bởi một bộ tạo dãy bit ngẫu nhiên nào đó. 1.3. Mật mã khóa đối xứng và mật mã khóa công khai 1.3.1. Hệ mật mã khóa đối xứng Mật mã khoá đối xứng là các hệ mật mã khi biết đƣợc khoá lập mã (ke) thì có thể tính đƣợc khoá giải mã (kd) và ngƣợc lại. Đặc biệt một số hệ mật mã có khoá lập mã và khoá giải mã trùng nhau, nhƣ hệ mật mã dịch chuyển hay hệ mật mã DES. Hệ mật mã khoá đối xứng còn gọi là hệ mật mã khoá bí mật hay khóa riêng, vì phải giữ bí mật cả 2 khoá. Trƣớc khi dùng hệ mật mã khoá đối xứng, ngƣời gửi và 10
  11. Giáo trình Bảo mật thông tin ngƣời nhận phải thoả thuận thuật toán mã hoá và khoá chung (lập mã hay giải mã), khóa phải đƣợc giữ bí mật. Độ an toàn của hệ mật mã loại này phụ thuộc vào khoá . Một số hệ mật mã khóa đối xứng: - Các hệ mã hóa cổ điển - Một số hệ mã hóa hiện đại: DES, ASE, IDEA,… Nơi ứng dụng: Hệ mật mã khoá đối xứng thƣờng đƣợc sử dụng trong môi trƣờng mà khoá chung có thể dễ dàng trao chuyển bí mật nhƣ trong cùng một mạng nội bộ. Hệ mật mã khóa đối xứng thƣờng dùng để mã hoá những bản tin lớn vì tốc độ mã hoá và giải mã nhanh hơn hệ mật mã khoá công khai. Các vấn đề đối với phƣơng pháp mã hóa đối xứng - Phƣơng pháp mã hoá đối xứng đòi hỏi ngƣời mã hoá và ngƣời giải mã phải cùng chung một khoá. Khi đó khoá phải đƣợc giữ bí mật tuyệt đối vì dễ dàng xác định một khoá nếu biết khoá kia. - Hệ mật mã khóa đối xứng không an toàn nếu khoá bị lộ với xác suất cao. Trong hệ này khoá phải đƣợc gửi đi trên kênh an toàn. - Vấn đề quản lý và phân phối khoá khó khăn phức tạp khi sử dụng hệ mật mã khoá đối xứng. Ngƣời gửi và ngƣời nhận phải luôn thống nhất với nhau về khoá. - Việc thay đổi khoá rất khó và dễ bị lộ. - Khuynh hƣớng cung cấp khoá dài mà nó phải đƣợc thay đổi thƣờng xuyên cho mọi ngƣời trong khi vẫn duy trì cả tính an toàn lẫn hiệu quả chi phí sẽ cản trở rất nhiều tới việc phát triển hệ mật mã này. 1.3.2. Hệ mật mã khóa công khai Hệ mật mã khóa công khai còn gọi là hệ mật mã phi đối xứng là hệ mật mã có khoá lập mã và khoá giải mã khác nhau (ke ≠ kd), biết đƣợc khoá này cũng “khó” tính 11
  12. Giáo trình Bảo mật thông tin đƣợc khoá kia. Trong hệ mật mã này khoá lập mã cho công khai, gọi là khoá công khai (public key), khoá giải mã giữ bí mật, gọi là khoá riêng (private key) hay khoá bí mật. Một ngƣời bất kỳ có thể dùng khoá công khai để mã hoá bản tin, nhƣng chỉ ngƣời có đúng khoá giải mã thì mới có khả năng đọc đƣợc bản rõ. Đặc điểm của hệ mật mã khóa công khai. - Thuật toán đƣợc viết một lần, công khai cho nhiều lần dùng, cho nhiều ngƣời dùng, chỉ cần giữ bí mật khoá riêng. - Khi biết các tham số ban đầu của hệ mã hoá, việc tính ra cặp khoá công khai và bí mật phải là “dễ”, tức là trong thời gian đa thức. Ngƣời gửi có bản rõ P và khoá công khai thì “dễ” tạo ra bản mã C. Ngƣời nhận có bản mã C và khoá bí mật thì “dễ” giải đƣợc thành bản rõ P. - Ngƣời mã hoá dùng khoá công khai, ngƣời giải mã giữ khoá bí mật. Khả năng lộ khoá bí mật khó hơn vì chỉ có một ngƣời biết. Nếu thám mã biết khoá công khai, cố gắng tìm khoá bí mật thì phải đƣơng đầu với bài toán “khó”. Nếu thám mã biết khoá công khai và bản mã C, thì việc tìm ra bản rõ P cũng là bài toán “khó”, số phép thử là vô cùng lớn, không khả thi. - Hệ mật mã khoá công khai thực hiện mã hoá và giải mã chậm hơn hệ mật mã khoá đối xứng. Nơi sử dụng hệ mật mã khóa công khai Hệ mật mã khoá công khai thƣờng đƣợc sử dụng chủ yếu trên các mạng công khai nhƣ Internet khi mà việc trao chuyển khoá bí mật tƣơng đối khó khăn. Đặc trƣng nổi bật của hệ mật mã khoá công khai là khoá công khai (public key) và bản mã (ciphertext) đều có thể gửi đi trên một kênh truyền tin không an toàn. Có biết cả khoá công khai và bản mã thì thám mã cũng không dễ khám phá đƣợc bản rõ. Nhƣng vì tốc độ mã hoá và giải mã chậm, nên hệ mật mã khoá công khai chỉ dùng để mã hoá những bản tin ngắn nhƣ mã hoá khoá bí mật gửi đi. Hệ mật mã khoá công khai thƣờng đƣợc sử dụng cho cặp ngƣời dùng thoả thuận khoá bí mật của hệ mã hoá khoá riêng. 1.4. Các bài toán trong an toàn thông tin Trong thời đại bùng nổ thông tin nhƣ hiện nay, nhu cầu trao đổi thông tin và các phƣơng tiện truyền đƣa thông tin phát triển một cách nhanh chóng. Cùng với sự phát 12
  13. Giáo trình Bảo mật thông tin triển đó, đòi hỏi bảo vệ tính bí mật và an toàn của thông tin cũng ngày càng lớn và có tính phổ biến. Có nhiều bài toán khác nhau về yêu cầu an toàn thông tin tùy theo những tình huống khác nhau, thƣờng gặp trong thực tiễn là những bài toán sau đây: - Bảo mật: giữ thông tin đƣợc bí mật đối với tất cả mọi ngƣời, trừ một ít ngƣời có thẩm quyền đƣợc đọc, biết thông tin đó - Toàn vẹn thông tin: bảo đảm thông tin không bị thay đổi hay xuyên tạc bởi những kẻ không có thẩm quyền hoặc bằng những phƣơng tiện không đƣợc phép - Nhận thực một thực thể: xác nhận danh tính của một thực thể, chẳng hạn một ngƣời, một máy tính cuối trong mạng, một thẻ tín dụng,... - Nhận thực một thông báo: xác nhận nguồn gốc của một thông báo đƣợc gửi đến - Chữ ký: một cách để gắn kết một thông tin với một thực thể, thƣờng dùng trong bài toán nhận thực một thông báo cũng nhƣ trong nhiều bài toán nhận thực khác - Ủy quyền: chuyển cho một thực thể khác quyền đƣợc đại diện hoặc đƣợc làm một việc gì đó - Cấp chứng chỉ: cấp một sự xác nhận thông tin bởi một thực thể đƣợc tín nhiệm - Báo nhận: xác nhận một thông báo đã đƣợc nhận hay một dịch vụ đã đƣợc thực hiện - Làm chứng: kiểm thử việc tồn tại một thông tin ở một thực thể khác với ngƣời chủ sở hữu thông tin đó - Không chối bỏ được: ngăn ngừa việc chối bỏ trách nhiệm đối với một cam kết đã có (ví dụ đã ký vào một văn bản) - Ẩn danh: che giấu danh tính của một thực thể tham gia trong một tiến trình nào đó (thƣờng dùng trong giao dịch tiền điện tử) - Thu hồi: rút lại một giấy chứng chỉ hay ủy quyền đã cấp Cơ sở của các giải pháp cho các bài toán kể trên là các phƣơng pháp mật mã, đặc biệt là mật mã khóa công khai. 1.5. Thám mã và tính an toàn của các hệ mật mã 1.5.1. Vấn đề thám mã Mật mã đƣợc sử dụng trƣớc hết là để bảo đảm tính bí mật cho các thông tin đƣợc trao đổi, do đó bài toán quan trọng nhất của thám mã cũng là bài toán phá bỏ tính bí mật đó, tức là từ bản mật mã có thể thu đƣợc dễ dàng (trên các kênh truyền tin công 13
  14. Giáo trình Bảo mật thông tin cộng) ngƣời thám mã phải phát hiện đƣợc nội dung thông tin bị che giấu trong bản mật mã, tốt nhất là tìm ra đƣợc bản rõ gốc của bản mật mã đó. Tình huống thƣờng gặp là bản thân sơ đồ hệ thống mật mã, kể cả các phép lập mã và giải mã (tức các thuật toán E và D), không nhất thiết là bí mật, do đó bài toán qui về việc tìm chìa khóa mật mã K hay chìa khóa giải mã K'', nếu hệ mật mã có khóa phi đối xứng. Nhƣ vậy, có thể qui ƣớc xem bài toán thám mã cơ bản là bài toán tìm khóa mật mã K (hay khóa giải mã K''). Để giải bài toán đó, giả thiết ngƣời thám mã biết thông tin về sơ đồ hệ mật mã đƣợc dùng, kể cả các phép lập mã và giải mã tổng quát E và D. Ngoài ra, ngƣời thám mã có thể biết thêm một số thông tin khác, tùy theo những thông tin đƣợc biết thêm này mà có thể phân loại bài toán thám mã thành các bài toán cụ thể nhƣ sau: - Bài toán thám mã chỉ biết bản mã: là bài toán phổ biến nhất, khi ngƣời thám mã chỉ biết một bản mật mã Y - Bài toán thám mã khi biết cả bản rõ: ngƣời thám mã biết một bản mật mã Y cùng với bản rõ tƣơng ứng X - Bài toán thám mã khi có bản rõ được chọn: ngƣời thám mã có thể chọn một bản rõ X, và biết bản mật mã tƣơng ứng Y. Điều này có thể xẩy ra khi ngƣời thám mã chiếm đƣợc (tạm thời) máy lập mã - Bài toán thám mã khi có bản mã được chọn: ngƣời thám mã có thể chọn một bản mật mã Y, và biết bản rõ tƣơng ứng X. Điều này có thể xẩy ra khi ngƣời thám mã chiếm đƣợc tạm thời máy giải mã 1.5.2. Tính an toàn của một hệ mật mã Tính an toàn của một hệ thống mật mã phụ thuộc vào độ khó của bài toán thám mã khi sử dụng hệ mật mã đó. Ngƣời ta đã đề xuất một số cách hiểu cho khái niệm an toàn của hệ thống mật mã, để trên cơ sở các cách hiểu đó nghiên cứu tính an toàn của nhiều hệ mật mã khác nhau, sau đây là vài cách hiểu thông dụng nhất: - An toàn vô điều kiện: giả thiết ngƣời thám mã có đƣợc thông tin về bản mã. Theo quan niệm lý thuyết thông tin, nếu những hiểu biết về bản mã không thu hẹp đƣợc độ bất định về bản rõ đối với ngƣời thám mã, thì hệ mật mã là an toàn vô điều kiện, hay theo thuật ngữ của C.Shannon, hệ là bí mật hoàn toàn. Nhƣ vậy, hệ là an toàn vô điều kiện, nếu độ bất định về bản rõ sau khi ngƣời thám mã có đƣợc các thông tin (về bản mã) bằng độ bất định về bản rõ trƣớc đó. - An toàn được chứng minh: một hệ thống mật mã đƣợc xem là có độ an toàn đƣợc chứng minh nếu ta có thể chứng minh đƣợc là bài toán thám mã đối với hệ thống 14
  15. Giáo trình Bảo mật thông tin đó khó tƣơng đƣơng với một bài toán khó đã biết, thí dụ bài toán phân tích một số nguyên thành tích các thừa số nguyên tố, bài toán tìm logarithm rời rạc theo một modulo nguyên tố,... (khó tương đương có nghĩa là nếu bài toán này giải đƣợc thì bài toán kia cũng giải đƣợc với cùng một độ phức tạp nhƣ nhau). - An toàn tính toán: hệ mật mã đƣợc xem là an toàn (về mặt) tính toán, nếu mọi phƣơng pháp thám mã đã biết đều đòi hỏi một nguồn năng lực tính toán vƣợt mọi khả năng (kể cả phƣơng tiện thiết bị) tính toán của một kẻ thù giả định. An toàn theo nghĩa này, nói theo ngôn ngữ của lý thuyết về độ phức tạp tính toán, là bao hàm cả khái niệm an toàn theo nghĩa "đƣợc chứng minh" nói trên. 15
  16. Giáo trình Bảo mật thông tin CHƢƠNG 2: MẬT MÃ CỔ ĐIỂN 2.1. Giới thiệu Hệ mật mã khoá đối xứng đã đƣợc dùng từ rất sớm, nên còn gọi là hệ mật mã khoá đối xứng - cổ điển. Trong suốt một thời kỳ lịch sử dài từ thời cổ đại cho đến vài ba thập niên gần đây, các phƣơng pháp mật mã đƣợc sử dụng trong thực tế đều là mật mã khoá đối xứng, từ hệ mật mã Ceasar đã đƣợc dùng hơn nghìn năm trƣớc cho đến các hệ mật mã đƣợc sử dụng với sự trợ giúp của kỹ thuật máy tính hiện đại trong thời gian gần đây. Các phƣơng thức mã hoá cổ điển chủ yếu dựa trên mã hoá hoán vị và mã hoá thay thế. Trong mã hoá thay thế, các ký tự (hoặc nhóm ký tự) đƣợc thay thế một cách có quy luật trong toàn bộ thông điệp bằng các ký tự khác (hoặc nhóm ký tự). Trong phƣơng thức mã hoá hoán vị thì các ký tự đƣợc giữ nguyên, nhƣng trật tự của chúng trong bản tin lại thay đổi theo một quy luật nào đó. Nói chung các hệ mật mã khóa đối xứng dùng để mã hóa và giải mã các văn bản thông thƣờng, để đơn giản, ta xét các văn bản tiếng Anh, nghĩa là sử dụng bảng chữ cái Latinh từ A đến Z. Quá trình lập mã và giải mã thƣờng đƣợc tiến hành theo các bƣớc: Lập mã : 1. Nhập bản rõ ký tự : Rõ_Chữ. 2. Chuyển Rõ_Chữ ==> Rõ_Số. 3. Chuyển Rõ_Số ==> Mã_Số. 4. Chuyển Mã_Số ==> Mã_Chữ Giải mã : 1. Nhập bản mã ký tự : Mã_Chữ . 2. Chuyển Mã_chữ ==> Mã_số. 3. Chuyển Mã_số ==> Rõ_số. 4. Chuyển Rõ_số ==> Rõ_chữ. Để chuyển từ chữ sang số hay ngƣợc lại từ số trở về chữ, ngƣời ta theo một qui ƣớc nào đó, ví dụ chữ cái thay bằng số theo modulo26 nhƣ sau: 16
  17. Giáo trình Bảo mật thông tin 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 Để thực hiện mã hoá hay giải mã với các “số”, ngƣời ta dùng các phép toán số học theo modulo26. Một số hệ mã hoá cổ điển: Hệ mã hoá dịch chuyển: Khoá có 1 “chìa” (thể hiện bằng 1 giá trị) Hệ mã Affine: Khoá có 2 “chìa” (thể hiện bằng 2 giá trị). Hệ mã hoá thay thế: Khoá có 26 “chìa” (thể hiện bằng 26 giá trị). Hệ mã hoá Vigenere: Khoá có m “chìa” (thể hiện bằng m giá trị). Hệ mã hoá HILL:Khoá có ma trận “chìa” (chùm chìa khoá). 2.2. Cơ sở toán học Lý thuyết mật mã là một ngành khoa học đƣợc xây dựng dựa trên cơ sở toán học, đặc biệt là lý thuyết số học. Phần này sẽ hệ thống lại một số kiến thức toán học cần thiết đƣợc sử dụng trong các hệ mật mã cổ điển nói riêng và lý thuyết mật mã nói chung. 2.2.1. Tính chia hết của các số nguyên Ta ký hiệu: Z là tập hợp các số nguyên Z = {.....,-2,-1, 0, 1, 2,....} Z + là tập hợp các số nguyên không âm Z += {0, 1, 2,.....} Zn là tập các số nguyên không âm nhỏ hơn n Zn = {0, 1, 2, …, n-1 } a. Một số khái niệm Ước số và bội số: Cho hai số nguyên a và b, b ≠0. Nếu có một số nguyên q sao cho a = b*q thì ta nói rằng a chia hết cho b, ký hiệu ba. Khi đó, b là ƣớc của a và a là bội của b. 17
  18. Giáo trình Bảo mật thông tin Cho các số nguyên a, b ≠0, tồn tại cặp số nguyên (q, r) (0 ≤ r < b) duy nhất sao cho a = b*q + r. Khi đó q gọi là thƣơng nguyên, r gọi là số dƣ của phép chia a cho b. Nếu r = 0 ta có phép chia hết. Ước chung lớn nhất, bội chung nhỏ nhất Số nguyên d đƣợc gọi là ƣớc chung của các số nguyên a1, a2, …, an nếu nó là ƣớc của tất cả các số đó. Số nguyên m đƣợc gọi là bội chung của các số nguyên a1, a2, …, an nếu nó là bội của tất cả các số đó. Một ƣớc chung d > 0 của các số nguyên a1, a2, …, an trong đó mọi ƣớc chung của a1, a2, …, an đều là ƣớc của d thì d đƣợc gọi là ƣớc chung lớn nhất của a1, a2,…, an, ký hiệu d = gcd(a1, a2, …, an). Nếu gcd(a1, a2, …, an) = 1 thì các số a1, a2,…, an đƣợc gọi là nguyên tố cùng nhau. Một bội số chung m > 0 của các số nguyên a1, a2, …, an trong đó mọi bội chung của a1, a2, …, an đều là bội của m thì m đƣợc gọi là bội số chung nhỏ nhất của các số a1, a2, …, an, ký hiệu m = lcm(a1, a2, …, an) b. Một số tính chất 1. d = gcd(a1, a2, …, an)  tồn tại các số x1, x2, …, xn sao cho d = a1x1 + a2x2 +…+ anxn 2. Nếu a1, a2, …, an nguyên tố cùng nhau  tồn tại các số x1, x2, …, xn sao cho a1x1 + a2x2 +…+ anxn =1 3. d = gcd(a1, a2, …, an)  gcd(a1/d, a2/d, …, an/d) =1 4. Nếu gcd (a, b) = 1 thì lcm (a,b) = a*b 5. Nếu b > 0, a = b*q + r thì gcd(a, b) = gcd (b, r) 6. gcd(a, b)*lcm(a,b) = a*b 2.2.2. Thuật toán Euclide và thuật toán Euclid mở rộng Thuật toán Euclid tìm ước chung lớn nhất Bài toán Input : Hai số nguyên không âm a, b thỏa mãn a ≥ b Output : d = gcd(a,b) Thuật toán : 18
  19. Giáo trình Bảo mật thông tin Euclid(int a, int b) 1. while( b>0) { r=a%b; a=b; b=r; } 2. Return a ; Ví dụ: Dùng thuật toán Euclide tìm gcd( 4864, 3458) a b r 4864 3458 3458 1406 1406 1406 646 646 646 114 114 114 76 76 76 38 38 38 0 0 Kết quả: gcd(4864, 3458) = 38 Nếu gcd(a, b) = d thì phƣơng trình a*x + b*y = d có nghiệm nguyên (x, y) duy nhất tìm đƣợc bởi thuật toán Euclide mở rộng nhƣ sau: Thuật toán Euclid mở rộng Thuật toán Euclid mở rộng sử dụng để giải phƣơng trình vô định nguyên (còn đƣợc gọi là phƣơng trình Đi-ô-phăng) a*x+b*y = c với a, b,c là các hệ số nguyên, x, y là các ẩn nhận giá trị nguyên. Điều kiện cần và đủ để phƣơng trình này có nghiệm (nguyên) là UCLN(a,b) là ƣớc của c. Khẳng định này dựa trên một mệnh đề: nếu d=UCLN(a,b) thì tồn tại các số nguyên x, y sao cho a*x+b*y = d Cơ sở lý thuyết: Giải thuật Euclid mở rộng kết hợp quá trình tìm ƢCLN(a,b) trong thuật toán Euclid với việc tìm một cặp số x, y thoả mãn phƣơng trình Đi-ô-phăng. 19
  20. Giáo trình Bảo mật thông tin Giả sử cho hai số tự nhiên a, b thỏa mãn a > b > 0. Đặt ro = a,r1 = b, chia r0 cho r1 đƣợc số dƣ r2. Nếu r2 = 0 thì dừng, nếu r2 khác không, chia r1 cho r2 đƣợc số dƣ r3,… Vì dãy các ri là giảm thực sự nên sau hữu hạn bƣớc ta đƣợc số dƣ rm = 0. ro = q1 * r1 + r2,0 < r2 < r1; r1 = q2 * r2 + r3,0 < r3 < r2; ....; rm − 1 = qm * rm + rm + 10 < rm + 1 < rm rm = qm + 1 * rm + 1 trong đó số dƣ cuối cùng khác 0 là rm + 1 = d. Bài toán đặt ra là tìm x, y sao cho a * x + b * y = rm + 1( = d) Để làm điều này, ta tìm x,y theo công thức truy hồi, nghĩa là sẽ tìm xi và yi sao cho: a * xi + b * yi = ri với i = 0,1,.... Ta có a * 1 + b * 0 = a = ro và a * 0 + b * 1 = b = r1, nghĩa là xo = 1,x1 = 0 và yo = 0, y1 = 1. (1) Tổng quát, giả sử có a * xi + b * yi = ri với i = 0,1,.... a * xi + 1 + b * yi + 1 = ri + 1 với i = 0,1,.... Khi đó từ ri = qi + 1 * ri + 1 + ri + 2 suy ra ri − qi + 1 * ri + 1 = ri + 2 (a * xi + b * yi) − qi + 1 * (a * xi + 1 + b * yi + 1) = ri + 2 a * (xi − qi + 1 * xi + 1) + b * (yi − qi + 1 * yi + 1) = ri + 2 từ đó, có thể chọn xi + 2 = xi − qi + 1 * xi + 1 (2) yi + 2 = yi − qi + 1 * yi + 1 (3) Khi i = m − 1 ta có đƣợc xm + 1 và ym + 1. Các công thức (1), (2), (3) là công thức truy hồi để tính x,y. Giải thuật Input : Hai số nguyên không âm a, b, a ≥ b Output : d = gcd(a, b) và hai số x, y thỏa mãn ax + by = d 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
7=>1