Tham gia Đăng nhập
Điểm:1
avatar Crypto

Sửa bài toán logarit rời rạc trong Zp bằng cách chọn tập con các phần tử nhóm

lá cờ do
Panos

Để cho $g$ máy phát điện của nhóm tuần hoàn $Z_p$ trật tự $p-1$, ở đâu $g$ có thể tạo tất cả các phần tử nhóm $\alpha \trong Z_p$ như $\alpha = g^x$chế độ$p$, $x \in (0..p-1)$, nơi bài toán logarit rời rạc khó, tức là tính toán $x= $đăng nhập$_ga$.

Giả sử chúng ta khởi tạo một hệ thống mật mã với các tham số trên (ví dụ: lược đồ mã hóa hoặc lược đồ chữ ký số), nhưng với việc sửa đổi chỉ xem xét các giá trị $x$ hợp lệ sao cho $\alpha < t$, ở đâu $t \in (0..p-1)$ một giá trị "mục tiêu". Theo trực giác, tính bảo mật của hệ thống này tương đương với hệ thống không có sửa đổi đó (tức là đưa ra yêu cầu rằng nó chỉ có thể sử dụng những $x$ sao cho kết quả $a$ nằm dưới mục tiêu), bởi vì kẻ tấn công vẫn cần phải brute-force tất cả $x$ không thỏa mãn điều này.

Tuy nhiên, câu hỏi của tôi là, điều này có mở ra bất kỳ cuộc tấn công lý thuyết số tiềm năng nào không? Ví dụ: liệu công việc của kẻ tấn công có thể được tăng tốc bằng cách sử dụng một số công thức toán học để loại trừ "không hợp lệ" $x$ và do đó trực tiếp làm giảm tính bảo mật của hệ thống mật mã?

88
0 + 0
kelalaka avatar
lá cờ in
kelalaka
Trước tiên, hãy đảm bảo rằng $p-1$ không gây ra cuộc tấn công của Pohlig-Hellman. Thứ hai, hãy tìm Pollard's Kangaroos, chúng hoạt động rất tốt trong phạm vi.
0
Hồi đáp
lá cờ do
Panos
Vì vậy, để Pohlig-Hellman hoạt động, $p-1$ cần phải là lũy thừa của một số nguyên tố, điều này cũng áp dụng cho các tham số ban đầu (tức là có vẻ như sửa đổi của tôi không bị ảnh hưởng bởi điều này). Thuật toán kangaroo có thể áp dụng cho sửa đổi của tôi, nhưng tôi vẫn không chắc nó có thể làm giảm tính bảo mật của vấn đề ban đầu như thế nào. Xem xét thuật toán trong https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm, ngay cả khi phạm vi hợp lệ của tôi (0,...t) là rất nhỏ (ví dụ: nếu t=1 là trường hợp cực đoan), thì kangaroo sẽ vẫn cần tính toán chuỗi số nguyên $d_0,... ,d_p$ đắt tiền, phải không?
0
Hồi đáp
fgrieu avatar
lá cờ ng
fgrieu
Về mặt tính toán, khó có thể khởi tạo một hệ thống mật mã giới hạn ở $x$ với $g^x\bmod p=\alpha
1
Hồi đáp
lá cờ do
Panos
Tôi đồng ý rằng việc đạt được $t$ đòi hỏi nỗ lực tính toán. Giả sử rằng $t$ đủ lớn để nỗ lực này nằm trong giới hạn hợp lý. Vì vậy, theo trực giác, tính bảo mật của hệ thống đã sửa đổi (tức là công việc vũ phu của kẻ tấn công cần thiết) sẽ là $p-t$, bởi vì kẻ tấn công biết $t$. Tôi chỉ đang cố gắng tìm hiểu liệu có bất kỳ cuộc tấn công lý thuyết số nào làm giảm mức bảo mật xuống dưới mức $p-t$ hay không. Kangaroo được đề cập ở trên dường như không phải là vấn đề với tôi.
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đă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.