سه شنبه 2 آبان 1396 | Tuesday 24 th of October 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
5-2-8-4 معرفی حملات همبستگی سریع در رمز کننده های پی در پی

وجود همبستگی زیاد بین دنباله های خروجی Zو دنباله خروجی LFSRیعنی  به معنای ان است که می توان انتظار داشت که تعداد بیتهای زیادی از این دو دنباله با یکدیگر مساوی باشند.

فرض کنید تعداد ضرایب فیدبک غیر صفر LFSRبرابرtباشد در این صورت هر بیت  از دنباله  در چند رابطه برگشتی که هر کدام شامل tرقم از دنباله است صدق می کند .

صدق نمودن در این روابط می تواند معیاری برای تساوی  باشد ، بنابراین با داشتن چند جمله ای مشخصه LFSRو ضرایب فیدبک می توان روابط برگشتی هر بیت را نوشته و صدق نمودن  متناظر در انها را بررسی نمود.

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

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

مثال:

فرض کنید  بوده و رابطه برگشتی رقم هفتم دنباله یعنی را بخواهیم. رابطه اصلی برای همه ارقام دنباله عبارت است از :                                                                           

با مربع نمودن C(x)داریم :

بطور کلی هر گاه Nرقم از دنباله Zرا داشته باشیم ، بطور متوسط mرابطه خطی برای هر رقم می توان یافت که:

(5-19)                                                      

هر چه Nو tبیشتر باشند تعداد روابط برگشتی بیشتر خواهد بود .

با تعریف    می توان ثابت نمود که:                                                                                                                                                            

            =)حداقل درhرابطه صدق کند)P=Q

R=P(   رابطه صدق کندوhحداقل در(  (5-20)                که iاز hتا mتغییر می کندو Sاز رابطه برگشتی زیر بدست می اید.

 (5-21)                                              

در حقیقت sاحتمال صدقدر یک رابطه برگشتی است که هر بار با افزایش j، تغییر می کند .

بنابراین احتمال صدقدر iرابطه برگشتی برابر است با:

(5-22)                                                                            

بنابراین داریم:

t: احتمال تطابق وبه شرط صدقدر hرابطه

افزایش mاختیار ما را در انتخاب hبگونه ای که احتمالات T,Qهمزمان زیاد شوند بیشتر می کند و روشن است که افزایش Q(به جهت کاهش حجم عملیات و امکان انجام حمله با Nکمتر )و افزایش T(به جهت کمتر نمودن احتمال خطا ) بطور همزمان مطلوب می باشد.

مراحل اجرای حمله همبستگی سریع:

1)mرا بیابید.       

2)حداکثر hرا بگونه ای بیابید که

3)تعداد متوسط خطاها برابر است با:

4)ارقامی از Zرا که حداقل در hرابطه برگشتی صدق می کنند بدست اورید.

5)با تغییر حداکثر rبیت در دنباله بدست امده ،فاز صحیح دنباله را بدست اورید.

پیچیدگی محاسباتی این روش است که C<1بوده و به مقادیر بستگی دارد .به عنوان مثال هر گاه  باشد به ازای مقادیر مختلف qوtجدول زیر به عنوان نمونه اورده می شود.

12

10

8

6

4

2

t  

q

1

1

1

1

1

0.999

0.51

0.993

0.993

0.993

0.993

0.992

0.870

0.55

0.965

0.965

0.965

0.963

0.926

0.132

0.61

0.934

0.934

0.932

0.917

0.734

0.007

0.65

0.868

0.863

0.836

0.692

0.150

0

0.71

0.800

0.771

0.660

0.311

0.009

0

0.75

 

با توجه به این جدول دو نتیجه حاصل می شود.

1.                     اول اینکه برای یک qخاص هر چه tکمتر باشد Cکاهش یافته و در نتیجه پیچیدگی محاسباتی برای شکستن سیستم کمتر می شود و دوم اینکه برای یک tخاص هر چه qبیشتر باشد Cکمتر خواهد بود.

2.                     بنابراین در طراحی ترکیب کننده های حالت بایستی حتی الامکان qکوچک (نزدیک2/1)و tیعنی تعداد ضرایب فیدبک غیر صفر زیاد باشد.

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