Đồ Án Môn Bảo Mật Thông Tin

Digital Signature
GVHD: Th.s Lê Phúc
Nhóm thực hiện:
Nguyễn Thị Huyền
Trần Thị Thu Hồng
Trần Quốc Việt

Digital Signature 2 Mục lục:
I. Tổng quan:
1. Giới thiệu
2. Chữ ký số
II. Kiến thức nền tảng:
1. Thuật ngữ
2. Mã hóa đối xứng
3. Mã hóa bất đối xứng
4. Hàm băm
5. Giải thuật SHA-1
III. Thuật toán tạo chữ ký số
1. Giải thuật DSA
2. Giải thuật RSA

Digital Signature 4

I. Tổng quan:
I.1.Giới thiệu:
Mạng máy tính ra đời giúp con người có thể trao đổi thông tin một cách thuận lợi hơn,
nhu cầu trao đổi thông tin ngày càng lớn và đa dạng, các tiến bộ về khoa học kỹ thuật
không ngừng phát triển ứng dụng để nâng cao chất lượng và lưu lượng truyền tin thì các
quan niệm ý tưởng về biện pháp bảo vệ an toàn thông tin cũng được đổi mới.
An toàn thông tin bao gồm các nội dung sau:
 Tính bí mật: tính kín đáo riêng tư của thông tin.
 Tính xác thực: bao gồm xác thực đối tác, xác thực thông tin trao đổi.
 Tính trách nhiệm: bảo đảm người gởi không thoái thác trách nhiệm về thông tin
mình đã gởi.
 Tính toàn vẹn: thông điệp nhận được không bị thay đổi một cách ngẫu nhiên hay
cố ý.
Bảo vệ an toàn thông tin là một chủ đề rộng liên quan đến nhiều lĩnh vực và trong
thực tế có nhiều phương pháp để thực hiện bảo vệ an toàn thông tin. Phương pháp đạt
hiệu quả và kinh tế nhất hiện nay là bảo vệ an toàn thông tin bằng biện pháp thuật toán
(Mật mã thông tin).
Mật mã thông tin là việc biến đổi thông tin thành một dạng khác nhằm che dấu nội
dung, ý nghĩa thông tin. Ngày nay, rất nhiều ứng dụng mã hóa và bảo mật thông tin được
sử dụng trong nhiều lĩnh vực khác nhau trên thế giới như an ninh, quân sự, quốc phòng
cho đến các ứng dụng thương mại điện tử ngân hàng
Trong những năm gần đây sự phát triển của khoa học máy tính và Internet càng cho

Hình 1- Những xử lý trong mô hình chữ ký số.

Tạo chữ ký số
Xác minh chữ ký số
Message/Data
Hash function
Message Digest
Message/Data
Hash function
Message Digest
Sinh chữ ký số
Private Key

II.2 Mã hóa đối xứng (Symmetric Cryptography):
Người gởi và người nhận sẽ dùng chung một khóa để mã hóa và giải mã dữ liệu.
Trước khi mã hóa dữ liệu gởi đi trên mạng người gởi và người nhận phải thống nhất khóa
và thuật toán mã. Một số thuật toán ứng dụng của mã hóa bí mật: DES, 3DES, RC2,
RC4
 Ưu điểm:
 Có thể hỗ trợ bằng phần cứng, đạt hiệu quả cao. Khóa tương đối ngắn.
 Có thể kết hợp để tạo ra các thuật toán mã hóa mạnh hơn.
 Nhược điểm:
 Trong quá trình truyền thông giữa hai người cần phải giữ bí mật cho cả
hai phía.
 Trong một mạng lớn thì số lượng khóa cần quản lý rất nhiều, do vậy để
quản lý hiệu quả cần có một bên thứ ba tin cậy.
 Khóa bí mật cần được trao đổi thường xuyên.
II.3 Mã hóa bất đối xứng (Asymmetric Cryptography)

Digital Signature 7

Hay còn gọi là phương pháp mã hóa công khai giải quyết được vấn đề phải trao đổi
khóa bí mật của mã hóa đối xứng. Với phương pháp mã hóa công khai mỗi thực thể duy
trì 2 khóa là public key và private key. Public key được công khai trên mạng trong khi
Private Key thì được giữ kín. Hai khóa này có quan hệ với nhau nhưng tính năng thì trái
ngược nhau, một khóa dùng cho việc mã hóa, còn khóa kia dùng cho việc giải mã.
 Ưu điểm:
 Chỉ có Private key cần được giữ bí mật với điều kiện việc công khai
