Factorisation par courbe elliptique

Il y a quelques années, lorsque nous penchions sur le Green Code, nous avions trouvé une méthode de factorisation intéressante appelée communément appelé ECM (pour Elliptic Curve Method). Etant curieux, nous avons voulu percer les zones ombres de cette méthode. Notre article précédent nous a permis de définir les bases sur les courbes elliptiques. Cela nous sera utile pour cet article.

Hendrik Lenstra a, en 1985, découvert/inventé un algorithme de factorisation qui utilise des courbes elliptiques. Cet algorithme a la particularité de permettre de trouver  les petits facteurs premiers d’un nombre aussi grand qu’il soit.  Et là où la plus part des algorithmes de factorisation dépendent de la taille du nombre à factoriser celui-ce dépend principalement de la taille du facteur à trouver.

L’idée de la factorisation par courbe elliptique consiste à choisir une courbe elliptique modulo N (le nombre à factoriser) et de tenter de multiplier un point P plusieurs fois sur cette courbe.

Comme nous l’avons vu, pour le calcul de la somme de deux points sur une courbe elliptique il faut calculer la pente m. Cette pente contient une division qui en arithmétique modulaire n’est rien d’autre que le calcul d’un inverse. Or cet inverse n’existe pas toujours dans le cas où N est composé. Ainsi si notre addition de deux points échoue, nous avons probablement trouvé un diviseur de N.

Petit exemple avec 91

Plus concrêtement, essayons de factoriser le nombre  N=91 avec la courbe E(1,1) :

On choisit un point de la courbe : par exemple  P (37,37) est bien sur la courbe car :

37^2 \mod 91 = 1369 \mod 91 = 4
37^3+37+1 \mod 91 = 50653 +37 +1 \mod 91 = 50691 \mod 91 = 4

Puis on l’additionne à lui-même plusieurs fois : Au début tout se passe bien : P = (37,37) ;  2P = (56,15) ; 3P = (49,20) ; 4P = (86,40)
Mais pour 5P = 4P + P = (86,40)+(37,37), on doit calculer m =  \frac{40 -37}{86-37} \mod 91 = \frac{3}{49} \mod 91 Or 49 n’a pas d’inverse modulo 91.

Comme le calcul échoue, on sait que \gcd(91,49) > 1 on a donc trouvé un diviseur de N.

Notez que bien que le point 5P n’existe pas, le point 6P existe bel et bien sur la courbe :(23,58).

Les calculs échouent pour k = 5 ( et tous ces multiples) car 7 est un diviseur de 91 et que 5 est le nombre d’éléments de E(1,1) modulo 7.

Projetons-nous

Si l’on veut comprendre d’où vient ce lien, il faut comprendre les liens des courbes E(a,b) modulo 91 et modulo 7.

Chaque point de la courbe modulo 91 peut être « projeter » sur la courbe modulo 7 simplement en réduisant ces coordonnées modulo 7.

Tout d’abord remarquons que sur la courbe E(1,1) modulo 7, il n’y a que 5 éléments.

sage: Z = Zmod(7)
sage: E = EllipticCurve(Z, (1,1))
sage: E.points()
[(0 : 1 : 0), (0 : 1 : 1), (0 : 6 : 1), (2 : 2 : 1), (2 : 5 : 1)]
sage: E.cardinality()
5
sage:

Si l’on reprend le point P_{91} (37,37) sur la courbe modulo 91 et qu’on le réduit modulo 7 alors on tombe sur P_7 (2,2), mais cela fonctionne aussi avec les multiples de P : 2*P_{91}  = (56,15) qui se projete Q_{7}  = (0,1) = 2P_7.

Mais c’est Absurde

On peut continuer de vérifier les additions pour les multiples suivants. Vient alors le cas 5*P_{91} et raisonnons par l’absurde.

Si  nous supposons qu’un tel point existe, alors on pourrait calculer m donc ces coordonnées seraient finis. Et nécessairement la réduction modulo 7 de ces coordonnées le seraient aussi (ie celles de 5*P_{7} ).

Or on sait que l’ordre de cette courbe est 5 et donc d’après Lagrange, 5 fois n’importe quel point est égal à l’élément neutre. Dans le cas des courbes elliptiques, l’élément neutre a des coordonnées infinies.

D’où l’absurdité.

Quels paramètres choisir ?

Revenons au cas général. Si nous souhaitons utiliser cette technique pour factoriser un entier quelconque, plusieurs questions se posent :

Y-a-t-il un point P à choisir en particulier ?

La réponse à cette question est assez simple : pour l’instant nous n’avons pas de moyen de déterminer à l’avance si un point sera meilleurs qu’un autre. Le point est donc souvent choisi au hazard.

Quelle est la valeur optimale pour k (le nombre de fois qu’on multiplie le point P) ?

Pour répondre à cette question, posons-nous en une autre quelle sont les propriétés que nous souhaitons avoir pour k ? De plus, nous avons vu plus haut dans notre exemple que 5*P n’existait pas (ni ses multiples) mais que 6*P lui existait. Autrement dit, nous cherchons un k qui soit au moins égal à l’ordre de la courbe modulo le facteur cherché. Bien entendu, nous n’avons aucune idée de l’ordre en question.

Soyons naïfs :

Du coup une approche naïve pourrait être de prendre k = r!  avec r l’ordre maximum possible pour notre facteur :

Si nous cherchons les facteurs plus petit que 1000000 on sait que l’ordre maximum sera 1000000+2\sqrt(1000000)+1 = 1002001.

Mais ça fait quand même beaucoup…

Soyons attentifs !

Nous pourrions donc utiliser non plus la factorielle mais la primorielle. Cela réduit significitivement notre nombre. Cependant cela reste incomplet et nous pouvons « probablement » mieux faire.

Cela reste incomplet car si l’ordre pour le facteur chercher est par exemple 9. La multiplication par k = 11# (primorielle 11 = 2*3*5*7*11), ne donnera pas le résultat escompté car nous n’avons pas de puissance des nombres premiers.

Idéalement, il faut choisir une borne B et calculer le produit de toutes les puissances de nombres premiers inférieurs à B. Pour 27, nous aurions  k = 2^4*3^3*5*2*7*11*13*17*19*23. Ce nombre est aussi le plus petit commun multiple (ppcm ou lcm chez Shakespeare)  de tous les nombres entre 2 et 23 (le dernier nombre premier précédent 27)

Mais le nombre k est toujours très (trop) grand pour une utilisation en pratique

Par ailleurs, les lecteurs assidus de ce blog auront peut-être reconnu un problème se rapproche d’une notion déjà abordée ici. En effet, les plus attentifs auront probablement fait le lien avec la friabilité introduite lorsque nous parlions de l’algorithme p-1 de Pollard et l’optimisation de k.

