Discussion :

[Chaka_Sobek]

Bonjour � tous,

Je me permets de poster ici apr�s de multiples tests infructueux.

En effet, j'ai g�n�r� une clef RSA via openssl ($openssl genrsa macle.pem 512) de 512 bits dans le format base64. Je voulais r�cup�rer l'int associ� � cette clef via python en utilisant la biblioth�que base64 et plus pr�cis�ment base64decode avec la commande int.from_bytes(b64decodes(la_str_clef),'big') puis je la r�cup en hexa puis en int base 10 mais le r�sultat n'est jamais le bon j'ai l'impression ...

Auriez-vous des pistes pour r�gler ce soucis ?
P.S. je fais cette manip pour ensuite faire le pgcd des cl�s et regarder si elles partagent des facteurs communs.

Merci par avance pour vos retours.

Chaka

[Sve@r]

Bonjour

Je r�fl�chis � ton truc car il parait logique... mais je sens qu'il y a un cafouillage. Et je crois que le cafouillage se situe au niveau de base64 car cet outil n'est pas d�di� � convertir une clef RSA en int. C'est un outil d�di� � convertir un binaire en ascii

Exemple

Code python :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
>>> x=base64.b64encode(b"123")
>>> x
b'MTIz'
>>> y=base64.b64decode(x)
>>> y
b'123'
>>> int.from_bytes(y, 'big')
3224115
>>> int.from_bytes(y, 'little')
3355185

De l�, si tu utilises un outil non adapt�, l'int que tu obtiens ne peut pas �tre correct...

[Chaka_Sobek]

Bonjour

Je r�fl�chis � ton truc car il parait logique... mais je sens qu'il y a un cafouillage. Et je crois que le cafouillage se situe au niveau de base64 car cet outil n'est pas d�di� � convertir une clef RSA en int. C'est un outil d�di� � convertir un binaire en ascii

Exemple

Code python :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
5
6
7
8
9
10
>>> x=base64.b64encode(b"123")
>>> x
b'MTIz'
>>> y=base64.b64decode(x)
>>> y
b'123'
>>> int.from_bytes(y, 'big')
3224115
>>> int.from_bytes(y, 'little')
3355185

De l�, si tu utilises un outil non adapt�, l'int que tu obtiens ne peut pas �tre correct...

Merci beaucoup pour ton message !

Effectivement, ton explication parait logique ! N'ayant pas trouv� d'autre biblioth�que qui faisait �a, j'ai pris la seule dont j'avais connaissance qui pouvait traiter mon probl�me.

Aurais-tu une solution/recommandation/conseil afin que j'obtienne le bon r�sultat ?

Merci par avance

[Sve@r]

Aurais-tu une solution/recommandation/conseil afin que j'obtienne le bon r�sultat ?

Ben en fait je n'ai pas compris quel r�sultat tu cherches. Tu veux l'int correspondant � la clef c'est �a?
Mais la clef ce n'est pas un int !!! C'est une combinaison de plein d'int !!!

Principe de base de RSA

• choisir P et Q premiers (exemple 89 et 97)
• calculer delta=(P-1) * (Q-1) => 8448
• calculer N=P*Q => 8633
• choisir e tel e premier avec delta => pgcd(e, delta)=1. Exemple e=7, pgcd(7, 8448) est bien �gal � 1 => la clef publique sera le coupe (N, e) soit ici (8633, 7)
• choisir une valeur "d" telle que (d * e) modulo delta = 1. Exemple d=1207 => 1207 * 7 = 8449 et 8449 modulo 8448 est bien �gal � 1. La clef priv�e sera le couple (N, d) soit ici (8633, 1207)

A partir de l�, pour chiffrer une valeur (exemple) 555 sur la clef publique (N, e) on calcule (555^e) modulo N soit (555^7) % 8633 = 2928
Et pour d�chiffrer 2928 avec la clef priv�e (N, d) on calcule (2928^d) modulo N soit (2928^1207) % 8633 = 555

Et pour signer c'est dans l'autre sens. Exemple on veut signer 667 via la clef priv�e (N, d) on calcule (667^d) modulo N soit (667^1207) % 8633 = 8625
Et on v�rifie la signature avec la clef publique (N, e) via (8625^e) modulo N soit (8625^7)%8633 ce qui redonne 667.

