Почему генетические алгоритмы не работают над такими проблемами, как факторинг RSA?

Question

Некоторое время назад меня очень интересовали ГА, и я довольно много о них изучал. Я использовал C ++ GAlib для написания некоторых программ, и я был очень удивлен их способностью решать сложные задачи за несколько секунд. Они казались отличной техникой брутфорса, которая работает действительно умно и адаптируется.

Я читал книгу Михаэльвица, если я правильно помню имя и все это, казалось, основано на теореме схемы, доказанной MIT.

Я также слышал, что его нельзя использовать для решения таких проблем, как разбор закрытых ключей RSA.

Кто-нибудь может объяснить, почему это так?

Answer 1

Генетический алгоритм совсем не умный , это очень жадные алгоритмы оптимизатора. Все они работают вокруг одной идеи. У вас есть группа точек («совокупность людей»), и вы преобразуете эту группу в другую со стохастическим оператором с уклоном в сторону лучшего улучшения («мутация + кроссовер + отбор»). Повторяйте, пока он не сойдет или вам это не надоест, ничего умного там нет.

Чтобы сработал генетический алгоритм, новая совокупность точек должна работать вблизи предыдущей совокупности точек. Небольшое возмущение должно создавать небольшие изменения. Если после небольшого возмущения точки вы получаете точку, представляющую решение с совершенно другой производительностью, тогда алгоритм ничем не лучше случайного поиска, обычно не очень хорошего алгоритма оптимизации. В случае RSA, если ваши точки - это непосредственно числа, это либо ДА, либо НЕТ, просто щелкнув немного ... Таким образом, использование генетического алгоритма не лучше случайного поиска, если вы представляете проблему RSA, не задумываясь «давайте код поиска точек в виде битов чисел "

Answer 2

Я бы сказал, потому что факторизация ключей - это не проблема оптимизации, а точная проблема.Это различие не очень точное, поэтому здесь есть детали.Генетические алгоритмы хороши для решения задач, где есть минимумы (локальные / глобальные), но в факторинговой проблеме их нет.Генетический алгоритм, такой как DCA или моделируемый отжиг, требует меры «насколько я близок к решению», но вы не можете сказать это для нашей проблемы.проблема с лазанием.

Answer 3

GA основаны на оценке пригодности возможных решений.

У вас в основном есть фитнес-функция, которая принимает решение кандидата в качестве входных данных и возвращает вам скаляр, сообщающий вам, насколько хорош этот кандидат.Затем вы продолжаете и позволяете лучшим людям данного поколения спариваться с большей вероятностью, чем у остальных, так что потомство будет (надеюсь) более «подходящим» в целом, и так далее .

В сценарии факторизации RSA нет способа оценить пригодность (насколько хорошо подходящее решение по сравнению с остальными), поэтому вы не можете их использовать.

Answer 4

Косвенно, вы можете использовать генетический алгоритм для факторизации целого числа N. Метод целочисленной факторизации Диксона использует уравнения со степенями первых k простых чисел, по модулю N. Эти произведения степенеймалых простых чисел называются «гладкими».Если мы используем первые k = 4 простых чисел - {2,3,5,7} - 42 = 2x3x7 является гладким, а 11 - нет (из-за отсутствия лучшего термина 11 - "грубый"),Метод Диксона требует обратимой k x k матрицы, состоящей из показателей, определяющих эти гладкие числа.Подробнее о методе Диксона см. https://en.wikipedia.org/wiki/Dixon%27s_factorization_method.

Теперь вернемся к первоначальному вопросу: существует генетический алгоритм для нахождения уравнений для метода Диксона.

1. Пусть r будет инверсией сглаженного числа mod N - поэтому r является грубым числом
2. Пусть s будет гладким
3. Генерация случайных решенийrx = sy mod N. Эти решения [x, y] являются популяцией для генетического алгоритма.Каждый x, y имеет гладкий компонент и грубый компонент.Например, предположим, что x = 369 = 9 x 41. Тогда (при условии, что 41 не достаточно мал, чтобы считать его гладким), шероховатая часть x равна 41, а гладкая - 9.
4. Выберите пары решений -«родители» - объединять в линейные комбинации с еще меньшими шероховатыми частями.
5. Алгоритм заканчивается, когда пара [x, y] найдена с шероховатыми частями [1,1], [1, -1][-1,1] или [-1, -1].Это приводит к уравнению для метода Диксона, потому что rx = sy mod N и r - единственное оставшееся приблизительное число: x и y гладкие, и s началось гладко.Но даже 1 / r mod N является гладким, так что все гладко!

Каждый раз, когда вы объединяете две пары - скажем, [v, w] и [x, y] - гладкие части четырехчисла стираются, за исключением факторов, которые имеют гладкие части v и x, и факторов, которые имеют гладкие части w и y.Поэтому мы выбираем родителей, которые делят гладкие части в максимально возможной степени.Чтобы сделать это более точным, напишите

g = gcd (гладкая часть v, гладкая часть x)

h = gcd (гладкая часть w, гладкая часть y)

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

с трудом завоеванные коэффициенты сглаживания g и h будутбудут сохранены в следующем поколении, но гладкие части v / g, w / h, x / g и y / h будут принесены в жертву, чтобы объединить [v, w] и [x, y].Поэтому мы выбираем родителей, для которых v / g, w / h, x / g и y / h имеют наименьшие гладкие части.Таким образом, мы действительно приводим грубые части наших решений к rx = sy mod N от одного поколения к следующему.

Answer 5

ГА - это не грубой силы, это всего лишь алгоритм поиска. Каждый GA по сути выглядит так:

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

Где good_enough и best_of определены в терминах фитнес-функции . Функция пригодности говорит , насколько хорошо данный кандидат решает проблему . Похоже, в этом заключается основная проблема: как бы вы написали функцию пригодности для факторизации? Например 20 = 2 * 10 или 4 * 5. Кортежи (2,10) и (4,5) явно выигрывают, но как насчет других? Насколько «подходит» (1,9) или (3,4)?

Answer 6

Если подумать, то лучший способ сделать шаг к гладким коэффициентам x, y в оси решетки = по модулю N - это регрессия, а не генетический алгоритм.

Выполняются две регрессии, одна с ответомвектор R0, состоящий из значений x из случайно выбранных решений ax = by mod N;и другой с вектором отклика R1, состоящим из значений y из тех же решений.Обе регрессии используют одну и ту же объяснительную матрицу X. В X есть столбцы, состоящие из остатков значений x по модулю гладких делителей, а другие столбцы, состоящие из остатков значений y по модулю других гладких делителей.

лучший выбор гладких делителей - это тот, который минимизирует ошибки каждой регрессии:

E0 = R0 - X (обратный (X-транспонировать) (X)) (X-транспонировать) (R0)

E1 = R1 - X (обратный (X-транспонировать) (X)) (X-транспонировать) (R1)

Ниже приведены операции со строками для уничтожения X. Затем примените результат z из этихОперации со строками для значений x и y из исходных решений, из которых был сформирован X.

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

Аналогично, z R1 = z E1

Три свойства теперь объединены в z R0и z R1:

• Они кратны большим гладким числам, потому что z уничтожает остатки по модулю гладких чисел.
• Они относительно малы, поскольку E0 и E1 малы.
• Как и любая линейная комбинация sВычисления в ax = по mod N, z R0 и z R1 сами являются решениями этого уравнения.

Относительно небольшое кратное большого гладкого числа может быть просто самим гладким числом.Гладкое решение ax = by mod N дает вход для метода Диксона.

Две оптимизации делают это особенно быстрым:

• Нет необходимости угадывать все гладкие числа истолбцы X сразу.Вы можете запускать регрессии непрерывно, добавляя один столбец к X за раз, выбирая столбцы, которые больше всего уменьшают E0 и E1.Ни в коем случае нельзя выбирать любые два гладких числа с общим множителем.
• Вы также можете начать с множества случайных решений zx = по модулю N и удалить те из них, которые имеют наибольшие ошибки между выборами новыхколонки для X.