Pourquoi les algorithmes génétiques ne fonctionnent-ils pas sur des problèmes comme le RSA?

Question

Il y a quelque temps, j'étais assez intéressé par le gaz et j'ai étudié à leur sujet un peu. J'ai utilisé C ++ Galib pour écrire certains programmes et j'ai été assez étonné par leur capacité à résoudre autrement difficile à calculer des problèmes, en quelques secondes. Ils semblaient être une excellente technique de brute qui fonctionne vraiment très intelligente et s'adapte.

Je lisais un livre de Michalewitz, si je me souviens du nom correctement et que tout semblait être basé sur le théorème du schéma, prouvé par le MIT.

J'ai également entendu dire qu'il ne peut pas vraiment être utilisé pour aborder des problèmes comme l'affacturage des clés privées RSA.

Quelqu'un pourrait-il expliquer pourquoi c'est le cas?

Answer 1

L'algorithme génétique n'est pas intelligent du tout, ce sont des algorithmes d'optimiseur très gourmands. Ils travaillent tous autour de la même idée. Vous avez un groupe de points («une population d'individus»), et vous transformez ce groupe en un autre avec un opérateur stochastique, avec un biais dans le sens de la meilleure amélioration («Mutation + Crossover + Sélection»). Répétez jusqu'à ce qu'il converge ou que vous en en avait assez, rien de intelligent là-bas.

Pour qu'un algorithme génétique fonctionne, une nouvelle population de points devrait fonctionner près de la population de points précédents. Peu de perturbation devrait créer peu de changements. Si, après une petite perturbation d'un point, vous obtenez un point qui représente une solution avec des performances complètement différentes, alors, l'algorithme n'est rien de mieux qu'une recherche aléatoire, un algorithme d'optimisation généralement pas bon. Dans le cas RSA, si vos points sont directement les nombres, c'est OUI ou non, simplement en retournant un peu ... Ainsi, l'utilisation d'un algorithme génétique n'est pas meilleure que la recherche aléatoire, si vous représentez le problème RSA sans trop penser " Points de recherche de code comme les bits des nombres "

Answer 2

Je dirais parce que la factorisation des clés n'est pas un problème d'optimisation, mais un problème exact. Cette distinction n'est pas très précise, alors voici des détails. Les algorithmes génétiques sont formidables pour résoudre des problèmes où il s'agit minimum (local / global), mais il n'y en a pas dans le problème factoriel. L'algorithme génétique en tant que DCA ou recuit simulé nécessite une mesure de "à quel point je suis proche de la solution" mais vous ne pouvez pas dire cela pour notre problème.

Pour un exemple de génétique des problèmes, il y a le problème de l'escalade de la colline.

Answer 3

Le gaz est basé sur l'évaluation de la forme physique des solutions candidates.

Vous avez essentiellement une fonction de fitness qui prend une solution candidate en entrée et vous rend un scalaire en vous indiquant à quel point ce candidat est bon. Vous continuez ensuite et permettez aux meilleurs individus d'une génération donnée de s'accoupler avec une probabilité plus élevée que les autres, afin que la progéniture soit (espérons-le) plus `` en forme '' dans l'ensemble, etc.

Il n'y a aucun moyen d'évaluer la forme physique (la qualité d'une solution candidate par rapport au reste) dans le scénario de factorisation RSA, c'est pourquoi vous ne pouvez pas les utiliser.

Answer 4

Les gaz ne sont pas brutaux, ce ne sont qu'un algorithme de recherche. Chaque GA ressemble essentiellement à ceci:

candidates = seed_value;
while (!good_enough(best_of(candidates))) {
    candidates = compute_next_generation(candidates);
}

Où good_enough et best_of sont définis en termes de fonction de remise en forme. Une fonction de fitness dit Dans quelle mesure un candidat donné résout le problème. Cela semble être le problème central ici: comment rédigeriez-vous une fonction de fitness pour la factorisation? Par exemple 20 = 2 * 10 ou 4 * 5. Les tuples (2,10) et (4,5) sont clairement des gagnants, mais qu'en est-il des autres? À quel point est «l'ajustement» (1,9) ou (3,4)?

Answer 5

Indirectement, vous boîte Utilisez un algorithme génétique pour prendre en compte la méthode de factorisation entière de N. Dixon entier utilise des équations impliquant des pouvoirs du premier k Primes, modulo N. Ces produits des pouvoirs de petits nombres premiers sont appelés "lisses". Si nous utilisons le premier k = 4 Primes - {2,3,5,7} - 42 = 2x3x7 est lisse et 11 n'est pas (faute d'un meilleur terme, 11 est "rugueux"). La méthode de Dixon nécessite un inversible k X k matrice composée des exposants qui définissent ces nombres lisses. Pour en savoir plus sur la méthode de Dixon, voir https://en.wikipedia.org/wiki/Dixon%27S_Factorisation_Method.

