روشی ساده و سریع برای رمزنگاری LFSR

در این مقاله قصد داریم شما را با روش رمزنگاری دنباله ای (Stream Cipher) براساس LFSR آشنا کنیم و مزایا و معایب آن را بیان کنیم و همچنین روش‌هایی برای بهبود این روش و افزایش امنیت آن بیان کنیم‌. هدف این نوشته افزایش اطلاعات شما درباره رمزنگاری دنباله‌ای و به طور خاص LFSR و روش‌های بهبود آن است‌.

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

رمزنگاری از دیرباز به عنوان یک ضرورت برای حفاظت از اطلاعات خصوصی در مقابل دسترسی - های غیرمجاز در تجارت و سیاست و مسائل نظامی وجود داشته است به طور مثال تلاش برای ارسال یك پیام سری بین دو هم پیمان به گونه ای كه حتی اگر توسط دشمن دریافت شود قابل درك نباشد، در رم قدیم نیز دیده شده است(رمز سزار).در سالیان اخیر رمزنگاری و تحلیل رمز از یک هنر پا را فراتر گذاشته و یک علم مستقل شده است و در واقع به عنوان یک وسیله عملی برای ارسال اطلاعات محرمانه روی كانا ل های غیر امن مانند تلفن ، ماکروویو و ماهواره ها شناخته می شود.

پیشرفت علم رمزنگاری موجب به وجود آمدن روشهای تحلیل مختلفی شده است به گونه ای كه به طور متناوب سیستم های رمز مختلف شكسته شده اند . معروف ترین نمونه این نوع سیستمها ماشین «انیگما » بوده است . انیگما ماشین رمز گذار و كد گذار وكد كننده ای بوده است كه حزب نازی در زمان جنگ جهانی دوم برای ارسال پیام ها یشان از طریق رادیو به سایر نقاط استفاده می کردند .

رمزنگاری كه به طور عمده به دو بخش رمزنگاری متقارن یا رمزنگاری با کلید خصوصی و رمزنگاری نامتقارن یا رمزنگاری با کلید عمومی صورت می گیرد، تلاش میکند برای ایجاد یک ارتباط سرّی از طریق سیستمهای مخابراتی و شبكه های كامپیوتری مباحث مربوط به محرمانگی و احراز هویت، را تحت فرض های مشخص به درستی اثبات نماید .

رمز دنباله ای یکی از روش های رمزنگاری متقارن است که یک قسمت مهم در رمزنگاری محسوب می شود. به این صورت عمل می کند که تک به تک مولفه های متن اصلی که معمولا اعداد باینری هستند را مورد بررسی قرار می دهد و آنها را رمز می کند . از آن جهت که به صورت تکی مولفه را بررسی می کند دارای سخت افزار و مدار ساده ای نسبت به رمز قالبی(Block Cipher) است که مولفه ها را به صورت گروهی و همزمان باهم رمز می کند . همچنین استفاده از رمز دنباله ای زمانی مناسب و لازم می شود که بافر ما محدود است و یا لازم است مولفه ها به صورت تک تک پردازش و دریافت شوند . همچنین به دلیل اینکه این روش دارای خطای محدود یا بدون خطا در زمینه انتشار است برای مواقعی که احتمال خطای انتقال ما بالاست بسیار مناسب و سودمند است . یکی از روش های پیاده سازی رمز دنباله ای استفاده از ثبات تغییر بازخورد خطی یا Linear feedback shift register یا به اختصار( LFSR) ها است . LFSR شیفت‌رجیستری n-بیتی است که ترکیب خطی برخی از بیت‌های آن، به عنوان ورودی، به آن بازگردانده می‌شود به بیانی ساده تر با اعمال ترکیب های خطی مانند XOR بر روی همه یا برخی از بیت ها ، بیت جدیدی به دست می آورد و آن را به عنوان ورودی به چرخه اعداد بازمی گرداند . برای پیاده سازی LFSR و تولید ترکیب خطی از روش های مختلفی مانند فیبوناچی ، گالوا و … می توان استفاده کرد . از ویژگی های این روش می توان به تولید دنباله هایی با دوره تناوب بزرگ و خاصیت آماری خوب اشاره کرد که به راحتی با استفاده از تکنیک های جبری مورد تجزیه و تحلیل قرار می گیرند . ولی این روش علاوه بر مزیت هایی که دارد دارای معایبی نیز است و یکی از آنها این است که خروجی این الگوریتم نیز مانند ورودی آن دارای پیچیدگی خطی است که این باعث می شود خروجی به راحتی قابل تشخیص و پیش بینی باشد .که این مسئله امنیت داده ها را به خطر می اندازد . از آنجا که یک سیستم با طراحی مناسب باید در برابر حملات شناخته شده متن مطمئن باشد ، LFSR هرگز نباید به عنوان یک تولید کننده کلید اصلی مورد استفاده قرار گیرد. با این وجود ، LFSR به دلیل هزینه های اجرای بسیار پایین مطلوب است. سه روش کلی برای از بین بردن خواص خطی LFSR ها و استفاده مطمئن از آن در این بخش مورد بحث قرار گرفته است:

(الف)استفاده از یک تابع ترکیب غیرخطی در خروجی (استفاده از چندین LFSR).

(ب) استفاده از یک تابع فیلتر غیرخطی بر روی محتویات یک LFSR واحد

(پ) استفاده از خروجی یک (یا چند) LFSR برای کنترل کلاک LFSR های دیگر

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

رمزهای دنباله ای

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

۱) دوره تناوب رشته كلید تولید شده باید به حد کافی بزرگ باشد تا با طول پیام ارسال شده سازگاری داشته باشد .

۲) دنباله بیت خروجی حاصله از مولد باید به راحتی قابل تولید کردن باشد .

۳) بیتهای خروجی باید به سختی قابل پیش بینی باشند .

در واقع با در اختیار داشتن مولد و اولین n بیت خروجی a(۰) ، a(۱) …… . a(n-) از لحاظ محاسباتی پیش بینی بیت n+۱ ام یعنی a(n+1) در دنباله با احتمال بیشتر از ½ باید غیر ممکن باشد.

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

ثبات های انتقال بازخورد خطی (LFSR)

این ثبات ها مدت ها برای كدهای كنترل خطا ، آزمایشهای VLSI و مخابرات طیف گسترده مورد استفاده بوده اند و از جمله مهمترین اجزاء در ساختار مولدهای شبه تصادفی می باشند آنها توابع بازگشتی به شكل زیر دارند .

a(t) =c۱ a(t-۱) Å c۲ a(t-۲) Å …………. Å c(n-۱) a(t-n-۱) Å a(t-n)

c i Î [۰,۱]

و با چند جمله ای بازگشتی زیر نشان داده میشوند .

f(n) = ۱+ c۱x + c۲x۲ + ……..+ c( n-۱) x ( n-۱) + x(n)

به طور کلی برای اینکه حداكثر دوره تناوب ممكن ۲n-۱ را برای دنباله خروجی از یك LFSR داشته باشیم ، چند جمله ای بازگشتی آن می باید اولیه باشد . تعداد چند جمله ای های اولیه درجه n از رابطه f (۲ n –۱)/n بدست می آید كه (n) f نمایانگر تابع اویلر می باشد كه تعداد اعداد صحیح مثبت و اول كوچكتر از عدد n را نشان میدهد .

کاربردهای رمزهای دنباله ای ،مزایا و معایب

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

در عین حال که برای رمز نمودن حجم عظیمی از داده ها بعلت سرعت اجرای بالا، رمزهای دنباله ای می توانند گزینه مناسبی باشند . همانطور كه در سیستم های امنیت مخابراتی و رمزنگاری نظیر BEU ها دیده می شود .

تحلیل و آنالیز نمودن رمزهای دنباله ای نیز معمولاً ساده تر از رمزهای قطعه ای صورت می گیرد . در عین حال امكان طرح حملات وابستگی بر روی اینگونه سیستم ها كه بر مبنای ثبات های انتقال خطی عمل می نمایند ، بیشتر است اغلیب رمزنگارها سعی می نمایند اجزاء مختلف اینگونه الگوریتم ها را در حالتی غیرخطی تركیب نمایند و یا از ثبات های انتقال غیرخطی استفاده نمایند تا مصونیت وابستگی لازم پدید آید .

نمونه های رمزهای دنباله ای پیاده سازی شده

رمزهای دنباله ای بسیاری در طرح های مختلف پیاده سازی شده اند .A۵ یک الگوریتم رمز دنباله ای است که برای رمز نمودن سیستم ارتباط گروهی موبایل و یا در واقع سیستم مخابراتی GSM به كار می رود . این الگوریتم برای رمز نمودن لینک ارتباطی میان گوشی تلفن به ایستگاه پایه به كار می رود .

