LFSR

LFSR מקסימלי המורכב מארבע סיביות. האנימציה מראה כיצד ה-LFSR עובר בצורה מחזורית בין כל חמישה עשר המצבים האפשריים שלו.

LFSR (ראשי תיבות של: Linear Feedback Shift Register) הוא מונח במדעי המחשב המתאר אוגר זיזה שהקלט שלו הוא פונקציה לינארית של סיביות המצב שלו. LFSR הוא אוטומט סופי דטרמיניסטי. הערך ההתחלתי של LFSR נקרא גרעין ומתוכו נקבעת שרשרת המצבים האפשרית של האוטומט לאורך זמן ריצתו. מכיוון ש-LFSR הוא פונקציה מחזורית בעלת קלט בגודל סופי הוא אוצר בתוכו מחזור מצבים שתדירותו תלויה בכמות הסיביות המרכיבות את הרכיב ובפונקציית ההיזון שלו.

בקריפטוגרפיה, מימושים של LFSR בחומרה ובתוכנה משמשים כרכיבים במחוללי מספרים פסאודו-אקראיים, אלגוריתמים להרחבת מפתח, פונקציות גיבוב ועוד.

מאפיינים ואופן הפעולה

LFSR מקסימלי המורכב מ-16 סיביות

בכל מחזור התייחסות, ה-LFSR מזיז את כל סיביות המצב שלו מקום אחד הצידה, הסיבית שנדחקה החוצה משמשת כפלט. למקום המתפנה במצב כתוצאה מההזזה מוכנסת סיבית המחושבת על ידי פונקציית ההיזון הלינארית (לרוב, או מוציא) המופעלת על ערכים במקומות ידועים (באנגלית נקראים המקומות מהם נלקחים ערכי הקלט לפונקציה Taps) ועל הפלט. LFSR שפונקציית ההיזון הלינארית שלו נבחרה בצורה טובה יעבור דרך כל $2^{n}-1$ המצבים האפשריים שלו LFSR כזה נקרא LFSR-מקסימלי.

פוקנציית ההיזון ב-LFSR (או פולינום הבסיס) ניתנת לביטוי כפולינום בבסיס בינארי כך שכל אחד מהמקדמים בפולינום הוא 0 או 1. בדוגמה המופיעה משמאל הסיביות המשתתפות בחישוב הפונקציה נמצאות במקומות 16,14,13 ו-11 ופונקציית ההיזון היא: $x^{16}+x^{14}+x^{13}+x^{11}+1$