Une formule de dénombrement servant en cryptographie

pp. 405-412 405

Robert C O H E N *

Marc G I R A U L T **

Mireille C A M P A N A *

Une formule de d6nombrement servant en cryptographie

R6sum~

On dtudie la probabifitd que deux dchantillons tir6s avec remises posskdent une intersection constitute de i ~ldments distincts exactement. La formule obtenue 6tend un r~sultat connu sous le nom de <~ paradoxe des jumeaux ~> et qui sert dans un problOme d'attaque de messages sign,s en cryptographie.

Mots cl6s : Cryptographie, Authentification, Calcul proba- bi'it6, Comportement asymptotique.

A PROBABILITY FORMULA SUITABLE FOR CRYPTOGRAPHY

Abstract

We study the probability that two independent samples drawn with replacements contain exactly i common elements. The obtained formula extends a result known as the << birthday paradox >>, and is used to attack signed messages in cryptography.

Key words : Cryptography, Authentication, Probability calculus, Asymptotic behaviour.

Sommaire

I. Introduction.

II. Rappels et notations.

IlI. Calcul de la probabilitd.

IV. Etudes asymptotiques.

V. Rdsultats num~riques.

VI. Conclusion.

Bibliographic (8 r~f ).

I. I N T R O D U C T I O N

