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
IV. Phụ lục
1. SHA-256
2. SHA-384 và SHA-512
3. Thuật toán kiểm tra số nguyên tố.
4. Thuật toán sinh 2 số nguyên tố p và q trong giải thuật DSA
V. Ví dụ
1. SHA-1
2. DSA
3. RSA
Digital Signature 3
VI. Chương trình minh họa
1. Các chức năng chính
2. Sơ lược về việc ký và xác minh
3. Giao diện chương trình
Tài liệu tham khảo.
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ố ý.
. . .
I.2. Chữ ký số (Digital Signature):
Digital Signature 5
Là một kỹ thuật giúp sự phát triển của thương mại điện tử, giúp việc trao đổi dữ liệu được tin cậy hơn. Chữ ký số chứng minh rằng một thông điệp đã thực sự được gởi được chính người gởi mà không phải của kẻ khác giả mạo. Khi sử dụng chữ ký số ta có thể kiểm tra được tính xác thực của thông điệp. Nó không chỉ kiểm tra được thông tin về người gởi mà còn có thể kiểm tra được cả thông tin về thông điệp, giúp ta có thể biết được thông điệp có bị giả mạo hay can thiệp gì không trong quá trình vận chuyển. Chữ ký số cung cấp các chức năng quan trọng như: tính xác thực (authentication), tính bí mật (confidentiatly), tính toàn vẹn dữ liệu (data integrity), tính không thoái thác (non-repudiation).
. . .
(TÀI LIỆU CÓ RẤT NHIỀU HÌNH ẢNH MINH HỌA VỀ CÁC THUẬT TOÁN VÀ CÁC GIẢI THUẬT)
37 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 4978 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Nghiên cứu về chữ kí số (digital signature), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Đồ Á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
IV. Phụ lục
1. SHA-256
2. SHA-384 và SHA-512
3. Thuật toán kiểm tra số nguyên tố.
4. Thuật toán sinh 2 số nguyên tố p và q trong giải thuật DSA
V. Ví dụ
1. SHA-1
2. DSA
3. RSA
Digital Signature 3
VI. Chương trình minh họa
1. Các chức năng chính
2. Sơ lược về việc ký và xác minh
3. Giao diện chương trình
Tài liệu tham khảo.
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
thấy tầm quan trọng của mật mã thông tin. Ứng dụng của mật mã thông tin không chỉ đơn
thuần là mã hóa và giải mã thông tin nó còn được dùng trong việc chứng thực nguồn gốc
thông tin, xác thực người sở hữu mã hóa, các quy trình giúp trao đổi thông tin và thực
hiện trao đổi an toàn trên mạng. Sự phát triển nhanh chóng của Internet đã kéo theo một
loạt các dịch vụ mới ra đời như trò chuyện, quảng cáo, đặt hàng, mua hàng... qua Internet.
Trong số đó thì các dịch vụ thương mại điện tử là một bước nhảy vọt trong việc ứng dụng
của Internet vào cuộc sống và kinh doanh.
Ưu điểm: việc trao đổi thông tin, dữ liệu không cần qua giấy tờ, tiện lợi
trong giao dịch.
Nhược điểm: vấn đề xác thực nguồn gốc và nội dung thông tin.
I.2. Chữ ký số (Digital Signature):
Digital Signature 5
Là một kỹ thuật giúp sự phát triển của thương mại điện tử, giúp việc trao đổi dữ liệu
được tin cậy hơn. Chữ ký số chứng minh rằng một thông điệp đã thực sự được gởi được
chính người gởi mà không phải của kẻ khác giả mạo. Khi sử dụng chữ ký số ta có thể
kiểm tra được tính xác thực của thông điệp. Nó không chỉ kiểm tra được thông tin về
người gởi mà còn có thể kiểm tra được cả thông tin về thông điệp, giúp ta có thể biết
được thông điệp có bị giả mạo hay can thiệp gì không trong quá trình vận chuyển.
Chữ ký số cung cấp các chức năng quan trọng như: tính xác thực (authentication),
tính bí mật (confidentiatly), tính toàn vẹn dữ liệu (data integrity), tính không thoái thác
(non-repudiation).
Quy trình tạo và xác minh chữ ký số:
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 Chữ ký
Xác minh chữ
ký số
Public Key
Hợp lệ hay
không hợp
lệ
Digital Signature 6
II. Kiến thức nền tảng:
II.1 Thuật ngữ:
Message/Data: thông điệp dữ liệu ban đầu chưa qua quá trình xử lý (plaint-text).
CA (Certification Authority): một thực thể trong hạ tầng khóa công khai (PKI)
đảm nhiệm việc cấp phát chứng chỉ và những đòi hỏi từ chính sách PKI.
PKI (Public Key Infrastructure): một cơ cấu được tổ chức để cấp phát, duy trì, và
loại bỏ những chứng chỉ khóa công cộng.
Hash function: là hàm ánh xạ từ một chuối bit có kích thước tùy ý sang một chuỗi
có kích thước cố định.
Message Digest: kết quả của sự tính toán hàm băm trên thông điệp nguồn (cũng
được hiểu như là hash value).
Key pair: cặp public key và private key.
Private key: là một khóa trong thuật toán mã hóa bất đối xứng. Trong chữ ký số
khóa này có mối quan hệ toán học với public key và không được công khai.
Private key thường dùng để tạo chữ ký số và được xác minh bằng public key
tương ứng.
Public key: là một khóa trong thuật toán mã hóa bất đối xứng. Khóa này có quan
hệ toán học với private key và được công khai. Đối với chữ ký số, public key được
dùng để xác minh chữ ký đã được ký với private key tương ứng.
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óa đối xứng.
Khuyết điểm:
Tốc độ cho các phương thức mã hóa công khai chậm hơn rất nhiều so
với các mô hình mã hóa đối xứng.
Kích thước khóa lớn hơn rất nhiều so với mã hóa đối xứng.
Không có mô hình mã hóa công khai nào được chứng minh là an toàn.
Phần lớn các mô hình mã hóa hiện nay có sự an toàn dựa trên các giả
thuyết của của một tập nhỏ các vấn đề lý thuyết số học.
Không có bề dày lâu đời như hệ mã hóa đối xứng, nó chỉ được tìm ra
vào những năm 1970.
II.4 Hàm băm (hash function):
Hash function ánh xạ giữa một 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 (message digest). Dùng với mục đích xác thực thông điệp.
II.4.1 Điều kiện xác thực
Trong quá trình truyền dữ liệu qua mạng có một số loại hình tấn công sau:
Mạo danh (Masquerade): gởi những thông điệp vào mạng từ nguồn giả. Đây là
việc tạo các thông điệp từ một thực thể nào đó mà đã được xác thực.
Chỉnh sửa nội dung (content-modification): việc thay đổi nội dung của thông điệp
như là thêm, sửa, xóa.
Chỉnh sửa thứ tự (Sequence-modification): chỉnh sửa thứ tự các thông điệp gởi
giữa thực thể như là việc thêm, sửa, sắp xếp lại.
Chỉnh sửa thời gian (timing-modification): làm trì hoãn hay phát lại thông điệp.
Nguồn từ chối (Source Repudiation): nguồn từ chối đã truyền thông điệp.
Digital Signature 8
Đích từ chối (Destination Repudiatin): đích từ chối nhận thông điệp.
Nói chung, việc xác thực thông điệp là một thủ tục để xác minh tính thông điệp nhận
được từ một nguồn hợp lệ và không bị thay đổi. Xác thực thông điệp cũng có thể xác
minh thứ tự và tính hơp thời của thông điệp. Chữ ký số cũng là một kỹ thuật xác thực có
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ử 2n
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ử 2n 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ử 2n/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ị 2n/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
Ngoài ra còn một cách tấn công nữa là tìm lỗ hổng của giải thuật để tấn công
MAC hay hàm băm, việc tấn công này không cần phải vét cạn như vậy số lần thử
trong cách phân tích luôn nhỏ hơn hoặc bằng với brute force.
II.5 Giải thuật hàm băm bảo mật SHA
Hàm băm (hash function) hiệu quả trong quá trình xác thực thông điệp, xem như
là một fingerprint cho thông tin. Một giá trị h được sinh bởi hàm H có dạng:
h=H(M)
Trong đó M là thông điệp có chiều dài tùy ý, h gọi là giá trị băm có chiều dài cố
định. Giá trị băm này được đính kèm với thông điệp nguồn, bên nhận sẽ xác thực
Digital Signature 9
thông điệp đó thông qua việc tính toán lại giá trị băm. Do bản thân hàm băm tự nó
không bí mật nên cần có biện pháp bảo vệ giá trị băm.
Thuật toán SHA: có 4 thuật toán: SHA-1, SHA-256, SHA-384 và SHA-512.
Đây là những hàm băm một chiều (one-way hash function) có thể xử lý một thông
điệp để tạo ra Message Digest. Những giải thuật này đảm bảo tính toàn vẹn của
thông điệp: bất kì sự thay đổi nào trong thông điệp gốc sẽ có khả năng phát hiện ra
sự thay đổi đó. Điều này rất có ý nghĩa trong vấn đề tạo và xác minh chữ ký số.
Mỗi thuật toán SHA đều trải qua 2 quá trình đó là tiền xử lý và tính toán hash
value. Tiền xử lý bao gồm quá trình: padding, chia thông điệp sau khi thêm bit
thành N blocks m-bits, khởi tạo một số giá trị cho việc tính giá trị băm (W, H[i],
K). Tiếp đó là quá trình tính toán tìm giá trị băm thông qua một quy trình lặp.
Sự so sánh giữa các giải thuật SHA:
Hình 2- Các thuộc tính của SHA
Chi tiết giải thuật SHA-1: ( Các giải thuật SHA-2 xem trong phần phụ lục)
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:
H0
(0)
= 67452301
H1
(0)
= efcdab89
H2
(0)
= 98badcfe
H3
(0)
= 10325476
H4
(0)
= c3d2e1f0
Tính toán SHA-1
Sau khi chia thông điệp đã padding thành N block 512-bits
For i=1 to N
{
1. Tính Wt của từng block
2. Khởi tạo biến a, b, c , d, e.
Digital Signature 11
3. For t=0 to 79
{
}
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 đó:
ROLn(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,
B không có khả năng chứng minh điều này là sai.
Giải pháp để giải quyết vấn đề này là chữ ký số. Chữ ký số có khả năng:
Xác minh người ký và thời điểm ký.
Xác minh nội dung thông điệp tại thời điểm ký.
Có thể xác minh bởi thực thể khác giải quyết việc tranh cãi của hai thực thể này.
Có hai kỹ thuật tạo chữ ký:
Ký trực tiếp (Direct Digital Signature): hai thực thể tham gia truyền thông trực tiếp
ký trên thông điệp, đòi hỏi đích phải biết public key của nguồn để xử lý trong quá
trình xác minh. Chữ ký số này có thể là việc mã hóa cả thông điệp với private key
hay việc mã hóa hash code của thông điệp với khóa riêng. Vấn đề bảo mật khóa
riêng trong kỹ thuật ký trực tiếp.
Ký qua trọng tài:
Digital Signature 13
Trường hợp 1: sử dụng kỹ thuật mật mã đối xứng, trọng tài có thể xem nội
dung thông tin.
X → A:
M + E([IDX +H(M)], Kxa)
A → Y:
E([IDX +M + E([IDX+H(M)], Kxa) +T], Kay)
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:
IDX+E(M,Kxy) +E([IDX +H(E(M,Kxy))],Kxa)
A → Y:
E([IDX + E(M, Kxy)], Kay) + E([IDX + H(E(M, Kxy)) + T], Kxa)
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
thông tin.
X A:
IDX + E([IDX + E(E(M, PRx), PUy)], PRx)
A Y:
E([IDX + E(E(M, PRx), PUy) + T], PRa)
Kỹ thuật chữ ký số là kỹ thuật số để mô phỏng chứ ký bằng tay, dùng để xác định
người tạo ra và chịu trách nhiệm với thông tin người đó đã kí vào. Kỹ thuật chữ ký số bao
gồm 2 phần: thuật toán ký tên và thuật toán xác nhận hay kiểm tra chữ ký. Theo kỹ thuật
này thì chỉ có người tạo ra chữ ký mới có khả năng ký tên và tất cả mọi người đều có thể
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ố:
Tính xác thực: bảo đảm người ký là người tạo ra nó.
Tính an toàn: không thể giả chữ ký nếu như không biết thông tin bí mật tạo
chữ ký.
Không thể dùng lại: một chữ ký số không thể dùng cho một tài liệu khác.
Không thể phủ nhận: người ký không thể phủ nhận thông tin đã ký.
Tính hiệu quả: ký và xác minh nhanh chóng dễ dàng.
Hai mô hình chữ ký số:
(a) Tiếp cận RSA
Digital Signature 15
(b)Tiếp cận DSA
Hình 3 – Mô hình tạo và xác minh chữ ký số.
III.1 Thuật toán DSA:
Mỗi bản ký kết sử dụng một cặp khóa, một khóa riêng x và một khóa chung y có mối
quan hệ toán học với nhau. Khóa riêng được sử dụng trong một khoảng thời gian cố định
khi mà chữ ký số được sinh ra, còn khóa công cộng sẽ vẫn còn được sử dụng khi mà chữ
ký đã được sinh ra đó còn cần xác minh.
Thuật toán DSA tính toán trên một tập các tham số, một khóa riêng x, một số bí mật
trên từng thông điệp k, dữ liệu cần được ký, và một hàm băm. Đối với quá trình xác minh
cũng sử dụng các tham số, một khóa công khai y có mối quan hệ toán học với x, dữ liệu
cần được xác minh, hàm băm sử dụng trong lúc ký.
p là số nguyên tố mà 2L-1 <p< 2L , L là chiều dài bit của p.
q là số nguyên tố chia hết bởi (p-1), 2N-1 <q< 2N , 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
tham số sẽ phải có sự đảm bảo khi muốn sử dụng chúng. Tập tham số này có thể được sử
dụng trong khoảng thời gian cố định.
Miền tham số của DSA là các số nguyên p, q, g.
Các xử lý trong DSA:
Tạo khóa chung:
Tạo 1 số nguyên tố p đủ lớn chiều dài từ 512-1024 bits, là bội số chiều dài
và độ lớn của 64.
Số nguyên tố q sao cho q chia hết (p-1), chiều dài 160 bits.
Số nguyên g=h(p-1)/q mod p . Trong đó: 11.
Tạo khóa bí mật x
Khóa bí mật là giá trị x sao cho:
0 < x < q
Tạo khóa công khai y
Khóa công khai là số nguyên y thỏa:
y = g
x
mod p
Tạo số bí mật k
Số bí mật là số nguyên thỏa mãn:
0 < k < q
Tạo chữ ký (signing)
r = (gk mod p) mod q
s = [ k-1 ( H(M) + xr)] mod q
Signature = (r,s)
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 = [ (gu1yu2) 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:
Sinh khóa:
Lựa chọn 2 số nguyên tố p và q (p ≠ q)
Tính n=p*q
Tính φ(n)= (p-1)*(q-1)
Tìm e sao cho: gcd( φ(n), e) =1 (1 < e < φ(n))
Tính d: d ≡ e-1 (mod (φ(n)).
PU: {e,n}
PR: {d,n}
Mã hóa:
Plain-text: M < n
Cipher text: C= Me mod n
Digital Signature 18
Giải mã:
Cipher text: C
Plaintext: M=Cd mod n
Nhận thấy: giá trị n và e được công khai để bên gởi có thể mã hóa dữ liệu khi muốn
gởi cho thực thể này. Ở giai đoạn sinh khóa, các giá trị p và q có thể dễ dàng sinh ra
nhưng để dò ngược lại chúng từ n (vì n công khai) là rất khó. Cho nên vấn để cốt lõi
trong giải thuật RSA là sự bí mật của hai số p và q. Ta có thể tính private key dựa vào
việc phân tích n ra hai số p và q nhưng việc này không phải dễ dàng.
Thuật toán RSA trong chữ ký số:
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).
Digit Số lượng thao tác Thời gian
50 1.4*10^10 3.9 giờ
75 9.0*10^12 104 ngày
100 2.3*10^15 74 năm
200 1.2*10^23 3.8*10^9 năm
300 1.5*10^29 4.9*10^15 năm
500 1.3*10^39 4.2*10^25 năm
Theo khuyến nghị chiều dài n nên vào khoảng 200 chữ số, dài hơn hay ngắn hơn phụ
thuộc vào tốc độ mã hóa và tính bảo mật trong từng ứng dụng.
IV. Phụ Lục
IV.1 SHA-256
SHA-256 Funtions
SHA-256 sử dụng 6 hàm logic, mỗi hàm thao tác trên 32 bits word, được ký hiệu là
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ị Wt
2. Khởi tạo a,b,c,d,e,f,g,h.
Digital Signature 21
3. for t=0 to 63
4. Tính toán H(i)
Sau khi tính toán qua N lần, kết quả là một message digest 256 bits như sau:
IV.2 SHA-384 và SHA-512
Digital Signature 22
Những hàm SHA-384 và SHA-512
Hai giải thuật này sử dụng 6 hàm logic, mỗi hàm thao tác trên 64 bit, ký
hiệu là x, y, z. Kết quả là giá trị 64 bits
Ràng buộc trong SHA-384 và SHA-512
Hai thuật toán này sử dụng 80 ràng buộc, mỗi ràng buộc 64 bit. K0 , K1,…,
K79 .
Padding the Message
Giả sử chiều dài bit của thông điệp M làℓ. Thêm 1 bit “1” vào cuối chuỗi,
sau đó thêm k bit “0” (k là số nhỏ nhất) sao cho k+ℓ+1≡896 mod 1024.
Dùng 128 bits còn lại để biểu diễn giá trị ℓ.
Ví dụ: giả sử M=”abc”, ℓ=8*3=24. Vậy k=896-(24+1)=871 bit “0”, thông
điệp M sau khi thêm sẽ có chiều dài 1024 bits.
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ị Wt
2. 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.
Tính toán trong SHA-384
Việc tính toán trong SHA-384 hoàn toàn giống với SHA-512 ngoại trừ 2
yếu tố:
a) Khởi tạo hàm H
b) Kết quả Message Digest chỉ lấy 384 bit cao nhất của H(N).
Digital Signature 25
IV.3 Kiểm tra một số nguyên tố:
Giải thuật này do M.O.Rabin tìm ra dựa trên một phần ý tưởng của Gary L.
Miller. Theo giải thuật này thì nếu được lặp lại n lần, xác suất sinh ra một số
nguyên tố sai nhỏ hơn 1/4n . Vì thế xác suất khi chọn n>=50 là chấp nhận
được. Chi tiết các bước thực hiện như sau:
B1: Đặt i=1 và chọn n>=50
B2: Xét w là số nguyên cần kiểm tra xem có phải là số nguyên tố hay không.
w=1+2
am, trong đó m là một số lẻ và 2n là lũy thừa lớn nhất của 2 chia cho w-1
B3: Sinh một số nguyên b ngẫu nhiên sao cho 1<b<w.
B4: Đặt j=0 và z=bm 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=z2 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. 2L-1 <p< 2L , trong đó L=512+64j (0≤j≤8).
3. q chia hết bởi p-1.
Digital Signature 26
Thuật toán này sử dụng SHA-1 cùng với việc dùng hạt nhân SEED để sinh ra số
nguyên tố q. Từ đó sinh ra giá trị X từ cùng SEED này 2L-1 <X< 2L . Sau đó số
nguyên tố p được tạo thành thông qua việc làm tròn X đồng dạng với 1 mod 2q.
Chi tiết thuật toán:
Đặt L-1=n*160+b, trong đó b và n là các số nguyên và 0≤b<160
B1: Chọn một giá trị SEED nhỏ hơn 160 bits. Gọi g là số bit trong SEED đó.
B2: Tính:
U=SHA-1[SEED] XOR SHA-1[(SEED+1) mod 2
g
].
B3: q=U OR 2
159
OR 1.
B4: Kiểm tra xem q có phải là số nguyên tố hay không
B5: Nếu q không phải là số nguyên tố, trở về B1.
B6: Đặt counter=0, offset=2.
B7: for k=0 to n
Vk=SHA-1[(SEED + offset + k) mod 2
g
]
B8: Đặt số nguyên W:
Và đặt X=W + 2L-1. Trong đó 0≤W≤2L-1, vì vậy 2L-1 ≤X≤2L.
B9: Đặt c= X mod 2q và đặt p=X-(c-1). p≡1 mod 2q.
B10: if(p<2
L-1
) nhảy đến B13.
B11: Kiểm tra xem p có phải là số nguyên tố hay không.
B12: Nếu p là số nguyên tố thì đến B15
B13: Đặt counter=counter+1 và offset=offset+n+1.
B14: if(counter>=4096) nhảy về B1, else nhảy về B7.
B15: Giữ giá trị SEED và counter dùng cho việc sinh giá trị p và q.
V. Ví dụ
V.1. SHA-1
Giả sử M= “abc”
ℓ=24
Xác định 16 word đầu tiên
Digital Signature 27
Bảng sau thể hiện các giá trị a,b,c,d,e trong 80 vòng ( t từ 0 đến 79)
Digital Signature 28
Giá trị băm cuối là:
Digital Signature 29
Vậy message digest là:
H= a9993e36 4706816a ba3e25717850c26c9cd0d89d
V.2 DSA
p= 8df2a494 492276aa 3d25759b b06869cb eac0d83a fb8d0cf7
cbb8324f 0d7882e5 d0762fc5 b7210eaf c2e9adac 32ab7aac
49693dfb f83724c2 ec0736ee 31c80291
q= c773218c 737ec8ee 993b4f2d ed30f48e dace915f
g= 626d0278 39ea0a13 413163a5 5b4cb500 299d5522 956cefcb
3bff10f3 99ce2c2e 71cb9de5 fa24babf 58e5b795 21925c9c
c42e9f6f 464b088c c572af53 e6d78802
x= 2070b322 3dba372f de1c0ffc 7b2e3b49 8b260614
k= 358dad57 1462710f 50e254cf 1a376b2b deaadfbf
k
-1
= 0d516729 8202e49b 4116ac10 4fc3f415 ae52f917
SHA-1(“abc”) = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
y = 19131871 d75b1612 a819f29d 78d1b0d7 346f7aa7 7bb62a85
9bfd6c56 75da9d21 2d3a36ef 1672ef66 0b8c7c25 5cc0ec74
858fba33 f44c0669 9630a76b 030ee333
r = 8bac1ab6 6410435c b7181f95 b16ab97c 92b341c0
s = 41e2345f 1f56df24 58f426d1 55b4ba2d b6dcd8c8
w = 9df4ece5 826be95f ed406d41 b43edc0b 1c18841b
u1 = bf655bd0 46f0b35e c791b004 804afcbb 8ef7d69d
Digital Signature 30
u2 = 821a9263 12e97ade abcc8d08 2b527897 8a2df4b0
g
u1
mod p = 51b1bf86 7888e5f3 af6fb476 9dd016bc fe667a65 aafc2753
9063bd3d 2b138b4c e02cc0c0 2ec62bb6 7306c63e 4db95bbf
6f96662a 1987a21b e4ec1071 010b6069
y
u2
mod p = 8b510071 2957e950 50d6b8fd 376a668e 4b0d633c 1e46e665
5c611a72 e2b28483 be52c74d 4b30de61 a668966e dc307a67
c19441f4 22bf3c34 08aeba1f 0a4dbec7
v = 8bac1ab6 6410435c b7181f95 b16ab97c 92b341c0
V.3 RSA
Giá trị tính theo hệ 10.
p =
133292657448557616802657131665285833287877734001136246987594108938323041
565963184047372525300048638222671381997285204077359844477346621486175708
514662953388831972497347014683246110657167088788554998459502628712251992
480921617791784084360810958873999832051687214683235767948555343134155829
585783099993417928279
q =
914752293194834722444127979748526806105022056483901995340123628609819164
056441932958048074541895555642029604328753370506498618905603461196860052
722522533009877354107862071173509339982296641071150270213583050119583058
372827465687249086020522197292702482154659499922137898469654903694249793
17962047623792056977
n =
121929764067101647430675890922291673582665413588522445540051132331873243
627138367570820968261817375797443533451407773906058199080948494750468742
679507444361498598362131942827182158496537654489340140734662947115566636
928293759047196211574561550648659452267854998174520600188507930094548805
734111099592361289409066190253256621719660468763823181479207673145108009
553945455586146793147353033853193600262779413437681590978280502975527355
566256210201313382264036477882030989239251670505276485491574782128451802
196611502452268596953500798507237944217465353623313428892434260589497201
45489285578377445963347871754987267552583
(p-1)(q-1) =
121929764067101647430675890922291673582665413588522445540051132331873243
627138367570820968261817375797443533451407773906058199080948494750468742
Digital Signature 31
679507444361498598362131942827182158496537654489340140734662947115566636
928293759047196211574561550648659452267854998174520600188507930094548805
734111099592361289406818511385576210829189769467421796340223873748612745
088729390868153743567636960079761826935237031499812847553978897564247258
502577140525254765126167325815132792160170338287270515045020814599495101
941802893115026493970318754863632854287836721837280728089762728942742705
87693764744873865154444126607370057567328
e =
176104600836597418745778256964402408956712209503179709019887721425658953
033509456613884723861708069843925873849624064652935165252471311243014884
007714083867275825779950211809621165266308146156135802858523986287238012
672833978375133249631493134364174457761960680149643912629143034170564579
614147665408038712533
d =
458247634583134693624909553695269214556413947970693332310147203524870321
535410186123636273343733459549468208153699230495371360036226134765061404
090302603825362520543975159561011722196965452817919080722862600644431538
453853760391139165797303728607757859706052283629544190890124219052610668
668901002113592855027727734667909003290930525287934010213503392073914495
345251246449212174532806075804680254875755399149700562946330449536941538
672767154070966044854297661938272119299058418082166820263335086755791333
271043194038276623850634185992306546713998903523547487058629087955428738
4815504795162195323770165482458379717533
H (“abc”) = 968236873715988614170569073515315707566766479517
C =
600535078200821363499995363357174276785482254622416432910645395938015897
052286373896027465962611597327003974168830525590621062042141617323245097
756096929245424952534436043346127153267335457894286206633063184016171540
516515721551589629071697237057733334356860094376735298300842428691747892
013472398096350167338934748199875441036737813230280357038713021440784280
046801541545544802099280811526642847601778498422094767806973370663508784
016030094752710067649126219344588764217568888961421964785218828201165489
086290811340888938442394884007646691187807020541705902151954218949418806
8350699903481413803007352962344509433185
VI. Chương trình minh họa
VI.1 Các chức năng chính của chương trình
Digital Signature 32
Tạo mới một chứng chỉ: tạo cặp khóa riêng và chung.
Thực hiện ký kết trên một dữ liệu.
Xác minh dữ liệu.
Import khóa riêng, khóa chung.
Export khóa riêng, khóa chung.
Biểu diễn các khóa có trong cơ sở dữ liệu.
VI.2 Sơ lược về việc ký kết và xác minh dữ liệu.
Ký kết
Input:
o Định danh cần ký.
o Thuật toán dùng tạo khóa.
o Thông điệp cần ký.
o Nơi trích xuất chữ ký
Output
o Chữ ký tương ứng với thông điệp cần ký.
Xác minh
Input:
o Xác minh cho định danh nào.
o Thông điệp nhận được.
o Chữ ký mà bên gởi đã ký.
Output:
o Nguồn gốc và nội dung chính xác.
VI.3 Giao diện chương trình:
Giao diện chính
Menu file:
Digital Signature 33
Menu Action:
Form tạo chứng chỉ:
Lưu đường dẫn khóa công cộng khi tạo chứng chỉ.
Digital Signature 34
Đã xuất hiện user myteam trong cơ sở dữ liệu.
Khi ký cần phải login, yêu cầu nhập passphrase vì cần xác phải unlock khóa private.
Khi đã nhập đúng username và passphrase sẽ cho phép xác minh thông tin ứng với username đó.
Digital Signature 35
Khi nhấn nút sign file sẽ xuất hiện dialog lưu chữ ký số ứng với username và thông tin đã ký.
Nếu việc ký file thành công sẽ sinh ra chữ ký số.
Việc xác minh chữ ký số:
Vì việc xác minh đòi hỏi biết khóa công cộng của bên ký cho nên trong cơ sở dữ liệu cũng cần
có thông tin về khóa công cộng này, thông qua việc nhập username (không yêu cầu nhập
passphrase). Nếu trong cơ sở dữ liệu chưa có thông tin khóa công cộng của user đó sẽ không thể
xác thực. (Chương trình cũng có chức năng import khóa công cộng).
Form login để xác thực chỉ cần nhập username
Xác minh thông tin cần file thông tin và chữ ký
Digital Signature 36
Tài liệu tham khảo
[1] Security - 2005 - Cryptography and Network security Principles and Practices by
William Stalling.
[2]
Digital Signature 37
Các file đính kèm theo tài liệu này:
- NGHIÊN CỨU VỀ CHỮ KÍ SỐ (Digital Signature)-Ths Lê Phúc -Trường Đại Học BK TpHCM hướng dẫn.pdf