شنبه 2 بهمن 1395 | Saturday 21 st of January 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
5-2-8-3 معرفی حملات همبستگی سریع

Nبیت اغازین دنباله خروجی یک LFSRبه طول Lرا می توان بصورت یک کد خطی(N,L)  در نظر گرفت. این کد بصورت یکتا توسط چند جمله ای پس خورد[1] مشخص می گردد.

در حمله همبستگی پایه که در مثال های قبلی توضیح داده شد ، تمامی حالت های یک LFSRبرای رسیدن به حالت مناسب باید جستجو شوند و بنابراین ، در حملات همبستگی سریع به دنبال روشی برای کاهش پیچیدگی این جستجو هستیم.

Meier, Staffelbachبا تغییر اندکی در مدل مذکور ،حمله همبستگی سریع را معرفی کردند.  به این مدل می توان به شکل ارسال خروجی یک LFSRاز یک کانال  متقارن باینری (BSC)با احتمال خطای 1-pتوجه کرد . فرض کنید همبستگی بین خروجی یک LFSRو دنباله خروجی وجود دارد بطوریکه  .

مجموع اثرات سایر LFSRها و تابع غیر خطی در احتمال خطای کانال BSC، مدل می شود. با توجه به خطی بودن رابطه بازگشتی ساختار پس خوردLFSR، مقادیر به ازای tهای مختلف در معادلات خطی متناظر با چند جمله ای پس خورد صدق می کند.

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

اخیرا ایده کانال مخابراتی مورد توجه johnssonقرار گرفت و با استفاده از کد های کانولوشن[2] و الگوریتم کد گشایی ویتربی[3] توانستند الگوریتم حمله همبستگی سریع را بطور قابل ملاحظه ای بهبود دهند . این الگوریتم مستقل از وزن چند جمله ای پس خورد است



[1]  Feedback Polynomial

[2]  Convolutional Codes                                          2  Viterbi Decoding Algorithm

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