La cryptographie, d6finie ici et lb. comme la science (l 'art ?) des messages secrets, permet d 'assurer la confidentialit6 et l'authenticit6 des messages sensibles, transmis b. travers d~.s syst~mes de t616communications, au moyen d'algorithmes param6tr6s par des cl6s. La confidentialit6 est assur6e en chiffrant les messages, ce qui les rend incompr6hensibles b. qui ne d6tient pas la c16 (secrete) de d6chiffrement. L'authenticit6 est assur6e en signant 61ectroniquement les messages, b. l 'aide d 'une c16 (secrete) de production de signature, puis en adjoignant au message sa signature.

Afin de justifier son appellation, il est n6cessaire qu'une signature 61ectronique puisse ~tre v6rifiable par tout le monde mais imitable par personne. C'est seulement en 1977, date d 'appari t ion des algorithmes cryptographiques b. cl6s publiques [1], qu 'on a pu d6finir de telles signatures. Elles sont le plus souvent calcul6es en deux temps. Tout d 'abord, le message M est condens6 de faqon b. en obtenir une image m aussi caract6ristique que possible [2]. Ensuite, on applique b. cette image un algorithme S (par exemple Rivest, Shamir, Adleman [3]) param6tr6 par une c16 secrete K connue du seul signataire. On obtient ainsi une signature Sk(m) courte, d6pendant b. la fois du texte et de son signataire, inimitable et v6rifiable par tous.

La phase de condensation n'est pas uniquement motiv6e par le d6sir d 'obtenir une signature aussi courte que possible (afin de ne pas trop allonger le message). Le d6faut des algorithmes b. cl6s publiques r6side dans leur lenteur d'ex6cution. Aussi est-il hors de question de les mettre directement en oeuvre sur des messages autres que tr~s courts. Ceux-ci devront donc ~tre pr6alablement condens6s.

Cette condensation dolt &re effectu6e avec pr6cau- tion. En effet cette premiere phase de la production de signature n'6tant - - elle - - param6tr6e par aucune c16, il est primordial que l 'obtention de messages distincts ayant m~me image soit, en pratique, une

* CIqET/PAA/TIM, 38-40, rue du g6n6ral Leclerc, 92131 Issy-les-Moulineaux, France. ** SEPT/PEM, 42, rue des Coutures, BP 6243, 14066 Caen Cedex.

1/7 ANN. TELI~COMMUN., 44, n ~ 7-8, 1989

406 R. C O H E N . - FORMULE DE DI~NOMBREMENT SERVANT EN C R Y P T O G R A P H I E

tfiche quasi impossible, y compris pour qui disposerait d 'un parc important de superordinateurs. Imaginons en effet que Barbara ait produit une signature du message M, et qu'elle envoie son message sign6 ~t Casimir. Si le fraudeur Achille a trouv6 un message M' ayant m~me condens6 que M, il pourra en toute impunit6 substituer M' 5. M sur la ligne de commu- nication, puisque ces deux messages ont m~me signa- ture [4].

Un certain nombre d'attaques g6n6rales ont 6t6 r6pertori6es, qui permettraient 5. un fraudeur, astucieux et 6quip6, de fabriquer de tels messages-fr6res. Plusieurs d'entre elles (attaque de Yuval [5], attaque dite dans le milieu [6], etc.) reposent sur le paradoxe des jumeaux et ses variantes. Rappelons comment s'6nonce ce c616bre paradoxe : soit r l'effectif d 'une classe et soit p(r) la probabilit6 qu 'au moins deux 616ves de cette classe f~tent leur anniversaire le m~me jour ; quelle est la valeur minimale de r pour laquelle p(r) > 0,5 ? La r6ponse est 23, r6sultat nettement inf6rieur ~ celui que sugg~re g6n~ralement l'intuition.

En fait, les attaques mentionn6es reposent plutSt sur la variante suivante du paradoxe des jumeaux : soient deux classes de m~me effectif r, et soit p(r) la probabilit6 que deux 616ves n'appartenant pas ~. la m~me classe f~tent leur anniversaire le m~me jour ; quelle est la valeur minimale de r pour laquelle p(r) > 0,5 ? La r6ponse est r = 16 mais le calcul est cette fois plus compliqu6, du fait que chacune des classes est susceptible de contenir elle-m~me des jumeaux.

Cet article propose une 6tude math6matique pr6cise des paradoxes mentionn6s. Apr6s quelques rappels et notations (section II), on calcule la probabilit6 de trouver i ~< coincidences >> dans deux 6chantillons d'effectifs r et s pr61ev6s dans une population de taille n (section III). Le comportement asymptotique est ensuite analys6 dans les cas qui nous int6ressent, c'est-5.-dire ceux oh le nombre de coincidences est faible : les attaques cryptographiques 6voqu6es plus haut sont gagnantes d6s lors qu'une coincidence au moins a 6t6 d6tect6e (section IV). C'est ainsi que la loi-limite s'av6re ~tre une loi de Poisson lorsque r et s sont de l 'ordre de la racine carr6e de n. Ceci permet d'6valuer avec pr6cision l'efficacit6 des attaques cryptographiques 6voqu6es plus haut. Pour terminer, les formules obtenues ont 6t6 programm6es, et des r6sultats num6riques sont donn6s h titre d'exemples (section V).

II. RAPPELS ET NOTATIONS

Pr6cisons d 'abord quelques notations :

- - E, est la notation pour un 6chantillon de taille r (avec ou sans remises),

- - Igl repr6sente le cardinal de l'ensemble E,

- - C ~ d6signe le coefficient binomial, 6gal ~t: n!/(n - - k)! k!,

- - soit Q(x, y) une quantit6 d6pendant de x et y. Soit C un ensemble de conditions aux limites portant sur x et y. On appelle s de Q(x, y), not6e s Q(x, y), la limite de Q(x, y) quand les conditions de C sont satisfaites.

Rappelons que : - - dans le cas discret, et quand toutes les confi-

gurations sont 6quiprobables, la probabilit6 P(E) d 'un 6v6nement E s'obtient en calculant le rapport du nombre N(E) de configurations favorables 5. la r6a- lisation de l'6v6nement E au nombre N de configura- tions possibles : P(E) = N(E)]N;

- - les valeurs de N sont tir6es selon une loi de Poisson de param6tre Z, not6e Sz , si la probabilit6 de sortie de l'entier k est 6gale h Yx(k) ---- e -x Zk]k! ;

- - la fonction de r6partition au point 0~ d 'une loi de Poisson de param6tre Zes t not6e Yz(00, et vaut :

~-z(~) = ~. e -z Zk/k! ; k=O

- - pour n 6v6nements A1 . . . . . An, on a la formule de Poincar6 :

n

P( u Ak) : k = l

E ( - - 1) k-* P(A,, c~... c~A,.k). k = l l<~i i< . . .< tk<.n

Si P(At~c~... n A~k ) ne d6pend pas des indices eux-m~mes, mais seulement du nombre d'indices, le nombre de termes 6gaux h cette quantit6 est C k, et la formule s'6crit :

P( tj Ak) = ( - - 1) k-~ C~ P(A~ c~... c~Ak). k = l k = l

Pour plus de d6tails sur des questions de probabilit6, le lecteur int6ress6 pourra consulter [7], [8].

D~finition 1. Lorsque l 'on proc6de ~ des tirages avec remises dans une population de taille n, on appellera nombre de coincidences la diff6rence entre le nombre de tirages et le nombre d'individus distincts tir6s.

IlL CALCUL DE LA PROBABILITI~

Dans l'6tude qui suit, on suppose que l'ensemble {1, ..., n}, duquel sont tir6s les 6chantillons, est muni de la loi uniforme.

Thdor~me 1. On proc6de au tirage d 'un premier 6chantillon Er avec remises de r individus b. partir d 'une population de taille n. On proc6de ensuite au tirage d 'un second 6chantillon Es avec remises de s individus ~t partir de la m~me population de taille n. La probabilit6 P(n, r, s, i) que i individus exactement fassent partie des deux 6chantillons vaut :

r--l s - i

5", E P({IE, c~E~[ = i}/{]E,[ = r - - k} n(IE, I = s - - I ) ) k=O l = 0

P({IEr[ = r - - k}) P({IE,[ = s - - l}).

ANN. TI~L~COMMUN., 44 , rl ~ 7-8 , 1989 2 /7

R . C O H E N . - F O R M U L E D E D I ~ N O M B R E M E N T S E R V A N T E N C R Y P T O G R A P H I E 407

D~monstration. La probabilit6 que l ' intersection des deux 6chantillons soit constitu6e de i individus (distincts) exactement se calcule par condi t ionnement : P(n, r, s, i) - -

r - i s - i

a ( w u {IErl = r - - k, IE, I = s - - ;, [ErnE~l = i } ) k = 0 1 = 0

probabilit6 d ' avo i r i individus distincts exactement dans l ' intersection de deux 6chantillons ind6pendants tir6s sans remise, de tailles respectives r et s.

III.2. Calcul de Q.

r - - i s - - i

: X X P ( ( IL [ : = s - - l } ) x k = O I = O

P({IErc~E~I =/)/{ILl = r - - k) {IE l s - - t))

r - i s - i

= X X P(IErl ~ r - - k ) P ( I E = l : s - - I ) • k = O / = 0

P({[ErnE~[ = / ) / { I L l = r - - k ) ~ ( I E ~ l =

la derni6re 6galit6 ayant lieu car les tirages sont ind6pendants. D ' o h "

r - i s - i

P ( n , r , s , i ) = ~ ~. Q(n ,r ,k ) k = O l = O

H(n, r - - k, s - - I, i) Q(n, s, l),

o/a Q(n, r, k) = P([Erl = r - - k) repr6sente la pro- babilit6 d ' avo i r k coincidences dans l '6chantillon avec remises de r individus extraits d 'une populat ion de taille n, et H(n, r - - k, s - - l, i) = P(I{Er l = i}[ {lEt] = r - -k} c~{IE, I = s - - / } ) repr6sente la probabilit6 que i individus distincts exactement aient 6t6 tir6s dans les deux 6chantillons (ind6pendants tir6s avec remises, de tailles respectives r et s) ayant respective- ment r - - k et s - - l individus distincts.

1II.1. Calcul de H.

Proposition 1. La probabilit6 H(n, r, s, i) que i individus exactement fassent partie de deux 6chantil- lons Er ayant r individus distincts, et E~ ayant s individus distincts, v a u t "

C._r/C.. D#monstration. Nous disposons de deux ensembles

E, et E~ de cardinaux r et s respectivement. La pro- babilit6 d ' avo i r i individus dans leur intersection se calcule en choisissant les i individus parmi les r du premier 6chantillon, ce qui se fait de C~ faqons, et s - - i individus parmi les n - - r restants, ce qui se fait de ~-~ C,_r faqons , on divise ensuite par le nombre total, C,], de sous-populations de taille s qu ' i l est possible d 'extraire de {1 . . . . , n} muni de la loi uni- forme, sans contrainte. On a finalement :

s - i s H(n, r, s, i) = C] C,_dC, .

I1 s 'agit donc d 'une loi hyperg6om6trique [7], [8].

Remarques.

1) En particulier la probabilit6 en z6ro vaut : (n - - r)! (n - - s) !

n! ( n - - s - - r ) !"

2) Par d6finition de la loi hyperg6om6trique, H ( n , r, s, i ) s 'interpr~te encore comme la

Proposition 2. On proc6de au tirage avec remises d ' u n 6chantillon Er de r individus h partir d 'une populat ion de taille n. La probabilit6 Q(n, r, c) que c coincidences aient lieu dans l '6chantillon vaut :

C , ' - c r! Q(n, r, c) - Z

nr (~1 ..... ~r-c),o~ cq!.., err-c!"

D~monstration. Pour calculer la probabilit6 Q(n, r, c) on 6value le nombre de configurations favorables q u ' o n divise par le nombre de configurations possibles. S i r > ~ n e t c < r - - n a l o r s Q ( n , r , c ) - - - - 0 . S i r ~<n, ou si r >~ n e t c ~> r - - n, alors on peut tenir le raison- nement suivant :

- - le nombre d'6chantil lons de taille r avec remises q u ' o n peut tirer dans une populat ion de n individus est de n r,

- - on choisit les r - - c individus (distincts) parmi les n de C~ -C faqons,

- - pour l e s c coincidences, on choisit I ~1 616ments parmi les r de l '6chantillon identiques h l ' individu n ~ 1, puis ~z parmi les r - ~1 restants identiques l ' individu n ~ 2, etc. j u squ ' au tirage des r - - c individus distincts de l '6chantillon. II y a donc

~1 ~ 2 . .* Cr Cr ~ C~'__~ . . . . . ~ , _ _ , choix possibles pour chaque (r - - c)-uplet de l 'ensemble :

r - - c

- ~ = {(~, . . . . . ~r-c) 6 N r - ~ , % ~> 1, E ~s = r}. j = l

Apr~s simplification, le produit de ces coefficients binomiaux vaut :

r!

Le nombre de configurations favorables s 'obt ient en sommant sur t ous l e s (r - - e)-uplets de l 'ensemble ~ , ainsi d6fini. On a donc la formule annone~e.

Remarques.

1) La probabilit6 de tirer r individus (distincts) au cours des r tirages se calcule facilement : il y a n r configurations possibles, et le nombre de configu- rations favorables est de n(n - - 1) . . . . . ( n - r + 1). Soit :

n! Q(n, r, 0) -

(n - - r)! n r

Dans le cas du ~ bir thday paradox )), cette formule permet de d6terminer le nombre r d'61~ves : pour n ---- 365, r = 23 est le plus petit entier tel que :

Q(365, r, 0) > 0,5.

En utilisant comme dans [7] la formule de Poincar6, on obtient une formule qui permet une p rogrammat ion

3/7 ANN. TI~L~COMMUN., 44, n ~ 7-8, 1989

408 R. C O H E N . - F O R M U L E D E D I ~ N O M B R E M E N T S E R V A N T E N C R Y P T O G R A P H I E

plus facile. D6signons par Ak l '6v6nement << l ' individu k n 'est pas tir6 >). Alors l '6v6nement ~< r - - c individus dans l '6chantillon E~>> s'6crit :

{]Er] = r - - c} :

Q r--c n ) def .

c ~ ~ A i j : L3 B p w c~ A~j {il ..... l,}~,D- ~ j=l j = r - c + l pefs ~

o/l ~,_ ~ est l 'ensemble, de cardinal Cg -~, des parti- tions de {1 . . . . . n} en ensembles de r - - c, et n - - r + c individus. C o m m e l '6v6nement Bp est disjoint de Bq pour toute part i t ion q qui diff&e de p par au moins un indice entre les r - - c premiers et n - - r + c 616- ments suivants, la probabilit6 de la r6union est 6gale

la somme des probabilit6s des P(Bp). En utilisant P (AmB) = P(A/B) P(B), on a :

e t r - c / , ) r X P(Bp) = n A~j ~ Aij j = l I j = r - - c + l

