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


XML English Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Gharavi N H, Mirqadri A, Abdollahi azgomi M, Mousavi S A. Expected coverage rate for the Hellman matrices. JSDP. 2018; 15 (3) :47-58
URL: http://jsdp.rcisp.ac.ir/article-1-607-fa.html
غروی ناصرحسین، میرقدری عبدالرسول، عبدالهی ازگمی محمد، موسوی سید احمد. امید ریاضی نرخ پوشش برای ماتریس‌های هلمن. پردازش علائم و داده‌ها. 1397; 15 (3) :47-58

URL: http://jsdp.rcisp.ac.ir/article-1-607-fa.html


دانشگاه جامع امام حسین (ع)
چکیده:   (364 مشاهده)

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

متن کامل [PDF 4821 kb]   (138 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: مقالات گروه رمز
دریافت: ۱۳۹۶/۹/۱۶ | پذیرش: ۱۳۹۷/۵/۳ | انتشار: ۱۳۹۷/۹/۲۸ | انتشار الکترونیک: ۱۳۹۷/۹/۲۸

فهرست منابع
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.

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA code

ارسال پیام به نویسنده مسئول


کلیه حقوق این تارنما متعلق به فصل‌نامة علمی - پژوهشی پردازش علائم و داده‌ها است.