Doğrusal Geri Besleme Kaydırma Kayıtları, Sözde Rastgele Sayı Üreticileri olarak. Geri besleme kaydırmalı kayıtlar Doğrusal geri besleme kaydırmalı kayıt örneği

Shift register dizileri hem kriptografide hem de kodlama teorisinde kullanılır. Teorileri iyi gelişmiştir, vardiya kaydına dayalı akış şifreleri, elektroniklerin ortaya çıkmasından çok önce askeri kriptografinin beygir gücüydü.

Bir geri besleme kaydırma kaydı iki bölümden oluşur: bir kaydırma kaydı ve bir geri besleme işlevi (Şekil 1.2.1). Kaydırma yazmacı bir bit dizisidir. (Bit sayısı, kaydırma yazmacının uzunluğu tarafından belirlenir. Eğer uzunluk n bit ise, yazmaç n-bit kaydırmalı yazmaç olarak adlandırılır.) Bir bitin çıkarılması gerektiğinde, kaydırma yazmacının tüm bitleri 1 konum sağa kaydırılır. En soldaki yeni bit, kayıttaki diğer tüm bitlerin bir işlevidir. Kaydırma yazmacının çıktısı bir, genellikle en az anlamlı bittir. Kaydırmalı yazmacın periyodu, sonuç dizisinin tekrar etmeye başlamadan önceki uzunluğudur.

Pirinç. 1.2.1.

Kriptograflar, vardiya kaydına dayalı akış şifrelerini sevdiler: dijital donanımla uygulanması kolaydı. Matematik teorisine sadece kısaca değineceğim. 1965 yılında, Norveç hükümetinin baş kriptografı Ernst Selmer, kaydırmalı kayıt dizileri teorisini geliştirdi. Bir NSA matematikçisi olan Solomon Golomb, kendisinin ve Selmer'in bazı sonuçlarını özetleyen bir kitap yazdı.

En basit geri besleme kaydırmalı yazmaç türü, doğrusal geri besleme kaydırmalı yazmaç veya LFSR'dir (Şekil 1.2.2). Geri besleme, bir kayıttaki bazı bitlerin basitçe bir XOR'sidir, bu bitlerin bir listesine bir kademe dizisi denir. Bazen böyle bir kayıt, bir Fibonacci konfigürasyonu olarak adlandırılır. Geri besleme dizisinin basitliği nedeniyle, LFSR'yi analiz etmek için oldukça gelişmiş matematiksel teori kullanılabilir. Kriptograflar dizileri analiz etmeyi severler ve kendilerini bu dizilerin güvenli olacak kadar rastgele olduğuna ikna ederler. LFSR'ler, kriptografide diğer kaydırmalı yazmaçlardan daha yaygın olarak kullanılır.

Pirinç. 1.2.2.

Şek. 1.2.3, birinci ve dördüncü bitlere bir dokunuşla 4 bitlik bir LFSR gösterir. 1111 değeri ile başlatılırsa, tekrarlamadan önce kayıt aşağıdaki dahili durumları alacaktır:

Pirinç. 1.2.3. 4

Çıktı dizisi, en az anlamlı bitlerden oluşan bir dizi olacaktır:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

Bir n-bit LFSR, 2n-1 dahili durumlardan birinde olabilir. Bu, teorik olarak, böyle bir kaydın, 2n-1 bitlik bir periyotla sahte rastgele bir dizi oluşturabileceği anlamına gelir. (Dahili durumların sayısı ve periyot 2n-1'dir, çünkü LFSR'yi sıfırlarla doldurmak, kaydırma yazmacının kesinlikle işe yaramaz olan sonsuz bir sıfır dizisi vermesine neden olacaktır.) Yalnızca belirli kademe dizileriyle, LFSR döngü yapacaktır. tüm 2n-1 dahili durumlar, bu tür LFSR'ler maksimum periyodu olan LFSR'lerdir. Ortaya çıkan sonuca M-dizisi denir.

