معرفی حمله بده بستان زمان-حافظه (TMTO) بر توابع چکیده ساز
نویسنده:
نوع مقاله:
مقاله پژوهشی/اصیل (ترویجی)
چکیده:
در این مقاله به معرفی حمله TMTO و نحوه پیدا کردن نزدیک- برخوردها در یک تابع چکیده ساز پرداخته شده است. با در نظر گرفتن محاسبات چکیده ساز، محاسبه یک حد پایین برای پیچیدگی الگوریتم های نزدیک - برخورد و ساخت یک الگوریتم مطابق با آن آسان است؛ با این حال، این الگوریتم نیاز به مقدار زیادی حافظه دارد و موجب استفاده از حافظه می شود. به تازگی، چند الگوریتم بدون نیاز به این مقدار حافظه ارائه شده اند. این الگوریتم ها نیاز به مقدار بیشتری از محاسبات چکیده ساز دارند؛ اما این حمله در واقعیت عملی تر است. این دسته از الگوریتم ها را به دو دسته اصلی می توان تقسیم کرد: گروهی مبتنی بر کوتاه سازی و گروهی دیگر مبتنی بر کد های پوششی هستند. در این کار، بده بستان زمان - حافظه برای الگوریتم های مبتنی بر کوتاه سازی در نظر گرفته شد. برای پیاده سازی عملی، می توان فرض کرد مقداری از حافظه موجود است و نشان داد که با استفاده از این حافظه قابل توجه پیچیدگی را می توان کاهش داد؛ در مرحله بعد، با استفاده از برخورد های متعدد براساس جدول هلمن، بهبود شناخته شده ترین بده بستان زمان حافظه، برای Kدرخت ارائه شد. در نتیجه، منحنی بده بستان جدید به دست آورده شد، با در نظرگرفتن k = 4 منحنی بده بستان به شکل خواهد بود. در این مقاله، ابتدا روش های TMTO و سپس نحوه پیدا کردن نزدیک-برخورد با استفاده از TMTO شرح داده می شود.
کلیدواژگان:
زبان:
فارسی
انتشار در:
صفحات:
15 تا 26
لینک کوتاه:
magiran.com/p1803509
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!