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

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

Схема [ править ]

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

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

Затем мы выбираем случайный неприводимый многочлен степени k над GF (2) и определяем отпечаток сообщения m как остаток после деления на над GF (2), который можно рассматривать как многочлен степени k -1. или как k- битное число. ${\ displaystyle p (x)}$ ${\ Displaystyle г (х)}$ ${\ displaystyle f (x)}$ ${\ displaystyle p (x)}$

Приложения [ править ]

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

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

Обратите внимание, что это проблема, аналогичная той, с которой сталкивается rsync .

См. Также [ править ]

Ссылки [ править ]

^ Майкл О. Рабин (1981). «Отпечатки пальцев случайными многочленами» (PDF) . Центр исследований в области компьютерных технологий Гарвардского университета. Технический отчет TR-CSE-03-01 . Проверено 22 марта 2007 . Цитировать журнал требует |journal=( помощь )CS1 maint: обескураженный параметр ( ссылка )
^ Athicha Muthitacharoen, Бенджи Chen и Дэвид Mazieres «с низкой пропускной способностью сетевой файловой системы»

Внешние ссылки [ править ]

Андрей З. Бродер (1993). «Некоторые применения метода дактилоскопии Рабина» . Проверено 12 сентября 2011 . Цитировать журнал требует |journal=( помощь )CS1 maint: обескураженный параметр ( ссылка )
Дэвид Андерсен (2007). «Использование сходства для загрузки из разных источников с помощью файловых отпечатков» . Проверено 12 апреля 2007 . Цитировать журнал требует |journal=( помощь )CS1 maint: обескураженный параметр ( ссылка )
Росс Н. Уильямс (1993). « Безболезненное руководство по алгоритмам обнаружения ошибок CRC ».

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

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

[2] Athicha Muthitacharoen, Бенджи Chen и Дэвид Mazieres «с низкой пропускной способностью сетевой файловой системы»

[1]