رمز دنباله ای چیست و روش FSR در این رمزنگاری چگونه عمل می کند؟

مقدمه :

رمز دنباله ای به دلیل سادگی و سرعت یکی از روش های مهم رمزنگاری است. رمزهای دنباله ای کاراکتر های یک متن (معمولا اعداد باینری) را در لحظه، با استفاده از یک الگوریتم رمزگذاری با یک دنباله از ارقام رمزنگاری شده شبه تصادفی (Keystream)، رمزنگاری می کند. هدف آن تولید یک دنباله از کلیدها است که برای رمزگذاری دنباله یا stream دیگری استفاده می شود. در مقابل رمز بلوکی (Block Cipher) گروهی از کاراکتر ها را به صورت همزمان با استفاده از یک کلید ثابت (رمز تغییر) رمزنگاری می کند.رمزهای دنباله ای به طور کلی سریع تر از رمز بلوکی در سخت افزار هستند و پیچیدگی کمتری در مدار سخت افزار دارد.آنها حتی بهتر هستند و در بعضی مواقع استفاده از آنها اجباری تلقی می شود،مانند زمانی که ظرفیت ذخیره بافر محدود است یا زمانی که کاراکتر ها باید به صورت تکی و مجزا، زمانی که دریافت می شوند پردازش شوند.به دلیل این که رمزهای دنباله ای محدود هستند و یا هیچ خطایی در انتقال آنها رخ نمی دهد، می توانند در شرایطی که خطای ارسال و انتقال خیلی محتمل است، سودمند باشند.

دانش تئوری وسیعی درباره ی رمز های دنباله ای وجود دارد و قواعد طراحی های متنوعی برای آنها ارائه شده و به طور گسسته ، بررسی و آنالیز شده است. هرچند تعداد کمی از الگوریتم های رمز دنباله ای یا Stream cipher به طور کاملا تخصصی در مقالات باز موجود است. این سطح تاسف بار از امور را می توان با این حقیقت توضیح داد که بیشتر رمزهای دنباله ای که در عمل استفاده می شوند، اختصاصی و محرمانه بودنشان ترجیح داده می شود. در مقابل تعداد زیادی از ارائه های واقعی رمز بلوکی نشر داده شده اند، بعضی از آنها استاندارد سازی شده و در اختیار عموم قرار گرفته اند. با این اوصاف به دلیل سود و مزایای چشمگیر آنها، رمز دنباله ای یا Stream Cipher به طور وسیعی این روزها مورد استفاده قرار می گیرند و چیزی است که در سالهای آینده به شکل واقعی تر، پروپوزال هایی راجع به آنها انتظار می رود.

One-Time-Pad

در این روش به ازای هر حرف از متن اصلی یک کد مبنای 2 نسبت می دهیم. برای مثال اگر پیام 8 حرفی باشد کد ما با 3 بیت کامل می شود.این کد (بر اساس ویژگی های رمزنگاری ) نباید محرمانه باشد. برای رمز گذاری متن بدست آمده به کلید نیاز داریم که طول آن دقیقا به اندازه ی طول پیام باشد. این کلید باید به طور تصادفی انتخاب شود.

در شیوه‌ی رمزنگاری One Time Pad برای تولید متن رمزگذاری شده یا Ciphertext متن ساده (Plain Text) را با کلید رمزنگاری XOR می‌کنیم.

یکی از ویژگی‌های عملیات XOR این است که:

a XOR b XOR b = a

به همین دلیل اگر متن رمزگذاری شده (Ciphertext) با کلید رمزنگاری XOR شود حاصل عملیات متن ساده (Plain Text) خواهد بود. به این ترتیب شیوه‌ی رمزگذاری (Encryption) و رمزگشایی (Decryption) دقیقا مشابه هم است.

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

چرا کلید رمزنگاری One Time Pad یک بار مصرف است؟

فرض کنید دو پیام P1 و P2 هر دو با کلید K رمزگذاری شده باشند.

C1 = P1 XOR K

C2 = P2 XOR K

C1 XOR C2 = P1 XOR K XOR P2 XOR K = P1 XOR P2

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

