سه شنبه 6 تیر 1396 | Tuesday 27 th of June 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
5-2-12-2 تکنیک نمونه برداری

در FSE2000,Shamir,Biryukov,Wagner  یک روش نمونه برداری معرفی کردند که برای حمله به رمز دنباله ای خاص A5/1مورد استفاده قرار گرفت و در انجا حالت کلی استفاده از این تحلیل برای سایر رمز های دنباله ای مورد توجه قرار نگرفت .ShamirوBiryukovحالت کلی این تعمیم را بررسی کردند و این روش را تکنیک نمونه برداری BSWنامیدند که در زیر معرفی می گردند.

ایده اصلی نمونه برداری BSWاین است که در بسیاری از رمزهای دنباله ای ، حالت مولد متاثر تعداد کمی از بیتها ی قبلی است . لذا می توان همه حالتها ی ویژه را با یک الگوی مشخص kبیتی ( برا یمقدار کوچک k) تولید،شمارش و کد گذاری نمود بدون اینکه این حالت ها را به روش سعی و خطا تولید کنیم .

این کار اغلب برای k=1امکان پذیر است و درمواردی که بیت خروجی به تعدا کمی از بیت های حالت بستگی داشته باشد ، ساده تر صورت میگیرد اما به ازای مقادیر بزرگتر k، تحمیل کردن الگوی خاصی برای خروجی مشکل تر است.

این روش نمونه برداری قابل اعمال به رمز های قالبی نیست ، زیرا شمارش و تولید کلیدهایی که متن رمز شده معادل یک متن ثابت را با الگوی خاصی تولید می کند ، بدون سعی و خطا امکان پذیر نیست.

اگر k  بیشترین مقداری باشد ، که این شمارش را بطور مستقیم می توان انجام داد ، در این صورت  را مقاومت نمونه برداری سیستم می نامیم .

با استفاده از روش نمونه برداری BSWمی توان حمله بده بستان BGرا بدون افزایش زمان پیش پردازش انجام داد . در حالیکه روش نمونه برداری Rivestزمان پیش پردازش را با ضریب 1/Rافزایش می دهد.

حال روش  استفاده از تکنیک نمونه برداری BSWرا برای بهبود بده بستان BSWتوضیح می دهیم . یک رمز دنباله ای با  حالت را در نظر بگیرید . هر حالت یک کد کامل[1] nبیتی دارد . همچنین به هر حالت یک کد خروجی[2] که شامل nبیت اول دنباله خروجی ان است ، نسبت می دهیم .

اگر سیستم دارای مقاومت نمونه برداری  [3]باشد ، میتوانیم به هر حالت ویژه ، یک کد کوتاه[4] n-kبیتی نسبت دهیم که با استفاده از روندی که برای شمارش در نظر گرفته ایم بدست می اید . همچنین به هر خروجی ویژه میتوان یک کد خروجی کوتاه n-kبیتی اختصاص داد که به راحتی از حذف kبیت اول کد خروجی بدست می اید.

بنابراین می توان یک تابع تصادفی جدید روی مجموعه کاهش یافته عضوی ، نقاط ویژه تعریف کنیم که بصورت زیر عمل می کند

                                                شکل5-5 نحوه ذخیره زوج های ورودی و خروجی کوتاه شده

شکل5-5 نحوه ذخیره زوج های ورودی و خروجی کوتاه شده

در بین Dنقطه خروجی انتظار داریم که DRخروجی ویژه موجود باشد(فرض می کنیم که(، بنابراین در حمله بده بستان BSWکافیست Dرا به DRو Nرا به NRتبدیل کنیم. رابطه  تغییر نمی کند .

لذا روابط بده بستان BSWبا تکنیک نمونه برداری BSWبه صورت زیر در می اید.

(5-43)                                                                               

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

دیگر اینکه تعداد جستجو در حافظه نسبت به قبل تغییر نکرده است . اگر از تکنیک نمونه برداری Rivestاستفاده کنیم مانند قبلی می توان ان را به tکاهش داد.


[1]  Full Name                                                                    2  Output name

[3]  Sampling Resistance                                                   4  Short name

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