P r ( ( j = r ~ _ c + l A ' J ) ) "

Le calcul du second terme est facile ; le premier terme se caicule en utilisant la formule de Poincar6 car :

( , -col, , ) P c~ A 0 c~ Al~ = \ j = l I j = r - - c + l /

1 - Pr w A O n A,~ �9 \ j = l [ j = r - - c + l

Cette probabilit6 ne d6pendant pas de la parti t ion p, on obtient alors :

Cr--c r- -c n Q(n, r, c ) - n~ Z ( - - 1) ~ C ~ - c ~ ' .

0~=O

Cette formule diff6re de celle de [7] car les d6fini- tions des coincidences ne sont pas les m~mes.

IV. I~TUDES A S Y M P T O T I Q U E S

On d6sire connaitre le compor tement asymptot ique de la probabilit6 obtenue dans le cas avec remises pour deux raisons. On cherche d ' une part b. savoir sous quelles conditions et vers quoi la probabilit6 du cas avec remises converge, d ' au t re part h 6valuer une approximat ion des probabilit6s pour obtenir des r6sultats num&iques.

Sous les conditions qui nous int6ressent, il est bien connu que la limite de la loi H est une loi de Poisson de param6tre v = lim rs[n. Cependant, nous

n, r.s--~ + O0 aurons besoin d ' u n r~sultat plus pr6cis : nous obte- nons des bornes sur H en fonction de sa loi limite, ainsi que des bornes sur la fonction de r6partition de H en fonction de celle de la loi de Poisson de param~tre v.

L '6tude du compor tement asymptot ique de Q est faite sous deux conditions sur la limite du rappor t r]n (d ' abord r ~ n, puis r >> n). On montre que sous

certaines conditions, Q converge vers une loi de Poisson de param6tre X ---- lim r2[2n, et nous

r . ~--~ -I- oo

donnons des bornes pour Q et sa fonct ion de r6parti- t ion en fonction de la loi limite et de sa fonct ion de r6partition, respectivement.

Enfin, l '&ude montre que P(n, r, s, .) converge aussi vers une loi de Poisson de param6tre = lim rs]n. Des bornes sont obtenues pour P

r,s n~+oo relativement ~t sa loi limite, de celles-ci on pourra d6duire des bornes sur sa fonct ion de r6partition.

Dans l '6valuation des bornes s~ar les probabilit6s, nous ferons un usage fr6quent deTin6gali t6 suivante, qui se montre ais6ment : pour K I N <~ 1[2,

N! (*) e-KZl2N + KI2N - Ka/3N2 ~ N r ( N - - K)I <~

e-K212N + KI2N

I V . I . Etude de H .

Soit i fix6, et s l 'ensemble de conditions : rsln --> v, r2s[n 2 ~ 0 et s2r[n 2 -+ O, r, s, n -+ + ~ . Le calcul de convergence [7], [8] donne comme loi iimite, une loi de Poisson :

s H(n, r, s, i) = 5'~(i) avec v = lim rs[n. r,s,n--~ + oo

En particulier, s H(n, r, s, 0) = e - L Pour pouvoir obtenir des bornes sur la pr6cision

de l ' approximat ion de P(n, r, s, i) par la loi de Poisson de param6tre v = rs]n, on a besoin de r6sultats similaires sur la probabilit6 H(n, r, s, i).

Proposition 3.

1) On a l ' encadrement suivant de la probabilit6 H en fonction de la probabilit6 de Poisson de param6tre

= rsln :

,y~(i) exp (__ i 2 r + s- 2 r2S + s2r ) rs n 2

H(n, r, s, i) ~< '$~(i) e 2"'+s)/".

2) L 'er reur commise sur la fonct ion de r6partition F de la probabilit6 H(n, r, s, .) relativement ~t Y, avec ~ = r~/n est major6e par :

( r + s ) 3 ( r + s ) - - 5 2 - [ - - - 0 ~

[F(~) - - Y~(~)I ~< rs n

sr 2 -~- rs 2 + 2

n 2

Ddmonstration. Elle r6sulte d ' u n calcul assez long mais sans difficult6, bas6 sur l 'usage de l'in6galit6 (*).

Exemple.

Sin = 264, r = S = 236 ,

alors 1F(256) - - Y256(256)[ ~< 2 -*6.

ANN. T[L~COMMUN., 44, n ~ 7-8, 1989 4/7

R. COHEN. -- FORMULE DE DI~NOMBREMENT SERVANT EN CRYPTOGRAPHIE 409

IV.2. Etude de Q.

Thgordme 2.

Quand rZ ]2n -+ X, n --> + ~ , la probabilit6 Q(n, r, c) tend vers une probabilit6 de Poisson Yz(c) de para- m6tre X = lim rZ[2n.

D~monstration. Le calcul met en 6vidence que la contr ibut ion la plus importante /t Q(n, r, c) est due /l l '6v6nement ~ il n ' y a que des paires de coinci- dences )r. On cherche /~ 6valuer la contr ibut ion de chaque configuration de coincidences. Rappelons que :

C~ ' - c r! Q(n, r, c) - 3",

nr (~ ..... ~,-~)~0"~ 0q!, ..., ~r-c!

Nous allons parti t ionner ~ de faqon /~ faire appa- raltre des sous-ensembles int6ressants. Dans un 616- ment ~ de :g, il peut intervenir au plus c composantes distinctes de 1 (s'il y en a exactement c, alors % = 2 pour c indices, les autres valant 1).

Soit a un (r - - c)-uplet de :g ayant k composantes distinctes de 1. Le produit ~a ! ... ~,_ c! 6tant invariant par permutation, le rapport r![~x! ... ~,_~! inter- viendra C~_~ lois dans la sommation. En tenant compte de ces remarques :

C;,- ~ ~ (r - - c) ! Q(n, C) r , x

n ~ ~ k ! ( r - - c - - k ) !

r!

o~ :

:R~ = { (~ ..... ~.) e {2 ..... c @ 1} ~ ;

k

~2 0 % = c + k , et ~ ~<... ~<o~}. j = l

r! Pour c fix6, et k ~ c, (r - - c - - k)! ~ rc+k' quand

r ~ + or. De sorte que :

r C + k C"-~ (r - - c)! y~ = Q(n, r, c) ~ n----- 7 -

k = l

n [ r 2c / 2Cc

n , ( n _ _ r _ _ c ) ! 2 ~ c ! ~1 + - 7 - y ~ _ ~ + . . . +

2%! )

r-g=_-; u ~ ,

avec : 1

Y k = (~l . . . . . ~ k ) ~ R k ~1 ! . . . ~ k !

(y~ = 2 - ~, car le c-uplet d6fini par 0% = 2, j = 1 .. c est le seul 616ment de 5~).

Finalement, avec une notat ion 6vidente,

Q ( n , r , C ) ~ n , ( n _ _ r § 1 +

e-'212" r2C ( Y) r212" (rz/2n)~ n~ 2 ~ e ! 1 + r ~ e - e!

D'of l la convergence :

Vcfix6, si r212n--->X, quand r, n ---> -k ~ , alors Q(n, r, c) --> fix(c).

La limite est donc une loi de Poisson de param6tre : = lira r2/2n.

r.n-~ -t- oo

En particulier, pour r = ~/n, on obtient une loi de Poisson de param6tre 0,5.

Remarques.

1) Si X = 0, alors la loi de Poisson est d6g6n6r6e :

Q ( n , r , c ) = t l s i c = 0 ,

0 si c =/: O.

2) On peut donner la majorat ion suivante pour le reste qui correspond ~. l '6v6nement ~ au moins une coincidence n 'es t pas une paire >>. Cet 6v6nement est inclus dans l '6v6nement ~ trois 616ments du tirage au moins coincident avec un m~me individu >~, dont la probabilit6 vaut :

n r - 3 - -

H r

De sorte que : r3 n! r! y

~=1 n'( n - r - - c)! ( r - - 2e)! 2 c c! r 6n z '

Proposition 4.

1) On a l 'encadrement suivant de la probabilit6 Q en fonct ion de la probabilit6 de Poisson ~x avec X = rZ/2n.

c 2 2 c 2 r 3 3 c3\ fix(c) exp . . . .

n r "3n 2 r "~ ) ~

(_~_ r , c 2 c 2) § r 3 Q(n, r, c) ~< fx(c) exp + ~nn T r 6 n 2"

2) La pr6cision de l ' approximat ion de la fonct ion de r6partition F de la loi Q par la fonction de r6parti- tion ~-x de la loi de Poisson de param6tre X = r2]2n, est donn6 par :

5 3r r 3 I F(~162 - - ~-~(~162 ~ -r g2 _}_ _n ~ § ~'/n 2"

Ddmonstration. Elle se calcule comme pour la proposi t ion 4 ~t l 'aide de l'in6galit6 (*).

Exemple.

Dans le cas off n = 264, r = 236, alors l'in6galit6 pr6c6dente condui t / t "1F(256) - - Ylzs(256)[ ~< 2-17

ThdorOme 3.

Si t in --> § ~ , n ---> § 0% alors :

Vc fix6, si r/n ---> q- ~ , quand r, n ---> + ~ , alors Q(n, r, c) ---> 0.

Ddmonstration. Le r6sultat d6coule de ce que Q ( n , r , c ) = 0 p o u r c < r - - n , e t q u e r - - n - - - > + ov quand n ---> § ~ avec r/n --~ ~ .

5/7 ANN. TELECOMMUN., 44, n ~ 7-8, 1989

410 R. COHEN. - FORMULE DE Dt~NOMBREMENT SERVANT EN CRYPTOGRAPH1E

IV.3. Etude de P.

Thdordme 4.

Soit s l 'ensemble de conditions aux limites (r2[2n -+ ~, s2[2n ~ ~t, r, s, n -+ + ~ } . Alors,

r - - l s - - l

P ( n , r , s , i ) = ~ E Q(n , r , k ) H ( n , r - - k , s - - l , i ) k = O l = O

Q(n, s, l) tend vers la probabilit6 de Poisson ~'~(i) de param~tre

= lim rs[n. r ) s ) ) l - - ) + CO

