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

Xác định xem một chức năng có phải là PRG khi PRG nối với Seed không?

lá cờ bd
cryptonoob

Tôi là người mới sử dụng Mật mã học và gặp khó khăn khi giải quyết câu hỏi sau.

Để cho $G: \{0,1 \}^n \rightarrow \{0,1 \}^{l(n)}$ là một PRG và $x \epsilon \{0,1 \}^n$. Xác định xem hàm $Z: \{0,1 \}^n \rightarrow \{0,1 \}^{(l(n)+n)}$ s.t. $Z(x) := G(x)||x$ cũng là một PRG.

Giả định đầu tiên của tôi là nó là PRG, bởi vì phép nối của PRG Đầu ra G(x) dưới dạng chuỗi giả ngẫu nhiên với Chuỗi x ngẫu nhiên được phân phối đồng đều cũng là một chuỗi ngẫu nhiên. Do đó, nó cũng không thể được phân biệt bởi một đối thủ. Hơn nữa l(n)+n > n nên Expansion cũng ok.

Làm thế nào tôi có thể chứng minh điều đó? Ý tưởng của tôi là Giảm rằng nếu có một bộ phân biệt D phá vỡ Z(x) thì G(x) cũng sẽ phá vỡ G(x) với xác suất không âm, điều này mâu thuẫn với giả định ban đầu rằng G(x) là một PRG.

Tôi đang đi đúng hướng hay hoàn toàn lạc lối?

223
0 + 6
Maarten Bodewes avatar
lá cờ in
Maarten Bodewes
Vì vậy, hàm Z của bạn đang xuất hạt giống cùng với các giá trị ngẫu nhiên được lấy từ nó? Thuật toán cũng được biết đến.
1
Hồi đáp
cryptonoob avatar
lá cờ bd
cryptonoob
@MaartenBodewes Vâng, chính xác. Nhưng ý của bạn là gì với "thuật toán cũng được biết đến"? G ist không được chỉ định thêm. Do đó, nếu tôi cần đưa ra một phản ví dụ cho trường hợp Z không phải là PRG, tôi có thể thiết kế G theo bất kỳ cách nào tôi muốn.
0
Hồi đáp
Maarten Bodewes avatar
lá cờ in
Maarten Bodewes
Không, điều này thường không đúng. Chúng tôi thường giả định nguyên tắc của Kerckhoff: mọi bảo mật không nằm trong thuật toán mà nằm trong khóa hoặc - trong trường hợp này - hạt giống. Bạn có thể thiết kế $G$ theo cách bạn muốn, nhưng bạn nên cho rằng bất kỳ đối thủ nào cũng biết thuật toán. Nói cách khác: bạn không thể cho rằng $G$ tạo ra bất kỳ bí mật nào ngoài hạt giống $x$. Bây giờ điều gì sẽ xảy ra nếu trước tiên bạn tạo một khóa và sau đó là IV bằng cách sử dụng $Z$?
0
Hồi đáp
SEJPM avatar
lá cờ us
SEJPM
Gợi ý: Có lẽ có một số loại kiểm tra/phân biệt có thể kiểm tra xem một chuỗi tìm kiếm ngẫu nhiên đã cho đến từ $Z$ hay chỉ là ngẫu nhiên? Giả sử đối thủ cũng có thể tính $G$.
2
Hồi đáp
cryptonoob avatar
lá cờ bd
cryptonoob
@MaartenBodewes Ý tưởng duy nhất mà tôi có là kẻ thù có thể lấy khóa/hạt giống từ đầu ra của Z bằng cách thực hiện cắt (vì kẻ thù biết thuật toán và biết rằng khóa có độ dài n). Sau đó, anh ta có thể nhập "chìa khóa" này vào hàm và kiểm tra xem nó có giống đầu ra hay không. Theo như tôi biết, PRG mang tính quyết định. Và trong trường hợp này, anh ta thậm chí còn biết chìa khóa. Đi đúng hướng?
0
Hồi đáp
Maarten Bodewes avatar
lá cờ in
Maarten Bodewes
Vâng, đó là con đường đúng đắn. Nói chung, không thể lấy được trạng thái của RNG vì nó sẽ làm rò rỉ thông tin về tất cả các byte khác trong luồng.
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.