Bonjour,
Je m’intéresse par curiosité à l'intelligence de ce magnifique algorithme qu'est RSA. J'ai a peu près compris le principe mais une question demeure. On voit souvent "clé RSA de x bits".
Ce qui m'intrigue ici, c'est la méthode qui permet de générer une clé RSA à la taille voulu.
Dans cet article : http://www.di-mgt.com.au/rsa_alg.html#note1 ; Je cite :
Si je comprends l'anglais, je lis ceci :To generate the primes p and q, generate a random number of bit length b/2 where b is the required bit length of n; set the low bit (this ensures the number is odd) and set the two highest bits (this ensures that the high bit of n is also set); check if prime (use the Rabin-Miller test); if not, increment the number by two and check again until you find a prime. This is p. Repeat for q starting with a random integer of length b-b/2. If p<q, swop p and q (this only matters if you intend using the CRT form of the private key). In the extremely unlikely event that p = q, check your random number generator. Alternatively, instead of incrementing by 2, just generate another random number each time.
Pour générer les nombres premiers p et q, il faut générer un nombre aléatoire dont la taille est b/2 bits avec b le nombre de bits requis pour n. Par exemple 1024 bits. Mettre le bit de poids faible à 1 (Cela assure que le nombre est premier) et les 2 bits premiers bits de poids fort à 1 également (Cela assure que le produit n=pq donne le bit de poids fort à 1). Vérifier que p est premier sinon augmenter p de 2 et continuer jusqu'à ce qu'il soit premier.
Faire de même avec q et vérifier que p != q.
Il rajoute : Au lieu d'incrémenter par 2 la valeur du nombre aléatoire s'il n'est pas premier, générer un nouveau aléatoire alternativement avec l'incrémentation.
Un truck que j'ai pas pigé, il dit que mettre le bit de faible à 1 assure que le nombre soit premier. 9 = 1001 en base 2 et n'est pas premier. Ou alors je traduis mal ensure. En plus, il dit juste après qu'il faut vérifier que le nombre est premier.
En omettant le dernier point, il faut donc trouver p et q premier et qu'ils aient cette forme :
p = 11.....0 sur 512 bits ( Soit 128 chiffres décimaux ou 64 octets )
q = 11.....0 sur 512 bits
ET p != q
Donc le fait que p et q aient cette forme assure que le produit
n = pq ( dont la taille de n représente la taille de la clé ) est sur 1024 bits ?
Sur un exemple, effectivement 11*12 = 132 > 127 et inférieur à 255 donc deux nombres de même taille (ici 4 bits) dont MSB=11 et LSB=1 donne par leur produit un nombre du double de leur taille.
Est-ce bien cela ?
Le fait de connaître les tailles et la forme de p et q ne réduit-il pas considérablement la robustesse de RSA en procédant de cette façon comparé à une clé dont on serait sûr qu'elle ferait au moins 1024 bits et non pas exactement 1024 bits ?
Merci pour vos lumières.
Partager