Le RSA est-il fiable ?

Modélisations Mathématiques

Présentation

group

Etude de la cryptographie informatique

L’équipe :

  • Damien Dumas (Système de Vigenère)

  • Remi Cros (Système de Vigenère)

  • Vincent Fougeras (Système de César)

  • Alex Fabre (Système de Vernam)

Le rapport complet est consultable ici

Le chiffre de Vernam

Le chiffre de Vernam ou masque à clef jetable se base sur deux principes:

  1. Une clef aléatoire

  2. Une clef de la même taille que le message

	VERNAM #message
+	MAISON #clef
=>	RFGBVH #chiffre

Générer une clef

Reçoit la longueur du message en paramètre, et retourne une clef composée aléatoirement.

def KeyGen(message):
	key=""
	dic=string.ascii_uppercase
	for x in range(0,len(message)):
		letter=dic[randint(0,25)]
		key=key+letter
	key=key.upper()
	return key

Attention

Les ordinateurs sont des machines déterministes il n’existe pas de nombre réellement aléatoires. On parle plutôt de nombres pseudo-aléatoire.

Chiffrer le message

Combiner le message avec la clef. On réalise l’opération sur la valeur des caractères en binaire. Cette opération binaire s’appelle le XOR, ou « Ou exclusif ».

=> M xor K = C 	#chiffrement
=> C xor K = M 	#déchiffrement

Le xor

def Xor(s1, s2):
    if not s1 or not s2:
        return ''

    maxlen = max(len(s1), len(s2))

    s1 = s1.zfill(maxlen)
    s2 = s2.zfill(maxlen)

    result  = ''

    i = maxlen - 1
    while(i >= 0):
        s = int(s1[i]) + int(s2[i])
        if s == 2: #1+1
            result = "%s%s" % (result, '0')
        elif s == 1: # 1+0
            result = "%s%s" % (result, '1')
        else: # 0+0
            result = "%s%s" % (result, '0')

        i = i - 1;
    return result[::-1]

Le chiffrement

def CreateBin(message,key):
	code=""
	for x in range(0,len(message)):
		lettreM=bin(ord(message[x])-64)[2:]
		lettreK=bin(ord(key[x])-64)[2:]
		lettreC=Xor(lettreM,lettreK)
		print lettreM+" xor "+lettreK+" = "+lettreC
		lettreC=(int(lettreC,2)+64)
		code=code+chr(lettreC)
	return code

Vernam Application

L’application complète : ici

Le chiffrement RSA

Le chiffre RSA est actuellement le chiffre le plus sur du fait de sa rapidité d’utilisation et des calculs énormes nécessaires pour être craqué. Les deux principes du RSA sont:

  1. Utilisation d’une clef pour chiffrer et d’une autre pour déchiffrer.

  2. Création des clefs avec de très grands nombres premiers.

Générer le couple de clefs

On commence par générer deux très grands nombres premiers p et q. Plus ils seront grands, plus ils assureront la sécurité du chiffre.

Liste des nombres premiers

def premier(max):
	# The firsts 100 firsts are in range(0,548) (547 is number 100)
	listNPremiers=[]
	listNPremiers.append(2)
	start_time=time.time()
	for i in range(3,max):
		for prime in listNPremiers:
			if i%prime==0:
				event=False
				break
			if prime>sqrt(i):
				event=True
				break
		if event:
			listNPremiers.append(i)
	interTime=str(time.time() - start_time)
	fichier.write("    Recherche des deux premiers terminee en "+interTime+" secondes.\n")
	return listNPremiers

n et φ

  • module de chiffrement n

n = p*q
  • Indicatrice d’Euler φ

φ(n) = (p-1)*(q-1)

Plus p et q sont grand plus le code sera sur

Exposant de chiffrement e

Il est premier avec φ(n). On utilise l’algorithme d’Euclide

def euclide(a,b):
	#Return the higher common divider of a and b. Used to test if a and b are firts together.
	if (b==0) :
		return a
	else :
		r=a%b
		return euclide(b,r)

Exposant de déchiffrement d

Il est premier avec e. On utilise l’algorithme d’Euclide étendu Il doit être inférieur à φ

def euclidextended(a,b):
	# r entier (naturel) et  u, v entiers relatifs tels que r = pgcd(a, b) et r = a*u+b*v
	# https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return y

Couple de clefs

On a maintenant le couple de clefs:

clef-publique : (n,e)
clef-privee : (n,d)

Chiffrement

Chaque caractère va être élevé à l’exposant e modulo n. C’est l’exponentiation modulaire réalisée avec la fonction pow.

code=pow(message,exposant-de-chiffrement,modulo)
#et inversement
message=pow(code,exposant-de-dechiffrement,modulo)

Chiffrement

def expmodsecured(message,e,m):
	#Fonctionne parfaitement !
	code=""
	i=0
	blocs=(len(message)/2)
	r=(len(message)%2)
	while(i<blocs*2):
		c=ord(message[i])
		k=ord(message[i+1])
		while len(str(c))<3:
			c='0'+str(c)
		while len(str(k))<3:
			k='0'+str(k)
		b6=str(c)+str(k)
		b6=pow(int(b6),e,m)
		while len(str(b6))<len(str(m)):
			b6='0'+str(b6)
		code=code+str(b6)
		i=i+2
	if r==1:
		c=ord(message[i])
		while len(str(c))<3:
				c='0'+str(c)
		b6=pow(int(b6),e,m)
		while len(str(b6))<len(str(m)):
			b6='0'+str(b6)
		code=code+str(b6)
	return code

Déchiffrement

def expmodinverted(intarray,d,m):
	for i in intarray:
		message=""
		letter1=""
		letter2=""
		letters=pow(int(i),d,m)
		print letters
		if len(str(letters))>3:
			letter1=str(letters)[:3]
			print letter1
			letter2=str(letters)[3:]
			mot=chr(int(letter1))+chr(int(letter2))
			print mot
			message=message+mot
		else:
			letter=chr(letters)
			print letter
			message=message+letter
	return message

RSA Application

L’application complète : ici

Conclusion

Le chiffre parfait n’existe pas. Les attaquants sont de plus en plus nombreux, le nombre de connexions sécurisé croit avec le nombre d’utilisateurs en plus sur internet chaque jour, et c’est bien en multipliant les chiffres parfois en mixant les méthodes comme avec la cryptographie hybride que la sécurité continuera à évoluer.

Merci

Damien Dumas, Rémi Cros, Alex Fabre, Vincent Fougeras Janvier 2015