Tài liệu Luận văn Nghiên cứu lược đồ chia sẻ bí mật và ứng dụng của chúng vào việc thi tuyển sinh đại học: ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN BÁ THÁI
NGHIÊN CỨU LƯỢC ĐỒ CHIA SẺ BÍ MẬT VÀ
ỨNG DỤNG CỦA CHÚNG VÀO VIỆC
THI TUYỂN SINH ĐẠI HỌC
Nghành : Công nghệ Điện tử - Viễn thông
Chuyên nghành : Kỹ thuật Điện tử
Mã số : 60 52 70
LUẬN VĂN THẠC SỸ
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS Hồ Văn Canh
Hà Nội - 2011
- -
2
LỜI CAM ĐOAN
Tôi xin cam đoan: Luận văn “ Nghiên Cứu Lược Đồ Chia Sẻ Bí Mật Và
Ứng Dụng Của Chúng Vào Việc Thi Tuyển Sinh Đại Học” là công trình nghiên
cứu khoa học độc lập của tôi.
Kết quả nghiên cứu được trình bầy trong luận văn chưa được công bố
dưới bất kỳ hình thức nào.
Hà nội, ngày 20 tháng 05 năm 2011
Tác giả luận văn
Nguyễn Bá Thái
- -
3
MỤC LỤC
LỜI NÓI ĐẦU ................................................................................................... 5
CHƯƠNG 1. MẬT MÃ CỔ ĐIỂN..................................................................... 7
1.1 KHÁI NIỆM VÀ ĐỊNH NGHĨA VỀ MẬT MÃ.....................
80 trang |
Chia sẻ: haohao | Lượt xem: 1522 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn Nghiên cứu lược đồ chia sẻ bí mật và ứng dụng của chúng vào việc thi tuyển sinh đại học, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN BÁ THÁI
NGHIÊN CỨU LƯỢC ĐỒ CHIA SẺ BÍ MẬT VÀ
ỨNG DỤNG CỦA CHÚNG VÀO VIỆC
THI TUYỂN SINH ĐẠI HỌC
Nghành : Công nghệ Điện tử - Viễn thông
Chuyên nghành : Kỹ thuật Điện tử
Mã số : 60 52 70
LUẬN VĂN THẠC SỸ
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS Hồ Văn Canh
Hà Nội - 2011
- -
2
LỜI CAM ĐOAN
Tôi xin cam đoan: Luận văn “ Nghiên Cứu Lược Đồ Chia Sẻ Bí Mật Và
Ứng Dụng Của Chúng Vào Việc Thi Tuyển Sinh Đại Học” là công trình nghiên
cứu khoa học độc lập của tôi.
Kết quả nghiên cứu được trình bầy trong luận văn chưa được công bố
dưới bất kỳ hình thức nào.
Hà nội, ngày 20 tháng 05 năm 2011
Tác giả luận văn
Nguyễn Bá Thái
- -
3
MỤC LỤC
LỜI NÓI ĐẦU ................................................................................................... 5
CHƯƠNG 1. MẬT MÃ CỔ ĐIỂN..................................................................... 7
1.1 KHÁI NIỆM VÀ ĐỊNH NGHĨA VỀ MẬT MÃ....................................... 7
1.1.1 Khái niệm: ......................................................................................... 7
1.1.2 Định nghĩa ......................................................................................... 7
1.2 MỘT SỐ MÃ HÓA ĐƠN GIẢN: ............................................................. 9
1.2.1 Mã dịch vòng ( shift cipher)............................................................... 9
1.2.1.1 Định nghĩa (modulo): ..................................................................... 9
1.2.1.2 Định nghĩa mã dịch vòng:............................................................. 10
1.2.2 Mã thay thế (MTT) ......................................................................... 12
1.2.3. Mã Affine ....................................................................................... 14
1.2.3.1 Định lý (đồng dư thức): ............................................................... 14
1.2.3.2 Định nghĩa (hàm Euler):............................................................... 14
1.2.3.3 Định nghĩa (phần tử nghich đảo trong phép nhân): ...................... 16
1.2.4. Mật mã Hill .................................................................................... 19
1.2.4.1 Khái niệm: .................................................................................... 19
1.2.4.2 Định nghĩa ( ma trận đơn vị) ........................................................ 20
1.2.4.3 Định nghĩa (Định thức của ma trận):............................................ 20
1.2.4.4 Định lý (ma trận ngịch đảo): ........................................................ 20
1.2.4.5 Định nghĩa Mật mã Hill ................................................................ 21
1.2.5. Mã chuyển vị (Transposition): ........................................................ 22
CHƯƠNG 2. CHUẨN MÃ DỮ LIỆU (DES).................................................. 24
2.1 MÔ TẢ DES (Data Encryption Standard)............................................... 24
2.2 Các bước thực hiện:................................................................................ 25
2.2.1 Cách tính biến x0 ............................................................................. 25
2.2.2 Cách tính LiRi: ................................................................................ 26
2. 2.2.1. Các biến trong hàm f: ................................................................. 26
2.2.2.2 Cách tính hàm f: ........................................................................... 30
2.2.3 Xác định bản mã y: .......................................................................... 35
2.3 Giải mã DES .......................................................................................... 43
2.3.1 Thuật toán........................................................................................ 43
2.3.2 Chứng minh thuật toán .................................................................... 43
2.4 Các vấn xung quanh DES .................................................................... 46
2.4.1 Những ý kiến phản hồi..................................................................... 46
2.4.2 DES trong thực tế ............................................................................ 47
2.4.3. Một vài kết luận về mã DES ........................................................... 48
CHƯƠNG 3. CÁC SƠ ĐỒ CHIA SẺ BÍ MẬT ................................................ 49
3.1 Khái niệm về chia sẻ bí mật:................................................................... 49
3.2 Sơ đồ chia sẻ bí mật................................................................................ 50
3.2.1 Khái niệm “Sơ đồ chia sẻ bí mật”: ................................................... 50
3.2.2 Định nghĩa: ...................................................................................... 50
3.3 Cấu trúc truy nhập và sơ đồ chia sẻ bí mật.............................................. 55
3.3.1 Định nghĩa sơ đồ chia sẻ bí mật hoàn thiện ..................................... 55
- -
4
3.3.2 Định nghĩa tập hợp thức” tối thiểu .................................................. 56
3.4 Mạch đơn điệu:....................................................................................... 56
3.4.1 Định nghĩa( mạch đơn điệu): ........................................................... 56
3.4.2 Chia sẻ Khóa bí mật dựa vào “ mạch đơn điệu” ............................... 57
CHƯƠNG 4. ỨNG DỤNG THUẬT TOÁN DES VÀ LƯỢC ĐỒ CHIA SẺ BÍ
MẬT VÀO THI TUYỂN SINH ....................................................................... 61
4.1 Các ứng dụng: ........................................................................................ 61
4.2 Quy trình thực hiện giải bài toán: ........................................................... 61
4.2.1 Sơ đồ: .............................................................................................. 61
4.2.2 Các bước thực hiện: ........................................................................ 62
4.2.3. Mô phỏng lược đồ chia sẻ bí mật bằng ngôn ngữ C: ....................... 63
4.2.3.1 Chia sẻ khoá bí mật theo giao thức “chia sẻ bí mật” Shamir. ....... 63
4.2.3.2 Khôi phục khoá bí mật bằng phương pháp giải hệ phương trình
tuyến tính.................................................................................................. 64
4.2.3.3 Khôi phục khoá bí mật bằng phương pháp dùng công thức nội suy
Lagrange .................................................................................................. 68
4.2.3.4 Chia sẻ khoá bí mật theo phương pháp bằng mạch đơn điệu ........ 69
4.2.3.4 Khôi phục khoá bí mật theo phương pháp mạch đơn điệu............ 71
4.3 Mã nguồn mở của chương trình .............................................................. 72
KẾT LUẬN...................................................................................................... 79
TÀI LIỆU THAM KHẢO ................................................................................ 80
- -
5
LỜI NÓI ĐẦU
Ngày nay, mạng máy tính ngày càng trở nên phổ biến. Mỗi quốc gia đều có
mạng riêng với rất nhiều mạng mang tính bộ phận. Trên pham vi toàn cầu, người
ta đã dùng mạng Internet một cách thông dụng. Nhiều dịch vụ điện tử như: thư
điện tử, chuyển tiền, thương mại điện tử, chính phủ điện tử...đã được áp dụng
rộng rãi.
Các ứng dụng trên mạng máy tính ngày càng trở nên phổ biến, thuận lợi và
quan trọng thì yêu cầu về an toàn mạng, về an ninh dữ liệu càng trở nên cấp
bách và cần thiết.
Trên thế giới có rất nhiều quốc gia, nhiều nhà khoa học nghiên cứu về vấn đề
bảo mật, đưa ra nhiều thuật toán với mục đích thông tin truyền đi không bị lấy
cắp hoặc nếu bị lấy cắp thì cũng không sử dụng được.Trong đề tài của em đưa ra
một thuật toán đó là thuật toán DES (Data encryption standar) đây là thuật toán
chuẩn của mỹ, được mỹ và nhiều nước trên thế giới sử dụng, thuật toán này đã
được đưa vào sử dụng nhiều năm nhưng vẫn giữ được tính bảo mật của nó. Tuy
nhiên với công nghệ phát triển như hiện nay thì thuật toán DES trở lên không
được an toàn tuyệt đối nữa, người ta đã đưa ra thuật toán 3DES về nguyên tắc
thuật toán 3DES dựa trên nền tảng của thuật toán DES nhưng số bít được mã
hóa tăng lên.
Mã hóa và các lược đồ chia sẻ bí mật có thể được ứng dung trong rất nhiều lĩnh
vực ví dụ: phát hành thẻ ATM trong ngân hàng, đấu thầu từ xa, trong thi tuyển
sinh, trong lĩnh vực quân sự….Trong đề tài của em đề cập tới một lĩnh vực đó là
ứng dụng trong thi tuyển sinh đại học.
Vấn đề thi tuyển sinh đại học ở nước ta trở thành gánh nặng cho nghành Giáo
Dục và các ban nghành khác liên quan. Nó làm tổn hại về kinh tế và công sức
không chỉ đối các ban nghành tham gia tổ chức kỳ thi mà ngay cả đối với các thí
sinh dự thi, nhưng đó là điều bắt buộc phải được tổ chức hàng năm. Do vậy làm
sao để giảm thiểu các khâu trong thi tuyển sinh mà vẫn đảm bảo tính công bằng
và chính xác là điều cần thiết, theo tôi để làm được điều đó ta nên ứng dụng
công nghệ thông tin vào việc thi tuyển sinh đại học, một trong các ứng dụng đó
là ứng dụng LƯỢC ĐỒ CHIA SẺ BÍ MẬT vì nó đảm bảo được tính bí mật và
chính xác mà trong thi tuyển sinh hai điều đó là quan trọng nhất.
Phạm vi luận văn đề cập đến vấn đề mật mã, thuật toán DES, lược đồ chia sẻ bí
mật và ứng dụng của chúng trong thi tuyển sinh.
Luận văn gồm 4 chương:
- -
6
Chương 1: Mật mã cổ điển: chương này nói về khái niệm và định nghĩa
một số mật mã cổ điển
Chương 2: Thuật toán DES: chương này nói về mã hóa và giải mã trong
thuật toán DES, các vấn đề xung quanh DES.
Chương 3: Chia sẻ bí mật: Chương này nói về khái niệm chia sẻ bí mật,
phương thức chia sẻ và khôi phục khóa bí mật.
Chương 4: Ứng dụng thuật toán DES và Lược đồ chia sẻ bí mật vào thi
tuyển sinh: chương này nói về phần ứng dụng và mô phỏng lược đồ chia se bí
mật bằng ngôn ngữ C
Để hoàn thành luận văn này, trước hết em xin chân thành cảm ơn TS Hồ
Văn Canh – người đã trực tiếp hướng dẫn, cung cấp tài liệu và đóng góp nhiều ý
kiến cho luận văn. Em cũng xin chân thành cảm ơn các thầy cô giáo, các cán bộ
khoa Điện tử , phòng Sau đại học, Trường Đại học công nghệ - ĐHQG Hà nội
đã tận tình giảng dậy, giúp đỡ em trong suốt khóa học.
- -
7
CHƯƠNG 1. MẬT MÃ CỔ ĐIỂN
1.1 KHÁI NIỆM VÀ ĐỊNH NGHĨA VỀ MẬT MÃ
1.1.1 Khái niệm:
- Chức năng cơ bản của mật mã là tạo ra khả năng liên lạc trên một kênh
không mật cho hai người sử dụng (tạm gọi là A và B) sao cho đối phương (C)
không thể hiểu được thông tin được truyền đi.
- Kênh liên lạc có thể là một đường dây điện thoại hoặc một mạng máy tính.
Thông tin mà Al muốn gửi cho B bản rõ có thể là một văn bản tiếng Anh, các dữ
liệu bằng số hoặc bất cứ tài liệu nào có cấu trúc tuỳ ý.
- A sẽ mã hoá bản rõ bằng một khóa đã được xác định trước và gửi bản mã
kết quả trên kênh. C có bản mã thu trộm được trên kênh song không thể xác
định nội dung của bản rõ, nhưng B (người đã biết khoá mã) có thể giải mã và
thu được bản rõ.
Ta sẽ mô tả hình thức hoá nội dung bằng cách dung khái niệm toán học như
sau:
1.1.2 Định nghĩa
Một hệ mật là một bộ 5 (P,C,K,E,D) thoả mãn các điều kiện sau:
1. P là một tập hữu hạn các bản rõ có thể.
2. C là một tập hữu hạn các bản mã có thể.
3. K (không gian khoá) là tập hữu hạn các khoá có thể.
4. Đối với mỗi k K có một quy tắc mã ek: P C và một quy tắcv giải
mã tương ứng dk D. Mỗi ek: P C và dk: C P là những hàm
sao cho:
dk(ek (x)) = x với mọi bản rõ x P.
Trong đó, chúng ta cần lưu ý tính chất 4: Nội dung của nó là nếu một bản
rõ x được mã hoá bằng ek và bản mã nhận được sau đó được giải mã bằng dk thì
ta phải thu được bản rõ ban đầu x.
Giả sử ta có bản rõ cần truyền đi là:
x = x1,x2 ,. . .,xn
- -
8
với số nguyên n 1 nào đó. Ở đây mỗi ký hiệu của mỗi bản rõ xi P , 1 i
n. Mỗi xi sẽ được mã hoá bằng quy tắc mã ek với khoá K xác định trước đó.
Bản mã thu được là:
y = y1,y2 ,. . .,yn Trong đó yk=ek(xi) i=1,2,…,n. còn kєK
Khi Bob nhận đươc y1,y2 ,. . .,yn anh ta sẽ giải mã bằng hàm giải mã dk và thu
được bản rõ gốc x1,x2 ,. . .,xn.
Hình 1.1 là một ví dụ về một kênh liên lạc
`
Rõ ràng là trong trường hợp này hàm mã hoá phải là hàm đơn ánh ( tức là ánh
xạ 1-1), nếu không việc giải mã sẽ không thực hiện được một cách tường minh.
Ví dụ
y = ek(x1) = ek(x2)
trong đó x1 x2 , thì B sẽ không có cách nào để biết liệu bản rõ là x1 hay x2 .
Hình 1.1. Kênh liên lạc
C
Bộ giải mã Bộ mã hoá B A
Kênh an toàn
Nguồn khoá
x
k
k
k
y
k
x
- -
9
1.2 MỘT SỐ MÃ HÓA ĐƠN GIẢN:
1.2.1 Mã dịch vòng ( shift cipher)
1.2.1.1 Định nghĩa (modulo): Định nghĩa về đồng dư
Giả sử a và b là các số nguyên và m là một số nguyên dương. Khi đó ta
viết a b (mod m) nếu a-b chia hết cho m. Mệnh đề a b (mod m) được gọi là "
a đồng dư với b theo modulo m". Số nguyên m được gọi là mudulus.
Bây giờ ta có thể định nghĩa số học modulo m: Zm được coi là tập hợp
{0,1,. . .,m-1} có trang bị hai phép toán cộng và nhân. Việc cộng và nhân trong
Zm được thực hiện giống như cộng và nhân các số thực ngoài trừ một điểm là
các kết quả được rút gọn theo modulo m.
Ví dụ tính 11 13 trong Z16 . Tương tự như với các số nguyên ta có 11
13 = 143. Để rút gọn 143 theo modulo 16, ta thực hiện phép chia bình thường:
143 = 8 16 + 15, bởi vậy 143 mod 16 = 15 trong Z16 .
Các định nghĩa trên phép cộng và phép nhân Zm thảo mãn hầu hết các quy
tắc quen thuộc trong số học. Sau đây ta sẽ liệt kê mà không chứng minh các tính
chất này:
1. Phép cộng là đóng, tức với bất kì a,b Zm ,a +b Zm
2. Phép cộng là giao hoán, tức là với a,b bất kì Zm
a+b = b+a
3. Phép cộng là kết hợp, tức là với bất kì a,b,c Zm
(a+b)+c = a+(b+c)
4. 0 là phần tử đơn vị của phép cộng, có nghĩa là với a bất kì Zm
a+0 = 0+a = a
5. Phép nhân là đóng , tức là với a,b bất kì Zm , ab Zm .
6. Phép nhân là giao hoán , nghĩa là với a,b bất kì Zm , ab = ba
7. Phép nhân là kết hợp, nghĩa là với a,b,c Zm , (ab)c = a(cb)
8. 1 là phần tử đơn vị của phép nhân, tức là với bất kỳ a Zm
- -
10
9. a1 = 1a = a Phần tử nghịch đảo của phép cộng
của phần tử bất kì (a Zm ) là m-a, nghĩa là a+(m-a) = (m-a)+a = 0 với
bất kì a Zm .
10. Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với
a,b,c Zm , (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac)
Vì phần tử ngược của phép cộng tồn tại trong Zm nên cũng có thể trừ các
phần tử trong Zm . Ta định nghĩa a-b trong Zm là a+m-b mod m. Một cách
tương tự có thể tính số nguyên a-b rồi rút gọn theo modulo m.
Ví dụ : Để tính 11-18 trong Z31, ta tính 11+13 mod 31 = 24. Ngược lại, có
thể lấy 11-18 được -7 rồi sau đó tính -7 mod 31 = 24.
1.2.1.2 Định nghĩa mã dịch vòng:
Mã dịch vòng được xác định trên Z26 (do có 26 chữ cái trên bảng chữ cái
tiếng Anh) mặc dù có thể xác định nó trên Zm với modulus m tuỳ ý. Dễ dàng
thấy rằng, mã dịch vọng (MDV) sẽ tạo nên một hệ mật như đã xác định ở trên,
tức là dK (eK(x)) = x với mọi x Z26 .
Hình 1.2: Mã dịch vòng
Ta sẽ sử dụng MDV (với modulo 26) để mã hoá một văn bản tiếng Anh
thông thường bằng cách thiết lập sự tương ứng giữa các kí tự và các thặng dư
theo modulo 26 như sau: A 0,B 1, . . ., Z 25. Vì phép tương ứng này
còn dùng trong một vài ví dụ nên ta sẽ ghi lại để còn tiện dùng sau này:
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
Giả sử P = C = K = Z26 với 0 k 25 , định nghĩa:
eK(x) = x +k mod 26
và dK(x) = y -k mod 26
(x,y Z26)
- -
11
13 14 15 16 17 18 19 20 21 22 23 24 25
- -
12
Ví dụ 1.1:
Giả sử khoá cho MDV là K = 11 và bản rõ là:
wewillmeetatmidnight
Trước tiên biến đổi bản rõ thành dãy các số nguyên nhờ dùng phép tương
ứng trên. Ta có:
22 4 22 8 11 11 12 4 4 19
0 19 12 8 3 13 8 6 7 19
sau đó cộng 11 vào mỗi giá trị rồi rút gọn tổng theo modulo 26
7 15 7 19 22 22 23 15 15 4
11 4 23 19 14 24 19 17 18 4
Cuối cùng biến đổi dãy số nguyên này thành các kí tự thu được bản mã
sau:
HPHTWWXPPELEXTOYTRSE
Để giải bản mã này, trước tiên, Bob sẽ biến đổi bản mã thành dãy các số
nguyên rồi trừ đi cho 11 ( rút gọn theo modulo 26) và cuối cùng biến đổi lại dãy
này thành các ký tự.
Nhận xét rằng, MDV (theo modulo 26) là không an toàn vì nó có thể bị
thám theo phương pháp vét cạn. Do chỉ có 26 khoá nên dễ dàng thử mọi khoá dK
có thể cho tới khi nhận được bản rõ có nghĩa.
1.2.2 Mã thay thế (MTT)
Trên thực tế MTT có thể lấy cả P và C đều là bộ chữ cái tiếng anh, gồm
26 chữ cái. Ta dùng Z26 trong MDV vì các phép mã và giải mã đều là các phép
toán đại số. Tuy nhiên, trong MTT, thích hợp hơn là xem phép mã và giải mã
như các hoán vị của các kí tự.
Hình 1.3 Mã thay thế
Cho P =C = Z26 . K chứa mọi hoán vị có thể của 26 kí hiệu 0,1, . . .
,25
Với mỗi phép hoán vị K , ta định nghĩa:
e(x) = (x)
và
d(y) = -1(y)
trong đó -1 là hoán vị ngược của .
- -
13
Sau đây là một ví dụ về phép hoán vị ngẫu nhiên tạo nên một hàm mã hoá
(cũng như trước, các kí hiệu của bản rõ được viết bằng chữ thường còn các kí
hiệu của bản mã là chữ in hoa).
a b c d e F g h i j k l M
X N Y A H P O G Z Q W B T
n o p q r S t u v w x y Z
S F L R C V M U E K J D I
Như vậy, e (a) = X, e (b) = N,. . . . Hàm giải mã là phép hoán vị ngược.
Điều này được thực hiện bằng cách viết hàng thứ hai lên trước rồi sắp xếp theo
thứ tự chữ cái. Ta nhận được:
A B C D E F G H I J K L M
d l r y v O h e z x w p T
N O P Q R S T U V W X Y Z
b g f j q N m u s k a c i
Mỗi khoá của MTT là một phép hoán vị của 26 kí tự. Số các hoán vị này
là 26!, lớn hơn 4 10 26 là một số rất lớn. Bởi vậy, phép tìm khoá vét cạn không
thể thực hiện được, thậm chí bằng máy tính. Tuy nhiên, sau này sẽ thấy rằng
MTT có thể dễ dàng bị thám bằng các phương pháp khác.
- -
14
1.2.3. Mã Affine
MDV là một trường hợp đặc biệt của MTT chỉ gồm 26 trong số 26! các
hoán vị có thể của 26 phần tử. Một trường hợp đặc biệt khác của MTT là mã
Affine được mô tả dưới đây. trong mã Affine, ta giới hạn chỉ xét các hàm mã có
dạng:
e(x) = ax + b mod 26,
a,b Z26 . Các hàm này được gọi là các hàm Affine (chú ý rằng khi a = 1, ta có
MDV).
Để việc giải mã có thể thực hiện được, yêu cầu cần thiết là hàm Affine
phải là đơn ánh. Nói cách khác, với bất kỳ y Z26, ta muốn có đồng nhất thức
sau:
ax + b y (mod 26)
phải có nghiệm x duy nhất. Đồng dư thức này tương đương với:
ax y-b (mod 26)
Vì y thay đổi trên Z26 nên y-b cũng thay đổi trên Z26 . Bởi vậy, ta chỉ cần nghiên
cứu phương trình đồng dư:
ax y (mod 26) (y Z26 ).
1.2.3.1 Định lý (đồng dư thức):
Đồng dư thức ax b mod m chỉ có một nghiệm duy nhất x Zm với mọi b
Zm khi và chỉ khi UCLN(a,m) = 1.
Vì 26 = 2 13 nên các giá trị a Z26 thoả mãn UCLN(a,26) = 1 là a = 1,
3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 và 25. Tham số b có thể là một phần tử bất
kỳ trong Z26 . Như vậy, mã Affine có 13 25 = 325 (vì k=0 bị loại) khoá có thể
( dĩ nhiên con số này quá nhỏ để bảo đảm an toàn).
Bây giờ ta sẽ xét bài toán chung với modulo m. Ta cần một định nghĩa
khác trong lý thuyết số.
1.2.3.2 Định nghĩa (hàm Euler):
Giả sử a 1 và m 2 là các số nguyên. UCLN(a,m) = 1 thì ta nói rằng a
và m là nguyên tố cùng nhau. Số các số nguyên trong Zm nguyên tố cùng nhau
với m thường được ký hiệu là (m) ( hàm này được gọi là hàm Euler).
- -
15
Một kết quả quan trọng trong lý thuyết số cho ta giá trị của (m) theo các thừa
số trong phép phân tích theo luỹ thừa các số nguyên tố của m. ( Một số nguyên p
1 là số nguyên tố nếu nó không có ước dương nào khác ngoài 1 và p. Mọi số
nguyên m 1 có thể phân tích được thành tích của các luỹ thừa các số nguyên tố
theo cách duy nhất. Ví dụ 60 = 2 3 3 5 và 98 = 2 7 2 ).
Ta sẽ ghi lại công thức cho (m) trong định lí sau:
Định lý
Giả sử m =
n
i
e
i
ip
1
Trong đó các số nguyên tố pi khác nhau và ei >0 , 1 i n. Khi đó
)(m =
n
i
e
i
ip
1
( - )1ieip
Định lý này cho thấy rằng, số khoá trong mã Affine trên Zm bằng m x
(m), trong đó (m) được cho theo công thức trên. ( Số các phép chọn của b là
m và số các phép chọn của a là (m) với hàm mã hoá là e(x) = ax + b).
Ví dụ, khi m = 60, m=2×2×3×5=22×31×51=>(60) = (22-21)( 31-30)(51-50) = 16
và số các khoá trong mã Affine là:
16 x 60=960.
Một vài tính chất đáng lưu ý của hàm Erler().
(a) Nếu p là số nguyên tố thì
(p)=p-1.
(b) Nếu p,q là hai số nguyên tố khác nhau.Khi đó,
(p.q)= (p). (q)=(p-1)(q-1)
(c) Giả sử m,n là hai số nguyên dương tùy ý sao cho UCLN(m,n)=1 (tức m,n
nguyên tố cùng nhau).Khi đó ,
(m,n)= (m). (n)
Ví dụ m=15, n=16 Khi đó
(m,n)= (15,16)= (15). (16)=8.8=64.
(d) Nếu m=pk với p là số nguyên tố ,thì
(m)= (pk)=pk-1(p-1).
- -
16
Từ đó suy ra rằng (2)=1, (1)=0
1.2.3.3 Định nghĩa (phần tử nghich đảo trong phép nhân):
Giả sử a Zm . Phần tử nghịch đảo (theo phép nhân) của a là phần tử a-1
Zm sao cho aa-1 a-1a 1 (mod m).
Bằng các lý luận tương tự như trên, có thể chứng tỏ rằng a có nghịch đảo
theo modulo m khi và chỉ khi UCLN(a,m) =1, và nếu nghịch đảo này tồn tại thì
nó phải là duy nhất. Ta cũng thấy rằng, nếu b = a-1 thì a = b-1 . Nếu p là số
nguyên tố thì mọi phần tử khác không của ZP đều có nghịch đảo. Một vành trong
đó mọi phần tử khác 0 đều có nghịch đảo được gọi là một trường.
Bằng phương pháp thử và sai ta có thể tìm được các nghịch đảo của các
phần tử nguyên tố cùng nhau với 26: 1-1 = 1, 3-1 = 9, 5-1 = 21, 7-1 = 15, 11-1 =
19, 17-1 =23, 25-1 = 25. (Có thể dễ dàng kiểm chứng lại điều này, ví dụ: 7 15 =
105 1 mod 26, bởi vậy 7-1 = 15).
Xét phương trình đồng dư y ax+b (mod 26). Phương trình này tương
đương với
ax y-b ( mod 26)
Vì UCLN(a,26) =1 nên a có nghịch đảo theo modulo 26. Nhân cả hai vế của
đồng dư thức với a-1 ta có:
a-1(ax) a-1(y-b) (mod 26)
Áp dụng tính kết hợp của phép nhân modulo:
a-1(ax) (a-1a)x 1x x.
Kết quả là x a-1(y-b) (mod 26). Đây là một công thức tường minh cho x.
Như vậy hàm giải mã là:
d(y) = a-1(y-b) mod 26
Thuật toán Euclide mở rộng :
Bổ đề : Nếu UCLN(m,n)=k thì tồn tại 2 số nguyên x,y sao cho mx+ny=k.
Thuật toán Euclide mở rộng cho phép tìm được cả 3 số x,y,k khi điều kiện
của bồ đề được thỏa mãn.
Sau đây là nội dung của thuật toán Euclide mở rộng:
Cho m,n là hai số nguyên dương
Ta hãy tìm x,y,k sao cho mx + ny =k.
- -
17
Đầu vào (input) : m,n (giả sử m>n).
đầu ra: x,y,k.
cho (a1,a2,a3),( b1,b2,b3),(c1,c2,c3) là 3vectơ
Bước 1: (a1,a2,a3)←(1,0,m), (b1,b2,b3)←(0,1,n)
Bước 2: Nếu b3=0 thì thuật toán dừng và a1,a2,a3 là đáp số của bài toán
(tức là x=a1,y=a2,k=a3).
Bước 3: Đặt q=[a3/b3]; (là phần nguyên của a3/b3 , tức q là số nguyên lớn
nhất nhưng không vượt quá a3/b3) và (c1,c2,c3)← (a1,a2,a3)-q( b1,b2,b3);
(a1,a2,a3)← ( b1,b2,b3); ( b1,b2,b3)← (c1,c2,c3) và trở về bước 2. Thuật toán dừng
sẽ cho :
out put:
Ví dụ1 cho m=42, n=4
Ta có bảng quá trình tính toán sau đây:
Vậy x=1, y=-10 và k=2.
Ví dụ 2 : m=95, n=8.
Quá trình tính toán được cho trong bảng sau:
Vậy x=-1, y=12, k=1.
q a1 a2 a3 b1 b2 b3 c1 c2 c3
11 1 0 95 0 1 8 1 -11 7
1 0 1 8 1 -11 7 -1 12 1
7 1 -11 7 -1 12 1 8 -95 0
-1 12 1 8 -95 0
a1=x, a2=y, a3=k
q a1 a2 a3 b1 b2 b3 c1 c2 c3
10 1 0 42 0 1 4 1 -10 2
2 0 1 4 1 -10 2 -2 21 0
1 -10 2 -2 21 0
- -
18
Chú ý : số trong ô a2 chính là nghịch đảo của 8mod95 (tức số y là nghịch
đảo của n theo module m) (Trong trường hợp k=1).
Thật vậy ta có 12.8≡1mod95 Do đó từ định nghĩa 12 là nghịch đảo của 8
theo module95 (vì UCLN(8,95)=1 nên tồn tại nghịch đảo của 8 theo mod95).
Hình 1.4 cho mô tả đầy đủ về mã Affine.
Hình 1.4 Mật mã Affine
Ví dụ 1.3
Giả sử K = (7,3). Như đã nêu ở trên, 7-1 mod 26 = 15. Hàm mã hoá là
eK(x) = 7x+3
Và hàm giải mã tương ứng là:
dK(x) = 15(y-3) = 15y -19
Ở đây, tất cả các phép toán đều thực hiện trên Z26. Ta sẽ kiểm tra liệu
dK(eK(x)) = x với mọi x Z26 không?. Dùng các tính toán trên Z26 , ta có
dK(eK(x)) =dK(7x+3)
=15(7x+3)-19
= x +45 -19
= x.
Để minh hoạ, ta hãy mã hoá bản rõ "hot". Trước tiên biến đổi các chữ h,
o, t thành các thặng du theo modulo 26. Ta được các số tương ứng là 7, 14 và
19. Bây giờ sẽ mã hoá:
7 7 +3 mod 26 = 52 mod 26 = 0
7 14 + 3 mod 26 = 101 mod 26 =23
Cho P = C = Z26 và giả sử
P = { (a,b) Z26 Z26 : UCLN(a,26) =1 }
Với K = (a,b) K , ta định nghĩa:
eK(x) = ax +b mod 26
và
dK(y) = a-1(y-b) mod 26,
x,y Z26
- -
19
7 19 +3 mod 26 = 136 mod 26 = 6
Bởi vậy 3 ký hiệu của bản mã là 0, 23 và 6 tương ứng với xâu ký tự AXG.
1.2.4. Mật mã Hill
1.2.4.1 Khái niệm:
Giả sử m là một số nguyên dương, đặt P = C = (Z26)m . Ý tưởng ở đây là lấy m
tổ hợp tuyến tính của m ký tự trong một phần tử của bản rõ để tạo ra m ký tự ở
một phần tử của bản mã.
Ví dụ nếu m = 2 ta có thể viết một phần tử của bản rõ là x = (x1,x2) và một
phần tử của bản mã là y = (y1,y2). Ở đây, y1cũng như y2 đều là một tổ hợp tuyến
tính của x1và x2. Chẳng hạn, có thể lấy
y1 = 11x1+ 3x2
y2 = 8x1+ 7x2
Tất nhiên có thể viết gọn hơn theo ký hiệu ma trận như sau
Nói chung, có thể lấy một ma trận K kích thước m m làm khoá. Nếu một phần
tử ở hàng i và cột j của K là ki,,j thì có thể viết K = (ki,,j), với x = (x1, x2, . . . ,xm)
P và K K , ta tính y = eK(x) = (y1, y2, . . . ,ym) như sau:
Nói một cách khác y = xK.
(y1 y2) = (x1 x2)
11 8
3 7
k1,1 k1,2 ... k1,m
k2,1 k2,2 ... k2,m
... ... ... . .
km,1 km,2 ... km,m
(y1,. . .,ym)=(x1, . ….,xm)
- -
20
1.2.4.2 Định nghĩa ( ma trận đơn vị)
Ma trận đơn vị m m (ký hiệu là Im ) là ma trận cấp m m có các số 1 nằm ở
đường chéo chính và các số 0 ở vị trí còn lại. Như vậy ma trận đơn vị 2 2 là:
Im được gọi là ma trận đơn vị vì AIm = A với mọi ma trận đơn vị là ma trận
vuông cấp m m tập ma trận vuông cấp m × m nghịch đảo dùng ma trận Tm × m
làm thành 1 nhóm nhân. Ma trận nghịch đảo của ma trận A cấp m m ( nếu tồn
tại) là ma trận A-1 sao cho AA-1 = A-1A = Im . Không phải mọi ma trận đều có
nghịch đảo, nhưng nếu tồn tại thì nó duy nhất.
Với các định nghĩa trên, có thể dễ dàng xây dựng công thức giải mã đã
nêu: Vì y = xK, ta có thể nhân cả hai vế của đẳng thức với K-1 và nhận được:
yK-1 = (xK)K-1 = x(KK-1) = xIm = x
1.2.4.3 Định nghĩa (Định thức của ma trận):
Định thức của ma trận A = (a,i j ) cấp 2 2 là giá trị
det A = a1,1 a2,2 - a1,2 a2,1
Một ma trận có nghịch đảo khi và chỉ khi định thức định thức của nó khác 0.
Tuy nhiên trên Z 26 một ma trận K có nghịch đảo khi và chỉ khi UCLN (det
K,26)= 1
1.2.4.4 Định lý (ma trận ngịch đảo):
Giả sử A = (ai j) là một ma trận cấp 2 2 trên Z26 sao cho det A = a1,1a2,2
–a1,2.a2,1#0.
Khi đó:
Ví dụ: Có 1 ma trận K
I2 = 1 0
0 1
A-1 = (det A)-1
a2,2 -a1,2
-a2,1 a1,1
K =
11 8
3 7
- -
21
det K = 11x7 – 8x3 mod 26 = 77 – 24 mod 26 = 53 mod 26 = 1
Vậy ma trận K có nghịch đảo.
1.2.4.5 Định nghĩa Mật mã Hill
Hình 1.5 Mật mã HILL
Vi dụ 1.5
Từ các tính toán trên ta có:
Giả sử cần mã hoá bản rõ "July". Ta có hai phần tử của bản rõ để mã hoá: (9,20)
(ứng với Ju) và (11,24) (ứng với ly). Ta tính như sau:
Bởi vậy bản mã của July là DELW. Để giải mã Bob sẽ tính :
Như vậy Bob đã nhận được bản đúng.
Giả sử khóa K = 11 8
3 7
K-1 = 7 18 23 11
(9,20) 11 8 3 7 = (99+60, 72+140) = (3,4)
(11,24) 11 8 3 7 = (121+72, 88+168) = (11,22)
(11,22) 7 18 23 11 = (11,24)
Cho m là một số nguyên dương có định. Cho P = C = (Z26 )m và cho
K = { các ma trận khả nghịch cấp m m trên Z26}
Với một khoá K K ta xác định
eK(x) = xK
và dK(y) = yK -1
Tất cả các phép toán được thực hiện trong Z26
- -
22
1.2.5. Mã chuyển vị (Transposition):
Ý tưởng của MHV là giữ các ký tự của bản rõ không thay đổi nhưng sẽ
thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này. MHV (còn được
gọi là mã chuyển vị) đã được dùng từ hàng trăm năm nay.
Định nghĩa Mã hoán vị
Ví dụ 1.6
Giả sử m = 6 và khoá là phép hoán vị =(1 2 3 4 5 6 )
Khi đó phép hoán vị ngược -1 sẽ là: -1=(1 2 3 4 5 6 )
Bây giờ giả sử có bản rõ
Shesellsseashellsbytheseashore
Trước tiên ta nhóm bản rõ thành các nhóm 6 ký tự:
shesel | lsseas | hellsb | ythese | ashore
Bây giờ mỗi nhóm 6 chữ cái được sắp xếp lại theo phép hoán vị , ta có:
EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS
Như vậy bản mã là
EESLSH SALSES LSHBLE HSYEET HRAEOS
Để giải bản mã này ta dùng phép hoán vị -1.
Thực tế mã hoán vị là trường hợp đặc biệt của mật mã Hill. Khi cho phép
(3,4) 7 18 23 11 = (9,20)
Cho m là một số nguyên dương xác định nào đó. Cho P = C = (Z26 )m và
cho K gồm tất cả các hoán vị của {1, . . ., m}. Đối một khoá ( tức là một
hoán vị) ta xác định
e(x1, . . . , xm ) = (x(1), . . . , x(m))
và d(x1, . . . , xm ) = (y -1(1), . . . , y -1(m))
trong đó -1 là hoán vị ngược của
- -
23
hoán vị của tập {1, . . . ,m}, ta có thể xác định một ma trận hoán vị m m
thích hợp K = { ki,j} theo công thức:
( ma trận hoán vị là ma trận trong đó mỗi hàng và mỗi cột chỉ có một số "1", còn
tất cả các giá trị khác đều là số "0". Ta có thể thu được một ma trận hoán vị từ
ma trận đơn vị bằng cách hoán vị các hàng hoặc cột).
Dễ dàng thấy rằng, phép mã Hill dùng ma trận K trên thực tế tương
đương với phép mã hoán vị dùng hoán vị . Hơn nữa K-1= K -1 tức ma trận
nghịch đảo của K là ma trận hoán vị xác định theo hoán vị -1. Như vậy, phép
giải mã Hill tương đương với phép giải mã hoán vị.
Đối với hoán vị được dùng trong ví dụ trên, các ma trận hoán vị kết hợp
là:
ki,j=
1 nếu j = (i)
0 với các trường hợp còn lại
K =
0 0 1 0 0 0
0 0 0 0 0 1
1 0 0 0 0 0
0 0 0 0 1 0
0 1 0 0 0 0
0 0 0 1 0 1
và K-1 =
0 0 1 0 0 0
0 0 0 0 1 0
1 0 0 0 0 0
0 0 0 0 0 1
0 0 0 1 0 0
0 1 0 0 0 0
- -
24
CHƯƠNG 2. CHUẨN MÃ DỮ LIỆU (DES)
Các hệ mật mã truyền thống được trình bày ở chương 1 có một số ưu
điểm là mã hóa và giải mã bằng thủ công được thực hiện rất dễ dàng , việc trao
đổi khóa mã cũng đơn giản bằng thủ công hoặc bằng qui ước. Song với lượng
thông tin quá phong phú như hiện nay và với mạng truyền thông như hiện nay
thì mật mã thủ công vừa không đảm bảo bí mật lại việc mã hóa quá chậm khó tự
động hóa mã và giải mã .Mặt khác các thuật toán mã hóa thủ công đòi hỏi phải
tuyệt đối dữ bí mật…Như vậy mật mã thủ công đòi hỏi bảo mật cả thuật toán mã
hoa svaf cả khóa mã.
Sau nhưng năm 70 của thế kỷ trước, các nhà toán học đã nghiên cứu và
tạo ra nhiều phương thức mật mã với tốc độ mã hóa rất nhanh (hàng chục thậm
chí hàng trăm kilo Byte trong một giây) và người ta chỉ cần giữ bí mật khóa mã
và mã hóa được mọi dữ liệu tùy ý. Đó là một bước tiến vĩ đại của kỹ thuật mật
mã .Trong đó mã DES (Data Encryption Standard) là một điển hình của bước
tiến này. Chương này, em muốn mô phỏng mã hóa và giải mã của thuật toán
DES.
2.1 MÔ TẢ DES (Data Encryption Standard)
DES mã hoá một xâu bít x:
Bản rõ x độ dài 64 bit.
khoá k độ dài 56 bít.
Bản mã y nhận được cũng là một xâu bít có độ dài 64 bit.
Thuật toán tiến hành theo 3 giai đoạn:
1.Với bản rõ cho trước x, một xâu bít x0 sẽ được xây dựng bằng cách hoán
vị các bít của x theo phép hoán vị cố định ban đầu IP.
Ta viết:x0= IP(X) = L0R0,
trong đó L0 gồm 32 bít đầu và R0 là 32 bít cuối.
2. Sau đó tính toán 16 lần lặp theo một hàm xác định. Ta sẽ tính LiRi, 1 i
16 theo quy tắc sau:
Li = Ri-1
Ri = Li-1 f(Ri-1,Ki)
trong đó
- -
25
kí hiệu cộng theo modulo 2 của hai xâu bít.
f là một hàm mà của Ri-1,Ki mô tả sau.
Ki là các xâu bít độ dài 48 được tính như hàm của khoá K. ( trên
thực tế mỗi Ki là một phép chọn hoán vị bít trong K).
3. Áp dụng phép hoán vị ngược IP -1 cho xâu bít R16L16, ta thu được bản
mã y. Tức là y=IP -1 (R16L16).
Hình 2.1. Một vòng của DES
2.2 Các bước thực hiện:
2.2.1 Cách tính biến x0: Hoán vị biến x theo phép hoán vị ban đầu IP(X)
x0= IP(X) = L0R0
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 31 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
Li-1 Ri-1
A
J
f
Ki
+
Li Ri
- -
26
63 55 47 39 31 23 15 7
Theo bảng này có nghĩa là bít thứ 58 của x là bít đầu tiên của IP(x); bít thứ 50
của x là bít thứ hai của IP(x), bit ở vị trí thứ 7 là bit cuối của IP(x)
2.2.2 Cách tính LiRi: Để tính LiRi trước hết ta phải xác định hàm f
2. 2.2.1. Các biến trong hàm f: có hai biến vào
+ Biến thứ nhất A là xâu bít độ dài 32,
+ Biến thứ hai J là một xâu bít độ dài 48.
+ Đầu ra của f là một xâu bít độ dài 32. Hàm f thực hiện theo các
bước sau:
Bước 1:Xác định biến thứ nhất (biến A):
Xâu bit của Ri-1 được mở rộng thành một xâu bít có độ dài 48 theo một hàm mở
rộng cố định E.
- -
27
E(Ri-1) gồm 32 bít của Ri-1 (được hoán vị theo cách cố định) với 16 bít
xuất hiện hai lần. Theo bảng Ebit ở vị trí thứ 32 là bit đầu tiên của E(Ri-1), ở vị
trí thứ 1 là bit thứ 2 và bit cuối của E(Ri-1).
Bước 2:Xác định biến thứ hai (biến J) :
Biến j thực chất là phép hoán vị và dịch vòng của xâu bit khóa k,
Thuật toán tạo 16 khóa con k 1 , k 2 ,…….. k16 ,
Bảng chọn E bít
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
- -
28
Theo sơ đồ trên việc xác định Ki được thực hiện theo 03 bước sau:
Bước 1. Với khóa K 64 bit cho trước hoán vị các bít của K theo
phép hoán vị cố định PC-1. Ta viết:
PC-1(K) = C0D0
Khi thực hiện hoán vị K theo PC-1 thi chỉ còn lại 56 bit. Trong đó C0 là
28 bit đầu và D0 là 28 bit cuối.
PC-1
K
PC-1
C0 D0
LS1 LS1
C1 D1 PC-2 K1
.
.
LS16 LS16
C16 D16 PC-2 K16
- -
29
57 49 41 33 25 17
1 58 50 42 34 26
10 2 59 51 43 35
19 11 3 60 52 44
63 55 47 39 31 23
7 62 54 46 38 30
14 6 61 53 45 37
21 13 5 28 20 12
Bước 2: Ta tính Ci Di Với i thay đổi từ 1 đến 16:
Ci = LSi(Ci-1)
Di = LSi(Di-1)
LSi là phép dịch vòng (dịch trái):
+ Với i = 1, 2, 9, 16 dịch trái 1 bước
+ Với i còn lại dịch trái 2 bước
Bước 3: Sau khi tìm được Ci Di ta thực hiện phép hoán vị PC-2
thu được Ki
PC-2 được dùng trong bảng khoá là:
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
- -
30
2.2.2.2 Cách tính hàm f:
Ta có sơ đó tính hoạt động của hàm f(Ri-1,Ki):
Ki
Sau khi mở rộng Ri-1 bởi hàm mở rộng E để chuyển Ri-1 gồm 32 bít thành E(Ri-1)
gồm 48 bít, E(Ri-1) cộng XOR với khóa Ki cho ra là:
E(Ri-1) + Ki = B = B1 B2 ….. B8
B gồm 48 bít được phân thành 8 khối như nhau và mỗi block Bi , i= 1,8 có độ dài
6 bít.
Sau đó , mỗi Bi được đưa vào hộp Si , i= 1,8 và biến đổi để cho đầu ra là Ci gồm
4 bít (i= 1,8).Sự biến đổi này hoạt động như sau:
Giả sử Bi gồm 6 bít là Bi=bi1bi2…bi6.Khi đó ,bi1 và bi6 được nhập thành cặp bi1bi6
được chuyển thành số thập phân từ 0 đến 3.Ví dụ:
bi1bi6=00→0
bi1bi6=01→1
bi1bi6=10→2
bi1bi6=11→3.
Còn bi2bi3bi4bi5 của Bi được chuyển thành số thập phân từ 0 đến 15 như sau:
P
F(Ri-1,Ki)
Ri-1
E(Ri-1)
Cộng XOR
S1 S2 S3 S4 S5 S6 S7 S8
B1 B2 B3 B4 B5 B6 B7 B8
C1 C2 C3 C4 C5 C6 C7 C8
48 bít 48 bít
- -
31
bi2 bi3 bi4 bi5 số tự nhiên
0 0 0 0 1
0 0 0 1 2
0 0 1 0 3
0 0 1 1 4
0 1 0 0 5
0 1 0 1 6
0 1 1 0 7
0 1 1 1 8
1 0 0 0 9
1 0 1 0 10
1 0 1 1 11
1 1 0 0 12
1 1 0 1 13
1 1 1 0 14
1 1 1 1 15
Số nguyên dương ri← bi1bi6 và si← bi2bi3bi4bi5 chính là tọa độ (hoành tung) của
ma trận Si từ ti chuyển thành Ci=Ci1Ci2Ci3Ci4 với Cijє{0,1} i= 1,8 và j= 1,4 .
Vậy đầu ra của 8 hộp S là:
C1,C2,….,C8 mỗi Ci gồm gồm 4 bít tạo thành khối C= C1 C2….C8 gồm 32 bít. 32
bít này được đưa vào ma trận chuyển vi P để cho đầu ra cũng là 32 bít . Đó là
đầu ra của hàm f(Ri-1,Ki).
Ta có thể trình bầy cụ thể cách tính hàm f như sau:
Với xâu bít có độ dài 6bit (Kí hiệu Bi = b1b2b3b4b5b6), ta tính Sj(Bj) như
sau: Hai bít b1b6 xác định biểu diễn nhị phân của hàng r của Sj ( 0 r 3) và
bốn bít (b2b3b4b5) xác định biểu diễn nhị phân của cột c của Sj ( 0 c 15 ). Khi
đó Sj(Bj) sẽ xác định phần tử Sj(r,c); phần tử này viết dưới dạng nhị phân là một
- -
32
xâu bít có độ dài 4. ( Bởi vậy, mỗi Sj có thể được coi là một hàm mã mà
đầu vào là một xâu bít có độ dài 2 và một xâu bít có độ dài 4, còn đầu ra là một
xâu bít có độ dài 4). Bằng cách tương tự tính các Cj = Sj(Bj), 1 j 8.
Thật vậy mỗi chuỗi B là một chuỗi 6 bit trong đó bit đầu và bit cuối được
dùng để xác định vị trí của hàng trong phạm vi từ 0 đến 3 (hoặc từ 00 đến 11)
bốn bit giữa dùng để xác định vị trí của cột trong phạm vi từ 0 đến 15 (hoặc từ
0000 đến 1111). Sau khi xác định được vị trí của hàng và cột ta đối chiếu trong
bảng S được một số thập phân quy đổi số thập phân đó ra gia trị nhị thân ta được
Cj .
Ví dụ: Bit đầu vào của B là B = 100110.
Bit đầu và cuối là “10” cho ta thứ tự của hàng là 2 bốn bít giữa là “0011”
cho ta thứ tự của cột là 4. Đối chiếu với hộp S1 xuất hiện só 14, chuyển 14 sang
nhị phân 14 = 1110. Vậy S(B) = S(100110) = 1110.
Tám hộp S là:
S1
14 4 13 1 2 15 11 8 3 10 3 12 5 9 1 7
1 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
- -
33
S3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 5 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S6
12 1 10 15 9 2 6 8 0 13 3 4 14 7 15 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 11 7 6 0 8 13
- -
34
S7
4 11 12 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
Sau khi thực hiện các phép đối chiếu hộp S ta được các giá trị SiBi
Tính hàn f =P (S1(B1) = S2(B2) …………. S8(B8) thực hiện theo phép hoán vị P
Phép hoán vị P có dạng:
P
16 7 20
29 12 28
1 15 23
5 18 31
32 27 3
19 13 30
22 11 4
Theo bảng p thì bit thứ 16 và bit thứ 7 của xâu bit Sj(Bj) là bit thứ nhất và bít
thứ 2 của hàm f………
- -
35
LiRi được xác định theo công thức sau:
Li = Ri-1
Ri =Li-1 + f(Ri-1, Ki )
2.2.3 Xác định bản mã y: Sau khi xác định được LiRi ta thu được L16R16 vậy
bản mã y được xác định theo công thức
y = IP 1 ( L16 ,R16 )
IP -1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
Ví dụ:
Ta có bản rõ M = 0123456789ABCDEF
Khóa K = 133457799BBCDFF1.
Giải
Bước 1: Tìm x0= IP(X) = L0R0
M = 0000.0001. 0010.0011. 0100.0101. 0110.0111. 1000.1001. 1010.1011.
1100.1101. 1110.1111
8 16 24 32
L = 0000.0001. 0010.0011. 0100.0101. 0110.0111
40 48 56 64
- -
36
R = 1000.1001. 1010.1011. 1100.1101. 1110.1111
Thực hiện phép hoán vị IP
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 31 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
IP (M) = 1100.1100. 0000.0000. 1100.1100. 1111.1111. 1111.0000.
1010.1010. 1111.0000. 1010.1010
L0 = 1100.1100. 0000.0000. 1100.1100. 1111.1111
R0 = 1111.0000. 1010.1010. 1111.0000. 1010.1010
Bước 2: xác định khóa Ki
K = 0001.0011. 0011.0100. 0101.0111. 0111.1001. 1001.1011. 1011.1100.
1101.1111. 1111.1001
Hoán vị khóa K theo phép hoán vị PC-1 ta thu được PC-1(K):
- -
37
PC-1
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
PC-1(K) = 1111000 0110011 0010101 0101111 0101010 1011001 1001111
000111
C 0 = 1111000 0110011 0010101 0101111
D 0 = 0101010 1011001 1001111 0001111
Tìm C i D i :
C i D i = C i-1 D i-1 dịch trái 1 lần : với i = 1, 2, 9, 16
= C i-1 D i-1 dịch trái 2 lần : với i còn lại
C 1 = 1110000 1100110 0101010 1011111
D 1 = 1010101 0110011 0011110 0011110
C 2 = 1100001 1001100 1010101 0111111
D 2 = 0101010 1100110 0111100 0111101
C 3 = 0000110 0110010 1010101 1111111
D 3 = 0101011 0011001 1110001 1110101
C 4 = 0011001 1001010 1010111 1111100
D 4 = 0101100 1100111 1000111 1010101
C 5 = 1100110 0101010 1011111 1110000
- -
38
D 5 = 0110011 0011110 0011110 1010101
C 6 = 0011001 0101010 1111111 1000011
D 6 = 1001100 1111000 1111010 1010101
C 7 = 1100101 0101011 1111110 0001100
D 7 = 0110011 1100011 1101010 1010110
C 8 = 0010101 0101111 1111000 0110011
D 8 = 1001111 0001111 0101010 1011001
C 9 = 0101010 1011111 1110000 1100110
D 9 = 0011110 0011110 1010101 0110011
C 10 = 0101010 1111111 1000011 0011001
D 10 = 1111000 1111010 1010101 1001100
C 11 = 0101011 1111110 0001100 1100101
D 11 = 1100011 1101010 1010110 0110011
C 12 = 0101111 1111000 0110011 0010101
D 12 = 0001111 0101010 1011001 1001111
C 13 = 0111111 1100001 1001100 1010101
D 13 = 0111101 0101010 1100110 0111100
C 14 = 1111111 0000110 0110010 1010101
D 14 = 1110101 0101011 0011001 1110001
C 15 = 1111100 0011001 1001010 1010111
D 15 = 1010101 0101100 1100111 1000111
C 16 = 1111000 0110011 0010101 0101111
D 16 = 0101010 1011001 1001111 0001111
Hoán vị C i D i theo phéo hoán vị PC-2 ta thu được K i
- -
39
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
K 1 = 000110 110000 001011 101111 111111 000111 000001 110010
K 2 = 011110 011010 111011 011001 110110 111100 100111 100101
K 3 = 010101 011111 110010 001010 010000 101100 111110 011001
K 4 = 011100 101010 110111 010110 110110 110011 010100 011101
K 5 = 011111 001110 110000 000111 111010 110101 001110 101000
K 6 = 011000 111010 010100 111110 010100 000111 101100 101111
K 7 = 111011 001000 010010 110111 111101 100001 100010 111100
K 8 = 111101 111000 101000 111010 110000 010011 101111 111011
K 9 = 111000 001101 101111 101011 111011 011110 011110 000001
K 10 = 101100 011111 001101 000111 101110 100100 011001 001111
K 11 = 001000 010101 111111 010011 110111 101101 01110 000110
K 12 = 011101 010111 000111 110101 100101 000110 01111 101001
K 13 = 100101 111100 010111 010001 111110 101011 101001 000001
K 14 = 010111 110100 001110 110111 111100 101110 011100 111010
K 15 = 101111 111001 000110 001101 001111 010011 111100 001010
K 16 = 110010 110011 110110 001011 000011 100001 011111 110101
- -
40
Bước 3: Tìm hàm f(Ri-1,Ki)
Ta tính : Ki + E (Ri-1) = B1 B2 B3 B4 B5 B6 B7 B8 Tìm E (Ri-1): hoán vị Ri-1 theo
phép hoán vị E
Bảng chọn E bít
32 1 2 3 4 5
4 5 6 7 8 9
9 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
25 25 26 27 28 29
28 29 30 31 32 1
Với R0 = 1111.0000. 1010.1010. 1111.0000. 1010.1010
Ta có E(R0 ) = 011110 100001 010101 010101 011110 100001 010101
010101.
K 1= 000110 110000 001011 101111 111111 000111 000001 110010
K 1 + E(R0 ) = 011000 010001 011110 111010 100001 100110 010100
100111 = B1 B2 B3 B4 B5 B6 B7 B8
Tính S1(B1) = S1(011000) thực hiện hoán vị S1(B1) theo phép hoán vị S1
S1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 3 12 5 9 1 7
1 1 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
- -
41
Bit đầu và bit cuối là “00” cho ta hàng 0
Bốn bít giữa “ 1100” = 12 cho ta cột 12
Chiếu hàng 0 cột 12 vào bảng S1 cho ta giá trị là 5 = “0101”
Vậy S1(011000) = “0101”.
Tính S2(B2) = S2(010001) thực hiện hoán vị S1(B1) theo phép hoán vị S1
S2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
Bit đầu và bit cuối là “01” cho ta hàng 1
Bốn bít giữa “1000” = 8 cho ta cột 8
Chiếu hàng 1 cột 8 vào bảng S2 cho ta giá trị là 12 = “1100”
Vậy S2(010001) = “1100”.
Tính tương tự ta có S1(B1) = S2(B2) = S3(B3) = S4(B4) = S5(B5) = S6(B6) = S7(B7)
= S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111.
Tính hàn f =P (S1(B1) = S2(B2) …………. S8(B8) thực hiện theo phép hoán vị P
P
16 7 20
29 12 28
1 15 23
5 18 31
32 27 3
19 13 30
- -
42
22 11 4
f =P (S1(B1) = S2(B2) …………. S8(B8) = P (0101 1100 1000 0010 1011 0101
1001 0111) = 0010 0011 0100 1010 1010 1001 1011 1011
R1 = L0 + f (R0,K1 ) = 1100 1100 0000 0000 1100 1100 1111 1111
+ 0010 0011 0100 1010 1010 1001 1011 1011
= 1110 1111 0100 1010 0110 0101 0100 0100
Tương tự ta tính: R2 = L1 + f (R1,K2 )
.
.
.
R16 = L15 + f (R15,K16 )
Ta thực hiên 16 lần vòng lặp thu được R16 L16
L16 = 0100 0011 0100 0010 0011 0010 0011 0100
R16 = 0000 1010 0100 1100 1101 1001 1001 0101
R16 L16 = 0000 1010 0100 1100 1101 1001 1001 0101 0100 0011
0100 0010 0011 0010 0011 0100
Thực hiện phép hoán vị ngược IP (IP 1 )
IP -1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
- -
43
Mã hóa
- Cho bản rõ x
- x 0 = IP(x) = L 0 R 0
- i=1, 2, 3……16
L i =R 1i
R i =L 1i ^f(R 1i ,k i )
- Y 0 = (R 16 L 16 )
- Y = IP 1 (Y 0 )
Giải mã
- Cho bản mã Y
- Y 0 = IP(y) = R 16 L 16 =L 0 ’R 0 ’
- i=1, 2, 3……16
L i ’=R 1i ’
R i ’=L’ 1i ^f(R’ 1i ,k i17 )
- x 0 = (R’ 16 L’ 16 )
- x = IP 1 (x 0 )
ta được IP 1 = 10000101 11101000 00010011 01010100
00001111 00001010 10110100 00000101. Chuyển IP 1 sang dạng hexa tta thu
được bản mã : 85E813540F0AB405
2.3 Giải mã DES
Tương Tự như mã hóa, để giải mã một chuỗi kỹ tự đã bị mã hóa ta cũng
làm tương tự theo các bước như trên, tuy nhiên hệ thống khóa lúc này đã được
tạo theo chiều ngược lại.
2.3.1 Thuật toán
2.3.2 Chứng minh thuật toán
Có bản mã Y
Y 0 = IP(y)= IP(IP 1 (R 16 L 16 ))= R 16 L 16 =L’ 0 R’ 0
Vậy L’ 0 =R 16 ; R’ 0 =L 16 ;
Với i=1
L’ 1 =R’ 0 =L 16 =R 15 ;
R’ 1 = L’ 0 f(R’ 0 ,K 16 )= R 16 f(L 16 K 16 )
= L 15 f(R 15 , K 16 ) f(R 15 ,K16 )=L 15 ;
- -
44
Tóm lại:
L’ 1 =R 15 ; R’ 1 =L 15 ;
- -
45
Y
IP x
E
Y 0
R 1i L 1i
+
B
K i17
K
C 0 D 0
LS i 1iC
C i
PC-2 k
qi
B 1 B 2 B 8
S 1
C 1
+
P
L i R i
L 16 R 16 IP(Y) X
S 2 S 8
C 2 C 8
- -
46
Từ đó ta thấy , thuật toán giải mã chỉ khác với thuật toán mã hoá ở chỗ tạo hệ
thống khoá ,nếu mã hoá tạo khoá từ k 1 ,k 2 ,…,k 16 thì giải mã tạo hệ thống khoá
từ k 16 ,k15 ,…,k 1 .Việc này được trình bày cụ thể trong hình sơ đồ giải mã DES.
2.4 Các vấn xung quanh DES
2.4.1 Những ý kiến phản hồi
Khi DES được đề nghị như một tiêu chuẩn thì đã có những lời phê bình ,sự
phản hồi có liên quan đến các hộp S. Tất cả các sự tính toán trong DES, ngoại
trừ các hộp S, đều là tuyến tính. Các hộp S, thành phần phi tuyến trong hệ thống
mật mã là sống còn đối với sự an toàn của hệ thống. tuy nhiên , tiêu chuẩn thiết
kế của hộp S chưa được hiểu hết, một số người gợi ý rằng những hộp S này có
chưa được hiểu hết, một số , một số người gợi ý rằng những hộp S này có thể
chứa đựng những cửa sập còn ẩn dấu ở đâu đó.Những cửa sập này có thể cho
phép cục an ninh quốc gia giải mã các thông điệp trong khi người dùng vẫn cho
rằng hệ hệ thống này an toàn. Tất nhiên khó có thể phản đối lại lời tuyên bố này
nhưng chưa có bằng chứng nào được đưa ra để chỉ rõ rằng trong thực tế các cửa
sập tồn tại trong DES.Năm 1976, cục an ninh quốc gia Hoa Kỳ tuyên bố rằng
những đặc tính của các hộp S là tiêu chuẩn thiết kế:
- Mỗi một dòng của một hộp S là sự lặp lại của các số nguyên từ 0 đến 15.
- Không có hộp S nào có tuyến tính hay là hàm Affine của các đầu vào.
- Thay đổi một bit đầu vào của hộp s gây ra ít nhất hai bit đầu ra thay đổi.
- Đối với bất kì một hộp S và bất kì đầu vào x ,S x và S 001100^x gây ra sự
khác biệt ở ít nhát là hai bit 9x ở đây là một chuỗi bit có độ dài 6)
Hai đặc tính khác của hộp S được thiết kế như là được điều khiển bởi các tiêu
chuẩn thiết kế của Cục an ninh quốc gia;
- Đối với bất kì một hộp S nào, bất kỳ x đầu nào và đối với e,f{0,1},S x
S 0011efx
- Đối với bất kì một hộp S nào , nếu một bit đầu vào là cố định và ta xem giá trị
của bit đầu ra cố định, số đầu vào làm cho đầu ra =0 sẽ gần với số đầu vào làm
cho cho số đầu ra =1 (lưu ý rằng nếu ta cố định giá trị của bit 1 va bit 16 thì sẽ
có 16 đầu vào lam cho một bit đầu ra cụ thể =0 và 16 đầu vào làm cho một bit
- -
47
đầu ra cụ thể =1. Đối với lần thứ 2 thông qua các bit đầu vào thứ 5 thì
điều này sẽ không đúng nhưng gần đúng. Cặn kẽ hơn với bất kì hộp S nào nếu
như giá trị
của bất cứ bit đầu vào nào là cố định thì số đầu vào mà nhờ đó bất cứ bit đầu ra
cố định nào có giá trị là 0 hoặc 1 thì luôn luôn nằm giữa 13 và 19 ).Lời chỉ chích
thích đáng nhất về DES là kích cỡ của không gian khoá 2 56 là khoá nhỏ để trở
lên an toàn. Những máy có mục đích đặc biệt khác nhau được đệ trình cho tấn
công bản rõ, mà nó thực hiện chủ yếu tìm kiếm khoá. Đó là đưa ra bản rõ x gồm
64 bit và một bản tương đương y, thì mỗi một khoá có thể có lớn hơn một khoá
k là E k x =y được tìm thấy (lưu ý rằng có thể lớn hơn một khoá k0.
Đầu năm 1977, Diffie và Hellman đề nghị rằng một người có thể xây dựng
một chíp VLSL có thể kiểm tra được 10 6 khoá một giây. Một máy với 10 6 khoá
cóthể tìm kiếm toàn bộ không gian khoá trong một ngày. Họ dự tính rằng máy
này được xây dựng với giá khoảng 20 triệu USD.
Tại hội nghị CRYPTO’93 (phần kéo dài ), Michael Wiener đưa ra một thiết
kế rất chi tiết về một máy dò khoá . Máy này dưạ trên một chip dò khoá được
nối truyền liên tiếp , vì vậy 16 mã hoá đươcj diễn ra đồng thời. Chip này có thể
kiểm tra 5.10 7 khoá một giây và có thể được xây dựng sử dụng cônh nghệ hiện
thời với giá 10,5 USD một chip. Một khung bao gồm 5760 chip, có thể được xây
dựng với giá 1triệu USD nhưng giảm thời gian dò trung bình xuống còn 3.5giờ.
2.4.2 DES trong thực tế
Ngay cả khi việc mô tả DES khá dài dòng thì DES được thực hiện rất hiệu
quả trong cả phần cứng lẫn phần mềm.Những tính toán số học duy nhất được
thực hiện là phép XOR của các chuỗi bit. Việc mở rộng hàm E các hộp S, sự
hoán vị IP và P, và việc tính toán k 1 ,k 2 ,..,k16 tất cả được thực hiện trong thời
gian ngắn bởi bảng tìm kiếm trong phần mềm hoặc cách nối dây cứng chúng vào
một mạch. Những thi hành phần cứng hiện thời có thể dạt tốc độ mã hoá cực
nhanh,công ty thiết bị số thông báo tại CRYPTO’92 rằng họ vừa mới chế tạo
được một chip với 50k Transistors có thể mã hoá với tốc độ 1GB/s sử dụng một
đồng hồ tốc độ là 250MHz. Giá của chip này khoảng 300USD.Năm 1991 có 45
phần cứng và chương trình cài sẵn thi hành DES đã được uỷ ban tiêu chuẩn quốc
gia Mĩ phê chuẩn.
Một ứng dụng rất quan trọng của DES là ứng dụng vào việc giao dịch ngân
hàng sử dụng cấ tiêu chuẩn được hiệp hội các ngân hàng Mĩ phát triển. DES
- -
48
được sử dụng để mã hoá các con số, nhận dạng các nhân (PÍN) và trao đổi
tài khoản được máy thu ngân tự động thực hiện (ÁTM).DES cũng được Clearing
Hourse Interbank System (CHIPS) sử dụng để trao đổi có liên quan đến trên
1,510 12 USD/tuần.
DES cũng được sử dụng rộng rãi trong các tổ chức chính phủ như: Bộ năng
lượng, bộ tư pháo và hệ thống phản chứng liên bang.
2.4.3. Một vài kết luận về mã DES
Có rất nhiều phương pháp mã hoá để đảm bảo an toàn dữ liệu. Để đánh giá
tính ưu việt một giải thuật mã hoá ,người ta thường dựa vào các yếu tố:Tính bảo
mật, độ phức tạp, tốc độ thực hiện giải thuật và vấn đề phân khoá trong môi
trường nhiều người sử dụng.
Hiện nay phương pháp mã hoá DES được sử dụng rộng rãi nhất. Các chíp
chuyên dụng DES được thiết kế nhằm tăng tốc độ sử lý của DES. Rất nhiều nhà
toán học, tin học đã bỏ nhiều công nghiên cứu trong nhiều năm nhằm tìm cách
phá vỡ DES (tức là tìm ra cách giải mã trong khoảng thời gian ngắn hơn thời
gian cần để thử lần lượt tát cả các khoá ). Ngoại trừ việc tìm ra bốn khoá yếu và
12 khoá tương đối yếu cho tới nay chưa có một thông báo nào về việc tìm ra
cách phá vỡ phương pháp mã hoá này. Để phá vỡ DES bằng phương pháp “vét
cạn” thử tất cả các khoá trong không gian khoá cần có một khoản tiền lớn và đòi
hỏi một khoảng thời gian dài.
Nhược điểm của DES nó là thuật toán mã hoá đối xứng. Khi phương pháp
này mới được tìm ra ý tưởng thực hiện 50.000 tỷ phép mã hoá cần thiết để vượt
mặt DES bằng cách thử lần lượt các khoá có thể là điều không thể làm được
nhưng ngày nay với sự phát triển mạnh của phần cứng liệu độ dài 56 bit đã đủ
chưa? Và các phép thay thế đã đủ phức tạp chưa ? để đạt được độ an toàn thông
tin mong muốn, đó là vấn đề người ta vẫn đang bàn luận.
Tuy vậy , DES đã được phân tích kĩ lưỡng và công nhận là vững chắc. Các
hạn chế của nó đã được hiểu rõ và có thể xem xét trong quá trình thiết kế và để
tăng độ an toàn hơn, ngày nay các hệ thống mã hoá sử dụng DES mở rộng
(DESX), được ứng dụng rộng rãi. Với DES mở rộng khoá có thể là 128 bit,…
độ lớn khối có thể là 128 bit. Do vậy độ an toàn mở rộng của DES cao hơn rất
nhiều.
- -
49
CHƯƠNG 3. CÁC SƠ ĐỒ CHIA SẺ BÍ MẬT
3.1 Khái niệm về chia sẻ bí mật:
Thông tin cần giữ bí mật được chia thành nhiều mảnh và giao cho nhiều người,
mỗi người giữ một mảnh. Thông tin này có thể được xem lại, khi mọi người giữ
các mảnh nhất trí. Các mảnh khớp lại để được tin gốc.
- Thông tin cần giữ bí mật được chia thành nhiều mảnh và trao cho mỗi thành
viên tham gia nắm giữ.
Thông tin bí mật Các mảnh được chia
- Khi các mảnh được khớp lại sẽ cho ta tín hiệu gốc
Các mảnh được chia Thông tin bí mật
- -
50
3.2 Sơ đồ chia sẻ bí mật
Bài toán: Trong một ngân hàng có một két phải mở hàng ngày. Ngân hàng sử
dụng ba thủ quỹ lâu năm nhưng họ không tin bất kỳ người nào. Bởi vậy họ cần
thiết kế một hệ thống sao cho bất kì hai thủ quỹ nào cũng có thể mở đuợc két
song riêng từng người một không thể mở được. Vấn đề này có thể giải quyết
được bằng lược đồ chia sẻ bí mật
3.2.1 Khái niệm “Sơ đồ chia sẻ bí mật”:
Sơ đồ chia sẻ bí mật là một phương thức để chia sẻ bí mật ra nhiều phần, sau đó
phân phối cho một tập hợp những người tham gia sao cho các tập con trong số
những người này được chỉ định, có khả năng khôi phục lại bí mật bằng cách kết
hợp dữ liệu của họ.
Một sơ đồ chia sẻ bí mật là hoàn hảo, nếu bất kì một tập hợp những người tham
gia mà không được chỉ định, sẽ không thu được thông tin về bí mật.
3.2.2 Định nghĩa:
Cho t, w là các số nguyên dương, tw. Một sơ đồ ngưỡng A(t,w) là một
phương pháp phân chia khóa K cho một tập w thành viên (kí hiệu là P) sao cho t
thành viên bất kì có thể tính được K nhưng không một nhóm (t-1) thành viên nào
có thể làm được điều đó.
Giá trị K được chọn bởi một thành viên đặc biệt được gọi là người phân phối
(D). DP
D phân chia khóa K cho mỗi thành viên trong P bằng cách cho mỗi thành viên
một thông tin cục bộ gọi là mảnh. Các mảnh được phân phát một cách bí mật để
không thành viên nào biết được mảnh được trao cho các thành viên khác.
Một tập con các thành viên B P sẽ kết hợp các mảnh của họ để tính khóa K
(cũng có thể trao các mảnh của mình cho một người đáng tin cậy để tính khóa
hộ).
Nếu B t thì họ có khả năng tính được K.
Nếu B < t thì họ không thể tính được K.
Gọi P là tập các giá trị được phân phối khóa K: P = wipi 1:
K là tập khóa: tập tất cả các khóa có thể
- -
51
S tập mảnh: tập tất cả các mảnh có thể
Sau đây ta trình bầy một sơ đồ ngưỡng được gọi là sơ đồ ngưỡng Shamir
Hình 3.1. Sơ đồ ngưỡng Shamir
Trong sơ đồ ngưỡng Shamir D xây dựng một đa thức ngẫu nhiên a(x) có bậc tối
đa là t-1.
Trong đa thức này hằng số là khóa K. Mỗi thành viên p i sẽ có một điểm
(x i ,y i ).
Ta xét một tập con B gồm t thành viên tạo lại khóa K bằng 2 phương pháp:
+ Phép nội suy đa thức.
+ Công thức nội suy lagrange.
Tạo lại khóa K bằng phương pháp sử dụng phép nội suy đa thức:
Giả sử các thành viên P i , muốn xác định khóa K.
Ta biết rằng: y
ji = a (x i ).
Giai đoạn khởi tạo:
1. D chọn w phần tử khác nhau và khác không trong Z p và kí hiệu
chúng là x i , 1 i w ( w p + 1).
Với 1 i w , D cho giá trị x i cho p i . Các gí trị x i là công khai
Phân phối mảnh:
2. Giả sử D muốn phân chia khóa K Z p . D sẽ chọn một cách bí mật
(ngẫu nhiên và độc lập) t-1 phần tử của Z p , a 1 ,…..,a 1t
3. Với 1 i w, D tính y i = a(x i ), trong đó
a(x) = K + pxa j
t
j
j mod
1
1
4. Với 1 i w, D sẽ trao mảnh y i cho p i
- -
52
Trong đó a(x i ) là một đa thức bí mật đươc D chọn.Vì a(x) có bậc lớn
nhất là t-1 nên có thể viết như sau:
a(x) = a 0 + a 1 x + ……+a 1t x 1t
Ta có hệ các phương trình tuyến tính (trong Zp) như sau:
a 0 + a 1 x 1i +a 2 x ……+a 1t x 1ti
1t = y
1i
a 0 + a 1 x 2i +a 2 x 2i ……+a 1t x ti
1t = y
2i
.
.
.
a 0 + a 1 x ti +a 2 x ti ……+a 1t x tit
1t = y
ti
trong đó hệ số a 0 , a 1 …a 1t là các phần tử chưa biết của Zp, còn a 0 = K là khóa.
Vì y i = a(x i ) nên B có thể thu được t phương trình tuyến tính t ẩn (a 0 , a 1
……a 1t ), ở đây tất cả các phép tính số học đều được thực hiện trên Zp.
Nếu các phương trình này độc lập tuyến tính thì sẽ cho ta nghiệm duy nhất và
thu được giá trị khóa a 0
Sau đây chúng tôi trình bày một thủ tục (protocol) chia sẻ bí mật dựa trên ý
tưởng của Languange:
Giả sử ta có n thực thể A1,A2,…,An-1 và có 1 người được ủy quyền B biết
được toàn bộ khóa bí mật S є N.
Người được ủy quyền B thực hiện các bước sau đây:
(1) B chọn một số nguyên tố P đủ lớn sao cho: . Với
(2) B tiếp theo chọn 2n-1 số một cách ngẫu nhiên :
Trong đó :
(3) B xác định một đa thức với các hệ số trên :
- -
53
(4) Bây giờ B gửi cho Aj (một cách công khai )
cặp coi như mảnh riêng của Aj
Khôi phục bí mật S:
Tất cả n người A 1 ,…,A n có thể hợp tác lại để khôi phục lại bí mật S bằng cách
.
Khi đó dễ dàng xác định được S = g(0)
Ta có định lý sau:
n thực thể kết hợp với nhau thì có thể khôi phục bí mật S một cách có hiệu quả
đó là: S = g(0) = f(0)
Chứng minh :
Thật vậy ,dễ thấy rằng g x là hàm nội suy Lagrange của hàm f x là một đa
thức có cấp bé hơn n và g thỏa mãn điều kiện:g(v j )=f(v j ) với 0 j<n
Do đó, f-g là đa thức trên Z p có cấp bé hơn n , nhưng nó lại có ít nhất là n
nghiệm khác nhau: là các số r thỏa mãn f r -g r =0.chứng tỏ rằng f a =g a
aZ p đặc biệt f 0 =g 0 =S.Đó là điều cần chứng minh.
Sau đây, tôi xin lấy một số ví dụ cụ thể:
Ví dụ 1: Có 3 người A1, A2, A3 muốn chia sẻ bí mật S = 472
Cho p=1999 công khai.
A chọn v0 = 626, v1 = 674, v2 = 93.
a1 = 334, a2 =223
Tính
Áp dụng công thức trên với S = 472 ta có:
A1 có cặp
- -
54
A2 có cặp
A3 có cặp
3 người hợp lại sẽ xác định được S:
Áp dụng công thức trên ta tính được:
b0 =1847
b1 =1847
b2 =1847
Ví dụ 2
Cho số p=342853815608923 (Đây là 1 số nguyên tố được lấy trong bảng các số
nguyên tố từ cuốn “The Art of Programing” của Knut(Vol 2)
n=3.ta có
a 1 =53958111706386.
a 2 =151595058245452
v 0 =111350135012507
v 1 =207244959855905
v 2 =20545949133543
giả sử bí mật là S=151595058245452
Tính f(v0) = 109351520587519
f(v1) = 174675701531216
f(v2) = 117471713218253
Đặt
- -
55
Ta có
b0 = 266921901220910
b1 = 129147516050688
b2 =289638215946249
Ta tính được S’ =151595058245452. S’ trùng với khóa bí mật đã cho.
3.3 Cấu trúc truy nhập và sơ đồ chia sẻ bí mật
Trong phần trước, ta mong muốn rằng t thành viên bất kỳ trong w thành
viên có khả năng xác định được khóa. Tình huồng tổng quát hơn là phải chỉ rõ
một cách chính xác các thành viên có khả năng xác định khóa và những tập con
không có khả năng này.
Ký hiệu:
- P là tập gồm m thành viên được chia mảnh công khai x i .
- Γ là một tập các tập con của P, các tập con trong Γ là các tập con các thành
viên có khả năng tính khóa.
+ Γ được gọi là một cấu trúc truy nhập
+ Các tập con trong Γ được gọi là các tập con hợp thức
Ví dụ:
Chìa khóa để mở két bạc là chìa khóa số được chia thành 3 mảnh khóa, có 3 thủ
quỹ là P 1 , P 2 , P 3 . Mỗi thủ quỹ giữ một mảnh khóa. Chỉ có thủ quỹ P 1 và P 2
hoặc P 2 và P 3 khi khớp 2 mảnh khóa của họ với nhau thì sẽ nhận được chìa
khóa gốc để mở két bạc.
Các tập con hợp thức là các tập con có thể mở khóa: {P 1 , P 2 }, {P 2 , P 3 }.
Vậy Γ là: {P 1 , P 2 }, {P 2 , P 3 }
3.3.1 Định nghĩa sơ đồ chia sẻ bí mật hoàn thiện
Một sơ đồ chia sẻ bí mật hoàn thiện thể hiện cấu trúc truy nhập Γ là phương
pháp chia sẻ khóa K cho một tập w thành viên (được ký hiệu là P) thỏa mãn hai
tính chất sau:
1. Nếu một tập con hợp thức các thành viên BP góp chung các mảnh
của họ thì họ có thể xác định được giá trị của K.
- -
56
2. Nếu một tập con không hợp thức các thành viên BP
góp chung các mảnh của họ thì họ không thể xác định được khóa K.
Ví dụ:
Trong sơ đồ Shamir A(t, m) thể hiện cấu trúc truy nhập sau:
Γ ={ BP: /B/}
Vậy sơ đồ Shamir là sơ đồ chia sẻ bí mật hoàn thiện.
Chú ý: “Tập trên” của một “tập hợp thức” sẽ là “tập hợp thức”
Giả sử B Γ và BCP, giả sử tập con C muốn K
Vì B là một tập con hợp thức nên nó có thể xác định được K.
Tập con C có thể xác định được khóa K bằng cách bỏ qua các mảnh (tin) của các
thành viên trong B.C.
Tức là: Nếu B Γ và BCP, thì C Γ.
3.3.2 Định nghĩa tập hợp thức” tối thiểu
Nếu Γ là một cấu trúc truy nhập thì B Γ được gọi là “ tập hợp thức” tối
thiểu nếu AB, A B thì A Γ. Nói cách khác B là “tập hợp thức” nhỏ nhất
trong Γ.
Tập các tập con hợp thức tối thiểu của Γ ký hiệu là Γ 0 và được gọi là cơ sở của
Γ .Vì Γ chứa tất cả các tập con của P là tập trên của một tập con trong cơ sở
Γ 0 nên Γ được xác định một cách duy nhất như một hàm của Γ 0 .
Biểu diễn về mặt toán học ta có:
Γ ={ CP; BC, B Γ 0 }
3.4 Mạch đơn điệu:
Một phương pháp đẹp và đơn giản về mặt khái niệm do Benaloh và leichter đưa
ra. Ý tưởng ở đây là xây dựng một mạch đơn điệu “ghi nhận” cấu trúc truy nhập
và sau đó xây dựng một sơ đồ chia sẻ bí mật trên cơ sở xây dựng mô tả về mạch.
Ta gọi đó là cấu trúc mạch đơn điệu.
3.4.1 Định nghĩa( mạch đơn điệu):
Một mạch Boolean C với w đầu vào x 1 ,……x w ( tương ứng với w thành
viên P 1 ……P w ) và một đầu ra y.
- -
57
Mạch này gồm các cổng “hoặc” và các cổng “và” không có bất kỳ một cổng
“phủ định” nào một mạch nhue vậy gọi là mạch đơn điệu.
Mạch được phép có số đầu vào tùy ý nhưng chỉ có 1 đầu ra (tức là một cổng có
thể có nhiều dây vào nhưng chỉ có một dây ra).
Xây dựng mạch đơn điệu:
Nếu Γ là một tập đơn điệu các tập con ủa P thì dễ dàng xây dựng được một
mạch đơn điệu C sao cho Γ(C) = Γ.
Giả sử Γ 0 là cơ sở của Γ . Khi đó ta xây dựng công thức Boolean dang tuyển
hội sau:
C = 0B ( BPi P i )
Ví dụ:
Nếu trong tập các thành viên {P 1 , P 2 , P 3 } có tập cơ sở
Γ 0 = {{ P 1 , P 2 },{ P 2 , P 3 }}
Ta thu được công thức Boolean sau:
C = (P 1 P 2 )( P 2 P 3 )
3.4.2 Chia sẻ Khóa bí mật dựa vào “ mạch đơn điệu”
Thuật toán thực hiện phép gán một giá trị f(W) K cho mỗi dây W trong mạch
C.
+ Đầu tiên, dây ra W out của mạch sẽ được gán giá trị khóa K.
+ Thuật toán sẽ được lặp lại một số lần cho đến khi mỗi dây có một giá trị gán
vào nó.
+ Cuối cùng, mỗi thành viên P i sẽ được một danh sách các giá trị f(W) sao cho
W là một dây vào của mạch có đầu vào x i .
Thuật toán “chia sẻ” khóa K
1. f(W out ) = K
2. While tồn tại một dây W sao cho f(W) không xác định DO
- -
58
Begin
3. Tìm cổng G của C sao cho f(Wg) được xác định, Wg là dây ra của G
nhưng f(W) không được xác định với bất kỳ dây nào của G.
4. If G là cổng “hoặc” Then f(W)=f(Wg) với mỗi dây vào W của G
Else ( G là cổng “và”)
Cho các dây vào của G là W 1 ,…….,W t
Chọn độc lập, ngẫu nhiên t-1 phần tử của Zm và ký hiệu chúng là:
Y 1g ,…….,Y 1gt
End;
5. For 1 im Do f(W i ) = Y g
Ví dụ:
Giả sử K là khóa`.Giá trị K sẽ được đưa tới mỗi một trong 3 đầu vào của cổng
“hoặc” cuối cùng. Γiếp theo ta xét cổng “và” ứng với mệnh đề P 1
^ P 2 ^ P 4 .Ba dây vào sẽ được gán các giá trị tương ứng là a 1 , a 2 ,K - a 1 -a 2 ,ở
đây tất cả các phép tính đều thực hiện trên Z m . Tương tự , ba dây vào tương ứng
với P 1 ^P 3 ^P 4 sẽ được gán các giá trị b 1 ,b 2 ,K-b 1 -b 2 .Cuối cùng hai dây vào
tương ứng với P 2 ^P 3 sẽ được gán các giá trị c 1 ,K-c 1 .Chú ý rằng a 1 ,a 2 ,b 1 ,b 2
và c 1 đều là các biến ngẫu nhiên độc lập trong Z m .Nếu nhìn vào các mảnh mà 4
thành viên nhận được thì ta có:
1. P 1 nhân a 1 ,b 1
2. P 2 nhân a 2 ,c 1
Hình 3.2 Một mạch đơn điệu
- -
59
3.P 3 nhân b 2 ,K-c 1
4.P 4 nhân K-a 1 -a 2 ,K-b 1 -b 2
Như vậy , mỗi thành viên sẽ nhân hai phân tử trong Z m làm mảnh của mình .
Ta sẽ chứng tỏ răng sơ đồ này là hoàn thiện .Trước tiên ta kiểm tra thấy
răng mỗi tập con cơ sở có thể tính được K . Tập con hợp thức {P 1 ,P 2 ,P 4 } có
thể tính :
K= a 1 + a 2 + (K-a 1 -a 2 ) mod m
Tập con {P 1 ,P 3 ,P 4 } có thể tính :
K= b 1 +b 2 +(K-b 1 -b 2 ) mod m
Cuối cùng tập con {P 2 ,P 3 } có thể tính :
K= c 1 + (K-c 1 ) mod m
Như vậy , mọi tập con hợp thức đều có thể tính được K, do đó ta sẽ hướng
sự chú ý tới các tập con không hợp thức .Chú ý là ta không cần phải xem xét tất
cả các tập con không hợp thức . Chẳng hạn ,nếu B 1 và B 2 là hai tập con không
hợp thức (B 1 B 2 ) và B 2 không thể tính được K thì B 1 . Cũng không thể tính
được K. Ta định nghĩa tập con B P là một tập con không hợp thức tối đa nếu
B 1 P đối với mọi B 1 B , B 1 B .Điều này dẫn đến kết luận là chỉ cần
kiểm tra thấy không một tập con không hợp thức tối đa nào có thể xác định được
một chút thông tin nào về khóa K là được .Ở đây các tập con không hợp thức tối
đa là :
{P 1 ,P 2 },{P 1 ,P 3 },{ P 1 , P 4 },{ P 2 , P 4 },{ P 3 , P 4 }.
^
x 1 x 2 x 3 x 4
K-b 1 -
b
a 1 a 2
K-c 1
b 2
K-a 1 -a 2
c 1
K
K K
^ ^
^
K
- -
60
Trong mỗi trường hợp ,dễ dàng thấy rằng K không thể tính được ; hoặc do
thiếu một mảnh thông tin ngẫu nhiên cần thiết nào đó hoặc do tất cả các mảnh
có từ một tập con đều ngẫu nhiên .ví dụ tập con {P 1 ,P 2 } chỉ có các giá trị ngẫu
nhiên a 1 ,b 1 , a 2 ,c 1 .Một ví dụ khác ,tập con { P 3 , P 4 } có mảnh b 2 ,K-c 1 , K-a 1 -
a 2 , K-b 1 -b 2 . Vì các giá trị c 1 ,a 2 ,a 1 và b 1 là các giá trị ngẫu nhiên chưa biết
nên k không thể tính được .trong mỗi trường hợp có thể , mỗi tập con không hợp
thức đều không có chút thông tin gì về giá trị của K .
- -
61
CHƯƠNG 4. ỨNG DỤNG THUẬT TOÁN DES VÀ LƯỢC
ĐỒ CHIA SẺ BÍ MẬT VÀO THI TUYỂN SINH
4.1 Các ứng dụng:
Ta có thể áp dụng thuật toán DES và sơ đồ chia sẻ bí mật và rất nhiều ứng
dụng chẳng hạn trong đấu, trong mã thẻ ATM, trong thi tuyển sinh…
Ở đây ta nghiên cứu một ứng dụng là trong thi tuyển sinh, vậy có một bài
toán được đưa ra là: trong một kỳ thi nơi ra đề thi và nơi tổ chức thi ở cách
xa nhau, ta phải thực hiện việc chuyển để thi từ nơi ra đề tới nơi tổ chức thi
sao cho đảm bảo về tính bảo mật.
4.2 Quy trình thực hiện giải bài toán:
4.2.1 Sơ đồ:
Khóa DES gồm 56 bit tương đương với một số nguyên gồm 20 chữ số thập
phân. Con số bí mật này không quá lớn đối với bài toán bài toán chia sẻ bí mật.
Cho nên việc tính toán là rất hiệu quả
Đề thi (bản rõ)
Mã hóa
Bản mã
Khóa K
Mã hóa
Giải mã
Bản rõ
Nơi ra đề thi
Nơi ra đề thi
- -
62
4.2.2 Các bước thực hiện:
Theo sơ đồ trên ta phải thực hiện theo các bước sau:
- Nơi ra đề thi:
+ Bản rõ (đề thi)
+ Mã hóa bản rõ
+ Tạo khóa K
+ Mã hóa khóa K
+ Gửi bản mã
- Nơi tổ chức thi:
+ Nhận bản mã (đề thi, khóa K)
+ Giải bản mã
Mã hóa bản rõ (đề thi): Dùng bảng mã ASCII mở rộng để chuyển bản rõ từ rạng
ký tự sang Hexa sau đó dùng thuật toán DES để mã hóa.
Tạo khóa K: Dùng dãy ký tự dạng số hoặc dạng chữ, nhóm 8 ký tự thành 1
nhóm sau đó dùng 56 bít để mã hóa.
Gửi bản tin: Dựa vào lược đồ chia sẻ bí mật chia khóa K thành 3 hoặc 4 mảnh
sau đó gửi độc lập các mảnh khóa cho từng thành viên (ở nới tổ chức thi), mỗi
thành viên giữ một mảnh khóa.
Nơi tổ chức thi nhận bản mã: Mỗi thành viên nhận được một mảnh khóa và bản
mã đề thi, các thành viên gom các mảnh khóa lại với nhau thành một khóa hoàn
chỉnh sau đó thực hiện việc giải mã đề thi
Sau đây là chương trình mô phỏng “ chia sẻ bí mật bằng ngôn ngữ C.
- -
63
4.2.3. Mô phỏng lược đồ chia sẻ bí mật bằng ngôn ngữ C:
Chương trình gồm có 5 phần:
Hình 4.1 Giao diện chương trình
4.2.3.1 Chia sẻ khoá bí mật theo giao thức “chia sẻ bí mật” Shamir.
void giaothuc::chiakhoa()
{
int h;
cout>k;
cout>p;
cout>m;
cout>t;
cout<<”\n Nhap gia tri xi de chao cho moi thanh vien P:”;
for(i=1;i<=m;i++)
{
cout>x[i];
}
cout<<”\n Nhap bi mat t-1 phan tu trong Zp”;
for(j=1;j<t;j++)
{
cout>a[j];
}
for(i=1;i<=m;i++)
{1=0;
for(j=1;j<t;j++)
{
- -
64
h=pow(x[i],j);
1=1+a[j]*h;
}
y=k+1;
cout<<”\n Manh y”<<i<<” trao cho thanh vien P”<<i<<” la:”<<y;
}
}
Hình 4.3, 4 Chia sẻ khóa bí mật theo giao thức Shamir
4.2.3.2 Khôi phục khoá bí mật bằng phương pháp giải hệ phương trình tuyến
tính
void giaothuc::giaihekhoiphuckhoa()
{
int n,m,v,b;
float mx=0,g,e,c,gt,h;
- -
65
float G[max] [max] [max],H[max] [max],A[max] [max],B[max]
[max],M[max] [max];
cout>p;
cout>n;
cout<<”\n Nhap gia tri xi da chao cho moi thanh vien P:”;
for(j=0;j<n;j++)
{
cout>x[j];
}
cout<<”\n Nhap cac manh khoa da chao cho moi thanh vien P:”;
for(1=0;<n;1++)
{
cout>B[1] [0];
}
for(i=0;i++)
{
for(j=0;j<n;j++)
{
A[i] [j]=pow(x[i],j);
}
}
cout<<”\n He phuong trinh tuyen tinh la:\n”;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(j<n-1)
{
cout<<A[i] [j]<<”a”<<j<<”+”;
}
if(j==n-1)
{
cout<<A[i] [j]<<”a”<<j;
}
}
cout<<”=”<<B[i] [j];
cout<<”\n”;
}
cout<<”\n Vay nghiem cua he phuong trinh la:”;
for(e=0;e<=n;e++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
- -
66
{
G[i] [j]=A[i] [j];
}
}
for(j=0;j<n;j++)
{
if(j==e-1)
{
For(i=0;i<n;i++)
{
G[i] [j]=B[i] [0];
}
}
}
i=0;t=0;
while(t<n-1)
{
if(G[i] [j]==0)
{
for(j=1;j<n;j++)
if(G[j] [i]>mx)
{
mx=G[j] [i];
v=j;
}
for(j=0;j<n;j++)
{ g=G[i] [j];
G[i] [j]=-G[v] [j];
G[v] [j]=g;
}
}
if(G[i] [i]!=0)
{
for(k=i+1;k<n;k++)
{ c=G[k] [i]/G[i] [i];
h=c+(G[k] [i]-c*G[i] [i])/G[i] [i];
for(j=0;j<n;j++)
{
G[k] [j]=G[k] [j]*h;
}
}
i++;
}
t=t+1;
- -
67
}
gt=1;
for(i=0;i<n;i++)
{
gt=gt*G[i] [i];
}
if(e==0)
{
1=gt;
}
else
{
b=gt/1;
if(b0)
{
cout<<”\n a”<<e<<”=”<<b;
if(e==1)
{
cout<<”\n Khoa duoc khoi phuc lai la K=a1=”<<b;
}
}
}
}
}
- -
68
Hình 4,5: Khôi phục khóa bí mật bằng phương pháp giải hệ phương trình
tuyến tính.
4.2.3.3 Khôi phục khoá bí mật bằng phương pháp dùng công thức nội suy
Lagrange
void giaothuc::congthuckhoiphuckhoa()
{
float m,n,b;
cout>p;
cout>t;
cout<<”\n Nhap gia tri xi da chao cho moi thanh vien P:”;
for(j=1;j<=t;j++)
{
cout>x[j];
}
cout<<”\n Nhap cac manh khoa da chao cho moi thanh vien P”;
for(j=1;j<=t;j++)
{
cout>g[j];
}
k=0;
for(1=1;1<=t;1++)
{ m=1;
for(j=1;j<=t;j++)
{ if(j!=1)
{ b=x[j]-x[1];
n=x[j]/b;
- -
69
m=m*n;
}
}
K=k+g[1]*m;
}
cout<<”\n vay khoa bi mat khoi phuc lai la:”<<k;
}
Hình 6,7: Khôi phục khóa bí mật bằng phương pháp dùng công thức nội suy
Lagrange.
4.2.3.4 Chia sẻ khoá bí mật theo phương pháp bằng mạch đơn điệu
void giaothuc::machchiakhoa()
{ int n,m,h[max],e;
char ten[32];
cout>m;
- -
70
cout>k;
cout>n;
for(j=1;j<=n;j++)
{
cout>t;
cout<<”\n Trong hop thuc”<<j<<” cac manh khoa cua tung thanh vien la:\n”;
for(i=1;i<t;i++)
{
cout<<”\n Nhap ten thanh vien thu”<<i<<” la: “;gets(ten);
cout<<”\n Nhap manh khoa trao cho tung thanh vien thu “<<i<<” la
:”;cin>>h[i];
}
cout<<”\n Nhap ten thanh vien thu “<<t<<” la: “;gets(ten);
for(i=1;i<t;i++)
{
e=k-h[i];
}
cout<<”\n Manh khoa trao cho tung thanh vien thu “<<t<<” trong hop thuc
la:\n”<<e;
}
}
- -
71
Hình 7,8: Chia sẻ khóa bí mật bằng mạch đơn điệu
4.2.3.4 Khôi phục khoá bí mật theo phương pháp mạch đơn điệu
void giaothuc::machphuckhoa()
{
int h;
cout>t;
cout<<”\n Nhap cac manh khoa da chao cho moi thanh vien P:”;
for(j=0;j<t;j++)
{
cout>g[j];
}
h=0;
for(j=0;j<t;j++)
{
h=h+g[j];
}
cout<<”\n Khoa can tim la:”<<h;
}
- -
72
Hình 9: Khôi phục khóa bí mật theo giao thức mạch đơn điệu
4.3 Mã nguồn mở của chương trình
Sau đây là mã nguồn của chương trình thử nghiệm:
#include
#include
#include
#include
const int max=30;
class giaothuc
{
private :
int m,t,y,p;
float k;
int x[max],a[max],g[max];
int i,j,l;
public :
void chiakhoa();
void giaihekhoiphuckhoa();
void congthuckhoiphuckhoa();
void machchiakhoa();
void machphuckhoa();
};
//====================================================
void giaothuc::chiakhoa()
{
int h;
- -
73
cout>k;
cout>p;
cout>m;
cout>t;
cout<<”\n nhap gia tri xi de chao cho moi thanh vien p:”;
for(i=1;i<=m;i++)
{
cout>x[i];
}
cout<<”\n Nhap bi mat t-1 phan tu trong Zp”;
for(j=1;j<t;j++)
{
cout>a[j];
}
for(i=1;i<=m;i++)
{ 1=0;
for(j=1;j<t;j++)
{
h=pow(x[i],j);
1=1+a[j]*h;
}
y=k+1;
cout<<’\n Manh y”<<i<<” trao cho thanh vien P”<<i<<” la:”<<y;
}
}
//===================================================
void giaothuc::giaihekhoiphuckhoa()
{
int n,m,v,b;
float mx=0,ge,c,gt,h;
float G[max] [max],H[max] [max],A[max] [max],B[max] [max],M[max]
[max];
cout>p;
cout>n;
cout<<’\n Nhap gia tri xi da chao cho moi thanh vien P:”;
for(j=0;j<n;j++)
{
cout>x[j];
}
cout<<”\n Nhap cac manh khoa da chao cho moi thanh vien P:”;
for(1=0;1<n;1++)
{
- -
74
cout>B[1] [0];
}
for(i=0;i,n;i++)
{
for(j=0;j<n;j++)
{
A[i] [j]=pow(x[i] ,j);
}
}
cout<<”\n He phuong trinh tuyen tinh la;\n”;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(j<n-1)
{
cout<<A[i] [j]<<”a”<<j<<”+”;
}
if(j==n-1)
{
cout<<A[i] [j]<<”a”<<j;
}
}
cout<<”=”<<B[i] [0];
cout<<”\n”;
}
cout<<”\n Vay nghiem cua he phuong trinh la:”;
for(e=0;e<=n;e++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
G[i] [j]=A[i] [j];
}
}
for(j=0;j<n;j++)
{
if(j==e-1)
{
for(i=0;i<n;i++)
{
G[i] [j]=B[i] [j];
}
- -
75
}
}
i=0;t=0;
while(t<n-1)
{
if(G[i] [j]==00
{
for(j=0;j<n;j++)
if(G[j] [i]>mx)
{
mx=G[j] [i];
v=j;
}
for(j=0;j<n;j++)
{ g=G[i] [j];
G[i] [j]=-G[v] [j];
G[v] [j]=g;
}
}
if(G[i] [j]!=0)
{
for(k=i+1;k<n;k++)
{ c=G[k] [i]/G[i] [i];
h=c+(G[k] [i]-c*G[i] [i])/G[i] [i];
for(j=0;j<n;j++)
{
G[k] [j]=G[k] [j]-G[i] [j]*h;
}
}
i++;
}
t=t+1;
}
gt=1;
for(i=0;i<n;i++)
{
gt=gt*G[i] [i];
}
if(e==0)
{
1=gt;
}
else
{
b=gt/1;
- -
76
if(b0)
{
cout<<”\n a”<<e<<’=”<<b;
if(e==1)
{
cout<<”\n Khoa duoc khoi phuc lai la K=a1=”<<b;
}
}
}
}
}
//==================================================
void giaothuc::congthuckhoiphuckhoa()
{
float m,n,b;
cout>p;
cout>t;
cout<<”\n Nhap gia tri xi da chao cho moi thanh vien P:”;
for(j=1;j<=t;j++)
{
cout>x[j];
{
cout<<”\n Nhap cac manh khoa da chao cho moi thanh vien P:”;
for(j=1;j,=t;j++)
{
cout>g[j];
}
k=0;
for(1=1;1<=t;1++)
{ m=1;
for(j=1;j<=t;j++)
{ if(j!=1)
{ b=x[j]-x[1];
n=x[j]/b;
m=m*n;
}
}
k=k+g[1]*m;
}
cout<<”\n Vay khoa bi mat khoi phuc lai la: “<<k;
}
//=================================================
- -
77
void giaothuc::machphuckhoa()
{
int h;
cout>t;
cout<<”\n Nhap cac mach khoa da chao cho moi thanh vien P:”;
for(j=0;j<t;j++)
{
cout>g[j];
}
h=0;
for(j=0;j<t;j++)
{
h=h+g[j];
}
cout<<”\n Khoa can tim la:”<<h;
}
//=================================================
void giaothuc::machchiakhoa()
{ int n,m,h[max],e;
char ten[32];
cout>m;
cout>k;
cout>n;
for(j=1;j<=n;j++)
{
cout>t;
cout<<”\n Trong hop thuc “<<j<<” cac manh khoa cua tung thanh vien
la:\n”;
for(i=1;i<t;i++)
{
cout<<”\n Nhap ten thanh vien thu “<<i<<” la: “;gest(ten);
cout<<’\n Nhap manh khoa trao cho thanh vien thu “<<i<<” la
:”;cin>>h[i];
}
cout<<”\n Nhap ten thanh vien thu “<<t<<” la:”;gest(ten);
for(i=1;i<t;i++)
{
e=k-h[i];
}
cout<<”\n Manh khoa trao cho tung thanh vien thu “<<t<<” trong hop thuc
la:\n”<<e;
}
}
- -
78
//============ CHUONG TRINH CHINH ============
void main()
{
clrscr()
int chon;
giaothuc g;
do
{
cout<<”\n\n\n\n MENU CHUONG TRINH “ ;
cout <<”\n======================================\n”;
cout<<”\n 1.Chia se khoa bi mat. “;
cout<<”\n 2.Khoi phuc khoa bang phuong phap giai he phuong trinh
tuyen tinh.”;
cout<<”\n 3.Khoi phuc khoa bang phuong phap dung cong thuc noi suy
Langrangre.”;
cout<<”\n 4.Chia se khoa bi mat bang mach don dieu,”;
cout<<”\n 5.Khoi phuc khoa bang mach don dieu.”;
cout<<”\n 0.Thoat khoi chuong trinh.”;
cout>chon;
switch(chon)
{
case 1:clrscr();g.chiakhoa();break;
case 2:clrscr();g.giaihekhoiphuckhoa();break;
case 3:clrscr();g.congthuckhoiphuckhoa();break;
case 4:clrscr();g.machchiakhoa();break;
case 5:clrscr();g.machphuckhoa();break;
}
}while(chon!=0);
getch();
}
- -
79
KẾT LUẬN
Các ứng dụng trên mạng máy tính ngày càng trở nên phổ biến, thuận lợi và quan
trọng thì yêu cầu về an toàn mạng, về an ninh dữ liệu càng trở nên cấp bách và
cần thiết.
Thuật toán mã hóa được ứng dụng trong rất nhiều lĩnh vưc như: xác thực người
dùng, chữ ký số, mã hóa và xác thực dữ liệu….
Kết quả của luận văn gồm hai phần chính:
1. Tìm hiểu lý thuyêt:
Luận văn nghiên cứu lý thuyết về mật mã, thuật toán DES và lược đồ chia
sẻ bí mật
2. Phần ứng dụng:
Luận văn đề cập tới vấn đề ứng dụng thuật toán DES và lược đồ chia sẻ bí
mật vào thi tuyển sinh. Mô phỏng lược đồ chia sẻ bí mật bằng ngôn ngữ C
Hạn chế luận văn đề cập tới phần lý thuyết nhiều hơn những ứng dụng .
Phần ứng dụng chưa được áp dụng trong thực tế do đó không tránh khỏi
những thiếu sót, rất mong được sự góp ý của độc giả để luận văn của tôi
được hoàn thiện hơn.
- -
80
TÀI LIỆU THAM KHẢO
Tiếng Việt:
1.Douglas (1994) Mật mã lý thuyết và thực hành. Người dịch Nguyễn Bình
2. Phan Đình Diệu (2002). Lý thuyết mật mã và an toàn thông tin.NXB Đại học
quốc gia Hà Nội.
3. Lê Thị Sinh (2010) Nghiên cứu một số mô hình đảm bảo an ninh cơ sở dữ
liệu và thử nghiệm ứng dụng, luận văn thạc sĩ Công nghệ thông tin, tr 28 – 35, Trường
Đại học công nghệ - Đại học Quốc gia Hà Nội
4.Dương Anh Đức (2008). Mã hóa và ứng dụng. NXB Đại học Quốc gia
TPHCM.
5. Nguyễn Viết Kính (2007) Mã hóa. Bài giảng cho học viên cao học Trường
Đai học công nghệ - Đai học Quốc gia Hà Nội.
Các file đính kèm theo tài liệu này:
- LUẬN VĂN- NGHIÊN CỨU LƯỢC ĐỒ CHIA SẺ BÍ MẬT VÀ ỨNG DỤNG CỦA CHÚNG VÀO VIỆC THI TUYỂN SINH ĐẠI HỌC.pdf