Les valeurs de a et b varient chacune de 0 à N, Il y a un peu moins de N^2 (il faut enlever les cas où \Delta = 4*a^3 + 27*b^2 mod N = 0 ) courbes possibles. Mais leurs ordres se répartissent sur 4*\sqrt{N}. Nécessairement, il y a plusieurs courbes qui possèdent le même ordre.

Cependant on doit aussi s’intéresser aux ordres super-friables. Grâce à un petit script, nous obtenons les résultats suivants qui donnent une  tendance.

P Ordres min et max Nombre d’ordres différents Valeurs B-smooth avec B = Sqrt(P) Ratio
11 (5, 18) 13 0 0
101 (81, 122) 41 4 0.097
1009 (946, 1073) 127 22 0.173
10009 (9809, 10210) 401 83 0.206
100003 (99371, 100636) 1265 314 0.248
1000003 (998003, 1002004) 4001 1036 0.258
10000019 (9993695, 10006344) 12649 3371 0.266
100000007 (99980007, 100020008) 40001 10961 0.274
1000000007 (999936762, 1000063253) 126491 35247 0.278

En effet, il semble que plus P augmente, plus le nombre de nombre B-superfriable (avec B = sqrt(B)) augmente. Nos calculs montrent que si nous avons un P proche de 10^6 alors nous avons 25% des ordres sont 1000-superfriables. Cela donne une précision intéressante.

Pour la suite, soyons probabilistes !

En utilisant la notion de friabilité et le fait que nous pouvons tester plusieurs courbes, il est peut-être possible de drastiquement réduire le nombre k. En effet, avec un peu de chance, nous pouvons tomber sur une courbe d’ordre B-super-friable, avec un B de taille raisonnable.

Puisque le nombre total de courbes est très grand, il n’est pas possible d’effectuer des recherches sur toutes les courbes, nous devons nous limiter à effectuer des calculs sur un sous-ensemble des courbes mais combien précisement ?  Il y a deux aspects à prendre en compte : il nous faut d’un coté avoir suffisament de courbes pour avoir une chance (probabilité) raisonnable de trouver un facteur de la taille choisie et d’un autre coté, il nous faut avoir un minimum de courbe pour que les temps de calculs soient compétitifs par rapport aux autres méthodes de recherche de facteur.

Nous avons donc réalisé une implémentation de l’algorithme ECM en utilisant l’outils SageMath. Le script donc le code est ci-dessous nous a permis d’étudier les valeurs optimales du nombre de courbe et de B en fonction de la taille du facteur à trouver. Le résultat est donné dans le tableau ci-aprés.

Taille du        B    Nb Moyen           Nb de courbe pour les 10 tests
facteur                        Nb Médian    réalisés pour chaque B     

1.00E+05	20	1322.8	1086	[849, 3276, 1932, 73, 1323, 2471, 599, 414, 187, 2104]
1.00E+05	50	41.5	24	[72, 25, 3, 23, 13, 18, 23, 140, 65, 33]
1.00E+05	100	18.3	15.5	[15, 11, 35, 5, 16, 35, 9, 14, 20, 23]
1.00E+05	200	5.8	3.5	[13, 3, 1, 12, 14, 3, 1, 5, 4, 2]
1.00E+05	500	3.1	2.5	[3, 2, 9, 1, 2, 3, 5, 4, 1, 1]
1.00E+05	1000	2	1	[5, 1, 1, 1, 2, 1, 2, 5, 1, 1]
1.00E+05	1500	2.2	2	[2, 1, 1, 2, 4, 5, 2, 2, 2, 1]
1.00E+06	20	5263.1	5603.5	[416, 26, 10000, 10000, 2149, 10000, 7829, 5929, 1004, 5278]
1.00E+06	50	156.4	128.5	[376, 31, 97, 160, 69, 168, 97, 358, 28, 180]
1.00E+06	100	21.6	12.5	[14, 10, 6, 72, 11, 1, 1, 25, 36, 40]
1.00E+06	200	12.8	7	[29, 21, 1, 4, 15, 1, 8, 4, 6, 39]
1.00E+06	500	4	3.5	[4, 3, 4, 3, 2, 7, 2, 4, 2, 9]
1.00E+06	1000	3.5	3.5	[4, 3, 2, 5, 4, 6, 6, 2, 1, 2]
1.00E+06	1500	3.1	2.5	[5, 3, 1, 1, 2, 5, 7, 1, 2, 4]
1.00E+07	20	10000	10000	[10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000]
1.00E+07	50	1204.3	802	[183, 794, 930, 2831, 372, 810, 55, 1747, 3974, 347]
1.00E+07	100	210.1	204	[67, 315, 71, 373, 10, 8, 555, 275, 133, 294]
1.00E+07	200	32.7	14.5	[10, 18, 3, 123, 1, 35, 83, 32, 11, 11]
1.00E+07	500	15.8	12	[14, 14, 6, 2, 7, 40, 5, 43, 17, 10]
1.00E+07	1000	3.6	3	[1, 1, 3, 6, 6, 4, 3, 3, 3, 6]
1.00E+07	1500	6.7	5	[5, 1, 8, 16, 5, 13, 3, 5, 4, 7]
1.00E+08	20	10000	10000	[10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000]
1.00E+08	50	2408.1	1555	[2199, 1213, 2309, 1724, 3939, 1386, 10000, 506, 385, 420]
1.00E+08	100	460.3	521	[599, 603, 127, 203, 868, 549, 1020, 90, 493, 51]
1.00E+08	200	53.2	50	[9, 51, 14, 49, 147, 67, 91, 3, 84, 17]
1.00E+08	500	23.1	16.5	[8, 25, 6, 18, 83, 7, 16, 13, 38, 17]
1.00E+08	1000	15.6	15	[4, 38, 17, 15, 12, 3, 22, 27, 3, 15]
1.00E+08	1500	9.4	3.5	[6, 1, 1, 2, 1, 4, 54, 13, 9, 3]
1.00E+09	20	10000	10000	[10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000]
1.00E+09	50	10000	10000	[10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000]
1.00E+09	100	3262.9	2229	[2496, 1305, 3913, 272, 282, 9391, 2991, 1962, 10000, 17]
1.00E+09	200	284.2	186.5	[92, 631, 123, 799, 169, 399, 168, 204, 233, 24]
1.00E+09	500	43	43.5	[41, 46, 49, 19, 4, 56, 88, 5, 119, 3]
1.00E+09	1000	25.7	18	[85, 15, 3, 21, 9, 36, 35, 13, 1, 39]
1.00E+09	1500	18.3	11.5	[62, 8, 15, 5, 19, 5, 5, 30, 26, 8]
1.00E+11	200	4203.5	2883.5	[479, 6265, 10000, 10000, 491, 6260, 3211, 2556, 1825, 948]
1.00E+11	500	188.9	203	[263, 238, 93, 362, 22, 229, 342, 57, 177, 106]
1.00E+11	1000	168.2	137.5	[134, 144, 223, 230, 567, 84, 71, 141, 80, 8]
1.00E+11	1500	109	58.5	[8, 40, 319, 35, 252, 57, 160, 60, 37, 122]
1.00E+12	200	7652.1	10000	[10000, 10000, 1126, 1425, 10000, 10000, 6572, 10000, 10000, 7398]
1.00E+12	500	1156.9	872	[403, 1414, 3639, 954, 1297, 303, 487, 663, 1619, 790]
1.00E+12	1000	288.3	186	[165, 207, 72, 728, 140, 324, 398, 628, 125, 96]
1.00E+12	1500	82.4	81	[74, 12, 12, 253, 91, 93, 1, 35, 88, 165]
1.00E+13	200	9562.1	10000	[10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 5621]
1.00E+13	500	3742.1	3837.5	[1038, 8005, 5419, 4126, 4256, 1254, 3449, 5933, 3549, 392]
1.00E+13	1000	746.6	645	[577, 1545, 389, 713, 1412, 1110, 85, 522, 921, 192]

Ici notons que nous avons une approche très naïve. Nous utilisons beaucoup de fonction aléatoire pour générer nos points et nos courbes. Cela donne que des résultats bien loin de standard moderne dont le raisonnement est hors de notre portée. Mais les mathématiciens sont des gens plein de ressources et ont trouvé des moyens pour encore rafiner et  abaisser la borne B et le nombre de courbes en remarquant que certains courbes notamment ont des propriétés intéressantes.

Y-a-t-il une courbe (des coefficients a et b) à choisir en particulier ?

Cette dernière question est en effet importante. Les coefficients a et b permettent d’influer sur l’ordre de la courbe et comme le rappelle le théorème de Haas, l’ordre d’une courbe modulo p varie entre p+1 -2\sqrt{p} et p+1+2\sqrt{p}. L’expérience montre que l’ordre de la courbe est assez régulièrement réparti pour l’ensemble des valeurs du couple (a,b) mais que certains ordres ont plus de succes que d’autre. Ci-dessous nous avons fait une recherche exhaustive du nombre de courbe par ordre pour différentes valeurs de nombres premiers

17: [4, 8, 24, 8, 16, 24, 28, 8, 32, 8, 28, 24, 16, 8, 24, 8, 4] 17 17
53: [39, 26, 104, 52, 104, 130, 52, 26, 260, 52, 117, 104, 156, 78, 156, 78, 156, 104, 117, 52, 260, 26, 52, 130, 104, 52, 104, 26, 39] 29 29
79: [52, 156, 78, 156, 91, 156, 156, 312, 78, 390, 78, 156, 156, 364, 117, 156, 234, 390, 234, 156, 117, 364, 156, 156, 78, 390, 78, 312, 156, 156, 91, 156, 78, 156, 52] 35 35
101: [25, 50, 300, 100, 100, 250, 300, 100, 400, 150, 500, 200, 200, 200, 600, 150, 200, 400, 375, 100, 700, 100, 375, 400, 200, 150, 600, 200, 200, 200, 500, 150, 400, 100, 300, 250, 100, 100, 300, 50, 25] 41 41
127: [126, 63, 336, 147, 252, 252, 630, 189, 252, 378, 504, 315, 252, 126, 1008, 504, 378, 252, 504, 189, 756, 273, 630, 273, 756, 189, 504, 252, 378, 504, 1008, 126, 252, 315, 504, 378, 252, 189, 630, 252, 252, 147, 336, 63, 126] 45 45
173 [129, 86, 516, 86, 516, 602, 344, 258, 1032, 172, 516, 602, 1032, 430, 688, 430, 516, 860, 516, 258, 2064, 344, 559, 430, 860, 430, 1204, 430, 860, 430, 559, 344, 2064, 258, 516, 860, 516, 430, 688, 430, 1032, 602, 516, 172, 1032, 258, 344, 602, 516, 86, 516, 86, 129] 53 53
257: [64, 128, 896, 256, 768, 1024, 768, 256, 1024, 384, 1536, 896, 768, 512, 2816, 640, 512, 1280, 1792, 896, 2048, 384, 768, 640, 1536, 1024, 3072, 512, 512, 1664, 1984, 512, 2048, 512, 1984, 1664, 512, 512, 3072, 1024, 1536, 640, 768, 384, 2048, 896, 1792, 1280, 512, 640, 2816, 512, 768, 896, 1536, 384, 1024, 256, 768, 1024, 768, 256, 896, 128, 64] 65 65

Même si aucune formule actuellement ne permet de déterminer l’ordre d’une courbe en fonction de a,b et p, En autre des mathématiciens en utilisant des notions que nous détaillerons pas ici (comprendre qu’on n’a pas vraiment compris) ont trouvé des sous-ensembles de courbes dont l’ordre est au moins toujours divisibles par 12 (Paramétrage de Sumaya). Cela donne un certain avantage et permet de réduire le nombre de courbes à tester.

Mais l’algorithme a encore et toujours été raffiné : tant sur l’implémentation (pour gagner en vitesse de calcul) que sur les choix des courbes et que celui de k.

Ainsi les dernieres valeurs recommandées lors de l’utilisation de GMP-ECM (la référence pour la factorisation par courbes elliptiques) sont les suivantes :

Digits optimal B1 expected curves
(default parameters for GMP-ECM 6)
expected curves
(default parameters for GMP-ECM 7)
20 11,000 86 107
25 50,000 214 261
30 250,000 430 513
35 1,000,000 910 1,071
40 3,000,000 2,351 2,753
45 11,000,000 4,482 5,208
50 43,000,000 7,557 8,704
55 110,000,000 17,884 20,479
60 260,000,000 42,057 47,888
65 850,000,000 69,471 78,923
70 2,900,000,000 102,212 115,153
75 7,600,000,000 188,056 211,681
80 25,000,000,000 265,557 296,479

Voici quelques lectures intéressantes pour ce qui voudraient aller plus loin :

En espérant que vous avez réussi à suivre, sinon n’hésitez pas à laisser un commentaire .

 

Implémentation naïve d’ECM avec Sage:


#!/usr/bin/env sage

from numpy import median
from itertools import groupby
from sage.all import *

'''
Naive implemenation of ECM method
for test and education purposes
'''
def factorECM(k,m,verbose):
	condition1 = True
	condition2 = True
	Z = Zmod(m)
	curvecount = 0
	x = 0
	y = 1
	while curvecount  0):
			curvecount += 1
			#The curve is defined modulo M
			E = EllipticCurve(Z, (a,b))
			if(verbose):
				print "Curve", a ,b
			'''For some reasons, Sage does not allow us to
			use E.random_point() when M is composite
			so we have to compute a point on the curve
			We simply try various value of x and hope to find one
			'''
			while condition2 :
				x = ZZ.random_element(0,m)
				y2 = x**3 + a*x + b % m
				try:
					y = mod(y2,m).sqrt(extend=False) 		

				except:
					continue
				break	

			P = E(x,y)
			#We compute k*P	on catch the error if any, if not we'll try another curve
			try:
				Q = k*P
			except ZeroDivisionError as err:
				d = Integer(err.args[0].split()[2])
				if(verbose):
					print "After testing ", curvecount, " curve(s), we have a winner : "
					print "\t Point P :"  , P
					print "\t on E(",a,",",b,")"
					print "\t In K*P computation, d=", d ,"has no inverse modulo", m
					print "\t So we found one factor gcd(m,d) =", gcd(m,d)
				print "m =", m , " = ", gcd(m,d),"x", m/gcd(m,d)
				return curvecount

	if(verbose):
		print "No factor found with the given parameter : try increase B"
	return curvecount

