Метод Полларда

Привет, Вы узнаете о том , что такое метод полларда, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое метод полларда , настоятельно рекомендую прочитать все из категории Криптоанализ, Виды уязвимости и защита Информации .

Этот вероятностный метод основан на следующем факте. Если на некотором конечном множестве М определить случайное отображение f и применить его поочередно ко всем элементам М, а ребрами соответстви - y=f(x) для x,yН М. Поскольку множество М конечно, то этот граф должен содержать деревья, корни которых соединены в циклы. Дл случайного отображения f длина цикла равна О(Ц #М ) и высота дерева в среднем равна О(Ц #М ). 

Для нахождения ключа, например в криптоалгоритме, основанном на задаче логарифма на некоторой группе, достаточно решить задачу о встрече на графе случайного отображения. Для этого из двух разных стартовых точек x0|, x0| | строятс траектория до входа в цикл. Затем одна из двух конечных точек, лежащих в цикле, фиксируется, а траектория другой продолжается до встречи с фиксированной точкой. Для функции f и точки входа x0 длина траектории составляет О(Ц #М ) шагов. Типичный вид этой траектории содержит предельный цикл длины О(Ц #М ) и отрезок до входа в цикл примерно такой же длины. В качестве индикатора замыкания траектории Поллард предложил использовать равенство xi = x2i , где xi - i-я точка траектории для входа x0. Это равенство будет выполняться всегда. Значение индекса i не превышает суммы длины пути до входа в цикл. 

В среднем сложность нахождения равенства xi = x2i равна 3Ц (p /8)#М. Сложность встречи, когда обе точки лежат в цикле, равна 0,5Ц (p /8)#М. Таким образом, итоговая сложность равна 6,5Ц (p /8)#М. 

метод полларда применяется для решения задачи логарифма на циклической группе, поиска частично эквивалентных ключей (коллизий), для нахождения двух аргументов, дающих одинаковое значение хэш-функции, и в некоторых других случаях. Применительно к задаче логарифмирования этот метод позволяет отказаться от использования большого объема памяти по сравнению с методом встречи посередине. Кроме того, пропадает необходимость сортировки базы данных. В результате временная сложность по сравнению с методом встречи посередине снижается на множитель О(log#М). Сложность этого метода в данном случае составляет О(Ц #М ) шагов и требует памяти объема О(1) блоков. Об этом говорит сайт https://intellect.icu . Однако не всегда требуетс малая память. 

Рассмотрим в качестве иллюстрации метода Полларда алгоритм нахождения коллизии (двух аргументов, дающих одинаковое значение хэш-функции) для вычислительной модели с объемом памяти О(v). Такими аргументами будут элементы множества М, стрелки от которых под действием 
хэш-функции f ведут в точку входа в цикл. Практически алгоритм сводится к нахождению точки входа в цикл. 
1. Войти в цикл, используя равенство xi = x2i = t . 
2. Измерить длину цикла m, применяя последовательно отображение f к элементу t до получения равенства fm(t)=t . 
3. Разбить цикл m на v интервалов одинаковой или близкой длины и создать базу данных, запомнив и упорядочив начальные точки интервалов. 
4. Для стартовой вершины п.1 выполнять одиночные шаги до встречи с какой-либо точкой из базы данных п.3. Отметить начальную и конечную точки интервала, на котором произошла встреча. 
5. Стереть предыдущую и создать новую базу данных из v точек, разбив интервал, на котором произошла встреча, на равные по длине части, запомнив и отсортировав начальные точки интервалов. 
6. Повторить процедуры пп.4,5 до тех пор, пока не получится длина интервала, равная 1. Вычислить точку встречи в цикле, вычислить коллизию как пару вершин, одна из которых лежит в цикле, а друга - нет. 

Этот алгоритм требует многократного выполнени О( Ц #М ) шагов до входа в цикл и выполнени сортировки базы данных. На каждом этапе при создании новой базы данных длина интервала сокращается в v раз, то есть количество повторов равно О( logv #М ). Если v << Ц #М, то сложностью сортировки базы данных можно пренебречь. Тогда сложность алгоритма равна О(Ц #М logv #М). 

Рассмотрим возможность улучшения оценки сложности этого метода за счет увеличения доступной памяти. Напомним, что почти все вершины графа случайного отображения лежат на одном дереве. Поэтому будем решать задачу о встрече на случайном ориентированном дереве. С ростом глубины h ширина дерева b(h) уменьшается, то есть случайное отображение обладает сжимающими свойствами. Поэтому с ростом глубины вершины, с одной стороны, увеличивается сложность встречи за счет многократного применения отображения, с другой стороны, увеличивается вероятность встречи в силу сжимающих свойств. Доля вершин с глубиной не менее h равна О(1/h). 

Рассмотрим два алгоритма для решения задачи о встрече. Первый алгоритм предусматривает выбор множества m случайных начальных вершин, применение к ним к раз отображения, сортировку множества конечных вершин и поиск среди них равных. Второй алгоритм предусматривает запоминание всей траектории спуска для каждой вершины, сортировку множества вершин, составляющих траектории, и поиск среди равных. Второй алгоритм являетс не менее сложным, чем первый, в силу сжимающих свойств случайного отображения. 

Сложность первого алгоритма равна km (log m). Множитель log m учитывает сложность сортировки. В силу парадокса дней рождения m = О(#M/h)0.5. Для одного шага сложность алгоритма равна О(Ц #M log#M), то есть этот алгоритм более эффективный, чем алгоритм встречи посередине 

После первого шага от листа глубины становитс равной О( log#М ). Однако в дальнейшем рост глубины с каждым шагом замедляется. Это объясняется существенно разрывным характером условной вероятности р(h|H) получения глубины h при исходной глубине H. Действительно, из определения глубины следует, что каждая вершина с глубиной H+1 связана ребром с вершиной с глубиной H. Из каждой вершины исходит единственное ребро. Поэтому в силу количественных оценок ширины графа 
р(H+1|H)=[O(H-2 - (H+1)-2)]/O(H-2)=1-O(H-1).

Числитель этого выражения равен разности ширины графа на глубинах H и H+1, знаменатель учитывает то, что исходная глубина равна Н. Вероятность попасть на глубину h>H+1 определяется вероятностью непопадания на глубину H+1 и шириной графа, 
р(h|H)=O(H-1h-2).

Сравним вероятность pk(h) получени глубины h после k шагов при спуске от листа и вероятность pk(h|Mk-1) глубины h после k шагов при условии, что на шаге k-1 глубина равнялась математическому ожиданию. Имеет место оценка pk(h)е pk(h|Mk-1). Поэтому место вероятности сложного события pk(h) можно рассматривать вероятность простого события pk(h|Mk-1). 

Пусть стартовая вершина лежит на глубине H=O( log#M). Какова будет глубина после очередного шага? Непосредственные вычисления показывают, что математическое ожидание глубины равно H+1+O(1), то есть второй и последующий шаги увеличивают глубину спуска на О(1). Подстановка в качестве исходной глубины математического ожидания глубины спуска на предыдущем шаге дает оценку математического ожидания глубины спуска после к шагов : 
h=O( log#M ) + O(k).

Поскольку оптимальное число шагов при спуске к алгоритма определяется равенством сложности спуска mk и сложности сортировки m log m, то копт=O(log#M). Отсюда следует, что задача встречи на случайном ориентированном дереве не менее сложна, чем задача о встрече в цикле, то есть алгоритм Полларда не улучшаем за счет увеличения доступной памяти.

Выводы из данной статьи про метод полларда указывают на необходимость использования современных методов для оптимизации любых систем. Надеюсь, что теперь ты понял что такое метод полларда и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Криптоанализ, Виды уязвимости и защита Информации

Из статьи мы узнали кратко, но содержательно про метод полларда