La difficulté de générer des nombres premiers de 1024 bits

• Il s’agit d’une expérience consistant à générer directement en Rust les deux nombres premiers d’environ 1024 bits nécessaires à une clé RSA de 2048 bits, en implémentant tout soi-même, de la génération aléatoire aux opérations sur grands entiers, sans dépendance externe
• Une simple trial division suffisait en 16 bits avec environ 40 ms, mais même en 64 bits elle demandait encore 6,4 secondes après optimisation, ce qui la rendait difficilement extensible à 1024 bits
• Le test de Fermat est rapide, mais il peut laisser passer des pseudoprimes ; le jugement final repose donc sur un test de Miller-Rabin avec k=10
• Pour dépasser les limites des types entiers de base, un BigInt a été créé à la main, puis son stockage est passé d’un tableau de booléens à un tableau d’octets, puis à une structure en chunks u64, ce qui a fait passer le temps de génération d’un premier de 1024 bits d’environ 32 minutes à 60–90 secondes
• L’implémentation finale combine un BigInt en chunks u64, une division rapide, une trial division sur de petits nombres premiers, l’incrémentation des candidats par +2 et une exécution parallèle sur 16 threads, pour trouver en moyenne un nombre premier de 1024 bits en environ 40 ms, sans pour autant constituer une bibliothèque cryptographique validée

---

Générer soi-même un nombre premier de 1024 bits pour RSA

• L’objectif était de générer soi-même un nombre premier utilisable pour la génération de clés RSA
  • Une clé RSA de 2048 bits étant produite à partir du produit de deux nombres premiers, il faut donc deux premiers d’environ 1024 bits chacun
  • Le défi s’est donc naturellement resserré sur la génération de nombres premiers de 1024 bits
• L’expérience imposait trois contraintes
  • écrire le code depuis zéro, sans dépendances externes
  • utiliser un ordinateur portable doté d’un CPU AMD Ryzen 7 et de 16 Go de RAM, sans matériel externe ni cloud
  • générer un nombre premier dans un “temps raisonnable”
• Le langage choisi a été Rust, que l’auteur apprenait récemment
  • il est jugé assez proche du bas niveau pour manipuler ces concepts, tout en restant assez haut niveau pour rendre les fragments de code compréhensibles

Les limites de la trial division révélées en 16 bits puis en 64 bits

• Le flux de base consiste à générer en boucle un entier aléatoire de N bits, puis à s’arrêter dès qu’il passe le test de primalité
• Les nombres aléatoires sont produits en lisant directement /dev/urandom sous Linux, plutôt que d’utiliser la crate rand de Rust
  • /dev/urandom est un pseudo-fichier donnant accès au CSPRNG du noyau Linux
  • le noyau collecte de l’entropie depuis l’environnement utilisateur et réensemence périodiquement un chiffrement de flot déterministe basé sur ChaCha20
• Pour les entiers aléatoires de 16 bits, le premier bit et le dernier bit sont forcés à 1
  • le dernier bit à 1 garantit que le nombre est impair
  • le premier bit à 1 garantit l’utilisation de toute la plage de bits visée
• En 16 bits, une simple trial division de 3 à sqrt(num) suffisait pour trouver un nombre premier en environ 40 ms
  • un exemple d’exécution affichait Prime found: 44809, avec un temps total d’environ 0,038 seconde
• En passant à 64 bits, la trial division naïve montait à environ 30 secondes
  • l’approche a ensuite été améliorée en ne testant que les candidats de la forme 6k±1, puis en divisant d’abord par une liste de petits nombres premiers
  • après optimisation, le temps de génération d’un premier de 64 bits est descendu à environ 6,414 secondes
• Le fait d’être encore à 6 secondes en 64 bits a clairement montré que cette méthode ne permettrait pas d’atteindre la génération de nombres premiers de 1024 bits

Passage à un test probabiliste de primalité

• Parmi les algorithmes déterministes, APR-CL et ECPP ont été examinés, mais ils se sont révélés trop complexes mathématiquement et trop peu documentés de façon accessible pour être raisonnablement implémentés ici
• Après consultation du code source d’OpenSSL et des recommandations du NIST, il est apparu que les tests probabilistes de primalité sont largement utilisés en pratique, y compris pour RSA
• L’algorithme a donc évolué : au lieu de “prouver” qu’un nombre est premier, il s’agit de le classer comme probable prime avec un certain niveau de précision