Belirli bir LFSR'nin maksimum periyoda sahip olması için, kademe dizisinden ve sabit 1'den oluşturulan polinom, ilkel modulo 2 olmalıdır. Polinomun derecesi, kaydırma yazmacının uzunluğudur. n dereceli ilkel bir polinom, bir bölen olan ancak 2n-1'in bölenleri olan tüm d'ler için xd+1'in bir böleni olmayan indirgenemez bir polinomdur.

Genel olarak, belirli bir modülo 2 derecesine sahip ilkel polinomları oluşturmanın kolay bir yolu yoktur. En kolay yol, rastgele bir polinom seçip ilkel olup olmadığını kontrol etmektir. Kolay değil - ve biraz rastgele seçilen bir sayının asal olup olmadığını kontrol etmeye benziyor - ancak birçok matematik yazılım paketi bunu yapabilir.

Çeşitli derecelerdeki polinomların bazıları, ancak kesinlikle hepsi değil, ilkel modulo 2'dir. Örneğin, (32, 7, 5, 3, 2, 1, 0) gösterimi, aşağıdaki polinomun ilkel modulo 2 olduğu anlamına gelir:

x32 + x7 +x5 + x3 + x2 + x + 1

Bu, maksimum süre ile LFSR'ye kolayca genelleştirilebilir. İlk sayı LFSR'nin uzunluğudur. Son sayı her zaman 0'dır ve atlanabilir. 0 dışındaki tüm sayılar, kaydırma kaydının sol kenarından sayılan bir kademe sırasını belirtir. Yani, daha düşük dereceli polinomun terimleri, kaydın sağ kenarına daha yakın konumlara karşılık gelir.

Örneğe devam edersek, (32, 7, 5, 3, 2, 1, 0) yazma, belirli bir 32-bit kaydırma yazmacı için otuz saniye, yedinci, beşinci, üçüncü, ikinci XORing ile yeni bir bit üretildiği anlamına gelir. , ve ilk bitler, sonuçtaki LFSR'nin yinelemeden önce 232-1 değerleri arasında dolaşarak maksimum bir uzunluğa sahip olacaktır.

Geri besleme kaydırma kaydı iki bölümden oluşur: vardiya kaydı ve geri bildirim işlevleri.

Şekil 19. Geri besleme kaydırma kaydı.

Genel olarak, bir kaydırma yazmacı, bir halkanın veya alanın bazı öğelerinin bir dizisidir. En çok kullanılan biraz vardiya kayıtları. Böyle bir kaydın uzunluğu, bit sayısı olarak ifade edilir. Her bit alındığında, kayıttaki tüm bitler bir konum sağa kaydırılır. Yeni en anlamlı bit, kayıttaki diğer tüm bitlerin bir fonksiyonu olarak hesaplanır. Çıktı genellikle en az anlamlı bittir. Kaydırmalı yazmacın periyodu, çıktı dizisinin tekrar etmeye başlamadan önceki uzunluğudur.

En basit kaydırmalı yazmaç türü, doğrusal bir geri besleme kaydırmalı yazmaçtır (LFSR veya LRS). Geri bildirim, bir kaydın bazı bitleri üzerinde basit bir XOR işlemidir. Bu bitlerin listesi tanımlanır karakteristik polinom ve aradı dokunma sırası. Bazen bu şema denir Fibonacci yapılandırması.

Şekil 20. Fibonacci konfigürasyonunun LFOS'u.

LFSR'nin yazılım uygulamasında, değiştirilmiş bir şema kullanılır: yeni bir anlamlı bit oluşturmak için, kademe dizisinin bitlerini kullanmak yerine, jeneratörün çıkışıyla bitlerinin her biri üzerinde eskisini değiştirerek bir XOR işlemi gerçekleştirilir. musluk dizisinin biraz. Bu değişiklik bazen denir Galois yapılandırması.

Şekil 21. Galois konfigürasyonunun RLOS'u.

