Tiết lộ độ dài tin nhắn gốc có phần đệm ngẫu nhiên

Nếu tôi có một tin nhắn có độ dài cố định không xác định $L$và chúng tôi thêm vào mã hóa TLS của nó một phần đệm có kích thước ngẫu nhiên $0\leq n \leq N$ vì vậy tin nhắn đã gửi nếu $L+n$. Tôi cũng có thể mã hóa lại mục tiêu và gửi đi gửi lại tin nhắn.

Tôi cần bao nhiêu lần để khiến mục tiêu gửi đi gửi lại tin nhắn, cho đến khi tôi tiết lộ độ dài ban đầu là $L$ hoặc $L+1$?

Tôi nghĩ rằng tôi cần phải làm cho nó gửi nó ít nhất $N+1$ lần, vì vậy tôi sẽ "bao quát" tất cả các tùy chọn về độ dài của phần đệm, nhưng tôi không biết cách tiếp tục từ đây.

Giả sử rằng tin nhắn được biết là có độ dài $L$ hoặc $L+1$ và độ dài đệm được phân phối đồng đều, trừ khi mật mã có độ dài $L$ hoặc $L+N$ cả hai độ dài tin nhắn đều có khả năng như nhau.

Sau đó, câu hỏi đặt ra là chúng ta phải đợi bao lâu để xem một mật mã có độ dài phân biệt.Như đã lưu ý trong các ý kiến, đây là một quy trình Bernoulli với tham số $1/(N+1)$. Vì vậy, thời gian chờ đợi để thành công thỏa mãn một phân bố hình học với tham số $1/(N+1)$.

Trực giác của bạn là chính xác rằng thời gian chờ đợi trung bình là $N+1$, nhưng bạn nên lưu ý rằng phân bố hình học có phần đuôi nặng. Ví dụ, cơ hội mà bạn có thể cần kiểm tra $2N$ hoặc nhiều mật mã là về $e^{-2}\khoảng 0,135$ đó là khá lớn. Nếu bạn muốn chắc chắn 95% về việc nhìn thấy một mật mã có độ dài phân biệt, bạn có thể cần phải xem $3N$ hoặc nhiều mật mã hơn.