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

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

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

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

واژه‌های کلیدی: مصالحه حافظه‌زمان، تابع یک‌طرفه، ماتریس هلمن، امید ریاضی نرخ پوشش
متن کامل [PDF 4821 kb]   (1055 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: مقالات گروه رمز
دریافت: 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.
ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA
ارسال پیام به نویسنده مسئول

بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.

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