Ci-joint un petit essai quand j'ai tent� du chiffrement en Python: Alice envoie un message vers Bob en utilisant la clef publique de Bob, et signe ce message en utilisant sa clef priv�e.
Et Bob d�chiffre le message avec sa clef priv�e et v�rifie qu'il vient bien de Alice en checkant sa signature via la clef publique de Alice.

Code python :

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
#!/usr/bin/env python3
# coding: utf-8
 
from Cryptodome.PublicKey import RSA
from Cryptodome.PublicKey import RSA
from Cryptodome.Cipher import PKCS1_OAEP
from Cryptodome.Signature import PKCS1_PSS
from Cryptodome.Hash import SHA
 
message="Hello Woréld !!!"
print(message, type(message))
 
alice=RSA.generate(2048)
bob=RSA.generate(2048)
print(alice.publickey().exportKey())
print(bob.publickey().exportKey())
 
secret={
	"chiffre" : PKCS1_OAEP.new(bob.publickey()).encrypt(message.encode("utf-8")),
	"sign" : PKCS1_PSS.new(alice).sign(SHA.new(message.encode("utf-8"))),
}
 
final=PKCS1_OAEP.new(bob).decrypt(secret["chiffre"]).decode("utf-8")
print("ok déchiffrement" if message == final else "erreur chiffrement")
 
verify=PKCS1_PSS.new(alice.publickey()).verify(SHA.new(final.encode("utf-8")), secret["sign"])
print("%s signature (%s)" % ("ok" if verify else "erreur", verify))

[Chaka_Sobek]

Ben en fait je n'ai pas compris quel r�sultat tu cherches. Tu veux l'int correspondant � la clef c'est �a?
Mais la clef ce n'est pas un int !!! C'est une combinaison de plein d'int !!!

Principe de base de RSA

• choisir P et Q premiers (exemple 89 et 97)
• calculer delta=(P-1) * (Q-1) => 8448
• calculer N=P*Q => 8633
• choisir e tel e premier avec delta => pgcd(e, delta)=1. Exemple e=7, pgcd(7, 8448) est bien �gal � 1 => la clef publique sera le coupe (N, e) soit ici (8633, 7)
• choisir une valeur "d" telle que (d * e) modulo delta = 1. Exemple d=1207 => 1207 * 7 = 8449 et 8449 modulo 8448 est bien �gal � 1. La clef priv�e sera le couple (N, d) soit ici (8633, 1207)

A partir de l�, pour chiffrer une valeur (exemple) 555 sur la clef publique (N, e) on calcule (555^e) modulo N soit (555^7) % 8633 = 2928
Et pour d�chiffrer 2928 avec la clef priv�e (N, d) on calcule (2928^d) modulo N soit (2928^1207) % 8633 = 555

Et pour signer c'est dans l'autre sens. Exemple on veut signer 667 via la clef priv�e (N, d) on calcule (667^d) modulo N soit (667^1207) % 8633 = 8625
Et on v�rifie la signature avec la clef publique (N, e) via (8625^e) modulo N soit (8625^7)%8633 ce qui redonne 667.

Ci-joint un petit essai quand j'ai tent� du chiffrement en Python: Alice envoie un message vers Bob en utilisant la clef publique de Bob, et signe ce message en utilisant sa clef priv�e.
Et Bob d�chiffre le message avec sa clef priv�e et v�rifie qu'il vient bien de Alice en checkant sa signature via la clef publique de Alice.

Code python :

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
#!/usr/bin/env python3
# coding: utf-8
 
from Cryptodome.PublicKey import RSA
from Cryptodome.PublicKey import RSA
from Cryptodome.Cipher import PKCS1_OAEP
from Cryptodome.Signature import PKCS1_PSS
from Cryptodome.Hash import SHA
 
message="Hello Woréld !!!"
print(message, type(message))
 
alice=RSA.generate(2048)
bob=RSA.generate(2048)
print(alice.publickey().exportKey())
print(bob.publickey().exportKey())
 
secret={
	"chiffre" : PKCS1_OAEP.new(bob.publickey()).encrypt(message.encode("utf-8")),
	"sign" : PKCS1_PSS.new(alice).sign(SHA.new(message.encode("utf-8"))),
}
 
