Mon problème est de calculer La plupart des logiciels que j'ai trouvés puissent le faire dans JavaScript semble utiliser la bibliothèque JavaScript Bigint ( http://www.leemon.com/crypto/bigint.html ). Faire une seule exponciation de cette taille avec cette bibliothèque prend environ 9 secondes sur mon navigateur lent (Firefox 3.0 avec SpiderMonkey). Je cherche une solution qui est au moins 10 fois plus rapide. L'idée évidente d'utiliser Square-and-Multiplier (exponentiation par quart, http://en.wikipedia.org/ wiki / exponentiation_by_squaring ) est trop lent pour les nombres 2048 bits: il a besoin jusqu'à 4096 multiplications. Mise à niveau du navigateur n'est pas une option. L'utilisation d'un autre langage de programmation n'est pas une option. L'envoi des numéros à un service Web n'est pas une option. existe une alternative plus rapide implémentée? Mise à jour: En effectuant des préparations supplémentaires (c.-à-d. PRÉCOMPUNION DE CIÈRES POUVOIRS) Comme recommandé par l'article http://www.ccrwest.org/gordon/fast.pdf mentionné Dans la réponse des Outtis ci-dessous, il est possible de faire une exponciation modulaire de 2048 bits en utilisant uniquement au plus 354 multiplications modulaires. (La méthode traditionnelle carrée et multiplier est beaucoup plus lente: elle utilise des multiplications modulaires maximales 4096.) Cela accélère donc l'exponenciation modulaire par un facteur de 6 dans Firefox 3.0, et par un facteur de 4 dans Google Chrome. La raison pour laquelle nous ne recevons pas la pleine vitesse du 4096/354 est que l'algorithme d'exponentation modulaire de Bigint est déjà plus rapide que carré-et-multiplier, car elle utilise la réduction de Montgomery ( http://fr.wikipedia.org/wiki/montgomery_reduction ). mise à jour: à partir du code de Bigint, il semble utile de faire deux niveaux de la multiplication karatsuba optimisée à la main ( http://en.wikipedia.org/wiki/karatsuba_algorithm < / a>), puis ensuite revenir à la multiplication de base-32768 O (N ^ 2) mise en œuvre dans Bigint. Cela accélère les multiplications d'un facteur de 2,25 pour les entiers 2048 bits. Malheureusement, l'opération MODULO ne devient pas plus rapide. mise à jour: à l'aide de la réduction modifiée de Barrett définie dans http://www.lirmm.fr/arith18/papers/hasenplaughing-fastmodularduction.pdf et les puissances de la multiplication de Karatsuba et des puissances précalisculantes (telles que définies dans http://www.ccrwest.org/gordon/fast.pdf ), je peux descendre le temps nécessaire à une multiplication unique de 73 secondes à 12,3 secondes dans Firefox 3.0. Cela semble être le meilleur que je puisse faire, mais c'est toujours trop lent. Mise à jour: L'interprète ActionScript 2 (As2) dans le lecteur Flash ne vaut pas la peine d'être utilisé, car il semble être plus lent que L'interpréteur JavaScript de Firefox 3.0: Pour Flash Player 9, il semble être 4,2 fois plus lent et pour Flash Player 10, il semble être 2,35 fois plus lent. Est-ce que quelqu'un connaît la différence de vitesse entre actionscript2 et actionscript3 (AS3) pour chiffrer en nombre? mise à jour: l'interpréteur ActionScript 3 (AS3) dans Flash Player 9 ne vaut pas à l'aide de la même vitesse En tant que JavaScript Int Firefox 3.0. Mise à jour: l'interpréteur ActionScript 3 (AS3) dans Flash Player 10 peut aller jusqu'à 6,5 fois plus rapide que l'interpréteur JavaScript dans Firefox 3.0 si mise à jour: il y a une solution Java très rapide, qui peut être appelée à partir de la JavaScript du navigateur Si le plugin Java est installé. La solution suivante est d'environ 310 fois plus rapide que l'implémentation pure JavaScript à l'aide de Bigint. peut traduire ce code à Silverlight (C #)? (g ^ x) MOD P rapidement dans JavaScript, où ^ est l'exponentiation, mod est l'opération MODULO . Toutes les entrées sont des entiers non négatifs, x a environ 256 bits, et p est un nombre privilégié de 2048 bits, et g peut avoir jusqu'à 2048 bits. int est utilisé au lieu de numéro et vecteur. tableau . Au moins, il était de 2,41 fois plus rapide pour une grande multiplication entière de 2048 bits. Cela vaut donc la peine d'être effectué l'exponentiation modulaire dans AS3, l'exécutant dans Flash Player 10 si disponible. Veuillez noter que cela reste plus lent que V8, l'interprète JavaScript de Google Chrome. Voir http://ptspts.blogspot.com/2009/10/ JavaScript-and-Actioncript-Performances.html pour une comparaison de vitesse de différentes implémentations de langage de programmation et JavaScript.
4 Réponses :
Pourquoi ne pas le faire du serveur dans une sorte de service Web en utilisant une langue plus appropriée comme c? Les temps seront alors temps pour un aller-retour (moins de 9 secondes), plus le temps nécessaire au serveur de calculer le résultat en utilisant une bibliothèque de Bigint dans un code natif. Ceci est susceptible d'être beaucoup plus rapide.
Vous ne voudrez peut-être pas envoyer votre clé privée au serveur.
Qui a dit quoi que ce soit sur les clés privées?
Avec C Utilisant la bibliothèque GMP, il est environ 1042 fois plus rapide. Mais en utilisant un langage de programmation différent ou l'envoi des numéros à un serveur n'est pas une option dans mon problème.
Alors je suppose que je suppose que les piquer dans Silverlight pour la forte crunching est trop hors de la question?
Je ne veux pas avoir Silverlight comme une dépendance. Mais en utilisant son Bigint ou Java's Bigint si disponible dans le navigateur peut être réalisable. Mais dans cette question, j'ai besoin d'une solution qui implémente une exponciation rapide modulaire dans JavaScript.
J'utilise "%" pour modulaire (mod) et "/" pour la division entière. Laissez la fonction F (p, g, x, r) calculer (r * g ^ x)% p sur la condition que r
XXX
Cette routine implique un peu plus de calcul, mais chaque entier est inférieur à 4096 bits qui est généralement beaucoup plus petit que g ^ x. Je crois que cela pourrait être plus efficace que le calcul direct. Notez également que g ^ (x% i) peut être calculé de manière plus rapide car nous avons calculé g ^ (i + 1).
EDIT: voir
Votre implémentation me donne une récursion infinie pour F (100, 3, 8, 1) au lieu de revenir 61. Votre algorithme a-t-il un nom propre?
Désolé, il y a une erreur mineure là-bas. J'ai changé cela. Cette méthode n'est que du résultat de simples mathématiques, trop simples pour obtenir un nom.
La méthode est basée sur l'observation que (k * p + g) ^ x% p = g ^ x% p. Il applique à plusieurs reprises cette règle pour éviter de calculer G ^ x directement.
F Les recouvrent pour toujours lorsque X / I> 2 dans l'appel récursif vers F, car y * y> p, la boucle de l'appel récursif sortira avec i = 1. Essayez F (100,5,8,1) (seulement pas vraiment, car vous devrez tuer votre navigateur). Notez également que i == plancher (journal (p) / journal (g)) . En fonction de la mise en œuvre de l'exponentiation et du journal, en utilisant i = plancher (log (p) / journal (g)); y = g ^ i peut être plus rapide que la boucle. Une fois que le problème de la récupération est corrigé, F serait logarithmique dans X pour le meilleur cas, mais SQRT dans X pour le pire des cas. L'exponentiation par quote-part (quels Bigint utilise) est logarithmique dans x dans tous les cas.
Une autre technologie latérale du client appelait-elle de JS, telle qu'un applet Java ou un film flash, être acceptable? Approche est déjà assez rapide. Vous pouvez tweak Bigint, ou vous pouvez essayer un Différents algorithmes , mais vous avez probablement gagné ' t obtenir un ordre d'amélioration de la magnitude.
Je dois confirmer que Bigint est assez bien optimisé. J'ai essayé de mettre en œuvre la multiplication à l'aide de l'algorithme Karatsuba, mais cela devient 4 fois plus lent que la simple multiplication O (n ^ 2) de Bigint.
Merci d'avoir mentionné le papier, il semble prometteur.
Utilisation de Bigint.js avec les techniques de l'article que vous avez liées, je pourrais accélérer la multiplication modulaire des entiers de 2048 bits par un facteur de 6 sur Firefox 3.0 et un facteur de 4 sur Google Chrome. Malheureusement, cela reste trop lent pour moi. Je dois donc trouver un protocole crypto différent, qui nécessite moins de calculs.
J'aimerais donner plus de upvotes pour cette réponse parce que j'ai trouvé l'article lié très utile. Mais je ne peux pas l'accepter comme la réponse, car ce n'est toujours pas assez rapide.
Essayez cette réduction modulaire MONTGOMERY de http://code.google.com/p/bi2php/ sur JavaScript.