Skip to content
بازگشت به نتایج جست‌وجو

تحلیل رمز خطی

معرفی‌شده توسط
Mitsuru Matsui
سال
1993
نوع
linear approximation attack
خانواده
Cryptanalytic technique

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

تحلیل رمز خطی یک حمله با متن آشکار شناخته شده است که از تقریب‌های خطی تبدیل‌های غیرخطی رمزنگاری شده برای بازیابی بیت‌های کلید مخفی سوء استفاده می‌کند. تحلیل رمز خطی که توسط میتسورو ماتسویی در سال ۱۹۹۳ معرفی شد، حملات عملی را بر روی رمزنگاری‌هایی مانند DES با پیچیدگی محاسباتی کمتر از جستجوی فراگیر ارائه می‌دهد. این تکنیک، سوگیری‌های آماری را در چگونگی ارتباط ترکیب‌های خطی بیت‌های متن آشکار و متن رمز شده با بیت‌های کلید تحلیل می‌کند و بازیابی کلید را با نیازهای داده‌ای کاهش یافته امکان‌پذیر می‌سازد.

شهود پشت روش

تحلیل رمز خطی معادلات خطی را که بیت‌های متن آشکار، بیت‌های متن رمز شده و بیت‌های کلید را به هم مرتبط می‌کنند، پیدا می‌کند. به دلیل اختلاط غیرکامل در دورهای رمزنگاری، این معادلات خطی با احتمالی کمی بهتر از تصادفی برقرار هستند. با جمع‌آوری جفت‌های متعدد متن آشکار-متن رمز شده و مشاهده اینکه کدام مقادیر کلید باعث می‌شوند این معادلات بیشتر برقرار باشند، مهاجم می‌تواند کلید صحیح را محدود کند.

تاریخ

تحلیل رمز خطی توسط ماتسویی در سال ۱۹۹۳ به عنوان یک حمله با متن آشکار شناخته شده بر روی DES معرفی شد. در سال ۱۹۹۴، ماتسویی اولین تحلیل رمزنگاری تجربی استاندارد DES را با استفاده از تحلیل رمز خطی نشان داد و کلیدی را با ۲^۴۳ متن آشکار شناخته شده بازیابی کرد. این پیشرفت، حملات عملی را در برابر یک استاندارد مستقر نشان داد و با مقاومت اثبات شده، بر توسعه AES تأثیر گذاشت.

چه زمانی استفاده شود

تحلیل رمز خطی در تحقیقات تحلیل رمزنگاری و ارزیابی طراحی رمزنگاری استفاده می‌شود. این امر طراحان رمزنگاری را در انتخاب جعبه‌های S و تبدیل‌هایی که در برابر تقریب‌های خطی مقاوم هستند، راهنمایی می‌کند. رمزنگاری‌های مدرن با حدود اثبات شده برای قدرت تقریب خطی طراحی شده‌اند.

محدودیت‌ها و ملاحظات

  • رمزنگاری‌های مدرن (AES) با دقت برای مقاومت در برابر تحلیل رمز خطی با حدود قابل اثبات طراحی شده‌اند
  • نیاز به جفت‌های متن آشکار-متن رمز شده شناخته شده دارد که ممکن است در همه سناریوها در دسترس نباشند
  • الزامات محاسباتی و داده‌ای می‌تواند از امکان‌سنجی عملی برای رمزنگاری‌های خوش‌طراحی فراتر رود
  • کشف تقریب‌های خطی قوی برای رمزنگاری‌های مدرن بسیار دشوار است

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • حمله عملی بر روی DES که به ۲^۴۳ جفت متن آشکار-متن رمز شده و ۲^۳۹ عملیات نیاز دارد
  • چارچوب ریاضی کاملاً فرموله شده (لم انباشتگی) برای تحلیل سوگیری‌های تقریب
  • تحلیل رمزنگاری دیفرانسیل را تکمیل می‌کند و ضعف‌هایی را پیدا می‌کند که تحلیل دیفرانسیل ممکن است از دست بدهد
  • الزامات طراحی رمزنگاری برای انتخاب جعبه S و تبدیل دور را شکل می‌دهد

