اثر انگشت رابین

طرح اثرانگشت رابین (یا اثرانگشت چند جمله ای) روشی برای اجرای اثرانگشت با استفاده از چند جمله ای ها بر روی یک میدان محدود است. این روش توسط مایکل او. رابین پیشنهاد شد. ^[۱]

طرح

با فرض پیام n-بیتی m₀,...,m_n-1، آن را یک چند جمله ای از درجه n-1 بر روی میدان متناهی GF(2) در نظر می گیریم.

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

یک چند جمله ای غیرقابل تجزیه (irreducible polynomial) p(x) از درجه k بر روی GF(2) را به طور تصادفی انتخاب می کنیم و اثرانگشت پیام m را باقیمانده r(x) تقسیم f(x) بر p(x) روی میدان متناهی GF(2) تعریف می کنیم که هم می توان یک چند جمله ای از درجه k-1 در نظر گرفت و هم یک عدد k-بیتی.

کاربردها

از اثر انگشت‌های رابین در اکثر پیاده‌سازی‌های الگوریتم Rabin–Karp استفاده می شود.

فایل سیستم شبکه با پهنای باند کم (LBFS) از MIT از اثر انگشت‌های رابین برای پیاده‌سازی بلوک‌های غیرقابل شیفت با اندازه متغیر استفاده می‌کند. ایده اصلی این است که فایل سیستم، هش رمزنگاری هر بلوکرا در یک فایل محاسبه می‌کند. برای صرفه‌جویی در انتقالات بین کلاینت و سرور، آن‌ها چک‌سام‌های خود را مقایسه می‌کنند و فقط بلوک‌هایی را که چک‌سام‌های آن‌ متفاوت است را منتقل می‌کنند. اما یکی از مشکلات این است که اگر از بلوک‌های با اندازه ثابت (مثلاً ۴ کیلوبایت) استفاده شود یک ورودی در ابتدای فایل باعث تغییر هر چک‌سام می‌شود. بنابراین بلوک‌ها را نه بر اساس یک آفست خاص بلکه بر اساس برخی ویژگی‌های محتوای بلوک انتخاب می کنیم. LBFS این کار را با کشیدن یک پنجره ۴۸ بایتی بر روی فایل و محاسبه اثر انگشت رابین هر پنجره انجام می‌دهد. زمانی که ۱۳ بیت پایین اثر انگشت صفر است، LBFS آن ۴۸ بایت را به عنوان یک نقطه شکست نامیده و بلوک فعلی را پایان می دهد و بلوک جدیدی را شروع می‌کند. از آنجایی که خروجی اثر انگشت‌های رابین شبه‌تصادفی است، احتمال اینکه هر ۴۸ بایت یک نقطه شکست باشد ${\displaystyle 2^{-13}}$ (1 در 8192) است. این به بلوک‌های غیرقابل شیفت با اندازه متغیر منجر می‌شود. از هر تابع هشی می‌توان برای تقسیم یک فایل بلند به بلوک‌ استفاده شود (به شرطی که یک تابع هش رمزنگاری برای پیدا کردن چک‌سام هر بلوک استفاده شود): اما اثر انگشت رابین یک هش چرخشی کارآمد است، زیرا زمانی که مناطق A و B همپوشانی دارند، می توان در محاسبه اثر انگشت رابین منطقه B از برخی محاسبات اثر انگشت رابین منطقه A استفاده کرد.

توجه داشته باشید که این مسئله مشابه مسئله‌ای است که در آرسینک (rsync) با آن مواجه می شوید.

منابع

1. Michael O. Rabin (1981). "Fingerprinting by Random Polynomials" (PDF). Center for Research in Computing Technology, Harvard University. Tech Report TR-CSE-03-01. Retrieved 2007-03-22.

پیوند به بیرون

• Andrei Z. Broder (1993). "Some applications of Rabin's fingerprinting method". pp. 143–152. Retrieved 2011-09-12.
• David Andersen (2007). "Exploiting Similarity for Multi-Source Downloads using File Handprints". Retrieved 2007-04-12.
• Ross N. Williams (1993). "A painless guide to CRC Error detection algorithms".