54

случайно, равновероятно и независимо друг от друга. Каково должно быть значение n, чтобы такая пара появилась с большой вероятностью?

Обозначим |Аl | = N и пусть р – вероятность того, что имеется пара сообщений Mi и Mi' таких, что H(Mi ) = H(Mi' ), то есть вероятность

успешной атаки. Нам проще вычислить вероятность противоположного события, то есть, что в (1) нет такой пары.

N N − n

2

n

(N − n)!n!(N − n)1

[(N − n)!]

1 – p =

n

=

=

.

(2)

N N

n!(N

− 2n)!N!

N!(N − 2n)!

n n

Условия, налагаемые на n, при которых вероятность (2) мала,

приводятся в следующей теореме.

n2

Теорема. Пусть N, n → ∞, но

→ t >0, тогда

N

р = (1 - e −t ) (1 + ο(1)).

Д о к а з а т е л ь с т в о.

Используя формулу Стирлинга, получим:

1 – p =

[(N − n)!]2

=

[(N − n)N −n e−N +n

2π(N − n)]2 (1+ο(1))

=

N!(N −

2n)!

N N e−N 2πN (N − 2n)N −2n e−N +2n 2π(N −

2n)

(1−

n

)

2N −2n

=

N

(1+ο(1)).

(1−

2n

)

N −2n

N

Отсюда, используя разложение логарифма в ряд, получим

ln( 1-p) = [(2N-2n)ln(1-

n

) – (N-n)ln(1-

2n

)](1+ ο(1)) =

n2

N

n3

N

2n2

= [(2N-2n)( -

n

-

+ O(

)) - (N-n)( -

2n

-

+

N

2N

2

N 3

N

N 2

n3

n2

+ O(

)](1+ο(1)) = -

(1+ο(1)) = -t (1+ο(1)).

N 3

N

Таким образом,

1 - р =

e −t (1 + ο(1)),

и

р = (1 - e −t ) (1 + ο(1)),