M.
El Marraki
Université Mohammed V Master 1ère Année
Faculté des Sciences Rabat
Département d’Informatique 2014– 2015
TD de Complexité & Cryptographie
Exercice 1 : Graphe
1. Soit G un graphe simple.
a. Montrer que dans G le nombre de sommets de degré impair est pair.
b. Dans un groupe de vingt enfants, est-il possible que sept d'entre eux aient chacun
exactement trois amis, neuf d'entre eux en aient exactement quatre, et quatre d'entre
eux exactement cinq ?
Exercice 2 : Complexité d’un graphe
Soit la carte Tn formée par n cycles C5 de la façon suivante :
1. Trouver le nombre de sommets et le nombre d’arêtes de la carte Tn.
2. Soit tn le nombre d’arbres couvrant de Tn.
a. Trouver une relation entre tn , tn-1 et tn-2.
b. En déduire la complexité de Tn.
Exercice 3 : Complexité d’un algorithme
Soient deux entiers de n chiffres. La multiplication de ces 2 entiers apprise à l’école primaire est un
algorithme de coût proportionnel à n².
L’algorithme de Karatsuba est une application du principe " diviser pour régner " : Soient a et b
deux nombres de n = 2k chiffres. On pose et
1. Montrer que a×b peut se calculer avec trois multiplications seulement.
2. En déduire que le temps de calcul tn vérifie la relation suivante :
avec un c=6 ....
3. En posant n=2m, montrer que
et en déduire la valeur de tn.
Exercice 4 : fonctions indécidables
1. Le cas de 196 : Etant donné un entier positif, renversez les chiffres et ajoutez les au nombre.
Recommencez tant que vous n’avez pas trouvé un palindrome. Par exemple pour 5280 on
trouve :
5280 + 825 = 6105
6105 + 5016 = 11121
11121 + 12111 = 23232
En général pour n’importe quel nombre cet algorithme s’arrête rapidement.
Examiner le cas de 196.
TD Complexité & Cryptographie 1
M. El Marraki
2. La conjecture de Syracuse: Soit la fonction mathématique f : N → N définie par :
f(x)=x/2 si x est pair et 3x+1 sinon (On appelle cette fonction la fonction de Collatz).
Soit un entier positif n. Si on calcule f(n), puis f(f(n)), puis f(f(f(n))) etc. on finit toujours par
tomber sur la valeur 1. Aucun mathématicien n’est arrivé à ce jour à le démontrer (et on ne
sait même pas démontrer que c’est indécidable, c’est à dire non démontrable à l’aide des
mathématiques usuelles). Cela reste une conjecture.
Ecrire un programme qui prend un entier n en entrée et retourne le nombre d’étape qu’il faut
pour arriver à 1.
Paul Erdős a dit à propos de la conjecture de Syracuse: « les mathématiques ne sont pas
encore prêtes pour de tels problèmes »
Exercice 5 : Empilements
1. Aicha désire effectuer des correspondances avec le système cryptographique à
empilements ; pour cela elle construit une suite de nombres super croissante : u1=10,
u2=13, u3=29, u4=74, u5=157 et u6=300, ensuite elle prend d = 19 et n =
700. Elle utilise une permutation π=(u1,u5)(u2,u4)(u3)(u6) sur les 6 éléments de la
suite super croissante.
a. Donner la clef publique de Aicha.
b. Calculer l’inverse de d modulo n
2. Brahim désire envoyer le message M = 111001 à Aicha.
a. Donner le message C que Brahim doit envoyer.
b. Déchiffrer le message C que Aicha à reçu et retrouver le message initial M (n’oublier
pas la permutation π).
3. Expliquer le rôle de la permutation secrète π.
Exercice 6 : RSA
1. Soit un système à clé publique utilisant le RSA, avec la clef public n=33 et e=7 vous
interceptez le texte chiffré C = 30 14 06 07 01 26. Trouvez la message M.
2. Dans un système RSA, la clé publique d’un utilisateur donné est e = 13, n = 1763. Quelle est
la clé privée de cet utilisateur.
3. Aicha et Brahim utilisent le cryptosystème RSA. On suppose que Aicha a pour clef publique
(n,e) et pour clef privée (n,d).
Supposons que Chihab intercepte tous les messages qui parvient à Aicha. Brahim envoi le
message C=me mod n à Aicha. Chihab intercepte ce message et elle veut retrouver le
message m.
Chihab choisit un nombre aléatoire r tel que, r est inférieur à n. Elle calcule :
x=re mod n, y=xc mod n et t=r-1 mod n.
a- Montrer que t=x-d mod n.
b- Chihab fait signer le message y par Aicha, donc Chihab reçoit u=yd mod n. Montrer que
maintenant Chihab est capable de retrouver le message m.
c- Conclusion.
TD Complexité & Cryptographie 2
M. El Marraki
Exercice 7 : El Gamal
1. Soit le message M = CLEF, on désire coder le message M par la méthode ELGamal avec :
Clef publique : p=47, g=23, x = ? et k=3
Clef privée : p=47 et s=5.
a. Calculer x et vérifier que les clefs précédentes sont bien des clefs publiques/privées
d’ElGamal.
b. Chiffrer le message M (donner le message codé C et α)
2. On désire vérifier qu’on obtient bien le message initial en déchiffrant le message C , pour
cela :
s
a. Calculer l’inverse modulaire de α .
b. Déchiffrer le message C et retrouver le message initial M.
Exercice 8 : Courbes Elliptiques
Soit la courbe elliptique cryptographique E(1,6,11) :
y2 mod 11 = (x3 + x + 6) mod 11.
1. Montrer que les points R(3,5) et M(10,9) sont des points de la courbe, et calculer les
points C=R+M (voir l’annexe).
2. Aicha et Brahim veulent correspondre en utilisant le cryptosystème elliptique : ils se mettent
d’accord sur E(1,6,11) et le point A=(2,7) de E. Supposons que la clef privée de Aicha
est dA=5 et celle de Brahim est dB=7 (Brahim communique à Aicha sa clef public :
P=7A=(7,2)). Supposons que Aicha veut envoyer à Brahim le message M=(10,9), elle
choisit une valeur aléatoire k=3.
a. Calculer le message que Aicha doit envoyer à Brahim (voir l’annexe).
b. Si Brahim reçoit le texte chiffré, expliquer comment il va faire pour retrouver le message
clair, et retrouver ce message par le calcul (voir l’annexe).
3. Expliquer comment on peut factoriser un nombre entier en utilisant les courbes elliptiques.
Annexe :
1. Règles de l'addition : Soit la courbe elliptique cryptographique
E(a,b,p): y2 mod p=(x3+ax+b)mod p
1. Si x1≠x2, (x1,y1)+(x2,y2)=(x3,y3), avec x3=(k2-x1-x2)mod p,
y3=(k(x1-x3)-y1) mod p où k = (y2-y1)×(x2-x1)-1 mod p
2. Si y1 ≠ 0, (x1,y1) + (x1,y1) = 2(x1,y1) = (x3,y3), avec x3=(k2-
2x1) mod p et y3=(k(x1-x3)-y1) mod p où k=(3x12+a)×(2y1)-1 mod
p
2. Dans E(1,6,11) :
- Si A=(2,7), alors 2A=(5,2), 3A=(8,3),4A=(10,2),5A=(3,6),6A=(7,9),
7A=(7,2)…
- Si P=(7,2) alors 3P=(3,5)
- Si Q=(8,3) alors 7Q=(3,5)
TD Complexité & Cryptographie 3
