Discussion :

[darkwall_37]

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 :

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.

Si je comprends l'anglais, je lis ceci :

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.

[kwariz]

Bonjour,

(this ensures the number is odd) => (Cela assure que le nombre est premier)

odd signifie impair, premier se dit prime.

p sera de la forme 11.......1 avec au moins (peut-être plus à cause des incrémentations) b/2 bits (au moins 512 pour ton exemple), q aura une taille de b-(nombre de bit de p). Sans incrémentations, les deux auront une taille de b/2.

Dans le cas b=1024 :
p et q sont de la forme : 11..(509 bits)..1
p>3x2^510
q>3x2^510
pq>9x2^1020>8x2^1020=2^1023 -> l'écriture de pq nécessite au moins 1024 bits

10b est le seul premier dont l'écriture binaire se termine par 0.

[darkwall_37]

En effet, je me suis laissé embrouillé...

En pratique, dans les PKI par exemple, on constate sur les certificats que les clés font 1024 bits. C'est fait en sorte que toutes les clés soient bien égales à cette valeur et non supérieure ou égale ?

[darkwall_37]

Peut être me suis-je mal exprimé.
Peut on garantir la taille d'une clé RSA à sa génération.
Visiblement de ce que vous me dites, elle peut être de 1024 bits si tout ce passe bien. Cependant, ce n'est pas toujours le cas.
Alors je me posais cette question étant donné que le temps de traitement est devenu un enjeu majeur dans les S.I d'aujourd'hui.
S'il faut que cet algorithme devienne récursif pour garantir la taille d'une clé, je ne sais pas si cela est une bonne idée.
Surtout que pour de grands systèmes où la sécurité est importante, les nombres p et q sont très grands et les calculer peut s'avérer couteux ?!

[kwariz]

Bonjour,

je ne répondais qu'à la partie «math» de la question en fait. Mais en gros on peut garantir le nombre exact de bits d'une clé. Par comparaison en base 10 (peut-être un peu plus intuitif) si on prend deux nombres p,q tels que 31<p,q<100 alors on est certain que le produit s'écrira avec exactement 4 chiffres. Le 31 est le plus grand nombre entier inférieur à la racine carrée de 10^3 et 100 la racine carrée de 10^4.
De la même manière pour être certain d'avoir une clé de 1024 bits en multipliant deux nombres de 512 bits p et q il faut que :
2^(1023/2)<11(510 bit quelqconques)b<p,q<2^(1024/2)=1...(512 fois 0)b
en effet 2^(1023/2) commence par 1011... donc en prenant un nombre commençant par 11... on est certain d'en avoir un plus grand.

La question de savoir s'il existe au moins deux (ou suffisament de) nombres premiers qui satisfassent la contrainte est une autre question. On peut estimer (très très très vaguement pour l'ordre de grandeur considéré) le nombre de nombre premiers entre 2^(1023/2) et 2^(1024) : x/ln(x)<𝝿(x)<Li(x), où 𝝿 est la fonction qui donne le nombre de nombres premiers inférieurs à x et Li le logarithme intégral :

3.77E151<𝝿(2^(1024/2))<3.79E151
2.67E151<𝝿(2^(1023/2))<2.69E151

1.08E151< nombre de nombres premiers entre ...<1.12E151

Edit: Typo

[darkwall_37]

Ah ! Excellent ! Merci beaucoup pour ce petit cours bien précis comme je le cherchais.

Je vais essayer d'implémenter ça en C. Je m'attaquerai au problème de la génération pseudo-aléatoire plus tard, ce qui semble rendre caduque l'utilisation de RSA.