خلاصه پایان نامه تشخیص کور پارامترهای اسکرمبلرهای مبتنی بر LFSR، در داده‌های دیجیتالی
پایان‌نامه کارشناسی ارشد در رشته
مهندسی برق
مخابرات- سیستم
چکیده
تشخیص کور پارامترهای اسکرمبلرهای مبتنی بر LFSR، در داده‌های دیجیتالی
در سیستم‌های مخابراتی دیجیتال از اسکرمبلرهای خطی هم برای رمزنگاری ساده و هم برای شکستن توالی زیادی از بیت‌های یکسان استفاده می‌شود. موضوع توالی بیت ها، یعنی تعدد زیادی از صفرها و یک‌های پشت سرهم، معمولاً منجر به مشکلاتی در سنکرون سازی می‌شود. در واقع روش‌های سفید کردن آماره‌های منبع دیجیتالی بدون استفاده از داده‌های حشویات تحت عنوان اسکرمبلینگ بیان می‌شود. در مخابرات و دی‌کد کننده‌ها، اسکرمبلر دستگاهی است که داده‌ها را قبل از ارسال دستکاری می‌کند و آنها را تغییر می‌دهد. این تغییرات در گیرنده به طور معکوس انجام می‌شود تا به داده‌ی اولیه برسیم.
در این پایان‌نامه پس از معرفی اسکرمبلر و اجزای تشکیل دهنده‌ی آن به بررسی روش‌های یافتن پارامترهای اسکرمبلر در دو حالت در دست داشتن دنباله متن ورودی (روش برلکمپ-مسی) و حالت دیگر داشتن فقط دنباله‌ی اسکرمبل شده (الگوریتم کلوزیو)، پرداخته می‌شود و نتایج آن مورد بررسی قرار می‌گیرد. پس از آن حالتی را در نظر می‌گیریم که داده‌های اسکرمبل شده پس از عبور از کانال دچار خطا شده و در حضور نویز کانال به شناسایی پارامترهای اسکرمبلر می‌پردازیم و اثر نویز را روی داده‌های خروجی از دو نوع اسکرمبلر(اسکرمبلرهای ضربی و اسکرمبلرهای جمعی) مشاهده می‌کنیم. پس از آن به بررسی روش شناسایی چندجمله‌ای فیدبک اسکرمبلرهای خطی با فرض اینکه بیت‌های منبع قبل از اینکه اسکرمبل شوند توسط کدینگ اصلاح خطا کدگذاری شده‌اند، می‌پردازیم.
واژگان کلیدی: اسکرمبلر، ثبات‌های انتقال خطی با پسخورد ، رمزنگاری، کانال دودوئی متقارنBSC، شنود سیگنال
1-1- اسکرمبلر چیست و چرا از آن استفاده می کنیم؟
یک سیستم انتقال داده دیجیتالی همواره در ارسال داده‌ها آنها را دچار خطا و آسیب می‌کند که مقدار این اختلالات و آسیب‌ها بسته به آماره‌های منبع تغییر می‌کند. گاهی اوقات همزمان‌سازی، تداخل و مشکلات اکولایز کردن به آماره‌های منبع مربوط می‌شود. اگرچه استفاده از حشویات در ارسال کدها تا حدی عملکرد سیستم را از آماره‌های منبع مستقل می‌کند اما همواره وابستگی‌هایی وجود دارد به علاوه اضافه کردن داده‌های حشویات باعث مشکلاتی از قبیل افزایش نرخ سمبل‌های ارسالی و یا اضافه شدن تراز در سمبل‌ها می‌شود. در یک سیستم ارسال کد اگر فرض کنیم سمبل‌های ارسالی از نظر آماری از هم مستقل هستند آنالیز و خطایابی آن بسیار آسان‌تر خواهد شد. به چنین منبعی که سمبل‌های آن از نظر آماری از هم مستقل هستند منبع سفید می‌گوییم چرا که آنالیز آن مانند نویز سفید گوسی است. روش‌های سفید کردن آماره‌های منبع دیجیتالی بدون استفاده از داده‌های حشویات تحت عنوان اسکرمبلینگ[1] بیان می‌شود. در مخابرات و دی‌کد کننده‌ها، اسکرمبلر[2] دستگاهی است که داده‌ها را قبل از ارسال دستکاری می‌کند و آنها را تغییر می‌دهد. این تغییرات در گیرنده به طور معکوس انجام می‌شود تا به داده‌ی اولیه برسیم. انواع روش‌های اسکرمبلینگ در ماهواره و مودم‌های [3]PSTN مورد استفاده قرار می‌گیرد. اسکرمبلر را می‌توان درست قبل از یک کدگذار FEC[4] قرار داد یا اینکه می‌توان پس از FEC و قبل از بلوک مدولاسیون قرار داد.
سعی ما در این پژوهش بر این است که روش‌ها و تکنیک‌های مختلف در شناسایی پارامترهای اسکرمبلرهای خطی را مورد بررسی قرار دهیم. این کار با داشتن رشته بیت‌های خروجی و بر اساس فرضیه‌هایی روی بیت‌های ورودی اسکرمبلر انجام می‌شود. البته شخصی که این کار را با استفاده از بیت‌های خروجی انجام می‌دهد باید دو مقوله را در نظر بگیرد ابتدا اصلاح خطا و سپس استخراج پارامترهای اسکرمبلر. با توجه به خطی بودن اسکرمبلرهای مورد بحث، استفاده از روش‌های جبری برای تخمین پارامترهای اسکرمبلر کارآمدترین روش می‌باشد. خصوصاً شیفت رجیسترهای خطی با پسخورد که تابع فیدبک آنها تابعی خطی می‌باشد که در ادامه بیشتر در این باره توضیح داده شده است.
1-2- مزایای استفاده از اسکرمبلینگ قبل از ارسال داده
با این روش بدون اضافه کردن داده‌ی حشویات به پیام ارسالی، می توان در تجهیزات گیرنده دقت Time Recovery را افزایش داد.
با پراکنده نمودن انرژی در کل سیگنال حامل، احتمال تداخل سیگنال‌های حامل را کاهش می‌دهد و وابستگی چگالی طیفی بین داده‌های اسکرمبل شده و داده‌های واقعی ارسال شده را از بین می‌برد.
امنیت ارسال داده را بالا می‌برد و در رمزنگاری می‌توان از اسکرمبلرها استفاده کرد. چرا که حالت ایده‌آل یک متن رمز شده این است که یک دنباله‌ی کاملاً تصادفی باشد. به عبارتی بیت‌های دنباله از یکدیگر کاملاً مستقل باشند و احتمال صفر و یک بودن برابر باشد و بتوان از روی کلیدی محدود و کوتاه، دنبالهای طویل و [5]i.i.d تولید نمود.
1-3- دنباله‌های شبه تصادفی
به منظور شبیه سازی و تست سیستم‌های ارتباطی دیجیتال، به دنباله‌هایی که تقریبی ازدنباله های تصادفی دودویی ایده آل می‌باشند نیاز داریم. در تولید دنباله شبه تصادفی دودویی از شیفت رجیسترهای خطی فیدبکی استفاده می کنیم. می توان با یک تغییر ساده در این مدارها از آنها به عنوان اسکرمبلر/دی اسکرمبلر های خود سنکرون دیجیتال استفاده کرد. اسکرمبلر ها با شکستن رشته طولانی 0 یا 1در داده ها اجازه می دهند تا حلقه های ردیابی در گیرنده به شکل مخفی و پنهان حفاظت و نگهداری شود.
اگر نرخ داده بسیار بالا باشد، این اسکرمبلر ها و دی اسکرمبلر ها را می توان با مدارهای ساده ساخت. در نرخ متوسط داده ها مانند مودم خط تلفن ، آن را می توان با چند خط کد ساده اجرا کرد. ترکیب این تابع وسایر ویژگی های آن به کد ، می توان سخت افزارهای اضافی را از میان می برد. این روش قابلیت اطمینان را افزایش و هزینه های تولید را کاهش می دهد.
یک دنباله تصادفی دودویی ایده آل در واقع یک دنباله نامتناهی مستقل و دارای توزیع یکنواخت است که متغیرهای تصادفی در آن هر یک از مقادیر 0 یا 1 را با احتمال 0.5 می‌پذیرند. این دنباله را می توان با رشته داده های تولید شده توسط منابع دودویی مدل کرد. با شیفت رجیسترهای خطی فیدبکی می‌توان به بهترین تقریب برای دنباله های تصادفی دودویی دست یافت. دنباله‌ی به دست آمده به این روش شبه تصادفی ، شبه نویز ، حداکثرطول ، یا دنباله نامیده می‌شوند.
برای شبیه‌سازی دنباله دودوئی تصادفی، ما به دنبال شیفت‌رجیستری هستیم که اگر طول آن رجیستر باشد، دنبالهای که تولید می‌کند دارای بزرگترین دوره ممکن یعنی باشد. چنین دنبالهای، "دنبالهای با طول حداکثر" نامیده می‌شود. می‌توان نشان داد شیفت‌رجیستری دنبالهای با طول حداکثر را تولید می‌کند که چند جمله‌ای اتصال آن (در فصل بعد در مورد چندجمله‌ای اتصال توضیح داده شده است.) از نوع چند جمله‌ای بنیادین باشد. چند جمله ای بنیادین از هر درجه‌ای وجود دارد. شرط لازم برای اینکه یک چند جمله ای بنیادین باشد این است که تجزیه ناپذیر باشد اما این شرط کافی نیست. زمانی یک چند جمله ای با ضرایب باینری در مبنای دودوئی را تجزیه ناپذیر می‌گوییم که که نتوانیم آن را به چند جمله ای باینری با ضرایب و در جه حداقل 1 تجزیه کنیم.
1-4- معیارهای میزان تصادفی بودن یک دنباله
میزان تصادفی بودن یک دنباله به میزان غیرقابل پیش بینی بودن یک دنباله اشاره دارد. هر دنباله‌ی تصادفی تولید شده توسط فرآیندهایی که در کاربردهای عملی از آنها استفاده می‌شود به طور قطعی تصادفی نیست. در اینجا به بیان چند ویژگی از دنباله‌های تصادفی می‌پردازیم و هر دنبالهای که این ویژگی‌ها را داشته باشد تصادفی و یا به طور دقیق‌تر شبه تصادفی می‌نامیم.
معیارها و اصول ارائه شده توسط گلمب برای تصادفی بودن یک دنباله:
معیارهای گلمب برای دنباله‌هایی با دوره تناوب از فضای برداری بعدی در میدان می‌باشد اما چون زمینه‌ی کاری این پایان نامه روی دنباله‌های باینری در میدان می‌باشد. این خواص را برای دنباله‌های باینری بیان می‌کنیم.
قانون توازن: در هر دوره تناوب از این دنباله‌ها تعداد صفرها و تعداد یک‌ها تقریبا برابر است.(به طور دقیق‌تر ناهمخوانی کمتر از یک است. )
قانون اجرا: در هر دوره تناوب، نصف اجراها دارای طول یک، (منظور از طول، تعداد یک‌ها یا صفرهای پشت‌سرهم است.) یک‌چهارم آنها دارای طول دو و یک‌هشتم آنها دارای طول سه و ... می‌باشند. در کل تعداد اجراهای صفرها و اجراهای یک‌ها باهم برابر است.
خود بستگی و همبستگی متقابل: اگر و دو دنباله باینری با دوره تناوب باشند، همبستگی متقابل آنها با نماد نمایش داده و به صورت زیر تعریف می‌شود:
که می‌توان آن را به صورت ضرب داخلی دو بردار و محاسبه کرد که در آن اندیس‌ها به پیمانه‌ی محاسبه می‌شوند. اگر باشد در این صورت با این رابطه خودهمبستگی دنباله محاسبه می‌شود. در این حالت مقدار همبستگی یک دنباله با شیفت‌یافته خود آن است و بیشترین مقدار آن زمانی است که باشد و برابر است با .
حال برای یک دنباله تصادفی تابع خودهمبستگی دارای دو مقدار زیر می‌باشد:
مقدار ثابتی می‌باشد. اگر برای های فرد و برای های زوج باشد، دارای خود همبستگی دو مقداری (ایده‌آل) است و تابع خودهمبستگی برای ها به صورت زیر خلاصه می‌شود:
فصل دوم
فصل 2-
تئوری عملکرد شیفت رجیسترهای خطی با پسخورد
تئوری عملکرد شیفت‌رجیسترهای خطی با پسخورد
2-1- ترکیب و ساختار شیفت رجیسترها
شمای کلی یک شیفت رجیستر فیدبک خطی با طولL ، در شکل زیر نشان داده شده که شامل ترکیبی ازL واحد سلول یا مرحله تاخیر دهنده می‌باشد و پس از آن با استفاده از ترکیبی خطی از مقادیر این سلول ها، به عنوان ورودی به مرحله اول بازخورد داده می‌شود. بنابراین خروجی LFSR در هر لحظه، از آخرین حالت قبلی آن گرفته می‌شود. مقادیر اولیه در شیفت رجیستر در واقع همان نخستین L بیت خروجی از آن می‌باشند و بقیه‌ی بیت‌های خروجی به طور منحصر بفرد توسط رابطه‌ی بازگشتی زیر تعیین می‌شوند:
2‑1
ارقام خروجی (که در میدان آنها را بیت در نظر می‌گیریم) و ضرایب معادله‌ی بازخورد شامل می‌توانند در میدان در نظر گرفته شوند که این میدان می‌تواند میدان متناهی باشد و یا اینکه یک میدان نامتناهی مانند میدان اعداد حقیقی باشد. هیچ اجباری وجود ندارد که باشد. در این صورت تپ آخر شیفت رجیستر به عنوان فیدبک در نظر گرفته نمی‌شود.
شکل 2‑1. شمای کلی شیفت رجیستر خطی با فیدبک یا (LFSR) که دارای L-مرحله می‌باشد.
زمانی گفته می‌شود یک LFSR دنباله‌ی را تولید می‌کند، که مقدار این دنباله با اولینN بیت خروجی از LFSR به ازای یک بارگذاری اولیه، برابر باشد. چنانچه باشد، واضح استLFSR همیشه این دنباله را تولید می‌کند و اگر باشد طبق رابطه2‑1، اگر و فقط اگر رابطه زیر برقرار باشد،LFSR دنباله‌ی موردنظر را تولید می‌کند:
2‑2
قضیه‌ی ساده‌ی زیر نقشی کلیدی را در مباحث پیش رو ایفا می‌کند.
قضیه2‑1 :
اگر LFSR ای با طول L دنباله ی را تولید کند، ولی نتواند دنباله‌ی تولید کند، سپس هر LFSR ای با طولL' که بتواند دنباله ی دوم را تولید کند، لزوماً طول آن شرایط زیر را برآورده خواهد کرد:
2‑3
اثبات: برای که قضیه به طور بدیهی صحیح می‌باشد بنابراین فرض می‌کنیم است. اگر و ضرایب دوLFSR مطرح شده باشند و برخلاف رابطه (3) فرض کنیم که باشد با توجه به فرضیات قبلی خواهیم داشت:
2‑4
و
2‑5
بنابراین می‌توان نوشت:
2‑6
اینکه از رابطه‌ی 2‑5 در سمت چپ رابطه‌ی 2‑6 استفاده کرده‌ایم به این دلیل است که مجموعه زیر مجموعه‌ای از مجموعه می‌باشد. با جا به جا کردن مرتبه‌ی جمع ها و استفاده از روابط 2‑4 و 2‑5 خواهیم داشت:
2‑7
استفاده از رابطه 2‑4 این را نشان می‌دهد که مجموعه زیر مجموعه‌ای از مجموعه می‌باشد. اما رابطه2‑7، رابطه 2‑4 را رد می‌کند و ثابت می‌کند که فرضیه غیرقابل قبول است. بنابراین همان‌طور که در قضیه2‑1 مطرح شد نتیجه می‌گیریم که می‌باشد.
اگر دنباله‌ی را یک دنباله‌ی نامتناهی در نظر بگیریم که N بیت اول این دنباله به صورت باشد، چند جمله ای را چند جمله‌ای با کمترین درجه تعریف می‌کنیم که در میان تمام LFSR ها بتواند دنباله‌ی را تولید کند. با توجه به گفته‌های قبلی می‌باشد. علاوه بر این با افزایش N ، درجه‌ی چندجمله‌ای باید به طور یکنواختی غیرکاهشی باشد. به تعبیر ساده‌تر می‌توان گفت که تمام دنباله‌های تمام صفر توسط LFSR ای با طول تولید می‌شوند، بنابراین است اگر و فقط اگر دنباله‌ی تماماً صفر باشد.
لم1:
اگر LFSR ای با طول دنباله‌ی را تولید کند اما نتواند دنباله‌ی تولید کند، خواهیم داشت:
اثبات: از غیر نزولی بودن داریم . قضیه 1 نیز تاکید می‌کند که پس با توجه با این دو رابطه، لم همیشه برقرار است.
فهرست پایان نامه تشخیص کور پارامترهای اسکرمبلرهای مبتنی بر LFSR، در داده‌های دیجیتالی
فهرست:
عنوان صفحه
فصل 1- مقدمه.. 2
1-1- اسکرمبلر چیست و چرا از آن استفاده می کنیم؟ 2
1-2- مزایای استفاده از اسکرمبلینگ قبل از ارسال داده 3
1-3- دنباله‌های شبه تصادفی.. 4
1-4- معیارهای میزان تصادفی بودن یک دنباله. 5
فصل 2- تئوری عملکرد شیفت‌رجیسترهای خطی با پسخورد. 8
2-1- ترکیب و ساختار شیفت رجیسترها 8
2-2- سنتز الگوریتم LFSR. 11
2-3- نمایش کلاسیک دنباله های LFSR. 18
2-4- شبیه‌سازی و نتایج مربوط به اجرای الگوریتم برلکمپ-مسی بر روی دنباله خروجی LFSR. 21
فصل 3- شناسایی پارامترهای اسکرمبلرهای خطی... 25
3-1- تشخیص پارامترهای اسکرمبلر با استفاده از دنباله متن ورودی x(t) 28
3-2- تشخیص پارامترهای اسکرمبلرجمعی فقط با استفاده از بایاس متن ورودی.. 29
3-3- تشخیص پارامترهای اسکرمبلرضربی فقط با استفاده از بایاس متن ورودی.. 39
3-4- الگوریتم کلوزیو اصلاح شده 42
3-5- نتایج شبیه‌سازی الگوریتم کلوزیو روی اسکرمبلرهای ضربی و جمعی.. 50
فصل 4- شناسایی پارامترهای اسکرمبلر در حضور نویز کانال.. 54
4-1- تشخیص اسکرمبلر زمانی‌که نویز به صورت بیت‌های تغییریافته باشد. 54
4-2- شناسایی اسکرمبلر زمانی‌که درج بیت به صورت نویز در دنباله رخ دهد. 59
3-3- نتایج شبیه‌سازی شناسایی چندجمله‌ای اسکرمبلرها در حضور نویز کانال.. 65
فصل 5- شناسایی پارامترهای اسکرمبلر با استفاده از کلمه دوگان انکدر کانال.. 68
5-1- محاسبه بایاس بعد از کدینگ کانال.. 69
5-2- بازسازی چندجمله‌ای فیدبک اسکرمبلر بعد از عبور از کدینگ کانال.. 71
5-3- نتایج مربوط به شناسایی اسکرمبلر قرار گرفته پس از انکدر بلوکی.. 79
نتیجه‌گیری.......................................................................................................................89
منابع....................................................................................................................................91
چکیده و عنوان انگلیسی................................................................................................93
منبع:
[1] F. G. Gustavson, "Analysis of the Berlekamp-Massey linear feedback shift-register synthesis algorithm," IBM Journal of Research and Development, vol. 20, pp. 204-212, 1976.
[2] J. L. Massey, "Shift-register synthesis and BCH decoding," IEEE Transactions on Information Theory, vol. 15, pp. 122-127, 1969.
[3] E. R. Berlekamp, Nonbinary BCH decoding: University of North Carolina. Department of Statistics, 1966.
[4] E. Filiol, "Reconstruction of punctured convolutional encoders," in International Symposium on Information Theory and its Applications (ISITA’00), 2000.
[5] A. Valembois, "Detection and recognition of a binary linear code," Discrete Applied Mathematics, vol. 111, pp. 199-218, 2001.
[6] M. Cluzeau, "Reconstruction of a linear scrambler," Computers, IEEE Transactions on, vol. 56, pp. 1283-1291, 2007.
[7] R. Lidl and G. L. Mullen, "When does a polynomial over a finite field permute the elements of the field?," American Mathematical Monthly, pp. 243-246, 1988.
[8] A. Canteaut and E. Filiol, "Ciphertext only reconstruction of stream ciphers based on combination generators," in Fast Software Encryption, 2001, pp. 165-180.
[9] X.-B. Liu, S. N. Koh, C.-C. Chui, and X.-W. Wu, "A study on reconstruction of linear scrambler using dual words of channel encoder," Information Forensics and Security, IEEE Transactions on, vol. 8, pp. 542-552, 2013.
[10] X.-B. Liu, S. N. Koh, X.-W. Wu, and C.-C. Chui, "Reconstructing a linear scrambler with improved detection capability and in the presence of noise," Information Forensics and Security, IEEE Transactions on, vol. 7, pp. 208-218, 2012.
[11] B. Sklar, Digital communications vol. 2: Prentice Hall NJ, 2001.
[12] X.-W. Wu, S. N. Koh, and C.-C. Chui, "Primitive polynomials for robust scramblers and stream ciphers against reverse engineering," in Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, 2010, pp. 2473-2477.
[13] K. Umebayashi, S. Ishii, and R. Kohno, "Blind adaptive estimation of modulation scheme for software defined radio," in Personal, Indoor and Mobile Radio Communications, 2000. PIMRC 2000. The 11th IEEE International Symposium on, 2000, pp. 43-47.
[14] H. Ishii, S. Kawamura, T. Suzuki, M. Kuroda, H. Hosoya, and H. Fujishima, "An adaptive receiver based on software defined radio techniques," in Personal, Indoor and Mobile Radio Communications, 2001 12th IEEE International Symposium on, 2001, pp. G-120-G-124 vol. 2.
[15] E. Filiol, "Decimation attack of stream ciphers," in Progress in Cryptology—INDOCRYPT 2000, ed: Springer, 2000, pp. 31-42.
[16] M. Cote and N. Sendrier, "Reconstruction of convolutional codes from noisy observation," in Proceedings of the 2009 IEEE international conference on Symposium on Information Theory-Volume 1, 2009, pp. 546-550.
[17] W. Meier and O. Staffelbach, "Fast correlation attacks on stream ciphers," in Advances in Cryptology—EUROCRYPT’88, 1988, pp. 301-314.
[18] R. Gautier, G. Burel, J. Letessier, and O. Berder, “Blind estimation
of scrambler offset using encoder redundancy,” in Proc. Thirty-Sixth
Asilomar Conf. Signals, Systems and Computers, Pacific Grove, CA,
Nov. 3–6, 2002, vol. 1, pp. 626–630.
[19] E. Filiol, “Reconstruction of convolutional encoder over ,” in
Proc. Sixth IMA Conf. Cryptography and Coding, 1997, Lecture Notes
in Computer Science, no. 1355, pp. 100–110, Springer Verlag..
[20] E. Filiol, “Reconstruction of punctured convolutional encoders,”
in Proc. IEEE Int. Symp. Information Theory and Applications
(ISITA’00), 2000, pp. 4–7, SITA and IEICE Publishing..
[21] J. Barbier, “Reconstruction of turbo-code encoders,” in Proc. SPIE Defense and Security Symp., Space Communications Technologies Conf.,
Mar. 28–31, 2005, vol. 5819, pp. 463–473.
[22] J. Barbier, G. Sicot, and S. Houcke, “Algebraic approach fo reconstruction of linear and convolutional error correcting codes,” Int. J Appl. Math. Comput. Sci., vol. 3, no. 3, pp. 113–118, 2006.