1
Mục lục
1. CƠ SỞ TOÁN HỌC 3
1.1. Lý thuyết số 3
1.1.1. Khái niệm đồng dư Modulo 3
1.1.2. Định lý về đồng dư thức 3
1.1.3. Khái niệm phần tử nghịch đảo 4
1.1.4. Thuật toán Euclide 4
1.1.5. Phần tử nguyên thủy và logarith rời rạc 4
1.1.6. Thặng dư bậc hai và ký hiệu Legendre 5
1.1.7. Một số thuật toán kiểm tra tính nguyên tố 6
1.2. Lý thuyết về độ phức tạp tính toán 6
1.2.1. Độ phức tạp tính toán 6
1.2.2. Các lớp phức tạp 7
1.3. Hàm một phía và hàm cửa sập một phía 8
2. GIỚI THIỆU VỀ MÃ HÓA 9
2.5.5. Mã HILL 21
2.5.6. Mã hoán vị 23
3. HỆ MÃ HÓA DES 24
3.1. Mô tả DES 24
3.1.1. Thuật toán DES 25
2
3.1.2. Mô tả một vòng của DES 25
3.1.3. Mô tả hàm f 25
3.1.4. Mô tả chi tiết các hàm trong DES 27
3.1.5. Tính toán bảng khóa từ khóa K 30
3.2. Ví dụ 34
3.3. Tranh luận về DES 37
3.4. DES trong thực tế 38
3.5. Ứng dụng của DES 42
4. MÃ HÓA KHÓA CÔNG KHAI 43
5.2. Hàm băm 58
5.3. Phân loại các sơ đồ chữ ký điện tử 60
5.3.1. Sơ đồ chữ ký kèm thông điệp 61
5.3.2. Sơ đồ chữ ký khôi phục thông điệp 62
5.4. Sơ đồ chữ ký RSA 63
5.5. Sơ đồ chữ kí ELGAMAL 64
5.5.1. Định nghĩa 65
5.5.2. Độ an toàn của chữ ký Elgamal 66
5.6. Chuẩn chữ ký số DSS (Digital Signature Standard) 69
5.6.1. Giới thiệu 69
5.6.2. Các giải thuật cơ bản của DSS 70
5.6.3. Tính chất của chữ ký của DSS 72
3
5.6.4. Lựa chọn sơ đồ ký khả thi 73
5.7. Tấn công chữ ký điện tử 74
thông tin một cách dễ dàng và hiệu quả. Các công nghệ E-mail cho phép mọi người có
thể gửi thư cho người khác cũng như nhận thư ngay trên máy tính của mình. Gần đây
có công nghệ E-business cho phép thực hiện các hoạt động thương mại trên mạng máy
tính. Việc ứng dụng các mạng cục bộ trong các tổ chức, công ty hay trong một quốc
gia là rất phong phú. Các hệ thống chuyển tiền của các ngân hàng hàng ngày có thể
chuyển hàng tỷ đôla qua hệ thống của mình. Các thông tin về kinh tế, chính trị, khoa
học xã hội được trao đổi rông rãi.
Tuy nhiên lại nảy sinh vấn đề về an toàn thông tin. Đó cũng là một quá trình tiến
triển hợp logic: khi những vui thích ban đầu về một siêu xa lộ thông tin, bạn nhất định
nhận thấy rằng không chỉ cho phép bạn truy nhập vào nhiều nơi trên thế giới, Internet
còn cho phép nhiều người không mời mà tự ý ghé thăm máy tính của bạn.
Thực vậy, Internet có những kỹ thuật tuyệt vời cho phép mọi người truy nhập, khai
thác, chia sẻ thông tin. Những nó cũng là nguy cơ chính dẫn đến thông tin của bạn bị
hư hỏng hoặc phá huỷ hoàn toàn.
Có những thông tin vô cùng quan trọng mà việc bị mất hay bị làm sai lệch có thể
ảnh hưởng đến các tổ chức, các công ty hay cả một quốc gia. Các thông tin về an ninh
quốc gia, bí mật kinh doanh hay các thông tin tài chính là mục tiêu của các tổ chức
tình báo nước ngoài về chính trị hay công nghiệp hoặc kẻ cắp nói chung. Bọn chúng
có thể làm mọi việc có thể để có được những thông tin quý giá này. Thử tưởng tượng
nếu có kẻ xâm nhập được vào hệ thống chuyển tiền của các ngân hàng thì ngân hàng
đó sẽ chịu những thiệt hại to lớn như mất tiền có thể dẫn tới bị phá sản. Chưa kể nếu
hệ thông thông tin an ninh quốc gia bị đe doạ thì hậu quả không thể lường trước được.
Theo số liệu của CERT(Computer Emegency Response Team - “Đội cấp cứu máy
tính”), số lượng các vụ tấn công trên Internet được thông báo cho tổ chức này là ít
hơn 200 vào năm 1989, khoảng 400 vào năm 1991, 1400 vào năm 1993, và 2241 vào
năm 1994. Những vụ tấn công này nhằm vào tất cả các máy tính có mặt trên Internet,
các máy tính của tất cả các công ty lớn như AT&T, IBM, các trường đại học, các cơ
quan nhà nước, các tổ chức quân sự, nhà băng Một số vụ tấn công có quy mô khổng
lồ (có tới 100.000 máy tính bị tấn công). Hơn nữa, những con số này chỉ là phần nổi
của tảng băng. Một phần rất lớn các vụ tấn công không được thông báo, vì nhiều lý do,
của nó và sau đó lại gửi cho người nhận. Người nhận không hề nghi ngờ gì trừ
khi nhận ra thông báo đó là vô lý, và có thể thực hiện vài hành động dựa trên
các thành phần sai này đem lại lợi ích cho bên thứ ba.
Người dùng log vào một server mà không sử dụng mật khẩu được mã hoá. Một
người khác đang nghe trộm trên đường truyền và bắt được mật khẩu logon của
người dùng, sau đó có thể truy nhập thông tin trên server như người sử dụng.
Một người quản trị hệ thống không hiểu về khía cạnh an toàn và yêu cầu của hệ
thống và vô tình cho phép người dùng khác truy nhập vào thư mục chứa các
thông tin hệ thống. Người dùng phát hiện ra họ có thể có được các thông tin hệ
thống và có thể dùng nó phục vụ cho lợi ích của mình.
Lý thuyết mật mã và an toàn dữ liệu
Trang 3 1. CƠ SỞ TOÁN HỌC
Trong phần này sẽ trình bày về một số cơ sở toán học của mã hóa, điều này sẽ giúp
ta nắm được một cách chi tiết hơn về các phương pháp mã hóa.
1.1. Lý thuyết số
1.1.1. Khái niệm đồng dư Modulo
Định nghĩa 1: 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 b-a chia hết cho m. Mệnh đề a
≡
b(mod m) được gọi là “a
đồng dư với b theo mođun m”.
Giả sử chia a và b cho m và ta thu được thương nguyên và phần dư, các phần dư
nằm giữa 0 và m-1, nghĩa là a = q
1*
đượ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 mođun m.
1.1.2. Định lý về đồng dư thức
Định lí 1: Đồng dư thức ax
≡
b (mod m) chỉ có một nghiệm duy nhất x
∈
Z
m
với
mọi b
∈
Z
m
khi và chỉ khi UCLN(a,m) = 1.
Ta giả sử rằng, UCLN(a,m) = d >1. Khi đó, với b = 0 thì đồng dư thức ax ≡ 0 (mod
m) sẽ có ít nhất hai nghiệm phân biệt trong Z
m
là x = 0 và x = m/d. Lý thuyết mật mã và an toàn dữ liệu
Trang 4
1.1.3. Khái niệm phần tử nghịch đảo
Định nghĩa 2: Giả sử a
∈
Z
m
đều có nghịch đảo.
1.1.4. Thuật toán Euclide
Cho hai số tự nhiên a, n. Ký hiệu (a,n) là ước số chung lớn nhất của a,n;
φ
(n) là số
các số nguyên dương < n và nguyên tố với n, không mất tính tổng quát giả sử n > a.
Thuật toán Euclide tìm UCLN (a,n) được thực hiện bằng một dãy các phép chia liên
tiếp sau đây:
Đặt r
0
= n, r
1
= a,
r
0
= q
1
r
1
+ r
2
, 0 < r
2
< r
1
r
1
= q
2
= (r
0,
r
1
) = (r
1,
r
2
) = …… = (r
m-1,
r
m
) = r
m
Vậy ta tìm được r
m
= (n,a). Mở rộng thuật toán Euclide bằng cách xác định thêm
dãy số t
0
, t
1
,…,t
m
:
t
0
= 0,
t
mod n
1.1.5. Phần tử nguyên thủy và logarith rời rạc
Cho số n nguyên dương. Ta biết rằng tập các thặng dư thu gọn theo mođun n (tức là
tập các số nguyên dương < n và nguyên tố với n) lập thành một nhóm với phép nhân
Lý thuyết mật mã và an toàn dữ liệu
Trang 5
mod n, ta ký hiệu là Z
n
*
. Nhóm đó có cấp (số phần tử) là
φ
(n). Một phần tử g ∈ Z
n
*
có
cấp m, nếu m là số nguyên dương bé nhất sao cho g
m
= 1 trong Z
n
*
.
Theo một định lý đại số, ta có m |
φ
(n) (ký hiệu m là ước số của
φ
(n)) vì vậy với mọi
b ∈ Z
p
*
là nhóm cyclic, và số các phần tử nguyên thủy của
Z
p
*
bằng
φ
(p-1)
• Nếu g là phần tử nguyên thủy theo mođun p, thì β = g
i
, với mọi i mà (i,p-1) = 1,
cũng là phần tử nguyên thủy theo mođun p
1.1.6. Thặng dư bậc hai và ký hiệu Legendre
Cho p là một số nguyên tố lẻ, và x là một số nguyên dương ≤ p-1. x được gọi là một
thặng dư bậc hai theo mođun p, nếu phương trình: y
2
≡ x (mod p) có nghiệm.
Ta có tiêu chuẩn Euler sau đây: x là thặng dư bậc hai theo mođun p, nếu và chỉ nếu
x
(p-1)/2
≡ 1 (mod p)
Tiêu chuẩn đó được chứng minh như sau: Giả sử có x
≡ y
2
(mod p). Khi đó có:
x
(p-1)/2
p
a
Legendre
như sau: đasad
p
a
=
0 nếu a
≡
0 (mod p)
1 nếu a là thặng dư bậc hai theo mod p
-1 nếu a không là thặng dư bậc hai theo mod p
|{a: 1 ≤ a ≤ n-1,
n
a
≡ a
(n-1)/2
(mod n)}| ≤ (n-1)/2
Solovay_Strassen (cải tiến bởi Lehmann):
Nếu n là số nguyên tố, thì với mọi 1 ≤ a ≤ n-1:
a
(n-1)/2
≡ ±1 (mod n);
Nếu n là hợp số thì:
|{a: 1 ≤ a ≤ n-1, a
(n-1)/2
≡ ±1(mod n)}| ≤ (n-1)/2
1.2. Lý thuyết về độ phức tạp tính toán
1.2.1. Độ phức tạp tính toán
Lý thuyết thuật toán và các hàm tính ra đời từ những năm 30 đã đặt nền móng cho
các nghiên cứu về các vấn đề “tính được”, “giải được”, và đã thu được nhiều kết quả
rất quan trọng. Nhưng từ cài “tính được” một cách trừu tượng, tiềm năng đến việc tính
được trong thực tế của khoa học tính toán bằng máy tính điện tử là một khoảng cách
rất lớn. Lý thuyết về độ phức tạp tính toán được nghiên cứu bắt đầu từ những năm 60
o Dữ liệu: Số nguyên dương N
o Câu hỏi: Có hay không hai số m,n > 1 sao cho N = m×n ?
1.2.2. Các lớp phức tạp
Ta định nghĩa P là lớp các bài toán có độ phức tạp thời gian là đa thức tức lớp các
bài toán mà đối với chúng có thuật toán giải bài toán đó trong thời gian đa thức.
Một lớp quan trọng các bài toán đã được nghiên cứu nhiều là lớp NP, tức các bài
toán mà đối với chúng có thuật toán không đơn định để giải trong thời gian đa thức.
Thuật toán không đơn định là một mô hình tính toán trừu tượng, được giả định là sau
mỗi bước có thể có một số hữu hạn bước được lựa chọn đồng thời tiếp sau.
Nhiều bài toán được chứng tỏ là thuộc lớp NP, nhưng chưa ai chứng minh được là
chúng thuộc lớp P hay không. Và một vấn đề cho đến nay vẫn còn mở, chưa có lời giải
là: NP = P ?
Một cách trực giác, lớp NP bao gồm các bài toán khó hơn phức tạp hơn các bài toán
thuộc lớp P, nhưng điều có vẻ hiển nhiên trực giác đó vẫn chưa được chứng minh hay
bác bỏ.
Lý thuyết mật mã và an toàn dữ liệu
Trang 8
Giả sử NP ≠ P, thì trong NP có một lớp con các bài toán được gọi là NP_đầy đủ , đó
là những bài toán mà bản thân thuộc lớp NP, và mọi bài toán bất kỳ thuộc lớp NP đều
có thể qui dẫn về bài toán đó bằng một hàm tính được trong thời gian đa thức.
Cho đến nay, người ta đã chứng minh được hàng trăm bài toán thuộc nhiều lĩnh vực
khác nhau là NP_đầy đủ. Bài toán đồng dư bậc hai kể trên là NP_đầy đủ, bài toán hợp
số không là NP_đầy đủ, nhưng chưa tìm được một thuật toán làm việc trong thời gian
đa thức giải nó.
1.3. Hàm một phía và hàm cửa sập một phía
Hàm f(x) được gọi là hàm một phía, nếu tính y = f(x) là dễ, nhưng việc tính ngược
x=f
(y) khá dễ.
Trên đây là hai thí dụ điển hình, và cũng là hai trường hợp được sử dụng rộng rãi về
hàm một phía và hàm cửa sập một phía. Vì đây là những điểm then chốt của lý thuyết
mật mã khóa công khai, nên việc tìm kiếm các loại hàm một phía và cửa sập một phía
được nghiên cứu rất khẩn trương, và đến nay tuy có đạt được một số kết quả, nhưng
việc tìm kiếm vẫn tiếp tục, đầy hứng thú nhưng cũng đầy khó khăn. Lý thuyết mật mã và an toàn dữ liệu
Trang 9
2. GIỚI THIỆU VỀ MÃ HÓA
2.1. Các thuật ngữ
1. Hệ mật mã là tập hợp các thuật toán và các thủ tục kết hợp để che dấu thông tin
cũng như làm rõ nó.
2. Mật mã học nghiên cứu mật mã bởi các nhà mật mã học, người viết mật mã và các
nhà phân tích mã.
3. Mã hoá là quá trình chuyển thông tin có thể đọc gọi là bản rõ thành thông tin
không thể đọc gọi là bản mã.
4. Giải mã là quá trình chuyển ngược lại thông tin được mã hoá thành bản rõ.
5. Thuật toán mã hoá là các thủ tục tính toán sử dụng để che dấu và làm rõ thông tin.
Thuật toán càng phức tạp thì bản mã càng an toàn.
6. Một khoá là một giá trị làm cho thuật toán mã hoá chạy theo cách riêng biệt và
sinh ra bản rõ riêng biệt tuỳ theo khoá. Khoá càng lớn thì bản mã kết quả càng an
toàn. Kích thước của khoá được đo bằng bit. Phạm vi các giá trị có thể có của khoá
được gọi là không gian khoá.
7. Phân tích mã là quá trình hay nghệ thuật phân tích hệ mật mã hoặc kiểm tra tính
toàn vẹn của nó hoặc phá nó vì những lý do bí mật.
che dấu thông tin sử dụng các kỹ thuật mã hóa.
Tính toàn vẹn: cung cấp sự bảo đảm với tất cả các bên rằng thông báo còn lại
không thay đổi từ khi tạo ra cho đến khi người nhận mở nó.
Tính không từ chối: có thể cung cấp một cách xác nhận rằng tài liệu đã đến từ ai
đó ngay cả khi họ cố gắng từ chối nó.
Tính xác thực: cung cấp hai dịch vụ: đầu tiên là nhận dạng nguồn gốc của một
thông báo và cung cấp một vài sự bảo đảm rằng nó là đúng sự thực. Thứ hai là
kiểm tra đặc tính của người đang logon một hệ thống và sau đó tiếp tục kiểm tra
đặc tính của họ trong trường hợp ai đó cố gắng đột nhiên kết nối và giả dạng là
người sử dụng
2.4. Các phương pháp mã hoá
2.4.1. Mã hoá đối xứng khoá bí mật
Thuật toán đối xứng hay còn gọi thuật toán mã hoá cổ điển là thuật toán mà tại đó
khoá mã hoá có thể tính toán ra được từ khoá giải mã. Trong rất nhiều trường hợp,
khoá mã hoá và khoá giải mã là giống nhau. Thuật toán này còn có nhiều tên gọi khác
như thuật toán khoá bí mật, thuật toán khoá đơn giản, thuật toán một khoá. Thuật toán
này yêu cầu người gửi và người nhận phải thoả thuận một khoá trước khi thông báo
được gửi đi, và khoá này phải được cất giữ bí mật. Độ an toàn của thuật toán này vẫn
phụ thuộc vào khoá, nếu để lộ ra khoá này nghĩa là bất kỳ người nào cũng có thể mã
hoá và giải mã thông báo trong hệ thống mã hoá.
Sự mã hoá và giải mã của thuật toán đối xứng biểu thị bởi :
E
K
( P ) = C và D
K
( C ) = P
Lý thuyết mật mã và an toàn dữ liệu
Trang 11
Việc thay đổi khoá là rất khó và dễ bị lộ.
Khuynh hướng cung cấp khoá dài mà nó phải được thay đổi thường xuyên cho mọi
người trong khi vẫn duy trì cả tính an toàn lẫn hiệu quả chi phí sẽ cản trở rất nhiều
tới việc phát triển hệ mật mã cổ điển. Bản rõ Mã hoá Giải mã Bản rõ
B
ản m
ã
Khoá
Hình
2
.1. Mã hoá v
ới khoá m
ã và khoá gi
ải giống nhau
K
1
K
2
Lý thuyết mật mã và an toàn dữ liệu
Trang 12
2.4.2. Mã hoá phi đối xứng khoá công khai
Bản rõ Mã hoá Giải mã Bản rõ
B
ản m
ã
Khoá giải mã k
2
Hình
2
.2. Mã hoá v
ới khoá m
ã và khoá gi
ải khác nhau
Khoá mã hóa k
1
Lý thuyết mật mã và an toàn dữ liệu
Trang 13
1. Việc tính toán ra cặp khoá công khai K
A
và bí mật K
B
dựa trên cơ sở các điều
kiện ban đầu phải được thực hiện một cách dễ dàng, nghĩa là thực hiện trong
thời gian đa thức.
2. Người gửi A có được khoá công khai của người nhận B và có bản tin P cần gửi
đi thì có thể dễ dàng tạo ra được bản mã C.
C = E
kênh. Oscar 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 Bob (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:
Đị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:
P là một tập hữu hạn các bản rõ có thể.
C là một tập hữu hạn các bản mã có thể.
K (không gian khoá) là tập hữu hạn các khoá có thể.
Đối với mỗi k∈ K có một quy tắc mã e
k
: P → C và một quy tắc giải mã tương ứng
d
k
∈ D. Mỗi e
k
: P → C và d
k
: C → P là những hàm mà:
d
k
(e
k
(x)) = x với mọi bản rõ x
∈
P.
Lý thuyết mật mã và an toàn dữ liệu
P
, 1 ≤ i ≤ n.
Mỗi x
i
sẽ được mã hoá bằng quy tắc mã e
k
với khoá k xác định trước đó. Bởi vậy Alice
sẽ tính y
i
= e
k
(x
i
), 1 ≤ i ≤ n và chuỗi bản mã nhận được:
y = y
1
, y
2
,. . ., y
n
sẽ được gửi trên kênh. Khi Bob nhận đươc y
1
,y
2
,. . .,y
n
anh ta sẽ giải mã bằng hàm
giải mã dk và thu được bản rõ gốc x
1
P
=
C
thì mỗi hàm mã hoá là một phép hoán vị, tức là nếu tập các
bản mã và tập các bản rõ là đồng nhất thì mỗi một hàm mã sẽ là một sự sắp xếp lại
(hay hoán vị ) các phần tử của tập này.
Oscar
B
ộ giải m
ã
B
ộ m
ã hoá
Bob
Alice
Kênh an toàn
Nguồn khoá
Lý thuyết mật mã và an toàn dữ liệu
Trang 15
Do các ví dụ của chúng ta xét trên tập dữ liệu là bảng chữ cái nên chúng ta coi bảng
chữ cái tiếng Anh là tập hợp gồm 26 giá trị như sau.
A B C D E F G H I J K L M
(x) = x +k mod 26
và d
k
(y) = y + (-k) mod 26 (x,y ∈ Z
26
)
-k là phẩn tử đối với k trong Z
26
, ví dụ phần tử đối của 3 là 23, phần tử đối của
15 là 11 xét trong Z
26
.
Nhận xét: Trong trường hợp k = 3, hệ mật thường được gọi là mã Caesar đã từng
được Julius Caesar sử dụ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 ứnggiữa các kí tự và các thặng dư theo modulo 26
như sau: A ↔ 0,B ↔ 1, . . ., Z ↔ 25.
Ví dụ 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ả mã 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 giá trị cho 11 (rút gọn theo modulo 26) và cuối cùng biến đổi lại dãy này
j b c r c l q r w c r v n b j e n b w r w n
i a b q b k p q v b q u m a i d m a v q v m
h z a p a j o p u a p t l z h c l z u p u l
g y z o z i n o t z o s k y g b k y t o t k
j x y n y h m n s y n r j e x f a j x s n s j
e w x m x g l m r x m q i w e z i w r m r i
d v w l w f k l q w l p h v o d y h v q l q h
c u v k v e j k p v k o g u c x g u p k p g
b t u j u d i j o u j n f t b w f o j o f
a s t i t c h i n t i m e s a v e s n i n e
Tới đây ta đã xác định được bản rõ và dừng lại. Khoá tương ứng K = 9.
Trung bình có thể tính được bản rõ sau khi thử 26/2 = 13 quy tắc giải mã. Như đã
chỉ ra trong ví dụ trên , điều kiện để một hệ mật an toàn là phép tìm khoá vét cạn phải
không thể thực hiện được; tức không gian khoá phải rất lớn. Tuy nhiên, một không
gian khoá lớn vẫn chưa đủ đảm bảo độ mật.
Lý thuyết mật mã và an toàn dữ liệu
Trang 17 2.5.2. Mã thay thế
Một hệ mật nổi tiếng khác là hệ mã thay thế. Hệ mật này đã được sử dụng hàng
trăm năm. Trò chơi đố chữ "cryptogram" trong các bài báo là những ví dụ về 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 Z
26
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
Bởi vậy d
π
(A) = d, d
π
(B) = 1, . . .
Bài tập: giải mã bản mã sau bằng cách dùng hàm giải mã đơn giản:
M G Z V Y Z L G H C M H J M Y X S S F M N H A H Y C D L M H A.
Mỗĩ 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
nên y+(-b) cũng thay đổi trên Z
26
. Bởi vậy, ta chỉ cần nghiên
cứu phương trình đồng dư:
ax ≡ y (mod 26) (y∈ Z
26
).
Ta biết rằng, phương trình này có một nghiệm duy nhất đối với mỗi y khi và chỉ khi
UCLN(a,26) = 1 (ở đây hàm UCLN là ước chung lớn nhất của các biến của nó).
Trước tiên ta giả sử rằng, UCLN(a,26) = d >1. Khi đó, đồng dư thức ax ≡ 0 (mod 26)
sẽ có ít nhất hai nghiệm phân biệt trong Z
26
là x = 0 và x = 26/d. Trong trường hợp
này, e(x) = ax + b mod 26 không phải là một hàm đơn ánh và bởi vậy nó không thể là
hàm mã hoá hợp lệ.
Giải thích theo một cách khác như sau:
Phép lập mã được cho bởi một hàm apphin dạng:
e(x) = ax + b mod 26
Để có được phép giải mã tương ứng, tức là để cho phương trình sau có nghiệm:
ax + b = c mod 26
có lời giải đối với x (với bất kỳ c cho trước), theo một định lý số học, điều kiện cần
và đủ là a nguyên tố với 26, tức là UCLN(a,26) = 1. Khi UCLN(a,26)=1 thì có:
a-1
⊆
Z
26
sao cho a.a
-1
=a
và d
k
(y) = a
-1
(y-b) mod 26, x,y ∈ Z
26Ví dụ: Giả sử k = (7,3). Như đã nêu ở trên, 7
-1
mod 26 = 15. Hàm mã hoá là
e
K
(x) = (7x+3) mod 26
Và hàm giải mã tương ứng là:
d
K
(x) = 15(y-3) mod 26 = (15y -19) mod 26=(15y +7) mod 26
7 là phần tử đối của 19.
Ở đây, tất cả các phép toán đều thực hiện trên Z
26
. Ta sẽ kiểm tra liệu d
K
(e
K
(x)) = x
với mọi x Z
26
không? Dùng các tính toán trên Z
26
(Z
26
)
m
. Với khoá K = (k
1
, k
2
, . . . ,k
m
) ta xác định :
e
K
(x
1
, x
2
, . . . ,x
m
) = (x
1
+k
1
, x
2
+k
2
, . . . , x
m
+k
Ví dụ: Giả sử m =6 và từ khoá là CIPHER. Từ khoá này tương ứng với dãy số K =
(2,8,15,7,4,17). Giả sử bản rõ là xâu: thiscryptosystemisnotsecure
Ta sẽ biến đổi các phần tử của bản rõ thành các thặng dư theo modulo 26, viết
chúng thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau:
Bởi vậy, dãy ký tự tương ứng của xâu bản mã sẽ là:
V P X Z G I A X I V W P U B T T M J P W I Z I T W Z T
Để giải mã ta có thể dùng cùng từ khoá nhưng thay cho cộng, ta trừ cho nó theo
modulo 26.
Ta thấy rằng các từ khoá có thể với số độ dài m trong mật mã Vigenère là 26
m
, bởi
vậy, thậm chí với các giá trị m khá nhỏ, phương pháp tìm kiếm vét cạn cũng yêu cầu
thời gian khá lớn. Ví dụ, nếu m = 5 thì không gian khoá cũng có kích thước lớn hơn
1,1 × 10
7
. Lượng khoá này đã đủ lớn để ngaen ngừa việc tìm khoá bằng tay( chứ
không phải dùng máy tính).
Trong hệ mật Vigenère có từ khoá độ dài m,mỗi ký tự có thể được ánh xạ vào trong
m ký tự có thể có (giả sử rằng từ khoá chứa m ký tự phân biệt). Một hệ mật như vậy
được gọi là hệ mật thay thế đa biểu (polyalphabetic). Nói chung, việc thám mã hệ thay
thế đa biểu sẽ khó khăn hơn so việc thám mã hệ đơn biểu.
19 7 8 18 2 17 24 15 19 14 18 24
2 8 15 7 4 17 2 8 15 7 4 17
21 15 23 25 6 8 0 23 8 21 22 15
18 19 4 12 8 18 13 14 19 18 4 2
1
cũng như y
2
đều là một tổ hợp tuyến tính của x
1
và
x
2
. Chẳng hạn, có thể lấy
y
1
= 11x
1
+ 3x
2
y
2
= 8x
1
+ 7x
2
Tất nhiên có thể viết gọn hơn theo ký hiệu ma trận như sau
1 2 1 2
11 8
( y ) ( )
3 7
y x x
m m
m m m
k k
y x x
k k
=
Nói một cách khác y = xK.
Chúng ta nói rằng bản mã nhận được từ bản rõ nhờ phép biến đổi tuyến tính. Ta sẽ
xét xem phải thực hiện giải mã như thế nào, tức là làm thế nào để tính x từ y. Bạn đã
làm quen với đại số tuyến tính sẽ thấy rằng phải dùng ma trận nghịch đảo K
-1
để giả
mã. Bản mã được giải mã bằng công thức y K
-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 cố định. Cho P = C = (Z
26
)
m
và cho
1
7 18
23 11
K
−
=
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:
11 8
(9,20) (99 60,72 140) (3, 4)
3 7
= + + =
Và
11 8
(11,21) (121 72,88 168) (11, 22)
3 7
= + + =
Bởi vậy bản mã của July là DELW. Để giải mã Bob sẽ tính:
a
2,2
- a
1,2
a
2,1
Một ma trận thức K là có nghịch đảo khi và chỉ khi định thức của nó khác 0. Tuy
nhiên, điều quan trọng cần nhớ là ta đang làm việc trên Z
26
. Kết quả tương ứng là ma
trận K có nghịch đảo theo modulo 26 khi và chỉ khi UCLN(det K,26) = 1.
Định lý: Giả sử A = (a
i j
) là một ma trận cấp 2 × 2 trên Z
26
sao cho det A = a
1,1
a
2,2
-
a
1,2
a
2,1
có nghịch đảo. Khi đó
2,2 1,2
1 1
2,1 1,1
(det )
−
(do theo modulo 26)
Đây chính là ma trận đã có ở trên.
Copyright: Tài liệu đại học ©