کاربردها

  • تحلیل رمزنگاری رمزنگاری‌های بلوکی ارزیابی خواص امنیتی در تحقیق و استانداردسازی
  • طراحی رمزنگاری و انتخاب جعبه S برای اطمینان از حدود کافی تقریب خطی
  • اعتبارسنجی استانداردهای رمزنگاری (NIST, ETSI) که نیاز به تحلیل مقاومت خطی دارند
  • ارزیابی رمزنگاری‌های قدیمی برای تصمیم‌گیری‌های بازنشستگی و جایگزینی

چگونه کار می‌کند

چگونه کار می‌کند

1

یافتن تقریب‌های خطی: روابط خطی بین بیت‌های متن آشکار، بیت‌های متن رمز شده و بیت‌های کلید که با احتمالی به طور قابل توجهی متفاوت از ۰.۵ برقرار هستند.

2

تخمین سوگیری (انحراف از ۰.۵) هر تقریب خطی با استفاده از تحلیل آماری تبدیل‌های دور.

3

برای مقادیر کلید کاندید، تعداد دفعاتی که تقریب خطی در جفت‌های متن آشکار-متن رمز شده شناخته شده برقرار است را بشمارید. کلید صحیح باعث می‌شود تقریب بیشترین فراوانی را داشته باشد.

4

تأیید بیت‌های کلید بازیابی شده با رمزگشایی متن رمز شده و بررسی صحت.

دام‌های رایج

  • فرض اینکه همه تقریب‌های خطی قابل سوء استفاده هستند؛ تقریب‌های ضعیف مزیت حداقلی را فراهم می‌کنند
  • دست کم گرفتن دشواری حمله عملی زمانی که الزامات داده‌ای نظری معقول به نظر می‌رسند
  • نادیده گرفتن تعامل بین خواص خطی و دیفرانسیل در تحلیل رمزنگاری

پرسش‌های متداول

لم انباشتگی چیست؟

لم انباشتگی روشی برای محاسبه سوگیری تقریب‌های خطی در چندین دور با ترکیب سوگیری‌های تقریب‌های دور منفرد ارائه می‌دهد. این لم اساس تحلیل رمز خطی است.

AES چگونه در برابر تحلیل رمز خطی مقاومت می‌کند؟

AES از جعبه‌های S انتخاب شده برای به حداقل رساندن احتمال حداکثر تقریب خطی و یک لایه انتشار استفاده می‌کند که انتشار سریع سوگیری‌های خطی را در دورها تضمین می‌کند. حدود اثبات شده هیچ تقریب خطی عملی را تضمین نمی‌کنند.

تفاوت بین تحلیل رمز خطی و دیفرانسیل چیست؟

تحلیل دیفرانسیل تفاوت‌های ورودی-خروجی را مطالعه می‌کند، در حالی که تحلیل خطی تقریب‌های خطی (XOR بیت‌های متن آشکار و متن رمز شده) را مطالعه می‌کند. هر دو از ضعف‌های ساختاری در رمزنگاری‌ها سوء استفاده می‌کنند.

آیا تحلیل رمز خطی می‌تواند رمزنگاری‌های مدرن را بشکند؟

عملاً خیر. رمزنگاری‌های مدرن مانند AES دارای حدود قابل اثبات برای تقریب‌های خطی هستند که حملات را از نظر محاسباتی غیرممکن می‌سازد.

چگونه مقاومت خطی را در طراحی رمزنگاری خود ارزیابی کنم؟

جداول تقریب خطی جعبه S را تحلیل کنید و حداکثر سوگیری را از طریق دورها با استفاده از لم انباشتگی محاسبه کنید. اطمینان حاصل کنید که حداکثر سوگیری در تمام تقریب‌های خطی ممکن ناچیز است.

روش‌های مرتبط

منابع

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    باز کردن مرجع DOI
    کپی شد.
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    باز کردن مرجع DOI
    کپی شد.