Public key cần được đảm bảo.
 Cặp khóa riêng và công khai có thể sử dụng trong thời gian dài.
 Nhiều mô hình khóa công cộng được phát triển hình thành nên các kỹ
thuật chữ ký số hiệu quả
 Trong mạng lớn số lượng khóa quan tâm ít hơn nhiều so với việc dùng

khả năng chống lại tính chối cãi của nguồn.

II.4.2 Hash function
Hàm băm một chiều là một loại mã xác thực. Chấp nhận đầu vào là một thông điệp có
chiều dài bất kì và đầu ra là một mã băm có chiều dài cố định, gọi là hash code H(M).
Không giống với MAC (Message Authentication Code), hàm băm không dùng khóa để
tính mã xác thực, thay vào đó là một hàm được thao tác trên thông điệp.
II.4.3 Tính bảo mật của hàm băm
Đối với hệ mã hóa đồng bộ và bất đồng bộ, ta có thể chia cách tấn công vào hàm băm
thành hai loại chính là: Brute force và phân tích (cryptanalysis).
II.4.3.1 Brute force attack:
Độ mạnh của hàm băm phụ thuộc vào độ dài của hash code khi sinh ra bởi thuật
toán. Một vài thuộc tính của hàm băm:
 One way (một chiều): cho giá trị h, không thể tìm ra x để H(x)=h. Cần thử 2
n

lần.
 Đụng độ yếu (weak conllistion restriction): cho trước khối x, không thể tìm khối
y ≠ x sao cho H(y) = H(x). Cần thử 2
n
lần.
 Đụng độ mạnh (strong collistion restriction): không thể tìm thấy một cặp (x,y)
sao cho H(x)=H(y). Cần thử 2
n/2
lần.
Muốn chống lại đụng độ mạnh (điều này xem là mục đích bảo mật chính của hàm
băm), giá trị 2
n/2
dùng để xác định độ mạnh của hàm băm chống lại brute force attack.
II.4.3.2 Cryptanalysis

Block size: 512 bits=64bytes
Word size=32 bits
Message Digest=160bits
Message size < 2
64
.

 Thêm bit (padding)
Giả sử chiều dài của thông điệp M là ℓ bits. Thêm bit “1” vào sau chuỗi,
tiếp đó là k bit 0 (k≥0) sao cho k này là nhỏ nhất thỏa điều kiện sau:
ℓ+1+k ≡ 448 mod 512. Phần còn lại là 64 bits để mô tả chiều dài thực của
thông điệp M ℓ bits.
Ví dụ: giả sử M=”abc”.
Vậy ℓ=24, M thêm 1 bit 1 và 448-ℓ-1=448-24-1=423 bits 0. Sau đó thêm
64bits còn lại mô tả chiều dài chuỗi.

Digital Signature 10 Điều này tương tự với các thông điệp có kích thước nhiều khối, sau khi
thêm thì chiều dài thông điệp chia hết cho 512.
 Chia nhỏ thông điệp đã thêm bit:
Sau khi thông điệp được thêm bit nó cần được chia thành những khối 512
bits (độ dài này tùy theo giải thuật SHA).
 Khởi tạo giá trị H:
Vì đơn vị xử lý của SHA-1 là 32 bits nên:
H
0
(0)
= 67452301


}
4. Tính hash value thứ i:

}
Sau khi thực hiện qua N block ta thu được Message Digest của thông điệp
M là:

Trong đó:
 ROL
n
(a): quay chuỗi a n bits
 : phép xor.
 +: (a+b)= cộng theo số nguyên và modulo 2^32.

Digital Signature 12


 III. Các thuật toán Chữ ký số
Việc dùng mã xác thực chỉ có thể bảo vệ hai thực thể tham gia trong phiên giao dịch
đối với sự xâm phạm của thực thể thứ 3, tuy nhiên lại chưa có thể bảo vệ giữa hai thực
thể với nhau. Ví dụ: giả sử A gởi cho B một thông điệp đã được xác thực theo mô hình sử
dụng mã xác thực thông điệp (MAC), A có thể tạo ra một thông điệp khác và tính toán
MAC dựa vào key share giữa A và B, lúc này A nói thông điệp mà A tạo ra là do B gởi,

ay
)
 Trường hợp 2: sử dụng mật mã đối xứng, trong tài không thể xem nội dung
