1. Cơ sở hình thành nên chữký số1.1 Cơ sở toán học

Số học là một nhánh của toán học, nhưng nó lại trở thành một trong những công cụ hữu hiệu nhất của ngành an ninh máy tính. Như là sự khởi đầu, số học giúp bảo vệ những dữ liệu nhạy cảm như số thẻ tín dụng khi giúp người dùng mua sắm trực tuyến. Đó chính là kết quả của một số thành tựu nghiên cứu đáng ghi nhận từ những năm 1970 tới nay, đã được áp dụng rộng rãi trên thế giới. Những giao thức mã hóa đặc biệt là chữ ký số điện tử đều dựa trên lý thuyết số học để tạo khóa, mã hóa và giải mã. An tòan của những giao thức này đều liên quan tới vấn đề trong số học : giải thuật công khai và phân tích thừa số nguyên tố.

1.1.1 Sinh số nguyêntố vàphân tích thừa sốnguyêntố

Hai hệ quả và một ước lượng trong thuyết số học là tiền đề cho hệ thống khóa công khai RSA ngày nay

Hệ quả 1 : Sinh số nguyên tố thì dễ. Việc tìm ra một số nguyên tố ngẫu nhiên với kích cỡ cho trước là dễ dàng.

Nó là kết quả của hai điểm khác : Số nguyên tố với kích thước bất kỳ thì rất phổ biến và việc kiểm tra số nguyên tố thì không khó – thậm chí với cả số nguyên tố rất lớn Để sinh số nguyên tố ngẫu nhiên, đơn giản nhất là chỉ việc sinh ra một số nguyên ngẫu nhiên với độ lớn đã cho và kiểm tra tính nguyên tố cho đến khi một số nguyên tố được tìm thấy. Dựa vào điều kiện số nguyên tố, một số kỳ vọng được kiểm tra dựa vào thứ tự của lnx( thuật toán tự nhiên của x) khi mà x là một số điển hình với độ lớn mong muốn.

Việc kiểm tra một số là số nguyên tố là không dễ. Trong thực tế, dường như việc kiểm tra tính nguyên tố sẽ yêu cầu một số khác ngoài chính số đó và số 1 là ước của số nguyên cần kiểm tra. Hầu hết các hệ mã hóa khóa công khai ngày nay đề phụ thuộc vào việc sinh số nguyên tố.

Cho p, và q là 2 số nguyên tố lớn được sinh ngẫu nhiên.(kích cỡ trung bình trong các hệ mã hóa thường là 512 bits hoặc lớn hơn).

Hệ quả 2 : Phép tính nhân là dễ : Với p và q cho trước, việc tính kết quả của phép nhân n = pxq là dễ dàng.

Ước lượng 3 : Phân tích thừa số là khó : Với một số nguyên n là kết quả của phép nhân số nguyên tố lớn, việc tìm lại các số nguyên tố thừa số p, q là rất khó.

Bất chấp hàng trăm năm nghiên cứu trong vấn đề này, việc phân tích ra thừa số của một số nguyên lớn vẫn mất rất một thời gian dài. Phương pháp nhanh nhất gần đây đã nhanh hơn rất nhiều so với những cách đơn gaỉn là tìm tất cả các thừa số ở cùng một thời

điểm. Tuy nhiên, chúng vẫn rất đắt. Cho ví dụ, việc phân tích ra thừa số nguyên tố cua một số 1024 bit mất một năm với một máy giá 10 triệu USD. Với một số 2048 bit thì thời gian để hoàn thành còn gấp vài tỉ lần.

Những ước lượng này thì ít hơn so với dự kiến ở những năm 1970 khi vấn đề đầu tiên được đề xuất trong ngành mật mã học. Độ lớn khuyến cáo đã tăng nhanh trong những năm gần dây, bởi sự khám phá ra những phương thức phân tích thừa số nhanh hơn cũng như sụ phá triển trong sức mạnh tính toán của máy tính. Không ai biết những phương thức nhanh hơn sẽ được phát hiện trong những năm tới sẽ xảy ra bao giờ. Nhưng mặt khác, không ai có thể chứng minh nó sẽ không xảy ra. Cả hai khía cạnh đều tồn tại thành những lĩnh vực nghiên cứu của toán học.

1.1.2Phép mũ hóa và khai căn modul

Như ở trên ta đã khai báo n là kết quả của phép nhân hai số nguyên tố lớn được sinh ngẫu nhiên. Cho m và c là những số nguyên nằm trong khoảng (0,n-1) và e là một số nguyên lẻ trong khoảng (3,n-1) và nguyên tố cùng nhau với p-1 và q-1.

Thao tác mã hóa và giải mã trong hệ mã hóa khóa công khai RSA được thực hiện dựa trên 2 hệ quả và 1 ước lượng sau :

Hệ quả 4: Phép tính mũ hóa modul là dễ : Cho n,m và e. Việc tính c = me mod n là dễ dàng

Giá trị me mod n chính thức là kết quả của nâng lũy thừa e của m, chia cho n và lấy phần dư. Điều này có thể là một phép tính toán phức tạp liên quan tới việc nhân (e-1) số m và kết quả trả về là một số nguyên lớn, trước khi việc thực hiện phép chia cho n. Tuy nhiên hai cách tối ưu hóa sau làm cho việc tính toán trở nên dễ dàng :

