RAM: 64 Gbps DDR 1600
HV: 1 Tb 6Gbps
فصل سوم
شناسایی پارامترهای اسکرمبلرهای خطی
شناسایی پارامترهای اسکرمبلرهای خطی
مسئله ای که در اینجا به بررسی آن می پردازیم در حوزه ی مهندسی معکوس سیستم های مخابراتی قرار می گیرد. در این حالت هدف، یافتن اطلاعات مربوط به مخابره استراق سمع شده است در حالی که فرد استراق سمع کننده مشخصات و ویژگی های سیستم انتقال دهنده‌ی استفاده شده را نمی‌داند. حتی زمانی که در سیستم ارتباطی هیچگونه رمزنگاری استفاده نشود و یا مشخصات آن به طور عمد پنهان نشوند، مهندسی معکوس در این مرحله به چند دلیل کار سختی محسوب می شود. نخست اینکه برای هر عنصر در سیستم گزینه های انتخابی زیادی وجود دارد، بعلاوه سیگنال استراق سمع شده در حین ارسال دچار خطاهایی می شود. بنابراین شخص استراق سمع کننده هم باید خطاها را مشخص و رفع کند و هم ویژگی های هر عنصر را در سیستم های ارتباطی بازیابی کند که شامل یافتن اسکرمبلر و تصحیح خطای کد می باشد. مسئله‌ی بررسی تصحیح خطای کد در[۴] و [۵]بررسی شده است. در این بخش ما به شناسایی عنصر دیگری در سیستم های مخابراتی که اسکرمبلرهای خطی می باشند می پردازیم [۶].

