Bài giảng Lý thuyết mật mã và an toàn thông tin: Mật mã cổ điển

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

Mã hoá

Giải mã

Bob

Alice

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

J K L M

I

0

1

2

3

4

5

6

7 9 10 11 12

8 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 :

K=0

K=1

K=2

K=3

K=4

K=5

K=6

K=7

K=8

K=9

jbcrclqrwcrvnbjenbwrwn iabqbkpqvbqumaidmavqvm hzapajopuaptlzhclzupul gyzozinotzoskygbkytotk fxynyhmnsynrjxfajxsnsj ewxmxglmrxmqiweziwrmri dvwlwfklqwlphvdyhvqlqh cuvkvejkpvkogucxgupkpg btujudijoujnftbwftojof a stitch in times saves nine 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 ”

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



e a ( ) 

X e b ,... ( ) , Do đó , 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 i b g

q n m u

s k a



,...

d A ( ) 

d d B ( ) 

Do đó ,

Ví dụ giải mã đoạn bản mã sau :

MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA

Ta thu được thisciphertextcannotbedecrypted

Discrete Mathematics I

Số Số nguyên nguyên Integer Integer

phép chia phép chia division division

Chương 2.4, 2.5 Kenneth H. Rosen Xuân 2008 Đại học FPT

GIỚI THIỆU Số nguyên 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

Definition Definition

Integer DIVISION

Phép chia

Định nghĩa Định nghĩa Cho hai số nguyên a, b với a ≠ 0, ta nói b chia hết cho 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 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 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ì 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. ta kí hiệu a|b.

Theorem

Định lí Cho 3 số nguyên a, b, c. Khi đó

a|b  cZ, (a.c =b) a|b  cZ, (a.c =b)

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

Example

Ví dụ

21 chia hết cho 3 vì tồn tại 7 để 21 = 3.7

tập các số chẵn Tập tất cả các bội của 2 là

{1, -1, 2, -2} Tập tất cả các ước của 2 là

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

Algorithm

Thuật toán 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

Số nguyên

PHÉP CHIA

Integer DIVISION

Example

Div, mod

Ví dụ Xác định thương và số dư khi chia 11 cho 3

q = 0 & r = 11

thương 8  3 2  3 11  3 5  3

q = 2 + 1 = 3 q = 1 + 1 = 2 q = 0 + 1 = 1

số dư r = 8 – 3 = 5 r = 11 – 3 = 8 r = 5 – 3 = 2

Xác định thương và số dư khi chia -11 cho 3 -11 < 0 & 2 > 0 q = -(3 + 1) = -4

r = 3 – 2 = 1

Số nguyên

SỐ NGUYÊN TỐ

Integer PRIME

Definition Definition

Số nguyên tố

Định nghĩa Định nghĩa Số nguyên dương p > 1 được gọi là số nguyên tố nếu Số nguyên dương p > 1 được gọi là số nguyên tố nếu nó chỉ có các ước số dương là 1 và p. Các số nguyên nó chỉ có các ước số dương là 1 và p. Các số nguyên dương > 1 và không phải là số nguyên tố được gọi là dương > 1 và không phải là số nguyên tố được gọi là hợp số. hợp số.

Định lí Theorem

Chú ý: n  N* là hợp số  (a, 1< a < n, a|n).

Nếu n là một hợp số thì n có ước nguyên tố ≤ n1/2

Số nguyên

SỐ NGUYÊN TỐ

Definition Definition

Integer PRIME

Định nghĩa Định nghĩa Để tìm tất cả các số nguyên tố ≤ n ta sử dụng sàng Để tìm tất cả các số nguyên tố ≤ n ta sử dụng sàng

Erathosthenes. Thủ tục này được mô tả như sau: Erathosthenes. Thủ tục này được mô tả như sau: 1. Liệt kê tất cả các số nguyên từ 2 đến n. Gọi là danh 1. Liệt kê tất cả các số nguyên từ 2 đến n. Gọi là danh

Số nguyên tố

sách A. sách A.

2. Lấy ra số 2 là số đầu tiên của danh sách A và cũng 2. Lấy ra số 2 là số đầu tiên của danh sách A và cũng

là số nguyên tố đầu tiên. Gọi là danh sách B. là số nguyên tố đầu tiên. Gọi là danh sách B. 3. Xóa bỏ 2 và các bội của nó ra khỏi danh sách A. 3. Xóa bỏ 2 và các bội của nó ra khỏi danh sách A. 4. Số x đầu tiên trong danh sách A mới là số nguyên tố 4. Số x đầu tiên trong danh sách A mới là số nguyên tố

và viết vào B. và viết vào B.

5. Xóa x và các bội ( x2) của x ra khỏi A. 5. Xóa x và các bội ( x2) của x ra khỏi A. 6. Lặp lại bước 4 và 5 cho đến khi A không còn phần tử 6. Lặp lại bước 4 và 5 cho đến khi A không còn phần tử nào. Chú ý là khi phần tử đều tiên của danh sách nào. Chú ý là khi phần tử đều tiên của danh sách còn lại > (phần tử lớn nhất)1/2 thì tất cả các phần tử còn lại > (phần tử lớn nhất)1/2 thì tất cả các phần tử còn lại đều là số nguyên tố. còn lại đều là số nguyên tố.

Số nguyên

SỐ NGUYÊN TỐ

Integer PRIME

Example

Ví dụ Tìm tất cả các số nguyên tố ≤ 120

Số nguyên tố

Số nguyên

SỐ NGUYÊN TỐ

Integer PRIME

Số nguyên tố

 ...

...





Định lí cơ bản của số học Theorem Mọi số nguyên dương n > 1 đều có thể được viết duy nhất dưới dạng tích của các số nguyên tố, trong đó các số nguyên tố được viết theo thứ tự tăng dần, sự phân tích này gọi là phân tích tiêu chuẩn của n. v p r

v pp . 1 1

p 1

v 2

Định lí Theorem

)

s] + …

Với mọi n > 1, dạng phân tích của n! là pv pv rpv ( ( ( ) n  p p p ! . ... 1 r 1 2 2] + … + [n/pi ở đó, v(pi) = [n/pi] + [n/pi

Số nguyên

SỐ NGUYÊN TỐ

Integer PRIME

Example

Ví dụ Tìm dạng phân tích tiêu chuẩn của 10!

Số nguyên tố

10! = 2v(2).3v(3).5v(5).7v(7)

v(2) = [10/2] + [10/22] + [10/23] + [10/24] + … = 8

v(3) = [10/3] + [10/32] + [10/33] + … = 4

v(5) = [10/5] + [10/52] + … = 2

v(7) = [10/7] + [10/72] + … = 1

10! = 28.34.52.71

Bài tập: viết thuật toán xác định dạng phân tích tiêu chuẩn của n!

Số nguyên

SỐ NGUYÊN TỐ

Integer PRIME

Định lí Euclid Theorem

Số nguyên tố

Tồn tại vô số số nguyên tố.

Chứng minh: Giả sử chỉ có một số hữu hạn số nguyên tố: p1, p2, …, pn. Đặt Q = p1.p2 …pn + 1 > 1 Theo Định lí cơ bản của số học: pj, 1≤ j ≤ n, pj|Q. pj|Q  pj|(Q – p1.p2 …pn) = 1 (vô lí)  ĐPCM

VD: (10) = 4 Gọi (x) là số số nguyên tố ≤ x.

Định lí Euclid: limx→(x) = .

Hãy mô tả độ tăng của (x)? Xem trang bên → …

ƯCLN

Số nguyên Integer GCD

Definition Definition

Ước chung

Định nghĩa Định nghĩa •Cho a và b hai số nguyên khác 0, số nguyên d lớn •Cho a và b hai số nguyên khác 0, số nguyên d lớn nhất sao cho d|a và d|b được gọi là ước chung lớn nhất nhất sao cho d|a và d|b được gọi là ước chung lớn nhất của a và b, kí hiệu là ƯCLN(a, b). của a và b, kí hiệu là ƯCLN(a, b).

•Bội chung nhỏ nhất của hai số nguyên dương a và b là •Bội chung nhỏ nhất của hai số nguyên dương a và b là số nguyên dương nhỏ nhất chia hết cho cả a lẫn b, kí số nguyên dương nhỏ nhất chia hết cho cả a lẫn b, kí hiệu là BCNN(a, b). hiệu là BCNN(a, b).

ƯCLN

Số nguyên Integer GCD

Định lí Theorem

Cho 2 số nguyên dương a, b có dạng phân tích tiêu

Ước chung

ra p ... r rb p ... r

a a pp . 1 1 2 b b pp . 1 1 2 2

a b ở đó, ai, bj  0 (có thể bằng 0). Khi đó

)

r ba , r

ba , 11

ba , 2 2

UCLN(

ba ),

...



min( p r

min( p 2

min( p 1

)

r ba , r

ba , 11

ba , 2 2

BCNN(

ba ),

...



max( p r

max( p 1

max( p 2

chuẩn như sau:

Hơn nữa: a.b = ƯCLN(a, b). BCNN(a, b)

ƯCLN

Số nguyên Integer GCD

Example Ví dụ Cho hai số a = 300, b = 315 tìm ƯCLN và BCNN của a và b.

Ước chung

= 22.31.52.70 300 = 22.31.52

= 20.32.51.71 315 = 32.51.71

ƯCLN(300, 315) = 2min(2, 0).3min(1, 2).5min(2, 1).7min(0, 1)

= 20.31.51.70 = 15

BCNN(300, 315) = 2max(2, 0).3max(1, 2).5max(2, 1).7max(0, 1)

= 22.32.52.71 = 6300

300*315 = 94500 = ƯCLN(300, 315)*BCNN(300, 315)

ƯCLN

Số nguyên Integer GCD

Definition Definition

Định nghĩa Định nghĩa •Hai số nguyên a và b được gọi là nguyên tố cùng •Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. nhau nếu ước chung lớn nhất của chúng bằng 1.

Hàm Euler

•Các số nguyên a1, a2, …, an được gọi là đôi một •Các số nguyên a1, a2, …, an được gọi là đôi một nguyên tố cùng nhau nếu hai số bất kì trong chúng nguyên tố cùng nhau nếu hai số bất kì trong chúng ai, aj (1  i < j  n) nguyên tố cùng nhau. ai, aj (1  i < j  n) nguyên tố cùng nhau.

Chú ý: Cho p là số nguyên tố, thì p nguyên tố cùng nhau với tất cả các số nguyên a không chia hết cho p.

ƯCLN

Số nguyên Integer GCD

Bổ đề Lemma

Để tìm ước chung lớn nhất của hai số nguyên a và b ta thường áp dụng thuật toán Euclid cơ sở toán học của thuật toán này như sau

T.T Euclid

Cho a = q.b + r, trong đó a, b, q, r là các số nguyên. Khi

đó

ƯCLN(a, b) = ƯCLN (b, r)

ƯCLN

Số nguyên Integer GCD

Thuật toán Euclid Algorithm procedure ƯCLN (a, b nguyên dương)

x: = a

Dạng đệ quy y: = b

procedure: ƯCLN (a, b  N, a < b) while y ≠ 0

T.T Euclid

if a = 0 then begin

ƯCLN(a, b): = b r: = x mod y

x: = y else

y: = r ƯCLN(a, b): = ƯCLN(b mod a, a)

end

{ƯCLN(a, b) = x}

ƯCLN

Số nguyên Integer GCD

Example

Ví dụ Tìm ước chung lớn nhất của 123 và 456

456 = 3.123 + 87

123 = 1.87 + 36

T.T Euclid

87 = 2.36 + 15

36 = 2.15 + 6

15 = 2.6 + 3 6 = 2.3 + 0

ƯCLN(123, 456) = 3

ƯCLN

Số nguyên Integer GCD

Example

Ví dụ Tìm ước chung lớn nhất của 123 và 456

ƯCLN(123, 456) = ƯCLN(87, 123) = ƯCLN(456 mod 123, 123)

= ƯCLN(123 mod 87, 87) = ƯCLN(36, 87)

T.T Euclid

= ƯCLN(87 mod 36, 36) = ƯCLN(15, 36)

= ƯCLN(6, 15) = ƯCLN(36 mod 15, 15)

= ƯCLN(3, 6) = ƯCLN(15 mod 6, 6)

= ƯCLN(0, 3) = ƯCLN(6 mod 3, 3) = 3

ƯCLN

Số nguyên Integer GCD

Định lí Theorem

Cho hai số nguyên dương a và b, với a  b. Khi đó độ

T.T Euclid

phức tạp của thuật toán Euclid theo số phép chia là

O(logb).

Đồng dư

ĐỊNH NGHĨA

Congruence DEFINITION

Đồng dư

Definition Definition

Định nghĩa Định nghĩa Cho a và b là hai số nguyên và m là một số nguyên Cho a và b là hai số nguyên và m là một số nguyên dương. Ta nói a đồng dư với b theo môđun m và kí dương. Ta nói a đồng dư với b theo môđun m và kí hiệu là a  b (mod m) nếu a – b chia hết cho m, nếu trái hiệu là a  b (mod m) nếu a – b chia hết cho m, nếu trái lại thì kí hiệu là a  b (mod m). lại thì kí hiệu là a  b (mod m).

Như vậy: Như vậy:

a  b (mod m)  m|a – b a  b (mod m)  m|a – b

 a mod m = b mod m  a mod m = b mod m

Tập tất cả các số nguyên sẽ thu gọn về m “số” mới theo mod m mỗi “số” này là một lớp đồng dư.

Đồng dư

ĐỊNH NGHĨA

Definition Definition

Congruence DEFINITION

Đồng dư

Định nghĩa Định nghĩa Tập hợp gồm m số nguyên đôi một không đồng dư theo Tập hợp gồm m số nguyên đôi một không đồng dư theo mod m gọi là một hệ thặng dư đầy đủ theo mod m. mod m gọi là một hệ thặng dư đầy đủ theo mod m. Một số nguyên bất kì sẽ đồng dư với một và chỉ một số Một số nguyên bất kì sẽ đồng dư với một và chỉ một số trong một hệ thặng dư đầy đủ. trong một hệ thặng dư đầy đủ.

Example

Ví dụ {0, 1, 2, 3, 4, 5, 6} là một hệ thặng dư đầy đủ theo mod 7 {1, 2, 3, 5, 8, 13, 21} không là một hệ thặng dư đầy đủ theo mod 7 vì …

1  8 (mod 7)

{20, 21, 22, 23, 24, 25, 26} có là một hệ thặng dư đầy đủ theo mod 7 không? Không

Đồng dư

ĐỊNH NGHĨA

Congruence DEFINITION

Đồng dư

Theorem

Định lí Cho m là số nguyên dương. Khi đó

• a  b (mod m)  k, a = b + km.

• Nếu a  b (mod m) và c  d (mod m) thì

a + c  b +d (mod m); a.c  b.d (mod m)

Có một mối liên hệ giữa các phép tính số học thông thường và các phép tính số học theo môđun m dấu bằng “=” liên hệ với dấu đồng dư “” +, –, *, / liên hệ với +, –, *, / rồi lấy đồng dư

Đồng dư

ĐỊNH NGHĨA

Congruence DEFINITION

Đồng dư

Vẫn có những tính chất đúng trong số học nhưng không còn đúng trong số học đồng dư nữa.

a.b = 0  a = 0 hoặc b = 0 nhưng …

Example

a.b  0 (mod m)  a  0 hoặc b  0

Ví dụ 4.3  0 (mod 6) nhưng … 4  0 (mod 6) 3  0 (mod 6)

Đồng dư

NGHỊCH ĐẢO

Congruence INVERSE

Nghịch đảo

Hệ quả lemma Cho hai số a và m nguyên tố cùng nhau và m > 1 thì tồn tại số nguyên s (duy nhất theo mod m) để sa  1 (mod m).

Definition Definition

Định nghĩa Định nghĩa Cho hai số a và m nguyên tố cùng nhau và m > 1 thì a Cho hai số a và m nguyên tố cùng nhau và m > 1 thì a gọi là khả nghịch theo mod m, nghịch đảo s của a gọi là khả nghịch theo mod m, nghịch đảo s của a thỏa mãn sa  1 (mod m) duy nhất (theo mod m). thỏa mãn sa  1 (mod m) duy nhất (theo mod m).

Tập con của một hệ thặng dư đầy đủ mod m gồm tất cả Tập con của một hệ thặng dư đầy đủ mod m gồm tất cả các phần tử khả nghịch mod m gọi là một hệ thặng dư các phần tử khả nghịch mod m gọi là một hệ thặng dư thu gọn mod m. thu gọn mod m.

Chú ý: nếu a là phần tử khả nghịch theo mod m thì a.b  0 (mod m) khi và chỉ khi b  0 (mod m)

Đồng dư

NGHỊCH ĐẢO

Congruence INVERSE

Example

Nghịch đảo

Ví dụ Một hệ thăng dư đầy đủ mod 12 là

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

Định lí Theorem

Một hệ thăng dư thu gọn mod 12 là 1, 5, 7, 11 Cho p là một số nguyên tố, một hệ thăng dư thu gọn mod p là {1, 2, …, p–1}

Số phần tử của mọi hệ thặng dư thu gọn mod m là như nhau và bằng (m), hàm Euler của m.

1.1.3. Hệ mã tuyến tính

Vì gcd(a,26)=1 nên a chỉ có thể nhận các giá trị sau đây: a= 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25

a 1 3 5 7 9 11 15 17 19 21 23 25

a-1 1 9 21 15 3 19 7 23 11 5 17 25

)(xeK

Ta xem xét ví dụ sau đây : Giả sử K= ( 7,3). Hàm mã hoá là = 7x+3mod 26 Mã hoá văn bản P - hot . Số hóa h, o, t được 7,14,19 . e(h) = 7.7+3 mod 26 = 0 , e(o) = 7.14+3 mod 26 = 23 , và e(t) = 7.19+3 mod 26 = 6 , Bản mã là xâu ký tự “AXG”.

)( y

1a

d K

Để giải mã bản mã , ta sử dụng hàm giải mã d K = (y-b) mod 26 . Trong ví dụ trên với K = ( 7,3) ta có a= 7 1a nên =15 )( y Do đó = (15y-19) mod 26 Khi ta giải mã, thu được các số 7, 14, 19. Các số này tương ứng với các ký tự h, o, t. Do đó ta có văn bản gốc là hot Lưu ý: Có 12 x 26 = 312 chìa khóa có thể, có thể duyệt toàn bộ để thám mã.

1.1.4 Hệ mã Vigenère Cả hai hệ mật mã Shift Cipher và Substitution Cipher, khi đã chọn khoá K, mỗi ký tự Alphabe ánh xạ đến một ký tự Alphabe duy nhất. Vì lý do này , các hệ mật mã đó được gọi là đơn ký tự ( monoalphabetic ). Đến đây , ta giới thiệu một hệ mật mã không phải là monoalphabetic , được biết đến là Vigenère Cipher, mang tên của Blaise de Vigenère, thế kỷ 16.

  

2,...,



Sử dụng tương ứng , 0, ta có thể kết hợp với mỗi khoá K vào xâu ký tự

Alphabe có độ dài m, gọi là từ khoá. Mật mã

Vigenère Cipher mã hoá theo từng khối m ký tự của

văn bản gốc. Ví dụ : Giả sử m = 6 và từ khoá là C I P H E R . Tương ứng với nó là các số K = ( 2, 8,15,7,4,17 ). Giả sử văn bản gốc :thiscryptosystemisnotsecure Ta biến đổi các phần tử của văn bản gốc quy đổi sang modulo 26 , và viết chúng thành một nhóm của sáu số , và cộng thêm vào từ khoá ( modulo 26 ) , giống như sau đây :