- Nhân với một trình tự thích hợp của các giá trị trung gian trước đó, thay vì hơn chỉ bằng m, có thể giảm số lượng các phép nhân để không quá hai lần kích thước của e trong hệ nhị phân

- Chia và lấy phần dư sau khi mỗi phép nhân giữ kết quả trung gian có cùng kíchthước như n

Hệ quả 5 : Phép khai căn module – nghịch đảo của phép lũy thừa module. mod n là dễ dàng.

Giá trị m có thể khôi phục từ c bởi thao tác mũ hóa modul với một số nguyên lẻ d nằm trong khoảng (3,n-1). Đặc biệt, với số d này, biểu thức sau thể hiện cho tất cả m : m = (me)d mod n.

Số nguyên d này thì dễ dàng tính với e, p, q cho trước.

Ước lượng 6: Phép khai căn modul lại khó ở một hoàn cảnh khác

Cho n,e, và nhưng không biết những thừa số nguyên tố, việc khôi phục lại m là khó khăn.

Phương pháp nhanh nhất thì có sẵn trong việc tính toán khai căn modul dưới điều kiện dựa là n và e là phân tích thừa số n và áp dụng hệ quả 5 để quyết định d. Thực sự, bất kỳ phương thức nào quyết định d đều bị chuyển về một cách khác của việc phân tích thừa số n. Đúng là có thể khi mà tồn tại một phương pháp mà tính toán khai căn modul mà không cần phân tích n hoặc quyết định d. Nhưng cho đến nay chưa phương phàp nào có thể làm như vậy nhanh hơn việc phân tích thừa số n.

Nhận xét :

Số học, đặc biệt là số nguyên lớn và các phép tính đồng dư là những công cụ quan trọng trong mật mã học đặc biệt là trong việc tính toán mật mã học khóa công khai, điển hình là RSA. Tuy nhiên chương này cũng chỉ trình bày qua các thuật toán để làm việc với những số nguyên lớn mà hầu hết đều đã được cài đặt thành thư viện nên ở những hệ thống thực tế người ta sẽ sử dụng chúng để tiện cho quá trình cài đặt.

1.2 Hàm băm mật mã1.2.1 Giới thiệu

Trong ngành mật mã học, một hàm băm mật mã học (cryptographic hash function) là một hàm băm với một số tính chất bảo mật nhất định để phù hợp việc sử dụng trong nhiều ứng dụng bảo mật thông tin đa dạng, chẳng hạn như chứng thực (authentication) và

kiểm tra tính nguyên vẹn của thông điệp (message integrity). Một hàm băm nhận đầu vào

là một xâu ký tự dài (hay thông điệp) có độ dài tùy ý và tạo ra kết quả là một xâu ký tự có độ dài cố định, đôi khi được gọi là tóm tắt thông điệp (message digest) hoặc chữ ký số (digital fingerprint)[11].

Các hàm băm nhận một chuỗi bit có chiều dài tùy ý ( hữu hạn) làm dữ liệu đầu vào và tạo ra một chuỗi bit có chiều dài cố định bằng n bit, gọi là mã băm. Sự thay đổi nhỏ của chuỗi đầu vào cũng làm thay đổi giá trị băm. Ký hiệu D là miền xác định, R là miền giá trị của hàm băm h(x).

h(x) : D  R

Ta có số lượng phần tử của tập D lớn hơn giá trị của tập R  hàm băm h(x) không

phải là đơn ánh  Luôn tồn tại cặp đầu vào khác nhau có cùng giá trị băm.

Giả sử hạn chế hàm h(x) trên miền xác định chỉ bao gồm các chuỗi bit có chiều dài t (t>n). Nếu h(x) là ngẫu nhiên với tất cả các giá trị đầu ra của nó có xác suất bằng nhau thì có khoảng 2(t-n) đầu ánh xạ vào mỗi giá trị đầu ra. Xác suất để hai giá trị( có chiều dài bằng nhau) đầu vào ánh xạ vào cùng một giá trị là 2-n(không phụ thuộc vào t)  Nếu n lơn thì 2-n sẽ rất nhỏ. Như vậy mặc dù biết trước giá trị băm nhưng để tìm một đầu vào có cùng giá trị băm với giá trị băm đã biết là rất khó nếu chọn được h(x) thích hợp và n đủ lớn.

Trong lĩnh vực mã hóa thông tin, mã băm được xem như đặc trưng thu gọn của một chuỗi bit tùy ý và dùng để nhận ra chuỗi bit đó. Hàm băm chính là công cụ để tạo ra chữ ký số và đảm bảo an toàn dữ liệu

1.2.2Các khái niệm vàđịnh nghĩa :

Hàm băm là một giải thụât nhằm sinh ra các giá trị băm tương ứng với mỗi khối dữ liệu. Giá trị băm đóng vai trò gần như một khóa để phân biệt các khối dữ liệu

Hình 3.1 – Sơ đồ hàm băm.

Phân loại :

Hàm băm một chiều : (one – way hash functions) : Là hàm băm mang chất : với mọi mã băm biết trước, không thể tính toán để tìm được chuỗi bit ban đầu vào có mã băm bằng với mã băm đã cho