Ddmonstration. Elle est faite en quatre &apes.

1) A l 'aide de la double in6galit6 (*) on est en mesure d 'ob ten i r :

H(n, r, s, i) 9i(n, r, s, i, k , / ) ~< H(n, r - - k , s - - 1, i) ~<

H(n, r, s, i) %(n, r, s, i, k, l) avec :

q%(n, r, s, i, k, 1) ---- q;(r, i, k) ~ ( s , i, l) q"(n, r, k)

q~(n, s, l) e - (~+l )" . . . . . )

~,(n, r, s, i, k, l) : u/'(n, r, i, k) tF'(n, s, i, 1) e ( k + l ) 2 I ( n - � 9 s) + 2 (k + l ) ( r + n) ln

oh :

u/'(r, i, k) : exp ( r k

et W ( n , r , i , k ) : e x p ( k - - ~ 2 r

r - -

k - ~ _ r . +---= r - I

Pour k et l fix6s, g-lim q~(n, r, s, i, k, 1) = s %(n, r, s, i, k, l) : 1.

2) La somme por tan t sur des termes positifs, on a, pour ~ et ~ fix6s :

~ t

P ( n , r , s , i ) ~ ~ ~ Q ( n , r , k ) H ( n , r - - k , s - - l , i ) k = 0 l = O

