Discussion :

[akrogames]

Bonjour à tous,

J'espère que vous allez bien, moi je me casse un peu les dents sur des petit problème. Mais je suis pas assez fort pour m'en sortir en python.

Alors mon problème c'est que j'essaye de faire le cryptage RSA mais dans ma textNum() il faudrait que je convertisse ma chaine en caractère ASCII mais que le résultat soit une chaine de nombre et non un tableau comme j'ai fait.

Il faudrais aussi une fonction qui découpe une chaine par exemple: split("TOTO",2) = TO, TO

Vous voyez ?

Ensuite un problème de math, car je suis un piètre matheux.
Je dois résoudre d tel que 71*d mod 1008 = 1
mais je sais pas résoudre cela sous forme équation à 1 inconnu en Python

J'espère que vous pourrez m'aider

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
 
#On convertit le texte initial en texte ASCII
def textNum():
	text=raw_input("Votre texte: \n")
 
	text=map(ord,text)
 
	return text
 
#Il faut qu'on retourne la clé publique et privé 
def key():
	#On prend 2 nombres premiers au hasard p et q
	#Pour les tests on utilise p=29 q=37
 
	p=29
	q=37
	n= p*q
 
	x=(p-1)*(q-1)
 
	#Pour les tests on prend e=71 où e est normalement choisit au hasard
 
	e=71
 
	#Trouver d en résolvant l'équation e*d%x=1
	d=1079
	y=e*d%x
 
	keyPub=[e,n]
	keyPriv=[d,n]
 
	print keyPub
	print keyPriv
 
#On crypte à l'aide de la clé publique et du texte sous forme ASCII
def RSACrypt():
 
#On décrypte à l'aide de la clé privée et du texte crypté
def RSADecrypt():
 
 
 
texte = textNum()
key()

Merci de votre aide bonne journée

[tyrtamos]

Bonjour,

Je dois résoudre d tel que 71*d mod 1008 = 1

J'adore ce genre de torture!

71*d mod 1008 = 1 , ça veut dire: le reste de la division entière de (71*d) par 1008 est égal à 1.

Ça veut donc dire que 71*d=k*1008+1, k étant un coefficient entier.

Donc que d=(k*1008+1)/71. Mais k et d doivent rester entier.

Cela revient à chercher toutes les valeurs de k (entier) pour que (k*1008+1)/71 soit entier. Il y en a, a priori, une infinité.

Voilà une liste de valeurs de d qui conviennent:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
[71,1079,2087,3095,4103,5111,6119,7127,8135,9143,10151,11159,12167,13175,14183]

avec les valeurs du coef k correspondants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
[5,76,147,218,289,360,431,502,573,644,715,786,857,928,999]

Vérification: tu vois bien qu'avec les 1ères valeurs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
71*71 % 1008 => 1  et d = (5*1008+1)/71 => 71
71*1079 % 1008 => 1  et d =(76*1008+1)/71 => 1079
etc...

Avec ma calculatrice en ligne (http://calculext.jpvweb.com), tu peux calculer autant de valeurs que tu veux (tant que le calcul est inférieur à 8 secondes).

Pour le calcul de d, tu recopies (copier-coller) la formule suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
[(k*1008+1)/71 for k in range (1,1000) if int((k*1008+1)/71)==(k*1008+1)/71]

Et pour calculer les valeurs de k:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
map(lambda x: (x*71-1)/1008,[(k*1008+1)/71 for k in range (1,1000) if int((k*1008+1)/71)==(k*1008+1)/71])

Désolé pour la beauté de la formule, mais il faut que tout tienne sur une seule ligne, ce qui produit quelques redondances.

Je précise aussi que cette calculatrice est configurée pour que '/' donne une division décimale et non entière, sinon, ça ne marcherait pas.

Tu peux changer le coeff 1000 par une valeur plus grande. Par exemple, avec une valeur de k pouvant aller jusqu'à 1000000, tu trouveras les 14085 valeurs de d qui satisfont ton équation: quelle chance tu as!

Tyrtamos

[akrogames]

Merci pour cette explication !

Cela me convient parfaitement.

Par contre pourrais tu m'expliquer comment on fais pour découper des chaines comme je l'ai expliqué plus haut ?


Merci

[tyrtamos]

Par contre pourrais tu m'expliquer comment on fais pour découper des chaines comme je l'ai expliqué plus haut ?

Il y a certainement plus subtil et plus "pythonique":

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
def decoupe2(x):
    L=[]
    for i in range(0,len(x),2):
        L.append(x[i:i+2])
    return L
 
x="n'importe quoi"
print decoupe2(x)

Ce qui affiche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
["n'", 'im', 'po', 'rt', 'e ', 'qu', 'oi']

Tyrtamos

[oiffrig]

Pour ta résolution, il y a aussi une version plus mathématique que la force brute
Ton équation est équivalente à 71*d - 1008*k = 1, avec k entier quelconque. C'est une équation diophantienne, la résolution n'est pas bien compliquée :
On a une solution particulière: k = 5, d = 71 (s'obtient à partir de l'algorithme d'Euclide pour le PGCD de 1008 et 71)
Ensuite avec les théorèmes d'arithmétique on obtient les autres

[tyrtamos]

Pour oiffrig:

Merci de la référence à Diophante, je l'avais oublié celui-là. (http://fr.wikipedia.org/wiki/%C3%89q..._diophantienne)

Ta solution m'intéresse, mais tu n'en dis pas assez.

=> Comment as-tu trouvé les valeurs k = 5, d = 71 ?
=> le pgcd de 1008 et 71 est égale à 1 (71 est premier): on fait quoi avec ça?
=> comment trouve-t-on les autres valeurs?

Merci d'avance!

Tyrtamos