n-bit LFSR 2'den birinde olabilir n– 1 dahili durum. Bu, teorik olarak, böyle bir kaydın, 2 periyodu olan bir sözde rasgele dizi oluşturabileceği anlamına gelir. n– 1 bit (sıfırlarla doldurmak tamamen işe yaramaz). Tüm 2'nin geçişi n– 1 dahili durum yalnızca belirli kademe sıralarıyla mümkündür. Bu tür kayıtlara maksimum süre ile LFSR denir. LFSR'nin maksimum periyodunu sağlamak için, karakteristik polinomunun olması gerekir. ilkel modulo 2. Polinomun derecesi, kaydırma yazmacının uzunluğudur. İlkel derece polinomu n- öyle indirgenemez bölen ama bölen olmayan bir polinom xd hepsi için +1 D 2'nin bölenleri olan n– 1. (Polinomları tartışırken, terim asal sayı terimi ile değiştirildi indirgenemez polinom). Şekillerde gösterilen LFSR'nin karakteristik polinomu:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

ilkel modulo 2'dir. Böyle bir kaydın süresi, tekrar edene kadar 2 32 - 1 değerin tümü arasında döngü yaparak maksimum olacaktır. En yaygın olarak kullanılanlar, inceltilmiş polinomlardır, yani. sadece bazı katsayıları olan en popüler üç terimli.

LFSR'ye dayalı jeneratörün önemli bir parametresi, doğrusal karmaşıklık. Uzunluk olarak tanımlanır n jeneratör çıkışını simüle edebilen en kısa LFSR. Doğrusal karmaşıklık önemlidir çünkü basit bir Berlenkamp-Massey algoritması sadece 2'yi kontrol ederek böyle bir LFSR'yi yeniden oluşturmak mümkündür. n gama bitleri. İstenen LFSR'nin tanımı ile akış şifresi aslında bozulur.

Doğrusal geri beslemeli kaydırma yazmacında iki kısım (modül) ayırt edilir: kaydırma kaydının kendisi ve eklenen bitin değerini hesaplayan devre (veya alt program). Kayıt, her biri bir bitin mevcut durumunu saklayan fonksiyon hücrelerinden (veya bir makine kelimesinin bitleri veya birkaç kelimeden) oluşur. Hücre sayısı, kayıt uzunluğu olarak adlandırılır. Bitler (hücreler) genellikle her biri bir bit depolayabilen sayılarla numaralandırılır ve hesaplanan bit hücreye itilir ve bir sonraki üretilen bit hücreden çekilir. Eklenen bitin hesaplanması genellikle kaydın kaydırılmasından önce yapılır ve hücreye yerleştirilen hesaplanan bitin değeri ancak kaydırmadan sonra yapılır.

Kaydırmalı yazmacın periyodu, tekrar etmeye başlamadan önce ortaya çıkan dizinin minimum uzunluğudur. Bit hücrelerinin kaydı yalnızca sıfır olmayan farklı durumlara sahip olduğundan, prensipte kaydın periyodu bu sayıyı aşamaz. Sicilin süresi bu sayıya eşitse, böyle bir sicile azami süre sicili denir.

LFSR için geri besleme işlevi, kaydın tüm veya bazı bitlerinin durumlarının doğrusal bir Boole işlevidir. Örneğin, toplam modulo iki veya mantıksal tersi, doğrusal bir Boole işlevidir (formüllerde gösterildiği gibi XOR işlemi) ve en sık olarak bu tür kayıtlarda kullanılır.

Bu durumda, geri besleme fonksiyonunun değişkenleri olan bitler genellikle kıvrımlar.

Donanım uygulamalarında kayıt kontrolü, bir kaydırma darbesi uygulanarak gerçekleştirilir (aksi halde saat veya senkronizasyon darbesi) yazılımdaki tüm hücrelere - kelimedeki geri besleme fonksiyonunun hesaplanması ve bit kaydırma dahil olmak üzere bir program döngüsü yürüterek.

Her saat tik sırasında aşağıdaki işlemler gerçekleştirilir:

Doğrusal Geri Besleme Kaydırma Kaydı

Bu nedenle, mantıksal işlem XOR (hariç OR) bir geri besleme işlevi olarak alınır, yani:

İlkel polinomların özellikleri

