Bài 1: Thuật toán chữ ký số

Blockchain là công nghệ của tương lai, sẽ được ứng dụng trong nhiều lĩnh vực, nhiều mục đích. Nó không phải là Bitcoin, mà Bitcoin chỉ là một con cá trong đại dương Blockchain. Loạt bài tìm hiểu công nghệ Blockchain thông qua cái đang tồn tại _ Bitcoin, hi vọng sẽ cung cấp cho các bạn nào quan tâm có cái nhìn sâu sắc hơn về Blockchain.

Bài viết trích dẫn từ nguồn Toán Học đằng sau Bitcoin và có chỉnh sửa lại đồng thời bổ sung thêm các nguồn tham khảo có giá trị khác, cảm ơn tác giả PHIL TRINH

Lý do mà các Cryptocurrencies gây khó hiểu cho nhiều người là do công nghệ đằng sau nó định nghĩa lại khái niệm về quyền sở hữu.

Để sở hữu một cái gì đó theo nghĩa truyền thống có nghĩa là thứ đó tồn tại và thuộc quyền nắm giữ từ cá nhân hoặc một thực thể đáng tin cậy như một ngân hàng.

Với trường hợp của các Cryptocurrencies thì hoàn toàn khác. Các Cryptocurrencies không được lưu trữ một cách tập trung, vì vậy không có một thực thể nào nắm giữ nó. Chúng tồn tại như những hồ sơ trên sổ cái, gồm nhiều Block nối tiếp nhau gọi là Blockchain (chuỗi khối), nó có thể được phân phối thành các bản sao chia sẻ bởi một mạng lưới các máy tính ngang hàng (P2P) tình nguyện kết nối, mỗi máy tính như vậy được gọi là một Node và cùng lưu trữ một bản sao của Blockchain. “Sở hữu” một Cryptocurrency chỉ có nghĩa là có khả năng chuyển giao kiểm soát nó cho người khác bằng cách tạo ra một hồ sơ chuyển nhượng trong Blockchain. Đó là quyền nắm giữ một cặp mã khóa Public Key và Private Key ECDSA.

Điều đó có nghĩa là gì và tại sao nó giúp các Cryptocurrencies an toàn? Hãy có một cái nhìn sâu hơn.

ECDSA là viết tắt của Elliptic Curve Digital Signature Algorithm _ Thuật toán chữ ký điện tử dựa trên đường cong Elliptic. Đó là việc sử dụng một đường cong Elliptic và một trường hữu hạn để “ký” (sign) vào dữ liệu sao cho người khác có thể xác minh tính xác thực của chữ ký đó trong khi người ký vẫn giữ được độc quyền tạo ra các chữ ký. Với các Cryptocurrencies, các dữ liệu được ký kết là các giao dịch chuyển quyền sở hữu.

ECDSA có thủ tục riêng biệt cho việc ký kết và xác minh. Mỗi thủ tục là một thuật toán bao gồm một vài phép tính số học. Các thuật toán thực hiện việc ký sử dụng các Private Key, và quá trình xác minh sử dụng Public Key. Chúng ta cùng xem vài ví dụ về điều này, nhưng trước tiên, hãy cùng tìm hiểu một chút về đường cong Elliptic và các trường hữu hạn.

1.1. Giới thiệu đường Cong Elliptic
Một đường cong Elliptic được biểu diễn đại số là một phương trình có dạng:

y² = x³ + ax + b

Phiên bản được sử dụng bởi Bitcoin có a = 0 và b = 7, đồ thị của nó trông như sau:

Đường cong Elliptic có những tính chất hữu ích, ví dụ:

+ Một đường thẳng không thẳng đứng, giao nhau tại hai điểm không tiếp tuyến của đường cong sẽ luôn luôn giao nhau tại một điểm thứ ba trên đường cong.

+ Một đường tiếp tuyến với đường cong tại một điểm và không thẳng đứng sẽ cắt nhau đúng một điểm khác trên đường cong.

1.2. Các phép toán trên dường cong Elliptic

1.2.1. Phép cộng điểm P + Q = R

Được định nghĩa là điểm đối xứng qua trục x của điểm giao nhau thứ ba R’ trên một đường thẳng đi qua 2 điểm P và Q. Cách dễ nhất để hiểu được điều này là nhìn vào sơ đồ sau:

1.2.1. Phép nhân đôi điểm R = 2P = P + P

Tại điểm P vẽ đường tiếp tuyến với đường cong Elliptic, tiếp tuyến này cắt đường cong Elliptic tại một điểm R', điểm R đối xứng với R' qua trục x chính là kết quả của phép nhân đôi. Phép nhân một số với một điểm P trên đường cong Elliptic gọi là phép nhân vô hướng. Xem sơ đồ sau:

Hai phép toán này được sử dụng cùng nhau để nhân vô hướng, R = a*P, bằng cách thêm các điểm P với chính nó một số lần. Ví dụ:

R = 7P
R = P + (P + (P + (P + (P + (P + P)))))

Quá trình nhân vô hướng thường được đơn giản hóa bằng cách kết hợp phép cộng điểm và nhân đôi điểm. Ví dụ:

R = 7P
R = P + 6P
R = P + 2 (3P)
R = P + 2 (P + 2P)

Ở đây, 7P đã được chia thành 2 bước nhân đôi điểm và 2 bước cộng điểm

Có thể xem thêm về đường cong Elliptic tại đây

1.2.3. Trường Hữu Hạn

Một trường hữu hạn là một tập hợp số nguyên dương được xác định trước mà trong đó tất cả các tính toán sẽ nằm trong đó. Bất kỳ số nào ngoài phạm vi sẽ “được đưa về” phạm vi này bằng phép chia lấy dư _ modulus (mod). Ví dụ, 9/7 sẽ có phần dư là 2:

9 mod 7 = 2

Ở đây trường hữu hạn của chúng ta là Modulo 7, và tất cả các phép toán mod trong trường này đều đem lại một kết quả nằm trong phạm vi từ 0 tới 6.

Kết hợp lại với nhau

ECDSA sử dụng các đường cong Elliptic trong bối cảnh của một trường hữu hạn, làm thay đổi đáng kể hình dạng của nó nhưng không làm thay đổi các phương trình cơ bản và tính chất đặc biệt. Phương trình tương tự được vẽ ở trên, trong một trường hữu hạn của Modulo 67, sẽ trông như thế này:

Tham khảo công cụ vẽ biểu đồ đường cong Elliptic trong trường hữu hạn tại đây

Bây giờ nó trở thành một tập hợp điểm, trong đó tất cả các giá trị x và y là các số nguyên giữa 0 và 66. Lưu ý rằng “đường cong” vẫn giữ lại đối xứng ngang của nó.

Phép cộng điểm và phép nhân đôi điểm tại đây có hơi khác nhau. Đường vẽ trên đồ thị này sẽ quấn quanh hướng ngang và dọc, và vẫn duy trì độ dốc. Hãy xem hình này để hình dung:

Vì vậy, nếu cộng điểm (2, 22) và (6, 25) thì đồ thị sẽ trông như thế này:

Điểm giao nhau thứ ba là (47, 39) và điểm ánh xạ của nó là (47, 28).

Xem thêm công cụ thực hiện phép cộng trên đường cong Elliptic tại đây

Trở lại với ECDSA và Bitcoin

Một giao thức như Bitcoin chọn một tập các tham số cho các đường cong elliptic và đại diện trường hữu hạn của nó được cố định cho tất cả người dùng của giao thức. Các thông số bao gồm các phương trình được sử dụng, modulo số nguyên tố của trường này, và một điểm cơ sở nằm trên đường cong. Bậc của điểm cơ sở không được lựa chọn độc lập mà là một hàm của các thông số khác, có thể được xem như số lần điểm đó có thể được cộng vào chính nó cho tới khi độ dốc của nó là vô hạn (tức là một đường thẳng đứng). Các điểm cơ sở được lựa chọn sao cho bậc là một số nguyên tố lớn.

Bitcoin sử dụng con số rất lớn đối với điểm cơ sở của nó, modulo nguyên tố, và bậc. Trong thực tế, tất cả các ứng dụng thực tế của ECDSA sử dụng các giá trị rất lớn. An ninh của các thuật toán bảo mật dựa trên các giá trị lớn, và do đó rất khó hoặc đảo ngược hoặc tấn công bằng cách thử lần lượt (brute-force).

Đối với Bitcoin, những thứ dưới đây đã được chọn sẵn:

Phương trình đường cong Elliptic: y² = x³ + 7
Modulo nguyên tố = 2²⁵⁶ – 2³² – 2⁹ – 2⁸ – 2⁷ – 2⁶ – 2⁴ – 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
Điểm cơ sở = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Bậc của điểm = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Ai đã chọn những con số này, và tại sao? Một lượng lớn các nghiên cứu xung quanh việc lựa chọn các thông số thích hợp. Sau tất cả, một số lớn dường như ngẫu nhiên có thể che giấu Private Key khỏi các phương pháp tìm kiếm. Tóm lại, phương thức đặc biệt này có tên là secp256k1 và là một phần của họ đường cong Elliptic trên trường vô hạn, mà được đề xuất để sử dụng trong ngành mật mã.

Private Key và Public Key

Trong ECDSA, Private Key là một số là một số ngẫu nhiên được tạo ra trong đoạn [1; bậc của điểm]. Public Key được tạo ra bằng cách nhân vô hướng Private Key với Điểm cơ sở.

Public Key = Private Key * Điểm cơ sở

Điều này cho thấy số lượng tối đa Private Key là bằng Bậc của điểm.

Trong một trường liên tục chúng ta có thể vẽ đường tiếp tuyến và xác định Publick Key trên đồ thị, nhưng có một số phương trình có thực hiện điều tương tự trong bối cảnh trường hữu hạn. Từ phép cộng điểm P + Q để tìm ra R được xác định như sau:

c = (Q_y – P_y) / (Q_x – P_x)
R_x = c² – P_x – Qx
R_y = c (P_x – R_x) – P_y

Và từ phép nhân đôi điểm p để tìm ra r là như sau:

c = (3P_x² + a) / 2P_y
R_x = c² – 2P_x
R_y = c(P_x – R_x) – P_y

Trong thực tế, việc tính toán khóa public được chia thành một số phép toán phép nhân đôi điểm và phép cộng điểm bắt đầu từ điểm cơ sở.

Hãy thử ví dụ với một số cỡ nhỏ, để có được cái nhìn trực giác về cách các khóa được xây dựng và được sử dụng trong việc ký và xác minh. Các thông số chúng tôi sẽ sử dụng là:

Phương trình: y² = x³ + 7 (tức là a = 0 và b = 7)
Modulo nguyên tố: 67
Điểm cơ bản: (2, 22)
Bậc của điểm: 79
Khóa riêng: 2

Trước tiên, hãy tìm khóa public. Vì chúng ta đã lựa chọn khóa private đơn giản nhất có thể với giá trị = 2, chúng ta chỉ cần thực hiện phép toán phép nhân đôi điểm một lần từ điểm cơ sở. Việc tính toán như sau:

c = (3 * 22 + 0) / (2 * 22) mod 67
c = (3 * 4) / (44) mod 67
c = 12 / 44 mod 67

Ở đây chúng ta phải dừng lại một chút: làm thế nào để chúng ta thực hiện phân chia trong bối cảnh của một trường hữu hạn, nơi mà kết quả phải luôn luôn là một số nguyên? Chúng ta phải nhân với nghịch đảo.

44^-1 = 32

Kết quả phép nhân nghịch đảo trong trường hữu hạn có thể tìm được nhờ thuật toán Euclid mở rộng. Tôi đã viết sẵn code PHP để các bạn có thể kiểm tra:

<?php
/**
 * Thuật toán Euclid tìm ước số chung dương lớn nhất của a và b
 * 
 * @param int $a 
 * @param int $b 
 * 
 * @return int
 */
function gcd($a,$b) { 
	while ($b>0) {
		$r = $a%$b;
		$a = $b;
		$b = $r;
	}
	return $a;
}

/**
 * Tìm nghịch đảo của a trong GL(m), dựa theo thuật toán Euclid mở rộng
 * a, m > 0. Trả về a^-1 mod m, gcd(a, m) phải bằng 1
 * 
 * @param int $m - số nguyên tố
 * @param int $a 
 * 
 * @return int
 */
function ModuloInverse($m,$a) {
	$xa = 1; $xm = 0;
	while ($m!=0) {
		$q = intdiv($a,$m);
		$xr = $xa - $q * $xm;
		$xa = $xm;
		$xm = $xr;
		$r = $a%$m;
		$a = $m;
		$m = $r;
	}
	return $xa;
}

echo 'Nghịch đảo của 44 trong trường Galoa GL(67) là: ' . ModuloInverse(67, 44);
echo '<br/>Nghịch đảo của 550 trong trường Galoa GL(1759) là: ' . ModuloInverse(1759, 550);

?>

Tiếp tục:

c = 12 * 32 mod 67
c = 384 mod 67
c = 49

R_x = (492 – 2 * 2) mod 67
R_x = (2401 – 4) mod 67
R_x = 2397 mod 67
R_x = 52

R_y = (49 * (2 – 52) – 22) mod 67
R_y = (49 * (-50) – 22) mod 67
R_y = (-2450 – 22) mod 67
R_y = -2472 mod 67
R_y = 7

Khóa public của chúng ta do đó tương ứng với điểm (52, 7). Tất cả chỉ để tính cho khóa riêng bằng 2

Phép toán này – đi từ khóa private tính ra khóa public – là một phép toán dễ dàng trên máy tính so với nỗ lực làm việc ngược trở lại để suy ra khóa private từ khóa public, khi về mặt lý thuyết việc thể tính toán này là không khả thi do các thông số rất lớn được sử dụng trong mật mã elliptic.

Vì vậy, từ khóa private để tính ra khóa public được thiết kế là chuyến đi một chiều.

Như với khóa private, khóa public thường được đại diện bởi một chuỗi thập lục phân. Đợi đã! Làm thế nào để chúng ta nhận được từ một điểm trên mặt phẳng, được mô tả bởi hai con số, để ra một số duy nhất? Trong một khóa public không được nén, hai số 256-bit đại diện cho các tọa độ x và y được đính với nhau trong một chuỗi ký tự dài. Chúng ta cũng có thể tận dụng lợi thế của tính đối xứng của các đường cong elliptic để tạo ra một khóa public nén, chỉ bằng cách giữ giá trị x và ghi nhận nửa nào của đường cong mà điểm đó nằm trên. Từ phần thông tin này, chúng ta có thể phục hồi cả hai tọa độ.

Ký kết dữ liệu với Private Key

Bây giờ chúng ta có một cặp khóa Private Key và Public Key, chúng ta hãy ký một số dữ liệu

Các dữ liệu có thể chiều dài bất kỳ. Bước bình thường đầu tiên là băm (hash) dữ liệu để tạo ra một số có chứa cùng một số bit (256) như bậc của điểm của đường cong. Ở đây, để đơn giản, chúng ta sẽ bỏ qua bước băm và chỉ ký dữ liệu thô z. Chúng tôi sẽ gọi G là điểm cơ sở, n là bậc của điểm, và d là Private Key. Công thức ký như sau:

1. Chọn một số nguyên k giữa 1 và n – 1.
2. Tính điểm (x, y) = k * G, sử dụng phép nhân vô hướng.
3. Tìm r = x mod n. Nếu r = 0, quay lại bước 1.
4. Tìm s = (z + r * d) / k mod n. Nếu s = 0, quay lại bước 1.
5. Chữ ký là cặp (r, s)

Xin nhắc lại, ở bước 4, nếu các con số tính toán ra là số thập phân (thực tế phần lớn sẽ là như vậy), tử số sẽ được nhân với nghịch đảo của mẫu số. Trong bước 1, điều quan trọng là k không được lặp lại trong chữ ký khác nhau và nó không thể đoán bởi một bên thứ ba. Đó là, k nên là số ngẫu nhiên hoặc được tạo ra bởi các phương tiện xác định được giữ bí mật khỏi bên thứ ba. Nếu không, bên thứ ba sẽ có thể để tìm ra khóa private từ bước 4, vì s, z, r, k và n đều được biết. Bạn có thể đọc về một trường hợp tấn công kiểu này trong quá khứ ở đây.

Hãy chọn dữ liệu của chúng tôi là số 17, và theo các công thức. Các biến số của chúng tôi:

z = 17 (dữ liệu)
n = 79 (bậc của điểm)
G = (2, 22) (điểm cơ bản)
d = 2 (khóa private)

1. Chọn một số ngẫu nhiên:

k = rand (1, n – 1)
k = rand (1, 79 – 1)
k = 3 (số này thực sự ngẫu nhiên? Không, nhưng nó sẽ đơn giản hóa dụ của chúng ta!)

2. Tính điểm (x, y). Điều này được thực hiện theo cách tương tự như xác định khóa public, nhưng để ngắn gọn chúng ta hãy bỏ qua phép phép cộng điểm và phép nhân đôi điểm số học.

(x, y) = 3G
(x, y) = G + 2G
(x, y) = (2, 22) + (52, 7)
(x, y) = (62, 63)
x = 62
y = 63

3. Tìm r:

r = x mod n
r = 62 mod 79
r = 62

4. Tìm s:

s = (z + r * d) / k mod n
s = (17 + 62 * 2) / 3 mod 79
s = (17 + 124) / 3 mod 79
s = 141/3 mod 79
s = 47 mod 79
s = 47

Lưu ý rằng ở phía trên, chúng ta có thể chia cho 3 vì kết quả là một số nguyên. Trong thực tế chúng ta sẽ sử dụng nghịch đảo của k:

s = (z + r * d) / k mod n
s = (17 + 62 * 2) / 3 mod 79
s = (17 + 124) / 3 mod 79
s = 141/3 mod 79
s = 141 * 3-1 mod 79
s = 141 * 53 mod 79
s = 7473 mod 79
s = 47

5. Chữ ký của chúng ta là cặp (r, s) = (62, 47).

Như với các Private Key và Public Key, chữ ký này thường được đại diện bởi một chuỗi thập lục phân.

Xác minh chữ ký với Khóa Public

Bây giờ chúng ta có một dữ liệu và chữ ký cho dữ liệu đó. Một bên thứ ba có Public Key của chúng ta có thể nhận được dữ liệu và chữ ký của chúng ta, và xác nhận rằng chúng ta là người gửi. Hãy xem cách làm việc này.

Với Q là khóa công khai và các biến khác được xác định như trước, các bước để xác minh chữ ký như sau:

1. Xác minh rằng r và s nằm giữa 1 và n – 1.
2. Tính w = s-1 mod n
3. Tính u = z * w mod n
4. Tính v = r * w mod n
5. Tính điểm (x, y) = uG + vQ
6. Xác minh rằng r = x mod n. Nếu sai, thì chữ ký không hợp lệ.

Tại sao các bước trên lại dùng để xác minh được? Hãy thực hiện theo các công thức và xem cách nó hoạt động. Các biến của chúng ta, một lần nữa là:

z = 17 (dữ liệu)
(r, s) = (62, 47) (chữ ký)
n = 79 (bậc của điểm)
G = (2, 22) (điểm cơ bản)
Q = (52, 7) (khoá public)

1. Xác minh rằng r và s là giữa 1 và n – 1. Kiểm tra và kiểm tra.

r: 1 <= 62 <79
s: 1 <= 47 <79

2. Tính toán w:

w = s-1 mod n
w = 47-1 mod 79
w = 37

3. Tính toán u:

u = zw mod n
u = 17 * 37 mod 79
u = 629 mod 79
u = 76

4. Tính toán v:

v = rw mod n
v = 62 * 37 mod 79
v = 2294 mod 79
v = 3

5. Tính điểm (x, y):

(x, y) = uG + vQ

Hãy chia nhỏ phép toán phép cộng điểm và phép nhân đôi điểm trong uG và vQ riêng biệt.

uG = 76G
uG = 2(38G)
uG = 2( 2(19G) )
uG = 2( 2(G + 18G) )
uG = 2( 2(G + 2(9G) ) )
uG = 2( 2(G + 2(G + 8G) ) )
uG = 2( 2(G + 2(G + 2(4G) ) ) )
uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

Hãy suy nghĩ một lát để đánh giá cao việc sử dụng phép nhóm lại như trên chúng ta đã giảm được từ 75 phép phép cộng điểm liên tục để chỉ cần dùng 6 lần phép nhân đôi điểm và 2 lần phép cộng điểm. Những thủ thuật sẽ có ích khi các con số trở nên thực sự lớn.

Làm theo cách của chúng ta từ trong ra ngoài:

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )
uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )
uG = 2( 2(G + 2(G + 2(25, 17) ) ) )
uG = 2( 2(G + 2( (2, 22) + (21, 42) ) ) )
uG = 2( 2(G + 2(13, 44) ) )
uG = 2( 2( (2, 22) + (66, 26) ) )
uG = 2( 2(38, 26) )
uG = 2(27, 40)
uG = (62, 4)

Và bây giờ cho vQ:

vQ = 3Q
vQ = Q + 2Q
vQ = Q + 2(52, 7)
vQ = (52, 7) + (25, 17)
vQ = (11, 20)

Đưa chúng lại với nhau:

(x, y) = uG + vQ
(x, y) = (62, 4) + (11, 20)
(x, y) = (62, 63)

Rõ ràng bước 5 chứa phần lớn các công việc tính toán.

6. Xác minh rằng r = x mod n

r = x mod n
62 = 62 mod 79
62 = 62

Chữ ký của chúng ta là hợp lệ!

Kết luận

Đối với những bạn bỏ qua tất cả các phương trình và chỉ đọc phần dưới cùng, chúng ta vừa học được điều gì?

Chúng ta đã phát triển một số trực giác về mối quan hệ toán học sâu sắc tồn tại giữa Public Key và Private Key. Chúng ta đã thấy ngay cả trong các ví dụ toán học đơn giản nhất đằng sau chữ ký và xác minh đã nhanh chóng trở nên phức tạp, và chúng ta có thể đánh giá cao sự phức tạp rất lớn khi các thông số liên quan đến những con số 256-bit. Chúng ta đã thấy các ứng dụng thông minh của các thủ tục toán học đơn giản nhất có thể tạo ra những “cái bẫy cửa” một chiều để tạo ra các hàm toán học cần thiết để bảo vệ sự bất đối xứng thông tin mà trong đó xác định quyền sở hữu của một Bitcoin. Qua đó chúng ta có được sự tự tin về sự vững mạnh của hệ thống, với điều kiện là chúng ta cẩn thận bảo vệ các thông tin về Private Key.

Đây là lý do tại sao người ta thường nói rằng Bitcoin được “sự ủng hộ của toán học.”

Tham khảo thêm tại bài viết Elliptic Curve Cryptography: a gentle introduction