اسکرمبلرهای خطی در واقع یک طرح مخابراتی برای شکستن توالی زیادی از بیت‌های یکسان در یک دنباله می‌باشند که این بیت‌های یکسان و پشت سرهم می‌توانند باعث مشکلاتی در همزمان سازی^[۱۲] شوند. یک اسکرمبلر خطی شامل شیفت رجیستر فیدبک خطی می‌باشد که خروجی آن با دنباله ورودی ترکیب می‌شود. دو نوع متفاوت از اسکرمبلرهای خطی وجود دارد:
شکل ‏۳‑۱ الف) اسکرمبلر جمعی ب)اسکرمبلرضربی [۶]
اسکرمبلرهای همزمان^[۱۳] و اسکرمبلرهای خود هماهنگ شده^[۱۴]. تفاوت این دو نوع اسکرمبلر همان‌طور که در شکل ۳-۱ نشان داده شده است مربوط به چگونگی ترکیب خروجی LFSRها با دنباله ورودی می باشد.
در اینجا روش متفاوتی برای بازیابی مشخصه های این دو نوع اسکرمبلر بر اساس اطلاعاتی که از خروجی آن‌ها  داریم، بیان می کنیم. اطلاعاتی که ما از خروجی اسکرمبلر داریم وابسته به متن ارسالی می‌باشد و تا حد زیادی روی تکنیک های بازیابی که می‌توانند مورد استفاده قرار بگیرند تاثیر می‌گذارد. وقتی در مورد بازیابی ویژگی‌های اسکرمبلرهای خطی در طرح های ارتباطی صحبت می‌کنیم به طور ضمنی بیان کرده‌ایم تصحیح خطای کد^[۱۵] صورت گرفته است. اگر خطای کدها شناسایی شود باز هم ممکن است با کدگذارهای مختلفی مطابقت داشته باشد. در واقع، حتی اگر فضای خطی تشکیل دهنده کلمه کدها مشخص شود ما قادر به تعیین اساس کدگذاری انجام شده نخواهیم بود. بنابراین دنباله‌ی قبل از کدگذار که همان دنباله خروجی اسکرمبلر می‌باشد را در نظر می گیریم. ما در اینجا تنها کدهای بلوکی را در نظر می‌گیریم و به کدگذارهای کانولوشنی نمی‌پردازیم. این نشان می دهد که خروجی اسکرمبلر تحت یک تبدیل خطی با بلوک هایی به اندازه k قرار می گیرد که k ابعاد تصحیح خطای کد درگیر می باشد.
در ادامه نماد میدان باینری با دو عنصر است و L طول LFSR می‌باشد. این طول را کمتر از  فرض می‌کنیم و در عمل نیز  می‌باشد. چندجمله ای فیدبک را با نماد P به صورت  نمایش می‌دهیم و دنباله‌ی  که توسط این LFSR تولید می‌شود به صورت  به ازای تمام  می‌باشد.
تشخیص پارامترهای اسکرمبلر شامل یافتن طول آن، چندجمله ای فیدبک و در مورد اسکرمبلرهای سنکرون، حالت اولیه آن می باشد. علاوه بر داشتن دنباله خروجی  به داشتن برخی فرضیات بر روی دنباله ورودی  نیز احتیاج داریم چرا که هر دنباله باینری می تواند از خروجی از هر اسکرمبلری به دست آمده باشد. ما در اینجا دو فرضیه مختلف بر روی دنباله های ورودی در نظر می‌گیریم: چه برخی بیت های ورودی را بدانیم و یا اینکه هیج کدام از بیت های دنباله ورودی را ندانیم. در هر صورت فرض می کنیم که بیت های دنباله ورودی توسط یک منبع بدون حافظه بایاس دار به صورت  و  تولید شده است. اگرچه این فرضیه در نگاه اول محدودیت ایجاد می‌کند اما در عمل زمانی که قسمتی از ورودی شامل برخی رشته های سربار ویا چیدمان فریم‌های سیگنال و یا غیره باشد این رابطه وجود دارد. فرضیه دوم نیز شامل بسیاری موارد عملی می‌باشد مانند استفاده از کد‌گذارهای کلاسیکی مثل  در تولید دنباله ورودی می باشد. مقادیر معمول برای بایاس  ،  و  می باشند.
در قسمت‌های بعدی فرض می‌کنیم که هم تصحیح خطای کد صورت گرفته است و هم اینکه نوع کدگذار را می‌دانیم به این معنی که دقیقاً همان دنباله خروجی از اسکرمبلر خطی را در دسترس داریم. دراین قسمت و در بخش های بعدی یک سری روش هایی برای بازیابی ویژگی های اسکرمبلرهای خطی بر اساس همان فرضیه های گفته شده بر دنباله ورودی ارائه می‌کنیم.
تشخیص پارامترهای اسکرمبلر با بهره گرفتن از دنباله متن ورودی x(t)
در این قسمت روشی برای بازیابی ویژگی های اسکرمبلرهای همزمان با داشتن دو فرضیه بر روی دنباله ورودی آنها می پردازیم این دو فرضیه شامل اینکه برخی از بیت های دنباله ورودی را می‌دانیم و یا اینکه در حالت دیگر بیت‌های دنباله ورودی را نمی‌دانیم اما بایاس دنباله را می‌دانیم، می‌باشد. قابل ذکر است که برای اسکرمبلرهای سنکرون چندجمله‌ای فیدبک باید بنیادین^[۱۶]باشد در غیر این صورت دوره تناوب دنباله تولید شده بهینه نخواهد بود[۷] .
فرض می کنیم M بیت پشت سرهم دنباله ورودی را داریم در این حالت با اضافه کردن این بیت ها به دنباله خروجی بیت های متناظر با بیت های دنباله ی LFSR به دست خواهند آمد. پس از آن با اجرای الگوریتم برلکمپ-مسی بر روی این M بیت دنباله ی LFSR ، می توان چندجمله ای فیدبک اسکرمبلر را به دست آورد. از آنجایی که این الگوریتم نیاز با داشتن  بیت از دنباله ی LFSR را دارد چندجمله ای فیدبک اسکرمبلر به محض داشتن  بیت از دنباله ی ورودی، قابل بازیابی می باشد. پیچیدگی زمانی اجرای این الگوریتم به شدت به طول موثر LFSR بستگی دارد حتی اگر از قبل این طول را بدانیم. در واقع در i-امین تکرار الگوریتم برلکمپ-مسی، LFSR کمینه طولی که می تواند نخستین i-بیت دنباله را تولید کند تعیین می شود. بنابراین برای  در i-امین تکراردر الگوریتم تنها چک می شود که  (i-امین بیت متناظر) توسط LFSR قبلی به دست خواهد آمد یا خیر. پس در تکرار iام الگوریتم زمانی که  باشد به اندازه  عملیات محاسبه انجام می شود و زمانی که  باشد در حدود  عملیات محاسبه انجام می شود. بنابراین تعداد کل محاسبات مورد نیاز برای بازیابی اسکرمبلربا طول L با بهره گرفتن از M بیت ورودی تقریباً برابر است با :

