Làm cách nào bạn có thể xác minh quyền sở hữu khóa riêng bằng khóa chung và chữ ký thư?

Khi tôi ký một tin nhắn bằng khóa riêng tư và tôi nhận được chữ ký tin nhắn, làm cách nào để tôi có thể - sử dụng khóa chung tương ứng - xác minh rằng chữ ký giao dịch/tin nhắn đó phải được tạo bởi người nắm giữ khóa riêng tư khóa đằng sau khóa công khai có liên quan?

Tôi hiểu rằng với các cặp khóa riêng/công khai, điểm quan trọng của công nghệ là bạn không thể thiết kế ngược khóa riêng từ khóa chung. Vì vậy, làm thế nào là nó có thể làm điều đó?

Về cơ bản, sự khác biệt giữa kỹ thuật đảo ngược khóa riêng từ khóa chung và xác minh rằng ai đó phải có khóa riêng để tạo chữ ký thư tương ứng với khóa chung là gì? Làm thế nào là một có thể nhưng không phải là khác?

Tôi sẽ giải thích cách chữ ký liên quan đến đường cong elip hoạt động. Tiền điện tử chủ yếu sử dụng các đường cong elip do kích thước chữ ký nhỏ hơn cần được xuất bản trên chuỗi khối.

Khi một khóa riêng, chỉ là một số nguyên lớn, được ánh xạ tới một khóa chung (là một điểm trên một đường cong elip xác định), ánh xạ này có các thuộc tính toán học nhất định. Lưu ý rằng ánh xạ này được thực hiện theo cách "một chiều". Bạn có thể dễ dàng ánh xạ từ khóa riêng sang điểm đường cong elip của khóa chung, nhưng thực tế bạn không thể đảo ngược thao tác đó.

Thứ nhất, các điểm trên đường cong elip sẽ tạo thành một nhóm Abelian theo một phép toán mà chúng tôi gọi là "phép cộng". Điều này có nghĩa là bạn có thể làm những gì giống như đại số đơn giản với các điểm. Bạn có thể lấy điểm $A$ và $B$, thêm chúng để nhận điểm $C$, và bạn sẽ có thể quan sát điều đó $A+B==B+A$. Lưu ý rằng chúng tôi chỉ xác định các hoạt động cộng và trừ và chúng tôi không thể "nhân" điểm hoặc "chia" điểm với các điểm khác.

Thứ hai, ánh xạ của các số nguyên khóa riêng tới các điểm là "đồng hình bổ sung". Điều này có nghĩa là nếu bạn có khóa riêng $a$ và $b$, ánh xạ tới các khóa công khai $A$ và $B$, thì khóa công khai của $a+b$ sẽ bằng cả hai $A+B$ và để $C$.

Việc ánh xạ khóa riêng sang khóa chung chỉ đơn giản là lấy khóa riêng $a$ và tính khóa công khai $aG$, có nghĩa là thêm điểm nổi tiếng $G$ với chính nó $a$ lần. Vì sẽ mất mãi mãi để thực sự tính toán điều này bằng cách thêm G vào chính nó $a$ lần, có sẵn các phím tắt toán học. Vì các phím tắt này chỉ tồn tại để thực hiện phép nhân một cách nhanh chóng chứ không phải để quay ngược lại và xác định khóa riêng từ bất kỳ kết quả phép nhân nào, điều này trở thành "một chiều"cửa sập" chức năng.

Bây giờ, hãy tưởng tượng rằng tôi có khóa riêng $a$ và khóa công khai $A=aG$, và bạn đưa ra một thách thức với tôi. Bạn nghĩ ra một số nguyên khóa riêng ngẫu nhiên $x$, và bạn yêu cầu tôi cung cấp cho bạn một số nguyên phản hồi $y$ để bạn có thể xác minh rằng $xA==yG$. Tôi sẽ chỉ có thể vượt qua thử thách của bạn nếu tôi biết khóa riêng $a$, điều này sẽ cho phép tôi tính toán $y=xa$. Điều này sẽ xác minh bởi vì sau đó $xA==xaG==yG$.

Những gì tôi đã mô tả ở trên có hai sai sót. Đầu tiên là khi tôi vượt qua thử thách, bạn có thể dễ dàng tính khóa riêng của tôi $a$ như $y/x$.

Lỗ hổng thứ hai là tôi cần bạn đưa ra một thử thách cho tôi, thay vì chỉ đơn giản là có thể cung cấp cho bạn chữ ký mà không cần phải tương tác với bạn.

Lỗ hổng đầu tiên được giải quyết bằng cách bao gồm một "yếu tố mù", cho phép tôi vượt qua thử thách mà không tiết lộ khóa riêng của mình. Ví dụ: với chữ ký Schnorr, tôi chọn một khóa riêng ngẫu nhiên $k$, chỉ tiết lộ $K=kG$, và sau đó yêu cầu bạn cho thử thách của bạn $x$. Sau đó, tôi tạo ra một giá trị $y$ để bạn có thể xác minh rằng $xA==K+yG$. Bây giờ, sau khi tôi tiết lộ $y$ để vượt qua thử thách, bạn biết rằng tôi chỉ có thể tính toán $y$ với kiến ​​​​thức về khóa riêng của tôi $a$, nhưng bạn không thể tính toán khóa riêng của tôi mà không biết yếu tố che khuất bí mật của tôi $k$.

Lỗ hổng thứ hai được giải quyết bằng cách sử dụng FiatâShamir heuristic để tạo thử thách bằng cách sử dụng chức năng đóng vai trò là "Oracle ngẫu nhiên" điều đó cho phép tôi đưa ra thử thách ngẫu nhiên mà không có cách nào để gian lận. Trong trường hợp lược đồ chữ ký ECDSA, đầu ra của hàm này là tọa độ x của khóa chung được ánh xạ từ một đầu vào cụ thể. Trong trường hợp của Schnorr chữ ký, hàm này là hàm băm bảo mật bằng mật mã, chẳng hạn như SHA512/256.

Khi tôi ký một tin nhắn/giao dịch¹ bằng khóa riêng tư,
và tôi nhận được một tin nhắn/giao dịch¹ chữ ký,

Điều quan trọng là nó đã sử dụng các cặp khóa công khai/riêng tư khác nhau trong hai thứ này. Không có gì trong phần còn lại của câu hỏi là về điều đầu tiên trong hai điều này. Mọi thứ là về việc xác minh chữ ký trong điều thứ hai trong số những điều này, đối với khóa công khai của cặp khóa công khai/riêng tư được người ký sử dụng trong điều thứ hai đã nói. Khóa công khai đã nói được giả định là có sẵn cho người xác minh. Khóa riêng phù hợp thì không.

Với các cặp khóa riêng tư/công khai, điểm mấu chốt của công nghệ là bạn không thể thiết kế ngược khóa riêng tư từ khóa chung

Chính xác. Còn một điều nữa: với khóa chung, không thể thực hiện những việc mà khóa riêng dự định thực hiện.

Sự khác biệt giữa kỹ thuật đảo ngược khóa riêng từ khóa chung và xác minh rằng ai đó phải có khóa riêng để tạo chữ ký thư tương ứng với khóa chung là gì? Làm thế nào là một có thể nhưng không phải là khác?

Chữ ký hoạt động theo sơ đồ này:

và bởi một sách giáo khoa hiện đại

• $1^n$ mã hóa số nguyên $n$ xác định kích thước của các phím. Trong thực tế $n$ là cố định và công khai.
• $(\mathrm{pk},\mathrm{sk})$ là đầu ra của cặp khóa công khai/riêng tư bằng thuật toán tạo khóa $\mathrm{Gen}$. Nó giả định $\mathrm{sk}$ được giữ bí mật bởi chủ sở hữu được chỉ định của cặp khóa, người thường xuyên nhất là người đã chạy $\mathrm{Gen}$.
• $m$ là thông báo cần ký (một chuỗi bit tùy ý, có thể lưu lại cho các yêu cầu về kích thước).
• $\sigma$ là chữ ký của tin nhắn. Nó được sản xuất từ $\mathrm{sk}$ và $m$ bằng thuật toán chữ ký $\mathrm{Sign}$.
• $b$ là chỉ báo toàn vẹn, nhận một trong hai giá trị, Có hiệu lực hoặc Không hợp lệ. Nó được sản xuất từ $\mathrm{pk}$, $m$ và $\sigma$ bằng thuật toán xác minh $\mathrm{Vrfy}$.

Sơ đồ chữ ký đúng khi, với những thứ như hình vẽ, $b$ luôn luôn là Có hiệu lực. Nó an toàn² khi có đối thủ $\mathrm{pk}$ và khả năng thu được $\sigma_i$ bất cứ gì $m_i$ họ thấy phù hợp, không thể thể hiện một $(m,\sigma)$ cặp với $\mathrm{Vrfy}(\mathrm{pk},m,\sigma)$ Có hiệu lực, và $m\ne m_i$ bất cứ gì $i$. Có một số chi tiết kỹ thuật khác³.

Thật đáng ngạc nhiên khi có những lược đồ chữ ký chính xác và an toàn. Việc phát minh ra một chiếc đã được thực hiện từ lâu. Nhưng không có gì đáng ngạc nhiên hơn khả năng mã hóa khóa công khai. Nếu một người chủ yếu quan tâm đến việc hiểu sử dụng của chữ ký, một tùy chọn là thừa nhận có các sơ đồ chữ ký như vậy.

Một lựa chọn khác là nghiên cứu một. Tôi đề nghị chữ ký Schnorr (thay thế. phiên bản), nguyên tắc được sử dụng trong một số loại tiền điện tử, có lẽ là đơn giản nhất và có mức giảm bảo mật định lượng tương đối đơn giản đối với độ khó của Bài toán logarit rời rạc trong nhóm được sử dụng, theo mô hình tiên tri ngẫu nhiên của hàm băm của nó. Phơi bày nó sẽ tăng gấp ba lần độ dài của câu trả lời.

¹ Trong bối cảnh tiền điện tử, một thông báo có thể mô tả một giao dịch.

² Theo tiêu chí Existentally UnForgeable theo Chosen Message Attack, thường là tiêu chí duy nhất được thảo luận trong phần trình bày giới thiệu hiện đại. Có các tiêu chí bảo mật chữ ký hữu ích khác.

³ $\mathrm{Gen}$, $\mathrm{Sign}$, $\mathrm{Vrfy}$ và các đối thủ được mô hình hóa như các thuật toán thời gian đa thức xác suất. Đề xuất được nêu cho bất kỳ cố định $(\mathrm{pk},\mathrm{sk})$ cặp đầu ra bởi $\mathrm{Gen}$, và ngoại trừ với xác suất không đáng kể $p(n)$, đó là $p(n)$ sao cho với mọi đa thức $Q(n)$ nó giữ $\displaystyle 0=\lim_{n\to\infty} p(n)\,Q(n)$. Trong thực tế $n$ được chọn đủ cao để làm cho xác suất đó thực tế không đáng kể.

Về cơ bản, sự khác biệt giữa kỹ thuật đảo ngược một khóa riêng từ khóa chung và xác minh rằng ai đó phải có khóa riêng để tạo chữ ký tin nhắn tương ứng với một khóa công khai? Làm thế nào là một có thể nhưng không phải là khác?

Thực tế là không thể tìm thấy khóa riêng dựa trên khóa chung và đây là toàn bộ điểm của mật mã khóa công khai. Đây là vẻ đẹp thuần túy của toán học. Câu hỏi thứ hai của bạn là hỏi cách thức hoạt động của chữ ký điện tử. Chữ ký điện tử thường được tạo bằng cách trước tiên tính toán thông báo tóm tắt của tin nhắn văn bản thuần túy của bạn (ví dụ: sử dụng sha256), sau đó mã hóa thông báo bằng khóa riêng của bạn. Văn bản mật mã của bạn cùng với chữ ký điện tử trông giống như:

public_announcement, signature=encrypt(sha256(public_annoucement), private_key)

Bất kỳ người nhận nào cũng có thể tính toán thông báo sha256 của public_annoucement và so sánh với giải mã(sha256(public_annoucement), public_key)`. Nếu hai điều này không khớp, thì thông báo bị giả mạo hoặc nó không được ký bằng khóa riêng mà nó tuyên bố là.