اثر انگشت (رایانش)
در علوم رایانه، یک الگوریتم انگشت‌نگاری رویه‌ای است که داده‌های به اندازه دلخواه بزرگ (مانند فایل‌های کامپیوتر) را به رشتهٔ خیلی کوچک‌تری از بیت‌ها نگاشت می‌کند، که به آن اثر انگشت (به انگلیسی: Fingerprint) می‌گویند، که مانند اثر انگشت انسان، به صورت منحصر به فردی دادهٔ اصلی را برای مقاصد عملی مشخص می‌کند. این اثر انگشت می‌تواند برای مبارزه با تکثر داده استفاده شود. این اثر انگشت برای مقاصدی از جمله داده کاوی استفاده می‌شود و به آن همچنین با عناوینی چون انگشت‌نگاری فایل، انگشت‌نگاری داده، یا انگشت‌نگاری داده‌های ساختاریافته اشاره می‌شود.
اثر انگشت‌ها معمولاً برای جلوگیری از مقایسه و انتقال داده‌های بزرگ استفاده می‌شوند. برای مثال، مرورگر وب یا سرور پروکسی می‌تواند فقط با گرفتن اثر انگشت یک فایل دور از آن و مقایسه آن با کپی قبلی به صورت کارآمد بررسی کند که آیا این فابل تغییر داده شده‌است یا نه.
توابع انگشت نگاری شاید مانند توابع هش کردن با عملکرد بالا، برای مشخص کردن تودهٔ قابل توجهی از داده‌ها به صورت منحصر به فرد، در حالی که توابع هش رمزنگاری مورد نیاز نیستند به نظر برسند.
خاصیت‌ها
منحصر به فرد بودن مجازی
برای تحقق اهداف مورد نظر، در یک الگوریتم انگشت نگاری احتمال برخورد (دو فایل متفاوت، اثر انگشت مشابه داشته باشند) باید ناچیز باشد. مثلاً: حدود 10 یا کمتر.
از این لحاظ تا حدودی به مشابه توابع سرجمع است؛ البته به مراتب سخت گیرانه تر. برای شناسایی خطاهای تصادفی داده یا خطاهای ایجاد شده هنگام انتقال، کافی است که سرجمع‌های فایل اصلی و هر نسخه خراب، با اطمینان خاصی (مطابق با برخی مدل‌های آماری برای خطاها) با یکدیگر متفاوت باشد. در شرایط عادی، این هدف به آسانی با سرجمع‌های ۱۶ یا ۳۲ بیتی به دست می‌آید. در مقابل، اثر انگشت فایل باید حداقل ۶۴ بیت طول داشته باشد تا منحصر به فرد بودن مجازی در سیستم فایل بزرگ را تضمین کند (نگاه کنید به حمله روز تولد).
هنگام اثبات نیازمندی فوق، باید توجه داشته باشید که فایل‌ها با فرایندهای بسیار غیر تصادفی ایجاد می‌شوند که وابستگی‌های پیچیده بین فایل‌ها را ایجاد می‌کنند. به عنوان مثال، در یک شبکه معمولی کسب و کار، معمولاً یک جفت یا مجموعه ای از اسناد را پیدا می‌کند که فقط در ویرایش‌های جزئی یا سایر تغییرات جزئی با یکدیگر متفاوت‌اند. یک الگوریتم انگشت نگاری خوب باید اطمینان حاصل کند که چنین پردازش‌های طبیعی دارای اثر انگشت متمایز با اطمینان مورد نیاز است.
ترکیب کردن
فایل‌های کامپیوتری اغلب با روش‌های مختلف ترکیب می‌شوند، مانند پیوند زنجیره ای (در فایل‌های آرشیو) یا شامل سازی‌های نمادین(include# مستقیم در پیش‌پردازنده c). برخی از الگوریتم‌های انگشت نگاری، اثر انگشت یک فایل مرکب از چند فایل دیگر را از اثر انگشت‌های بخش‌های آن محاسبه می‌کنند. این ویژگی ترکیبی ممکن است در بعضی موارد کاربردهای مفیدی داشته باشد، مثلاً تشخیص زمانی که یک برنامه باید مجدداً کامپایل شود.
الگوریتم‌ها
الگوریتم رابین
الگوریتم انگشت نگاری رابین سریع و آسان است در پیاده‌سازی، دارای قابلیت ترکیب و آنالیز دقیق ریاضی برای محاسبه احتمال برخورد است. به این صورت که احتمال یکسان بودن اثر انگشت‌های w بیتی برای رشته‌های متفاوت به طول‌های r و l بیت از max(r,s)/2 بیشتر نیست. این الگوریتم نیاز به انتخاب قبلی یک کلید داخلی w بیتی دارد و این کلید تا زمانی قابل استفاده است که رشته‌های مورد نظر برای انگشت نگاری بدون اطلاع از آن انتخاب شوند. روش رابین در برابر حملات مخرب امن نیست. عامل مداخله‌کننده می‌تواند به راحتی کلید را بیابد و از آن برای تغییر فایل‌ها بدون تغییر اثر انگشت استفاده کند.
توابع هش در رمزنگاری
توابع هشی که در رمزنگاری به کار می‌روند می‌توانند به عنوان تابع انگشت نگاری با کیفیت بالا مورد استفاده قرار گیرد، زیرا برای سخت‌تر کردن رمزگشایی مورد استفاده قرار می‌گیرند و باور بر این است که در مقابل حملات مخرب، ایمن هستند.
ولی از معایب توابعی از این دسته (مانند MD5 و SHA) نسبت به توابع ساده‌تر (مانند الگوریتم رابین) این است که به زمان نسبتاً طولانی تری برای هش کردن رشته‌ها نیاز است. همچنین اثباتی برای ضمانت احتمال برخورد مورد انتظار وجود ندارد. بعضی از این الگوریتم‌ها، مخصوصاً MD5، دیگر برای انگشت نگاری ایمن توصیه نمی‌شوند. با این حال این الگوریتم‌ها هنوز برای بررسی خطا، در جاهایی که مداخله عمدی در داده‌ها نگرانی اصلی نیست، قابل استفاده هستند.
انگشت نگاری و برچسب گذاری برای پایگاه داده‌های ارتباطی
انگشت نگاری و برچسب گذاری برای پایگاه داده‌های ارتباطی به عنوان راه حل‌های مناسب برای حفظ حق نسخه برداری، شناسایی تهاجم، ردیابی خیانت کار و حفظ یکپارچگی داده‌های ارتباطی ظاهر شدند. برای اشاره به این اهداف، بسیاری از تکنیک‌ها در ادبیات ارائه شده‌اند. بررسی وضعیت فعلی و طبقه‌بندی رویکردهای مختلف با توجه به هدف آنها، نحوه بیان اثر انگشت / برچسب، نوع پوشش، سطح دانه بندی و قابل اطمینان بودن آنها در دسترس است.
نمونه کاربردها
NIST یک کتابخانه مرجع نرم‌افزاری (کتابخانه مرجع نرم‌افزار ملی آمریکا) را توزیع می‌کند که با استفاده از توابع هش در رمزنگاری برای انگشت نگاری فایل‌ها و نگاشت آنها به محصولات نرم‌افزاری می‌پردازد. پایگاه داده HashKeeper، که توسط مرکز ملی مواد مخدر نگهداری می‌شود، مخزن اثر انگشت‌های «شناخته شده به عنوان خوب» و «شناخته شده به عنوان بد» فایل‌های رایانه، برای استفاده در کاربردهای مربوط به اجرای قانون است (به عنوان مثال در تجزیه و تحلیل محتویات دیسک‌های جمع‌آوری شده).
جستارهای وابسته
منابع
- ↑ A. Z. Broder. Some applications of Rabin's fingerprinting method. In Sequences II: Methods in Communications, Security, and Computer Science, pages 143--152. Springer-Verlag, 1993
- ↑ Detecting duplicate and near-duplicate files. US Patent 6658423 Issued on December 2, 2003
- ↑ A. Z. Broder (1997). On the Resemblance and Containment of Documents (PDF). Proceedings of Compression and Complexity of Sequences. IEEE Computer Society. pp. 21–27. CiteSeerX 10.1.1.24.779. doi:10.1109/SEQUEN.1997.666900. ISBN 978-0-8186-8132-5. Archived from the original (PDF) on 21 February 2018. Retrieved 24 May 2019.
- ↑ Brin, S. and Davis, J. and Garcia-Molina, H. (1995) Copy Detection Mechanisms for Digital Documents. In: ACM International Conference on Management of Data (SIGMOD 1995), May 22-25, 1995, San Jose, California, from stanford.edu. Archived 18/08/2016. Retrieved 11/01/2019.
- ↑ L. Fan, P. Cao, J. Almeida and A. Broder, Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol, IEEE/ACM Transactions on Networking, vol. 8, No. 3 (2000)
- ↑ U. Manber, Finding Similar Files in a Large File System. Proceedings of the USENIX Winter Technical Conf. (1994)
- ↑ M. O. Rabin Fingerprinting by random polynomials. Center for Research in Computing Technology Harvard University Report TR-15-81 (1981)
- ↑ http://www.jucs.org/jucs_16_21/watermarking_techniques_for_relational/jucs_16_21_3164_3190_halder.pdf