final=PKCS1_OAEP.new(bob).decrypt(secret["chiffre"]).decode("utf-8")
print("ok déchiffrement" if message == final else "erreur chiffrement")
 
verify=PKCS1_PSS.new(alice.publickey()).verify(SHA.new(final.encode("utf-8")), secret["sign"])
print("%s signature (%s)" % ("ok" if verify else "erreur", verify))

Merci pour ta r�ponse qui est tr�s claire !

En fait, quelqu'un m'a demand� de l'aide sur leboncoin pour un devoir mais son sujet me parait flou et j'ai donc cherch� de mon c�t� sans succ�s.

Ci-joint l'�nonc� :



et le projet 1 dont il est question


Ne connaissant pas le " Batch GCD" et n'ayant trouv� aucune documentation python dessus sur le web, je lui ai demand� ce qu'il en �tait et elle m'a r�pondu qu'elle supposait que c'�tait un pgcd classique ce qui paraissait �trange (d'o� mes b�tises de vouloir transform� cette cl� en un int qui n'a aucun sens et ne correspond � rien .... ^^' )

Je ne sais pas quoi faire pour ce batch gcd... Aurais-tu une piste ?

Encore d�sol� pour mes questions en cha�ne d'autant plus qu'elles n'ont pas de sens :/

[wiztricks]

Ne connaissant pas le " Batch GCD" et n'ayant trouv� aucune documentation python dessus sur le web

C'est l� qu'il est frustrant de ne pas voir comment vous vous d�patouillez avec votre moteur de recherche pour ne rien trouver sur Internet avec les mots cl�s "python batch gcd"...

- W

[Chaka_Sobek]

Je ne sais pas ce que vous avez trouv� en �crivant �a dans la barre de recherche mais, pour ma part, je n'ai trouv� aucune docu officiel python et aucune fonction d�j� impl�ment�e. J'ai trouv� ce truc concernant une impl�mentation en sagemath : https://facthacks.cr.yp.to/batchgcd.html .
Avez-vous trouv� autre chose ?

Merci par avance.

[Sve@r]

J'ai trouv� ce truc concernant une impl�mentation en sagemath : https://facthacks.cr.yp.to/batchgcd.html .

J'avais trouv� la m�me chose. Toutefois sagemath c'est du Python (mais les exemples sont en Python2 vu les print sans parenth�ses et les divisions utilis�es comme divisions euclidiennes).
Ensuite les exemples font appels � des outils qui semblent d�di�s � sage mais o� en regardant le r�sultat attendu, ne sont pas compliqu�s � r��crire en Python (je parle de producttree() utilis� dans batchgcd_faster())

Code python :

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
from math import gcd, floor
 
def producttree(X):
	result = [X,]
	while len(X) > 1:
		X = [(X[i-1] * (X[i] if i < len(X) else 1)) for i in range(1, len(X)+1, 2)]
		result.append(X)
	return result
 
