سه شنبه 5 اردیبهشت 1396 | Tuesday 25 th of April 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
5-2-6 حمله حدس و تعیین Biham,Dunkelmanبه طرح A5/1 در سال 2000

ساختار فرض شده A5/1در مقاله Biham,Dunkelman  مطابق با ساختار حقیقی ان است که در بخش قبل بیان شد. این حمله با اضافه کردن پیچیدگی داده سعی بر کاهش پیچیدگی پردازش (زمانی) دارد .

ایده اصلی حمله مذکور به این صورت است که فرض می کنیم مقدار R3[10](بیت ورودی مدار کنترل) به گونه ای باشد که LFSRشماره سه در طی 10 انتقال مولد انتقالی نداشته باشد.

به عبارت دیگر اکثریت در این 10 بار به هنگام شدن  مولد با بیتهای کنترل دو LFSR دیگر است.به این ترتیب اگر R3[10]را حدس بزنیم ، با توجه به این 10 انتقال ، 11 معادله به صورت زیر بدست می اید.

  (5-3)                                     

به این ترتیب 20 بیت از دو LFSRشماره 1و2 به دست می اید . از طرفی با حدس R3[22](خروجی LFSRشماره سه به ازای 10 انتقال مذکور ) و داشتن خروجی مولد در 11 زمان متناظر با انتقالها 11 معادله دیگر برای خروجی دو LFSRبه دست می اید.

R1[t]R2[t]=y(t) R3[22] , t=8,…,18                         (5-4)                                   

با توجه به رابطه های  (5-3)و (5-4) و روابط بازگشتیLFSRبا حدس 10خانهR2[0],R1[18],R1[17],R1[16],R1[15],R1[14],R1[12],R1[11],R1[10],R1[9]بقیه خانه های R1,R2معین می شوند.به این ترتیب تا این مرحله از حمله نیاز به  بار عملیات بهنگام سازی داریم .

برای محاسبه مقادیر خانه های R3نیز با حدس R3[0]تاR3[9]و محاسبه معکوس رابطه بازگشتی برای به صورت متوسط به 16 انتقال مولد و عملیات بررسی حدس مورد نظر (دو انتقال مولد ) می توان به این منظور دست یافت که پیچیدگی  دارد.

بنابراین پیچیدگی حمله مذکور  بار بهنگام سازی  است ، البته مشروط به درستی فرض این که در این 10 انتقال مولد LFSR3انتقال نیابد که در حقیقت 20بیت کنترل انتقال دو LFSRدیگر را محدود می کند و احتمال ان است .

این امر سبب می گردد پیچیدگی زمانی و پیچیدگی داده ای یک حمله موفق به A5/1با این روش به ترتیب وباشد.Bihamپیچیدگی این حمله را از طریق ذخیره سازی حالات متوالی LFSRها در جداول حالت تا حد قابل قبولی پایین اورد.

با ذخیره کردن تمامی حالت های متوالی سه LFSRبرای دوره تناوب هر یک در جدول حالت (با فضایی حدود 72 مگابایت) پیچیدگی زمان به  می رسد.

در بهترین وضعیت حمله فوق ،با افزایش حافظه تا حد 64 گیگا بایت و طرح مرحله ای پیش پردازش  انتقال مولد،پیچیدگی زمانی پردازش به و پیچیدگی داده به (معادل 2.36دقیقه مکالمه)رسید.

 

شکل5-2: شکل الف : حدس بیت کلاک  )R3کهبا G نشان داده شده) و تعیین19 بیت کلاک R1و R2که با  Dنشان داده شده است) ومجموع چهار بیت که با dنشان داده شده است. شکل ب : حدس 12 بیت دیگر از حالت داخلی (که با Gنشان داده شده است و تعیین 31 بیت باقیمانده که با Dنشان داده شده است.

 

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