• Test de Fermat

  • Le petit théorème de Fermat exploite la relation suivante : si p est premier et que a n’est pas divisible par p, alors a^(p-1) = 1 mod p
  • Une exponentiation directe provoquant des dépassements de capacité en u128, une exponentiation modulaire a été implémentée
  • pow() prend un exposant de type u32, et élever un u128 à un exposant plus grand peut provoquer un overflow
  • la multiplication elle-même peut dépasser la capacité de u128, si bien qu’une solution temporaire a consisté à stocker des entiers 64 bits dans un u128
  • le test de Fermat est rapide, mais les Fermat pseudoprimes peuvent faire classer à tort des composés comme premiers
  • même si ces composés sont rares, ils le sont suffisamment peu pour que le test de Fermat seul soit jugé insuffisamment fiable

• Test de Miller-Rabin

  • Miller-Rabin repose sur le même principe que Fermat, mais constitue un algorithme probabiliste plus robuste pour tester la primalité
  • l’implémentation commence par décomposer n-1 = 2^s × d, puis vérifie plusieurs conditions
  • a^d = 1 mod n
  • ou bien, pour un certain 0 <= r < s, a^(2^r × d) = n - 1 mod n
  • dans les essais en 128 bits, un nombre premier était trouvé en environ 0,042 seconde, soit à peu près comme avec Fermat
  • la borne d’erreur au pire de Miller-Rabin est de 4^-k, et en moyenne plutôt de l’ordre de 8^-k pour les grands n
  • pour k=10, la probabilité d’erreur moyenne calculée était de 0.000000000931323%
  • cela est comparé à la probabilité d’obtenir 30 fois de suite pile en lançant une pièce, soit 2^-30
  • pour un usage réellement cryptographique, il faut toutefois être plus prudent dans le choix aléatoire des bases et face à des conditions adversariales

Construire son propre BigInt

• Les types entiers natifs de Rust ne permettant pas de manipuler confortablement des nombres bien au-delà de 64 bits, il a fallu implémenter un entier à précision arbitraire (BigInt)
• La contrainte interdisant l’usage d’une crate bigint externe, ce BigInt a lui aussi été écrit à la main

• Tentative 1 : tableau de chiffres

  • au départ, une représentation sous forme de tableau de chiffres décimaux a été essayée
  • l’addition et la multiplication pouvaient être codées comme un calcul à la main, mais l’implémentation de la division s’est révélée bloquante

• Tentative 2 : tableau binaire basé sur des booléens

  • la deuxième approche stockait le nombre comme un tableau de 0 et de 1
  • BigInt utilisait un tableau [bool; 2048]
  • comme le produit de deux entiers de 1024 bits peut nécessiter jusqu’à 2048 bits, un espace de 2048 bits était réservé
  • l’addition et la soustraction étaient implémentées comme un full adder
  • la multiplication utilisait une approche shift-and-add exploitant la nature binaire
  • la division était implémentée via une division longue binaire
  • cette version a permis de trouver un premier de 1024 bits pour la première fois, mais le temps d’exécution était d’environ 32 minutes et 44,90 secondes
  • l’objectif était donc atteint sur le plan technique, mais pas au regard de la contrainte de “temps raisonnable”

• Tentative 3 : chunks d’octets

  • il est apparu que chaque bool du tableau de booléens occupait 1 octet, et non 1 bit
  • [bool; 2048] utilisait donc 2048 octets, et non 2048 bits
  • la représentation a ensuite été remplacée par un tableau de 256 octets pour stocker 2048 bits
  • l’addition, la soustraction et la multiplication continuaient de fonctionner sans grand changement, et la division a été adaptée pour traiter les chunks d’octets comme une liste de bits
  • avec cette approche, le temps de génération d’un premier de 1024 bits est descendu à 4 minutes 43 secondes

• Tentative 4 : chunks u64

  • l’approche en octets revenait en pratique à un BigInt basé sur des chiffres de grande base
  • l’étape suivante a consisté à stocker 2048 bits dans 32 chunks u64
  • chaque chunk se comporte comme un “chiffre”
  • u128 est utilisé pour contenir le résultat du produit de deux chunks u64
  • avec cette structure, un entier de 1024 bits peut être représenté par 16 chunks u64 au lieu de 309 chiffres décimaux
  • le temps de génération d’un premier de 1024 bits a été ramené à 60 à 90 secondes

