Một lý do mà Bitcoin có thể gây khó hiểu cho người mới bắt đầu là 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ó thể là một ngôi nhà hoặc một khoản tiền, có nghĩa là thứ đó 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 Bitcoin thì hoàn toàn khác. Bitcoin 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ổ kế toán phân phối được gọi là chuỗi khối (blockchain), mà bản sao được chia sẻ bởi một mạng lưới các máy tính tình nguyện kết nối. Để “sở hữu” một Bitcoin 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. Điều gì cho phép khả năng này? Đó là quyền nắm giữ một cặp mã khóa public và khóa private ECDSA. Điều đó có nghĩa là gì và tại sao nó giúp Bitcoin an toàn?
Chúng ta 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à một quá trình 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 khả năng độc quyền tạo ra các chữ ký. Với Bitcoin, 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 ký sử dụng các khóa riêng (private key), và quá trình xác minh sử dụng khóa công khai (public key). Chúng tôi sẽ đưa ra một ví dụ về điều này.
Nhưng trước tiên, hãy có một khóa học nhỏ về đường cong Elliptic và các trường hữu hạn.
Đường Cong Elliptic.
Một đường cong elliptic được biểu diễn đại số như là một phương trình có dạng:
y 2 = x 3 + ax + b
Đối với a = 0 và b = 7 (phiên bản được sử dụng bởi Bitcoin), nó trông như sau:
Các đườ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 tính chất khác là một đường tiếp tuyến không thẳng đứng với đường cong tại một điểm sẽ cắt nhau đúng một điểm khác trên đường cong.
Chúng ta có thể sử dụng các đặc tính này để xác định hai phép toán: Cộng điểm và Nhân Đôi Điểm.
Phép Cộng Điểm, P + Q = R, được định nghĩa là sự phản ánh thông qua trục x của điểm giao nhau thứ ba R’ trên một đường thẳng bao gồm P và Q. Cách dễ nhất để hiểu được điều này là nhìn vào sơ đồ sau:
Tương tự như vậy, phép nhân đôi điểm, P + P = R được xác định bằng cách tìm các đường tiếp tuyến với phép nhân đôi điểm P, và việc phản ánh thông qua trục x của các điểm giao nhau R’ trên đường cong để có được R. Dưới đây là một ví dụ về việc nó trông thế nào:
Cùng với nhau, hai phép toán này được sử dụng để nhân vô hướng, R = a P, được xác định 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.
Trường Hữu Hạn
Một trường hữu hạn, trong bối cảnh ECDSA, có thể được hiểu như là một phạm vi 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 này sẽ “được đưa về” phạm vi này.
Cách đơn giản nhất để nghĩ về điều này là phép dư, được đại diện bởi phép modulus (mod). Ví dụ, 9/7 sẽ ra 1 với 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:
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 một cách trực quan. Đường vẽ trên đồ thị này sẽ quấn quanh hướng ngang và dọc, giống như trong một trò chơi các tiểu hành tinh, và vẫn duy trì độ dốc. 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).
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).
Trong trường hợp của Bitcoin:
Phương trình đường cong Elliptic:
Khóa Private và Khóa Public
Bây giờ chúng ta sẽ tìm hiểu thế nào là khóa public và khóa private, và chúng liên quan với nhau thế nào. Đây là một cách giải thích ngắn gọn: Trong ECDSA, khóa private là một số không đoán được nằm giữa số 1 và bậc của điểm. Khóa public có nguồn gốc từ khóa riêng bằng cách nhân vô hướng điểm cơ sở số lần bằng giá trị của khóa private. Thể hiện như phương trình sau:
Khóa public = khóa private * điểm cơ sở
Điều này cho thấy số lượng tối đa khóa private (là các địa chỉ Bitcoin) 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 khóa public 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 = (qy – py) / (qx – px)
rx = c2 – px – qx
ry = c (px – rx) – py
Và từ phép nhân đôi điểm p để tìm ra r là như sau:
c = (3px2 + a) / 2py
rx = c2 – 2px
ry = c (px – rx) – py
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 2 = x 3 + 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 (bạn có thể đọc ở đây và ở đây nếu quan tâm). Trong trường hợp hiện tại, bạn sẽ phải tin tưởng chúng tôi khi viết rằng:
44-1 = 32
Tiếp tục:
c = 12 * 32 mod 67
c = 384 mod 67
c = 49
rx = (492 – 2 * 2) mod 67
rx = (2401 – 4) mod 67
rx = 2397 mod 67
rx = 52
ry = (49 * (2 – 52) – 22) mod 67
ry = (49 * (-50) – 22) mod 67
ry = (-2450 – 22) mod 67
ry = -2472 mod 67
ry = 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 Khóa Private
Bây giờ chúng ta có một cặp khóa private và khóa public, 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à khóa private. Công thức ký như sau:
Chọn một số nguyên k giữa 1 và n – 1.
Tính điểm (x, y) = k * G, sử dụng phép nhân vô hướng.
Tìm r = x mod n. Nếu r = 0, quay lại bước 1.
Tìm s = (z + r * d) / k mod n. Nếu s = 0, quay lại bước 1.
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à kkhô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)
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!)
Tính điểm. Đ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
Tìm r:
r = x mod n
r = 62 mod 79
r = 62
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
Chữ ký của chúng ta là cặp (r, s) = (62, 47).
Như với các khóa private và khóa public, 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ó khóa công khai của chúng tôi có thể nhận được dữ liệu và chữ ký của chúng tôi, và xác nhận rằng chúng tôi 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:
Xác minh rằng r và s nằm giữa 1 và n – 1.
Tính w = s-1 mod n
Tính u = z * w mod n
Tính v = r * w mod n
Tính điểm (x, y) = uG + vQ
Xác minh rằng r = x mod n. Chữ ký không hợp lệ nếu nó không đúng.
Tại sao các bước trên lại dùng để xác minh được? Chúng tôi sẽ bỏ qua các bằng chứng, nhưng bạn có thể thêm đọc chi tiết ở đây. 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 tôi, 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)
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
Tính toán w:
w = s-1 mod n
w = 47-1 mod 79
w = 37
Tính toán u:
u = zw mod n
u = 17 * 37 mod 79
u = 629 mod 79
u = 76
Tính toán v:
v = rw mod n
v = 62 * 37 mod 79
v = 2294 mod 79
v = 3
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 tôi 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. Đối với bước cuối cùng,
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 khóa public và khóa private. 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ề khóa private.
Nói cách khác, đâ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.”
Nếu bạn chịu khó đọc và tìm hiểu kỹ, chúng tôi hy vọng bài viết sẽ đem đến cho bạn sự tự tin để thực hiện bước tiếp theo và tự mình thử lấy các phép toán (sử dụng máy tính số học modular sẽ dễ dàng hơn nhiều cho bạn). Chúng tôi thấy rằng tìm hiểu các bước của việc ký kết và xác minh dữ liệu bằng tay sẽ giúp chúng ta có một sự hiểu biết sâu sắc hơn về mật mã mà đại diện cho hình thức sở hữu riêng biệt của tiền mã hóa Bitcoin.
***
Cảm ơn Steven Phelps đã giúp đỡ với bài viết này.
Để sở hữu một cái gì đó theo nghĩa truyền thống, có thể là một ngôi nhà hoặc một khoản tiền, có nghĩa là thứ đó 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 Bitcoin thì hoàn toàn khác. Bitcoin 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ổ kế toán phân phối được gọi là chuỗi khối (blockchain), mà bản sao được chia sẻ bởi một mạng lưới các máy tính tình nguyện kết nối. Để “sở hữu” một Bitcoin 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. Điều gì cho phép khả năng này? Đó là quyền nắm giữ một cặp mã khóa public và khóa private ECDSA. Điều đó có nghĩa là gì và tại sao nó giúp Bitcoin an toàn?
Chúng ta 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à một quá trình 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 khả năng độc quyền tạo ra các chữ ký. Với Bitcoin, 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 ký sử dụng các khóa riêng (private key), và quá trình xác minh sử dụng khóa công khai (public key). Chúng tôi sẽ đưa ra một ví dụ về điều này.
Nhưng trước tiên, hãy có một khóa học nhỏ về đường cong Elliptic và các trường hữu hạn.
Đường Cong Elliptic.
Một đường cong elliptic được biểu diễn đại số như là một phương trình có dạng:
y 2 = x 3 + ax + b
Đối với a = 0 và b = 7 (phiên bản được sử dụng bởi Bitcoin), nó trông như sau:
Các đườ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 tính chất khác là một đường tiếp tuyến không thẳng đứng với đường cong tại một điểm sẽ cắt nhau đúng một điểm khác trên đường cong.
Chúng ta có thể sử dụng các đặc tính này để xác định hai phép toán: Cộng điểm và Nhân Đôi Điểm.
Phép Cộng Điểm, P + Q = R, được định nghĩa là sự phản ánh thông qua trục x của điểm giao nhau thứ ba R’ trên một đường thẳng bao gồm P và Q. Cách dễ nhất để hiểu được điều này là nhìn vào sơ đồ sau:
Tương tự như vậy, phép nhân đôi điểm, P + P = R được xác định bằng cách tìm các đường tiếp tuyến với phép nhân đôi điểm P, và việc phản ánh thông qua trục x của các điểm giao nhau R’ trên đường cong để có được R. Dưới đây là một ví dụ về việc nó trông thế nào:
Cùng với nhau, hai phép toán này được sử dụng để nhân vô hướng, R = a P, được xác định 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.
Trường Hữu Hạn
Một trường hữu hạn, trong bối cảnh ECDSA, có thể được hiểu như là một phạm vi 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 này sẽ “được đưa về” phạm vi này.
Cách đơn giản nhất để nghĩ về điều này là phép dư, được đại diện bởi phép modulus (mod). Ví dụ, 9/7 sẽ ra 1 với 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:
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 một cách trực quan. Đường vẽ trên đồ thị này sẽ quấn quanh hướng ngang và dọc, giống như trong một trò chơi các tiểu hành tinh, và vẫn duy trì độ dốc. 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).
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).
Trong trường hợp của Bitcoin:
Phương trình đường cong Elliptic:
Phương trình đường cong Elliptic: y 2 = x 3 + 7Ai đã chọn những con số này, và tại sao? Một lượng lớn các nghiên cứu, và một lượng kha khá những thuyết âm mư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 một phương pháp backdoor để tìm ra khóa private. 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ã.
Modulo nguyên tố = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 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
Khóa Private và Khóa Public
Bây giờ chúng ta sẽ tìm hiểu thế nào là khóa public và khóa private, và chúng liên quan với nhau thế nào. Đây là một cách giải thích ngắn gọn: Trong ECDSA, khóa private là một số không đoán được nằm giữa số 1 và bậc của điểm. Khóa public có nguồn gốc từ khóa riêng bằng cách nhân vô hướng điểm cơ sở số lần bằng giá trị của khóa private. Thể hiện như phương trình sau:
Khóa public = khóa private * điểm cơ sở
Điều này cho thấy số lượng tối đa khóa private (là các địa chỉ Bitcoin) 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 khóa public 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 = (qy – py) / (qx – px)
rx = c2 – px – qx
ry = c (px – rx) – py
Và từ phép nhân đôi điểm p để tìm ra r là như sau:
c = (3px2 + a) / 2py
rx = c2 – 2px
ry = c (px – rx) – py
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 2 = x 3 + 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 (bạn có thể đọc ở đây và ở đây nếu quan tâm). Trong trường hợp hiện tại, bạn sẽ phải tin tưởng chúng tôi khi viết rằng:
44-1 = 32
Tiếp tục:
c = 12 * 32 mod 67
c = 384 mod 67
c = 49
rx = (492 – 2 * 2) mod 67
rx = (2401 – 4) mod 67
rx = 2397 mod 67
rx = 52
ry = (49 * (2 – 52) – 22) mod 67
ry = (49 * (-50) – 22) mod 67
ry = (-2450 – 22) mod 67
ry = -2472 mod 67
ry = 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 Khóa Private
Bây giờ chúng ta có một cặp khóa private và khóa public, 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à khóa private. Công thức ký như sau:
Chọn một số nguyên k giữa 1 và n – 1.
Tính điểm (x, y) = k * G, sử dụng phép nhân vô hướng.
Tìm r = x mod n. Nếu r = 0, quay lại bước 1.
Tìm s = (z + r * d) / k mod n. Nếu s = 0, quay lại bước 1.
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à kkhô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)
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!)
Tính điểm. Đ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
Tìm r:
r = x mod n
r = 62 mod 79
r = 62
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
Chữ ký của chúng ta là cặp (r, s) = (62, 47).
Như với các khóa private và khóa public, 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ó khóa công khai của chúng tôi có thể nhận được dữ liệu và chữ ký của chúng tôi, và xác nhận rằng chúng tôi 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:
Xác minh rằng r và s nằm giữa 1 và n – 1.
Tính w = s-1 mod n
Tính u = z * w mod n
Tính v = r * w mod n
Tính điểm (x, y) = uG + vQ
Xác minh rằng r = x mod n. Chữ ký không hợp lệ nếu nó không đúng.
Tại sao các bước trên lại dùng để xác minh được? Chúng tôi sẽ bỏ qua các bằng chứng, nhưng bạn có thể thêm đọc chi tiết ở đây. 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 tôi, 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)
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
Tính toán w:
w = s-1 mod n
w = 47-1 mod 79
w = 37
Tính toán u:
u = zw mod n
u = 17 * 37 mod 79
u = 629 mod 79
u = 76
Tính toán v:
v = rw mod n
v = 62 * 37 mod 79
v = 2294 mod 79
v = 3
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 tôi 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. Đối với bước cuối cùng,
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 khóa public và khóa private. 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ề khóa private.
Nói cách khác, đâ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.”
Nếu bạn chịu khó đọc và tìm hiểu kỹ, chúng tôi hy vọng bài viết sẽ đem đến cho bạn sự tự tin để thực hiện bước tiếp theo và tự mình thử lấy các phép toán (sử dụng máy tính số học modular sẽ dễ dàng hơn nhiều cho bạn). Chúng tôi thấy rằng tìm hiểu các bước của việc ký kết và xác minh dữ liệu bằng tay sẽ giúp chúng ta có một sự hiểu biết sâu sắc hơn về mật mã mà đại diện cho hình thức sở hữu riêng biệt của tiền mã hóa Bitcoin.
***
Cảm ơn Steven Phelps đã giúp đỡ với bài viết này.
Nguồn: The Math behind Bitcoin – Chain.com
Dịch: Phil Trịnh /http://www.bitcoinvietnam.com.vn
[toan-hoc-dang-sau-bitcoin-blockchain]. rev
Ngày đăng 22/06/2016
Post a Comment