Đã đăng vào thg 8 5, 2:00 SA 8 phút đọc

152

[Cryptography p7] Chữ ký điện tử ECDSA

Bài viết được lấy từ https://truongphuoc.wordpress.com/2023/03/28/blockchain-20-chu-ky-dien-tu-digital-signature/

Xin chào các bạn, trong hai bài trước mình đã trình bày về hai thuật toán trong hệ mật bất đối xứng là RSA và Elliptic curve cryptography. Đó là hai thuật toán được dùng phổ biến hiện nay trong bảo mật thông tin. Trong bài viết này mình sẽ trình bày về chữ ký số.

Chữ ký điện tử

Ngày xửa ngày xưa, khi xem phim Trung Quốc, nhất là mấy phim xử án như Bao Thanh Thiên, chúng ta hay thấy sau khi thư ký đã ghi lời khai hay lời nhận tội của phạm nhân, phạm nhân đã đồng ý vào lời khai đó thì phải xác nhận bằng cách điểm dấu vân tay. Dấu vân tay này để làm chứng nếu như sau này phạm nhân có lật lọng.

Trong thời đại ngày nay, đối với các văn bản như hợp đồng, hóa đơn hay các giao dịch ngân hàng, chúng ta cũng dùng một cách để xác nhận mình đồng ý, hay xác nhận mình là người giao dịch bằng các ký tên vào hóa đơn hay hợp đồng đó.

Thế làm thế nào khi các giao dịch, hợp đồng là ở dưới dạng số hóa, hay nói cách khác chúng ta sử dụng trên môi trường internet, làm cách nào để một người điểm dấu vân tay hay ký vào văn bản số đó để xác nhận rằng tôi là người đồng ý?

Đồng thời sau khi ký thì người đã ký không thể chối bỏ trách nhiệm, rằng mình không phải là người ký?

Và người ta đã nghĩ ra cách để làm điều đó, một trong những cách đó là chữ ký điện tử hay còn gọi là chữ ký số. Chữ ký điện tử đã được công nhận trong luật của rất nhiều quốc giá trên thế giới như Việt Nam, Mỹ, EU, Trung Quốc,...

Theo bộ luật GPEA(Mỹ), điều 1710 định nghĩa: Chữ ký điện tử (eletronic signature) là cách ký các văn bản điện tử đảm bảo:

Nhận dạng và xác thực cá nhân đã tạo ra văn bản.
Chỉ ra sự chập nhận của người ký đối với nội dung trong văn bản.

Hay bộ luật UETA (Mỹ), điều 2 định nghĩa: Chữ ký điện tử là các tín hiệu âm thanh, ký hiệu, quá trình gắn (vật lý hoặc logic) với hợp đồng hay văn bản và được thực hiện bời người muốn ký vào hợp đồng hay văn bản đó.

Tóm lại chữ ký điện tử là một cách nào đó để xác định người ký vào một tập tin điện tử đã thực sự chấp nhận nội dung trong tập tin đó.

Có nhiều cách để tạo chữ ký điện tử, hôm nay mình sẽ trình bày về thuật toán ECDSA, một thuật toán ký số dựa trên đường cong Elliptic mới học ở bài trước. Nếu bạn nào chưa đọc qua về bài trước thì nên đọc trước để hiểu rõ hơn về thuật toán này nhé.

ECDSA (Elliptic Curve Digital Signature Algorithm)

ECDSA là một thuật toán ký số, được phát triển dựa trên hệ mật đường cong Elliptic. ECDSA được thực hiện như sau:

Cho đường cong $E_p(a, b)$ , điểm cơ sở G nằm trên đường cong. Số n là một số nguyên dương thỏa mãn điều kiện nG = O với O là điểm vô cực.

Ta có một thông điệp m, để ký thông điệp này ta làm như sau: Chọn một số nguyên dương bất kỳ là d với d < n để làm khóa bí mật, khóa công khai ứng với d là Q = dG. Sau đây là các bước ký vào thông điệp m với khóa bí mật d:

B1: Chọn số ngẫu nhiên $k ∈ [1, n-1]$

B2: Tính điểm $R = kP = (x_1, x_2)$

B3: Tính $r = x_1 (mod\; n)$

B4: Nếu $r = 0$ quay lại B1

B5: Tính $e = H(m)$ // Với H là một hàm băm bất kỳ.

B6: Tính $s = k^{-1}(e + dr) (mod\; n)$

B7: Nếu $s = 0$ quay lại B1.

B8: Trả về $(r, s)$

Đến đây ta có cặp (r, s) là chữ ký số.

Sơ đồ tạo chữ ký số ECDSA

Với cặp (r,s) ở trên, Public key Q cùng thông điệp m, ta cùng xác thực xem có đúng người có Public key Q đã ký xác thực vào thông điệp m hay không bằng cách sau:

B1: Kiểm tra $r, s$ có phải là những số nguyên $∈ [1, n-1]$ Nếu không trả về kết quả: 'Chữ ký không hợp lệ'.

B2: Tính $e = H(m)$

B3: Tính $w = s^{-1} (mod\; n)$

B4: Tính

$u_1 = ew (mod\; n)\\u_2 = rw (mod\; n)$

B5: Tính $R' = u_1P + u_2Q = (x_1, x_2)$

B6: Nếu $R' = ∞$ trả về kết quả 'Chữ ý không hợp lệ'.

B7: Đặt $r' = x_1$

B8: Nếu $r' = r$ trả về kết quả 'Chữ ký hợp lệ'.

B9: Nếu $r' ≠ r$ trả về kết quả 'Chữ ký không hợp lệ'.

Sơ đồ xác thực ký số ECDSA

Ví dụ thuật toán ECDSA

Ví dụ: Ta có đường cong $E_{23}(1, 1)$ , điểm cơ sở G(3, 10). Với điểm cơ sở này thì n = 28 (do 28G = O). Chọn Private key d = 13, Public key Q = 13G = 13(3, 10) = (1, 7). Thông điệp cần ký là m = 11. Ta cùng thực hiện thuật toán ký:

B1: Chọn $k = 3$

B2: $R = kG = 3(3, 10) = (19, 5) = (x_1, y_1)$

B3: $r = x_1 (mod\; n) = 19 \;mod\; 23 = 19$

B4: $r > 0$ nên đi tiếp.

B5: $e = MD5(m) = MD5(11)$ // Sử dụng hàm băm MD5

$= 6512bd43d9caa6e02c990b0a82652dca$ (cơ số 16)

$= 134349327668835346876933282647662472650$ (cơ số 10).

B6: $s = k^{-1}(e + dr) (mod\; n)$

$= 3^{-1}(e + dr) (mod\; n)$ // ( $3^{-1} (mod\; 28) = 19$ , Nếu không hiểu xem lại bài 17.

$= 19(134349327668835346876933282647662472650 + 13*19) (mod\; 28)$

$= 15 ≠ 0$

B7: Trả về $(r, s) = (19, 15)$

Ta chứng thực thông điệp m = 11 với Public key Q = (1, 7) cùng chữ ký số (r, s) = (19, 15) trên như sau:

B1: Kiểm tra $(r, s) = (19, 15)$ là số nguyên và $∈ [1, n-1] = [1, 27]$ nên tiếp tục.

B2: $e = MD5(m) = MD5(11)$ // Phải cùng hàm băm với thuật toán ký

$= 6512bd43d9caa6e02c990b0a82652dca$ (cơ số 16)

$= 134349327668835346876933282647662472650$ (cơ số 10).

B3: $w = s^{-1} (mod \;n)$

$= 15^{-1} (mod\; 28)$ // Nếu không hiểu xem lại bài 17.

$= 15$ .

B4: $u_1 = ew (mod \;28)$

$= 134349327668835346876933282647662472650 * 15 (mod\; 28)$

$= 22$

$u_2 = rw (mod\; 28)$

$= 19*15 (mod\; 28)$

$= 5$

B5: $R' = u_1G + u_2Q$

$= 22(3, 10) + 5(1, 7)$

$= (19, 5) = (x_1, x_2)$

B6: $R' ≠ ∞$ nên đi tiếp

B7: Đặt $r' = x_1 = 19$

B8: Ta thấy $r' = r = 19$ trả về kết quả 'Chữ ký hợp lệ'.

Phù cuối cùng cũng đã xong.

Nếu bạn đã đọc và hiểu hai bài: các kiến thức toán học và bài hệ mật Elliptic rồi thì hẳn bài này cũng không khó nhằn lắm phải không? Nếu quả thực như thế thì xin chúc mừng, bạn đã thực sự hiểu về một thuật toán ký điện tử rồi. Hiện nay chữ ký điện tử được sử dụng ngày càng rộng rãi, đặc biệt trong các văn bản hành chính, thuế má cũng bắt đầu áp dụng chữ ký điện tử rồi. Chúng ta thấy rằng sau khi đã đi từ nguồn thì mọi thứ đều hiển hiện rõ ràng: Toán học. Đúng thế các thuật toán, kỹ thuật đằng sau đều là các công thức toán học cả mà thôi.

Bài tập về nhà: Các bạn hãy tự tính toán trên giấy để tự tạo và verify chữ ký điện tử của riêng mình nhé.

Bài tập nâng cao: Nếu rảnh, các bạn có thể làm một project "nho nhỏ" là tự tạo một ứng dụng ký điện tử, sử dụng thuật toán ECDSA. Nếu bạn làm được thì CV của các bạn hẳn sẽ thêm phần xịn xò nhé 😁 (thế này thì các công ty ký điện tử có mà khóc thét hết cả thôi 🤣)

Link bài viết gốc https://truongphuoc.wordpress.com/2023/03/28/blockchain-20-chu-ky-dien-tu-digital-signature/