Các cuộc tấn công đa mục tiêu của khóa công khai ECC

Liệu kẻ thù có thể tìm thấy một trong những khóa riêng phù hợp với chi phí thấp hơn nhiều so với việc tìm khóa riêng cho một khóa cụ thể không?

Không, và điều đó có thể chứng minh được (và không phụ thuộc vào công nghệ được sử dụng)

Giả sử rằng chúng ta có một hộp đen có thể lấy $k$ khóa công khai khác nhau $a_1G, a_2G, ..., a_kG$, và phục hồi $a_iG$ (đối với một số $i$) Trong $o(\sqrt{n})$ thời gian.

Sau đó, đây là cách chúng ta có thể sử dụng hộp đen đó, được cung cấp một khóa công khai $aG$, khôi phục khóa riêng $a$ Trong $o(\sqrt{n})$ thời gian. Chúng tôi sẽ:

• Lựa chọn $k$ giá trị ngẫu nhiên $r_1, r_2, ..., r_k$, và tính trình tự $r_1(aG), r_2(aG), ..., r_k(aG)$, mà (bằng cách xác định $b_i = r_i a$) có thể xem như $b_1G, b_2G, ..., b_kG$

• Đưa ra trình tự $b_1G, b_2G, ..., b_kG$, sẽ phục hồi $b_i$

• chúng tôi tính toán $a = r_i^{-1}b_i$, và do đó khôi phục khóa.

Các bước ngoài việc gọi hộp đen thực hiện $O(k)$ thời gian, có thể bỏ qua đối với kích thước hợp lý $k$.

Lưu ý rằng trình tự $b_1G, b_2G, ..., b_kG$ được phân phối đồng đều và do đó, ngay cả khi hộp đen là xác suất, thì nó vẫn cho phép chúng tôi khôi phục khóa chung.