Özellikleri

LFSR tarafından üretilen dizinin özellikleri, ilişkili polinomun özellikleri ile yakından ilişkilidir. Sıfır olmayan katsayıları denir kıvrımlar, kayıt defterinin karşılık gelen hücrelerinin yanı sıra, geri besleme işlevinin argümanlarının değerlerini sağlar.

Doğrusal karmaşıklık

Bir ikili dizinin doğrusal karmaşıklığı, LFSR işleminin en önemli özelliklerinden biridir. Aşağıdaki gösterimi tanıtalım:

Sonsuz bir ikili dizinin doğrusal karmaşıklığı aşağıdaki gibi tanımlanan bir sayı olarak adlandırılır:

Sonlu bir ikili dizinin doğrusal karmaşıklığı ilk terimleri olan bir dizi oluşturan en kısa LFSR'nin uzunluğuna eşit olan sayıya denir.

Doğrusal Karmaşıklık Özellikleri

Let ve ikili diziler olsun. O zamanlar:

Korelasyon Bağımsızlığı

Yüksek doğrusal karmaşıklık elde etmek için kriptograflar, birden çok çıktı dizisinin sonuçlarını doğrusal olmayan bir şekilde birleştirmeye çalışırlar. Bu durumda tehlike, bir veya daha fazla çıktı dizisinin (çoğu zaman tek tek LFSR'lerin çıktılarının bile) ortak bir anahtar akışı ile bağlanabilmesi ve lineer cebir kullanılarak açılabilmesidir. Böyle bir güvenlik açığına dayalı hackleme denir. korelasyon otopsisi. Thomas Siegenthaler, korelasyon bağımsızlığını tam olarak tanımlamanın mümkün olduğunu ve korelasyon bağımsızlığı ile doğrusal karmaşıklık arasında bir değiş tokuş olduğunu gösterdi.

Bu hack'in arkasındaki ana fikir, bir jeneratörün çıktısı ile bileşen parçalarından birinin çıktısı arasında bir korelasyon bulmaktır. Daha sonra çıkış sırası gözlemlenerek bu ara çıkış hakkında bilgi alınabilir. Bu bilgiyi ve diğer korelasyonları kullanarak, jeneratör hacklenene kadar diğer ara çıktılar hakkında veri toplamak mümkündür.

Korelasyon saldırıları veya hızlı korelasyon saldırıları gibi varyasyonlar, hesaplama karmaşıklığı ve verimlilik arasında bir ödünleşim içeren birçok lineer geri besleme kaydırma yazmacına dayalı anahtar akışı oluşturucularına karşı başarıyla kullanılmıştır.

Örnek vermek

İlişkili bir polinomlu LFSR için, üretilen dizi forma sahiptir. İşlemin başlamasından önce dizinin kayıt defterine yazıldığını varsayalım, ardından oluşturulan bit akışının periyodu aşağıdaki sıra ile 7'ye eşit olacaktır:

Yedinci basamaktaki içsel durum eski haline döndüğü için bir sonraki adımdan itibaren bir tekrar olacaktır. Başka bir deyişle, polinomun ilkelliği nedeniyle dizinin periyodu 7'ye eşit çıktı.

İlkel polinomlar üretmek için algoritmalar

Hazır tablolar

Bir polinomun ilkelliğini hesaplamak oldukça karmaşık bir matematiksel problemdir. Bu nedenle, jeneratörün maksimum periyodunu sağlayan kademe sıralarının numaralarını listeleyen hazır tablolar bulunmaktadır. Örneğin, 32 bitlik bir kaydırma yazmacı için bir dizi vardır. Bu, yeni bir bit oluşturmak için XOR işlevini kullanarak 31., 30., 29., 27., 25. ve 0. bitlerin toplanması gerektiği anlamına gelir. Bu tür LFSR'nin C dilindeki kodu aşağıdaki gibidir:

Int LFSR (void ) ( static unsigned long S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) ve 1)<< 31 ) | (S>> 1); dönüş S & 1 ; )