بنا بر این ، چرا رمزنگاری One Time Pad برای کاربردهای امروز قابل استفاده نیست؟ دیدیم که لازم است کلید رمزنگاری در شیوه‌ی رمزنگاری One Time Pad هربار تغییر کند و همچنین طول این کلید باید به اندازه‌ی پیام اصلی باشد. انتخاب کلیدی با این طول در کاربردهای امروزی که با داده‌های بسیار بزرگ سروکار داریم عملا بسیار چالش برانگیز است و انتقال کلیدی به این بزرگی آن هم برای هر پیام به صورت ایمن در عمل شدنی نیست. بنابراین این روش رمزنگاری اگرچه ایمنی بسیار مطلوبی را ارائه می‌کند اما در بیشتر کاربردهای امروزی قابل استفاده نیست. اما دانستن آن به درک شیوه‌های رمزنگاری امروزی که مورد استفاده قرار می‌گیرند کمک می‌کند.اشکالی که در روش one time pad وجود داشت این بود که طول کلید رمزنگاری باید با طول پیام برابر می‌بود و به همین دلیل استفاده از آن در کاربردهای امروزی عملا ممکن نبود. با ابداع الگوریتم‌های رمزنگاری Stream Cipher به جای استفاده از یک کلید رمزنگاری که به اندازه‌ی طول پیام باشد، از یک تابع استفاده می‌شود که وظیفه‌ی آن این است که با استفاده از کلیدی که طول کوتاه‌تری دارد، یک کلید رمزنگاری با طولی به اندازه‌ی طول پیام ایجاد کند. به این ترتیب امنیت قابل اثبات در شیوه‌ی One Time Pad که در بخش قبل به آن اشاره شد در این روش‌ها به دلیل استفاده از کلیدی با طول کوتاه‌تر وجود ندارد.

تاریخچه stream cipher

مفهوم Keystream را می توان به عنوان مجموعه ای منحصر به فرد از بیت ها دانست که باید به اندازه متن اصلی باشد. با این حال ، توزیع مداوم توالی داده های طولانی مدت برای دنباله کلید ها غیر قابل انکار و نامطلوب است. با افزایش انتقال های متنی بزرگ الکترونیکی در قرن بیستم ، نیاز به جایگزین سازی افزایش یافت. در پاسخ به این نیاز، تکنیک های رمز گذاری متعدد stream cipher معرفی شدند.برای مثال در سال 1930 ، از رمز دنباله ای یا stream cipher به صورت رسمی در ماشین های روتر یا rotor machines که بیشتر به صورت مکانیکی عمل می کرد، استفاده می شد. مثال شناخته شده از rotor machine ها ، Enigma است .

چند سال بعد، معرفی شبکه های کامپیوتری در مقیاس بزرگ، تقاضای رمز دنباله ای بر پایه ی نرم افزار و سخت افزار که ارتباطات خودکار را پشتیبانی کند افزایش یافت.

یکی از پرطرفدار ترین تکنیک ها در دهه 60 و 70 میلادی، رمز دنباله ای ترتیبی دودویی غیر خطی (nonlinear binary sequence stream cipher ) بود که یک دنباله کلید باینری یا دودویی تولید می کرد که رمزگذاری One-Time-Pad می توانست با استفاده از آن، بدون نیاز به کلید امنیتی طولانی و خیلی بزرگ، رمزنگاری کند. تصویر زیر یک سیستم رمزنگاری عادی بر پایه ی nonlinear stream cipher را نمایش می دهد.این نوع از رمزها به دلیل footprint سخت افزار کوچک آنها مورد استقبال قرار گرفته بود.

تصویر بالا یک rotating shift register (ثبات جابجایی چرخشی) را نشان می دهد که حالت داخلی رمز را نمایش می دهد. بعد از محاسبه ی بیت دنباله ی کلید ها، تابع successor یا جانشی حالت یا وضعیت داخلی را با استفاده از تابع خطی برای حفظ همان مقدار آنتروپی در رمز به روز رسانی می کند.سپس، جزء خروجی یک تابع فیلتر غیرخطی (f0) برای محاسبه ی بیت بعدی دنباله ی کلید اعمال می کند.بیت های دنباله ی کلید توسط فرستنده استفاده می شود تا رمزنگاری متن اصلی را با ترکیب هر دو رشته بیت با عملگر XOR انجام دهد. نتیجه ی متن رمزنگاری شده از طریق کانال های ناامن انتقال می یابد.گیرنده، همان عملیات را دقیقا انجام می دهد و تابع XOR دیگری را این بار روی ترکیب بیت های متن رمزنگاری شده با بیت های دنباله کلید اعمال می کند.دنباله کلید هایی که در متن رمزنگاری شده جا گرفته بودند، خارج می شوند و متن اصلی در اختیار گیرنده قرار می گیرند.