Hàm băm kháng xung đột : (collision resistant hash funtions) là hàm băm mang tính chất : không thể tính toán để tìm ra hai chuỗi bit có cùng giá trị băm

Một số tính chất cơ bản của hàm băm :

- (i) Có thể áp dụng với thông báo đầu vào có độ dài bất kỳ

- (ii) Tạo ra giá trị băm y = h(x) có độ dài cố định

- (iii) h(x) dễ dàng tính được với bất kỳ x nào

- (iv) Tính một chiều : Với mọi đầu ra y cho trước không thể tìm được x' sao cho h(x') bằng giá trị y cho trước

- (v) Tính chống xung đột yếu : Với mọi dữ liệu đầu vào x1 cho trước không thể tìm được bất kỳ giá trị x2 nào (x2 khác x1) mà h(x2) = h(x1).

- (vi) Tính chống xung đột mạnh : Không thể tính toán đẻ tìm được hai dữ liệu đầu vào x1 và x2 phân biệt sao cho chúng có cùng giá trị băm (h(x1) = h(x2))

Như vậy dựa theo các tính chất tren ta thấy hàm băm một chiều thỏa mãn tính chất (iv) và tính chất (v), còn hàm băm kháng xung đột thỏa mãn tính chất (iv) và (vi).

1.2.3 Cấu trúc cơ bản của thuật toán băm

Khối dữ liệu đầu vào x có chiều dài hữu hạn tùy ý sẽ được phân thành các khối conliên tiếp có chiều dài cố định r, giả sử được đánh số là x1,x2,...,xm. Tuy nhiên do chiều dài của khối dữ liệu ban đầu x là tùy ý, do đó cần phải thêm vào dữ liệu ban đầu một số bit phụ sao cho tổng số bit của khối dữ liệu x' sau khi thêm vào sẽ là bội số của r. Ngoài ra khối bit thêm vào thường chứa một khối bit (có chiều dài cố định trước, thường là 64 bit) xác định chiều dài thực sự của khối bt dữ liệu khi chưa thêm các bit phụ.

Tiếp theo, lần lượt cắt các khối con r bit từ khối mở rộng x'. Mỗi khối con r bit xi lần lượt bước qua một hàm nén f của hàm băm h(x). Tại bước thứ i, hàm nén f nhận dữ liệu đàu vào là xi và kết quả trung gian của bước trước đó (bước i – 1) để tạo đầu ra là kết quả trung gian bước thứ i, được ký hiệu là Hi . Kết quả trung gian tại mỗi bước Hi là một chuỗi bit có độ dài cố định bằng n > 0.

Kết quả ký hiệu IV là giá trị ban đầu (cho H0 ), thì quá trình lặp xử lý dãy các khối con x1,x2,..,xm được mô tả :

H0 = IV

Hi = f(Hi-1,xi) (i = 1,2,..,m)

h(x) = g(Hm)

- Các biến Hi là các biến dây chuyền

- Hàm g(x) lấy biến dây chuyền cuối cùng để tạo ra mã băm cuối cùng cần tìm. Trong hầu hết các thuật toán g(x) thường được chọn là ánh xạ đồng nhất tức là g(Hm) = Hm

- Khâu then chốt trong xây dựng hàm băm là thiết kế hàm nén f

- Giá trị của hàm băm mật mã của một thông điệp được gọi là Message Digest (MD).

Một số hàm băm mật mã thông dụng : MD4,MD5,SHS và SHA-1

1.2.4 Hàm băm MD4

Hàm hash MD4 được Rivest đề xuất năm 1990. Chúng ta xem miêu tả thuật tóan MD4.

Đầu vào: Bản tin M có chiều dài nhỏ hơn 264.

1. Mở rộng bản tin: Thêm các bít vào bản tin để bản tin có chiều dài là bội của 512. Quá trình thêm diễn ra như sau. Thêm bít 1 vào cuối bản tin, sau đó thêm vào một số bít 0 để nhận bản tin có chiều dài là đồng dư với 448 modulo 512, và cuối cùng thêm vào 64 bít, 64bít này biểu diễn chiều dài của bản tin ban đầu. Bản tin được thêm vào bao gồm các khối M1, M2, ... , Mn, chiều dài mỗi khối là 32 bít.

2. Khởi tạo các biến:

A=67452301 B=EFCDAB89 C=98BADCFE D=10325476

3. i=1

4. for j=1 to 16 do X[j]=M[16i+j]

5. AA=A;BB=B;CC=C;DD=D;

6. round1

7. round2

8. round3

9. Nếu i < n/16 thì i=i+1 và quay về bước 4.

10. A=A+AA;B=B+BB;C=C+CC;D=D+DD;

Đầu ra: 128 bít là liên kết của 4 từ 32 bít:A|B|C|D.

Trong 3 vòng "round1", "round2","round3" sử dụng 3 hàm bool sau:

g(X,Y,Z)=(X^Y)v(X^Z)v(Y^Z).

Round1 được miêu tả như sau:

1. A=(A+f(B,C,D)+X[1])<<3

2. D=(D+f(A,B,C)+X[2])<<7

3. C=(C+f(D,A,B)+X[3])<<11

4. B=(B+f(C,D,A)+X[4])<<19

5. A=(A+f(B,C,D)+X[5])<<3