Maintenant, revenons à la question initiale: il existe un algorithme génétique pour trouver des équations pour la méthode de Dixon.

1. Laisser r être l'inverse d'un nombre lisse mod n - donc r est un nombre approximatif
2. Laisser s être lisse
3. Générer des solutions aléatoires de Rx = Sy Mod N. Ces solutions [x, y] sont la population de l'algorithme génétique. Chaque x, y a un composant lisse et un composant rugueux. Par exemple, supposons x = 369 = 9 x 41. Ensuite (en supposant que 41 n'est pas assez petit pour compter comme lisse), la partie rugueuse de X est 41 et la partie lisse est 9.
4. Choisissez des paires de solutions - "parents" - pour se combiner en combinaisons linéaires avec des pièces rugueuses toujours plus petites.
5. L'algorithme se termine lorsqu'une paire [x, y] est trouvée avec des pièces rugueuses [1,1], [1, -1], [- 1,1] ou [-1, -1]. Cela donne une équation pour la méthode de Dixon, car rx = sy mod N et r est le seul nombre difficile à gauche: X et y sont lisses, et s a commencé lisse. Mais même 1 / r mod n est lisse, donc tout est lisse!

Chaque fois que vous combinez deux paires - disons [v, w] et [x, y] - les parties lisses des quatre nombres sont effacées, à l'exception des facteurs que les parties lisses de V et X partagent, et les facteurs les parties lisses des parties de w et y partager. Nous choisissons donc les parents qui partagent des parties lisses dans la plus grande mesure possible. Pour rendre cela précis, écrivez

g = gcd (partie lisse de V, partie lisse de x)

H = GCD (partie lisse de W, partie lisse de Y)

v, w], [x, y] = [gv / g, hw / h], [gx / g, hy / h].

Les facteurs lisses durs G et H seront conservés dans la prochaine génération, mais les parties lisses de V / G, W / H, X / G et Y / H seront sacrifiées afin de combiner [V, W] et [x, y]. Nous choisissons donc les parents pour lesquels V / G, W / H, X / G et Y / H ont les plus petites pièces lisses. De cette façon, nous conduisons vraiment les parties rugueuses de nos solutions à Rx = sy mod n d'une génération à l'autre.

Answer 6

En outre, la meilleure façon de vous diriger vers des coefficients lisses x, y dans le réseau ax = par mod n est avec la régression, pas un algorithme génétique.

Deux régressions sont effectuées, une avec un vecteur de réponse R0 composé de valeurs X à partir de solutions choisies au hasard de AX = par mod n; et l'autre avec un vecteur de réponse R1 composé de valeurs Y des mêmes solutions. Les deux régressions utilisent la même matrice explicative X. Dans X, des colonnes constituées des restes des diviseurs lisses modulo de valeurs X et d'autres colonnes composées des restes des valeurs de valeur Y des autres diviseurs lisses.

Le meilleur choix de diviseurs lisses est celui qui minimise les erreurs de chaque régression:

E0 = r0 - x (inverse de (x-transspose) (x)) (x-transspose) (R0)

E1 = r1 - x (inverse de (x-transspose) (x)) (x-transspose) (R1)

Ce qui suit, ce sont les opérations de ligne pour anéantir X. Appliquez ensuite un résultat Z de ces opérations de ligne aux valeurs x et y à partir des solutions d'origine à partir desquelles X a été formée.

z R0 = z R0 - 0
     = z R0 - zX (inverse of (X-transpose)(X)) (X-transpose) (R0)
     = z E0 

De même, z r1 = z e1

Trois propriétés sont maintenant combinées en Z R0 et Z R1:

• Ce sont des multiples de grands nombres lisses, car Z anéantisse les nombres lisses modulo.
• Ils sont relativement petits, car E0 et E1 sont petits.
• Comme toute combinaison linéaire de solutions à AX = par mod n, z r0 et z r1 sont eux-mêmes des solutions à cette équation.

Un multiple relativement petit d'un grand nombre lisse pourrait bien être le nombre lisse lui-même. Avoir une solution lisse d'Ax = par mod n donne une entrée à la méthode de Dixon.

Deux optimisations rendent cela particulièrement rapide:

• Il n'est pas nécessaire de deviner tous les nombres et colonnes lisses de X à la fois. Vous pouvez exécuter des régressions continuellement, en ajoutant une colonne à x à la fois, en choisissant les colonnes qui réduisent le plus E0 et E1. À aucun moment, deux nombres lisses avec un facteur commun ne seront sélectionnés.
• Vous pouvez également commencer avec de nombreuses solutions aléatoires de ZX = par mod n, et supprimer celles avec les plus grandes erreurs entre les sélections de nouvelles colonnes pour X.