Q(n, s, l) ~ H(n, r, s, i) ~t(n, r, s, i, o~, ~)

E Q(n , r , k ) ~, Q(n ,s , l ) . k = O / = 0

En passant ~ la s on a : s P(n, r, s, i) >~ s H(n, r, s, i) ~-x(0Q ~-u([~).

3) On fract ionne la double somme en quatre, puis on majore H(n, r - - k, s - - l, i) par 1 (en tant que probabilit6) pour k ~> ~ ou l >~ [~, et par une fonction de H(n, r, s, i) pour la somme restante. Il vient : P(n, r, s, i) ~< H(n, r, s, i) ~,(n, r, s, i, ~, [~)

f~ r - t

~. E Q(n , r , k ) Q ( n , s , l ) + ~ Q(n , r , k ) k = O 1 = 0 k = ~ t + 1

~ t s - i

~.. Q ( n , s , l ) + ~ Q ( n , r , k ) ~ Q ( n , s , l ) + I = 0 k = O I = ~ + l

r - - i s - i

5". Q ( n , r , k ) E Q ( n , s , l ) . k = 0 r 1 / = [ 5 + X

En passant h la s on a :

s P(n, r, s, i) ~< s H(n, r, s, i) ~-x(e) Y~(~) +

( 1 - ~-x(g))~-~([~) + ~-x(00 ( l - ~-u([3)) + ( 1 - Yx(g)) (1 - - .$'~(~)).

4) Lorsque 0~ et ~ tendent vers l'infini, les fonctions de r6partitions tendent vers 1 ([7], [8]) et les probabilit6s de tirages avec et sans remises coincident :

s P(n, r, s, i) = s H(n, r, s, i).

Si on ajoute h E la condit ion rs[n -+ ~ du para- graphe IV.I. , on a �9

r 2 s 2 ES

~/i fix6, s i ~ - + Z,~n--~ ~, n

quand r, s, n -+ + ~ alors P(n, r, s, i) -+ $~(i). La limite est donc une loi de Poisson de param6tre

v : lim rs]n. En particulier, pour r : s ~ k,~/-ff, r ) ~ / l --~ + co

on a une loi de Poisson de param~tre k 2.

Proposition 5.

P(n, r, s, i) est minor6e par :

'$~(i) e (-~2(r + s)/'s)- 2Cns+*2m"~ q~,(n, r, s,i, ~, ~) F,(~) F,(~)

et major6e par :

'2~(i) e 2""+*)t" q~,(n, r, s, i, c~, 13) F,(~) F~(~) +

(I - - F,(~)) F,(~) + Fr(ot) (I - - F,(~)) + (I - - F,(e)) (1 - - F~([33),

oh F, est la fonct ion de r6partit ion de Q(n, r, .), et pour des valeurs de 0~ et ~ arbitraires.

Ddmonstration. On obtient ce r6sultat en combinant les bornes obtenues pour H, avec les in6galit6s obtenues dans la d6monstrat ion du th6or6me 4.

V. RI~SULTATS NUMI~RIQUES

Les formules donnant la probabilit6 Q(n, r, c) du nombre de coincidences e lors du tirage avec remises de r individus d 'une popula t ion de taille n, ainsi que celle P(n, r, s, i), donnant le nombre d' individus distincts i dans l ' intersection des deux 6chantillons de tailles respectives r et s tir~s avec remises dans une populat ion de taille n, ont 6t6 programm6es.

On donne dans ce paragraphe, des exemples illus- trant les convergences dans le cas oh r : - s = fib-. A titre de r6f6rence, on rappelle les premi6res valeurs des lois de Poisson ~'o,s de param6tre 0,5, et ~Yx de param6tre 1 (Tabl. I e t II).

ANN. Ti~L~COMMUN., 44, n ~ 7-8, 1989 6/7

R. COHEN. - FORMULE DE DENOMBREMENT SERVANT EN CRYPTOGRAPHIE

TABL. I. - - Comparaison des premi6res valeurs de la probabilit6 Q(n, r, .) avec r = ~/~-, et de la probabilit6 de Poisson de param6tre 0,5, pour n croissant.

First values of the probability Q(n, r, .) with r = ~/FF, compared to the Poisson law with parameter 0.5, n growing.

411

c Q(100, 10, c) Q(144, 12, c) Q(256, 16, c) Q(625, 25, c) ff0,5(c)

0,628 0,310 0,056 0,004 0,000 0,000

0,624 0,309 0,059 0,006 0,000 0,000

0,619 0,308 0,064 0,007 0,000 0,000

0,611 0,307 0,068 0,009 0,000 0,000

0,607 0,303 0,076 0,013 0,002 0,000

First

.TABL. II. - - Comparaison des premi6res valeurs de la probabilit6 P(n, r, s, .) avec r = s = ~/h-, et de la probabilit6 de Poisson de param~tre 1, pour n croissant.

values of the probability P(n, r, s, .) with r = s = ~/h-, compared to the Poisson law with parameter 1, n growing.

P(100, 10, 10, i)

0,366 0,405 0,179 0,041 0,005 0,000 0,000 0,000

P(144, 12, 12, i)

0,367 0,399 0,181 0,045 0,006 0,000 0,000 0,000

P(256, 16, 16, i)

0,367 0,391 0,182 0,049 0,008 0,001 0,000 0,000

P(625, 25, 25, i)

0,365 0,379 0,182 0,053 0,010 0,001 0,000 0,000

~xl(i)

0,368 0,368 0,184 0,061 0,015 0,003 0,001 0,000

VI. C O N C L U S I O N

D a n s cet article, nous avons 6tudi6 l ' a spec t p ro - babi l i s te sous- jacent /t l ' a t t a q u e su ivan te en c ryp to - graphie : subs t i tue r ~ u n message sign6 u n message ( f raudu leux) a y a n t m~me s ignature , s a ch an t que la recherche exhaus t ive de tels messages est imposs ib le m~me avec des m o y e n s i n fo rma t i q u es i mp o r t an t s .

E n te rmes probabi l i s tes , la ques t i on est de calculer

la p robab i l i t6 P(n, r, s, i) que deux 6chant i l lons , de tailles r et s, tir6s avec remises, d ' u n e p o p u l a t i o n de taille n m u n i e de la loi un i fo rme , c o n t i e n n e n t u n n o m b r e fix6 i d ' i n d i v i d u s en c o m m u n . N o u s avons

m o n t r 6 que le p r o b l 6 m e se r a m 6 n e ~t l ' 6 tude de deux probabi l i t6s r e l a t i vemen t s imples h calculer , et n o u s avons 6tudi6 le c o m p o r t e m e n t a s y m p t o t i q u e de ces p robab i l i t6s sous des c o n d i t i o n s aux l imites inspir6es des r6sul ta ts d u ~< p a r a d o x e des jumeaux)>.

Si r2[2n t e n d vers Z, s2]2n t e n d vers ~t, rs /n t end

vers ~, (Z, ~t, v f n i s ) a lors la p robab i l i t6 P(n, r, s, .) t end vers une loi de Po i s son de p a r a m 6 t r e v.

Les c o n d i t i o n s sur les tailles r, s et n, p e r m e t t e n t de cons t ru i r e une a t t aque effective en ~ /n essais.

Manuscr i t rer le 6 ma i 1988,

acceptd le 29 sep tembre 1988.

BIBLIOGRAPHIE BIOGRAPHIE S

[1] DIFFIE (W.), HELLMAN (M. E.). New directions in crypto- graphy. IEEE Trans. Inf. theory (nov. 1976), 22, pp. 644-654.

[2] CAMPANA (M.), GIRAULT (M.). Comment utiliser les fonc- tions de condensation dans la protection des donn6es. Securicom (1988), pp. 91-110.

[3] RIVEST (R. t . ) , SHAMIR (A.), ADLEMAN (L.). A method for obtaining digital signatures and public key cryptosystems. C A C M (f6v. 1978), 21, n ~ 2, pp. 120-125.

[4] GIRAULT (M.), COHEN (R.), CAMPANA (M.). A generalized birthday attack. Advances in cryptology, Proc. of Crypto'88, Lecture Notes in Computer Science, Springer, n ~ 330.

[5] YUVAL (G.). HOW to swindle Rabin. Cryptologia (juil. 1979), 3, pp. 187-189.

[6] COPPERSMITH (D.). Another birthday attack. Advances in Cryptology, Proc. of Crypto'85, Lecture Notes in Computer Science. Springer (1986), 218, pp. 14-17.

[7] FELLER (W.). An introduction to probability theory and its applications. Wiley (1968), 1.

[8] COHEN (R.). GROJNOWSKI (M.). Cours de probabilit6s. Cours polycopi6. ENST, France (1985).

Robert COHEN, ne le 19 janvier 1960. Docteur de I'ENST en ~< Automatique et traitement du signal >> et titulaire d'une th6se de 3 e cycle en <~ Probabilit6s et applications >~, il a d'abord travaill6 dans le groupe de probabilit6s, puis dans l'6quipe de recherche en cryptographie de la division TIM t616matique, informatique et math6matiques appliqu6es, au CNET, avant de rejoindre le d6partement de radio-communications avec les mobiles de la division RDS R6seaux, distribution et services.

Marc GIRALrLT, n6 le 20 juillet 1955. Dipl6m6 de I'ErqST en 1977 et agr6g6 de math6matiques en 1980, il a enseign6 quatre ans avant de rentrer au SEPT dans la division ~ Paiement 61ectro- nique et mon6tique )), o/a il 6tudie plus particuli6rement les aspects cryptographiques des recherches qui y sont men6es.

Mireille CAMPANA, n6e le 13 novembre 1956. Ing6nieur des T616communications et agr6g6e de math6matiques, elle entre au CNET en 1982. Elle y travaille tout d'abord dans le d6parte- ment de math6matiques appliqu6es. Depuis 1985, elle est charg6e de l'6quipe de recherche en cryptographie de la division TIM.

7/7 ANN. T~L~COMMUN., 44, n ~ 7-8, 1989