Bài giảng Bảo mật thông tin - Bài 2: Mã hóa đối xứng cổ điển

Trình bày: Ths. Lương Trần Hy Hiến http://hienlth.info/hutech/baomatthongtin

1. Tổng quan về mã hóa

2. Tổng quan về các hệ mã đối xứng

3. Các hệ mã thay thế

4. Các hệ mã hoán vị

5. Nhận xét

2

3

(cid:1) It all started with

(cid:1) Encryption / Decryption

- plaintext

“ATTACK AT MIDNIGHT”

- ciphertext

“BUUBDL BU NJEOJHIU”

bla-bla

Shared Key

ciphertext msg

decoder

(ciphertext in

- plaintext out)

bla-bla

cmb-cmb

encoder (plaintext in - ciphertext out)

eavesdropper

(should understand nothing about the msg)

- to establish shared key

party you really meant to (cid:1) public (cid:1) private (cid:1) Signatures (cid:1) Hashing (cid:1) Certificates, PKI

(cid:1) Encryption/decryption – to hide info (cid:1) Key exchange (cid:1) Authentication – to establish shared key with the

(cid:1) plaintext: nội dung cần được mã hóa (cid:1) ciphertext: đã mã hóa (cid:1) encryption: quá trình mã hóa, chuyển từ plaintext sang

ciphertext

(cid:1) secret key: khóa dùng để mã hóa. Chú ý là khóa này cũng

dùng để giải mã. Vì vậy được gọi là mã hóa đối xứng (symmetric key cryptography).

(cid:1) decryption: giải mã (cid:1) cryptography: tất cả các lược đồ mã hóa và giải mã ngày nay (cid:1) block cipher: mã hóa một khối dữ liệu, cho ra một khối đã

được mã hóa

(cid:1) stream cipher: mã hóa liên tục dòng dữ liệu, thường là mỗi

byte một lần

(cid:1) Lịch sử mã hóa có từ trên 3.000 năm (cid:1) Đối tượng của mã hóa là các ký tự (cid:1) Việc mã hóa được thực hiện bằng phương pháp thủ

công hoặc sử dụng các nguyên lý cơ học

(cid:1) Ứng dụng phổ biến trong quân sự

(cid:1) Mã hóa cổ điển

(cid:1) Xuất hiện cùng với sự ra đời và phát triển của MTĐT

và CNTT

(cid:1) Xử lý bằng MTĐT với đơn vị là các bit (cid:1) Được ứng dụng rộng rãi trong nhiều lĩnh vực đặc biệt

là trong thương mại điện tử

(cid:1) Mã hóa hiện đại (Từ 1970)

– Bên gửi và bên nhận sử dụng chung một khóa – Còn gọi là

• Mã hóa truyền thống • Mã hóa khóa riêng / khóa đơn / khóa bí mật

– Là kỹ thuật mã hóa duy nhất trước những năm 70 – Hiện vẫn còn được dùng rất phổ biến • Mã hóa khóa công khai (bất đối xứng)

– Mỗi bên sử dụng một cặp khóa

• Một khóa công khai + Một khóa riêng

– Công bố chính thức năm 1976

• Mã hóa đối xứng

– Mã hóa khối

• Mỗi lần xử lý một khối nguyên bản và tạo ra khối bản mã

tương ứng (chẳng hạn 64 hay 128 bit)

– Mã hóa luồng

• Xử lý dữ liệu đầu vào liên tục (chẳng hạn mỗi lần 1 bit)

• Theo phương thức xử lý

– Mã hóa thay thế

• Chuyển đổi mỗi phần tử nguyên bản thành một phần tử bản

mã tương ứng – Mã hóa hoán vị

• Bố trí lại vị trí các phần tử trong nguyên bản

• Theo phương thức chuyển đổi

11

12

∈ E và hàm giải mã

∈ D. Mỗi ek: P → C và dk: C → P là các hàm thỏa

– P không gian bản rõ – C không gian bản mã – K không gian khóa – E giải thuật mã hóa – D giải thuật giải mã Với mỗi k ∈ K, tồn tại hàm lập mã ek dk dk(ek(x))=x với mỗi x ∈ P.

• Gồm có 5 thành phần, bộ năm (P, C, K, E, D)

• An toàn phụ thuộc vào sự bí mật của khóa,

không phụ thuộc vào sự bí mật của giải thuật

13

1. Thuật toán mã hoá mạnh. Có cơ sở toán học vững chắc đảm bảo rằng mặc dù công khai thuật toán, mọi người đều biết, nhưng việc thám mã là rất khó khăn và phức tạp nếu không biết khóa.

2. Khóa mật chỉ có người gửi và người nhận biết. Có kênh an toàn để phân phối khóa giữa các người sử dụng chia sẻ khóa. Mối liên hệ giữa khóa và bản mã là không nhận biết được.

14

• Là nỗ lực giải mã văn bản đã được mã hóa

không biết trước khóa bí mật • Có hai phương pháp phá mã

– Vét cạn

• Thử tất cả các khóa có thể

– Thám mã

• Khai thác những nhược điểm của giải thuật • Dựa trên những đặc trưng chung của nguyên bản hoặc một

số cặp nguyên bản - bản mã mẫu

• Về lý thuyết có thể thử tất cả các giá trị khóa cho

đến khi tìm thấy nguyên bản từ bản mã

• Dựa trên giả thiết có thể nhận biết được nguyên

bản cần tìm

• Tính trung bình cần thử một nửa tổng số các

trường hợp có thể

• Thực tế không khả thi nếu độ dài khóa lớn

Thống kê về thời gian vét cạn theo kích thước khóa:

17

– Chỉ biết giải thuật mã hóa và bản mã hiện có

• Chỉ có bản mã

– Biết thêm một số cặp nguyên bản - bản mã

• Biết nguyên bản

– Chọn 1 nguyên bản, biết bản mã tương ứng

• Chọn nguyên bản

– Chọn 1 bản mã, biết nguyên bản tương ứng

• Chọn bản mã

– Kết hợp chọn nguyên bản và chọn bản mã

• Chọn văn bản

• An toàn vô điều kiện

– Bản mã không chứa đủ thông tin để xác định duy nhất

nguyên bản tương ứng, bất kể với số lượng bao nhiêu và tốc độ máy tính thế nào

– Chỉ hệ mã hóa độn một lần là an toàn vô điều kiện – Chưa có thuật toán mã hóa nào được coi là an toàn không

điều kiện • An toàn tính toán

– Thỏa mãn một trong hai điều kiện

• Chi phí phá mã vượt quá giá trị thông tin • Thời gian phá mã vượt quá tuổi thọ thông tin

– Thực tế thỏa mãn hai điều kiện

• Không có nhược điểm • Khóa có quá nhiều giá trị không thể thử hết – Thuật toán an toán tính toán (cid:2) an toàn.

(cid:1) Chia làm hai kĩ thuật chính: thay thế, đảo vị trí:

(cid:1) Thay thế: nghĩa là thay 1 kí tự plaintext thành một

kí tự ciphertext

(cid:1) Đảo vị trí: thay đổi thứ tự xuất hiện của các kí tự

(cid:1) CAESAR (cid:1) Thay thế đơn bảng (cid:1) Vigener (cid:1) Mã hóa tự động (cid:1) Độn một lần (One-Time Pad, OTP)

21

• Là hệ mã hóa thay thế xuất hiện sớm nhất và

đơn giản nhất.

• Sử dụng đầu tiên bởi Julius Caesar vào mục

đích quân sự.

– Khóa k là số bước dịch chuyển – Với mỗi chữ cái của văn bản

• Đặt p = 0 nếu chữ cái là a, p = 1 nếu chữ cái là b,... • Mã hóa : C = E(p) = (p + k) mod 26 • Giải mã : p = D(C) = (C - k) mod 26

• Dịch chuyển xoay vòng theo thứ tự chữ cái

• Ví dụ : Mã hóa "meet me after class" với k = 3

– Khóa chỉ là một chữ cái (hay một số giữa 0 và 25) – Thử tất cả 26 khóa có thể – Dễ dàng thực hiện • Ba yếu tố quan trọng

– Biết trước các giải thuật mã hóa và giải mã – Chỉ có 26 khóa để thử – Biết và có thể dễ dàng nhận ra được ngôn ngữ của

nguyên bản

• Phương pháp vét cạn

• Ví dụ : Phá mã "GCUA VQ DTGCM"

(cid:1) Trong cuộc sống nếu: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z (cid:1) tương đương với giá trị: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 Thì:

(cid:1) Nếu tích cực làm việc chỉ là: H+A+R+D+W+O+R+K = 8+1+18+4+23+15+18+11 = 98%.

(cid:1) Kiến thức vẫn chỉ là: K+N+O+W+L+E+D+G+E =

11+14+15+23+12+5+4+7+5 = 96%

(cid:1) Hay là may mắn?

L+U+C+K = 12+21+3+11 = 47%

(cid:1) Để đạt được sự tuyệt đối (100%) trong cuộc

sống (cid:2) thái độ là 100%: A+T+T+I+T+U+D+E = 1+20+20+9+20+21+4+5 = 100%

• Thay một chữ cái này bằng một chữ cái khác theo trật tự bất kỳ sao cho mỗi chữ cái chỉ có một thay thế duy nhất và ngược lại

– Khóa a b c d e f g h i j k l m n o p q r s t u v w x y z M N B V C X Z A S D F G H J K L P O I U Y T R E W Q – Nguyên bản i love you

• Khóa dài 26 chữ cái • Ví dụ

• Phương pháp vét cạn – Khóa dài 26 ký tự – Số lượng khóa có thể = 26! > 4 x 1026 (~ 288) – Rất khó thực hiện

– Biết rõ tần số các chữ cái tiếng Anh

• Có thể suy ra các cặp chữ cái nguyên bản - chữ cái bản mã • Ví dụ : chữ cái xuất hiện nhiều nhất có thể tương ứng với 'e'

– Có thể nhận ra các bộ đôi và bộ ba chữ cái

• Ví dụ bộ đôi : 'th', 'an', 'ed' • Ví dụ bộ ba : 'ing', 'the', 'est'

• Khai thác những nhược điểm của giải thuật

T ầ n s ố t ư ơ n g đ ố i (

%

)

• Cho bản mã

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

• Tính tần số chữ cái tương đối • Đoán P là e, Z là t • Đoán ZW là th và ZWP là the • Tiếp tục đoán và thử, cuối cùng được it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow

(cid:1) Nếu mỗi lần chỉ mã hóa một kí tự thì sẽ để lại cấu trúc của của plaintext trong ciphertext

(cid:1) Để phá cấu trúc này thì người ta đề nghị mã

hóa một lần nhiều kí tự

(cid:1) Phương pháp tốt nhất được đề xuất là Playfair

Cipher

– Giảm bớt tương quan cấu trúc giữa bản mã và

nguyên bản bằng cách mã hóa đồng thời nhiều chữ cái của nguyên bản

• Là một hệ mã hóa nhiều chữ

• Phát minh bởi Charles Wheatstone vào năm

1854, lấy tên người bạn Baron Playfair

• Sử dụng 1 ma trận chữ cái 5x5 xây dựng trên cơ

sở 1 từ khóa – Điền các chữ cái của từ khóa (bỏ các chữ trùng) – Điền nốt ma trận với các chữ khác của bảng chữ cái – I và J chiếm cùng một ô của ma trận

– Nếu 2 chữ giống nhau, tách ra bởi 1 chữ điền thêm – Nếu 2 chữ nằm cùng hàng, thay bởi các chữ bên phải – Nếu 2 chữ nằm cùng cột, thay bởi các chữ bên dưới – Các trường hợp khác, mỗi chữ cái được thay bởi chữ

cái khác cùng hàng, trên cột chữ cái cùng cặp

• Ví dụ ma trận với từ khóa MONARCHY M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z • Mã hóa 2 chữ cái một lúc

34

(cid:1) Ví dụ như khóa là : smythework

S

M

Y

T

H

E

W

O

R

K

I/J

1. Hai kí tự trên cùng dòng sẽ được thay thế bởi

hai kí tự bên phải của nó (xoay vòng). Ví dụ bf thì thay bằng CA

2. Hai kí tự trên cùng cột thì được thay thế bởi hai

kí tự ngay dưới nó. Ví dụ ol thay bằng CV

3. Còn lại, mỗi kí tự được thay thế bằng kí tự cùng dòng nhưng ở cột của kí tự còn lại. Ví dụ gf.

g ở dòng 4 cột 1, f ở dòng 3 cột 5. Nên thay g bằng kí tự dòng 4 và cột 5. đó là P. Và ??? thay cho f

1. Bạn phải loại bỏ bất cứ sự trùng lắp trong khóa

2. Trước khi áp dụng phương pháp thay thế, phải chèn kí tự đặc biệt xen giữa hai từ trùng lắp liên tiếp

Ví dụ: carry (cid:2) carxry, nếu chọn x là kí tự đặc biệt

– Việc giải mã từng cặp khó khăn hơn – Cần phân tích 676 tần số xuất hiện thay vì 26

• An toàn đảm bảo hơn nhiều hệ mã hóa đơn chữ • Có 26 x 26 = 676 cặp chữ cái

• Từng được quân đội Anh, Mỹ sử dụng rộng rãi • Bản mã vẫn còn lưu lại nhiều cấu trúc của

nguyên bản

• Vẫn có thể phá mã được vì chỉ có vài trăm cặp