معرفی Stream Cipher

در رمزنگاری stream cipher یا رمز دنباله ای یک رمز کلید متقارن است که بیت های متن اصلی با یک دنباله ای از بیت های رمز شبه تصادفی با استفاده از عملگر XOR ترکیب می شود.

در این روش، ارقام متن اصلی در لحظه رمزنگاری می شوند و انتقال ارقام جانشین در طی حالات رمزنگاری تغییر می کند.از آنجایی که رمزنگاری هر رقم به حالت فعلی بستگی دارد، نام دیگر این روش رمز حالت (state cipher) است. در عمل، ارقام به طور معمول، تک بیت ها یا بایت ها هستند.

رمز دنباله ای یا stream cipher یک دیدگاه متفاوت به رمزنگاری متقارن از رمز بلوکی یا block cipher است.رمز بلوکی ها روی بلوک های بزرگی از طول ثابت عمل می کنند. رمزهای دنباله ای به طور معمول با سرعتی بالاتر از رمزهای بلوک اجرا می شوند و نیاز سخت افزاری کمتری دارند.

رمزهای دنباله ای می توانند کلید متقارن ( symmetric-key ) یا کلید عمومی (Public key) باشند. تمرکز این بخش روی کلید متقارن رمزهای دنباله ای می باشد. طرح رمزنگاری کلید عمومی احتمالی Blum-Goldwasser می تواند نمونه ای کلید عمومی رمز دنباله ای باشد.

در بسیاری از سیستم های رمزنگاری مهم است که چند پیام رمز شده را در یک session به هم لینک شوند. به این مهم ، زنجیره ای از رمز ها گفته می شود. رمزهای دنباله ای ذاتاََ این ویژگی را از زمانی که متن رمزگذاری شده به طور افزایشی تولید می شود، ارائه می کنند.

رمزگذاری جریان از کلید رمزنگاری بسیار کوچکتر و راحت تری استفاده می کند ، به عنوان مثال کلیدهای 128 بیتی. براساس این کلید ، یک جریان اصلی شبه تصادفی ایجاد می کند که می تواند با ارقام ساده در یک روش مشابه با الگوریتم رمزگذاری پد یکبار ترکیب شود.

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

رمز های بلوکی، متن اولیه را در بلوکها تقریبا بزرگ (بزرگتر مساوی 64 بیت) پردازش می کنند. این تابع برای رمزنگاری بلوک های پی در پی استفاده می شود. رمزهای بلوکی بدون حافظه یا memoryless هستند. در مقابل، رمزهای دنباله ای متن اصلی را در بلوک های کوچک به اندازه ی تک بیت پردازش می کنند و امکان دارد تابع رمزنگاری به ازای متن اصلی که پردازش می شود، تغییر یابد.بنابراین رمز دنباله ای نیازمند حافظه است. آنها در مواقعی رمز حالت (State Cipher) نامیده می شوند، به این دلیل که رمزنگاری نه تنها به کلید و متن اصلی، بلکه به حالت فعلی هم بستگی دارد.

این تفاوت بین رمزهای بلوکی و دنباله ای خیلی قطعی نیست. اضافه کردن مقدار کمی از حافظه به رمز بلوکی، رمز دنباله ای با بلوک های بزرگتر را نتیجه می دهد.

دسته بندی stream cipher

• رمز دنباله ای همزمان (synchronous stream cipher)

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

ویژگی های رمز دنباله ای همزمان

• نیازمند همزمانی است. فرستنده و گیرنده باید هماهنگ باشند و از یک کلید استفاده کنند و در یک حالت عمل کنند.اگر هماهنگی به دلیل اضافه یا حذف شدن اعداد متن رمزنگاری شده در حال انتقال، بهم بریزد، رمزنگاری اشتباه می شود و فقط می توانند با تکنیک های دوباره هماهنگ سازی، متن را بازگردانند.
• خطای انتقال ندارد.عدد متن رمزگذاری شده ای که حین انتقال تغییر داده شده باشد ( حذف نشده باشد)، اعداد دیگر متن رمزگذاری شده را تحت تاثیر قرار نمی دهد.
• حمله های فعال . بنا به ویژگی اول، اضافه کردن یا حذف یا دوباره پخش کردن اعداد متن رمزگذاری شده به وسیله ی یک دشمن یا هکر فعال، باعث از دست رفتن سریع هماهنگی می شود وبنابراین ممکن است توسط کسی که رمزگشایی می کند قابل تشخیص باشد. بنا به ویژگی دوم، هکر می تواند با تغییر اعداد متن رمزنگاری شده، تشخیص دهد که این تغییرات چه اثراتی روی متن اصلی داشته است.
• رمزهای دنباله ای خود -همزمانی (Self-synchronizing stream ciphers)

