Chaine de caractère et arithmétique

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 ? :roll:

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:

---

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

Bonjour,

Citation:

---

Envoyé par akrogames

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:

---

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:

---

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:

---

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:

---

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:

---

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! :D

Tyrtamos

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

Citation:

---

Envoyé par akrogames

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:

---

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:

---

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

---

Tyrtamos

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

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

Solution particulière:
On écrit l'algorithme d'Euclide, ensuite on "remonte" en exprimant le PGCD en fonction des restes successifs

Code:

---

1 2 3 4

1008 = 14 * 71 + 14 => 14 = 1008 - 14*71 71 = 5*14 + 1 => 1 = 71 - 5*14 = 71*71 - 5*1008

---

On pose d0 = 71, k0 = 5
Si (d, k) est solution, alors

Code:

---

1 2 3 4 5

71*d - 1008*k = 71*d0 - 1008*k0 71*(d - d0) = 1008*(k - k0) => 1008 divise d - d0 (théorème de Gauss) => il existe a entier tel que d = d0 + 1008*a (on a à ce stade les solutions de l'équation de départ, k ne nous intéresse pas) de même il existe b entier tel que k = k0 + 71*b

---

Réciproquement si (d0 + 1008*a, k0 + 71*b) est solution, alors on a (facilement) a = b

D'où les solutions, (d0 + 1008*a, k0 + 71*a), avec a entier relatif

Bonjour,

Pour oiffrig:

Merci de ce rappel!

Ça ne semble pas conduire à un codage plus simple, mais ce n'est pas mal de se reposer sur les fondamentaux! :D

Tyrtamos

Merci pour vos réponses.

Existe t'il une fonction python pour convertir une chaine de caractère en ASCII qui ne convertit pas dans un tableau...

Bonjour,

Citation:

---

Envoyé par akrogames

Existe t'il une fonction python pour convertir une chaine de caractère en ASCII qui ne convertit pas dans un tableau...

---

Je ne comprends pas ta question. Tu pourrais la préciser et donner des exemples?

Est-ce que tu parles de pb d'encodage?

Tyrtamos

Non en fait j'essaye d'avoir une fonction comme ord()

Qui transforme la chaine en une suite ASCII

exemple:
"bebe" = "9810198101"

car b=98 et e=101

Tu comprend ?

Car j'utilise map(ord,"bebe") mais sa me met dans un tableau c'est triste :( :D

Mon but ultime est:

d'avoir une chaine par exemple: "12345678912"
De la découpé par 3 par exemple: [123,456,789,120]
On rajoute un 0 pour toujours avoir 3 chiffre
Voilà mon but ultime:D

Si vous y arrivez dites moi comment faire.

Merci

Bien, allons-y

On peut passer de "bebe" à "9810198101" de la façon suivante:

Code:

---

1 2	''.join(map(str,map(ord,"bebe")))

---

Ce n'est pas mystérieux:

map(ord,"bebe") donne [98, 101, 98, 101]

map(str,[98, 101, 98, 101]) donne ['98', '101', '98', '101']

et

''.join(['98', '101', '98', '101']) donne "9810198101"

Pour découper par groupe de 3 chiffres, tu peux utiliser ce que je t'ai donné plus haut en le modifiant:

Code:

---

1 2 3 4 5 6 7 8 9

def decoupe3(x): L=[] for i in range(0,len(x),3): L.append(x[i:i+3]) return L   x="9810198101" print decoupe3(x)

---

Ce qui affiche: ['981', '019', '810', '1']

Je n'ai pas bien compris le "On rajoute un 0 pour toujours avoir 3 chiffres". Je suppose que cela ne concerne que le dernier ('1' dans l'exemple).

Pour ajouter des "0" à gauche dans une chaine X jusqu'à obtenir une longueur donnée lg, il suffit de faire ceci:

Code:

---

1 2 3 4

X='1' lg=3 X=X.zfill(lg)

---

X est devenu: '001'

Ce qui veut dire qu'une fois obtenue la liste L=['981', '019', '810', '1'], il suffit d'ajouter l'instruction L[-1]=L[-1].zfill(3) pour que L devienne ['981', '019', '810', '001']. Si la dernière valeur possède déjà 3 chiffres, zfill(3) ne fait rien.

Ok?

Tyrtamos

génial tyrtamos

Je te redit si cela marche cette après midi.