Optimisation des goulets d’étranglement

• De simples benchmarks ont mis en évidence un écart net entre l’implémentation binaire et celle en chunks u64
  • a + b et a - b : 5537.35ns → 123.57ns
  • a * b : 1292283.14ns → 842.32ns
  • a / b et a % b : 733446.76ns → 44440.12ns
  • a < b et a > b : 2506.02ns → 58.91ns
• Les optimisations se sont ensuite concentrées surtout sur la division, la multiplication, les opérations internes à Miller-Rabin et la logique de génération des candidats

• Division

  • le principal goulet d’étranglement était la division
  • même avec la structure en chunks u64, l’ancienne division effectuait toujours une division longue bit par bit
  • en s’appuyant sur l’algorithme décrit à la page 598 du Handbook of Applied Cryptography, une division longue fondée sur la base de représentation a été implémentée
  • l’idée consiste à estimer le “chiffre” courant du quotient à partir des 3 premiers “chiffres” du dividende et des 2 premiers “chiffres” du diviseur
  • cette implémentation a permis d’économiser environ 40 000 ns par division
  • lorsqu’un diviseur tient dans un seul chunk u64, un traitement spécial utilise u128 pour effectuer une division longue plus directe
  • ce cas revient souvent dans Miller-Rabin

• Multiplication

  • la multiplication a été rendue environ deux fois plus rapide en réorganisant les boucles pour supprimer un BigInt temporaire destiné au stockage des résultats intermédiaires
  • le nombre de chunks effectivement occupés est calculé afin de ne boucler que sur les chunks non nuls
  • comme BigInt stocke la plupart du temps des nombres d’au plus 1024 bits, la moitié des 2048 bits réservés est souvent vide
  • des méthodes comme Karatsuba ou la multiplication basée sur FFT ont aussi été envisagées, mais elles ont été jugées trop complexes à implémenter manuellement, et la multiplication actuelle a été jugée suffisamment rapide

• Optimisations internes à Miller-Rabin

  • dans Miller-Rabin, l’accent a été mis sur la réduction des opérations coûteuses
  • x = mod_exp(x, 2, n) a été remplacé par x = (x * x) % n
  • le premier mod_exp() a été remplacé par une version inline simplifiée pour réduire l’overhead des appels de fonction
  • num.is_even() a été ajouté pour éviter le calcul % 2 lors du test de parité
  • d / 2 a été remplacé par d >>= 1
  • += 1 et -= 1 sont gérés spécialement via increase() et decrease()
  • en particulier, is_even() et d >>= 1 ont chacun apporté un gain d’environ 70 000 ns
  • dans le benchmark final, la version optimisée en chunks u64 a nettement accéléré
  • a * b : 842.32ns → 295.04ns
  • a / b et a % b : 44440.12ns → 831.77ns
  • a / 2 : 75121.58ns → 60.89ns
  • a % 2 == 0 : 78400.87ns → 21.65ns
  • a - 1 : 103.15ns → 67.54ns

Générateur final de nombres premiers de 1024 bits

• La fonction finale commence par lire un entier aléatoire de 1024 bits depuis /dev/urandom
  • le bit de poids fort est activé pour garantir une taille de 1024 bits
  • le bit de poids faible est activé pour garantir un nombre impair
• Ensuite, au lieu de relire un nouvel aléa à chaque essai, elle ajoute 2 au candidat pour passer au nombre impair suivant
  • increase_by_2() n’effectue généralement qu’une addition sur un seul chunk u64
• Avant Miller-Rabin, une trial division est effectuée à l’aide d’une liste de petits nombres premiers
  • dans le code final, les 1000 premiers petits nombres premiers sont utilisés
  • comme ces petits nombres premiers tiennent dans un seul chunk u64, le traitement spécial rapide de division sur un seul chunk peut être exploité
• Le problème se prête à une forme embarrassingly parallel, sans mémoire partagée ni synchronisation entre threads
  • 16 threads CPU cherchent chacun un nombre premier, et la valeur renvoyée par le thread qui termine en premier est retenue
• Un exemple d’exécution final a enregistré un temps écoulé d’environ 0,086 seconde
  • l’utilisation CPU affichée était de 690 %