در این روش دنباله ی کلید، به کلید مخفی طرح و یک عدد ثابت(مثل t ) از اعداد متن رمزگذاری شده بستگی دارد. یک مثال ساده از رمز دنباله ای خود-همزمانی، یک رمز بلوکی از cipher-feedback mode یا CFB می باشد.

نمودار زیر یک CFB را نمایش می دهد .

برای مثال، در سیستم نشان داده شده در نمودار، سایز یک بلوک پیام s بیت است که n > s > 1

حالت CFB نیازمند یک وکتور اولیه (Initial vector یا به اختصار IV) به عنوان n بیت بلوک رندوم ورودی است . IV نیازی به امن و مخفی ماندن ندارد. قدم های عملیات به شرح زیر است :

• بارگیری مقدار IV را در ثبات یا register بالایی
• رمزنگاری ارزش داده در register بالایی با رمز بلوکی با کلید k
• برداشت فقط s تعداد از مهمترین بیت ها (بیت های سمت چپ) از خروجی پروسه ی رمزنگاری و XOR آنها با s بیت بلوک پیام متن اصلی، برای تولید بلوک متن رمزنگاری شده
• وارد کردن متن رمزگذاری شده داخل register بالایی با جابجا کردن داده های حاضر به سمت چپ و ادامه ی عملیات تا زمانی که تمام بلوک های متن اصلی، پردازش شده باشند
• اساساََ، بلوک متن رمزنگاری شده قبلی با کلید رمزنگاری شده و نتیجه با بلوک متن اصلی فعلی XOR شده
• قدم های مشابه برای رمزگشایی دنبال می شوند. IV قبل از تصمیم گیری، در ابتدا در شروع رمزگشایی بارگیری می شود.

ظاهرا ، حالت CFB در حال تبدیل رمز بلوک به نوعی رمز دنباله ای است. الگوریتم رمزگذاری به عنوان یک مولد دنباله کلید برای تولید دنباله کلید استفاده می شود که در register پایین قرار می گیرد. سپس این دنباله کلید با متن ساده مانند رمز دنباله ای XOR شده است.

ویژگی های رمزهای دنباله ای خود-همزمانی

• نیازمند خود-همزمانی است. خود همگام سازی یا خود همزمانی، زمانی اتفاق می افتد که اعداد رمزگذاری شده اضافه یا حذف شده باشند، به این دلیل که mapping در رمزگشایی فقط به یک عدد ثابت از کاراکتر رمزنگاری شده ی پیش واگذاری شده نیاز دارد.چنین رمزنگاری ها می توانند پس از از بین رفتن همگام سازی ، دوباره رمزنگاری مناسب را به طور خودکار برقرار کنند ، و فقط تعداد مشخصی از کاراکترهای متن ساده غیر قابل بازگشت هستند.
• خطای انتقال محدود . فرض کنید که وضعیت یک دنباله همزمان هماهنگ سازی به t رقم های متن رمزنگاری قبلی بستگی دارد. اگر یک رقم متن رمزنگاری هنگام انتقال تغییر یافته باشد (یا حتی حذف یا درج شود) ، ممکن است رمزگشایی حداکثر تا به رقم رمزگذاری بعدی نادرست باشد ، پس از آن رمزگشایی صحیح از سر گرفته می شود.
• حمله های فعال . بر اساس ویژگی 2 ، این بدان معنی است که هرگونه تغییر در ارقام رمزنگاری توسط دشمن فعال باعث می شود که چندین رقم رمزنگاری دیگر به اشتباه نادرست رمزگشایی شوند ، در نتیجه احتمال شناسایی توسط هکر بهبود می یابد (در مقایسه با رمزهای دنباله ای همزمان) .در نتیجه خاصیت اول ، تشخیص درج ، حذف یا پخش مجدد رقم های متن کدگذاری شده توسط یک هکر فعال ، دشوارتر است.
• انتشار آمار متن اصلی. از آنجایی که هر عدد متن اصلی بر تمام متن کدگذاری شده پیش رو تاثیر می گذارد، خصوصیات آماری متن اصلی از طریق متن کدگذاری شده انتشار می یابد.از این رورمزهای دنباله ای خود-همزمانی، می توانند نسبت به رمزهای دنباله همزمان در برابر حملات بر اساس افزونگی متن اصلی مقاوم باشند.

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

