C’est dû au fait que pour effectuer une vérification RSA, on ne peut pas utiliser les paramètres CRT (Chinese Remainder Theorem).
Avec les paramètres CRT (donc quand on possède la clé privée), l’exponentiation modulaire avec un module de 4096 bits demande :
- 2 exponentiations modulaires avec un exposant et un module de 2048 bits
- 1 multiplication modulaire de 2 éléments de taille 2048 bits
- 1 multiplication et une addition, de 3 éléments de taille 2048 bits
Sans les paramètres CRT (donc quand on n’a que la clé publique), on ne peut utiliser que l’exponentiation modulaire « naïve » avec un module de 4096 bits. Si l’exposant est assez grand (comme dans ce qui est montré par Adam Langley), cette opération devient très coûteuse.
Cette exponentiation « naïve » est un peu plus lente quand l’exposant a beaucoup de bits à 1. On effectue l’exponentiation bit par bit de l’exposant ; si le bit considéré est à 1 il s’agit d’une multiplication, si ce bit est à 0 il s’agit d’une mise au carré ; le tout suivi d’une réduction modulaire. La mise au carré permet quelques légères optimisations (faites l’opération de multiplication à la main, comme à l’école, vous devriez voir des patterns si vos 2 opérandes sont identiques).