Giải ngố Cryptography – Phần 5: Elliptic Curve Cryptography (ECC) và ứng dụng trong Blockchain

Tiếp theo nội dung Phần 4: Rivest–Shamir–Adleman (RSA), Diffie-Hellman (DH) và ứng dụng trong cấu hình OpenVPN, kỳ này tôi sẽ chiến đấu với Elliptic Curve Cryptography (ECC). Ngoài việc tóm lược về quá trình tạo key và mã hóa với ECC, tôi cũng sẽ bàn kỹ hơn việc so sánh với RSA cũng như ứng dụng của ECC trong một công nghệ rất hot hiện nay là Blockchain.

#1 Cơ chế hoạt động của ECC

#1.1 Quá trình tạo key của ECC

Trước hết, nếu bạn đã quên thì Elliptic Curve (EC) là dạng đường cong có thể thể hiện qua phương trình:

y² = x³ + ax + b

Và để tiện theo dõi, tôi xin nhắc lại quá trình tạo key với ECC túm gọn cho dễ hiểu như sau:

– Chọn một điểm ngẫu nhiên A trên EC

– Vẽ tiếp tuyến với EC qua A

– Tiếp tuyến này cắt EC tại B (cái này có thể xem là “dot function” lần 0: A “dot” A à B)

– Thực hiện “dot function” lần 1: vẽ đường nối AB cắt EC tại C’, lấy C là điểm đối xứng của C’ qua trục Ox (do tính chất của EC nên C sẽ vẫn nằm trên EC)

– Thực hiện “dot function” lần 2: vẽ đường nối AC cắt EC tại D’, lấy D là điểm đối xứng của D’ qua trục Ox (tương tự, D sẽ vẫn nằm trên EC)

…

– Thực hiện “dot function” lần n: thu được điểm Zn nào đó

– Lúc này A, Zn tương ứng với public key và số lần n tương ứng với private key (đây là mấu chốt của vấn đề: bạn khó có thể biết được n là bao nhiêu khi kể cả khi biết được A và Zn)

• Có thể bạn muốn xem: Giải ngố Blockchain – Phần 3: Nguyên lý cơ bản của Elliptic Curve Cryptography và vấn đề mã hóa.

#1.2 Mã hóa thông tin với ECC

Giống với Diffie-Hellman Key Exchange Protocol (DH) , ECC sẽ chỉ có thể cung cấp một thứ giống như shared secret để sử dụng cho quá trình tạo khóa tiếp theo chứ shared secret này không đóng vai trò như một encryption key.

• Có thể bạn muốn xem: Giải ngố Cryptography – Phần 3: Đảm bảo Confidentiality với Encryption và Diffie-Hellman Key Exchange Protocol

Do vậy, để mã hóa thông tin với ECC, quá trình thực hiện có thể diễn giải tóm lược với 2 nhân vật huyền thoại Alice và Bob như sau:

– Alice và Bob thống nhất một điểm khởi tạo G trên EC, Alice chọn số nguyên ngẫu nhiên a làm private key và tính public key A=a*G (tương ứng G dot a lần)

– Trong một diễn biến khác, Bob cũng sẽ chọn số nguyên b làm private key và tính public key B=b*G

– Kế tiếp, Alice và Bob sẽ xác định shared secret là:

a*B = a*(b*G) = (a*b)*G = (b*a)*G = b*(a*G) = b*A

– Dựa vào cái shared secret này, Alice và Bob có thể tạo Symmetric Encryption Key phục vụ việc mã hóa trong các phiên làm việc tiếp theo

#2 ECC và RSA

Bạn còn nhớ tôi đã cập 2 ngôi sao sáng trong làng Assymetric Encryption là RSA và ECC. Đây là lúc thích hợp để soi kỹ hơn về 2 đại ca này.

Thông số	RSA	ECC
Ephemeral Keys	Việc tạo Ephemeral Keys rất khó	Việc tạo Ephemeral Keys rất dễ
Security	Dựa trên độ khó của bài toán phân tích thừa số đối với tích của 2 số nguyên tố lớn	Dựa trên trên độ khó của bài toán Elliptic Curve Discrete Logarithm
Strength	RSA 3072 bit key tương đương ECC 256 bit key
Authentication	Có thể dùng cho Digital Signature để xác thực danh tính các bên	Shared Secret không thể dùng mã hóa trực tiếp nên cần kết hợp thêm với “đối tác khác” (ví dụ như Digital Signature Algorithm – DSA) để phục vụ cho Digital Signature
Attacks	Low exponent, common modulus, cycle attack	Nếu dùng đơn lẻ có thể gặp tình huống như DH (Man in the Middle (MiTM) attack )

Như vậy có thể thấy ECC có nhiều điểm tương đồng với DH:

Ưu điểm nổi bật của ECC so với RSA:

– Key size nhỏ hơn

– Tạo key nhanh

Khuyết điểm của ECC so với RSA:

– Chọn dạng EC và các thông số triển khai thực tế khó hơn RSA (chọn đại thông số sẽ bốc sh*t!)

– Chưa được kiểm tra điểm yếu toàn diện như như RSA (cái này thì phải chịu thôi, tính tuổi thì ECC phải gọi RSA bằng cụ)

– Vấn đề tương tự như DH nếu không có “đối tác” hỗ trợ

#3 Elliptic Curve Digital Signature Algorithm (ECDSA) và ứng dụng trong Blockchain

Như tôi giới thiệu trong Mục 2, ông ECC thực tế hay giao lưu phối hợp với các đối tác khác để khắc phục các vấn đề (tương tự như ông DH feat RSA trong OpenVPN). Và đối tác phổ biến của ECC là Digital Signature Algorithm (DSA).

DSA là thuật toán để tạo chữ ký số thông qua việc sử dụng public và private key được sử dụng trong Digital Signature Standard – DSS của National Institute of Standards and Technology – NIST. Ông DSA này hiện là hàng chính hãng USA của Federal Information Processing Standards – FIPS cho vấn đề Digital Signature.

Lưu ý:

– RSA hoàn toàn đáp ứng được mục tiêu triển cái Digital Signature chứ không phải chỉ có DSA mới làm được

– Bạn có thể xem tóm lược về Digital Signature với bảng sau và thông tin chi tiết hơn như tôi trình bày trong Giải ngố Pretty Good Privacy (PGP) – Phần 3: Sử dụng PGP trong xác thực và chữ ký số như thế nào

Stt	Public key	Private key	Mục đích
1	Mã hóa thông tin	Giải mã thông tin	Mã hóa
2	Giải mã thông tin	Mã hóa thông tin	Digital Signature

Thực tế khi đọc về nguyên lý của DSA tôi thấy nhiều nét khá tương đồng với RSA. Tuy nhiên, để tránh hiện tượng “chuyện này dẫn tới chuyện kia” và cuối cùng “quên cả lối về”, tôi xin phép ngắt cái mạch phát triển của câu chuyện về DSA ở đây (và sẽ quay lại vào một ngày xấu trời nào đó).

Quay trở lại vấn đề chính với ông ECDSA, đại ca này có thể xem là biến thể của DSA sử dụng key sinh ra từ ECC chứ không dùng số nguyên tố như RSA. Chính vì lẽ đó ECDSA hiển nhiên có được lợi thế key size nhỏ và tốc độ tạo key nhanh của ECC.

Nếu từng thử tạo cặp public/private key với RSA, bạn có thể bật lại “Tui tạo key trên laptop thấy vẫn chạy nhanh ầm ầm chứ có chậm mấy đâu mà cứ nói quá!”. Xin thưa, con lap bạn đang chạy có thể có “cấu hình ghẻ” khi so với các dòng laptop khác nhưng khi so với các thể loại “smart devices” như điện thoại thì thật sự nó vẫn có thể xem là thể loại trâu chó đấy. Ngoài ra, bạn cũng cần lưu ý, quá trình sử dụng thực tế cần tính toán tạo key rất nhiều lần chứ không phải bạn tính một lần rồi ngồi xỉa răng rung đùi đâu.

Chính vì lẽ đó, trong nội dung Giải ngố Blockchain – Phần 2: Hiểu nhanh cơ chế hoạt động của Blockchain với Bitcoin trong 5 phút, tôi đã từng đề cập “…Việc tạo cặp Public Key và Private Key có thể sử dụng một số thuật toán như Rivest–Shamir–Adleman (RSA) hay Elliptic Curve Digital Signature Algorithm (ECDSA)…”. Và như vậy, ông ECDSA với lợi thế key size và tốc độ hiện đang chiếm thế so với RSA trong chiến trường Blockchain (ví dụ như Bitcoin) với các smart phone app.

Đến đây tôi xin kết thúc nội dung kỳ này cũng như thông tin về Asymmetric Encryption. Nếu không có gì bất ngờ, kỳ tới tôi sẽ chuyển sang các nội dung liên quan đến Symmetric Encryption.