Trong đầu tôi, tôi đề xuất biến thể EC-ElGamal này trên Đường cong Elliptic 256 bit tiêu chuẩn, sử dụng hàm băm và XOR cho phần mã hóa (giảm gần một nửa kích thước bản mã so với EC-ElGamal trong sách giáo khoa) và giao dịch công việc/không gian đơn giản -off để thêm vào một bản mã 32 byte một tin nhắn $m$ của $b$ bit, với cố định nhỏ $b$ (ví dụ. $b=8$).
- Sử dụng Đường cong Elliptic tiêu chuẩn trên trường $\mathbb F_p$ với máy phát điện $G$ trật tự $n$, với $p$ và $n$ Số nguyên tố 256-bit và (phỏng đoán) bảo mật 128-bit. secp256r1 (còn gọi là NIST P-256) và secp256k1 đủ tiêu chuẩn. Tôi muốn đề cập đến Sec1v2 cho toán học và ký hiệu ECC.
- Tạo khóa:
- Chọn khóa riêng $d$ ngẫu nhiên trong khoảng thời gian $[1,n)$
- Tính khóa công khai $Q\được d\,G$
- mã hóa của $b$-bit bản rõ $m$
- Chọn $e$ ngẫu nhiên trong khoảng thời gian $[1,2^{32})$
- tính toán $F\được e\,G$
- Chọn $k$ ngẫu nhiên trong khoảng thời gian $[1,n)$
- tính toán $R\được k\,G$
- Trong khi $R_x\not\equiv0\pmod{2^b}$
- tính toán $R\được R+F$ và $k\được k+e$, duy trì $R=k\,G$
- Nếu $k\gen$ RNG đã chọn $k$ rất có thể bị hỏng; hủy bỏ hoặc khởi động lại mã hóa
- Nếu $R_y$ là lẻ, đặt $R_y\được p-R_y$ và $k\được n-k$, duy trì $R=k\,G$
- tính toán $S\được k\,Q$ (điểm bí mật được chia sẻ)
- tính toán $u\gets \operatorname{SHA-256}(S_x)\bmod2^b$, ở đâu $S_x$ được thể hiện dưới dạng một chuỗi byte 32 byte
- tính toán $v\được u\oplus m$
- Đầu ra bản mã 256-bit, bao gồm $256-b$ bit cho $R_x$ với bậc thấp $b$ các bit bị loại bỏ (chúng bằng 0 theo cấu trúc) và $b$ bit cho $v$
- giải mã:
- Từ trích xuất bản mã $R_x$ (chèn $b$ bit bậc thấp ở mức 0) và $v$
- tính toán một $R_y$ phù hợp $R_x$ (đó là một kỹ thuật tiêu chuẩn để hoàn tác nén điểm, xem Sec1v2 §2.3.4, bước 2.4.1); nếu thất bại, hủy bỏ giải mã.
- Nếu $R_y$ là lẻ, đặt $R_y\được p-R_y$
- tính toán $S\được d\,R$ (điểm bí mật được chia sẻ)
- tính toán $u\gets \operatorname{SHA-256}(S_x)\bmod2^b$, ở đâu $S_x$ được thể hiện dưới dạng một chuỗi byte 32 byte
- Tính toán và xuất bản rõ được giải mã $m\được u\oplus v$
tôi phỏng đoán IND-CCA1 (do đó IND-CPA) bảo mật ở mức 128 bit, theo các giả định hợp lý (độ cứng của một biến thể của bài toán Diffie-Hellman quyết định đối với Đường cong Elliptic và SHA-256 được lập mô hình như một tiên tri ngẫu nhiên). Có một cuộc tấn công nhỏ chống lại IND-CCA2 (do đó, việc truy cập vào một lời tiên tri giải mã sẽ ảnh hưởng đến tính bảo mật của các tin nhắn trong quá khứ ngay cả khi lời tiên tri giải mã đã đưa các bản mã gốc vào danh sách đen; đây không phải là vấn đề trong thực tế).
Hãy coi chừng rằng mật mã rất dễ uốn nắn. Điều này cho phép kẻ tấn công lật các bit mong muốn trong bản rõ bằng cách thay đổi các bit này trong bản mã. Đây có thể là một vấn đề thực tế. Một số mức độ giảm thiểu đó là có thể bằng cách thay thế $u\oplus\ldots$ qua Mã hóa bảo toàn định dạng với rộng hơn $u$ như chìa khóa; hoặc/và nhiều công việc hơn hoặc/và không gian.
Vòng lặp while khi mã hóa là sự đánh đổi thời gian/không gian, tìm kiếm $k$ bằng cách liệt kê để nó là $x$ Tọa độ $R_x$ có $b$ các bit bậc thấp ở mức 0 không cần truyền đi. Việc tìm kiếm được tối ưu hóa để yêu cầu $\approx2^b$ cộng điểm, nhưng đối với $b$ bắt đầu về $8$ điều này sẽ trở thành một nỗi đau. Sử dụng gia tăng bí mật $e$ và phù hợp $F=e\,G$ là một điều tốt đẹp để có được trận chung kết $k$ thống nhất hơn (xem ghi chú), nhưng tôi biết sẽ không có cuộc tấn công nào nếu chúng ta thực hiện $e=1$ và như vậy $F=G$. Gia tăng bí mật hơn nữa có thể giúp giảm thiểu các cuộc tấn công kênh phụ.
Nếu chúng ta muốn tránh một số hoặc tất cả sự đánh đổi thời gian/không gian đó, chúng ta có thể
- tầm thường, tăng kích thước bản mã.
- hoặc/và mạo hiểm tạo một đường cong tùy chỉnh, với kích thước bit là $n$ và $p$ giảm một vài bit từ 256. Đối với mỗi 1 bit bảo mật mà chúng tôi từ bỏ, chúng tôi nhận được khoảng 2 cho $n$ và $p$, do đó trên các bit bản mã hoặc phỏng đoán ít hơn 4 lần trong vòng lặp while. Và đối với secp256r1, các cuộc tấn công nổi tiếng nhất được cho là yêu cầu $>2^{140}$ hoạt động bit (dựa trên phép ngoại suy thận trọng của một phép toán tương tự yêu cầu của $>2^{140}$ cho Ed25519).
Chú ý: Trong giáo trình Diffie-Hellman hoặc ElGamal, ta chọn $k$ thống nhất trong $[0,n)$. biến thể của chúng tôi hạn chế để $k$ với $k\,G$ có một $x$ phối hợp với nó là bậc thấp $b$ bit ở mức không. Bằng một lập luận thống kê, có khoảng $n/2^b$ như là $k$. Chúng tôi muốn chọn $k$ thống nhất trong tập hợp con này của $[0,n)$. Đơn giản nhất sẽ được lặp lại cho ngẫu nhiên $k$, nhưng điều đó có chi phí tính toán cao cho phép nhân điểm $R\được k\,G$. Chúng tôi tiết kiệm điều này bằng cách di chuyển từ một ứng cử viên $k$ đến cái tiếp theo theo một mức tăng cố định $e$, cho phép cập nhật $R$ bằng một điểm cộng duy nhất $R\được R+F$.
Nếu chúng ta sử dụng cố định $e=1$, sau đó $k$ được chọn bởi vòng lặp while sẽ có một thuộc tính có thể phân biệt được (đối với một người biết $k$): xác suất để một $k$ được chọn tỷ lệ thuận với $j$ tính được từ $k$ như nhỏ nhất $j>0$ như vậy mà $k-j$ nằm trong tập con (hoặc $k+1$ nếu không có như vậy $j$, xảy ra cho một singe $k$ trong tập con). Vấn đề tương tự như sự lựa chọn không thống nhất của số nguyên tố thu được bằng cách chọn một điểm bắt đầu ngẫu nhiên và tìm kiếm số nguyên tố tiếp theo.
Chọn bất kỳ công cố định $e$ không giải quyết được vấn đề, bởi vì định nghĩa của $j$ có thể thích nghi với $k-e\,j$ trong tập hợp con. Tuy nhiên, việc chọn một bí mật ngẫu nhiên $e$ cho mỗi sự lựa chọn của $k$ làm. Một kỹ thuật tương tự được sử dụng trong các trình tạo số nguyên tố ngẫu nhiên cho RSA. Tôi không có tài liệu tham khảo, nhưng một lập luận là một đối thủ không biết $e$ không hiểu cái gì $e$ để sử dụng cho một bài kiểm tra; họ có thể kiểm tra tất cả $e$ và kết hợp các kết quả, nhưng sau đó bài kiểm tra của họ bị nhiễu.
Tôi đã chọn giới hạn trên của khoảng $[1,2^{32})$ vì $e$ sao cho phép tính $F\được e\,G$ có chi phí dự kiến cận biên so với $R\được k\,G$. Tôi tự tin (không có bằng chứng hoặc tài liệu tham khảo) điều này là quá đủ để tạo ra sự thiên vị trong việc lựa chọn $k$ thực tế không thể bị phát hiện ngay cả đối với những kẻ thù giả định biết $k$; và đối thủ thực sự chỉ có thể nhận được $k$ thông qua một kênh phụ.
Suy nghĩ cuối cùng: chúng ta có thể xoa dịu bất kỳ nỗi sợ hãi nào mà các tiêu chí $R_x\equiv0\pmod{2^b}$ tạo ra một điểm yếu bằng cách điều chỉnh nó thành: mức thấp $b$ một chút $R_x$ là một số chức năng (có phân phối đồng đều) của các bit khác của $R_x$. Một $b$-bit CRC sẽ làm được. Máy thu có thể tái tạo lại các bit bậc thấp cần thiết của $R_x$ bằng cách áp dụng chức năng này.