def batchgcd_faster(X):
	prods = producttree(X)
	R = prods.pop()
	while prods:
		X = prods.pop()
		R = [R[floor(i/2)] % X[i]**2 for i in range(len(X))]
	return [gcd(r//n,n) for r,n in zip(R,X)]
 
print(batchgcd_faster([1909, 2923, 291, 205, 989, 62, 451, 1943, 1079, 2419]))
# output: [1909, 1, 1, 41, 23, 1, 41, 1, 83, 41]

PS: quelques erreurs toutefois dans les exemples dudit site. Ainsi le coeur de productree() c'est cette ligne X = [prod(X[i*2:(i+1)*2]) for i in range((len(X)+1)/2)] qui dit "pour chaque i je multiplie X[i*2] avec X[(i+1)*2]" ce qui, si X vaut [10, 20, 30, 40, 50, 60], multipliera 10 avec 30, puis 30 avec 50 et finit par un IndexError quand i passe � 2 !!! Et comme le r�sultat attendu c'est [200, 1200, 3000] c'est en r�alit� 10*20, 30*40 et 50*60 soit en fait X[i*2] * X[i*2+1]

[wiztricks]

J'ai trouv� ce truc concernant une impl�mentation en sagemath : https://facthacks.cr.yp.to/batchgcd.html .
Avez-vous trouv� autre chose ?

Ben ce truc, c'est du Python...

Pour le reste, tout d�pend de ce qu'on cherche: d'apr�s l'�nonc�, c'est un programme � r�cup�rer peu importe le langage dans lequel il a �t� cod�.

- W

[Chaka_Sobek]

Merci pour vos pr�c�dents messages.
J'essaye �a en d�but d'apr�s midi !

Bonne journ�e,
Et encore merci

Chaka

[Chaka_Sobek]

Bonsoir,

J'ai enfin bient�t fini... Pour le batch gcd, j'ai utilis� cette librairie https://pypi.org/project/batch-gcd/. Cependant un dernier probl�me se pose (je commence � en avoir marre...) : la fonction batch.gcd que j'utilise prend en argument plusieurs int � la suite (et non pas un tuple). Or mes int sont tous stock�es dans une liste et je n'arrive pas � tous les mettre en argument. J'avais pens� � faire un truc du style batch.gcd(i for i in mes_int) o� mes_int est une liste remplies d'int de taille variable en fonction des ex�cutions.

Auriez-vous une solution � mon probl�me ?

Merci par avance pour vos retours !

[Sve@r]

Auriez-vous une solution � mon probl�me ?

Tu appelles ta fonction en passant "�toile liste" en param�tre. Exemple la liste se nomme "data" (et contient une liste d'int) tu appelles batch_gcd(*data). C'est le unpacking.

Maintenant... je viens de t�l�charger et installer ce module mais il n'a rien apport� � mon code post� ce matin. Les deux donnent le m�me r�sultat (et le mien lui il acceptait bien un it�rable en param�tre !!!)
Peut-�tre un bench pourrait dire lequel des deux est le plus rapide... Je vais voir si j'en fais un...

[edit]
Ok, j'ai fait un petit bench

Code python :

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
46
47
48
49
#!/usr/bin/env python3
# coding: utf-8
 
import random
import timeit
from functools import partial
from math import gcd, floor
from batch_gcd import batch_gcd
 
def producttree(X):
	result = [X,]
	while len(X) > 1:
		X = [(X[i-1] * (X[i] if i < len(X) else 1)) for i in range(1, len(X)+1, 2)]
		result.append(X)
	return result
 
def batchgcd_faster(X):
	prods = producttree(X)
	R = prods.pop()
	while prods:
		X = prods.pop()
		R = [R[floor(i/2)] % X[i]**2 for i in range(len(X))]
	return [gcd(r//n,n) for r,n in zip(R,X)]
 
# Initialisation random
random.seed()
 
# Les fonctions à tester
fct={
	"batch_faster" : lambda l: batchgcd_faster(l),
	"batch_module" : lambda l: batch_gcd(*l),
}
 
# Les données à traiter
data=list(range(1, 10_001))
 
# Vérification fonctions donnent résultats identiques
assert(len(set(tuple(f(data)) for f in fct.values())) == 1)
print("Vérification fonctions ok")
 
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat=20
 
# Appel des fonctions dans un ordre aléatoire et affichage du chrono
print("taille data=%d, repeat=%d" % (len(data), repeat))
for (k, v) in random.sample(tuple(fct.items()), len(fct)):
	t=timeit.Timer(partial(v, data)).repeat(repeat=repeat, number=100)
	print("%s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for

Il met � peu pr�s 3/4mn pour s'ex�cuter (la faute au number=100 qui teste 100 fois chaque fonction mais qui permet en retour plus de pr�cision dans les chronos)... et chez-moi c'est le faster qui est plus rapide !!!

Code :

S�lectionner tout - Visualiser dans une fen�tre � part

1
2
3
4
Vérification fonctions ok
taille data=10000, repeat=20
batch_faster: min=4.436149, max=4.468541, avg=4.443463
batch_module: min=4.540502, max=4.692805, avg=4.604616

[Chaka_Sobek]

Tu appelles ta fonction en passant "�toile liste" en param�tre. Exemple la liste se nomme "data" (et contient une liste d'int) tu appelles batch_gcd(*data). C'est le unpacking.

Top ! Merci �norm�ment

Je vous souhaite une bonne soir�e et un bon weekend