زهرا ذوالفقاری، نصور باقری،
دوره ۶، شماره ۱ - ( ۶-۱۳۹۶ )
چکیده
در این مقاله به معرفی حمله TMTO و نحوه پیدا‌کردن نزدیک- برخوردها در یک تابع چکیدهساز پرداخته شده است. با درنظرگرفتن محاسبات چکیدهساز، محاسبه یک حد پایین برای پیچیدگی الگوریتمهای نزدیک - برخورد و ساخت یک الگوریتم مطابق با آن آسان است؛ با این حال، این الگوریتم نیاز به مقدار زیادی حافظه دارد و موجب استفاده از حافظه می‌شود. به‌تازگی، چند الگوریتم بدون نیاز به این مقدار حافظه ارائه شده‌اند. این الگوریتمها نیاز به مقدار بیشتری از محاسبات چکیدهساز دارند؛ اما این حمله در واقعیت عملی‌تر است. این دسته از الگوریتمها را به دو دسته اصلی میتوان تقسیم کرد: گروهی مبتنی بر کوتاه‌سازی و گروهی دیگر مبتنی بر کد‌های پوششی هستند. در این کار، بده‌بستان زمان-حافظه برای الگوریتمهای مبتنی بر کوتاه‌سازی در نظر گرفته شد. برای پیاده‌سازی عملی، میتوان فرض کرد مقداری از حافظه موجود است و نشان داد که با استفاده از این حافظه قابل‌توجه پیچیدگی را میتوان کاهش داد؛ در مرحله بعد، با استفاده از برخورد‌های متعدد براساس جدول هلمن، بهبود شناخته‌شده‌ترین بده‌بستان زمان حافظه، برای Kدرخت ارائه شد. در‌نتیجه، منحنی بده‌بستان جدید به‌دست آورده شد، با درنظرگرفتن k = ۴ منحنی بده‌بستان به شکل خواهد بود. در این مقاله، ابتدا روشهای TMTO و سپس نحوه پیدا‌کردن نزدیک-برخورد با استفاده از TMTO شرح داده می‌شود.