• La moyenne sur 100 exécutions était de 0.04109 ± 0.00307 seconde
  • en moyenne, un nombre premier de 1024 bits est trouvé en environ 40 ms
  • un appel individuel à prime_1024bit() peut varier, en raison de l’aléa, d’environ 8 ms à environ 800 ms
  • l’exécution parallèle atténue cette variabilité en retenant le résultat le plus rapide

Code et limites

• L’ensemble du code et le dépôt sont disponibles sur github
• Des liens de discussion sont disponibles sur hackernews et reddit
• Cette implémentation ne doit pas être considérée comme réellement sûre du point de vue cryptographique ; son objectif relève davantage de l’apprentissage et de l’expérimentation d’implémentation que de la création d’une bibliothèque de chiffrement

[GN⁺]

Avis de Hacker News

• Quelques cryptomonnaies ont utilisé la recherche de grands nombres premiers comme partie de leur fonction de preuve de travail, et il y a environ 8 ans, on pouvait gagner pas mal d’argent simplement avec une implémentation très rapide de test de primalité
  J’ai été pendant un temps l’auteur et mainteneur du logiciel de minage de riecoin ; je ne sais pas trop pourquoi, sans doute simplement parce que j’aimais les nombres premiers
  Cet article omet l’optimisation numéro un pour les tests de primalité rapides : la multiplication de Montgomery : https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
  C’est la base des implémentations pratiques et rapides de l’exponentiation modulaire
  Niall Emmart, qui était à l’époque dans le milieu académique et qui, à ma connaissance, est maintenant chez Nvidia, a publié CGBN, une bibliothèque de grands entiers sur GPU vraiment incroyablement rapide : https://github.com/NVlabs/CGBN
  C’est encore l’implémentation d’exponentiation modulaire par lots la plus rapide que je connaisse, et, pour me permettre un instant d’enthousiasme de geek, elle est à couper le souffle
  Un jour, il faudra que j’écrive comment cela nous a permis de dominer pendant environ 5 ans la production d’une petite cryptomonnaie. Et Python intègre une exponentiation modulaire assez correcte avec la forme à trois arguments de pow(x, y, m), qui calcule x^y % m
  Avec ça, si vous voulez l’implémenter vous-même, il est très facile de faire un test de primalité de Fermat ou de Miller-Rabin, et c’est assez amusant. Si vous ne voulez pas l’écrire vous-même, mpz_probab_prime() de la bibliothèque gmp est très bien aussi. gmp est évidemment plus rapide, mais quand on joue avec de grands nombres premiers, il est difficile de battre le plaisir d’un test de Fermat en deux lignes

  • Niall a aussi participé à l’une des soumissions lauréates du ZPrize liées à la multiplication multi-scalaire rapide
    C’est étroitement lié à l’exponentiation modulaire par lots, mais avec la différence que cela fonctionne sur des courbes elliptiques plutôt que modulo des nombres premiers. J’y vois une continuation du travail sur CGBN
    Il a fait une bonne présentation l’an dernier au séminaire déjeuner de cryptographie de Stanford, et les diapositives ainsi que l’enregistrement sont en ligne
    https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
    https://www.youtube.com/watch?v=KAWlySN7Hm8
  • Je me demande pourquoi ces cryptomonnaies utilisaient une fonction de preuve de travail personnalisée de ce type
    J’aimerais savoir si c’était simplement l’idée vague que la crypto utilise bien des nombres premiers d’une façon ou d’une autre, sans savoir quand ni pourquoi, ou s’il y avait une raison plus profonde
  • C’est à cause de pow(x,e,mod) que je suis passé de Perl à Python

• Avec une borne maximale donnée pour les nombres, il est simple de rendre Miller-Rabin pratiquement déterministe
  Il suffit de choisir des bases dont il est prouvé qu’elles éliminent tous les pseudopremiers dans cette plage
  La liste ne devient pas très longue non plus. Miller-Rabin est vraiment puissant

  • Je me demande quelles seraient ces bases pour une plage de nombres de 1024 bits
    Je n’ai pas trouvé la réponse en ligne
  • En plus, si l’on cherche simplement des nombres premiers, on peut sélectionner des candidats qui ressemblent à des nombres premiers puis les vérifier avec un test déterministe