نتیجه گیری و چالش های پیش‌رو

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

به دلیل اینکه جریان اصلی شبه تصادفی است و واقعاً تصادفی نیست ، نمی توان امنیت مرتبط با One-Pad-Time را به کار برد و کاملاً امکان پذیر است که رمزنگار جریان کاملاً ناامن باشد.

بر خلاف مزایای روش های stream cipher (سرعت و انعطاف پذیری) ، این روش جدیداََ ، به ندرت در سیستم های امن که امنیت سفت و سختی را ارائه می دهند استفاده می شود.در حالت عادی،هدف حمله رمزهای دنباله ای این است که متن اصلی را از بیت های رمزنگاری جدا کنند.

Feedback Shift Register یا به اختصار FSR

معرفی

رجیسترهای تغییر بازخورد یا Feedback Shift Registers ، به خصوص Linear Feedback Shift Registers اجزاء پایه ای خیلی از تولید کننده های دنباله کلید ها(Keystream generator) هستند.

Linear Feedback Shift Register یا به اختصار LFSR

LFSR یا رجیسترهای تغییر بازخورد خطی، با بازگشت بر روی خروجی خود، کار می کند. آنها به شکلی ساخته شده اند که باعث می شود بی وقفه از طریق الگویی از مقادیر ،در حالی که از آن الگوی به ظاهر تصادفی خارج می شوند چرخش کنند.seed یا مقدار اولیه و تمام مقادیر خروجی باینری هستند ، به این معنی که مقادیر 0 یا 1 را بدست می آورند. نحوه ایجاد مقادیر جدید با استفاده از یک عملگر منطقی ، معمولاً (XOR) است.

برای توضیح LFSR به صورت ساده، باید ببینیم که به چه چیزهایی نیاز داریم:

• به seed یا مقدار اولیه نیاز داریم که یک لیست از 0 و 1 ها است. Seed رشته ای است که با آن جا به جایی را آغاز می کنیم.
• به tap هایی که به ما می گویند که چه قسمت هایی از ثبات را هنگام بازگرداندن دوباره به آن (feedback) استفاده می کنیم. برای مثال مقدار اولیه ما 100 است و دو tap داریم، 1و3. به این معنی است که زمانی که ما شروع به شیفت دادن یا جابه جایی می کنیم، مقدار جدید ترکیبی از اولین و سومین رقم از مقدار اولیه خواهد بود.
• به عملگر XOR نیاز داریم که دو رقم مشخص شده را ترکیب کنیم.
• از آنجایی که ما با اعداد باینری یا دودویی سروکار داریم،مقدار بازگردانده شده یا Feedback باید به صورت باینری باشد. بنابراین ما به عملگر mod 2 نیز نیاز داریم.

یعنی x^2 +1 mod 2

پس، اگر shift register برابر 001 باشد و ما با استفاده از XOR کردن tap های مشخص شده ( که در این مثال 3 و 1 است) عدد جدید 1 خواهد بود. این عدد را در جایگاه اولین رقم (از سمت چپ) قرار می دهیم و بقیه را به جایگاه بعدی شیفت می دهیم. در مرحله ی اول 100 بدست می آید. این جا به جایی را ادامه می دهیم تا زمانی که ببینیم shift register بدست آمده برابر مقدار اولیه یا seed شود.

بنا بر مقدار اولیه و tap هایی که انتخاب میکنیم، میتوانیم حلقه هایی از طول های متفاوت داشته باشیم. حلقه ای که تمامی حالات ممکن ترکیب را بررسی کند تا به مقدار اولیه برسد، maximal length نامیده می شود.در هنگام کار با اعداد باینری، maximal length حلقه برابر 2 به توان n-1 خواهد شد. این حلقه همچنین می تواند حالت اصلی خود را ترک کرده و در یک حلقه کوتاه تر در آن گیر کند ، هرگز به حالت اولیه خود باز نگردد.پیدا کردن مقدار اولیه و tap ها که به maximal length برسد، یک امر مهم است. بعضی از معیار های پیدا کردن این tap ها این است که تعداد آنها باید زوج باشد و مقسوم علیه مشترکی غیر از 1 نداشته باشند.

برای یادگیری عمیق تر با یک مثال پیش می رویم :

