معرفی حمله بده بستان زمان-حافظه (TMTO) بر توابع چکیده ساز

در این مقاله به معرفی حمله TMTO و نحوه پیدا کردن نزدیک- برخوردها در یک تابع چکیده ساز پرداخته شده است. با در نظر گرفتن محاسبات چکیده ساز، محاسبه یک حد پایین برای پیچیدگی الگوریتم های نزدیک - برخورد و ساخت یک الگوریتم مطابق با آن آسان است؛ با این حال، این الگوریتم نیاز به مقدار زیادی حافظه دارد و موجب استفاده از حافظه می شود. به تازگی، چند الگوریتم بدون نیاز به این مقدار حافظه ارائه شده اند. این الگوریتم ها نیاز به مقدار بیشتری از محاسبات چکیده ساز دارند؛ اما این حمله در واقعیت عملی تر است. این دسته از الگوریتم ها را به دو دسته اصلی می توان تقسیم کرد: گروهی مبتنی بر کوتاه سازی و گروهی دیگر مبتنی بر کد های پوششی هستند. در این کار، بده بستان زمان - حافظه برای الگوریتم های مبتنی بر کوتاه سازی در نظر گرفته شد. برای پیاده سازی عملی، می توان فرض کرد مقداری از حافظه موجود است و نشان داد که با استفاده از این حافظه قابل توجه پیچیدگی را می توان کاهش داد؛ در مرحله بعد، با استفاده از برخورد های متعدد براساس جدول هلمن، بهبود شناخته شده ترین بده بستان زمان حافظه، برای Kدرخت ارائه شد. در نتیجه، منحنی بده بستان جدید به دست آورده شد، با در نظرگرفتن k = 4 منحنی بده بستان به شکل خواهد بود. در این مقاله، ابتدا روش های TMTO و سپس نحوه پیدا کردن نزدیک-برخورد با استفاده از TMTO شرح داده می شود.