Tài liệu Cơ sở toán học của mã đối xứng

1 Khóa luận tốt nghiệp Trƣờng Đại Học Sƣ phạm Hà Nội 2 Khoa toán == o0o== đỗ ngọc tấn cơ sở toán học của mã đối xứng khoá luận tốt nghiệp đại học Chuyên ngành: ứng dụng Người hướng dẫn khoa học ts. Trần minh tƣớc hà nội – 2010 Đỗ Ngọc Tấn K32 CN Toán 2 Khóa luận tốt nghiệp MỤC LỤC Lời cảm ơn ………………….………………………………………………. 1 Lời cam đoan ………………………………………………………………... 2 Mở đầu ………………………………………………………………………. 3 CHƢƠNG 1. CÁC KIẾN THỨC CHUẨN BỊ 1.1. Phép đồng dư và vấn đề liên quan ……………………………………… 5 1.2. Trường hữu hạn ………………………………………………………… 7 1.3. Trường số (mở rộng đại số) …………………………………………….. 11 CHƢƠNG 2. MÃ ĐỐI XỨNG 2.1. Một số thuật ngữ và khái niệm …………………………………………. 14 2.2. Một số hệ mã đối xứng 2.2.1. Khái niệm chung ……………………………………………………… 15 2.2.2. Hệ mã dữ liệu tiêu chuẩn DES ……………………………………….. 15 2.2.3.Tiêu chuẩn mã nâng cao AES và thuật toán Rijndael ………………… 21 Kết luận …………………………………………………………………….. 42 Tài liệu tham khảo ………………………………………………………….. 43 Đỗ Ngọc Tấn K32 CN Toán 3 Khóa luận tốt nghiệp LỜI CẢM ƠN Để hoàn thành Khóa luận tốt nghiệp của mình em đã nhận được sự hướng dẫn, chỉ bảo tận tình của TS.Trần Minh Tƣớc, sự giúp đỡ, động viên của các thầy cô trong tổ toán ứng dụng, cùng tất cả các thầy cô và các bạn sinh viên trong khoa toán Trường Đại học sư phạm Hà Nội 2. Em xin chân thành cảm ơn sự giúp đỡ quý báu, chỉ đạo tận tình của thầy Trần Minh Tƣớc. Em cũng xin nói lời cảm ơn tới các thầy cô và các bạn sinh viên. Hà nội, tháng 5 năm 2010 Sinh viên thực hiện Đỗ Ngọc Tấn Đỗ Ngọc Tấn K32 CN Toán 4 Khóa luận tốt nghiệp LỜI CAM ĐOAN Tôi xin cam đoan nội dung khóa luận này hoàn toàn là kết quả nghiên cứu của riêng tôi dưới sự chỉ dẫn khoa học của thầy Trần Minh Tước. Tôi xin chịu mọi trách nhiệm về lời cam đoan của mình. Tác giả Đỗ Ngọc Tấn Đỗ Ngọc Tấn K32 CN Toán 5 Khóa luận tốt nghiệp MỞ ĐẦU Lý do chọn đề tài Có thể nói, mật mã đã xuất hiện từ thời cổ đại. Người ta cho rằng, người đầu tiên áp dụng mật mã một cách có hệ thống để đảm bảo bí mật thông tin quân sự là nhà quân sự thiên tài của La mã cổ đại Julius Caesar. Ngày nay mật mã không chỉ được dùng trong quân sự và ngoại giao mà còn được dùng trong rất nhiều các lĩnh vực khác như kinh tế, thương mại, truyền thông… Thừa nhận ý nghĩa quan trọng mang tính sống còn của mật mã trong thời đại ngày nay, đông đảo các chuyên gia đã đầu tư công sức để nghiên cứu, tìm tòi những điều mới mẻ và hiệu quả của mật mã. Trong công nghệ mã hóa thông tin về phương diện nghiên cứu và ứng dụng, Mã đối xứng có một vai trò quan trọng. Mã đối xứng là hệ mã mà trong đó việc lập mã và giải mã cùng sử dụng chung một chìa khóa mã. Các loại mã đối xứng điển hình trong lý thuyết mật mã như: Hệ mã dữ liệu tiêu chuẩn (DES), Mã hoá dữ liệu quốc tế (IDEA), Hệ mã SAFER, và gần đây là sự ra đời của loại mật mã có tính bảo mật cao đó là mã AES do Rijndael nghiên cứu. Trong đề tài này tôi đặt vấn đề nghiên cứu về vai trò của toán học trong lý thuyết mật mã nói chung thể hiện trong một số hệ mã đối xứng như DES, AES và lấy tên đề tài là “Cơ sở toán học của mã đối xứng”. Mục tiêu của đề tài Tìm hiểu sơ qua về công nghệ mã hóa thông tin cụ thể là về một số hệ mã đối xứng điển hình. *Đối tƣợng, phạm vi và phƣơng pháp nghiên cứu + Đối tượng: Một số hệ mã đối xứng. Đỗ Ngọc Tấn K32 CN Toán 6 Khóa luận tốt nghiệp + Phạm vi: Tìm hiểu về các hệ mã đối xứng và chú trọng đến cơ sở toán học của các hệ mã đối xứng. + Phương pháp nghiên cứu: Nghiên cứu tư liệu, phân tích, tổng hợp dựa trên các kết quả của số học và lý thuyết số. Ý nghĩa lý luận và thực tiễn của đề tài Trên thế giới nói đến thuật ngữ “Lý thuyết mật mã” hay “Công nghệ mã hóa thông tin” không phải là một thuật ngữ xa lạ. Nhưng ở Việt Nam khi nói đến thuật ngữ này là nói đến một vấn đề mới mẻ đối với sinh viên các ngành khoa học cơ bản. Là sinh viên ngành Toán, thực hiện đề tài “Cơ sở toán học của mã đối xứng” chúng tôi sẽ được tiếp cận với một lĩnh vực khá mới mẻ của toán học nhưng đã có ứng dụng hiệu quả trong thực tế. Việc thực hiện đề tài cũng là một lần tập dượt nghiên cứu khoa học nhằm nâng cao tri thức của bản thân đồng thời cũng để hiểu thêm về hoạt động nghiên cứu khoa học nói chung và nghiên cứu toán nói riêng. Đỗ Ngọc Tấn K32 CN Toán 7 Khóa luận tốt nghiệp CHƢƠNG 1. CÁC KIẾN THỨC CHUẨN BỊ 1.1. Phép đồng dƣ và vấn đề liên quan 1.1.1 Số nguyên tố * Ký hiệu Z là tập các số nguyên …,  2,1,0,1,2... và N là tập số tự nhiên (tức là các số nguyên không âm 0,1,2,3... ) * Với a, bZ ta nói rằng b chia hết cho a nếu như b có thể viết thành tích của a với một số nguyên khác ; khi đó ta cũng có thể nói rằng a chia hết b , hay a là một ước số của b , và ký hiệu a | b . Ta có một số tính chất sau: + Nếu a, b, cZ và a | b thì a | bc + Nếu a | b và b | c thì a | c + Nếu a | b và a | c thì a | b  c + Nếu a | b và a không chia hết c thì a không chia hết cả b  c và b c. * Số tự nhiên lớn hơn 1 mà không chia hết cho bất kỳ số tự nhiên nào khác ngoài 1 và chính nó được gọi là số nguyên tố. * Ước chung lớn nhất của 2 số tự nhiên a và b là số lớn nhất trong các tập ước chung của 2 số đó, được ký hiệu là gcd (a, b) hay đơn giản là  a, b  . Như vậy, nếu d | a và d | b thì d | gcd  a, b  * Khi 2 số tự nhiên có ước chung lớn nhất là 1 thì ta nói rằng chúng nguyên tố cùng nhau. 1.1.2. Phi hàm EULER Với nN số lượng các số tự nhiên bé hơn n và nguyên tố cùng nhau với n được kí hiệu là  (n) . Hàm  (n) được gọi là phi hàm Euler. Ví dụ:  (5)  4 ,  (6)  2 ,  (7)  6 Đỗ Ngọc Tấn K32 CN Toán 8 Khóa luận tốt nghiệp 1.1.3. Phép tính đồng dƣ và phƣơng trình đồng dƣ 1.1.3.1. Phép tính đồng dƣ Ta ký hiệu a  b (mod m) nếu như a và b sai khác nhau một bội của m , nói cách khác a  b (mod m) nếu a  b chia hết cho m . Quan hệ đồng dư modulo m dẫn đến việc phân hoạch tập số nguyên thành m lớp, mỗi lớp chứa các số nguyên đồng dư với nhau theo modulo m tập các lớp này được kí hiệu là Zm và chứa đúng m phần tử. Mỗi lớp trong tập Zm có đúng một số nằm trong 0,1,..., m  1 cho nên mỗi số nguyên trong đoạn này được xem đại diện cho một lớp của tập Zm . Một số tính chất của phép đồng dư  a  a (mod m) ;  Nếu a  b (mod m) thì b  a (mod m) ;  Nếu a  b (mod m) và b  c (mod m) thì a  c (mod m) ;  Nếu a  b (mod m) , c  d (mod m) thì a  c  b  d (mod m) , a.c  b.d (mod m) Như vậy ta có thể tự do thực hiện các phép tính số học thông thường trên tập Zm . Nếu x là một phần tử trong Zm và gcd ( x, m)  1 thì tồn tại các số u, v sao cho u.x  v.m  1, tức là u.x  1(mod m) , nên người ta nói x có nghịch đảo ( trong Zm ) là u và thường ký hiệu phần tử nghịch đảo là x 1 hay 1 . x Tập các phần tử trong Zm mà có nghịch đảo thường được ký hiệu là Z*m rõ ràng tập này có số phần tử nghịch đảo bằng  (m) , và trên tập này ngoài các phép cộng, trừ, nhân ta còn có thể đưa vào phép chia Nếu a  b (mod m) , c  d (mod m) với gcd (c, m)  1 thì a.c 1  b.d 1 (mod m) Đỗ Ngọc Tấn K32 CN Toán 9 Khóa luận tốt nghiệp Ví dụ: Với Z9  0,1,2,3,...,8  , Z*9  1,2,4,5,7,8 ta có 7 1  4(mod 9) và cho phép chia của 2 cho 7 (trong Z*9 ) được thực hiện như sau: 2  2.7 1  4.2  8(mod9) 7 Ta đương nhiên cũng có 2  7.8(mod9) vì 7.8  56  6.9  2 1.1.3.2. Phƣơng trình đồng dƣ tuyến tính ax  b (mod m) Khi gcd (a, m)  1 (tức a là phần tử của Z*m ) thì ta có ngay nghiệm x  a 1b (mod m) . Khi gcd (a, m)  g có 2 khả năng xảy ra: + phương trình có nghiệm khi g chia hết b , vì rằng khi ấy phương trình đã cho tương đương với phương trình (a / g ) x  b / g (mod m / g ) trong đó hệ số a / g là số nguyên tố cùng nhau với m / g + phương trình vô nghiệm nếu g không chia hết b , vì hiệu của 2 số chia hết cho g thì không thể là một số không chia hết cho g . 1.2. TRƢỜNG HỮU HẠN 1.2.1. Trƣờng Fp Với p là một số nguyên bất kì, trên tập các lớp đồng dư modulo p tức là Z p ta có thể thực hiện được các phép tính cộng, trừ, nhân. Khi p là số nguyên tố thì với mỗi phần tử khác không  Z p ta luôn tìm được phần tử nghịch đảo  1  Z p theo nghĩa  . 1  1(mod p) và do đó có thể thực hiện được phép chia (cho các phần tử khác 0 ), theo nghĩa sau:  :    . 1 Khi đó Z p có cấu trúc của một trường và ta kí hiệu trường này là trường Fp . Tập các phần tử khác 0 của trường này lập thành một nhóm đối với phép nhân và được kí hiệu là F p* . Như vậy: Đỗ Ngọc Tấn K32 CN Toán 10 Khóa luận tốt nghiệp Fp*  Fp \ 0  1,2,..., p  1. Từ nay, khi nói đến trường Fp hay nhóm F p* ta luôn hiểu rằng p là một số nguyên tố. Chú ý : Nếu p không là nguyên tố thì vẫn có thể định nghĩa một tập con bao gồm các phần tử khả nghịch của Z p và cũng ký hiệu là Z *p . Một phần tử g  Fp* được gọi là phần tử sinh của nhóm F p* nếu như tập các lũy thừa của g cũng chính là nhóm này, tức là 2 tập sau đây trùng nhau g , g 2  ,..., g p1  1,2,..., p  1 (không tính đến thứ tự). Rõ ràng, một phần tử chỉ có thể là phần tử sinh khi mọi lũy thừa của nó với bậc nhỏ hơn ( p  1) , bậc của nhóm, không phải là đơn vị. Ngược lại, một phần tử mà có lũy thừa bậc nào đó (nhỏ hơn hẳn ( p  1) ) bằng đơn vị thì không thể là phần tử sinh. Dễ thấy rằng một phần tử mà không sinh ra cả nhóm thì lũy thừa của nó cũng sẽ sinh ra một nhóm con và, theo Định lý Lagrange, ta biết rằng bậc của một nhóm con phải là ước của số lượng các phần tử có trong nhóm chứa nó (tức là ước của ( p  1) ). Như vậy muốn kiểm tra xem một phần tử nào đó có phải là phần tử sinh hay không chỉ cần nâng nó lên lũy thừa với bậc là ước của ( p  1) và xem xét: nếu tất cả lũy thừa này đều khác 1 thì nó là phần tử sinh (ngược lại thì không phải). Người ta chứng minh được rằng nếu g là một phần tử sinh của nhóm F p* còn b là một số nguyên tố cùng nhau với ( p  1) thì g b cũng là phần tử sinh của nhóm F p* . Cho nên, số các phần tử sinh của nhóm F p* đúng bằng số các số nguyên tố với ( p  1) tức là bằng  ( p  1). Đỗ Ngọc Tấn K32 CN Toán 11 Khóa luận tốt nghiệp Cho phần tử sinh g  Fp* . Khi ấy mọi phần tử h  F p* có thể được biểu diễn dưới dạng một lũy thừa nào đó của g . Tuy nhiên vấn đề tìm ra số x để có được biểu diễn h  g x là vô cùng gian nan, và được mang danh là bài toán logarit rời rạc. Một điều thú vị là tính khó giải của bài toán này không làm cho người ta khó chịu, mà ngược lại làm vui lòng các nhà mã hóa (một trong những ứng dụng vào tin học sẽ được nói đến ở phần sau). 1.2.2. Trƣờng F2r Đây cũng là loại trường có hữu hạn phần tử, nhưng có bản chất khác biệt so với loại trường hữu hạn đã xem xét ở trên. Ta kí hiệu F2 x là tập các đa thức với hệ số nằm trong trường F2 (đã xét ở trên). Có thể liệt kê ra rằng tập này có hai đa thức bậc 0 (là hai hằng số 0,1) hai đa thức bậc 1 là ( x và x  1), tức là có 4 đa thức bậc không vượt quá 1 , và khó khăn lắm ta mới có thể nhận ra rằng, với mỗi số tự nhiên n , có tất cả 2 n 1 đa thức với bậc không vượt quá x với dạng tổng quát là: an x n  an1 x n1  ...  a1 x  a0 , ai  F2 . Hai đa thức được cộng hoặc nhân với nhau theo quy tắc thông thường, chỉ lưu ý là các hệ số là các phần tử của trường F2 , trong đó 1  1  0. Ví dụ: ( x 2  x  1)( x 2  x)  ( x 4  x3  x 2 )  ( x3  x 2  x)  x 4  x. Đa thức gọi là bất khả quy (trên một trường nào đó) nếu nó không thể phân tích thành của các đa thức bậc nhỏ hơn (với các hệ số trên trường đã nói). Ví dụ: x 2  2, x 2  2 là những đa thức bất khả quy trên trường số hữu tỷ Q , nhưng trên trường số thực R thì chỉ có đa thức x 2  2 là đa thức bất khả quy. Trên trường F2 ta có x 2  1 là khả quy ( vì x 2  1  ( x  1) 2 ) còn x 2  x  1 là đa thức bất khả quy (đây là đa thức bậc hai duy nhất bất khả Đỗ Ngọc Tấn K32 CN Toán 12 Khóa luận tốt nghiệp quy). Trong tập đa thức bậc 3 chỉ có hai đa thức bất khả quy là x 3  x 2  1, x 3  x  1 . Tương tự như trên Z , trên tập F2 x ta cũng đưa vào phép tính đồng dư modulo một phần tử (tức là một đa thức) nào đó, và khi ấy F2 x sẽ được phân thành các lớp với các đại diện là đa thức bậc thấp hơn đa thức ta đã lấy làm modulo. Ví dụ: Nếu lấy đa thức x 3  x  1 (bất khả quy) làm modulo thì tập F2 x/ x 3  x  1 gồm các đa thức nhỏ hơn bậc 3 cụ thể là tập: 0,1, x, x  1, x , x 2 2   1, x 2  x, x 2  x  1 , trong đó đại diện của phần tử 0 chính là đa thức chọn làm modulo, nghĩa là x 3  x  1  0 . Trên tập này ta có thể thực hiện các phép cộng, trừ, nhân thông thường với lưu ý rằng x 3  x  1vì điều này tương đương với x 3  x  1  0 (trên F2 ). Ví dụ: ( x 2  x  1)( x  1)  x 3  1  ( x  1)  1  x(mod x 2  x  1) . Ngoài ra trên tập F2  x  / x3  x  1 ta còn thấy rằng. x 4  x 3 .x  ( x  1).x  x 2  x . Trong trường hợp chung , người ta chứng minh được rằng, với mỗi đa thức bất khả quy Pd (x) với bậc d , tập hợp F2 x/ Pd ( x) là một trường chứa đúng 2 d phần tử, kí hiệu là F2 d mỗi phần tử của nó được thể hiện bằng một đa thức với bậc không vượt quá d  1 Người ta cũng chứng minh được rằng tập các phần tử khác 0 của trường F2d , được kí hiệu là F2*d , cũng lập thành một nhóm và được sinh bởi một phần tử nào đó, tức là có cấu trúc tương tự như nhóm F p* . Phần tử sinh Đỗ Ngọc Tấn K32 CN Toán 13 Khóa luận tốt nghiệp của nó cũng phải có các lũy thừa bậc là ước của (2 d  1) khác đơn vị, và số lượng phần tử sinh trong nhóm này là  (2d  1) . Ta dễ thấy rằng x là phần tử sinh của F2*3  F2*8 . Thật vậy với g  x ta có g 2  x 2 , g 3  x  1, g 4  x 4  x 2  x, g 5  x 4 .x  x 2  x  1 g 6  x6  x3 .x3  ( x  1)2  x 2  1, g 7  x 6 .x  x3  x  1 Một phần tử của nhóm F2*d được gọi là chính phương (perfect square) nếu như nó là bình phương của một phần tử khác trong nhóm. Như vậy, hoàn toàn tương tự như trên ta có thể xây dựng các trường hữu hạn dạng Fp*d , với p là số nguyên tố bất kì (thay vì với p  2 ) Khi p  2 , có thể chỉ ra rằng một phần tử chính phương khi và chỉ khi lũy thừa của nó với bậc ( p d  1) chính là đơn vị. 2 1.3. Trƣờng số (mở rộng đại số) Cho đa thức với các hệ số nguyên f ( x)  an x n  an1 x n1  ...  a1 x  1, ai Z Số  thỏa mãn phương trình f ( )  0 được gọi là nghiệm của đa thức f . Giả sử  là một nghiệm của đa thức dạng như trên và n là bậc của đa thức có bậc thấp nhất nhận nó làm nghiệm. Người ta chứng minh được rằng tập các tổ hợp tuyến tính (với hệ số hữu tỷ) của các lũy thừa của số  tức là   Q ( )  b0  b1  ...  bn1 n1 | bi  Q , lập thành một trường số (với các phép tính quen thuộc trên trường số hữu tỷ). Mỗi phần tử của trường là nghiệm của một đa thức với hệ số nguyên, với hệ số đầu là số tự nhiên. Đa thức với bậc thấp nhất (trong các đa thức nhận phần tử đó là nghiệm) gọi là đa thức tối thiểu của phần tử đó. Nếu đa thức có hệ số Đỗ Ngọc Tấn K32 CN Toán 14 Khóa luận tốt nghiệp đầu bằng 1 thì phần tử được gọi là hệ số nguyên đại số. Rõ ràng mọi số nguyên n đều là số nguyên đại số, vì nó là nghiệm của đa thức bậc nhất 1.x  n  0. Ví dụ:   21/ 3  1 ta có (  1) 3  2 nên  3  3 2  3  3  0 , và do đó f ( x)  x 3  3x 2  3x  3 là đa thức tối thiểu của  , và suy ra  là một số nguyên đại số. Trong trường số nói trên, nếu 3 số nguyên đại số  ,  ,  thỏa mãn    . thì ta nói rằng  |  . Ta nói rằng số nguyên đại số  là nguyên tố nếu như  |  . kéo theo  |  hoặc  |  . Số nguyên đại số chia hết 1 thì được gọi là đơn vị (unit), ví dụ trong trường Q(i ) thì i là đơn vị, vì nó là nguyên (nghiệm của đa thức x 2  1 ) và chia hết 1 (do 1  i 4  i.i 3 ) ngoài ra  i,1,1 cũng là đơn vị. Hai số nguyên tố  ,  mà sai khác nhau một hệ số bằng đơn vị thì gọi là hai số nguyên tố kết hợp với nhau và ta viết    . Trong các số kết hợp với nhau ta luôn chọn được đại diện dưới dạng a  bi , với a  b, a  0 . Đáng buồn là không phải trường nào cũng “có đủ” số nguyên tố, nghĩa là không phải mọi số không nguyên tố đều có thể phân tích được thành tích của các số nguyên tố. Ví dụ: Trong trường Q( 5) thì 2 không phải là số nguyên tố, vì từ việc 2 chia hết 6 (do 2 / 2.3  6  (1   5 ).(1   5 ) ta không suy ra được 2 chia hết (1  5) hoặc 2 chia hết (1  5) , bởi vì các đa thức tối thiểu của (1   5 ) / 2 và (1   5 ) / 2 chính là 2 x 2  2 x  3 , có hệ số đầu không phải là 1. Trong khi đó 2 lại là số “bất khả quy”, nghĩa là không có phân tích nào khác ngoài 2=1.2=(-1).(-2). Đỗ Ngọc Tấn K32 CN Toán 15 Khóa luận tốt nghiệp Ta cũng thấy rằng việc phân tích một số (ra các thừa số) có thể không phải là duy nhất (như trên ta thấy, số 6 có 2 cách phân tích khác hẳn nhau). Tuy nhiên Q(i ) lại là một trường số có nhiều khía cạnh tốt. Tập các số nguyên đại số trên trường này cũng chính là tập các điểm có “tọa độ” nguyên trên mặt phẳng phức. Nó chính là Z(i) : a  bi | a, b  Z . Người ta chứng minh được rằng nếu số nguyên p (dương) thỏa mãn p  3(mod 4) thì cũng là số nguyên tố trên Z (i ) . Nếu p  1(mod 4) thì ta có thể viết: p  a 2  b 2 , a, b Z và do đó p  (a  bi)(a  bi) với (a  bi), (a  bi) không phải là các số nguyên tố kết hợp, và do đó ta có 2 số nguyên tố nằm trên số p. Đỗ Ngọc Tấn K32 CN Toán 16 Khóa luận tốt nghiệp CHƢƠNG 2. MÃ ĐỐI XỨNG 2.1. Một số thuật ngữ và khái niệm 2.1.1. Một số thuật ngữ - Văn bản (Plaintext) là một thông báo gốc cần chuyển được ghi bằng hình,ảnh âm thanh, chữ số, chữ viết. - Mã hóa (Encryption) là việc “ngụy trang” văn bản sang một dạng khác để cho người “ngoài cuộc” không thể đọc được, phục vụ cho nhu cầu bí mật trong trao đổi thông tin, dữ liệu và các giao dịch tài chính, thương mại… Quá trình “ngụy trang”văn bản gọi là lập mã, còn quá trình “khôi phục” lại văn bản nguồn gọi là giải mã. - Hệ mã (Cryptosystem) là một công cụ giúp thực hiện ngụy trang văn bản . Nghiên cứu để xây dựng và sử dụng các hệ mã có thể gọi là mật mã học (Cryptography). - Phân tích mã (Cryptanalysis), hay thám mã, là nghệ thuật phá các hệ mã (nhìn xuyên qua các phương pháp ngụy trang). - Công nghệ mã (Crytology) là viêc nghiên cứu tổng hợp cả Cryptography và Cryptanalysis. - Lập mã (Encrypt) là việc biến văn bản nguồn thành văn bản mã; - Giải mã (Decrypt) là việc đưa văn bản đã mã hóa trở về dạng văn bản nguồn; - Chìa khóa mã (Cipher key) là bí quyết lập mã và giải mã. 2.1.2. Vì sao cần mã hóa? Đó là một câu hỏi dễ trả lời, vì trong hoạt động của con người, nhu cầu bảo mật khi trao đổi thông tin giữa các thành viên trong nhóm nào đó với nhau có thể là hết sức cần thiết. Tuy nhiên, để thực sự thấy rõ yêu cầu cấp bách của mã hóa trong thời đại ngày nay, cần nhấn mạnh rằng với các phương Đỗ Ngọc Tấn K32 CN Toán 17 Khóa luận tốt nghiệp tiện kỹ thuật hiện đại việc giữ gìn bí mật ngày càng trở nên khó khăn. 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, các thông tin được chuyền qua mạng internet,… tất cả đều dễ dàng thu được nhờ các thiết bị điện tử trên mặt đất hoặc từ vệ tinh. Vì thế, phương pháp thông dụng nhất để giữ gìn bí mật thông tin là mã hóa chúng bằng một hệ mã trước khi truyền tải đi. Dĩ nhiên, việc mã hóa thông tin trước khi truyền đi và và việc giải mã các thông tin nhận được sẽ tạo nên một số khó khăn: giảm tốc độ đường truyền tin, tăng chi phí… Một hệ mã lý tưởng là một hệ mã đảm bảo được các yêu cầu thời gian mã hóa và giải mã nhanh, độ bảo mật cao. 2.2. Một số hệ mã đối xứng 2.2.1. Khái niệm chung  Mã đối xứng: là hệ mã mà trong đó việc lập mã và giải mã cùng sử dụng chung một chìa khóa mã.  Một đặc điểm chung của các hệ mã đối xứng là quá trình biến đổi được thực hiện trên các khối dữ liệu có độ dài đủ lớn và được thông qua nhiều vòng lặp tương tự nhau. 2.2.2. Hệ mã dữ liệu tiêu chuẩn – DES 2.2.2.1. Phƣơng án thu gọn của DES Trong mô hình này ta định ra độ dài của khối dữ liệu là 8 bit, độ dài của chìa khóa là 10 bit và số lượng vòng lặp trong thuật toán là 2. Như vậy, từ chìa khóa ban đầu (dài 10 bit) ta sẽ cho sinh ra 2 chìa khóa con có độ dài 8 bit dùng cho 2 vòng. Trong quá trình mã hóa ta sẽ thấy các công đoạn: Khóa con được sinh ra từ khóa ban đầu, dữ liệu tự biến đổi, rồi sau đó dữ liệu được kết hợp với khóa con trong một số phép biến đổi chung. Trước khi đi vào mô tả ta làm quen với một số phép biến đổi sẽ được dùng tới trong công đoạn này:  Phép hoán vị: Đỗ Ngọc Tấn K32 CN Toán 18 Khóa luận tốt nghiệp Ký hiệu là P, có vai trò tráo đổi vị trí các bit trong một khối dữ liệu. Mỗi phép trộn được cho bởi một vectơ có số tọa độ bằng số lượng bit trong khối dữ liệu. Mỗi tọa độ của vectơ cho biết vị trí mới của bit dữ liệu đang ở vị trí của tọa độ đó. Lưu ý rằng các vị trí được đánh số từ 0, nên vectơ P xác định phép hoán vị cho khối dữ liệu gồm k bit sẽ gồm các số tự nhiên từ 0 đến k  1. Ví dụ: P8  (2,5,0,4,7,3,1,6) xác định phép hoán vị trong 8 bit nó chuyển bit đầu tiên (mang chỉ số 0) ra vị trí thứ 3 (mang chỉ số 2), chuyển bit thứ 2 sang vị trí thứ sáu, chuyển bit thứ ba về vị trí đầu tiên, vv… và như vậy nó biến 10011101 thành ra 01111100.  Phép đảo vế dữ liệu: Ký hiệu là  , có vai trò đảo vị trí của nửa khối đầu (4 bit) cho nửa khối sau (4 bit); tức là ( X , X ')  ( X ', X ) , trong đó X , X ' là các xâu số nhị phân 4 bit ứng với các nửa khối dữ liệu (8 bit). Rõ ràng 1   , vì  2 là ánh xạ đồng nhất.  Ánh xạ “nâng” theo T : Giả sử T là một ánh xạ của các tập xâu số nhị phân 4 bit vào chính nó. T : 0,1  0,1 4 4 Khi đó ta ký hiệu T là ánh xạ được xác định bằng công thức T ( X , X ')  ( X  T ( X '). X ') , trong đó  là ký hiệu phép loại bit trên tập các xâu số nhị phân (hay cũng chính là phép cộng trong Z2 ), và do đó: T2 ( X , X ')  T ( X  T ( X '), X ')  ( X  T ( X ')  T ( X '), X ')  ( X , X ') tức ánh xạ T là ánh xạ tự khả nghịch, với mọi T bất kỳ. Sau đây là quy trình cơ bản trong DES.  Sinh các chìa khóa con từ chìa khóa ban đầu Đỗ Ngọc Tấn K32 CN Toán 19 Khóa luận tốt nghiệp Trong phương án DES rút gọn, ta dùng khóa ban đầu có độ dài 10 bit để sinh ra các khóa con có độ dài 8 bit. Cụ thể, trước hết ta sẽ dùng phép hoán vị P10  (2,4,1,6,3,9,0,8,7,5) đối với các xâu số nhị phân 10 bit; sau đó ta dùng phép dịch xoay vòng sang trái đối với từng nửa xâu bit theo một trình tự dịch chuyển (xác định trước) đối với từng khóa con, và cuối cùng là phép chọn ra 8 thành phần rồi sắp xếp lại theo trình tự xác định S 8  (5,2,6,3,7,4,9,8) đây là những thông tin công khai ai cũng biết. Như vậy, với khóa ban đầu là r0r1r2 ...r9 0,1 , ta áp dụng P10 và thu được P10(r0r1r2r3r4r5r6r7r8r9 )  (r2r4r1r6r3r9r0r8r7r5 )  s0s1s2s3s4s5s6s7 s8s9 ta phân kết quả thành 2 nửa là (s0 s1s2s3s4 )(s5s6s7 s8s9 ) và dịch mỗi nửa sang trái 1 bit (để làm khóa con thứ nhất) ta có được (s1s2 s3s4 s0 )(s6 s7 s8s9 s5 )  s1s2s3s4s0s6s7 s8s9s5  t0t1t2t3t4t5t6t7t8t9 tiếp tục theo S 8 , ta nhặt 8 phần tử và sắp xếp theo thứ tự đã định ra trong đó là t5t2t6t3t7t4t9t8 . Để tạo khóa con thứ 2 ta không bắt đầu lại từ 10 bit của khóa ban đầu, mà từ sản phẩm đã được tạo ra sau phép hoán vị trước khi nhặt ra khóa con thứ nhất, tức là t0t1t2t3t4t5t6t7t8t9 . Sau khi tách nó ra thành hai nửa và cho dịch từng nửa sang trái 2 vị trí, ta có được (t2t3t4t0t1 )(t7t8t9t5t6 )  t2t3t4t0t1t7t8t9t5t6  u0u1u2u3u4u5u6u7u8u9 Tiếp tục áp dụng phép chọn S 8 để chọn ra 8 thành phần u5u2u6u3u7u4u9u8  Mô tả các ánh xạ T và phép nâng tương ứng  T Ánh xạ T cho từng vòng biến đổi là khác nhau, nhưng về bản chất đều được sinh ra từ một ánh xạ nào đó thay đổi theo tham số vòng. + Toán tử T1 (thiết lập cho vòng thứ nhất) được xây dựng như sau: Đỗ Ngọc Tấn K32 CN Toán 20 Khóa luận tốt nghiệp Trước hết, xâu số nhị phân 4 bit ban đầu (nửa khối dữ liệu bên phải) là n4 , n5 , n6 , n7 được nở ra thành 8 bit bằng cách cho nó xoay vòng sang phải 1 bit để được 4 bit đầu (là n7 , n5 , n6 , n4 ) rồi sau đó số nhận được xoay vòng ngược về bên trái 2 bit để được 4 bit sau n5 , n6 , n7 , n4 . Khi đó xâu số nhị phân 8 bit thu được sau phép nở là n7 , n4 , n5 , n6 , n5 , n6 , n7 , n4 , và khi xếp các bit này thành 2 hàng (mỗi hàng 8 bit) thì ta có biểu đồ sau n7 n4 n5 n5 n6 n6 n7 n4 Sau khi đem bit loại bit với các thành phần của khóa con thứ nhất thu được trong quá trình sinh khóa con ở trên (ta đang nói đến T1 ), ta sẽ có n7  t5 n4  t2 n5  t7 n6  t4 n5  t6 n6  t3 n7  t9 n4  t8 Để tiện dùng cho các bước tiếp theo, kết quả này được viết lại như sau p00 p01 p10 p11 p02 p03 p12 p13 Biểu đồ này sẽ định ra một phép thay thế tiến hành như sau. Từng cụm thành phần ( p00 p03 ),( p01, p02 ),... sẽ biểu diễn số nhị phân nào đó từ 0 đến 3 (cụ thể 00=0,01=1,10=2,11=3), giúp ta định ra hàng và cột của phần tử trong các ma trận chữ nhật nào đó. Số tạo ra bởi các bit ngoài vùng “đóng cọc” , như ( p00 p03 ) , sẽ là số chỉ hàng, còn số tạo các bit nằm trong vùng “đóng cọc”, như ( p01 p02 ) , sẽ là số chỉ cột, và như vậy mỗi hàng của biểu đồ sẽ cho ta một “tọa độ” trên một bảng số (ma trận). Các ma trận này thường được cho sẵn được gọi là các hộp thay thế (S-box), và trong phương án DES thu gọn chúng là: Đỗ Ngọc Tấn K32 CN Toán