Khóa công khai RSA không có kiến ​​thức

Giả sử Bob có $k>1$ khóa công khai RSA $(e_i, n_i)$ mà không có bất kỳ kiến ​​thức nào về các khóa riêng tư tương ứng của họ. Alice cũng có tất cả các khóa công khai, nhưng cũng có một khóa riêng cho chỉ một trong số họ, chẳng hạn, $(d_j, n_j)$. Liệu cô ấy có thể chứng minh với Bob rằng cô ấy có ít nhất một trong các khóa riêng mà không tiết lộ $j$

CHỈNH SỬA: đã thay đổi ký hiệu theo đề xuất của fgrieu

Đây là một đề xuất (ra khỏi đầu của tôi). Bức tranh lớn

• Bob rút ngẫu nhiên $X$và gửi nó được mã hóa xác định dưới mỗi khóa công khai
• Alice giải mã $X$ với khóa công khai mà cô ấy nắm giữ
• Alice kiểm tra Bob đã làm như mong đợi với điều đó $X$
• Alice tiết lộ $X$ gửi Bob

Chính xác hơn:

• xác định một $8b$băm -bit (giả sử SHA-512) sao cho $\min(n_i)>2^{16b}$
• Xác định chức năng tạo mặt nạ (chẳng hạn như MGF1 với hàm băm đó) để cho bytestring $X$, $\operatorname{MGF}(X,\ell)$ là một $\ell$-byte băm của $X$
• Xác định độ dài byte $\ell_i=\left\lfloor\log_2(n_i)/8\right\rfloor$, đó là như vậy mà $2^{8\ell_i}<n_i<2^{8\ell_i+8}$ (để tránh các cuộc tấn công theo thời gian, điều mong muốn là $n_i$ có cùng kích thước bit, do đó $l_i$ công bằng)
• Bob rút ngẫu nhiên $X\in\{0,1\}^{8b}$ (một $b$-byte chuỗi byte)
• Cho mỗi $i$, Bob
  • tính toán $M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$
  • tính toán $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$ (một $l_i$-byte chuỗi byte)
  • tính toán và đầu ra $C_i={X_i}^{e_i}\bmod n_i$
• Alice được $C_i$, bao gồm $C_j$
• Alice tính toán $f={C_j}^{d_j}\bmod n_j$
• Alice bày tỏ $f$ dưới dạng chuỗi byte $M\mathbin\|G$ với $M$ của $l_i-b$ byte và $G$ của $b$ byte.
• Alice hồi phục $X$ bằng máy tính $X=G\oplus H(M\mathbin\|J)$
• Cho mỗi $i$, Alice
  • tính toán $M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$, ở đâu $I$ là chỉ mục $i$ như một chuỗi byte.
  • tính toán $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$ (một $l_i$-byte chuỗi byte)
  • Séc ${X_i}^{e_i}\bmod n_i=C_i$ (khi nào $i=j$, cái này kiểm tra $M=\operatorname{MGF}\bigl(X\mathbin\|H(n_j),l_j-b\bigr)$ như một tác dụng phụ)
• Chỉ khi tất cả các kiểm tra được thông qua và không tiết lộ (ví dụ: theo thời gian) nơi xảy ra lỗi nếu có hoặc lỗi nào $X_i$ đã được sử dụng để phục hồi $X$
  • Alice tiết lộ $X$
• Bob kiểm tra Alice tiết lộ đúng $X$

lý do:

• Alice chứng minh rằng cô ấy có thể giải mã một trong những mật mã $C_i$, do đó cô ấy giữ một khóa riêng
• Cô ấy không tiết lộ cái nào, vì cô ấy đã xác minh tất cả các mật mã đều giống nhau $X$. Không có nguy cơ sai lệch trong các bit bậc cao ở một số lượng trong $[0,n_j)$ có thể mang lại lợi thế trong việc đoán $j$ (như có thể là trường hợp trong một triển khai ngây thơ của câu trả lời khác).
• đại diện $X_i$ của $X$ được lan truyền trên $[0,n_i)$ như trong RSASSA-OAEP, với các chức năng đệm độc lập. Lưu ý rằng việc mã hóa trực tiếp $X_i=X$, hoặc $X_i=F(X)$ cho một số tiêm cố định $F$, sẽ khiến hệ thống dễ bị tấn công Cuộc tấn công phát sóng của HÃ¥stad; hơn nữa, không thể xác định chiều rộng chung an toàn cho $X_i$, ví dụ. nếu $n_0$ là 2048-bit, $n_1$ 8192-bit, $e_1=3$; phần đệm giải quyết điều đó.
• Từ $X$ là một thử thách do Bob đưa ra, giao thức này không bị lặp lại: Alice không thể thoát khỏi dữ liệu mà cô ấy đã tính toán trước trước khi mất quyền truy cập vào khóa riêng tư của mình hoặc dữ liệu được tính toán trước đó bởi Amanda, người cũng nắm giữ khóa riêng tư.

Những cải tiến có thể có để bảo vệ Alice khỏi trở thành một nhà tiên tri giải mã, Bob khỏi việc điều chỉnh nó $X$, và có lẽ làm cho một bằng chứng dễ dàng hơn:

• Alice lần đầu tiên vẽ $b$-byte $Y$ và gửi cam kết $H(Y\mathbin\|S_0)$
• Bob vẽ nó $b$-byte $X$ và gửi cam kết $H(X\mathbin\|S_1)$
• Alice tiết lộ $Y$, Bob kiểm tra lại $H(Y\mathbin\|0)$
• giao thức trên được sửa đổi
  • nó được sử dụng $M_i=\operatorname{MGF}\bigl(X\mathbin\|Y\mathbin\|H(n_i),l_i-b\bigr)$
  • nó được sử dụng $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|Y\mathbin\|H(n_i)))$
  • Alice kiểm tra thêm $H(X\mathbin\|1)$ diêm
  • Alice tiết lộ $H(X\mathbin\|S_2)$ còn hơn là $X$
  • Bob kiểm tra điều đó. (ở đâu $S_i$ là các chuỗi phụ ngắn không trống tùy ý riêng biệt)

Cập nhật: Một phương pháp khác, được nêu trong câu trả lời khác này, là sử dụng một Chữ ký vòng dựa trên RSAvà yêu cầu Alice chứng minh cho Bob thấy khả năng ký vào một thông báo thách thức của cô ấy.