thông tin.
X → A:
ID
X
+E(M,K
xy
) +E([ID
X
+H(E(M,K
xy
))],Kxa)
A → Y:
E([ID
X
+ E(M, K
xy
)], K
ay
) + E([ID
X
+ H(E(M, K
xy
)) + T], K
xa
)

 Trường hợp 3: sử dụng mã bất đối xứng, trọng tài không thể xem nội dung

kiểm chứng chữ ký.
Theo mô hình chữ ký số trên khóa riêng dùng trong quá trình sinh chữ ký, chỉ có chủ
sở hữu mới có thể sinh chữ ký, do đó khóa riêng này cần được giữ bí mật. Những kỹ
thuật chữ ký số được thiết kế để ngăn cản những kẻ tấn công tuy không biết khóa bí mật
nhưng vẫn có thể sinh ra chữ ký đúng trên các thông điệp.
Khóa công khai dùng trong quá trình xác minh chữ ký số, nó không cần được giữ bí
mật nhưng tính toàn vẹn cần được đảm bảo. Bất kì ai cũng có thể xác minh một thông
điệp được ký đúng dùng khóa công khai thích hợp.

Digital Signature 14

Đối với cả hai quá trình sinh chữ ký và xác minh chữ ký, thông điệp được ánh xạ
thành một giá trị có chiều dài cố định (hash value). Cần có sự đảm bảo khóa công cộng
dùng để xác minh là của thực thể đã ký thông điệp. Mô hình chữ ký số cũng giống mô hình mã hóa công khai do vậy thuật toán RSA có
thể áp dụng để xây dựng chữ ký số. Hiện nay có 2 thuật toán chữ ký số thông dụng là:
RSA, DSA.

 Yêu cầu chữ kí số:
 Chữ ký phải dựa vào thông điệp được ký.
 Chứa thông tin duy nhất của người gởi để tránh giả mạo.
 Dễ dàng tạo chữ ký.
 Dễ nhận diện và xác nhận chữ ký số.
 Khó khăn giả mạo chữ ký.
Để có thể sử dụng chữ ký số ta cần sử dụng một hàm băm để rút gọn thông
điệp có chiều dài bất kì thành một giá trị băm có kích thước cố định. Giá trị
này có thể được kiểm chứng tính toàn vẹn thông tin.
 Đặc điểm của chữ ký số:

q là số nguyên tố chia hết bởi (p-1), 2
N-1
<q< 2
N
, N là chiều dài bit của p.
g là một nhóm phụ của p và q, trong đó 1<g<p.
x là khóa riêng, cần giữ bí mật, 1<x<q.
y là khóa công khai, y=g
x
mod p.
k là số bí mật được sinh ra trên từng thông điệp, 1<k<q.

III.1.1 Lựa chọn những tham số chiều dài hàm băm cho DSA
Giả sử gọi L và N lần lượt là số bit chiều dài của p và q. Chuẩn DSA nêu một số đặc tính
kỹ thuật cho 2 tham số này.
L=1024, N=160
L=2048, N=224
L=2048, N=256
L=3028, N=256
Độ mạnh bảo mật của thuật toán DSA bé hơn độ mạnh bảo mật của của cặp (L,N) và độ
mạnh bảo mật của hàm băm. Kết hợp cả hai yếu tố này sẽ xác định được độ mạnh bảo
mật của chữ ký số.

Digital Signature 16 III.1.2 Những tham số DSA
Thuật toán DSA đòi hỏi cặp khóa chung và riêng sử dụng cho quá trình sinh và xác minh
chữ ký số được sinh ra từ một tập các tham số riêng. Những tham số này có thể đại diện
cho một nhóm người sử dụng và có thể là công khai. Một người sử dụng của một tập

 Xác minh chữ ký (verifying)
 Nhận được thông điệp M’ với chữ ký là (r’,s’) xác minh xem chữ ký này có
hợp lệ hay không.
 w = ( s’ )
-1
mod q
 u1 = [ H(M’)w] mod q
 u2 = r’ w mod q
 v = [ (g
u1
y
u2
) mod p ] mod q
 nếu r’ == v thì chữ ký được xác minh.

Digital Signature 17

Hình 4 – Ký và xác minh DSA

III.2 Thuật toán RSA
Thuật toán RSA do 3 nhà toán học Ron Rivest, Adi Shamir và Len Adleman tại đại
học MIT vào năm 1977 và được công bố vào năm 1978. Thuật toán này thiết kế theo hệ
thống mã công khai.
Sự khác biệt giữa một hệ thống mã bí mật (mã đồng bộ) với một hệ mã công khai là
hệ mã công khai sử dụng 2 khóa để thực hiện mã hóa và giải mã, còn trong hệ mã bí mật
thì dùng 1 khóa cho cả hai quá trình này.
Các bước thực hiện thuật toán RSA:
Hình 5 - Mô hình chữ ký số dùng RSA

