Tên đề tài

CHUẨN CHỮ KÝ SỐ
VÀ ỨNG DỤNG
Giáo viên hướng dẫn : TS.Lê Phê Đô
Sinh viên thực hiện : Nguyễn Đình Lượng
Lớp CT702
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG
ISO 9001:2000
HẢI PHÒNG - 2007
MỤC ĐÍCH ĐỀ TÀI
Nghiên cứu về lý thuyết mật mã, chữ ký điện tử, Chuẩn hàm
băm an toàn và Chuẩn chữ ký số.
NỘI DUNG TRÌNH BÀY
Giới thiệu về NIST
Sơ lược hàm băm
Chuẩn hàm băm an toàn
Giới thiệu
Tiền xử lý
Các hàm sử dụng tính toán
Quy trình tính toán
Chuẩn chữ ký số
Giới thiệu
Các tham số của DSA
Lựa chọn kich thước các tham số
Tạo chữ ký số DSA
Xác nhận chữ ký số DSA
Giải thuật tạo các số nguyên tố p và q
Giải thuật xác suất Miller-Rabin kiểm tra tính nguyên tố
Giới thiệu về NIST

Tiền xử lý:
Độn bản tin
Giải sử thông điệp M có độ dài là l bit
- Với SHA-1 và SHA-256
l +1+k ≡ 448 mod 512
- Với SHA-384 và SHA-512
l +1+k ≡ 896 mod 512
Chuẩn hàm băm an toàn (SHS)
Biểu diễn nhị phân của M
l bit
1 00…00
k bit
Biểu diễn nhị phân của l
64 bit
Biểu diễn nhị phân của M
l bit
1 00…00
k bit
Biểu diễn nhị phân của l
128 bit
Tiền xử lý:
Phân phối bản tin độn
- Với SHA-1 và SHA-256
Bản tin độn sẽ được phân ra thành N khối 512 bít: M

diễn thánh 16 từ-64 bít M
0
(i)
, M
1
(i)
,…, M
15
(i)
.
Chuẩn hàm băm an toàn (SHS)
Các hàm sử dụng tính toán
SHA-1:

f
t
(x, y, z) =

SHA-256
Ch( x, y, z) = ( x y) ( x z)
Maj( x, y, z) = ( x y) ( x z) ( y z)
và
và
SHA-348 và 512
Ch( x, y, z) = ( x y) ( x z)
Maj( x, y, z) = ( x y) ( x z) ( y z)
và
và



)()()(
3187
256
0
xROTRxROTRxROTR 

)()()(
101917
256
1
xROTRxROTRxROTR 




















M, H
(0)
, K, N

i=1
a = H
0
(i-1)
; b = H
1
(i-1)
; c = H
2
(i-1)
;
d = H
3
(i-1)
; e = H
4
(i-1)










e = d ; d = c; c = ROTL
30
(b);
b = a; a = T
t ≤ 79
1
H
0
(i)
= a + H
0
(i-1)
; H
1
(i)
= b + H
1
(i-1)
;
H
2
(i)
= c + H
2
(i-1)
; H
3
(i)
= d + H
3

15) (0
1615
256
072
256
1
tWWWW
tM
W
tttt
i
t
t

Quy trình tính toán
SHA-256:
Chuẩn hàm băm an toàn (SHS)
BEGIN
M, H
(0)
, K, N

i=1
a = H
0
(i-1)
; b = H
1
(i-1)
; c = H

;
T
2
= + Ch(e, f, g) + K
t
{256}
+ W
t
;
h = g; g = f; f = e; e = d + T
1
; d = c;
c = b; b = a; a = T
1
+ T
2

t ≤ 79
1
H
0
(i)
= a + H
0
(i-1)
;H
1
(i)
= b + H
1

(i-1)
;H
7
(i)
= h + H
7
(i-1)
i ≤ N
Đúng
Sai
Sai
END
t=t+1

256
1
)(e

256
0
)(e
In H
0
(N)
|| … || H
7
(N)

i=i+1
Đúng


i=1
a = H
0
(i-1)
; b = H
1
(i-1)
; c = H
2
(i-1)
;
d = H
3
(i-1)
; e = H
4
(i-1)
; f = H
5
(i-1)
;
g = H
6
(i-1)
; h = H
7
(i-1)
1
In H

2

t ≤ 79
1
H
0
(i)
= a + H
0
(i-1)
;H
1
(i)
= b + H
1
(i-1)
H
2
(i)
= c + H
2
(i-1)
;H
3
(i)
= d + H
3
(i-1)
H
4

1
)(e

512
0
)(e
2
i=i+1
Quy trình tính toán
SHA-348:
Giải thuật này được định nghĩa giống y hệt với giải thuật SHA-
512 trừ hai điểm khác biệt duy nhất sau:
- Giá trị băm khởi tạo H
(0)
của SHA-384 khác với giá trị khởi
tạo H
(0)
của SHA-512.
- Thông điệp rút gọn của SHA-384 là: H
0
(N)
|| H
1
(N)
|| H
2
(N)
||
H
3

Các tham số của DSA
• p: là một số nguyên tố trong đó 2L-1 < p < 2L với L là độ dài
bit của biến p.
• q: là một ước số nguyên tố của p-1 trong đó 2N-1< p < 2N
với N là chiều dài của biến q(tính theo bít).
• g: là căm bậc q của 1 theo modulo p. Dễ dàng tính được g
như sau: g = h
(p-1)/q
mod p. Với 1< h < p-1
• x: là khóa bí mật. x là một số nguyên dương được tạo ra một
cách ngẫu nhiên sao cho 0< x < q-1.
• y: là khóa công khai, trong đó y = g
x
mod p.
• k: là số bí mật và là duy nhất với mỗi một tin nhắn. k là số
nguyên được tạo ra ngẫu nhiên sao cho 0 < k < q.
Chuẩn chữ ký số (DSS)
Lựa chọn kích thước các tham số p và q
Chuẩn này đưa ra một số lựa chọn cho cặp (L, N) như sau:
(L = 1024, N = 160), (L = 2048, N = 224) và (L = 3072, N =
256)
Chuẩn chữ ký số (DSS)
Tạo chữ ký số DSA
Chữ ký trên thông điệp M là một cặp số (r, s) được tính toán
như sau:
r = (g
k
mod p) mod q.
s = k
-1

BEGIN
L, N, seedlen
kiểm tra L, N
domain_parameter_seed=RBG(seedlen)
U = Hash(domain_parameter_seed) mod 2
N

q = U 2
N-1
1


q ? nguyên tố
n = L / outlen - 1;
b = L - 1 - (n * outlen)
1
Hợp lệ
END
In “Không hợp lệ”
Không hợp lệ
5
Đúng Sai
Giải thuật tạo các số nguyên tố p và q
Chuẩn chữ ký số (DSS)
1
offset=1
counter=0
j=0
V
j

counter≤4095
5
3
3
Đúng
Sai
Đúng
Sai
Đúng
Sai
Đúng
Sai
4
Giải thuật tạo các số nguyên tố p và q
Chuẩn chữ ký số (DSS)
4
In p,q, domain_parameter_seed,
counter
END
Giải thuật xác suất Miller-Rabin kiểm tra tính nguyên tố
Chuẩn Miller-Rabin như sau: cho n là số nguyên lẻ thỏa mãn
n-1 = 2e.u, với u là số nguyên tố.
• Nếu n là số nguyên tố, thì với mọi số nguyên dương a với 0
≤ a ≤ n -1:
(a
u
≡ 1 mod n) hoặc  k < e sao cho a ≡ -1 mod n (*)
• Nếu n là hợp số thì
{a: 1 ≤ a ≤ n-1, a
u

mod w
z=1 or z= w-1
j=1
z = z
2
mod w
z= w-1
z= 1
i< iteration
j < a
j=j+1
1
i=i+1
2
2
In “Nguyên tố”
In “Hợp số”
1
END
a là số nguyên lớn nhất thỏa mãn: w-1 = 2
a
;
m = (w-1) / 2
a
; wlen = len(w); i=0

Đúng
Sai
Đúng
Sai