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

Độ phức tạp về thời gian của một cuộc tấn công vũ phu vào SSS Chia sẻ Bí mật của Shamir

lá cờ in
hambam

Tôi đã tìm kiếm khắp nơi trong các bài báo học thuật về độ phức tạp về thời gian của một cuộc tấn công vũ phu vào khóa Chia sẻ bí mật của Shamir. Tôi bối rối giữa nếu nó là $O(p^k)$ hoặc $O(p)$, như vậy mà $p$ là modulo mã hóa và $k-1$ là bậc của đa thức mã hóa. Bởi vì trên thực tế, nếu chúng ta định xây dựng lại đa thức mã hóa, thì điều đó tương đương với việc cưỡng bức tất cả $p$ các giá trị có thể cho $k$ hệ số, dẫn đến một $O(p^k)$ thuật toán. Nhưng tìm kiếm trực tiếp bí mật là hệ số không đổi của đa thức và biết rằng $S<p$, dẫn đến một $O(p)$ thuật toán. Ai đó có thể cho tôi biết cái nào đúng không, và nếu nó đúng $O(p^k)$, tại sao thuật toán tuyến tính không hoạt động?

127
1 + 0
Điểm:3
poncho avatar Crypto
lá cờ my
poncho

Tôi đã tìm kiếm khắp nơi trong các bài báo học thuật về độ phức tạp về thời gian của một cuộc tấn công vũ phu vào khóa Chia sẻ bí mật của Shamir.

Một cuộc tấn công vũ phu là không thể; ngay cả khi bạn có thể thực hiện bất kỳ tính toán tùy ý nào, với $k-1$ chia sẻ, bạn vẫn sẽ không nhận được bất kỳ thông tin bí mật nào (giả sử rằng tính ngẫu nhiên đã được sử dụng để tạo ra các chia sẻ; nếu chúng được tạo thông qua trình tạo số ngẫu nhiên xác định, thì bạn có thể).

Bởi vì trên thực tế, nếu chúng ta định xây dựng lại đa thức mã hóa, thì điều đó tương đương với việc cưỡng bức tất cả $p$ các giá trị có thể cho $k$ hệ số, dẫn đến một $O(p^k)$ thuật toán.

Không, ngay cả điều đó cũng không hiệu quả, bởi vì không có cách nào để xác định xem bạn đã tìm đúng đa thức hay chưa; đối với bất kỳ giá trị có thể có nào của bí mật, có một số lượng bằng nhau các đa thức phù hợp với nó. Do đó, bạn không nhận được thông tin nào (ngay cả thông tin xác suất) về bí mật.

0 + 5
hambam avatar
lá cờ in
hambam
cảm ơn vì câu trả lời nhanh ! nhưng tôi tìm thấy ở đây [link] (https://www.ijcaonline.org/archives/volume155/number13/kannan-2016-ijca-912051.pdf) rằng *Giá trị của p không được quá nhỏ nếu không nó có thể bị ảnh hưởng để tấn công vũ phu. Nếu giá trị của p là 128 bit thì điều này cung cấp 2^128 giá trị có thể, đây là một phạm vi quá lớn đối với lực lượng vũ phu từng thử*. Nó có nghĩa là gì sau đó?
0
Hồi đáp
Aman Grewal avatar
lá cờ gb
Aman Grewal
Nếu có cách nào đó để xác minh bí mật, nó có thể là brute-forced, nhưng đó không thực sự là tấn công SSS.
1
Hồi đáp
hambam avatar
lá cờ in
hambam
@AmanGrewal vậy điều đó có nghĩa là tấn công SSS tương đương với việc xây dựng lại đa thức được sử dụng trong mã hóa và không chỉ tìm lại bí mật?
0
Hồi đáp
poncho avatar
lá cờ my
poncho
@HamzaBa-mohammed: bình luận mà bạn tìm thấy là sai
1
Hồi đáp
poncho avatar
lá cờ my
poncho
@AmanGrewal: "nếu có cách nào đó để xác minh bí mật"; vâng, vâng, nếu bạn có thể tìm kiếm trong tất cả các giá trị bí mật có thể có và phát hiện ra giá trị nào là đúng, vâng, bạn có thể tìm hiểu nó. Tuy nhiên, bạn không sử dụng cổ phần; họ không cung cấp cho bạn bất kỳ thông tin nào mà bạn chưa có
3
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.