Điểm:1

Trên một đường cong Elliptic, có thể nào từ $P$ chúng ta có thể biết liệu $a$ có phải là dư bậc hai modulo $N$ hay không?

lá cờ sr

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:

  1. Con số $a$ là số nguyên LẺ/CHẲNG.
  2. Con số $a$ LỚN HƠN/NHỎ HƠN một nửa thứ tự nhóm $N/2$.
  3. Con số $a$$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$
  4. 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$$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.

kelalaka avatar
lá cờ in
Nguồn gốc của câu hỏi này là gì? Điều gì có ý nghĩa trong (3)? Làm thế nào để bạn định lượng điều này? 1 và 2 giảm không gian xuống 1/4. Hiệu ứng của 4 không thể được nói một cách hoàn hảo nếu $N$ không được đưa ra.
Titanlord avatar
lá cờ tl
Bạn có thể giải thích (3)? Nếu đó là số một và số không trong một khóa, đây là một rủi ro nghiêm trọng.
PouJa avatar
lá cờ sr
@kelalaka Tôi đã cập nhật câu hỏi và cố gắng giải quyết các câu hỏi của bạn, vui lòng xem.
PouJa avatar
lá cờ sr
@Titanlord Nếu tôi cung cấp cho bạn khóa công khai $P$ của mình và cũng cho bạn biết rằng khóa riêng của tôi có $124$ và $130$ thì bạn có thể tính được khóa riêng của tôi không? Điều gì sẽ xảy ra nếu tôi không cho biết số lượng số 0 và số 1 mà chỉ cho biết tổng số tiền trong ví dụ này là $254$.
kelalaka avatar
lá cờ in
Tại sao một khóa riêng với nguồn ngẫu nhiên tốt lại gặp sự cố rò rỉ 3 bit, mong đợi (3), vẫn chưa rõ những thứ này bị rò rỉ như thế nào.
Điểm:1
lá cờ tl

Tác động đến an ninh từ 1 và 2 có thể được coi là không đáng kể. Giả sử bạn có bảo mật 256 Bit, điều đó ngụ ý $2^{256}$ các phím khác nhau để lựa chọn. Nếu bạn biết khóa là số lẻ, điều này được giảm xuống $2^{255}$ các phím khác nhau. Đối với 2 nó là tương tự.

Biết có bao nhiêu số một và số không có thể được coi là một rủi ro đáng kể. Giả sử bạn có một khóa 256 Bit chứa một khóa 1. Chỉ còn lại 256 khóa có thể. Điều này dẫn đến câu hỏi có bao nhiêu hoán vị. Đối với các số nhị phân có độ dài X cho trước và một số đã cho nếu N, điều này dẫn đến các số khóa, có thể được tính bằng cách sử dụng:

$$ number\ of\ keys=\frac{(X!)}{ (N! * (X-N)!)} $$

Trong trường hợp tốt nhất, điều này dẫn đến $\khoảng 2^{252}$ khóa có thể, cho 128 cái. Nhưng đối với một số lượng khác nhau, điều này chỉ trở nên tồi tệ hơn. Tấn công theo thời gian thường cố gắng tìm xem có bao nhiêu số 1 và 0 khác nhau (hoặc thậm chí cố gắng xác định vị trí của một số). Những cuộc tấn công thường là một vấn đề nghiêm trọng. Một số cuộc tấn công này đã cố gắng đoán số 1 bắt đầu của các phím đường cong elip, bởi vì một số thuật toán cũ có thời gian tính toán khác nhau tùy thuộc vào vị trí của số 1 hàng đầu. Đây không phải là rủi ro, ví dụ: 1 là bit đầu tiên hoặc bit thứ hai. Nhưng nếu người dẫn đầu ở vị trí $i$ an ninh sẽ giảm xuống $2^{256-i}$. Phụ thuộc vào $i$ đây có thể là một rủi ro đáng kể, đặc biệt nếu các khóa được chọn hoàn toàn ngẫu nhiên. Bạn chắc chắn không muốn những rủi ro này.

Đối với 4 tôi không chắc chắn. Tôi sẽ chỉnh sửa điều này, nếu tôi tìm thấy một câu trả lời hay.

PouJa avatar
lá cờ sr
Cảm ơn bạn đã trả lời. Bạn đã tìm hiểu về 4 chưa?
PouJa avatar
lá cờ sr
Bất kỳ cập nhật về 4?!
Titanlord avatar
lá cờ tl
Xin lỗi, tôi không thể chứng minh giả định của mình, nhưng tôi nghĩ nó sẽ không tạo ra sự khác biệt đáng kể. Tùy thuộc vào cài đặt, có thể đã có các thuật toán hiệu quả để có được kiến ​​thức đó.
PouJa avatar
lá cờ sr
Cảm ơn, bạn có biết bất kỳ thuật toán hiệu quả nào mà với một $P$ nhất định, nó có thể cho biết liệu $a$ có phải là dư lượng bậc hai cho một đường cong do bạn chọn không?

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.