RSLOS oluşturucuların yazılım uygulamaları oldukça yavaştır ve C yerine assembler ile yazılırsa daha hızlı çalışır. Bir çözüm, paralel olarak 16 RLLS kullanmaktır (veya belirli bir bilgisayarın mimarisindeki kelime uzunluğuna bağlı olarak 32). Böyle bir şemada, boyutu LFSR'nin uzunluğuna eşit olan bir kelime dizisi kullanılır ve dizi kelimesinin her bir biti kendi LFSR'sine atıfta bulunur. Aynı musluk sıra numaralarının kullanılması şartıyla, bu fark edilir bir performans artışı sağlayabilir. [örnek koda ihtiyacım var] (bkz: bitslice).

Galois yapılandırması

Doğrusal bir geri besleme kaydırma yazmacının Galois konfigürasyonu

Geri bildirim şeması da değiştirilebilir. Bu durumda, oluşturucu daha fazla şifreleme gücüne sahip olmayacak, ancak bunu programlı olarak uygulamak daha kolay olacaktır. Yeni bir en soldaki biti oluşturmak için kademe dizisinin bitlerini kullanmak yerine, kademe dizisinin her bir bitini jeneratörün çıkışıyla XOR yapın ve bu işlemin sonucuyla değiştirin, ardından jeneratörün sonucu en soldaki yeni bit olur . C dilinde şöyle görünür:

Int LFSR (void ) ( static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

Avantajı, tüm XOR'lerin tek bir işlemde gerçekleştirilmesidir.

• İlk olarak verilen Fibonacci konfigürasyonunun ve burada verilen Galois konfigürasyonunun aynı dizileri (2 32 -1 uzunluğunda) verdiği, ancak faz olarak birbirinden farklı olduğu kanıtlanabilir.
• Galois yapılandırmasında LFSR işlevine yapılan sabit sayıda çağrı döngüsü, Fibonacci yapılandırmasındakinden yaklaşık iki kat daha hızlıdır (Intel Core i5 üzerinde MS VS 2010 derleyicisi)
• Galois konfigürasyonunda, geri besleme kelimesindeki bitlerin sırasının Fibonacci konfigürasyonuna kıyasla ters olduğuna dikkat edin.

Jeneratör örnekleri

dur-kalk jeneratörler

Dur-Git Alternatif Jeneratör

Bu osilatör, başka bir LFSR'nin saat frekansını kontrol etmek için bir LFSR'nin çıkışını kullanır. RSLOS-2'nin saat çıkışı, RSLOS-1'in çıkışı tarafından kontrol edilir, böylece RSLOS-2, yalnızca t-1 zamanında RSDOS-1'in çıkışı bire eşitse durumunu değiştirebilir. Ancak bu şema korelasyon açılışına direnmedi.

Bu nedenle, aynı fikre dayalı geliştirilmiş bir jeneratör önerilmiştir. Dur-kalk serpiştirilmiş jeneratör olarak adlandırılır. Farklı uzunluklarda üç LFSR kullanır. LFSR-2, LFSR-1'in çıkışı bire eşit olduğunda ve LFSR-3, LFSR-1'in çıkışı sıfıra eşit olduğunda saatlenir. Jeneratörün çıkışı, RSLOS-2 ve RSLOS-3'ün modulo 2 toplamıdır. Bu jeneratörün büyük bir periyodu ve büyük bir lineer karmaşıklığı vardır. Yazarları ayrıca RLOS-1'in korelasyon açılması için bir yöntem gösterdi, ancak bu, jeneratörü büyük ölçüde zayıflatmaz.

Gollmann Çağlayanı

Gollmann Çağlayanı

Gollmann Cascade, dur-kalk üretecinin geliştirilmiş bir versiyonudur. Her birinin zamanlaması önceki LFSR tarafından kontrol edilen bir dizi LFSR'den oluşur. LFSR-1'in t anında çıkışı 1 ise, LFSR-2 saatlidir. LFSR-2'nin t anında çıkışı 1 ise, LFSR-3 saatlidir ve bu böyle devam eder. Son LFSR'nin çıkışı, jeneratörün çıkışıdır. Tüm LFSR'lerin uzunluğu aynıysa ve n'ye eşitse, k LFSR sisteminin doğrusal karmaşıklığı .

Bu fikir basittir ve çok büyük periyotlara, büyük doğrusal karmaşıklıklara ve iyi istatistiksel özelliklere sahip diziler oluşturmak için kullanılabilir. Ancak ne yazık ki, "kilitleme" (kilitleme) adı verilen bir açıklığa karşı hassastırlar. Daha fazla stabilite için, en az 15 k kullanılması tavsiye edilir. Ayrıca, daha kısa LFSR kullanmak, daha az uzun LFSR kullanmaktan daha iyidir.

eşik üreteci

eşik üreteci

Bu oluşturucu, değişken sayıda vardiya kaydı kullanarak önceki oluşturucuların güvenlik sorunlarını aşmaya çalışır. Teoride, daha fazla sayıda kaydırmalı yazmaç kullanıldığında, bu üreteçte yapılan şifrenin karmaşıklığı artar.

Bu üreteç, çıktıları majörleştirme işlevine beslenen çok sayıda kaydırma kaydından oluşur. Kayıtların çıkışlarındaki birim sayısı yarıdan fazla ise üreteç bir birim üretir. Çıkışlardaki sıfırların sayısı yarıdan fazlaysa, jeneratör bir sıfır üretir. Sıfır ve bir sayılarının karşılaştırılabilmesi için kaydırmalı yazmaçların sayısının tek olması gerekir. Tüm kayıtların uzunlukları nispeten asal olmalıdır ve geri besleme polinomları, oluşturulan dizinin periyodu maksimum olacak şekilde ilkel olmalıdır.

Üç kaydırmalı yazmaç durumunda, üreteç şu şekilde temsil edilebilir:

Bu üreteç, eşik üretecinin daha fazla lineer karmaşıklığa sahip olması dışında Geff üretecine benzer. Doğrusal karmaşıklığı:

burada , , birinci, ikinci ve üçüncü kaydırma yazmaçlarının uzunluklarıdır.

Dezavantajı, her çıkış bitinin kaydırma yazmacının durumu hakkında bazı bilgiler vermesidir. Tam olarak 0.189 bit olmak üzere. Bu nedenle, bu üreteç korelasyon açıklığına direnemeyebilir.

Diğer çeşitler

kendi kendine incelme

Kendinden azalan jeneratörlere kendi frekanslarını kontrol eden jeneratörler denir. Bu tür jeneratörlerin iki türü önerilmiştir. Birincisi, lineer bir geri besleme kaydırmalı yazmaç ve kaydırma yazmacının çıkış değerlerinin ne olduğuna bağlı olarak bu kaydı saatleyen bir devreden oluşur. LFSR çıkışı bire eşitse, yazmaç d kez saatlenir. Çıkış sıfır ise, kayıt k kez saatlenir. İkincisi neredeyse aynı tasarıma sahiptir, ancak biraz değiştirilmiştir: saatli devrede, 0 veya 1 için bir kontrol olarak, çıkış sinyalinin kendisi alınmaz, ancak doğrusal geri beslemeli kaydırma yazmacının belirli bitlerinin XOR'u alınır. Ne yazık ki, bu tür bir jeneratör güvenli değildir.

İç çarpımlı çok hızlı osilatör

Bu üreteç, farklı saat frekanslarına sahip doğrusal geri beslemeli iki kaydırma yazmacı kullanır: LFSR-1 ve LFSR-2. RLOS-2'nin saat frekansı, RLLS-1'inkinden d kat daha yüksektir. Bu kayıtların bireysel bitleri bir AND işlemi ile birleştirilir. AND işleminin çıktıları daha sonra XOR'lanır. Çıkış sırası bu XOR bloğundan alınır. Yine, bu jeneratör mükemmel değil (Doğrusal tutarlılığın açılmasından kurtulamadı. - LFSR-1'in uzunluğu, - LFSR-2'nin uzunluğu ve d, saat frekanslarının oranıysa, o zaman iç durumu jeneratör, uzunluk çıkış dizisinden elde edilebilir), ancak yüksek doğrusal karmaşıklığa ve mükemmel istatistiksel performansa sahiptir.

En basit geri besleme işlevi türü, belirli bitlerin içeriğinin modulo 2 toplamı gibi doğrusal bir işlevdir. Böyle bir kayıt, bir Doğrusal Geri Besleme Kaydırma Kaydı (kısaca LFSR) olarak adlandırılır. Genel durumda, doğrusal geri besleme işlevi formülle verilir. Burada kk= 1 ise k th bit geri besleme işlevinde kullanılır ve kk= 0 aksi halde. Å sembolü, modulo 2 eklenmesini (özel VEYA) ifade eder.

Örneğin, geri besleme işlevine sahip bir LFSR düşünün (şekle bakın).

Eğer kaydın ilk durumu 1111 ise, sonraki döngülerde aşağıdaki durum serilerini alacaktır: …

Çıkış dizisi, kaydın en az anlamlı (en sağdaki) basamağından oluşturulur. Şu şekilde görünecektir: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Üretilen bit dizisinin tamamen kaydın başlangıç ​​durumu ve geri besleme fonksiyonu tarafından belirlendiği görülebilir. Olası kayıt durumlarının sayısı sonlu olduğundan (2'ye eşittir) L), sonra, er ya da geç, tuş dizisi kendini tekrar etmeye başlayacaktır. Bir tuş dizisinin tekrarlanmayan bölümünün maksimum uzunluğu, periyodu olarak adlandırılır. T. Süre, geri besleme işlevine bağlıdır. Mümkün olan maksimum süre T maks=2 L-1 (kayıt 0000...0 hariç tüm olası durumları alır). LFSR'nin maksimum periyotlu çıkış dizisine denir. M-dizisi.

LFSR'nin maksimum periyoda sahip olacağı koşulları bulmak için, geri besleme fonksiyonları karakteristik polinomla eşleşir. Yani yukarıda örnek olarak verilen register polinomuna karşılık gelir. Teorik analiz, LFSR'nin ancak ve ancak polinom P(x) bir ilkel. Aşağıda pratik kullanım için önerilen bazı ilkel polinomlar verilmiştir. Tablo, değişkenin derecelerini gösterir. x polinomda. Örneğin, (31, 3) girişi polinomla eşleşir.

LFSR'ler başlangıçta donanımda bir dizi dijital devre olarak uygulanmak üzere tasarlanmıştır. LFSR'nin yazılım uygulamaları genellikle donanım uygulamalarından daha yavaştır. Performansı artırmak için, kaydın durumunu bir tamsayı olarak saklamak avantajlıdır. L- bireysel bitleri kaydın ikili rakamlarına karşılık gelen bit numarası. Daha sonra tek tek bitlere erişmek için bitsel işlemler (kaydırma, maskeleme vb.) kullanılır.

Akış şifreleri oluşturmak için, kaydırma yazmaçlarındaki diziler çok sık kullanılır. Bir geri besleme kaydırma yazmacı, Şekil 2'de gösterildiği gibi bir kaydırma yazmacı ve bir geri besleme işlevi olmak üzere iki bölümden oluşur. 87. Kaydırma kaydının kendisi, sayısı kaydın uzunluğunu belirleyen bir bit dizisidir. Yani, kayıtta n bit varsa, o zaman n bitlik kaydırma kaydının olduğunu söylerler. Her bit alındığında, kaydırma yazmacının tüm bitleri, genellikle en az anlamlı bitlere doğru bir konum sağa kaydırılır. Kaydırmalı yazmacın periyodu, sonuç dizisinin tekrar etmeye başlamadan önceki uzunluğudur.

Pirinç. 87.

Bitler üzerinde işlem gerçekleştiren herhangi bir matematiksel işlev, geri besleme işlevi görebilir. En basit geri besleme kaydırmalı yazmaç türü, doğrusal geri besleme kaydırmalı yazmaçtır (LFSR). LFSR'de geri besleme, bir kaydın bazı bitleri üzerindeki bir modulo 2 ekleme (XOR) işlemidir; bu bitlerin listesi, şekil 2'de gösterildiği gibi, bir dizi musluk veya başlatma noktası olarak adlandırılır. 88. Bazen böyle bir modele Fibonacci konfigürasyonu denir. Geri besleme dizisinin basitliği nedeniyle, LFSR'yi analiz etmek için oldukça gelişmiş bir matematiksel teori kullanılabilir. Her durumda, üretilen SRP'nin kalitesi özel bir dizi testle değerlendirilir.

Pirinç. 88.

LFSR, polinomlar şeklinde yazılır. Bu durumda, polinomun birinci elemanının derecesi, kaydırma yazmacındaki bit sayısını gösterir ve polinomun geri kalan üyelerinin üstel üsleri, hangi başlatma noktalarının kullanılacağını belirtir. Bu nedenle, örneğin, x 4 + x + 1 yazmak, bi ve b 0 bitlerinin geri bildirim oluşumuna katılacağı dört öğeden oluşan bir kaydın kullanılacağı anlamına gelir (Şekil 89).

Pirinç. 89.4

Şekil 2'de gösterilen kaydın çalışmasını düşünün. 89. Örneğin, 0101 değeri ile sıfırlayın (ilk başlatma, yalnızca sıfır dizisi dışında herhangi bir bit dizisiyle gerçekleştirilebilir, çünkü bu durumda geri besleme her zaman sıfır değerini oluşturur ve kayıt beklenen PSP'yi üretmez). Yani, kayıtta bir pozisyon sağa kayma var. 1'e eşit olan en az anlamlı bit, kayıttan çıkmaya zorlanır ve PRS'nin ilk bitini oluşturur. Kaydırmadan önce b ve b 0 konumlarında olan bitler modulo 2 eklenir ve yeni bir

kaydın yüksek biti. Dikkate alınan LFSR'nin çalışmasının açıklayıcı bir örneği Şekil 2'de gösterilmektedir. 90.

Pirinç. 90.

Olarak Şekil l'de görülebilir. 90, kayıt doldurma 16 olası durumdan 15'lik bir ağırlıktan geçecektir (daha önce LFSR 0000 olduğunda on altıncı durumun dikkate alınamayacağını belirledik). Bundan sonra, kaydın doldurulması yeniden 0101'in başlangıç ​​değerine eşit olacak ve bit dizisinin gelişimi tekrar etmeye başlayacaktır. Kayıt defterinin çıktı dizisi, en az anlamlı bit dizisi olacaktır (Şekil 90'daki yatay çizgiye kadar): 1010111110001001. Bit dizisinin tekrarlanmadan önceki boyutuna periyot denir. Belirli bir LFSR'nin maksimum periyodunu sağlamak için (yani, kaydın olası tüm dahili durumlardan geçmesi için), kaydın çalışmasını belirleyen polinom ilkel modulo 2 olmalıdır. Böyle polinomlar üretin. Sadece bir polinom alınabilir ve indirgenemez modulo 2 olup olmadığı kontrol edilebilir. Genel durumda, n dereceli bir ilkel polinom, x 2 "+1'in bir böleni olan, ancak 2 "-1'in bölenleri olan tüm d'ler için xd +1'in bir böleni olmayan indirgenemez bir polinomdur. B. Schneier, indirgenemez modulo 2 olan bazı polinomların bir tablosunu sağlar.

LFSR'nin çalışması örneğini dikkate almanın sonucu olarak elde edilen bilgileri özetlersek (Şekil 90), n-bit LFSR'nin 2”-1 dahili durumlardan birinde olabileceğini söyleyebiliriz. Teorik olarak, böyle bir kayıt, 2 n -1 bitlik bir periyoda sahip bir sözde rasgele dizi üretebilir. Bu tür kayıtlara maksimum periyotlu LFSR kayıtları denir. Ortaya çıkan çıktıya t-dizisi denir.