دوره 15، شماره 3 - ( 9-1397 )                   جلد 15 شماره 3 صفحات 58-47 | برگشت به فهرست نسخه ها

‎ 10.29252/jsdp.15.3.47

XML English Abstract Print

امید ریاضی نرخ پوشش برای ماتریس‌های هلمن
ناصرحسین غروی* ، عبدالرسول میرقدری ، محمد عبدالهی ازگمی ، سید احمد موسوی
دانشگاه جامع امام حسین (ع)
چکیده:   (4932 مشاهده)

مصالحه حافظه‌زمان یک الگوریتم احتمالاتی برای وارون‌کردن توابع یک‌طرفه، با استفاده از داده‌های از پیش محاسبه‌شده است. هلمن در سال ۱۹۸۰ این روش را معرفی کرد و یک کران پایین برای احتمال موفقیت آن به‌دست آورد. پس از آن نیز تحلیل‌های پژوهش‌گران برای بررسی احتمال موفقیت، بر اساس همین کران پایین بوده است. در این مقاله، ابتدا به بررسی امید ریاضی نرخ پوشش یک ماتریس هلمن می‌پردازیم؛ سپس، این نرخ را برای ماتریس‌های هلمنی که فقط از یک زنجیره تشکیل شده‌اند، محاسبه کرده‌ایم. نشان داده‌ایم که امید ریاضی نرخ پوشش برای چنین ماتریس‌هایی بیشینه و برابر با ۸۵/۰ است. در ادامه، روش‌هایی برای تخمین دقیق‌تر این نرخ ارائه، و با روش هلمن مقایسه و در‌نهایت، ماتریس‌های هلمنی را معرفی کرده‌ایم که فقط از یک زنجیره تشکیل شده‌اند؛ ولی طول این زنجیره مقداری ثابت نیست و تا رسیدن به نخستین تکرار ادامه می‌یابد. به‌صورت نظری و عملی نشان داده‌ایم که احتمال موفقیت برای چنین ماتریس‌هایی بیشتر از روش هلمن است.
 

واژه‌های کلیدی: مصالحه حافظه‌زمان، تابع یک‌طرفه، ماتریس هلمن، امید ریاضی نرخ پوشش
متن کامل [PDF 4821 kb]   (1929 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: مقالات گروه رمز
دریافت: 1396/9/16 | پذیرش: 1397/5/3 | انتشار: 1397/9/28 | انتشار الکترونیک: 1397/9/28
فهرست منابع
1. [1] E. Barkan, E. Biham and A. Shamir, "Rigorous bounds on cryptanalytic time/memory tradeoffs", in Advances in Cryptology: Proceedings of Crypto, LNCS, 2006, 4117, pp. 1–21.
2. [2] J. Borst, "Block Ciphers: Design, Analysis and Side-Channel Analysis", PhD thesis, Katholieke Universiteit Leuven, 2001.
3. [3] D.E. Denning, Cryptography and data security, Addison-Wesley, 1982.
4. [4] P. Flajolet, and A. Odlyzko, "Random mapping statistics", Advances in Cryptology, Proceedings of Eurocrypt'89, LNCS, 1990, 434, pp. 329–354.
5. [5] P. Flajolet, and R. Sedgewick, An introduction to analysis of algorithms, Addison-Wesley, 2013.
6. [6] B. Harris, "Probability distributions related to random mappings", The Annals of Mathematical Statistics, pp. 1045–1062, 1960. [DOI:10.1214/aoms/1177705677]
7. [7] M. Hellman, "A cryptanalytic time-memory trade-off", IEEE Transactions on Information Theory IT, vol. 26, pp. 401–406, 1980. [DOI:10.1109/TIT.1980.1056220]
8. [8] J. Hong, and S. Moon, "A comparison of cryptanalytic tradeoff algorithms", Journal of cryptology, vol. 26 (4), pp. 559-637, 2013. [DOI:10.1007/s00145-012-9128-3]
9. [9] J. Hong and B.I. Kim, "Performance comparison of cryptanalytic time memory data tradeoff methods", Bull. Korean Math. Soc., vol. 53(5), pp. 1439-1446, 2016. [DOI:10.4134/BKMS.b150754]
10. [10] V. Kolchin, "Random mapp-ings", Translations series in mathematics and engineering, Optimization Software, Inc., Publications Division, 1986.
11. [11] K. Kusuda, and T. Matsumoto, "Optimization of time-memory trade-off cryptanalysis and is application to DES", FEAL-32, and Skipjack, E-79A, pp. 35–48, 1996.
12. [12] G. W. Lee, and J. Hong, "Comparison of perfect table cryptanalytic tradeoff algorithms", Designs, Codes and Cryptography, pp. 473-523, 2016. [DOI:10.1007/s10623-015-0116-0]
13. [13] R.C. Phan, "Mini advanced encryption standard (mini-AES): a testbed for cryptanalysis students", Cryptologia, vol. 26(4), pp. 283-306, 2002. [DOI:10.1080/0161-110291890948]
14. [14] Ph. Oechslin, "Making a faster cryptanaly-tic time-memory trade-off", Annual International Cryptology Conference, Springer Berlin Heidelberg, 2003.
بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.