def main(argv):
	if len(sys.argv) != 4:
	    print("Usage: %s     " % sys.argv[0])
	    print("Naive implementation of ECM for factorization")
	    print("v : Try to factor  with ")
	    print("q : Do some benchmark with random composite and predefine B")

	    sys.exit(1)

	#The number we want to factor
	m = sage_eval(sys.argv[2])

	#super-smooth border B
	B = sage_eval(sys.argv[3])

	if sys.argv[1] == 'v':
		#We compute the number k
		k = LCM(2..previous_prime(B))
		factorECM(k,m,True)
		return 0
	if sys.argv[1] == 'q':
		Blist = (200,500,1000,1500)
		for i in range (11,16):
			rg = 10**i
			for B in Blist:
				nbcurve = list()
				k = LCM(2..previous_prime(B))
				for l in range(10):
					p = next_prime(ZZ.random_element(rg,rg*10))
					q = next_prime(ZZ.random_element(rg*321,rg*14311))
					nbcurve.append(factorECM(k,p*q,False))
				print rg, B,
				print float(sum(nbcurve) / len(nbcurve)), float(median(nbcurve)),
				print nbcurve

if __name__ == "__main__":
   main(sys.argv[1:])
<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;">&#65279;</span>

Publicités
Publié dans Cryptographie Asymétrique, Outils, RSA | Tagué , , , , , , , | Laisser un commentaire

Comprendre les courbes elliptiques

Les courbes elliptiques sont devenues au fil des années un concept incontournable de la cryptographie asymétrique. Mais au final, elles restent un concept assez obscure pour beaucoup.  Que se cache derrière les ECDSA et ECDH pour ne parler que des applications les plus utilisées ?

Avant tout, ces courbes sont des outils mathématiques intéressants. Bien que récentes  en cryptographie (introduites en 1985), elles ont déjà été largement étudiées et ont notamment été utilisées par Andrew Wiles dans sa démonstration du grand Théorème de Fermat (vous savez, la fameuse conjecture du magistrat toulousain dont la démonstration ne tenait pas dans la marge).

Leurs propriétés leur donnent un intérêt particulier pour la cryptographie asymétrique et  il est désormais normal de voir ces deux acronymes dans les suites de chiffrement proposées : ECDSA et ECDH sont respectivement l’algorithme de signature numérique sur courbes elliptique et l’algorithme d’échange de clés Diffie-Hellman sur courbes elliptiques.

Mais comment l’utilisation de ces courbes elliptiques améliorent-elles la sécurité de ces algortihmes ?

Pour répondre à cette question, comprenons d’abord ce qu’est une courbe elliptique, et quelles sont celles qui sont intéressantes en cryptographie (et pourquoi).

Loin de nous l’idée de faire un cours magistral sur les courbes elliptiques, mais présentons ici rapidement de quoi il s’agit (et nous nous excusons par avance pour les approximations que nous ferons par la suite, l’idée étant de présenter le concept).

Quelques généralités

Une courbe elliptique est comme son nom l’indique une courbe (i.e: un ensemble de point). Elle est régi par une équation de la forme générique (appelée équation de Weierstrass) :
y^2  + a_1xy + a_3y  = x^3+a_2x^2+a_4x + a_5

Pour ne pas rentrer dans trop de détail, nous allons admettre que  les coefficients a_i doivent satisfaire certaines propriétés pour ne pas admettre de singularité (point de doublement ou  de rebroussement). C’est à dire que si on écrit l’équation précédente sous la forme d’une équation homogène F(x,y) = 0 alors les dérivées partielles de F ne doivent pas s’annuler simultanément en un point de la courbe.

Dans le cas qui nous intéresse (ie en cryptographie), l’équation précédente peut être simplifiée par changement de variable et on utilise le plus souvent une équation de la forme y^2 = x^3 + ax + b où a et b vérifient \Delta = 4a^3 + 27b^2 \neq 0 pour éviter toute singularité. On dit que cette équation est de la forme de Weierstrass simplifiée.  (Mais sachez qu’il existe aussi des équations dites de Montgomery ou d’Edward. Parfois, on l’explicite aussi sous sa forme de Legendre, chacune ayant des avantages).

Mais contrairement à ce que leur nom semble indiquer, ces courbes n’ont rien à voir avec des ellipses et peuvent avoir des formes variées comme le montre les exemples ci-après.

exemples_ce

Merci GnuPlot

Sur l’image ci-dessus, quelques courbes avec différentes  valeurs (a,b) utilisées. Notez que pour (0,0) et (-3,2), les courbes obtenues ne sont pas elliptiques car \Delta = 0.  En effet une courbe ne peut pas être elliptique si elle est singulière (comprendre que les dérivés partielles par rapport à x et y ne peuvent simultanement nulle en un point). Géométriquement on peut aussi l’interpréter comme  chaque point n’admet qu’une et une seule  tangente à la courbe. Si on en revient à nos deux exemples,  la courbe y^2=x^3 n’admet pas de tangente au point (0,0) On dit que c’est un point de rebroussement et  y^2 = x^3 -3x + 2 a deux tangentes au point (1,0), on parle alors de point double.  On vous laisse vérifier pour les dérivés partielles…

L’intéret des courbes elliptiques est que l’on peut définir une opération que nous noterons + entre des points de la courbe permettant alors de définir un groupe.

– Commutativité P + Q = Q + P
– Associativité P + (Q+R) = (P+Q) + R
– Il existe un élément neutre P + e = e + P = P
– Chaque point a un opposé R + R’ = e

Cette opération est très simple géométriquement :

On définit le résultat de P+Q, en traçant une droite qui passe par P et Q, cette droite coupera la courbe en un troisième point R. On prend alors le symétrique par rapport à l’axe des abscisses et nous obtenons alors un autre point que nous noterons R’ qui est le résultat de l’opération.

Si P = Q, alors on utilise la tangente de la courbe au point P pour remplacer la droite (PQ). Vous voyez maintenant l’importance de l’unicité de la tangente.

Enfin si Q=-P, alors la droite (PQ) est perpendiculaire à l’axe des abscisses et ne coupe pas la courbe en un autre point : on peut imaginer alors que cette droite coupe la courbe en l’infini, on notera ce point 0 et on pose P – P = 0 et ce 0 est l’élément neutre de notre addition sur courbe elliptique.

https://fr.wikipedia.org/wiki/Courbe_elliptique#/media/File:ECClines-2.svg

Merci Wikipedia

Cette méthode géométrique est certes pratique mais admet quelques limites. Nous devons donc définir ces opérations sous forme algébrique :

Notons (x_P,y_P) et (x_Q,y_Q), les coordonnées des points P et Q.

Les coordonnées de S = P + Q sont données par les formules suivantes :

x_S = m^2 -x_P-x_Q et y_S = m(x_P-x_S) -y_P

  • Si P = Q et si y_p \neq 0 latex m = \frac{(3x_P^2 + a)}{2y_P}$
  • Sinon m = \frac{(y_Q-y_P)}{x_Q-x_P}

Application à la cryptographie

En général, les courbes elliptiques sont définies sur des espaces continues : par exemple toutes les valeurs sont sur R (l’ensemble des réels). Mais dans le cadre de leur utilisation en cryptographie (et donc dans la suite de ce texte), on change un peu la donne : on va travailler sur les entiers modulo un nombre premier.

Du coup, la représentation de la courbe n’existe plus vraiment en tant que telle : on parle plutot de nuage de point. L’exemple ci-dessous montre la même courbe (y^2 =x^3 -3x) representée sur l’espace des réels puis sur les entiers modulo 7 et 23 :

Vous en conviendrez difficiles de remarquer qu’il s’agisse de la même courbe représenter sur des corps différents. Notez au passage que la symétrie est respectée.

La propriété de groupe entre les points est bien entendu préservée. La différence est que nous avons maintenant un groupe cyclique : si nous multiplions un point par 2, puis 3, puis 4, etc Nous finirons par retomber sur notre point.

Cela n’est pas sans rappeler la propriété de \mathbb{Z}/p\mathbb{Z}* avec p premier, où l’on sait d’après le petit théorème de Fermat que pour tout élément a \in [1;p-1]  : a^p = a \mod p

On dit alors que l’ordre du groupe \mathbb{Z}/p\mathbb{Z}* est p-1.

Dans notre exemple : pour la courbey^2 =x^3 -3x et sur les corps choisies  (ie \mathbb{Z}_7 et \mathbb{Z}_{23}),  l’ordre de la courbe (ou encore la cardinalité de la courbe), c’est à dire le nombre de points distinct de la courbe est respectivement égale à 8 et 24 : Soit le nombre de point de la courbe + l’élément neutre à l’infini (souvent noté (0,0,1)).

On pourrait donc croire à tort que l’ordre est toujours p+1.

Bien au contraire, l’ordre de la courbe modulo p est quelque chose de difficile à appréhender car sa valeur n’a rien de systématique. Le théorème de Hasse démontre que l’ordre d’une courbe elliptique est toujours compris entre p+1+2\sqrt{p} et p+1 - 2\sqrt{p}. Mais rassurez vous, nul besoin de compter le nombre de points pour obtenir l’ordre d’une courbe elliptique, l’algorithme de Schoof est là pour vous.

Si nous insistons sur le sujet, c’est que l’ordre d’une courbe elliptique est un critère important de sa sécurité, tout comme la friabilité d’un nombre premier peut l’être pour RSA.

ECDLP

Pour comprendre pourquoi, penchons nous sur l’ECDLP ou en bon français le problème du logarithme discret sur courbe elliptique. Toute la cryptographie sur courbes elliptiques est basée sur ce problème qui est bien similaire à son homologue sur les entiers.

Ici, étant donnés deux points P et Q de la courbe, la difficulté est de retrouver le nombre k tel que Q = kP.

Ainsi l’algorithme d’échange de clé de Diffie-Helman devient :

  • Arnaud et Bernard (oui, marre d’Alice et Bob)  s’accordent sur une courbe et un point G de la courbe.
  • Arnaud choisit aléatoirement d_A et calcule  G_A = d_A G et l’envoie à Bernard.
  • Bernard choisit aléatoirement d_B et calcule  G_B = d_B G et l’envoie à Arnaud.
  • Arnaud calcule alors S = d_AG_B = d_A d_B G et Bernard calcule S = d_BG_A = d_A d_B G.

Rien de plus.  ECDH est considéré aussi dur que ECDLP (de la même façon que la sécurité de DH classique est basée sur la difficulté à résoudre le DLP).

Quelques écueils à éviter :

La Friabilité de l’ordre de la courbe

Comme nous l’avons vu, la difficulté de ECDLP est basée sur la difficulté a retrouvé un nombre k tel que Q = kP. Si l’ordre de la courbe est petit (ou ne possède que des petits facteurs premiers), il sera alors (plus) facile de retrouver ce nombre k.

En pratique dans la vraie vie, les corps utilisés sont d’un ordre de grandeur d’au moins 128 bits, mais dans notre exemple prenons le corps \mathbb{Z}_{727}et choisissons deux courbes E(-3,4) (y^2 = x^3-3x+4) et E(-3,0) (y^2 = x^3-3x+4). Les deux courbes semblent proches (seul le paramètre b change).

Cependant la première a un ordre de 734 (2 x 367) et la seconde a un ordre de 728 (8 x 7 x  13). Cela a un impact significatif sur l’usage de la courbe en cryptographie. En effet nous utilisons la seconde courbe pour effectuer du Diffie-Helmann et que nous choisissions mal notre point G de départ, il pourrait être dans un sous-groupe d’ordre 7 ou 13, permettant alors une brute force alégé pour l’attaquant. Le code ci dessous explicite avec un point de la courbe à l’aide du logiciel sage (apt-get install sagemath) :

sage: Z = Zmod(727)
sage: E = EllipticCurve(Z, (-3,0))
sage: P = E(683, 340)
sage: P.order()
7
sage: P, 2*P,3*P,4*P,5*P,6*P,7*P,8*P
((683 : 340 : 1),
 (326 : 254 : 1),
 (491 : 531 : 1),
 (491 : 196 : 1),
 (326 : 473 : 1),
 (683 : 387 : 1),
 (0 : 1 : 0),
 (683 : 340 : 1))

Dans notre example, il est assez facile de voir que l’ordre est friable car le nombre de départ est petit et nous pouvons aisément le factoriser. Mais si nous avons des ordres de 256 bits; cela devient beaucoup moins trivial de déceler la présence d’un facteur de quelques dizaines de chiffres.

Attaque sur le temps d’éxécution de la multiplication d’un point

Comme nous l’avons vu, le principe du ECDLP repose sur la multiplication d’un point G de la courbe par un scalaire k secret.

Cette opération peut être réalisé de façon basique en additionnant k fois le nombre G

kG = G + G + \ldots + G

Mais nous pouvons être plus rapide et réduire le nombre d’opération en décomposant k en puissance de 2.  Par exemple si k = 18, au lieu de faire 18 additions successives, nous pouvons obtenir le résultat en 5 opérations en remarquant que 18 = 16 + 2 :

