تحلیل روش مصالحه زمان- حافظه با استفاده از گراف تصادفی

نویسندگان

دانشگاه جامع امام حسین(ع)

چکیده

در این مقاله، روش مصالحه زمان- حافظه (TMTO)، برای تحلیل رمزهای قالبی و روش‌های منطبق با آن بررسی می‌شود. همچنین، موضوع‌های پوشش در زنجیرهای هلمن، تصادم در این زنجیره‌ها، دورها و طوقه‌هایی که در یک تابع رمز قالیی ایجاد می‌شود مورد بحث قرار می‌گیرند. برای تحلیل روش هلمن از گراف تصادفی استفاده می‌شود. گراف تصادفی از روی تابع رمز قالبی ساخته شده و از آن برای استخراج زنجیره‌های بدون تصادم، دورها و طوقه‌ها استفاده می‌شود. با توجه به حالت‌ها و ویژگی‌های یکتای گراف ساخته‌شده، یک روش جدید برای استخراج دورها و طوقه‌ها در گراف تصادفی تحت عنوان "چابک‌سازی گراف" ارایه می‌شود. این روش به آسانی و با هزینه خیلی کم، دورها و طوقه‌های موجود در تابع رمز قالبی را استخراج میکند. دورها و طوقه‌های به‌دست‌آمده، برای تولید زنجیره‌های بدون تصادم در رمزهای قالبی مورد استفاده قرار گرفته و باعث پوشش کامل کلیدهای رمز قالبی در روش TMTO می‌شوند.

کلیدواژه‌ها


M. Helman, “A cryptanalytic time-memory trade off,” IEEE Transactions on Information Theory, vol. 26, no. 4, pp. 401–406, 1980.
E. Barkan, E. Biham, and A. Shamir, “Rigorous Bounds on Cryptanalytic Time/Memory Trade Offs,” Lecture note in computer science, pp. 1-21, 2006.
E. Barkan, E. Biham, and A. Shamir, “Rigorous Bounds on Cryptanalytic Time/Memory, “Proceedings of Crypto 2006, LNCS 4117, pp. 1-21, 2006.
N. A. Saran, “Time memory trade off attack on symmetric ciphers,” Applied Mathematics of Middle East Technical University, Feb. 2009.
M. Sourav, “A study on time/memory trade off cryptanalysis,” Applied Statistical Unit Indian Statistical 203, B. T. Road, Calcutta 700 108, INDIA, March 2006.
A. Shamir, “Random Graph in Security and Privacy,” The Weizmann Institute, Hifa, June 2010.
A. Shamir, “Random Graph in Cryptography,” The Weizmann Institute I...., Haifa, May 2007.
A. Doganakosy and S. Nurdan, “Variant Constructions for TMTO based on Random Mapping Statistics,” in 3rd Information Security & Cryptology Conferece With International Participation, Ankara, December 2008.
A. Gaini, “Introduction for probability thory,” The Publishing Center of Imam Hussein, Tehran, 1979.
S. Haridi and P. Roy, “Concepts, Techniques and Models of Computer Programing,” Universit´e catholique de Louvain (at Louvain-la-Neuve), 2003.
A. Renyi and P. Erdos, “On Random Graph,” Publication Mathematicas 6, pp. 290-297, Nov. 1958.
H. A. Zakerzade, H. Bigdeli, and M. A. Iranmanesh, “The concept of random graphs and models,” The Student publication Statistics (Neda), Tehran, vol. 7, no. 2, pp. 30-34, 2010.
E. Upfal and M. Mitzenmacher, “Balls, Bins, Random Graphs (Balls-and-Bins Model),” Probability and Computing, published by Cambridge University Press, 2005.