• Une seule ligne d’assembleur inline simplifie la multiplication de grands entiers « à l’école primaire » : https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
  Si je pouvais revenir en arrière et ne changer qu’une chose dans le langage C, j’y ajouterais la notion de multiplication étendue. C’est dommage que Rust ne l’ait pas non plus. Le support matériel existe partout. Le Cortex M0 ne fait même pas la division, mais il a la multiplication étendue
  Ce code vient d’une très vieille implémentation jouet de RSA, très laide, que j’avais écrite : https://github.com/jcalvinowens/toy-rsa
  La raison pour laquelle je pouvais m’en tirer avec seulement le test de Fermat, c’est que l’algorithme ne fonctionne pas si les nombres premiers ne sont pas réellement premiers. Le test de Fermat est rapide, et un seul chiffrement/déchiffrement élimine la probabilité extrêmement faible que l’un des deux soit un menteur de Fermat
  Cela dit, je ne sais pas si l’on peut prouver qu’il n’existe pas de paire de clés RSA capable de chiffrer/déchiffrer correctement un message avec des valeurs P/Q non premières. Dans une vraie implémentation, ce n’est évidemment pas la méthode canonique, mais je n’ai jamais trouvé la réponse

  • Fait intéressant, C dispose maintenant de grands entiers
    C23 a ajouté le type _BitInt(N) ; par exemple, on peut utiliser _BitInt(1024) comme type de 128 octets
    Le support des compilateurs reste toutefois limité. Avec Clang, pour autoriser un N supérieur à 128, on peut passer le drapeau -fexperimental-max-bitint-width=N. Si N est supérieur à 128 et que l’on divise un _BitInt(N), le compilateur plante purement et simplement, mais +, - et * fonctionnent comme attendu
  • En Zig, c’est relativement simple
    Il existe la primitive @mulWithOverflow, qui renvoie le résultat avec le bit de dépassement, et les entiers vont jusqu’à (u|i)65535
    Selon ce que l’on fait, on peut détecter le dépassement puis promouvoir vers un type plus grand, ou bien promouvoir d’abord puis tronquer éventuellement
    Il prend aussi en charge la multiplication saturante via l’opérateur distinct *|, et la multiplication avec wraparound via *%. On peut les utiliser quand on a besoin de ces sémantiques. Les autres dépassements relèvent d’un comportement indéfini soumis aux vérifications de sûreté, ce qui provoque un panic dans les modes de compilation Debug et ReleaseSafe
  • Si p et q sont des nombres de Carmichael premiers entre eux, RSA peut toujours chiffrer et déchiffrer correctement les messages
    En revanche, p*q aura des facteurs premiers plus petits, ce qui facilite la factorisation et réduit donc la sécurité
  • Dans la plupart des compilateurs C et en Rust, il me semble que caster vers un type plus grand puis multiplier génère exactement l’instruction machine souhaitée
  • La version originale de Pretty Good Privacy (PGP) de Philip Zimmermann, en 1994, utilisait seulement un crible divisant par tous les nombres premiers 16 bits connus, table produite avec le crible d’Ératosthène. Elle appliquait ensuite le test de Fermat

• Je me demande combien de temps cela a pris
  Pendant un projet de recherche en licence, j’ai travaillé sur la multiplication de grands entiers, et ça a pris presque deux semestres. J’ai implémenté Karatsuba, Toom-Cook, une FFT complexe, quelques NTT et Schonhage-Strassen
  Les nombres premiers, c’est presque de la magie mathématique. Pour les personnes intéressées, A Friendly Introduction to Number Theory de Silverman est un excellent livre de maths
  Au passage, le lien sur la page est 4025051 au lieu de 40250519

• Bon article. Moi aussi, j’ai récemment écrit un peu de code de grands entiers pour une première version de [0], et je me souviens à quel point il est frustrant de transformer les explications de haut niveau d’articles de maths en opérations concrètes
  J’ai toutefois une petite objection
  Si l’on utilise toute la plage de u64, les nombres sont en base 2^64, pas en base 2^64-1. Chaque mot a une valeur de 0 à 2^64-1, comme chaque chiffre décimal va de 0 à 9
  [0] https://github.com/LegionMammal978/bigfoot-sim

• Comme dans la dernière optimisation, si l’on incrémente le nombre de 2 en cas d’échec au lieu de générer un nouveau nombre aléatoire, cela affaiblit légèrement la sécurité
  Comme les nombres premiers ne sont pas répartis uniformément, cela introduit un biais vers les nombres premiers situés juste après de grands écarts entre nombres premiers

  • J’ai lu ça en me documentant
    C’est un compromis entre vitesse d’exécution et caractère aléatoire des nombres premiers ; j’ai privilégié la vitesse en considérant que 16 threads partant chacun d’un nombre aléatoire et faisant la course pour trouver un nombre premier ajoutaient assez d’aléa
    Si l’on veut plus d’aléa que de vitesse, remplacer +=2 par un appel à rng() est une modification facile

• Bon article, bien écrit
  L’auteur voulait sans doute dire base 256, et non base-255

• Quelques nombres de 1 à 2 Ko tiennent largement dans le cache L1, et même si ce n’était pas le cas, il y a plus d’un mégaoctet de cache L2 avec un temps d’accès d’environ 3 ns
  L’article disait qu’il avait probablement attendu des lectures/écritures en RAM à cause de défauts de cache L1, mais il ne revient pas ensuite sur ce point
  Par ailleurs, comme il ne s’agit ici que de génération de nombres premiers, on évite la plupart des pièges de RSA, et urandom devrait être sûr. Si le code fonctionne correctement, il n’y a pas tant de choses qui peuvent très mal tourner
  RSA comporte quelques problèmes liés aux nombres premiers faibles qu’il faut éviter, mais je ne sais pas s’ils sont assez fréquents pour poser réellement problème ici

• Ça me rappelle un projet de première année d’université, il y a quelques dizaines d’années
  Mon binôme et ami, qui est plus tard devenu major de promotion, avait eu l’idée et implémenté les maths essentielles : créer un chiffrement RSA 4096 bits
  Je me souviens à quel point la génération des nombres premiers était lente dans l’implémentation finale. Sur une station de travail PA-RISC, la génération prenait environ 20 minutes
  Mon ami, passionné de maths, a continué à optimiser le code après la fin du projet, et je me souviens l’avoir vu lire des articles sur les tests de primalité et l’implémentation de l’arithmétique des grands entiers
  Par exemple, dans la multiplication composée, ignorer la multiplication et renvoyer 0 quand l’un des nombres valait 0 a apporté une énorme amélioration

  • Sur du matériel lent, il vaut bien mieux générer des clés à courbe elliptique
    Sinon, il faut attendre longtemps, ou sacrifier une sécurité capable de tenir dans le temps

• Je comprends pourquoi on force le bit de poids faible à 1. Les nombres pairs ne sont jamais premiers, bien sûr, sauf 2
  Mais je ne comprends pas pourquoi on force aussi le bit de poids fort à 1. Je ne m’y connais pas spécialement en nombres premiers ni en crypto, mais ça ressemble à un abandon inutile d’1 bit d’entropie. Qu’est-ce qui m’échappe ?

  • Si le bit de poids fort est toujours défini et que le nombre premier est encodé en l’incluant, alors le nombre premier est toujours encodé avec le même nombre d’octets
    Les encodages d’octets à longueur variable peuvent poser des problèmes dans les échanges de données entre logiciels différents si la spécification n’est pas très claire et bien testée
    Il suffit de regarder les problèmes que provoquent les zéros de tête dans les clés publiques de serveur avec le DHE basé sur RSA
  • C’est comme générer un nombre à deux chiffres
    Si le premier chiffre est 0, ce n’est pas un nombre à deux chiffres
  • Mettre le premier bit à 1 fait perdre 1 bit d’entropie, mais garantit que le nombre premier est suffisamment grand
    J’ajouterais que, dans RSA, on multiplie deux nombres premiers. Si l’un fait 1024 bits, l’autre peut faire environ 200 bits, si je me souviens bien, tout en atteignant le nombre de bits d’entropie requis pour la clé
    Donc mettre les deux nombres premiers à 1024 bits donne aussi un peu de marge
  • C’est bien abandonner 1 bit d’entropie, mais il en reste tout de même 1022
    C’est probablement plus sûr que de se demander si un nombre premier de 1020 bits suffit alors que quelqu’un a demandé un nombre premier de 1024 bits. C’est comme le fait qu’on ne considère généralement pas 00042 comme un nombre à 5 chiffres
    Techniquement, le choix optimal peut varier selon l’usage exact, mais la méthode décrite dans l’article semble être un choix par défaut plus sûr
  • Perdre 1 bit d’entropie pour s’assurer de ne pas se retrouver avec un nombre premier limité à 50 bits paraît clairement être un compromis tout à fait acceptable