در این مثال 4 شخص وجود دارند. میخواهیم ببینیم با توجه به قوانین موجود در هر روز کدام یک از آنها کلاه را بر سر داشته باشد.

قوانین به این صورت است که :

• اگر روز قبل، خانم با موهای قهوه ای کلاه بر سر داشت(مقدار1) ،امروز آقا با مو های زرد، کلاه را بر سر می گذارد.در غیر این صورت کلاه بر سر نمی گذارد (مقدار 0)
• اگر روز قبل، آقا با مو های زرد کلاه بر سر داشت(مقدار1) ،امروز آقای عینکی با مو های سفید، کلاه را بر سر می گذارد.در غیر این صورت کلاه بر سر نمی گذارد (مقدار 0)
• اگر روز قبل، آقای عینکی با مو های سفید، کلاه بر سر داشت(مقدار1) ،امروز خانم با موهای مشکی، کلاه را بر سر می گذارد.در غیر این صورت کلاه بر سر نمی گذارد (مقدار 0)
• اگر روز قبل، یکی از آقای عینکی با موهای سفید یا خانم با موهای مشکی،کلاه بر سر داشتند(مقدار1)، امروز خانم با موهای قهوه ای، کلاه را بر سر می گذارد. در غیر این صورت (هر دو کلاه بر سر داشتند یا هر دو روز قبل کلاه بر سر نداشتند) کلاه بر سر نمی گذارد(مقدار 0)

این قوانین را می توانید در شکل زیر مشاهده کنید :

در تصویر زیر ترتیب بر سر گذاشتن کلاه را به ازای هر روز مشاهده می شود :

این فرایند تا زمانی که مقدار روز 1 تکرار شود ادامه می یابد.

اگر به جدول بدست آمده توجه کنید، مشاهده می کنید که یک عدد در روزهای متوالی جا به جا شده است و یک الگوی خاصی را ایجاد کرده است.

در نهایت کلید pseudo-random تولید شده به صورت زیر استخراج می شود :

این اتفاقی است که در Linear Feedback Shift Registers رخ می دهد.

نتیجه گیری و چالش های LFSR

رجیسترهای تغییر بازخورد خطی (LFSR) در تئوری و عمل تولید عدد شبه تصادفی و برنامه نویسی، ابتدایی و اساسی هستند.

به طور کلی، نمودار بالا یک LFSR معمولی را در مورد زمینه دو عنصر F2 = 0،1 شرح می دهد ، که در آن هر مرحله شامل اضافه کردن مقداری از بیت های حالت استفاده می شود ، و نتیجه به صورت FIFO (اولین ورودی،اولین خروجی) در رجیستر یا ثبات درج می شود.چنین ساختاری کند است به این معنی که در هر مرحله فقط یک بیت جدید تولید می کند. علاوه بر این ، اجرای آن در نرم افزار دشوار است ، زیرا دستکاری های بیت زیادی نیاز است.

امکان استفاده از LFSR تنها با دو tap بازخورد باعث می شود LFSR کمی سریعتر شود.در کنفرانس 1994 در مورد رمزنگاری سریع نرم افزار ، چالشی برای طراحی LFSR وجود داشت که از موازی سازی ارائه شده توسط عملیات کلمه گرا پردازنده های مدرن استفاده می کرد.

روش FSR روش رندوم به نظر نمی رسد. شاید کرک شدن حلقه به نظر آسان می رسد.

چیزی که در مورد FSR میتوان گفت این است که رشته های طولانی را با سرعت بالاتری پردازش و رمز میکند.

اما چالش قابل توجه در این روش طولی است که حلقه آن تولید می کند. به عنوان مثال برای 20 بیت رشته، با TAP های 2 و 19، 1048575 بیت تولید میشود، به این معنی که ما یک مقدار بزرگی از ارقام باینری به نظر رندم خواهیم داشت.

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

مراجع

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

Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of APPLIED CRYPTOGRAPHY , Chapter 6 - Stream Cipher , PARTS : 6.1 , 6,2

این لینک ها نیز توضیحات جامعی در مورد این مطلب دارند.

• http://www.cs.ru.nl/~rverdult/Introduction_to_Cryptanalysis-Attacking_Stream_Ciphers.pdf
• https://www.tutorialspoint.com/cryptography/block_cipher_modes_of_operation.htm
• https://www.freecodecamp.org/news/cryptography-and-lfsr/
• https://www.youtube.com/watch?v=1UCaZjdRC_c
• http://u.math.biu.ac.il/~vishne/publications/TSR.pdf