chữ cái cần giải mã

• Dựa vào tính chất: nếu AB (cid:2) XY thì BA (cid:2) YX.

với các chữ cái của văn bản

– Chữ cái thứ i tương ứng với hệ Ceasar bước chuyển i

• Là một hệ mã hóa đa bảng – Sử dụng nhiều bảng mã hóa – Khóa giúp chọn bảng tương ứng với mỗi chữ cái • Kết hợp 26 hệ Ceasar (bước dịch chuyển 0 - 25) – Khóa K = k1k2...kd gồm d chữ cái sử dụng lặp đi lặp lại

– Khóa : deceptivedeceptivedeceptive – Nguyên bản : wearediscoveredsaveyourself – Bản mã :

ZICVTWQNGRZGVTWAVZHCQYGLMGJ

• Ví dụ

– Khó thực hiện, nhất là nếu khóa gồm nhiều chữ cái

• Phương pháp vét cạn

– Cấu trúc của nguyên bản được che đậy tốt hơn hệ

Playfair nhưng không hoàn toàn biến mất

– Chỉ việc tìm độ dài khóa sau đó phá mã từng hệ

Ceasar

– Cách tìm độ dài khóa

• Nếu độ dài khóa nhỏ so với độ dài văn bản, có thể phát hiện

1 dãy văn bản lặp lại nhiều lần

• Khoảng cách giữa 2 dãy văn bản lặp là 1 bội số của độ dài

khóa

• Từ đó suy ra độ dài khóa

• Khai thác những nhược điểm của giải thuật

• Vigenère đề xuất từ khóa không lặp lại mà được

gắn vào đầu nguyên bản – Nếu biết từ khóa sẽ giải mã được các chữ cái đầu

tiên

– Sử dụng các chữ cái này làm khóa để giải mã các

chữ các tiếp theo,...

deceptivewearediscoveredsav – Khóa : – nguyên bản : wearediscoveredsaveyourself – Mã hóa : ZICVTWQNGKZEIIGASXSTSLVVWLA • Vẫn có thể sử dụng kỹ thuật thống kê để phá mã – Khóa và nguyên bản có cùng tần số các chữ cái

• Ví dụ :

• Là hệ mã hóa thay thế không thể phá được • Đề xuất bởi Joseph Mauborgne • Khóa ngẫu nhiên, độ dài bằng độ dài văn bản,

chỉ sử dụng một lần

• Giữa nguyên bản và bản mã không có bất kỳ

quan hệ nào về thống kê

• Với bất kỳ nguyên bản và bản mã nào cũng tồn

tại một khóa tương ứng

• Khó khăn ở việc tạo khóa và đảm bảo phân phối

khóa an toàn

(cid:1) Hệ mã Rail Fence (cid:1) Hệ mã hoán vị

44

(cid:1) Viết các chữ của bản rõ theo đường chéo trên một số dòng. Sau đó đọc các chữ theo từng dòng sẽ nhận được bản mã. Số dòng chính là khóa của mã. Vì khi biết số dòng ta sẽ tính được số chữ trên mỗi dòng và lại viết bản mã theo các dòng sau đó lấy bản rõ bằng cách viết lại theo các cột.

(cid:1) Ví dụ. Viết bản tin “meet me after the toga party” lần

lượt trên hai dòng như sau: m e m a t r h t g p r y e t e f e t e o a a t

(cid:1) Sau đó ghép các chữ ở dòng thứ nhất với các chữ

ở dòng thứ hai cho bản mã: MEMATRHTGPRYETEFETEOAAT

45

• Viết các chữ cái theo đường chéo trên một số

hàng nhất định

– Nguyên bản : attack at midnight – Mã hóa với độ cao hàng rào là 2 a t c a m d i h

• Sau đó đọc theo từng hàng một • Ví dụ

t a k t i n g t – Bản mã : ATCAMDIHTAKTINGT

• Viết các chữ cái theo hàng vào 1 số cột nhất định • Sau đó hoán vị các cột trước khi đọc theo cột • Khóa là thứ tự đọc các cột • Ví dụ

3 4 2 1 5 6 7

– Khóa : – Nguyên bản :

a t t a c k p o s t p o n e d u n t i l t w o a m x y z

– Bản mã :

TTNAAPTMTSUOAODWCOIXKNLYPETZ

(cid:1) Sắp xếp lại trật tự các chữ cái (không thay đổi

nguyên bản).

(cid:1) Định nghĩa: Một hệ mật là một bộ 5(P,C,K,E,D) 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 khóa Π (tức là một hoán vị) ta xác định: