Tôi sẽ mô tả thủ thuật Shamir tiêu chuẩn phù hợp với ngữ cảnh của xác minh chữ ký ECDSA. Giảm một số chỉ số, phần tính toán đắt tiền của nó là tính toán
$$u\cdot G+v\cdot Q$$
ở đâu $u$ và $v$ là (chúng tôi giả sử, hoàn toàn tích cực) số nguyên, $G$ và $Q$ là các điểm Đường cong Elliptic và $+$ là điểm cộng (để đơn giản hóa, tôi xem xét một hộp đen, mà việc thực thi chi phối chi phí tính toán). Nhớ lại rằng theo định nghĩa, $$u\cdot G=\underbrace{G+G+\ldots+G+G}_{u\text{ term}}$$
Đáng lưu ý $\mathbin\|u\mathbin\|$ cho số bit trong số nguyên $u$, đó là $\left\lfloor\log_2(u)+1\right\rfloor$; giống với $\mathbin\|v\mathbin\|$.
Một cách tính toán phổ biến $u\cdot G$ là để
- bộ $R:=G$
- cho bit $b$ được sao chép từ biểu diễn nhị phân của $u$, bắt đầu từ chỉ số $\mathbin\|u\mathbin\|-1$ (bit đầu tiên bên phải của ngoài cùng bên trái $1$ bit) xuống tới $0$ (bit ngoài cùng bên phải)
- bộ $R:=R+R$
- nếu $b=1$, bộ $R:=R+G$
Cách tính cơ bản $u\cdot G+v\cdot Q$ sẽ là để tính toán $u\cdot G$, sau đó $v\cdot Q$ bằng phương pháp tương tự, sau đó cộng hai kết quả. Thủ thuật của Shamir cải thiện điều đó:
- bộ $H:=G+Q$
- nếu $\mathbin\|u\mathbin\|>\mathbin\|v\mathbin\|$, bộ $R:=G$;
- khác nếu $\mathbin\|u\mathbin\|<\mathbin\|v\mathbin\|$, bộ $R:=Q$;
- khác (nghĩa là nếu $\mathbin\|u\mathbin\|=\mathbin\|v\mathbin\|$ ), bộ $R:=H$;
- cho bit $b$ (tương ứng $c$) được sao chép từ biểu diễn nhị phân của $u$ (tương ứng $v$), với các đại diện của $u$ hoặc $v$ đệm trái với số 0 khi cần thiết, tại chỉ mục từ $\max(\mathbin\|u\mathbin\|,\mathbin\|v\mathbin\|)-1$ xuống đến $0$
- bộ $R:=R+R$
- nếu $b=1$ và $c=0$, bộ $R:=R+G$
- (khác) nếu $b=0$ và $c=1$, bộ $R:=R+Q$
- (khác) nếu $b=1$ và $c=1$, bộ $R:=R+H$
Tuyên bố này gần tương đương với tuyên bố được đưa ra trong câu trả lời này dưới cái tên thủ thuật Strauss-Shamir (khi tôi biết thủ thuật này là của Shamir). Biến thể tôi đưa ra tránh nhu cầu biết nhóm trung lập, nhưng yêu cầu $\max(u,v)>0$.
Tính đúng đắn của phép nhân điểm tiêu chuẩn và mẹo của Shamir có thể được chứng minh chính thức bằng quy nạp.
Đối với ngẫu nhiên lớn $u$ và $v$ của $k$ bit, thuật toán ngây thơ để tính toán $u\cdot G+v\cdot Q$ thực hiện trung bình $\xấp xỉ3k$ bổ sung điểm, thủ thuật của Shamir làm giảm điều đó xuống $\khoảng 1,75k$, chẳng hạn như ít hơn 42% (lợi ích chi phí thấp hơn, phần lớn là do nhân đôi điểm $R:=R+R$ là loại cộng điểm nhanh nhất và là loại bị giảm nhiều nhất). Có những cải tiến hơn nữa có thể, ví dụ: nhóm các bit thành hai hoặc nhiều hơn một chút, có lẽ với "cửa sổ trượt" khi $b=0=c$.
Lưu ý rằng trong bối cảnh xác minh chữ ký, $u$, $v$, $G$ và $Q$ tất cả đều công khai, do đó, các kênh phụ (thời gian, mức tiêu thụ năng lượng, phát xạ, bộ nhớ cache...) không phải là vấn đề bảo mật vì chúng đang trong quá trình tạo chữ ký.
Tôi không biết thủ thuật Strauss-Shamir của câu hỏi tài liệu tham khảo khác, nhưng nghi ngờ một cách mơ hồ rằng nó sẽ cải thiện hơn nữa vấn đề này bằng cách đôi khi thực hiện phép trừ thay vì phép cộng và/hoặc tương thích hơn với kỹ thuật tăng tốc để cộng điểm.