تشخیص پارامترهای اسکرمبلرجمعی فقط با بهره گرفتن از بایاس متن ورودی
اگرچه دانستن ورودی برای بازیابی مشخصات اسکرمبلر یک فرضیه بسیار قوی است (دقیقاً مانند دانستن متن اصلی در عملیات رمزگشایی). در برخی شرایط عملی تنها اطلاعات در دسترس برای مهاجم^[۱۷] این است که اطلاعات ورودی توسط یک منبع حافظه که از نظر آماری دارای بایاس می باشد، تولید شده است. این بایاس ممکن است به علت مشخصه‌ های آماره های زبان به کار رفته و یا روش کدگذاری مورد استفاده، (به عنوان مثال کدهای  ) ایجاد شده باشد. بنابراین در حال حاضر فقط فرض می‌کنیم که دنباله‌ی پیام ورودی احتمال  با بایاس  می‌باشد.
الگوریتم کلوزیو برای شناسایی چندجمله‌ای فیدبک بسیار شبیه به تکنیک ارائه شده [۸] در اما در زمینه‌ای متفاوت می‌باشد. ایده اصلی این است که دنباله خروجی اسکرمبلر برخی از آماره‌های بایاس را با خود دارد و بدین وسیله ما قادر خواهیم بود مضاربی از چندجمله‌ای فیدبک را آشکارسازی کنیم و پس از آن می‌توان چند جمله ای فیدبک را توسط تست های آماری که جزئیات آن در قضیه ۱ آمده است، تعیین نمود. البته این نتیجه‌گیری‌ها نیاز به دانستن لم زیر دارد:
لم۱:
اگر متغیر تصادفی  و متغیر  به ازای برخی مقادیر ثابت و صحیح  که  باشد از هم مستقل باشند و متغیر تصادفی  را به صورت  تعریف کنیم و میانگین آن را با  و واریانس آن را با  نشان دهیم، زمانی که  را تا بی‌نهایت افزایش دهیم متغیر  به متغیری تصادفی با توزیع استاندارد نرمال متمایل می شود.
اثبات: بدون از دست دادن کلیت موضوع می‌توان فرض کرد که  خواهیم داشت  .
اگر  باشد می‌توان آن را به دو بخش کاربردی  و  تجزیه کرد که در آن  و  می‌باشد. پس:

با انتخاب هایی که در مجموعه  داریم می‌توان نوشت  . اندازه مجموعه  همیشه کوچکتر از  می‌باشد در حالی که با افزایش N اندازه مجموعه  تا بی‌نهایت رشد می‌کند. بنابراین خواهیم داشت:

حال اگر بنویسیم:

قسمت دوم در سمت راست معادله زمانی که N تا بی نهایت افزایش می‌یابد قابل چشم‌پوشی است چون V متشکل از  جمله می‌باشد. قسمت اول معادله نیز تقریباً برابر خواهد شد با

چنانچه مجموعه  طوری انتخاب شود که به ازای هر  ،  و  از هم مستقل باشند ، قضیه حد مرکزی در رابطه بالا بیان می‌کند که با افزایش N تا بی نهایت،  دارای توزیع نرمال استاندارد خواهد بود.
قضیه ‏۳‑۱ :
اگر  خروجی یک اسکرمبلر همزمان، با ورودی  با شرایط  باشد و Q یک چندجمله‌ای در میدان به صورت  و متغیرهای

و

را بدین صورت بیان کنیم که  تعداد تک جملاتی است که در چندجمله ای های  و  به طور مشترک وجود دارد. حال اگر  مضربی از چندجمله‌ای فیدبک LFSR باشد متغیر تصادفی  با افزایش N تا بی‌نهایت، دارای توزیع نرمال استاندارد خواهد بود.
اثبات: با توجه به تعریف متغیر  می توان نوشت

چرا که زمانی که  مضربی از چند جمله‌ای فیدبک  باشد  خواهد بود و چون  یک متغیر مستقل با بایاس  می‌باشد می‌توان با بهره گرفتن از رابطه جبری  احتمال  را به صورت زیر محاسبه نمود: