Dezvăluirea lungimii mesajului original cu umplutură aleatoare

Dacă am un mesaj care are o lungime fixă ​​necunoscută $L$și adăugăm la criptarea TLS o umplutură de dimensiuni aleatorii $0\leq n \leq N$ deci mesajul trimis dacă $L+n$. De asemenea, pot face ținta să re-cripteze și să trimită mesajul din nou și din nou.

De câte ori trebuie să fac ca ținta să trimită mesajul din nou și din nou, până când dezvălui dacă lungimea inițială este $L$ sau $L+1$?

Cred că trebuie să-l fac să trimită măcar $N+1$ ori, așa că voi „acoperi” toate opțiunile de lungime a umpluturii, dar nu știu cum să continui de aici.

Presupunând că mesajul este cunoscut ca fiind lung $L$ sau $L+1$ și că lungimea de umplutură este distribuită uniform, atunci cu excepția cazului în care cifra este de lungime $L$ sau $L+N$ ambele lungimi ale mesajelor sunt la fel de probabile.

Întrebarea este atunci cât timp trebuie să așteptăm pentru a vedea un cifr de lungime distinctă.După cum s-a menționat în comentarii, acesta este un procesul Bernoulli cu parametru 1 USD/(N+1)$. Ca atare timpul de așteptare pentru un succes satisface a distribuție geometrică cu parametru 1 USD/(N+1)$.

Intuiția ta este corectă că timpul mediu de așteptare este $N+1$, dar trebuie să aveți grijă că distribuția geometrică are o coadă grea. De exemplu, șansa pe care ați putea avea nevoie să o examinați 2 N$ sau mai multe cifruri este despre $e^{-2}\aproximativ 0,135$ care este destul de mare. Dacă ai vrut să fii 95% sigur că vei vedea un cifr de lungime distinctă, ar putea fi necesar să te uiți la 3 N$ sau mai multe cifruri.