Hãy tưởng tượng rằng, Trên sơ đồ mật mã Đường cong Elliptic nơi $P=a\lần G$, Bob chia sẻ khóa công khai của mình $P$ với Eve (con quỷ muốn biết những bí mật mà anh ta không được phép biết). Bob cũng đã tiết lộ một manh mối về $a$ vô tình. Đầu mối có thể là một hoặc kết hợp các mục từ danh sách sau:
- Con số $a$ là số nguyên LẺ/CHẲNG.
- Con số $a$ LỚN HƠN/NHỎ HƠN một nửa thứ tự nhóm $N/2$.
- Con số $a$ có $x$ các bit có ý nghĩa khi được viết dưới dạng nhị phân. (ở đó $x$ là số bit của $a$, ví dụ nếu $a=152=10011000$ sau đó $x=8$
- Con số $a$ là modulo DƯ/NON-RESIDUE bậc hai $N$.
Câu hỏi 1:
Việc biết về manh mối như vậy có được coi là một điểm yếu đáng kể đối với khóa công khai của Bob để chúng ta có thể nói rằng việc sử dụng nó không còn an toàn nữa không?
Câu hỏi 2:
Manh mối đề cập ở trên là rất ít thông tin về $a$ Tôi giả sử. Tôi có đúng không? Điều gì sẽ xảy ra nếu chúng ta có thể tiết lộ chúng cho tất cả các điểm trên đường cong bằng cách sử dụng một thuật toán kỳ diệu?
Tôi biết rằng, đối với các mục 1-3, kiến thức về một thuật toán chung cho bất kỳ mục nào $P=a\lần G$ nó có thể cho chúng ta biết chắc chắn rằng $a$ là LẺ/CHẲNG hoặc $a$ LỚN HƠN/NHỎ HƠN so với $N/2$ hoặc $a$ có $x$ các bit sẽ phá vỡ hoàn toàn tính bảo mật của Đường cong Elliptic và nhờ đó có thể truy xuất $a$ từ $P$.
Nhưng còn mục 4 thì sao? Ý tôi là nếu một người có thể khám phá ra một thuật toán mà nhờ đó họ có thể xác định thuật toán đó cho bất kỳ $P$, $a$ là hoặc không phải là dư lượng bậc hai modulo $N$, liệu họ có thể lấy lại hoàn toàn $a$ và phá vỡ sơ đồ mật mã?
Điều gì sẽ xảy ra nếu thuật toán cũng có thể cho biết căn bậc hai của $a$ modulo $N$?
Cập nhật 1:
Những câu hỏi này nảy sinh khi tôi đang nghiên cứu về rủi ro cơ sở dữ liệu khóa riêng bị xâm phạm một phần. Đó là điều sẽ xảy ra nếu kẻ tấn công biết manh mối về khóa riêng của chúng tôi.