6. D=(D+f(A,B,C)+X[6])<<7

7. C=(C+f(D,A,B)+X[7])<<11

8. B=(B+f(C,D,A)+X[8])<<19

9. A=(A+f(B,C,D)+X[9])<<3

10. D=(D+f(A,B,C)+X[10])<<7

11. C=(C+f(D,A,B)+X[11])<<11

12. B=(B+f(C,D,A)+X[12])<<19

13. A=(A+f(B,C,D)+X[13])<<3

14. D=(D+f(A,B,C)+X[14])<<7

15. C=(C+f(D,A,B)+X[15])<<11

16. B=(B+f(C,D,A)+X[16])<<19

Round2 được miêu tả như sau:

1. A=(A+g(B,C,D)+X[1]+5A827999)<<3

2. D=(D+g(A,B,C)+X[2] +5A827999)<<5

3. C=(C+g(D,A,B)+X[3] +5A827999)<<9

4. B=(B+g(C,D,A)+X[4] +5A827999)<<13

5. A=(A+g(B,C,D)+X[5] +5A827999)<<3

6. D=(D+g(A,B,C)+X[6] +5A827999)<<5

7. C=(C+g(D,A,B)+X[7] +5A827999)<<9

8. B=(B+g(C,D,A)+X[8] +5A827999)<<13

9. A=(A+g(B,C,D)+X[9] +5A827999)<<3

10. D=(D+g(A,B,C)+X[10] +5A827999)<<5

11. C=(C+g(D,A,B)+X[11] +5A827999)<<9

12. B=(B+g(C,D,A)+X[12] +5A827999)<<13

13. A=(A+g(B,C,D)+X[13] +5A827999)<<3

14. D=(D+g(A,B,C)+X[14] +5A827999)<<5

15. C=(C+g(D,A,B)+X[15] +5A827999)<<9

16. B=(B+g(C,D,A)+X[16] +5A827999)<<13

Round3 được miêu tả như sau:

1. A=(A+h(B,C,D)+X[1]+6ED9EBA1)<<3

2. D=(D+h(A,B,C)+X[2] +6ED9EBA1)<<9

3. C=(C+h(D,A,B)+X[3] +6ED9EBA1)<<11

4. B=(B+h(C,D,A)+X[4] +6ED9EBA1)<<15

5. A=(A+h(B,C,D)+X[5] +6ED9EBA1)<<3

6. D=(D+h(A,B,C)+X[6] +6ED9EBA1)<<9

7. C=(C+h(D,A,B)+X[7] +6ED9EBA1)<<11

8. B=(B+h(C,D,A)+X[8] +6ED9EBA1)<<15

9. A=(A+h(B,C,D)+X[9] +6ED9EBA1)<<3

10. D=(D+h(A,B,C)+X[10] +6ED9EBA1)<<9

11. C=(C+h(D,A,B)+X[11] +6ED9EBA1)<<11

12. B=(B+h(C,D,A)+X[12] +6ED9EBA1)<<15

13. A=(A+h(B,C,D)+X[13] +6ED9EBA1)<<3

14. D=(D+h(A,B,C)+X[14] +6ED9EBA1)<<9

15. C=(C+h(D,A,B)+X[15] +6ED9EBA1)<<11

16. B=(B+h(C,D,A)+X[16] +6ED9EBA1)<<15

Chúng ta thấy MD4 chủ yếu thực hiện nhờ các phép toán logic và một phép công theo modulo 232 nên thuật toán chạy rất nhanh, thích ứng với việc sử lý bản tin có độ lớn. Tuy nhiên thuật toán MD4 tồn tại một số hạn chế. Cụ thể là có thể tìm thấy va chạm nếu sử dụng 2 vòng. Vì điểm yếu này mà MD5 ra đời thay thế cho MD4.

1.2.5 Hàmbăm MD5

Thuật toán MD5 ra đời năm 1992. Nó có cấu trúc thuật toán giống với MD4. Chỉ có khác là MD5 sử dụng 4 vòng, trong khi MD4 sử dụng 3 vòng, và có một số thay đổi nữa. Cụ thể như sau:

Hàm g thiết kế trở lại để mất tính đối xứng:

Sử dụng thêm một hàm i:

Từ 4 hàm f,g,h và i ta đi định nghĩa 4 hàm FF,GG,HH và II như sau:

FF(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<<s;

GG(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<<s;

HH(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<<s;

II(a,b,c,d,Mi,s,ti):a=b+((a+F(b,c,d)+Mi+ti)<<<s;

Chúng ta định nghĩa các hệ số dịch trái:

S11= 7; S12= 12; S13= 17; S14= 22S21= 5; S22= 9; S23= 14; S24= 20S31= 4; S32= 11; S33= 16; S34= 23S41= 6; S42= 10; S43= 15; S44= 214 vòng tương ứng được miêu tả như sau:

Round

1. FF (a, b, c, d, X[1], S11, 0xd76aa478); 2. FF (d, a, b, c, X[2], S12, 0xe8c7b756); 3. FF (c, d, a, b, X[3], S13, 0x242070db); 4. FF (b, c, d, a, X[4], S14, 0xc1bdceee); 5. FF (a, b, c, d, X[5], S11, 0xf57c0faf); 6. FF (d, a, b, c, X[6], S12, 0x4787c62a); 7. FF (c, d, a, b, X[7], S13, 0xa8304613); 8. FF (b, c, d, a, X[8], S14, 0xfd469501); 9. FF (a, b, c, d, X[9], S11, 0x698098d8);10. FF (d, a, b, c, X[10],S12, 0x8b44f7af);11. FF (c, d, a, b, X[11],S13, 0xffff5bb1); 12. FF (b, c, d, a, X[12],S14, 0x895cd7be);13. FF (a, b, c, d, X[13],S11, 0x6b901122);14. FF (d, a, b, c, X[14],S12, 0xfd987193); 15. FF (c, d, a, b, X[15],S13, 0xa679438e); 16. FF (b, c, d, a, X[16],S14, 0x49b40821); Round 21. GG (a, b, c, d, X[2], S21, 0xf61e2562); 2. GG (d, a, b, c, X[7], S22, 0xc040b340);3. GG (c, d, a, b, X[12],S23, 0x265e5a51);4. GG (b, c, d, a, X[1], S24, 0xe9b6c7aa); 5. GG (a, b, c, d, X[6], S21, 0xd62f105d); 6. GG (d, a, b, c, X[11],S22, 0x2441453); 7. GG (c, d, a, b, X[16],S23, 0xd8a1e681);8. GG (b, c, d, a, X[5], S24, 0xe7d3fbc8); 9. GG (a, b, c, d, X[10],S21, 0x21e1cde6);10. GG (d, a, b, c, X[15],S22, 0xc33707d6);11. GG (c, d, a, b, X[4], S23, 0xf4d50d87); 12. GG (b, c, d, a, X[9], S24, 0x455a14ed); 13. GG (a, b, c, d, X[14],S21, 0xa9e3e905);14. GG (d, a, b, c, X[3], S22, 0xfcefa3f8); 15. GG (c, d, a, b, X[8], S23, 0x676f02d9);16. GG (b, c, d, a, X[13],S24, 0x8d2a4c8a); Round 3 1. HH (a, b, c, d, X[6], S31, 0xfffa3942); 2. HH (d, a, b, c, X[9], S32, 0x8771f681); 3. HH (c, d, a, b, X[12],S33, 0x6d9d6122);4. HH (b, c, d, a, X[15],S34, 0xfde5380c);5. HH (a, b, c, d, X[2], S31, 0xa4beea44);6. HH (d, a, b, c, X[5], S32, 0x4bdecfa9); 7. HH (c, d, a, b, X[8], S33, 0xf6bb4b60); 8. HH (b, c, d, a, X[11],S34, 0xbebfbc70); 9. HH (a, b, c, d, X[14],S31, 0x289b7ec6);10. HH (d, a, b, c, X[1], S32, 0xeaa127fa);11. HH (c, d, a, b, X[4], S33, 0xd4ef3085);12. HH (b, c, d, a, X[7], S34, 0x4881d05); 13. HH (a, b, c, d, X[10],S31, 0xd9d4d039);14. HH (d, a, b, c, X[13],S32, 0xe6db99e5); 15. HH (c, d, a, b, X[16],S33, 0x1fa27cf8); 16. HH (b, c, d, a, X[3], S34, 0xc4ac5665); Round 4 1. II (a, b, c, d, X[1], S41, 0xf4292244); 2. II (d, a, b, c, X[8], S42, 0x432aff97); 3. II (c, d, a, b, X[15],S43, 0xab9423a7); 4. II (b, c, d, a, X[6], S44, 0xfc93a039); 5. II (a, b, c, d, X[13],S41, 0x655b59c3); 6. II (d, a, b, c, X[4], S42, 0x8f0ccc92); 7. II (c, d, a, b, X[11],S43, 0xffeff47d); 8. II (b, c, d, a, X[2], S44, 0x85845dd1); 9. II (a, b, c, d, X[9], S41, 0x6fa87e4f); 10. II (d, a, b, c, X[16],S42, 0xfe2ce6e0); 11. II (c, d, a, b, X[7], S43, 0xa3014314); 12. II (b, c, d, a, X[14],S44, 0x4e0811a1); 13. II (a, b, c, d, X[5], S41, 0xf7537e82); 14. II (d, a, b, c, X[12],S42, 0xbd3af235); 15. II (c, d, a, b, X[3], S43, 0x2ad7d2bb); 16. II (b, c, d, a, X[10],S44, 0xeb86d391); 1.2.6 Hàm băm SHS

Thuật toán SHS (Secure Hash Standard) do NIST và NSA xây dựng và công bố trên Federal Register ngày 31/01/1992 và trở thành chuẩn từ ngày 13/05/1993.

Thuật toán được miêu tả như sau:

1. Mở rộng bản tin: Thêm các bít vào bản tin để bản tin có chiều dài là bội của 512. Quá trình thêm diễn ra như sau. Thêm bít 1 vào cuối bản tin, sau đó thêm vào một số bít 0 để nhận bản tin có chiều dài là đồng dư với 448 modulo 512, và cuối cùng thêm vào 64 bít, 64bít này biểu diễn chiều dài của bản tin ban đầu. Bản tin được thêm vào bao gồm các khối M1, M2, ... , Mn, chiều dài mỗi khối là 32 bít.

2. Khởi tạo các biến:

A=67452301 B=EFCDAB89 C=98BADCFE D=10325476 E=C3D2E1F0

3. i=1

4. for j=1 to 16 do X[j]=M[16i+j]

6. AA=A;BB=B;CC=C;DD=D;EE=E;

7. for j=1 to 80 do temp=(AA<<<5)+F(t,BB,CC,DD)+EE+K[t]

EE=DD

DD=CC

CC=BB<<<30

BB=AA

AA=temp

8. A=A+AA;B=B+BB;C=C+CC;D=D+DD;E=E+EE;

9. Nếu i < n/16 thì i=i+1 và quay về bước 4.

10. Bản tóm lượt của bản tin có chiều dài 160 bít là nối của 5 từ 32 bít:A|B|C|D|E

Với F(t,X,Y,Z) được cho như sau:

Và K[t] được xác định như sau:

1.2.7 Hàm băm SHA

Thuật toán hàm băm an toàn SHA (Secure Hash Algorithm) được chấm nhận trong số các chuẩn của Mỹ năm 1992 và nó được ứng dụng cùng với thuật toán chuẩn chữ ký số DSS. Khi đầu vào là một bản tin M có chiều dài bất kỳ, đầu ra là là 160 bít rút gọn.

Chúng ta xem làm việc của thuật toán chi tiết hơn.

Trong SHA-1 sử dụng hàm f(t, B, C, D), với 0£t£79; B, C và D –là các từ 32 bít.

f(t, B, C, D) = (B Ù C) Ú ((ØB) Ù D) khi 0£t£19

f(t, B, C, D) = B Å C Å D khi 20£t£39

f(t, B, C, D) = (B Ù C) Ú (B Ù D) Ú (C Ù D) khi 40£t£59

f(t, B, C, D) = B Å C Å D khi 60£t£79

và sử dụng các hằng số:

Kt = 5A827999 khi 0£t£19

Kt = 6ED9EBA1 khi 20£t£39

Kt = 8F1BBCDC khi 40£t£59

Kt = CA62C1D6 khi 40£t£79

Thuật toán Hash SHA-1 được miểu tả bởi các bước sau:

Đầu vào: bản tin có chiều dài <264 bít.

1) Mở rộng bản tin: thêm vào bít để chiều dài bản tin là bội của 512. Quá trình thêm diễn ra như sau. Thêm bít 1 vào cuối bản tin, sau đó thêm vào một số bít 0 để nhận bản tin có chiều dài là đồng dư với 448 modulo 512, và cuối cùng thêm vào 64 bít, 64bít này biểu diễn chiều dài của bản tin ban đầu. Bản tin được thêm vào bao gồm các khối M1, M2, ... , Mn, chiều dài mỗi khối là 512 bít.

2) Khởi tạo các biến

H0 := 67452301, H1 := EFCDAB89, H2 := 98BADCFE,

H3 := 10325476, H4 := C3D2E1F0

3) i := 1

4) Chia khối Mi thành 16 từ 32 bít w0, w1, ..., w15.

