Xem mẫu
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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 : CmPm 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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 ba. Khi đó, b là ƣớc của a và a là bội của b.
17
- 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
- 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
- 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
nguon tai.lieu . vn