Khi A muốn gởi một thông điệp M cho B, A tính giá trị băm của M, sau đó dùng khóa
riêng của mình để mã hóa giá trị băm đó, cuối cùng đính kèm phần mã băm đã mã hóa
vào thông điệp gốc gởi cho B. Quá trình xác thực tại B, B tính toán lại mã băm dựa trên
thông điệp thu được, dùng PU của A để giải mã phần mã băm đã bị mã hóa bởi A, tiến
hành so sánh hai giá trị này với nhau, nếu trùng thì tính toàn vẹn của dữ liệu được đảm
bảo.

*Tính bảo mật của phương pháp:
Do không có cách nào để chứng tỏ một chiến lược bảo mật nào tồn tại mà chỉ có cách
kiểm tra để xem có khả năng phá vỡ nó hay không. Sau đây là cách để xác định khóa bí
mật từ việc biết được khóa công khai của người gởi thông qua việc phân tích n thành thừa
số, theo đánh giá thì nếu hiện thực thì phương pháp này xem ra là hiệu quả nhất.

Như chúng ta đã biết n được tạo ra từ hai số nguyên tố p, q. Trong việc công bố khóa
công khai sẽ tiết lộ n và e. Nếu từ việc phân tích n thu được giá trị p và q đúng thì ta có
thể suy ra được khóa bí mật.

Digital Signature 19

Thuật toán phân tích thành thừa số nhanh nhất là của Richard Schroeppel, nó có thể phân
tích n theo một sự tính toán ước lượng như sau:
Bảng sau cho biết một số thao tác cần thiết để phân tích n thành thừa số theo thuật toán
của Schroeppel và thời gian cần thiết (giả sử một thao tác cần 1 micro giây).

x, y, z. Kết quả của mỗi hàm là một word 32 bits Digital Signature 20  SHA-256 Constants
Khác với SHA-1 sử dụng 80 ràng buộc với 4 nhóm chính, SHA-256 sử dụng 64
ràng buộc 32 bits.

 Padding Message
Giống với SHA-1. Giả sử chiều dài của thông điệp M là ℓ bit. Thêm bit "1" vào
cuối thông điệp, thêm một số lượng bit 0 nhỏ nhất vào tiếp sao cho ℓ+k+1≡448 mod 512.
64 bits dùng để biểu diễn ℓ.
 Parsing the padded message
Chia thông điệp thành N khối 512 bit
 Khởi tạo H(0)

 Tính toán trong SHA-256
For i=1 to N
1. Chuẩn bị W
t2. Khởi tạo a,b,c,d,e,f,g,h.

Digital Signature 21 3. for t=0 to 63


Digital Signature 23  Khởi tạo H(0) cho SHA-384
Gồm 8 words, mỗi word 64 bits.

 Khởi tạo H(0) cho SHA-512
Gồm 8 words, mỗi word 64 bits như sau:

 Tính toán trong SHA-512
For i=0 to N
1. Chuẩn bị W
t2. Khởi tạo các biến a,b,c,d,f,e,g,h.

Digital Signature 24 3. For t=0 to 79
{

}
4. Tính H(i) Sau khi tính toán N lần, ta thu được H(N) là message digest.


m
mod w.

B5: if(j==0&&z==1) or if(z=w-1) nhảy đến B9.

B6: if(j>0&&z==1) nhảy đến B8.

B7: j=j+1. If j<a, đặt z=z
2
mod w và nhảy đến B5.

B8: w không phải là số nguyên tố. Dừng thuật toán.

B9: if(i<n) lập i=i+1 và nhảy đến B3. w là số nguyên tố.

Lập trình: Trong Java có cài đặt sẵn lớp BigInteger nằm trong gói java.math có
phương thức cài tạo một số nguyên tố, và kiểm tra xem một số bất kì có phải là
số nguyên số hay không.

VI.4 Sinh 2 số nguyên tố p và q trong DSA
Sau đây là thuật toán sinh 2 số nguyên tố p và q thỏa điều kiện:
1. Chiều dài của q là 160 bits
2. 2
L-1
<p< 2
L
, trong đó L=512+64j (0≤j≤8).
3. q chia hết bởi p-1.