Отпечаток пальца Рабина

Схема снятия отпечатков пальцев Рабина (также известная как полиномиальная дактилоскопия ) — это метод реализации отпечатков пальцев с использованием полиномов над конечным полем . Его предложил Майкл О. Рабин . ^[1]

Схема

Учитывая n- битное сообщение m ₀ ,..., m _n-1 , мы рассматриваем его как многочлен степени n -1 над конечным полем GF(2) .

f(x)=m_{0}+m_{1}x+\ldots +m_{n-1}x^{n-1}

Затем мы выбираем случайный неприводимый полином ⁠ $p(x)$ ⁠ степени k над GF(2), и мы определяем отпечаток сообщения m как остаток $r(x)$ после разделения $f(x)$ к $p(x)$ над GF(2), который можно рассматривать как полином степени k - 1 или как k -битное число.

Приложения

Многие реализации алгоритма Рабина-Карпа внутренне используют отпечатки пальцев Рабина.

Сетевая файловая система с низкой пропускной способностью (LBFS) от Массачусетского технологического института использует отпечатки пальцев Рабина для реализации устойчивых к сдвигу блоков переменного размера. ^[2]Основная идея заключается в том, что файловая система вычисляет криптографический хэш каждого блока в файле. Чтобы сэкономить на переводах между клиентом и сервером,они сравнивают свои контрольные суммы и передают только те блоки, контрольные суммы которых различаются. Но одна проблема с этой схемой заключается в том, что одна вставка в начало файла приведет к изменению каждой контрольной суммы, если используются блоки фиксированного размера (например, 4 КБ). Таким образом, идея состоит в том, чтобы выбирать блоки не на основе конкретного смещения, а на основе некоторого свойства содержимого блока. LBFS делает это, перемещая окно размером 48 байт по файлу и вычисляя отпечаток Рабина для каждого окна. Когда младшие 13 бит отпечатка равны нулю, LBFS вызывает эти 48 байтов как точку останова, завершает текущий блок и начинает новый. Поскольку выходные данные отпечатков пальцев Рабина псевдослучайны, вероятность того, что любые данные 48 байтов являются точкой останова, равна $2^{-13}$ (1 из 8192). Это создает эффект устойчивых к сдвигу блоков переменного размера. Для разделения длинного файла на блоки можно использовать любую хеш-функцию (при условии, что затем используется криптографическая хеш-функция для нахождения контрольной суммы каждого блока): но отпечаток Рабина является эффективным скользящим хешем , поскольку вычисление отпечатка Рабина региона B может повторно использовать часть вычислений отпечатка пальца Рабина региона A, когда регионы A и B перекрываются.

Обратите внимание, что это проблема, аналогичная той, с которой сталкивается rsync . ^{[ нужен пример ]}

См. также

Ссылки

^ Майкл О. Рабин (1981). «Отпечатки пальцев с помощью случайных полиномов» (PDF) . Центр исследований в области вычислительных технологий Гарвардского университета. Технический отчет TR-CSE-03-01 . Проверено 22 марта 2007 г.
^ Атича Мутитачароен, Бенджи Чен и Дэвид Мазьер «Сетевая файловая система с низкой пропускной способностью»

Внешние ссылки

Андрей З. Бродер (1993). «Некоторые применения метода снятия отпечатков пальцев Рабина» . стр. 143–152 . Проверено 12 сентября 2011 г.
Дэвид Андерсен (2007). «Использование сходства для загрузки из нескольких источников с использованием отпечатков файлов» . Проверено 12 апреля 2007 г.
Росс Н. Уильямс (1993). « Безболезненное руководство по алгоритмам обнаружения ошибок CRC ».

Эта статья, посвященная криптографии, незавершена . Вы можете помочь Википедии, расширив ее .

[1] Майкл О. Рабин (1981). «Отпечатки пальцев с помощью случайных полиномов» (PDF) . Центр исследований в области вычислительных технологий Гарвардского университета. Технический отчет TR-CSE-03-01 . Проверено 22 марта 2007 г.

[2] Атича Мутитачароен, Бенджи Чен и Дэвид Мазьер «Сетевая файловая система с низкой пропускной способностью»

[1]

[2]