Основы современной криптографии


Криптосистемы Меркля-Хеллмана и Хора-Ривеста - часть 4


Во-первых, отметим, что любая супервозрастающая последо­вательность должна расти экспоненциально, поскольку минимальная супервозрастающая последовательность – это степени двойки. Во-вторых, отметим, что причина, по которой используются супервозрастающие последовательности заключается в том, что любая h-элементная сумма из нее уникальна.

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

Пусть GF(p) – поле целых чисел по модулю простого числа p, и GF(ph) – расширение степени h основного поля. Также пусть 1 – вектор, все элементы которого равны 1.

С формальной точки зрения мы строим последовательность длины p, такую что для любого i от 0 до p – 1

1 Ј ai Ј ph – 1

и для каждых различных x, y, таких что x*1 = y*1 = h, x*a

и y*a также должны быть различны. Мы можем представлять векторы x

и y как битовые (т.е. содержащие только 0 и 1).

Далее построение проводится довольно просто. Во-первых, выберем t – алгебраический элемент степени h над GF(p), т.е. минимальный многочлен с коэффициентами из GF(p), корнем которого является t, имеет степень h. Далее выберем g – мультипликативный генератор (примитивный элемент) поля GF(ph), т.е. для каждого элемента x из GF(ph) (кроме нуля) существует некоторое i, такое, что g в степени i

будет равно x.

Теперь рассмотрим аддитивный сдвиг GF(p), т.е. множество

t + GF(p) = {t + i

| 0 Ј i Ј p – 1 } М GF(ph)

Пусть каждый элемент вектора a будет логарифмом по основанию g соответствующего элемента из t+GF(p):

ai

= logg(t+i)

Мы должны проверить, что a, определенная подобным образом, удовлетворяет заданным свойствам. Определенно, каждый элемент в a




Начало  Назад  Вперед