Bài giảng Lý thuyết mật mã và an toàn thông tin: Mật mã cổ điển - Vũ Đình Hòa

Chia sẻ: Gió Biển | Ngày: | Loại File: PDF | Số trang:48

Thêm vào BST

Báo xấu

167
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Lý thuyết mật mã và an toàn thông tin: Mật mã cổ điển" cung cấp cho người đọc các kiến thức: Mật mã dịch chuyển - Shift cipher, mật mã thay thế - Substitution cipher, mật mã tuyến tính Affine cipher, mật mã Vigenère, mật mã Hill,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Lý thuyết mật mã và an toàn thông tin: Mật mã cổ điển - Vũ Đình Hòa

MẬT MÃ CỔ ĐIỂN
1.1 MỘT SỐ HỆ MẬT MÃ ĐƠN GIẢN 1.1.1 MẬT MÃ DỊCH CHUYỂN - SHIFT CIPHER 1.1.2 MẬT MÃ THAY THẾ - SUBSTITUTION CIPHER 1.1.3 MẬT MÃ TUYẾN TÍNH - AFFINE CIPHER 1.1.4 MẬT MÃ VIGENÈRE 1.1.5 MẬT MÃ HILL 1.1.6 MẬT MÃ HOÁN VỊ 1.1.7 MẬT MÃ DÒNG
MỞ ĐẦU: Mục đích cơ bản của hệ mật mã cho phép hai người, Alice và Bob, truyền thông tin qua một kênh không được bảo mật theo cách sao cho đối thủ, Oscar, không thể hiểu được thông tin gì đang được nhắc đến. Kênh đó có thể là đường điện thoại hoặc có thể là mạng máy tính. Thông điệp mà Alice muốn gửi tới Bob, chúng ta gọi là “ văn bản gốc ” hoặc “ bản rõ ” ( “ Plaintext ”), được xây dựng hoàn toàn tuỳ ý, có thể là các ký tự tiếng Anh, dữ liệu số…
Sơ đồ minh hoạ x y x Alice Mã hoá Giải mã Bob K K Tập các khoá
Mô tả hình thức bằng ký hiệu toán học
1.1.1 Hệ mã dịch chuyển Hệ mã dựa trên cơ sở của phép biến đổi một ký tự trong văn bản gốc thành một ký tự khác trong bản mã Trong trường hợp K=3 , hệ mật mã trên được gọi là mật mã Caesar , được thừa nhận là của Julius Caesar. Trong hệ mật mã Caesar , mỗi ký tự được thay thế bởi ký tự đứng sau nó ba vị trí trong bảng chữ cái Alphabet)
Để thực hiện theo phương pháp này, trước hết ta cần định nghĩa một bảng mã để số hoá văn bản gốc: A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25
Xét ví dụ Giả sử khoá K = 11, và văn bản gốc ban đầu là wewillmeetatmidnight Đầu tiên ta biến đổi văn bản gốc thành một dãy các số nguyên , kết quả nhận được như sau: 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 Tiếp theo, ta cộng 11 vào mỗi giá trị , sau đó quy các giá trị đó sang 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, ta biến đổi dãy số nguyên sang các ký tự Aphabet tương ứng như trên , nhận được bản mã HPHTWWXPPELEXTOYTRSE Để giải mã bản mã , Bob đầu tiên biến đổi tương ứng bản mã sang dãy của các số nguyên , rồi trừ từng giá trị trong dãy cho 11 ( sau đó quy đổi sang modulo 26), và cuối cùng biến đổi dãy số nguyên vừa nhận được sang các ký tự Alphabe.Ta thu được văn bản gốc ban đầu Wewillmeetatmidnight Nhận xét: Ta đã sử dụng ký tự hoa cho bản mã và ký tự thường cho văn bản gốc .
NHẬN XÉT Ta nhận xét rằng hệ mã dịch chuyển tính bảo mật không cao , chỉ với 26 khoá, rất dễ dàng để thử các quy tắc giải mã dK cho đến khi nhận được văn bản có “ ý nghĩa ”. Xem minh hoạ dưới đây : Ví dụ 1.2 Cho văn bản dưới dạng mật mã là xâu sau đây : JBCRCLQRWCRVNBJENBWRWN 9 1 2 17 2 11 16 17 22 2 17 21 13 1 9 4 13 1 22 17 22 13 Ta lần lượt thử các hàm giải mã d0 ,d1,… . Kết quả nhận được dưới đây :
jbcrclqrwcrvnbjenbwrwn K=0 iabqbkpqvbqumaidmavqvm K=1 hzapajopuaptlzhclzupul K=2 gyzozinotzoskygbkytotk K=3 fxynyhmnsynrjxfajxsnsj K=4 ewxmxglmrxmqiweziwrmri K=5 dvwlwfklqwlphvdyhvqlqh K=6 cuvkvejkpvkogucxgupkpg K=7 btujudijoujnftbwftojof K=8 a stitch in times saves nine K=9 k cdsdmr ….. K=10 Cuối cùng thử hết tới K=26, ta xác định được văn bản gốc và dừng lại. Khoá K= 9.
1.1.2 The Substitution Cipher ( Hệ mã thay thế )
Ví dụ : Cho hoán vị “ ngẫu nhiên ”  sau : 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 Do đó e (a)  X , e (b)  N ,... , Hàm giải mã là hoán vị nghịch đảo. Hãy mã hóa bản rõ: thisciphertextcannotbedecrypted
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 Do đó , d ( A)  d , d ( B)  l ,... Ví dụ giải mã đoạn bản mã sau : MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA Ta thu được thisciphertextcannotbedecrypted
Discrete Mathematics I Số nguyên Integer phép chia division Chương 2.4, 2.5 Kenneth H. Rosen Xuân 2008 Đại học FPT
Số nguyên GIỚI THIỆU Integer INTRODUCTION Giới thiệu Chúng ta sẽ học: Số nguyên •Phép chia hết: thương, số dư •Biểu diễn số nguyên theo cơ số: 10, 2, 8, 16 •Thuật toán cho các phép tính số nguyên •Số nguyên tố, hợp số •Ước chung lớn nhất, bội chung nhỏ nhất •Hàm Euler •Thuật toán Euclid
Số nguyên PHÉP CHIA Integer DIVISION Phép chia Định nghĩa Definition Cho hai số nguyên a, b với a ≠ 0, ta nói b chia hết cho a nếu tồn tại một số nguyên c sao cho b = a.c. Khi b chia hết cho a ta nói a là ước của b và b là bội của a và kí hiệu là a|b, nếu trái lại b không chia hết cho a thì ta kí hiệu a|b. a|b  cZ, (a.c =b) Định lí Theorem Cho 3 số nguyên a, b, c. Khi đó Nếu a|b và a|c thì a|(b + c). Nếu a|b thì a|bc, với mọi số nguyên c. Nếu a|b và b|c thì a|c.
Số nguyên PHÉP CHIA Integer DIVISION Phép chia Ví dụ Example 21 chia hết cho 3 vì tồn tại 7 để 21 = 3.7 Tập tất cả các bội của 2 là tập các số chẵn Tập tất cả các ước của 2 là {1, -1, 2, -2}
Số nguyên PHÉP CHIA Integer DIVISION Div, mod Định lí & định nghĩa Theorem & definition Cho a là một số nguyên và d là một số nguyên dương. Khi đó tồn tại duy nhất các số q và r, với 0  r < d sao cho a = qd + r. Với các kí hiệu như trên ta nói d là số chia, a là số bị chia, q được gọi là thương (q = a div d) và r được gọi là số dư (r = a mod d). Nhận xét: a chia hết cho d khi và chỉ khi số dư của phép chia a cho d bằng 0.
Số nguyên PHÉP CHIA Integer DIVISION Div, mod Thuật toán Algorithm procedure Chia(a  Z, d  N*) q: = 0 r: = |a| while r  d begin r: = r – d q: = q + 1 end if (a < 0 và r > 0) then begin r: = d – r q: = –(q + 1) end