الگوریتم XPD/KPD كه توسط شركت هیوز طراحی شده است ، در رادیوهای تاكتیكی نظامی ارتش و تجهیزات جهت یاب به كار رفته است .

الگوریتم رمز دنباله ای NaNoTEQ كه نام يك شركت الكترونيكي در آمریکای جنوبی است برای رمز نمودن ارتباطات و مراسلات از طريق فاكس در اداره پلیس آمریکای جنوبی بكار رفته است .

می توان انواع دیگر رمزهای دنباله ای طرح شده را بیان نمود ، اما آنچه مشخص است اینگونه رمزها در تجهیزات مخابراتی و سخت افزاری كاربرد گسترده و فراوان دارند . به خصوص در خطوط رادیوئی كه امكان اغتشاشات و نویزهای فراوان در آنها موجود می باشد . اما به علت سرعت نامناسب اجرای نرم افزاری آنها ، برای استفاده در شبكه های كامپیوتری و یا ایجاد امنیت در پروتکل های امنیت اینترنت بکار نمی روند .

روش های تبدیل خروجی خطی LFSR به خروجی غیر خطی

• استفاده از یک تابع ترکیب غیرخطی در خروجی

یک روش کلی برای از بین بردن خطی ذاتی در LFSR ها ، استفاده از چندین LFSR به صورت موازی است. کلید اصلی به خروجی تابع غیر خطی f است . همانطور که در شکل زیر مشاهده می کنید تابع f یک ترکیب غیر خطی ایجاد می کند.

• استفاده از یک تابع فیلتر غیرخطی بر روی محتویات یک LFSR واحد

یکی دیگر از تکنیک های کلی برای از بین بردن خطی ذاتی در LFSR ها ، تولید کلید از از مراحل مختلف یک تابع غیر خطی در یک LFSR است. این ساختار در شکل زیر نشان داده شده است. چنین مولدهای کلید به عنوان مولدهای فیلتر غیرخطی نامیده می شوند و f به عنوان تابع فیلتر نامیده می شود.

• استفاده از خروجی یک (یا چند) LFSR برای کنترل کلاک LFSR های دیگر

در این روش خروجی LFSR ها به صورت مرتب و براساس پالس یا کلاک کنترل می شود و کار می کند. برای کنترل این پالس از دو روش می توان استفاده کرد . الف- مولد مرحله متناوب (the alternating step generator ) و ب- مولد در حال کاهش (the shrinking generator)

الف- مولد مرحله متناوب

مولد مرحله متناوب از خروجی LFSR R1 برای کنترل دو LFSR دیگر یعنی R2,R3 استفاده می کند. کلید اصلی تولید شده، XOR خروجی R2 و R3 است.

همانطور که در شکل زیر مشاهده می کنید ابتدا پالس مربوط به R1 ثبت می شود . سپس با توجه به خروجی R1 تصمیم گرفته می شود که مقدار بعدی توسط R2 ویا R3 تعیین شود . اگر خروجی R1 مقدار 1 بود R2 اجرا می شود و اگر خروجی 0 بود R3 اجرا می شود . این کار تا زمانی ادامه می یابد که مقادیر کلید اصلی ما به طور کامل مشخص شوند و به تعداد دلخواه ما برسند.

ب ) مولد کاهشی

از خروجی LESR R1 استفاده می کند و با توجه به ان خروجی R2 را کنترل و تعیین می کند . همانطور که در شکل مشاهده می کنید به این صورت عمل می کند که ابتدا در یک پالس (کلاک)خروجی هر دو LFSR محاسبه می شود . اگر خروجی R1 مقدار 1 بود ، خروجی R2 به عنوان بخشی از کلید اصلی انتخاب می شود اما اگر خروجی R1 مقدار 0 بود خروجی R2 دور انداخته می شود و این کار را تا زمانی که به مقدار دلخواه از کلید اصلی برسیم ادامه می دهد.

نتیجه گیری

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

اگر علاقه مند هستید که با پیاده سازی نرم افزاری LFSR ها و مزایا و معایب آن بیشتر آشنا شوید می توانید این مقاله را مشاهده کنید .

منابع :

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

در آخر تشکر می کنم از اینکه با ما در این مقاله همراه بودید .خوشحال می شویم که نظرات و انتقادات و پیشنهاداتتان را با ما به اشتراک بگذارید.