2G = G + G
4G = 2G + 2G
8G = 4G+4G
16G = 8G + 8G
18G = 16G + 2G

 Cependant nous avons aussi vu l’opération d’un doublement d’un point et celle de l’addition de deux points variaient : la constante m n’est pas la même.

Une attaque par canaux auxiliaire consiste à mesure le temps des différents calculs pour (et en déduire s’il s’agit d’un doublement ou d’une addition) et ainsi réduire le champs des valeurs possibles du scalaire k.

Heureusement, certains mathématiciens ont pensé à ce problème et proposé  les fameuses équations d’Edwards (dont nous parlions plus haut) : x^2 + y^2 = 1 +dx^2y^2. Ces courbes sont elliptiques sous la condition que $d^5 \neq d$. Mais leur intéret que l’opération de doublement d’un point ou de somme de deux points distincts est identique. Nous vous laissons lire cette présentation pour vous en convaincre pleinement.

Le paramètre b

Bien que les attaques par canaux auxiliaires soient bien connues, en pratique peu de courbes sont de la forme d’Edwards et les courbes les plus utilisées sont de la forme de Weierstrass simplifiée. Il ne vous aura pas échappé que dans le calcul d’un point (doublement ou addition de deux points disctints) la variable b n’est jamais utilisée. L’idée de cette attaque est d’utilisé une courbe avec un ordre friable qui varie d’un facteur b par rapport à une courbe sûre.

Si l’hôte distant ne vérifie pas que le point est sur la bonne courbe, nous pouvons par essaie successif et en utilisant le théorème des restes chinois (encore lui) retrouver le secret de notre victime.

L’idée est alors la suivante :

  • Bernard et un attaquant se sont mis d’accord sur une courbe y^2 = x^3 + ax+b
  • L’attaquant propose d’utiliser le point G
  • Bernard pas méfiant utilise le point G et son secret S_B afin de renvoyer S_BG

Ce que Bernard ignore, c’est que G n’est pas sur la courbe retenue mais sur la courbe y^2 = x^3 + ax+b' qui a un ordre friable (comprendre plein de petit facteur). Le point G en question a d’ailleurs un ordre petit.

  • L’attaquant récupère le point qui est un point valide de sa courbe (en effet nul part dans les calcules le coefficient b n’est utilisé) et rapidement obtient une équation C_1 = S_B \mod N_1

L’attaquant réitère l’opération avec à chaque fois un point G d’ordre différent.

Au bout du compte, l’attaquant obtient un système d’équation :

C_1 = S_B \mod N_1
C_2 = S_B \mod  N_2
\vdots
C_e = S_B \mod N_e

Ce système lui permet à  l’aide du théorème des restes chinois de retrouver le secret S_B de Bernard.

Moralité de l’histoire : Bernard doit toujours vérifier que les points qu’on lui soumet sont bien des points de la courbe.

Pour plus d’information, vous pouvez lire le papier de recherche sur le sujet.

Préparez-vous à l’inconnu !

De façon générale, il faut être très méfiant sur les courbes elliptiques dès lors que les paramètres ne sont pas justifiés de manière claire et détaillée. Il y a déjà le cas de valeurs parachutées qui se sont avérées plus que douteuses par la suite.

Il ne faut pas non plus sous-estimer les attaques non-publiques ou qui pourraient voir le jour prochainement.

Mais alors pourquoi diable utiliser des courbes elliptiques ?

Voici la principale réponse à cette question :  les algorithmes sur courbes elliptiques nécessitent pour une sécurité équivalente moins de ressource.

jshmendes@vmhost:~$ openssl speed ecdsap256 dsa2048 rsa2048 rsa4096
                             sign     verify     sign/s verify/s
rsa 2048 bits              0.001124s 0.000033s    889.4  29557.2
rsa 4096 bits              0.008078s 0.000123s    123.8   8129.2
dsa 2048 bits              0.000391s 0.000409s   2554.6   2444.8
256 bit ecdsa (nistp256)   0.0001s   0.0001s    10919.0   8186.3

Notamment la signature est une action beaucoup plus rapide sur les courbes elliptiques et permet de dégager de la ressource pour faire autre chose. Rappelez vous que dans le cas d’une négotiation TLS c’est le serveur qui a le dernier mot sur le choix de la suite cryptographique et il doit aussi effectuer énormement d’opération de signature : Il a donc tout intérêt à choisir un algorithme sur courbes elliptiques.

Bref, on espère avec tout cela que les courbes elliptiques sont des objets moins obscures.

Si vous avez encore des doutes, n’hésitez pas à poser vos questions en commentaire.

Publié dans Cryptographie Asymétrique, Uncategorized | Tagué , , , , | 1 commentaire

Compression et chiffrement

L’utilisation de la cryptographie n’a pas de finalité en soi : elle sert un objectif particulier qui peut varier suivant le contexte et s’insère dans le traitement de données que l’on souhaite protéger.

Dans quel ordre est-il plus pertinent de réaliser les opérations de chiffrement et de compression de données ?

On a alors un chance sur deux de se planter :

  • Soit on répond « on compresse puis on chiffre »
  • Soit on répond « on chiffre puis on compresse »

La réponse peut paraître évidente à certains mais détaillons. Pour répondre rappelons deux choses :

Comment chiffre-t-on des données ?

Le propre du chiffrement est de décoréler un maximum le message original (en clair) de sa version chiffrée afin d’éviter que l’attaquant puisse retrouver l’original s’il intercepte le chiffré.

Comment compresse-t-on des données ?

Les algorithmes classiques de compression au contraire utilisent la réccurrence (i.e: la fréquence) de certains blops dans les données.

Voici deux exemples triviaux de compression de données sans perte :
« CCCCCCC » => 7*C
« CryptoBourrinCrypto » => Crypto1/3Bourrin2

Bien évidemment, les algorithmes modernes de compressions sont bien plus élaborés que ces deux exemples simplistes. Mais ces derniers illustrent une des logiques utilisées pour stocker des données en minisant la taille de la mémoire utilisée.

Du coup, si nos données sont chiffrées, donc avec une entropie forte. Les algorithmes de compression seront peu voir pas du tout efficaces.

Ainsi voyez-vous la réponse s’impose d’elle même : il vaut mieux commencer par compresser les données puis les chiffrer si l’on veut optimiser la taille du résultat pour des transmissions ou stockages. Car compresser du chiffrer, ça ne sert pas à grand chose sauf quand on s’appelle Microsoft et qu’on utilise des archives compressés comme fichier pour sa suite bureautique.

Le cas de Microsoft Office

En effet, Ms Office  depuis la version 2007, les extensions qui finissent en x (.docx, .xlsx, pptx, …) ne sont rien d’autres que des répertoires compressés. Nous pouvons donc les renommer en .zip et les ouvrir avec l’outils de Microsoft et comparer la version chiffrée et celle qui ne l’est pas. Regardons ce qui se passe dans le cas de l’utilisation de la fonction de confidentialité de Microsoft Word.

Nous avons rapidement créé un fichier Word et nous l’avons copié et chiffré la copie afin de comparer les tailles des deux fichiers puis nous avons ouvert l’archive de la version chiffré où on retrouve quelques méta-data et un « EncryptedPackage » faisant la même taille que le fichier originel.

Fichiers_office

On ne détaillera pas ici le mécanisme de chiffrement  d’Office qui mériterait bien un article à lui tout seul (un jour peut être). Mais nous voulions simplement voir comment il gérait le chiffrer/compresser : du coup nous avons la réponse : on compresse , on chiffre et on recompresse !

Un fichier chiffré peut-il être plus petit que sa version en clair ?

Avec de l’exemple précédent, certains nous diront que la réponse est évidente, le simple fait de chiffrer avec du symétrique par bloc c’est déjà rajouter a minima deux informations :

  • un vecteur d’initialisation (car si c’est pour faire de l’ECB, autant ne rien faire)
  • du bourrage à la fin du fichier

Ce n’est pas énorme mais cela suffit à avoir une taille strictement supérieure à l’original, suivant le mécanisme choisi on peut également avoir des entêtes (ou autre méta-données) à rajouter dans le fichier, mais parfois cela peut être un peu plus voir beaucou plus…

Le cas de S/MIME

Un grand classique pour illustrer cela est l’utilisation des messages S/MIME. En effet, le chiffrement peut poser problème en empéchant les messages de partir : Pas directement, mais par effet de bord. La plupart des systèmes de messagerie (notamment d’entreprise) ont des limites sur la taille du message qu’ils peuvent recevoir et transmettre pour des raisons tout à fait légitime de bon fonctionnement. Dans le cas contraire, imaginez les magnifiques attaques à base d’envoie de fichier de plusieurs giga, mais on s’éloigne du sujet.

Nous avons sur ce blog déjà abordé le S/MIME. Mais qu’il nous soit permis de rapidement rappeler que le S/MIME permet de chiffrer le contenu du corps d’un message MIME et ses pièces jointes. Rappelons aussi que le MIME est du pure ASCII, ainsi toutes les pièces jointes qui contiennent des caractères non imprimables sont convertis en base64 ce qui par définition multiple la taille du message par 4/3 mais si on rajoute le chiffrement qui s’applique au message en base64, le chiffrement rajoutant de l’entropie on se retrouve avec des caractères non-imprimables. On rajoute donc une nouvelle fois une conversion en base64 du chiffré soit une nouvelle augmentation de la taille du message de 4/3 : soit un total de 16/9.

 

Donc le chiffrement S/MIME multiplie la taille du message par 1,33 (1.78 par rapport aux pièces jointes) : c’est pas rien quand même !

Voilà, ce sont des petites considérations à garder en tête quand vous devez calmement expliquer au directeur financier que le chiffrement c’est bien, mais qu’il ne peut pas envoyer le bilan financier en S/MIME car le message est « tros gros » alors que tout le COMEX attend le document pour avant-hier…

Une petite image pour méditer pendant vos vacances :

rockdriving_smime

 

Publié dans Cryptographie Symétrique, Système, Uncategorized | Tagué | Laisser un commentaire

Cher Recruteur

Dans un poste depuis plusieurs années et pas franchement très heureux, nous avons souhaité en changer. Nous nous sommes donc mis à l’écoute du marché scrutant les offres à la recherche de la perle rare : Vous savez le fameux boulot qui combine une mission intéressante, des conditions correctes et le tout dans un endroit sympathique, tout cela étant vous en conviendrez très subjectif. Car comme nous disait un de nos professeurs en Résistance de Matériaux (#MyPathToInfoSec), « Il n’y a pas de bon ou mauvais matériaux, il y a un matériaux qui répond à un besoin précis ». Et chacun a ses attentes quand il cherche un emploi.

Nous avons passé un nombre certain d’entretiens et en sommes souvent sorti déçu : Rares sont les fois où les recruteurs ont su nous démontrer de l’intérêt pour le travail offert car souvent après avoir été cuisiné et harcelé de questions sur notre parcours, nos compétences, nos motivations, vient le moment pendant lequel les recruteurs nous permettent de poser quelques questions. Systématiquement nous posions la question « Et pourquoi devrais-je venir travailler chez vous ? ». Question très souvent suivie d’un échange de regard surpris entre recruteurs et presque toujours d’une réponse peu convaincante.

Ce constat fait particulièrement écho dans le contexte où beaucoup se plaignent de la pénurie de talents en sécurité des systèmes d’information, de ne pas trouver de candidat, de ne pas remplir les formations en sécurité.

Voici quelques notes en vrac fondés sur des retours d’expériences personnelles ou de connaissances :

Tout d’abord la description de poste :

  • La fiche de poste digne de l’incipit des Confessions de Jean-Jacques Rousseau : Tellement ambitieuse qu’une fois lu, même les plus vaillants membres de l’équipe se disent qu’ils n’ont pas le niveau pour postuler (par ex: Demander un doctorat pour faire de l’administration de pare-feu):  Au final les candidats retenus ne sont pas adaptés et/ou surqualifiés et ne donnent pas suite : Chers recruteurs, soyez honnêtes !
  • La fiche multifonction : on a déjà parlé de ce fameux syndrome  du couteau suisse mais il est tellement récurrent. Combien de fiches de poste peut-on lire où il est demandé au candidat d’être à la fois expert en réseau, en méthodologie EBIOS et en rétroconception x64 sur MIPS : Chers recruteurs, une fois encore soyez réalistes !
  • Les postes « carte blanche » : à la mode avec l’arrivée de ce nouveau règlement. Les entreprises prennent conscience du besoin d’avoir un(e) monsieur/madame sécurité et c’est tant mieux, et partant d’un honnête constat qu’ils n’y connaissent rien ou presque, souhaitent recruter un sachant. Mais ils veulent surtout/seulement recruter un responsable qui pourra être désigné comme coupable le moment venu. Ce RSSI se verra confier un titre honorifique mais quasiment aucune liberté d’action car pas de soutien de la hiérarchie et/ou pas de budget.  Dans la gestion de la SSI, le recrutement d’un responsable n’est pas une fin en soi mais uniquement la première étape d’un long et douloureux chemin : Chers recruteurs, soyez cohérent dans votre logique et donnez nous les moyens de vos ambitions !

Ensuite, les offres regorgent de l’expression « packages attractifs ». Même s’il est plaisant pour un candidat de savoir que son salaire sera élevé, ce n’est pas le seul critère de décision et bien souvent pour les passionnés, il ne constitue pas l’élément le plus important.  Faire la liste exhaustive de ces critères est très compliqué car les besoins évoluent au fil du temps, des profils et sont souvent très personnels. Mais citons en quelques uns qui nous paraissent parmi les plus importants:

  • Travailler sur des objectifs concrets pour une mission en laquelle on croit : On ne parle pas forcement des gens qui dorment en slip Bleu-Blanc-Rouge et qui veulent travailler à la Piscine. Mais sachez que la motivation est aussi de savoir que ce que l’on fait, ce que l’on protège est utile. La complexité des systèmes informatiques mais aussi des organisations qui les utilisent rend parfois difficile voir impossible de comprendre l’utilité de son job.  D’autres ne souhaiteront pas travailler pour les  Qosmos, Amesys ou autre Suneris solution parce que cela ne correspond pas à leurs éthiques et valeurs morales.
  • Travailler dans un environnement stimulant : Il est pour certains aussi important de savoir qu’ils seront immergés dans un milieu stimulant : challenge technique, liberté de proposer et tester des solutions novatrices. Cela peut paraitre anecdotique mais beaucoup d’entre nous sommes avant tout des gens curieux et nous aimons bidouiller, retourner un problème dans tous les sens pour en proposer la solution qui nous parait la meilleure et pas seulement nous limiter à implémenter la solution rapide, économique, temporaire (pour les dix prochaines années) mais inélégante.
  • Travailler sans stress : C’est un besoin très personnel, chacun ne ressent ni ne gère les émotions de la même façon. Mais globalement personne n’aime subir de stress de façon continue : pourtant on voit souvent dans les annonces des qualités requises « savoir gérer le stress » (Note : le nombre de retours sur une recherche sur le mot clé « stress » sur un site d’annonce est d’ailleurs assez frappant) ou des choses du genre. On a du mal à comprendre le pourquoi du comment. Si un employé en est à devoir gérer le stress, c’est que quelqu’un dans la boite ne fait pas son job (i.e n’assume pas ses décisions). On conçoit le travail sous pression ou dans l’adrénaline, et on peut même aimer cela. Mais le stress ? Faudra qu’on nous explique !
  • Travailler dans une équipe : La sécurité ne doit pas être perçue comme la cinquième roue du carosse. Nous sommes sensibles un supérieur qui sait relayer les messages entre les différentes équipes et résoudre les sources de tensions pour faire de la sécurité une démarche intégrée. Cette dernière expression peut paraître un peu bateau. Mais il faut arréter de nous faire croire que la sécurité est uniquement une affaire de spécialistes. L’émulation entre collègues (SSI ou autre) est aussi une source d’enrichissement pour compléter notre vision d’un problème.
  • Avoir la capacité de continuer à apprendre : cela est peut-être le plus important. Les technologies avancent tellement vite que c’est une nécessité absolue de se former en continu. Il est vrai que cela a un coût important et en plus récurrent (notamment quand on va chez SANS). Mais il participe aussi à montrer à vos employés que vous les valorisez. Et cette formation peut avoir différentes formes. Certes, la plus évidente reste d’envoyer régulièrement les gens en formation chez feu-hsc ou autre. Mais ce n’est pas la seule manière, citons aussi les participations à des conférences où on apprend souvent autant pendant les présentations qu’en échangeant avec différentes personnes pendant les pauses. N’oublions pas encore une fois l’émulation et l’échange entre collègues. Nous apprenons beaucoup de nos collègues et on espère modestement qu’ils apprennent aussi grâce à nous.

Bien sur, il y a aussi des aspects extra-professionnels qui peuvent entrer en ligne de compte : la situation géographique des locaux (Tout le monde n’est pas fan de Paris), la flexibilité sur les horaires, travail depuis la maison, le nombre de jour de congés, la facilité de combiner vie privée vs professionnelle, le droit à la déconnexion etc. Mais tout cela n’est pas propre à la SSI.

En conclusion, les quelques points cités ci-dessus ne sont que des exemples que nous avons pu recueillir à droite ou à gauche en échangeant sur notre vision du métier. En résumé, chers recruteurs ne demandez pas uniquement ce que votre candidat peut faire pour vous, mais plutôt ce que vous pouvez faire pour lui !

Car vous remarquerez que même s’il y a une pénurie évidente de talent en SSI, les entreprises où il fait bon travailler, elles, ne s’en plaignent pas !

 

Publié dans Sensibilisation, Uncategorized | Laisser un commentaire

Les classiques de RSA

Comme vous le savez très probablement, le produit de deux nombres premiers peut servir à former un modulus de RSA. La factorisation de grand nombre est pour l’instant un exercice complexe et cette même complexité à elle seule garantit la sécurité de l’algorithme de chiffrement RSA. Cependant plusieurs choses peuvent le fragiliser.

Outre, le cas bien connu du partage d’un même nombre premier p dans plusieurs modules distincts (au quel cas, un simple calcul de pgcd suffit à extraire les nombres premiers et donc à factoriser les moduli), dont nous avons donné un exemple avec les boitiers Juniper, il est parfois possible pour un attaquant de récupérer de l’information sans avoir à factoriser ces grands nombres.

Détaillons ici deux exemples bien connus :

Rappelons que dans le cas générale, la seule contrainte pour l’exposant public e est d’être premier avec \Phi{N}, et ce afin de garantir l’existence de son inverse d : l’exposant privé utilisé pour le déchiffrement  (ou la signature).

RSA et Bezout

Un premier cas classique est celui de l’utilisation du même modulus avec des exposants publics différents. Certes, nous ne pourrons pas à l’aide de cette technique factoriser le module RSA, mais nous pourrons facilement retrouver le message en clair.

Mathématiquement, cela se démontre ainsi :

Supposons que nous avons deux clés publiques {E1,N} et {E2,N}. Nous savons que pour un message donné le chiffré se calcule comme suit :

C_1 = M^{E_1} \mod N
C_2 = M^{E_2} \mod N.

Or si E1 et E2 sont premiers entre eux, nous savons d’après Bezout qu’il existe a et b tels que aE_11 + bE_2 = 1 et donc par conséquent que :

C1^a*C2^b = M^{a*E_1+b*E_2} = M^1 = M

Ce qui conclut notre démonstration.

Multiple chiffrement et théorème du reste chinois

De même, l’utilisation de moduli différents N_i  avec le même exposant public e permet également de casser le message.
Cependant, il y a une condition nécessaire : le nombre de messages chiffrés (avec des moduli tous différents) doit être au moins égal à « e ».

Avec les hypothèses, nous avons donc le système d’équation suivant :

C_1 = m^e \mod N_1
C_2 = m^e \mod N_2
\vdots
C_e = m^e \mod N_e

Ne reste alors plus qu’à résoudre ce système d’équation, en appliquant directement le théorème des restes chinois (dont nous en avons déjà évoqué ici. pour l’optimisation des ressources lors de calcul avec la clé privée).

En pratique, ces deux attaques  bien connues n’ont que peu d’application (en dehors des challenges :)), car généralement les hyptohèses ne sont pas vérifiées, notamment car la valeur de e est quasi-systématiquement 2^{16}+1 … Mais bon, sait-on jamais ?

Publié dans Cryptographie Asymétrique, RSA, Uncategorized | Tagué , , , , , | 1 commentaire