Estimating complexity of directed enumeration in non-uniformly distributed key spaces.pdf Решение криптографических задач часто состоит в определении значения ключевогопараметра. Мощность множества K значений этого параметра может быть огромной.Кроме того, часто значение самого параметра может быть получено только методомопробования. Этот метод подразумевает последовательный перебор элементовв K до тех пор, пока не будет получено истинное значение. Бывает, что значенияв K неравновероятны, и тогда можно осуществить их направленный перебор, начавс самых вероятных. Трудоёмкость такого перебора определяется как математическоеожидание длины перебора - количества опробованных значений, вычисляемое по фор-нмуле M = Е Qj ' j , где H - мощность множества K , Qj -вероятность j -го значения иj=iКак правило, вычислить трудоёмкость перебора по этой формуле невозможно в силунеобъятности множества значений. Поэтому необходимо строить легковычислимуюоценку трудоёмкости. В данной предлагается использовать следующий вероятностныйалгоритм.Разобъём множество K на два подмножества одинаковой мощности h = H/2. ОбозначимМ0 трудоёмкость перебора значений в K , Mi - трудоёмкость перебора значенийв блоке разбиения (будем предполагать, что она одинакова для обоих блоков),р0 -вероятность того, что искомое значение находится в первом блоке, pi = 1 - p0 -вероятность того, что искомое значение находится во втором блоке. Пусть p0 ^ pi .Любая сумма вида У] qj ■ j , где (ii , ... , %н) есть перестановка чисел 1,... , H , являетсяоценкой сверху для величины М .Если предположить, что значения в блоках перебираются последовательно, то естьсначала все элементы первого (более вероятного) блока, затем - все элементы второго,то получим следующую оценку:Если по очереди выбирать по одному элементу из каждого блока, то оценка будетследующей:Первая оценка будет близка к истинной в случае, когда вероятность pi близкак нулю; вторая - если вероятности р0 и pi примерно равны. Обе оценки не позволяютобъективно оценить трудоёмкость в случае, когда обе вероятности значительные, нов разы различаются между собой.Рассмотрим следующий способ перебора значений: в первую очередь опробуем nэлементов первого блока, затем будем по очереди выбирать оставшиеся элементы первогоблока и (h - n) элементов второго, затем - остаток второго блока. Тогда оценкаимеет виднj=iМ0 = Mi + pih. (1)Mo = 2Mi - po. (2)Mo(n)Mi + T + ti , если ti > t2;Mi + T + t3 иначе, (3)где(Mi - 1)(h2 + h - 2hn + n2 - n - 2)= Po h2 + h + 2n - 2*3 - g (k - 1) ^2Mi + 1 - J (2M i + 1)2 - 8k^k = h n.В формуле (3) можно варьировать параметр и и выбирать такой, при которомзначение M0(n) наименьшее. Этот подход оправдал себя, во многих случаях выдаваяв эксперименте более точные результаты по сравнению с формулами (1), (2).Величина М1 в формулах (1) - (3) находится по одному из блоков разбиения, причемс вероятностью р0 - по первому блоку и с вероятностью р1 - по второму. ВычисляетсяМ1 аналогично М0 -разбиением соответствующего блока на два подмножества,и так до тех пор, пока не получатся одноэлементные блоки, трудоёмкость перебораэлементов в которых равна 1.Описанные действия предлагается повторить многократно и в качестве результатавзять среднее арифметическое полученных оценок. Практические исследования показывают,что погрешность метода составляет до 17%.

Скачать электронную версию публикации