5) Đối với các t: 16£t£79 wt := (wt-3 Å wt-8 Å wt-14 Å wt-16)<<<1, ở đây lệnh "<<<x" là lệnh dịch trái x bít.

6) A := H0, B := H1, C := H2, D := H3, E := H4.

7) Đối với tất cả các t từ 0 đến 79

TEMP := (A <<< 5 + f(t, B, C, D) + E + wt + Kt) mod 232;

E := D; D := C; C := B <<< 30; B := A; A := TEMP.

8) H0 := H0 + A, H1 := H1+B, H2 := H2 + C, H3 := H3 + D, H4 := H4 + E,

Tất cả các lệnh cộng theo modulo 232

9) Nếu i<n, thì i := i+1 và chuyển sang bước 4.

Đầu ra: bản băm rút gọn có chiều dài 160 bít là liên kết của các từ 32 bít H0 | H1 | H2 | H3 | H4.

Chú ý: Ngoài SHA-1 chúng ta vừa xem, còn có những thuật toán có chiều dài khác nhau, nhưng về cơ bản thuật toán là giống SHA-1, nên ở đây không được miêu tả cụ thể mà chỉ nêu ra bảng tóm tắt so sánh của các biến dạng khác nhau của SHA.

Algorithm

Output size (bits)

Internal state size (bits)

Block size (bits)

Max message size (bits)

Word size (bits)

Rounds

Operations

SHA-0

160

160

512

264 − 1

32

80

+,and,or,xor,rotfl

Yes

SHA-1

160

160

512

264 − 1

32

80

+,and,or,xor,rotfl

263 attack

SHA-256/224

256/224

256

512

264 − 1

32

64

+,and,or,xor,shr,rotfr

None

SHA-512/384

512/384

512

1024

2128 − 1

64

80

+,and,or,xor,shr,rotfr

None

Hình 3.2 – Bảng tóm tắt so sánh các biến dạng khác nhau cảu SHA

3.1.2.8 Xây dựng hàm băm trên cơ sỡ mậtmã đối xứng

ở đây H0 là giá trị ban đầu đặc biệt. Giá trị băm của hàm H=Hn.

Sơ đồ cấu trúc đơn giản nhất xây dựng hàm Hash mang tên Rabin được miêu tả như hình 11.1.

