جمعه 5 خرداد 1396 | Friday 26 th of May 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
5-2-5 حملات حدس و تعیین Golic به طرح A5/1 در سال 1997

در ساختار فرض شده A5/1در مقاله Golic، مرحله پنجم فرایند تولید کلید بگونه ای دیگر است . در ساختار فرضی ، بعد 100 بار انتقال غیر منظم بدون تولید کلید اجرایی ، به ترتیب 114 بار انتقال غیر منظم به منظور تولید کلید اجرایی رمز نگاری (ارسال داده ) ،100 با ر انتقال غیر منظم بدون  تولید کلید و در نهایت 114 بار انتقال غیر منظم به منظور تولید کلید اجرایی رمز گشایی (دریافت داده) انجام می گیرد .

به عبارتی تعداد انتقال در یک دور تولید کلید 228 بیتی ، به جای 328بیت،428 است.در ]در مقاله Golic[  نشان داده شده است که دوره تناوب A5/1تقریبا" به اندازه دوره تناوب بزرگترین LFSRیعنی  است. تحلیل A5/1توسط Golicشامل یک حمله حدس و تعیین و یک حمله بده-بستان زمان وحافظه است .

در این بخش حمله حدس و تعیین را بررسی می کنیم.  از نکات مهم این حمله فرضی است که در مورد استقلال انتقال LFSRها صورت گرفته است که سبب می شود احتمال انتقال هر LFSRدر لحظه t  برابر 4/3 باشد.

دراینجا نشان داده شده است که مجموعه حالات درونی ممکن  الگوریتم برای هر زمان t>0زیر فضای غیر کامل  است.

تعداد اعضای این مجموعه برای t=1حدود است که نشان میدهد احتمال این که دو حالت 64 بیتی متفاوت به یک حالت بعدی منجر شود وجود دارد که البته پایین است .

نکته دیگر این که به دلیل همبستگی پایین بین بیتها ( خاصیت LFSRهاو تابع XOR) می توان بیان کرد که دو دنباله کلید متفاوت با احتمال نزدیک به 1 در 64 بیت اول دارای این تفاوت است .

در مرحله اول می خواهیم مقدار S(101)را روی دنباله کلید رمز نگاری یعنیو  تعیین کنیم . برای  این منظور ابتدا از هر LFSRبه تعداد nبیت (n<20) از حالت تا  ( یک دنباله n-بیتی پیوسته) حدس می زنیم که به این ترتیب 3nمعادله به دست می اید .

با توجه به احتمال انتقال هر یک از LFSRها در مجموع هر nانتقال LFSRدر ازای 3/4n  انتقال کل مولد ( لحظه ) اتفاق می افتد و مطابق این زمانها و مقدار y(101)تعداد معادله خروجی بدست می اید .

بنابراین باید معادلات از مجهولات ( حالات ممکن برای S(101)) بیشتر یا مساوی گردد.

 (5-2)                                                           

که پیچیدگی حدس 3nبیت برابر با است . البته با استفاده از روش شاخه ای ( درخت) این عدد را تا مرتبه نیز می توان پایین اورد. بعد از یافتن S(101)نوبت به محاسبه S(0)می رسد.

در این مرحله دنباله خروجی موجود نیست ، اما برای هر LFSRحالت درونی ان در لحظه 101 موجود است . به این ترتیب با توجه به انتقال تصادفی LFSRها احتمال اینکه LFSRشمارهiبه تعداد kانتقال از 100 انتقال داشته باشد یک توزیع دو جمله ای (100 ,k)  با میانگین 76 و واریانس 18.94 است.

 از این رو پیچیدگی یافتن S(0)بصورت متوسط و در بدترین حالت است که قابل صرفنظر است .

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

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26