Câu 1: Các khái niệm cơ bản của lý thuyết mã, các thao tác mã hóa cơ
bản, khóa và thuật toán mã/giải mã.
1.1 Các khái niệm cơ bản của lý thuyết mã.
- Bản gốc là dữ liệu ban đầu, có thể được hiểu mà không cần sử dụng những
công cụ, những biến đổi đặc biệt nào. Bản gốc hay còn được gọi là bản rõ.
- Bản mã hóa là kết quả của việc áp dụng phương pháp mã hóa lên bản gốc.
Với bản mã hóa, ta không thể thu được thông tin đúng mà không áp dụng
những cách thức đặc biệt. Bản mã hóa chính là dữ liệu đã được mã hóa.
- Mã hóa là phương pháp ngụy trang để ấn dấu đi nội dung thực sự của dữ
liệu.
- Giải mã là phương pháp chuyển đổi bản mã thành bản rõ.
- Khoa học mật mã là khoa học nghiên cứu về việc tạo mã và giải mã.
- Khoa học phân tích mã là khoa học nghiên cứu các nguyên lý giải mã mà
không biết khóa.
- Lược đồ mã hóa là lược đồ mô tả cách thức mã hóa của người gửi và giải
mã của người nhận.
1.2 Các thao tác mã hóa cơ bản.
- Phép thế:
+ ) Caesar cipher:
Bản chất trong mã hóa của Ceasar là thay thế các ký tự trong thư bằng
các ký tự khác theo một nguyên tắc nào đó.
+) Monoalphabetic cipher:
- Trong mật mã dịch chuyển của Ceasar. Ta có 25cách dịch chuyển khác
nhau, mỗi cách dịch chuyển cho một loại mã khác nhau.
- Thực ra với ý tưởng là sự thay thế, ta không chỉ hạn chế với phép dịch
chuyển trong bảng chữcái, khi đó bảng chữcái mật mã là bất kỳsựsắp xếp
lại nào của bảng chữcái thường. Nhưthếvới 26 chữcái ta sẽcó nhiều hơn
4 x 1026 bảng chữcái mật mã khác nhau.
- Monoalphabetic cipher là loại mã hóa thay thếchỉsửdụng một bảng chữ
cái mật mã đểthay thếcác ký tựtrong thông điệp gốc.
+) Substitution ciphers(mã thế)
• Số lượng khóa khả dĩ hay tiềm năng của một thuật toán mã hóa(giải mã) là
số lượng khóa có thể được lựa chọn như một tham số cho thuật toán mã
hóa(giải mã).Số lượng khóa khả dĩ là tùy thuộc vào thuật toán mã hóa(giải
mã).
Chú ý: nguyên lý Kerckhoff được đưa ra: “ Sự an toàn của một hệ thống mật
mã không phải phụ thuộc vào việc giữ bí mật thuật toán mật mã. Sự an toàn
này chỉ phụ thuộc vào việc giữ bí mật khóa.”
Câu 2: Trình bày về mã đối xứng.
Mã đối xứng là loại mật mã mà việc mã hóa và giải mã có thể sử dụng chung
một khóa, người mã hóa cũng có thể giải mã và ngược lại người giải mã
cũng có thể mã hóa. Mã đối xứng còn được gọi là mã một khóa.
+) Mã dịch chuyển Caesar:
- Ta lần lượt đánh chỉ số cho các chữ cái bắt đầu từ 0.
- Khi đó mã dịch chuyển Caesar có thể mô tả một cách hình thức như
sau:
+ k là một số nguyên từ 0 tới 25 được gọi là khóa.
+ Hàm mã hóa: E(k,p)=(p+k) mod 26 với p là chỉ số của ký tự cần mã
hóa.
2
+Hàm giải mã: D(k,c)=|c-k| mod 26 với c là chỉ số của ký tự cần giải
mã.
+ Như vậy số lượng khóa tiềm năng của mã dịch chuyển Caesar là
25(do k=0 không có giá trịmã hóa).
+) Mã Hill.
- Ta cũng lần lưlượt đánh chỉ số cho các chữ cái bắt đầu từ 0.
- Mã Hill dựa trên ý tư tưởng mã hóa từng nhóm các ký tự.
Cụ thể như sau:
–k là một ma trận vuông cỡ n(n là số lượng ký tự trong một nhóm).
– Hàm mã hóa: E(k,p)=k.p mod 26 với p là ma trận(1xn) với
các phần tử là chỉ số của n ký tự liên tiếp trong bản gốc.
tổ chức mong muốn được trao đổi với nhau một cách bí mật?.
• Vấn đề này được gọi là vấn đề phân phối khóa.
Cái khó của vấn đề là tồn tại một nghịch lý giữa sự bí mật và sự công
khai. Khóa mã rõ ràng là bí mật nhưngnhưng lại muốn đưđược biết bởi một
số cá nhân hay tổ chức.
+) Giải pháp phân phối khóa.
Cuối cùng thì giải pháp cho vấn đề phân phối khóa được gọi là Lược đồ trao
đổi khóa Diffie-Hellman-Merkle . Lược đồ cho phép thiết lập một kênh trao
đổi khóa bí mật trên hệ thống công cộng.
Lược đồ trao đổi khóa Diffie-Hellman-Merkle.
A và B thống nhất với nhau hai số Y và P: (7,11).
A và B chọn hai số ngẫu nhiên x và z : (3,6).
A tính α= Yx mod P : 73 mod 11=2.
B tính β= Yz mod P : 76 mod 11=4.
A gửi α cho B.
B gửi β cho A
A Tính βx mod P : 43 mod 11 = 9.
B Tính αz mod P : 26 mod 11 = 9
Thật kỳ lạ là A, B đều tính ra số 9. Đó chính là khóa mà A,B sẽ sử dụng
để trao đổi thông tin với nhau một cách bí mật.
Alice Alice và Bob ra công khai.
Diffie đã đưa ra ý tưởng mã hóa khóa công khai.
– Sử dụng một cặp khóa: một khóa công khai và một khóa
riêng.
– Một trong hai khóa có thể được sử dụng để mã hóa và khóa
còn lại để giải mã.
Tính an toàn của mã hóa khóa công khai.
• Cũng như với mã hóa đối xứng, mã hóa khóa công khai cũng luôn phải
đương đầu với tấn công vét cạn. Do đó tính an toàn của khóa công khai
cũng phải dựa trên số lượng khóa tiềm năng.
Lược đồ mã hóa
Khi đối tượng B muốn gửi một thông điệp cho đối tượng A.
Sau khi đã nhận được khóa công khai(RSA Publickey). B có
thể tiến hành mã hóa theo thuật toán sau:
Algorithm: RSA Publickey encryption
Thi hành việcxácnhận publickey (n,e).
Đặc tả thông điệp cần mã hóa như một số nguyên m: m thuộc [0,n-1].
Tính c = m
e
mod n.
Gửi cho c cho A (c chính là cipher text).
Lược đồ giải mã.
Khi A nhận được do B gửi đến.A sẽ sử dụng private key tương
ứng của mình đề giải mã thông điệp theo thuật toán sau:
Algorithm RSA private-key Decryption
m= c
d
mod n
RSA Public-key encryption
Chứng minh: Ta có e.d đồng dưvới 1 modul Ø(n) do vậy ta có: e.d= 1+k.
Ø(n).
* Khi đó nếu gcd(m,p)=1 thì theo định lý Fermat ta sẽcó: m
p-1
đồng dư với 1
modul
5
p vậythì: m
1+k(p-1)(q-1)
≡m (mod p) => m
e.d
Các số e và d là nghịch đảo nhau, có thể dùng thuật toán nghịch
đảo để tính số nọ khi biết số kia.
An toàn của RSA.
Có các cách tấn công
– Tìm kiếm khoá bằng phươngphương pháp vét cạn (không khả thi với
kích thước đủ lớn của các số).
– Tấn công bằng toán học dựa vào độ khó việc tính ø(n) bằng cách phân
tích n.
Tấn công toán học có 3 dạng
– Phân tích n = p.q, sau đó tính ø(n) và d.
– Tìm n trực tiếp và tính d.
– Tìm d trực tiếp.
- Hiện tại tin rằng tất cả đều tương đương với bài toán phân tích
thừa số nguyên
– Có các bước tiến chậm theo thời gian
– Hiện tại cho rằng RSA 1024 hoặc 2048 là an toàn
– Tấn công thời gian (trong khi giải mã).
+ Paul Kocher chỉ ra rằng kẻ thám mã có thể xác định được khoá riêng
nếu theo dõi thời gian máy tính cần để giải mã các bản tin.
+ Tấn công thời gian không chỉ áp dụng cho RSA, mà cả với các hệ mã
công khai khác.
+ Tấn công thời gian giống như kẻ cướp đoán sự an toàn bằng cách quan
sát một người nào đó trong bao lâu chuyển quay điện thoại từ số này
sang số khác.
– Tấn công với bản mã chọn trước.
+ RSA có điểm yếu với tấn công bản mã chọn trước.
+ Kẻ tấn công chọn bản mã và đoán bản rõ được giải mã.
+ Chọn bản mã để khám phá RSA cung cấp thông tin để thám mã.
6
+ Có thể tính với bộ đệm ngẫu nhiên của bản rõ. Hoặc sử dụng bộ đệm
Gửi cho c cho A(c là cipher text)
Lược đổ giải mã:
Khi đối tượng A nhận được thông điệp từ B. A tiến hành giải mã như
sau:
Algorithm Rabin Publickey dencryption
Trước hết cần tìm bốn số m
1
,m
2
,m
3
và m
4
là cănbậc hai của c modulo
n.Thông điệp được gửi có thể là một trong bốn số m
1
,m
2
,m
3
,m
4
.A bằng
một phương pháp nào đó có thể quyết định được đâu là m(plain text
thực sự).
Câu 6: Mã hóa khóa công khai ELGAMAL.
Cơ sở toán học.
7
ELGamal public-key encryption key encryption còn được xem là Diffie-
Hellman key agreement là một kỹ thuật xây dựng giao thức phân phối
a.b
Lược đồ sinh khóa.
Mỗi thức thể được tạo một publickey và một privatekeytương ứng.Khóa
được tạo theo thuật toán sau:
Algorithm: Key generation cho EL Gmal-key encryption
Sinh ngẫu nhiên số nguyên tố p và phần tử sinh α của nhóm nhân Z*
p
của
modulo p.
Chọn một số ngẫu nhiên a sao cho: 1≤a ≤p-2.Tính α
a
mod p
Publickey là : (p,α,α
a
) và Privatekey là : a.
Lược đổ mã hóa:
Khi đối tượng B muốn gửi một thông điệp cho đối tượng A. B tiến hành
mã hóa như sau:
Algorithm EL Gamal Publickey encryption
Thi hành việcxácnhận publickey (p,α,α
a
).
Đặc tả thông điẹpcần mã hóa như một số nguyên m:m thuộc [o,p-1]
Chọn mộtsố nguyên ngẫu nhiên k sao cho 1 ≤k ≤p-2 .
Tính γ=α
k
mod p và δ=m.(α
a
)
k
Bảng chữ cái gốc chính là bảng chữ cái mà mỗi chữ cái là một bộ n bits
Quá trình mã hóa khối đơn giản có thể hiểu là thay thế n bits ban đầu
bằng n bits mã hóa.Vậy nên nó cũng giống như việc thay thế chữ cái này
thành chữ cái khác.
Như thế phương thức mã hóa có thể được diễn đạt thông qua một bảng
chữ cái mã hóa mà ở đó mỗi chữ cái cũng là một bộ n bits
=> Như vậy mã khối tổng quát tương đương với mã một bảng chữ cái cổ
điển
• Mã khối tổng quát tỏ ra an toàn hơn mã môt bảng chữ cái cổ điển:
- Mã một bảng chữ cái:Việc mã hóa được tiến hành bằng cách thay thế
một chữ cái trong bản rõ thành một chữ cái trong bản mã.Như vậy số
lượng hoán vị của 26 chữ cái là 26!.Đây cũng chính là số lượng khóa
của phương pháp này. Vì 26! Là khá lớn nên khó có thể tấn công vét
cạn tuy nhiên nó bị tấn công bằng cách phân tích tần suất các chữ cái
tiếng anh:Trong ngôn ngữ TA tần suất sử dụng của các chữ cái không
đều nhau, chữ E được sử dụng nhiều nhất, còn các chữ ít được sử
dụng thường là Z,Q,J. Tương tự như vậy đối với cụm hai chữ cái và
ba chữ cái, cụm chữ TH được sử dụng nhiều nhất,
- Mã khối tổng quát: Mã hóa theo từng khối, mỗi khối có kích thước là
n bits. Với ngõ vào là n bits => sẽ có 2
n
bản rõ khác nhau,và cũng sẽ
có 2
n
bản mã khác nhau, để có thể giải mã được, mỗi bản rõ này cần
tạo ra 1 bản mã duy nhất.Như vậy số phép biến đổi là 2
n
!. Khi n càng
lớn thì mã khối tổng quát càng an toàn vì không thể tìm ra mối liên hệ
thống kê và không thể vét cạn vì hàm E tăng lên rất nhanh
của Claude Shannon
* Cấu trúc của mã Feistel:
1. Mã hóa
- Một khối của plaintext(PB) sẽ chạy qua n vòng mã hóa để sinh ra một khối
của ciphertext(CB).
- Đầu tiên PB được chia làm 2 phần ký hiệu là:R
0
,L
0.
-Khoá mã hóa K sẽ được sử dụng để sinh ra n khóa con: k
i
với 1≤i≤n
-Tại vòng mã hóa i:
2. Giải mã:
Để giải mã quá trình được thực hiện qua các vòng theo thứ tự ngược lại:
10
* Mô hình mã hóa Feistel
Nhận xét:
- Hàm thế được áp dụng trên nửa trái(F và phép XOR)
- Các vòng có cùng cấu trúc nhưng được đặc biệt hóa bởi khóa con k
1
- Cuối cùng phép hoán vị được thực hiện bằng cách đảo ngược vị trí hai
nửa
b) từ đó xác định các vấn đề cơ bản phải quan tâm khi thiết kế một mã
khối dựa trên ý tưởng chứa Horst Feistel.
- Tăng kích thước khối sẽ làm tăng độ an toàn , nhưng làm giảm tốc độ
mã.
- Tăng kích thước khóa sẽ làm tăng độ an toàn, tìm khóa khó hơn nhưng
làm chậm mã.
- Tăng số vòng làm tăng độ an toàn nhưng làm chậm mã.
= F(R
i-1
,k
i
) xor L
i-1
.
L
i=
R
i-1
.
CB = R
n
|| L
n
.
+) Nhận xét:
• Hàm thế được áp dụng trên nửa trái(F và phép xor).
• Các vòng có cùng một cấu trúc nhưng được đặc biệt hóa bởi khóa con
k
i
.
• Cuối cùng phép hoán vị được thực hiện bằng cách đảo vị trí hai nửa.
Cấu trúc của Feistel bản chất là việc thực hiện luân phiên các chức
Năng rối loạn và khuyếch tán.Cấu trúc của Feistel là một cái đặt cụ thể
cho ý tưởng của Claude Shannon.
Câu 10 : Hãy trình bày một cách ngắn gọn mật mã DES( cả mã hóa
và giải mã). Hãy cho biết DES được xây dựng trên ý tưởng mã khối
tổng quát hay ý tưởng xấp xỉ của Horst Feistel.Giải thích vì sao?
lần trong .
Thực hiện phép toán XOR cho hai dãy 48 bit và J, ta thu được một dãy
48 bit B. Biểu diễn B thành từng nhóm 6 bit như sau: .
Sử dụng tám ma trận , mỗi ma trận Si có kích thước 4x16 và
mỗi dòng của ma trận nhận đủ 16 giá trị từ 0 đến 15. Xét dãy gồm 6 bit
được xác định bằng giá trị của phần tử tại dòng r cột c
của Sj, trong đó, chỉ số dòng r có biểu diễn nhị phân là , chỉ số cột c có
biểu diễn nhị phân là . Bằng cách này, ta xác định được các dãy 4
bit
13
Tập hợp các dãy 4 bit Cj lại, ta có được dãy 32 bit . Dãy
32 bit thu được bằng cách hoán vị C theo một quy luật P nhất định chính là
kết quả của hàm
Giải mã DES.
• Giải mã đơn giản là áp dụng thuật toán mã nhưng với các khóa được sử
dụng theo chiều ngược lại. (k
16
->k
1
).
• DES gần giống như việc giữ thư bí mật bằng cách bỏ thư vào hòm và
khóa lại. Sau đó hòm thu được lại bỏ vào hòm lớn hơn và khóa lại, cứ
như vậy cho đủ 16 hòm thì thu được DES.
a) DES được xây dựng trên ý tưởng xấp xỉ của Horst Feistel.
- Được xây dựng trên ý tưởng một khối của plaintext(PB) sẽ chạy qua n
vòng mã hóa để sinh ra một khối của ciphertext(PC).
- Trong cấu tạo của DES sử dụng 2 nửa 32 bit trái và 32 bit phải. Như
đối với mọi mã Feistel, nửa phải của vòng trước được chuyển qua nửa
trái của bước sau và lấy đầu ra của hàm vòng trên nửa phải và khóa
con cộng cơ số 2 với nửa trái. Tại vòng mã hóa i:
≈7.2 *10
16
khóa tiềm năng.
• DES bị tấn công vét cạn:
+) Thám mã:
14
• Có nhiều nghiên cứu về thám mã trên DES.
• Lợi dụng những yếu điđiểm trong thiết kế của DES(S-box).
• Sử dụng kết quả thống kê=> cần một lượng thông tin lớn.
Một số hình thức chính
- Thám mã sai phân
- Thám mã tuyến tính
- Tấn công khóa liên kết.
+) Timing Attack
• Dựa trên cơ sở là: việc mã và giải mã cần một lượng thời gian khác
nhau với những input khác nhau.
• DES là hoàn hảo để đối phó với hình thức tấn công này.
• DES có thể kháng cự được với hình thức tấn công Differential
cryptanalysis.
• Việc sử dụng các S-box và các hàm hoán vị (P) làm cho DES mạnh hơn
Lucifer trong việc đối phó với thám mã sai phân.
Câu 12: Trình bày AES:
+) Mã hóa và giải mã AES.
- input cho cả mã hóa và giải mã là các khối 128 bits.
- khóa có cỡ là 128 bits.
Add round key( thêm khóa vòng)
• XOR trạng thái với 128 bit với khoá.
• Xử lý theo từng cột.
• Dễ tìm hàm ngưngược
• Thiết kế để đơnđơn giản nhất có thể:
còn lại trong nhóm đưđược tính = xor(w
i-1
,w
i-4
).
g là một hàm thực hiện liên tiếp: dịch trái, S-box, cuối cùng là xor với
một hằng số.
+) Cơ sở lý luận mở rộng khóa:
• Thiết kế chống các tấn công đã biết.
• Các tiêu chuẩn thiết kế bao gồm:
– Biết một phần khoá không đủ để biết nhiều hơnhơn.
– Phép biến đổi nghịch đảo đưđược.
– Nhanh đối với nhiều kiểu CPU.
– Sử dụng hằng số vòng để làm mất tính đối xứng.
– Khuếch tán bit khoá thành khoá vòng.
– Có đủ tính phi đối xứng để chống thám mã.
– Đơn giản trong việc giải mã.
Câu 13: Trình bày stream cipher?
Trả lời:
• Stream cipher xử lý plaintext theo từng bits hoặc theo từng nhóm nhỏ.
• Stream cipher được xây dựng như sau:
– Khóa đóng vai trò làm input cho một bộ sinh số giả ngẫu nhiên(PGN).
– Output của PGN được gọi là keystream.
– Keystream được tổ hợp với plaintext để tạo thành ciphertext.
Khi thiết kế stream cipher ta lưu ý hai yếu tố sau:
- Tính ngẫu nhiên của PNG khi sinh keystream.
- Key size.
Stream cipher đưđược chia thành hai loại:
- Stream cipher đối xứng và stream cipher bất đối xứng.
• Nếu PNG thỏa mãn những yêu cầu đặt ra trong thiết kế thì tính an toàn
swap(S[i],S[j]);
t = (S[i] + S[j]) mode 256;
ks = S[t];
end;
- Mã hóa đơn giản là sử dụng ks để xor với plaintext.
Câu 15: Chế độ thi hành mật mã khối là gì ? Nêu ngắn gọn chế độ ECB
và CBC? Phân tích ưu nhược điểm của 2 chế độ trên.
Trả lời:
+) Một chế độ thi hành là một kỹ thuật nhằm nâng cao hiệu quả của mật mã
khối cho một loại ứng dụng cụ thể.
+) Chế độ ECB-electronic code book(sách mật mã điện tử)
- ECB là chế độ đơn giản nhất, mỗi khối được mã hóa một cách riêng
rẽ, chung một khóa K cho tất cả các khối của plaintext.
- Khi dùng : truyền an toàn từng giá trị riêng lẻ.
- Mã hóa ECB
17
- Giải mã ECB
+) Ưu điểm của ECB.
- Đơn giản
- Không cần đồng bộ hóa giữa bên gửi và bên nhận.Nếu bên nhận
không nhận đủ các khối, vẫn có thể giải mã các khối nhận được.
- Các bit lỗi sẽ không được đưa vào các khối kế sau
- Vì các khối được mã hóa và giải mã hoàn toàn độc lập với nhau nên
ECB cho phép mã hóa và giải mã đồng thời nhiều khối(song song)
nếu có đủ phần cứng để thực thi
+) Nhược điểm của ECB
- ECB về bản chất giống hệt với mật mã bảng chữ cái cổ điển, chỉ có
điều bảng chữ cái của ECB phức tạp hơn.
- Các khối bản rõ giống nhau sẽ được ánh xạ thành khối bản mã giống
nhau(nếu dùng cùng 1 loại khóa) => dễ dàng tấn công bằng phương
mã.
- Cần giá trị vecto ban đầu IV được biết trước bởi người gửi và người
nhận. Tuy nhiên nếu IV được gửi công khai , kẻ tấn công có thể thay
đổi bit đầu tiên và thay đổi cả IV để bù trừ.
Câu 16: Phân tích ngắn gọn chế độ CFB, OFB, CTR. Ưu và nhược
điểm của các chế độ.
Trả lời:
+) Chế độ CFB- Cipher Feddback ( mã phản hồi ngược)
19
- Mô hình CFB có thay đổi một chút so với mô hình OFB. Mô hình OFB
dùng s bít của khóa do bộ sinh khóa tạo ra để ghép với IV cho lần
mã hóa tiếp theo. Còn mô hình CFB dùng s bít của bản mã để ghép
với IV.
CFB encrytption:
CFB decrytption:
Do đó giống như mô hình CBC, có thể thấy rằng nội dung của bản mã Ci
không chỉ phụ thuộc vào bản rõ Pi mà còn phụ thuộc vào tất cả các bản
rõ đứng trước và IV. Ngược lại, đối với việc giải mã, bản rõ Pi không chỉ
phụ thuộc vào bản mã Ci mà còn phụ thuộc vào bản mã Ci-1 đứng trước.
+) Ưu và nhược điểm của CFB
- Được dùng khi dữ liệu đến theo byte/bit.
- Chế độ dòng thường gặp nhất.
- Giống CBC
+)Nhược điểm
- Giống CBC
+) Chế độ OFB- Outer FeeBack( phản hồi ngược đầu ra)
- Mô hình CTR là một mã dòng trong đó đơn vị mã hóa có kích thước
cố định là b bít, với b là kích thước mã khối. Để mã hóa với đơn vị mã hóa
có kích thước bất kỳ, mô hình OFB được đề xuất. Mô hình này có hai điểm
khác so với mô hình CTR:
CTR sẽ chạy nhanh hơn.
- Xử lý : Nếu bộ nhớ cho phép và vẫn đảm bảo được sự an toàn thì các
output của khối mã hóa có thể được tính trước, từ đó mà tốc độ mã hóa sẽ
rất nhanh.
- Cho phép truy nhập ngẫu nhiên các khối.
+)Nhược điểm của CTR
- Về tính an toàn CTR không mạnh như các chế độ khác.
- CTR có cài đặt tương đối đơn giản do mã và giải mã là như nhau
- CTR song song hóa được ,có cấu trúc(quy luật) => độ an toàn yếu
- CTR có cài đặt tương đối đơn giản.
Câu 17: Trình bày hàm băm và hàm băm mật mã?
Trả lời:
+) Hàm băm.
22
• Định nghĩa
Cho hai miền D và R.
Một ánh xạ h: D -> R với |D|>|R|.
• Ứng dụng:
– Tìm kiếm nhanh(hash table).
– Error detection/correction.
– Cryptography: cryptographic hash function.
– Các ứng dụng khác.
• Các ứng dụng khác nhau yêu cầu những loại hàm băm khác nhau.
• Trong bối cảnh này, hash function có thể hiểu đơn giản là một ánh từ
một xâu bits bất kỳ tới một xâu bits có chiều dài cố định n.
• h: X -> Y với |X|>|Y|.
h: (0,1)* -> (0,1)
n
.
• Nếu tập X là hữu hạn thì h còn được gọi là hàm nén.
+ Phải chống tạo ảnh thứ 2.
+ Chống đụng độ, tìm được cặp có 2 giá trị băm bằng nhau.
- Trên cơ sở toán học , ta có:
Chống đụng độ, tìm được cặp có 2 giá trị băm bằng nhau => phải chống
tạo ảnh thứ 2=> phải chống tạo ảnh.
+ Chống đụng độ => chống tạo ảnh thứ 2.
Có thể tìm 1 tạo ảnh thứ 2 => có thể tìm 1 đụng độ.
Nếu ta có thể tìm được m’ là tạo ảnh thứ 2 của h(m) thì m và m’ là
một đụng độ.
23
+ Chống tạo ảnh thứ 2 => chống tạo ảnh.
Có thể tìm 1 tạo ảnh => có thể tìm 1 tạo ảnh thứ 2.
Đơn giản , giả thiết | h
-1
(y)| >1 với mỗi giá trị băm y. Có một thuật
toán xác suất A trả ra tạo ảnh của m với xác suất không nhỏ là p
Bằng cách gọi A như một hàm con, chúng ta có thể tìm tạo ảnh thứ 2
m với xác suất >= p/2
Định nghĩa : Một hàm băm được gọi là hàm băm mật mã nếu nó
chống được sự đụng độ.
Xây dựng các hàm băm như thế nào?
h : {0,1}* -> {0,1}
n
?
• Về mặt lý thuyết, ta có thể xây dựng các hàm băm chống đụng độ
bằng các hàm hoán vị một chiều.
• Trên thực tế, hàm băm mật mã được xây dựng từ các hàm nén thông
qua một tiến trình gọi là: Merkle-Damgard’s construction.
f : {0,1}
n+r
n
).
4. Giá trị băm h(m) = v
k
.
Khi thiết kế hàm băm mật mã ta hướng tới các tiêu chí sau:
1. Đầu vào là một xâu bits có cỡ “ bất kỳ ”.
2. Output phải có cỡ cố định(n)
3. Hàm phải có tính khả thi.
4. Chống đụng độ bền vững.
Trên thực tế, cỡ của xâu bits input thường có cỡ hữu hạn trong một miền
[0;2
s
]. Độ lớn của s nói chung càng lớn càng “tốt”.
Khi thiết kế hàm băm mật mã ta phải quan tâm tới độ lớn của
output(n).
- n phải đủ lớn để h có thể chống lại birthday attack.
- Birthday attack: sinh ra một tập message:
{m
1
,m
2
,…,m
k
} và kiểm tra h(m
i
)=h(m
j
).
- Birthday problem: trong một nhóm k người thì xác suất bắt gặp ít nhất 2
- Cỡ của thông điệp : 0<= l< 2
128
- Cỡ của khối : 1024 bits.
- Cỡ của giá trị băm của thông điệp : 512 bits.
- Cỡ của từ: 64 bits.
- Sử dụng 8 biến trung gian, mỗi biến là một từ 64 bits.
* Thuật toán hàm băm SHA-512 gồm 2 bước: tiền xử lý và tính toán giá trị
băm.
© Bước tiền xử lý bao gồm các thao tác:
o Mở rộng thông điệp
o Phân tích thông điệp đã mở rộng thành các khối m bit
o Khởi tạo giá trị băm ban đầu
© Bước tính toán giá trị băm bao gồm các thao tác:
o Làm N lần các công việc sau:
© - Tạo bảng phân bố thông điệp (message schedule) từ khối thứ i.
© - Dùng bảng phân bố thông điệp cùng với các hàm, hằng số, các thao
tác trên từ để tạo ra giá trị băm i.
o Sử dụng giá trị băm cuối cùng để tạo thông điệp rút gọn.
1. Tiền xử lý:
+) Padding message(Mở rộng thông điệp):
25
Copyright: Tài liệu đại học ©