Hình 11.1. Sơ đồ tạo hàm Hash Rabin

Sơ đồ hàm Hash Rabin có thể viết dưới dạng công thức:

Chúng ta có thể liệt kê một số sơ đồ khác, phục vụ cho việc xây dựng hàm Hash được miêu tả trong bảng sau:

Số thứ tự

Công thức

1

2

3

4

5

6

7

8

9

10

11

12

Dưới đây là biểu diến một số sơ đồ tương ứng với bảng trên ...

Hình 11.2.Sơ đồ biểu diễn hàm Hash tương ứng với phương án 1 (a), 5(b) và 10 (c) ở bảng...

Trên cơ sở ba tham số Hi-1, Mi-1 và Mi có thể xây dựng rất nhiều phương án xây dựng hàm Hash khác với việc sử dụng một thanh ghi có kích thước lớn.

Hình 11.3. Sơ đồ xây dựng hàm Hash trên cơ sở biến đổi khối một chiều

Hàm một chiều có thể xây dựng trên cơ sở hàm mật mã khối bền vững E, ví dụ có thể xây dựng F theo công thức sau:

ở đây K là một số khóa cố định đã biết. Đối với một thuật toán EK vững chắc thì hàm đã cho là hàm một chiều, bởi vì chúng ta không biết véc tơ được hình thành bởi đầu ra của EK.

1.3 Mật mã học và mật mã khóa công khai1.3.1 Một số thuật ngữ và khái niệm

Trong mật mã học, một ngành toán học ứng dụng cho công nghệ thông tin, mã hóa là phương pháp để biến thông tin (phim ảnh, văn bản, hình ảnh...) từ định dạng bình thường sang dạng thông tin không thể hiểu được nếu không có phương tiện giải mã.Văn bản là một thông báo gốc cần chuyển có định dạng là văn bản, âm thanh, hình ảnh, chữ số - Văn bản gốc trước khi mã hóa được ký hiệu là PT (plain text)

- Văn bản mã thường được ký hiệu là CT (ciphertext)

- Hệ mã là một phương pháp mã hóa văn bản.

- Thám mã là nghệ thuật phá các hệ mã

- Giải mã là phương pháp để đưa từ dạng thông tin đã được mã hóa về dạng thong tin ban đầu, quá trình ngược của mã hóa.

- Khóa là bí quyết lập mã và giải mã. Nếu như việc mã hóa được xem như một hàm y = f(x,k), trong đó x là văn bản đầu vào, còn k là một tham số điều khiển, f là phương pháp mã hóa. Trước đây bí quyết thường là cả f và k. Do yêu cầu hiện nay công nghệ mã hóa đã phải thay đổi quan điểm này. Phương pháp f thường không do một người nắm giữ nên không thể giữ bí mật nên phải coi nó là công khai. Tham số điều khiển k, có tác dụng làm thay đổi kết quả và được coi là chìa khóa mã. Thông thường nó là một xâu bit mà người sử dụng có thể giữ riêng cho mình.

Nguyên tắc chung của mã hóa là việc giải mã phải rất dễ dàng với người trong hệ thống sử dụng, và ngược lại rất khó giải mã (thậm chí không thực hiện được) đối với người ngoài.

1.3.2 Các hệ mãhóa

Hệ mã bí mật (secret key cryptosystem) hay hệ mã đối xứng là hệ mã hóa mà trong đó việc lập mã và giải mã cùng sử dụng chung một khóa.

Hệ mã công khai (public key cryptosystem) hay mã hóa phi đối xứng là hệ mã mà trong đó việc lập mã và giải mã sử dụng 2 chìa khóa riêng biệt, từ chìa khóa này không thể tìm ra chìa khóa kia và ngược lại. Khóa được dùng để mã hóa gọi là khóa công khai, còn khóa giành cho việc giải mã , luôn được giữ bí mật gọi là khóa riêng

1.3.3 Ứng dụng của mã hóa

Mã hóa có vai trò rất quan trọng, đặc biệt là trong giao dịch điện tử. Nó giúp đảm bảo bí mật, toàn vẹn của thông tin, khi thông tin đó được truyền trên mạng.Mã hóa cũng là nền tảng của kĩ thuật chữ ký điện tử, hệ thống PKI...

1.3.4 Hệ mã hóa bí mật (mã hóa khóa đối xứng)vànhững hạn chế :

Sử dụng thuật toán mã hóa đối xứng - giải thuật giải mã ngược với giải thuật tạo bản mã, cả 2 giải thuật dùng chung một khóa (Secret key). Khóa được dùng chung giữa bên gửi và bên nhận nên tồn tại một số điểm yếu :

- Vấn đề phân phối khóa khó bảo đảm chia sẻ mà không làm tiết lộ, hoặc trung tâm phân phối khóa có thể bị tấn công.

- Yêu cầu để tạo chữ ký số là phải bí mật chỉ người dùng duy nhất có khóa để tạo chữ ký nên mã hóa đối xứng không được áp dụng cho lĩnh vực chứ ký số.

1.3.5 Mật mã khóa công khai

Khắc phục điểm yếu của mã hóa khóa đối xứng với những đặc điểm , giải thuật khóa

công khai sử dụng 2 khóa khác nhau :

- Một khóa công khai

- Ai cũng có thể biết

- Dùng để mã hóa thông báo và thẩm tra chữ ký

- Một khóa riêng

- Chỉ nơi giữ được biết

- Dùng để giải mã thông báo và ký chữ ký

- Có tính chất bất đối xứng

- Bên mã hóa không thể giải mã thông báo (nếu dùng để mã hóa thông báo)

- Bên thẩm tra không thể tạo chữ ký ( nếu dùng để ký )

Hình 3.3 – Mô hình hoạt động của mật mã khóa công khai

2 Xây dưng lược đồ chữ ký dựa trên bài toánphân tích số2.1 Bài toán phân tích một sốnguyên lớn ra các thừa số nguyên tố

Có thể phát biểu bài toán này theo một cách đơn giản hơn như sau:

- Cho p, q là 2 số nguyên tố lớn và mạnh;

- Từ n rất khó tìm được p và q.

Trong hệ mật RSA [1], bài toán phân tích số được sử dụng làm cơ sở để hình thành cặp khóa công khai (e)/bí mật (d) cho mỗi thực thể k‎ý. Với việc giữ bí mật các tham số p, q thì khả năng tính được khóa mật (d) từ khóa công khai (e) và modulo n là rất khó thực hiện, nếu p, q được chọn đủ lớn và mạnh [2,3] .

Hiện tại, bài toán trên vẫn được coi là bài toán khó [4,5] do chưa có giải thuật thời gian đa thức cho nó và hệ mật RSA là một chứng minh thực tế cho tính khó giải của bài toán này.

3.2.2 Phương pháp xây dựnglược đồ chữ ký số dựa trên bài toán phân tích số

Lược đồ mới đề xuất ở đây được thiết kế theo dạng lược đồ sinh chữ ký 2 thành phần tương tự như DSA trong chuẩn chữ k‎ý số của Mỹ (DSS) hay GOST R34.10-94 của Liên bang Nga.

Giả sử thành phần thứ nhất của chữ k‎ý lên bản tin M là S và S được tính từ một giá trị u theo công thức:

Giả sử thành phần thứ hai của chữ k‎ý là Z và Z được tính từ một giá trị v theo công thức:

Giả thiết rằng:

và phương trình kiểm tra của lược đồ có dạng:

Vấn đề đặt ra ở đây là cần tìm {u,v} sao cho {S,Z} thỏa mãn (3) và (4).

Từ (1), (2) và (3) ta có:

Từ (1), (2) và (4) ta có:

Từ (5) và (7) suy ra:

hay:

dẫn đến:

và:

Từ (8) ta có công thức tính thành phần thứ nhất của chữ ký:

Từ (9) cho công thức tính thành phần thứ hai của chữ ký:

Cũng có thể chọn v làm thành phần thứ hai của chữ ký, khi đó cặp (v,S) sẽ là chữ ký lên bản tin M.

3.2.3 Một lược đồ chữ k‎ý số được đề xuất xây dựng dựa trên bài toán khai căn và phân tích số3.2.3.1 Thuật toán hình thành tham số

Thuật toán 1.1:

Input: p, q – các số nguyên tố lớn.

Output: n, t, H(.),ø(n).

[5]. return {n, t, H(.),ø(n)};

Chú ‎ý:

i) n, t, H(.): các tham số công khai.

ii) ø(n): tham số bí mật.

Nhận xét:

Ở lược đồ mới đề xuất không sử dụng cặp khóa bí mật/công khai như ở các lược đồ chữ k‎ý RSA, DSA,...

3.2.3.2 Thuật toán hình thành chữ k‎ý

Thuật toán 1.2:

Input: n, t, ø(n), M – Bản tin được k‎ý bởi đối tượng U.

Output: (v,s).

[9]. return (v,s);

Chú ‎ý:

U: đối tượng k‎‎ý và là chủ thể của các tham số {n,t,ø(n)}.

Nhận xét:

i) Thuật toán không sử dụng khóa bí mật trong việc hình thành chữ k‎ý như ở các lược đồ chữ k‎ý RSA, DSA,...

ii) Tham số ø(n) được sử dụng như khóa bí mật để hình thành chữ k‎ý (v,s) của đối tượng U lên bản tin M.

3.2.3.3Thuậttoán kiểm tra chữ k‎ý

‎‎ Thuật toán 1.3:

Input: n, t, M – Bản tin cần thẩm tra, (v,s) – Chữ k‎ý của U lên M.

Chú ‎ý:

i) U: đối tượng là chủ thể của cặp tham số {n,t}.

ii) (v,s) = true: chữ k‎ý hợp lệ, M được khẳng định về nguồn gốc và tính toàn vẹn.

iii) (v,s) = false: chữ k‎ý không hợp lệ, M không được công nhận về nguồn gốc và tính toàn vẹn.

Nhận xét:

Tham số {n,t} được sử dụng như khóa công khai của đối tượng U để kiểm tra tính hợp lệ của chữ k‎‎ý (v,s).

3.2.4 Tính đúng đắn củalược đồ mới đề xuất

Tính đúng đắn của lược đồ mới đề xuất được chứng minh như sau:

Ta có:

Do đó:

Mặt khác:

Đây là điều cần chứng minh.