Doğrusal geri besleme kaydırmalı kayıt örneği. Doğrusal geri beslemeli kaydırma kayıtları. Doğrusal olmayan geri beslemeli hücresel otomatlar ve vardiya kayıtları

şifre çözme - p i = D (k ben , c i) , gösterildiği gibi pilav. 7.21.

Pirinç. 7.21.

Akış şifreleri, blok şifrelerinden daha hızlıdır. Akış şifresinin donanım uygulaması da daha basittir. İkili akışları şifrelememiz ve bunları sabit bir hızda aktarmamız gerektiğinde, en iyi seçim bir akış şifresi kullanmaktır. Akış şifreleri, iletim sırasında bit bozulmasına karşı daha fazla korumaya sahiptir.

Modern bir akış şifresinde, her r -düz metin akışındaki bitword kullanılarak şifrelenir r karşılık gelen oluşturmak için anahtar akışındaki -bit kelime r - şifreli metin akışındaki bit kelime.

Pirinç. 7.22.

Tek seferlik ped mükemmel bir şifredir. O mükemmel. Rakibe şifreli metin ve düz metnin anahtarını veya istatistiklerini tanıma yeteneği verecek hiçbir yöntem yoktur. Orijinal ve şifreli metinler arasında hiçbir ilişki yoktur. Başka bir deyişle, düz metinden bazı örnekler alsanız bile, şifreli metin gerçek bir rastgele bit akışıdır. Eve, düz metin boyutu n-bit ise 2n olan tüm olası rastgele anahtar akışlarını denemedikçe şifreyi kıramaz. Ancak bununla ilgili bir sorun var. Verici ve alıcı, tek seferlik tuş takımını paylaşmak için her bilgi alışverişinde bulunmak istediklerinde bağlantı kurmalıdır. Bir şekilde rastgele bir anahtar üzerinde anlaşmaları gerekir. Dolayısıyla bu mükemmel ve ideal şifreyi uygulamak çok zordur.

Örnek 7.17

Aşağıdaki durumların her birinde tek seferlik ped şifresi kullanıldığında şifreli metnin biçimi nedir?

a. Orijinal metin n sıfırdan oluşur.

b. Kaynak metin n birimden oluşmaktadır.

içinde. Orijinal metin, değişen sıfırlar ve birlerden oluşur.

d. Orijinal metin rastgele bir bit dizisidir.

Çözüm

a. Çünkü , ardından şifreli metin akışı anahtar akışıyla eşleşir. Anahtar rastgele ise, şifreli metin de rastgeledir. Orijinal metnin parçaları şifreli metinde korunmaz.

b. Çünkü , dolgu nerede, şifreli metin akışı, anahtar akışının dolgusudur. Anahtar akışı rastgele ise, şifreli metin de rastgeledir, düz metnin bitleri şifreli metinde saklanmaz.

c. Bu durumda, şifreli metin akışındaki her bit, anahtar akışındaki veya tamamlayıcısındaki ile aynıdır. Bu nedenle, anahtar akışı rastgele ise sonuç da rastgeledir.

d. Bu durumda, şifreli metin açıkça rastgeledir, çünkü iki rastgele biti XORing yapmak rastgele bir bit akışı ile sonuçlanır.

Geri besleme kaydırma kaydı

Tek seferlik pedde bir iyileştirme (FSR - Geri Besleme Kaydırma Kaydı). FSR, yazılımda veya donanımda uygulanabilir, ancak basitlik için donanım uygulamasını ele alacağız. Geri besleme kaydırma kaydı içerir vardiya kaydı ve geri bildirim işlevleri, da gösterildiği gibi pilav. 7.23.

Pirinç. 7.23.

Kaydırmalı yazmaç, her hücrenin tek bir biti depolamaya tahsis edildiği, b0'dan bm-1'e kadar m hücre dizisidir. Hücreler, başlangıçta "tohum değeri" veya kaynak. Bir bitin çıkması gerektiğinde (örneğin, belirli bir zamanda bir sinyalde), her bit bir hücre sağa kaydırılır. Bu, her hücrenin değerinin sağdaki bitişik hücreye atandığı ve sol hücrenin değerini aldığı anlamına gelir. En sağdaki b 0 hücresi çıktı olarak kabul edilir ve çıktı değerini (k i ) verir. En soldaki hücre, b m-1, değerini geri besleme fonksiyonu bilgi değerine göre alır. Fonksiyonun çıktısını geri besleme bilgisi ile gösteriyoruz b m . Geri besleme bilgisi işlevi, bm'yi hesaplamak için hücrelerin hangi değerlere sahip olduğunu belirler. Geri besleme bilgisi kaydırma yazmacı, doğrusal veya doğrusal olmayan olabilir.

Doğrusal Geri Besleme Kaydırma Kaydı (LFSR). b m'nin b 0 , b 1 ,…..., b m-1 doğrusal bir fonksiyon olduğunu varsayalım, bunun için

Doğrusal geri besleme kaydırma yazmacı ikili rakamlarla çalışır, bu nedenle çarpma ve toplama GF(2) alanındadır, bu nedenle Ci'nin değeri 1 veya 0'dır, ancak çıktıda geri besleme bilgisi almak için C 0 1 olmalıdır. Toplama işlemi ÖZEL VEYA bir işlemdir. Diğer bir deyişle,

Örnek 7.18

5 hücreli doğrusal bir geri besleme kaydırma kaydı oluşturalım.

Çözüm

C i = 0 ise, b i, b m'nin hesaplanmasında bir rol oynamıyorsa, bu, b i'nin geri besleme bilgi fonksiyonu ile ilişkili olmadığı anlamına gelir. c i = 1 ise b m , b m hesaplamasına dahil edilir . Bu örnekte, c 1 ve c 3 sıfırdır; bu, yalnızca üç bağlantımız olduğu anlamına gelir. Şekil 7.24 doğrusal bir geri besleme kaydırma yazmacının devresini gösterir.

Pirinç. 7.24.

Örnek 7.19

4 hücreli bir lineer geri besleme kaydırma yazmacı oluşturalım. . 20'den sonra kayıt değerini göster operasyonlar (vardiyalar) orijinal değer (0001) 2 ise.

Çözüm

Şekil 7.25şifreleme için doğrusal bir geri besleme kaydırma yazmacının devresini ve kullanımını gösterir.

Pirinç. 7.25.

Tablo 7.6. anahtar akışı değerini gösterir. Her geçiş için b4'ün ilk değeri hesaplanır ve ardından her bit bir hücre sağa kaydırılır.

Tablo 7.6.

bugünkü değeri	b4	b3	b2	b1	0	ben
Başlangıç ​​değeri	1	0	0	0	1
1	0	1	0	0	0	1
2	0	0	1	0	0	0
3	1	0	0	1	0	0
4	1	1	0	0	1	0
5	0	1	1	0	0	1
6	1	0	1	1	0	0
7	0	1	0	1	1	0
8	1	0	1	0	1	1
9	1	1	0	1	0	1
10	1	1	1	0	1	0
11	1	1	1	1	0	1
12	0	1	1	1	1	0
13	0	0	1	1	1	1
14	0	0	0	1	1	1
15	1	0	0	0	1	1
16	0	1	0	0	0	1
17	0	0	1	0	0	0
18	1	0	0	1	0	0
19	1	1	0	0	1	0
20	1	1	1	0	0	1

Anahtar akışının 1000100110101111 1001…… olduğunu unutmayın. İlk bakışta rastgele bir dizi gibi görünüyor, ancak çok sayıda işleme (kaydırma) bakarsak dizilerin periyodik olduğunu görebiliriz. 15 bitlik bu tekrar aşağıda gösterilmiştir.

Akış anahtarı, doğrusal geri besleme kaydırma yazmacı kullanılarak üretilir sözde rastgele dizi, burada N uzunluğundaki diziler tekrarlanır. Akış periyodiktir. Jeneratör devresine ve ilk bilgilere bağlıdır ve 2 m - 1'den fazla olamaz. Her şema, tüm sıfırları içerenden tüm birleri içeren m-bit dizileri üretir. Bununla birlikte, ilk dizi yalnızca sıfırlardan oluşuyorsa sonuç işe yaramaz - orijinal metin tüm sıfırların bir akışı olacaktır. Bu nedenle, böyle bir başlangıç ​​dizisi hariç tutulur.

Eğitim ve Bilim Bakanlığı

RUS DEVLET SOSYAL ÜNİVERSİTESİ

BİLGİ TEKNOLOJİLERİ FAKÜLTESİ

BİLGİ KORUMA BÖLÜMÜ

Bilgi güvenliğini sağlamanın kriptografik yöntemleri ve araçları

ders çalışması

"R sözde rasgele sayı üreteçleri olarak doğrusal geri beslemeli kaydırma yazmaçları"

Tamamlanmış:

3. sınıf öğrencisi

KZOI-D-3 grubu

Larionov I.P.

Kontrol:

Doç. Baranova E.K.

Moskova 2011
İÇERİK

giriiş ……………………………..…………………………………….3

1. İşin teorik temelleri…………………………………………4
   1. Geri beslemeli kaydırma yazmaçları hakkında genel bilgiler…………..4
      1. RgCsLOS'a dayalı akış şifreleri hakkında………………….………10
      2. Oluşturulan sözde rastgele dizi PgCsLOS'un doğrusal karmaşıklığı üzerine……………………………………….……12
      3. Oluşturulan sözde rasgele sayı dizisinin korelasyon bağımsızlığı üzerine PrCsLOS………..….13
      4. Oluşturulan sözde rasgele sayı dizisini açmanın diğer yöntemlerinde RgCsLOS………………………………………..14
2. Sözde rastgele dizi oluşturucu olarak RgCsLOS'un yazılım uygulaması….…………………………….15
   1. Algoritmanın genelleştirilmiş şeması………………………………………...15
   2. Yazılım modüllerinin ve arayüzün tanımı.……………….16
   3. Kullanım kılavuzu………………………………………...20

Çözüm ………………………………………………………………22

bibliyografya………………………………………………….....23

Ek A ….………………………………………………………..24

GİRİİŞ

Bu çalışmanın amacı, geri beslemeli kaydırmalı yazmaçlara dayalı bir sözde rasgele sayı üretecinin çalışmasını gerçekleştiren bir yazılım uygulaması geliştirmektir. Bu uygulamanın grafiksel bir arayüz ile geliştirilmesi, dilde gerçekleştirilir. Windows işletim sistemi için C++.

20. yüzyılda kriptografinin gelişmesiyle kriptograflar, mesajları hızlı ve güvenilir bir şekilde şifreleyip şifresini çözebilecek şifreleme cihazları ve makineleri yaratma göreviyle karşı karşıya kaldılar. O zamanlar zaten açık olan simetrik şifreleme sistemleri bu gereksinimi karşılıyordu, ancak zayıf noktaları, anahtara ve gizliliğine güçlü bir bağımlılıktı. Bu amaçla kullanılabilecek en uygun şifre sınıfı kumar şifreleridir. Sorun, mesajın şifresi çözüldüğünde algılanamayan bir gama oluşturma sorunu ortaya çıktı. Teorik olarak, gama her seferinde rastgele olsaydı ve zamanla değişirse bu mümkündü. Ancak, tamamen rastgele değişen bir gama kullanıldığında, mesajın güvenilir bir şekilde şifrelenmesi-şifresinin çözülmesini sağlamak zor olacaktır. Kriptograflar, amacı, belirli bir kurala göre rastgele bir aralığın oluşturulmasını uygulayan bir algoritma bulmak olan bu sorunu çözme görevini üstlendiler, böyle bir dizi "sözde" rastgele konumlarda sıfırlar ve birler içermelidir ve birlerin ve sıfırların sayısı yaklaşık olarak aynı olmalıdır. Bu rastgele diziye denirsözde rastgeleRastgele değil, belirli bir kurala göre üretildiğinden.

Çözüm kısa sürede bulundu. Kaydırmalı yazmaçların özelliklerinin incelenmesi, geri besleme kaydırmalı yazmaçların, iç yapıları nedeniyle kod çözmeye yeterince dirençli olan sözde rastgele diziler üretebildiğini belirlemeyi mümkün kılmıştır.

1. İşin teorik temelleri

1.1 Doğrusal geri beslemeli kaydırmalı yazmaçlar hakkında genel bilgiler

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

Geri besleme kaydırma kaydı (bundan sonra PgCsOS olarak anılacaktır) iki bölümden oluşur: bir kaydırma kaydı ve bir geri besleme işlevi.Kaydırma yazmacı bir bit dizisidir. Bit sayısı belirlenirvardiya kaydı uzunluğu, uzunluk n bit ise, kayıt denirn-bit kaydırma yazmacı. 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.Vardiya kaydı dönemisonuçtaki dizinin tekrar etmeye başlamadan önceki uzunluğudur.

Şekil Geri Besleme Kaydırma Kaydı

Kaydırma yazmaçları, dijital donanım kullanılarak kolayca uygulandıkları için akış şifrelerinde hızla kullanım buldu. 1965 yılında, Norveç hükümetinin baş kriptografı Ernst Selmer, vardiya kaydı dizisi teorisini geliştirdi. Bir NSA matematikçisi olan Solomon Golomb, sonuçlarından bazılarını ve Selmer'in sonuçlarını özetleyen bir kitap yazdı. En basit geri besleme kaydırmalı yazmaç türüdoğrusal geri besleme kaydırma kaydı ( doğrusal geri besleme kaydırmalı yazmaç, bundan sonra LFSR veya RgCsLOS olarak anılacaktır) . Bu tür kayıtların geri bildirimi, kaydın bazı bitlerinin basitçe bir XOR'udur (iki modül ilavesi), 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, PgCsLOC'u analiz etmek için oldukça gelişmiş bir matematiksel teori kullanılabilir. Ortaya çıkan çıktı dizilerini analiz ederek, bu dizilerin güvenli olacak kadar rastgele olduğunu doğrulayabilirsiniz. Kaydırmalı yazmaçlar, kriptografide diğer kaydırmalı yazmaçlardan daha sık kullanılır.

Şekil PgCsLOS Fibbonacci

Genel olarak, n -bit PrCsLOS şunlardan birinde olabilir: N=2n -1 dahili durumlar. Bu, teorik olarak, böyle bir kaydın, T=2 periyodu ile sözde-rastgele bir dizi üretebileceği anlamına gelir. n -1 bit. (İç durumların sayısı ve periyot eşittir N=Tmaks=2n -1 çünkü PrCsLOC'u sıfırlarla doldurmak, kaydırma yazmacının sonsuz bir sıfır dizisi vermesine neden olur, bu kesinlikle işe yaramaz). Yalnızca belirli kademe dizileri ile PrCsLOS döngüsel olarak tüm 2 n -1 dahili durum, bu tür RgCsLOSMaksimum süre ile RgSsLOS. Ortaya çıkan sonuç denirM-dizisi.

Örnek . Aşağıdaki şekil, birinci ve dördüncü bitlerden bir dokunuşla 4 bitlik bir PrCsLOS'u göstermektedir. 1111 değeri ile başlatılırsa, tekrarlamadan önce kayıt aşağıdaki dahili durumları alacaktır:

Vardiya onay numarası (dahili durum)	Kayıt durumu				çıkış biti
Başlangıç ​​değeri
15 (başlangıç ​​durumuna dönüş)
16 (tekrar durumları)

Çı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 periyodu ile T=15, olası dahili durumların toplam sayısı (sıfır hariç), N=2 4 -1=16-1=15= Tmaks , bu nedenle, çıkış sırası M -sonraki.

Belirli bir PgCsLOS'un maksimum periyoda sahip olması için, kademe dizisinden ve sabit 1'den oluşturulan polinom, ilkel modulo 2 olmalıdır. Polinom, bir güçler toplamı olarak temsil edilir, örneğin, bir derece polinomu. n şöyle görünür:

a n x n +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 +…+a 1 x+a 0 , burada a ben =(0, 1 ) i=1…n için, a x i – biti gösterir.

Polinomun derecesi, kaydırma yazmacının uzunluğudur. n dereceli bir ilkel polinom, x'in böleni olan indirgenemez bir polinomdur. 2n-1 +1 ama x'in böleni değil d 2'nin bölenleri olan tüm d için +1 n -bir. İlgili matematiksel teori şurada bulunabilir.

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. Bu kolay değildir ve rastgele seçilen bir sayının asal olup olmadığını kontrol etmeye benzer - ancak birçok matematiksel yazılım paketi bu sorunu çözebilir.

Çeşitli derecelerdeki polinomların bazıları, ancak kesinlikle hepsi değil, ilkel modulo 2 aşağıda verilmiştir. Örneğin, giriş

(32, 7, 5, 3, 2, 1, 0) aşağıdaki polinomun ilkel modulo 2 olduğu anlamına gelir: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

Bu, maksimum periyotla PrCcLOC'a kolayca genelleştirilebilir. İlk sayı PrCsLOS'un 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 , elde edilen RgCsLOS maksimum uzunluğa sahip olacak ve 2'den sonra tekrarlanana kadar döngü yapacaktır. 32 -1 değer.

Şekil 4 maksimum uzunluklu 32-bit PrCsLOS

Tap dizisinin polinom (32, 7, 5, 3, 2, 1, 0) ile karakterize edildiği PgCsLOS program kodunu düşünün. C dilinde şöyle görünür:

int LFSR()(

statik imzasız uzun ShiftRegister = 1;

/* 0 hariç hepsi. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftKayıt))

& 0x00000001)

<<31)

| (ShiftKayıt >> 1) ;

dönüş ShiftRegister & 0 x 00000001;)

Kaydırmalı yazmaç bir bilgisayar sözcüğünden daha uzunsa, kod daha karmaşık hale gelir, ancak çok fazla değil. uygulamada B bazı ilkel polinomlar modulo 2'nin bir tablosu verilmiştir, bunu daha sonra bu polinomların bazı özelliklerini tanımlamak için kullanacağız ve ayrıca bir kademe dizisi ayarlamak için yazılım uygulamasında kullanacağız.

Tablonun tüm öğelerinin tek sayıda katsayıya sahip olduğuna dikkat edilmelidir. Böyle uzun bir tablo, PrCfLOC ile daha fazla çalışma için sağlanır, çünkü PrCfLOC genellikle akış şifreleri ile kriptografi için ve sözde rasgele sayı üreteçlerinde kullanılır. Bizim durumumuzda, yediden fazla olmayan en yüksek dereceye sahip polinomları kullanabiliriz.

p(x) ilkel ise, x de öyledir n p(1/x), yani tablonun her elemanı aslında iki ilkel polinomu tanımlar. Örneğin, (a, b, 0) ilkel ise, (a, a-b, 0) da ilkeldir. (a, b, c, d, 0) ilkel ise, o zaman (a, a-d, a-c, a-b, 0) da ilkeldir. Matematiksel olarak:

x ilkel ise a+xb +1, o zaman ilkel ve x a+x a-b+1,

x ilkel ise a + x b + x c + x d +1, o zaman ilkel ve x a + x a-d + x a-c + x a-b +1. Yeni bir bit oluşturmak için kaydırma yazmacının yalnızca iki bitini XOR yapmanız gerektiğinden (sıfır terim dikkate alınmaz, yani x 0 =1, yukarıdaki örneğe bakın). Aslında, tabloda verilen tüm geri besleme polinomları seyrektir, yani birkaç katsayıları vardır. Seyreklik her zaman bir zayıflık kaynağıdır ve bu bazen algoritmayı açmaya yeterlidir. Kriptografik algoritmalar için, çok katsayıları olan yoğun ilkel polinomları kullanmak çok daha iyidir. Yoğun polinomlar kullanılarak, özellikle anahtarın bir parçası olarak, çok daha kısa PrCcLOC kullanılabilir.

Yoğun ilkel polinomlar modulo 2 oluşturmak kolay değildir. Genel durumda, k dereceli ilkel polinomlar üretmek için 2 sayısının çarpanlara ayrılmasını bilmek gerekir. k-1.

Kendi başlarına, PgCsLOS iyi sözde rastgele dizi oluşturuculardır, ancak bazı istenmeyen rastgele olmayan (deterministik) özelliklere sahiptirler. Sıralı bitler doğrusaldır, bu da onları şifreleme için işe yaramaz hale getirir. n uzunluğundaki PgCsLOS için dahili durum, üretecin önceki n çıkış bitidir. Geri besleme şeması gizli tutulsa bile, yüksek verimli Berlekamp-Massey algoritması kullanılarak üretecin 2n çıkış bitinden belirlenebilir.

Ek olarak, bu dizinin ardışık bitleri kullanılarak üretilen büyük rastgele sayılar yüksek oranda ilişkilidir ve bazı uygulama türleri için hiç rastgele değildir. Buna rağmen, PgCsLOS genellikle sistemlerin ve şifreleme algoritmalarının bileşenleri olarak şifreleme algoritmaları oluşturmak için kullanılır.

1.2. RgCsLOS'a dayalı akış şifreleri hakkında

PrCsLOS tabanlı anahtar akışı oluşturucu tasarlamanın temel yaklaşımı basittir. İlk olarak, genellikle farklı uzunluklarda ve farklı geri besleme polinomlarında bir veya daha fazla PrCsLOS alınır. (Uzunluklar asal ve tüm geri besleme polinomları ilkel ise, sonuçta ortaya çıkan üreteç maksimum uzunluğa sahip olacaktır.) Anahtar, PrCcLOC kayıtlarının başlangıç ​​durumudur. Her yeni bit gerektiğinde, PrCsLOS kayıtlarını biraz kaydırın (bazen saatli olarak adlandırılır). Çıkış biti, PrCsLOC kayıtlarının bazı bitlerinin tercihen doğrusal olmayan bir fonksiyonudur. Bu işleve birleştirme işlevi denir ve bir bütün olarak üreteç birleşimsel üreteç olarak adlandırılır. (Çıkış biti tek bir PgCsLOS'un bir fonksiyonuysa, osilatöre filtre osilatörü denir.) Bu tür cihazların arkasındaki teorinin çoğu Selmer ve Neal Zierler tarafından geliştirilmiştir. Bir takım komplikasyonları tanıtabilirsiniz. Bazı jeneratörlerde, farklı PgCsLOS için farklı saat frekansları kullanılır, bazen bir jeneratörün frekansı diğerinin çıkışına bağlıdır. Bunların hepsi, saat kontrollü osilatörler olarak adlandırılan II. Dünya Savaşı öncesi şifre makinesi fikirlerinin elektronik versiyonlarıdır ( saat kontrollü jeneratörler ). Saat kontrolü, bir PgSsLOS'un çıktısının başka bir PgSsLOS'un saat hızını kontrol ettiği ileri beslemeli veya bir PgSsLOS'un çıktısının kendi saatini kontrol ettiği kapalı döngü olabilir. Bu oluşturucuların tümü, en azından teoride, yuvalama saldırılarına ve olası korelasyonlara karşı hassas olsa da, birçoğu hala güvenlidir.

Eskiden Cambridge'de saf matematik başkanı ve Bletchly Park'ta bir kriptanalist olan Ian Cassells, "kriptografi, matematik ve kafa karışıklığının bir karışımıdır ve karışıklık olmadan matematik size karşı kullanılabilir" dedi. Demek istediği, akış şifrelerinde, maksimum uzunluğu ve diğer özellikleri sağlamak için PrCcLOC gibi belirli matematiksel yapılara ihtiyaç duyulduğu, ancak birinin kaydın içeriğini almasını ve kırılmasını önlemek için bazı karmaşık doğrusal olmayan karışıklıkların getirilmesi gerektiğiydi. algoritma. Bu tavsiye blok algoritmalar için de geçerlidir.

Çoğu gerçek akış şifresi PrCsLOS'a dayanır. Elektroniğin ilk günlerinde bile inşa edilmeleri kolaydı. Bir kaydırma yazmacı bir dizi bitten başka bir şey değildir ve bir geri besleme dizisi bir dizi XOR kapısıdır. VLSI kullanırken bile, PrCsLOS'a dayalı bir akış şifresi, birkaç mantık kapısının yardımıyla önemli ölçüde güvenlik sağlar. PgCsLOS ile ilgili sorun, yazılım uygulamalarının çok verimsiz olmasıdır. Seyrek geri besleme polinomlarından kaçınmalısınız - korelasyon saldırılarını kolaylaştırırlar - ve yoğun geri besleme polinomları verimsizdir.

Kriptografinin bu dalı hızla büyümekte ve devlet tarafından ihtiyatlı hükümet kontrolü altındadır. NSA . Gelişmelerin çoğu sınıflandırılmıştır - bugün kullanılan birçok askeri şifreleme sistemi PrCsLOS'a dayanmaktadır. Gerçekten de, çoğu Cray bilgisayarı (Cray 1, Cray X-MP, Cray Y-MP), yaygın olarak "nüfus sayımı" olarak adlandırılan çok ilginç bir talimata sahiptir. Bir kayıttaki 1'lerin sayısını sayar ve hem iki ikili kelime arasındaki Hamming mesafesini verimli bir şekilde hesaplamak hem de PrCcLOS'un vektörleştirilmiş bir versiyonunu uygulamak için kullanılabilir. Bu talimat, NSA'nın kurallı talimatı olarak kabul edilir ve neredeyse tüm bilgisayar sözleşmelerinde görünür.

Öte yandan, şaşırtıcı derecede çok sayıda görünüşte karmaşık kaydırma yazmacı üreteci saldırıya uğradı. Ve elbette, NSA gibi askeri kriptanalitik kurumlar tarafından hacklenen bu tür jeneratörlerin sayısı daha da fazla.

1.3. Oluşturulan sözde rasgele sayı dizisinin doğrusal karmaşıklığı hakkında PrCsLOS

Akış şifrelerinin ayrıştırılması genellikle blok şifrelerden daha kolaydır. Örneğin, PgCsLOC tabanlı oluşturucuları analiz etmek için kullanılan önemli bir parametre, doğrusal karmaşıklık veya doğrusal aralıktır. Jeneratör çıkışını simüle edebilen en kısa PrCsLOS'un uzunluğu n olarak tanımlanır. Sonlu bir alan üzerinde sonlu bir otomat tarafından üretilen herhangi bir dizi, sonlu doğrusal karmaşıklığa sahiptir. Doğrusal karmaşıklık önemlidir, çünkü Berlekamp-Massey algoritması adı verilen basit bir algoritma ile, bu PrCcLOC anahtar akışının sadece 2n bitini inceleyerek belirlenebilir. İstenen PrCsLOS'u yeniden oluşturarak akış şifresini kırarsınız.

Bu fikir, alanlardan halkalara ve çıktı dizisinin tek karakterli bir alanda sayılar olarak ele alındığı durumlara kadar genişletilebilir. Daha fazla genişleme, bir dizinin uzadıkça doğrusal karmaşıklığını belirleyen bir doğrusal karmaşıklık profili kavramının tanıtılmasına yol açar. Küresel ve ikinci dereceden karmaşıklık kavramları da vardır. Her durumda, yüksek doğrusal karmaşıklığın mutlaka jeneratörün güvenliğini garanti etmediği, ancak düşük doğrusal karmaşıklığın yetersiz jeneratör güvenliğini gösterdiği unutulmamalıdır.

1.4 Oluşturulan sözde rasgele sayı dizisinin bağıntı bağımsızlığı hakkında PgCsLOS

Kriptograflar, bazı çıktı dizilerinin sonuçlarını doğrusal olmayan bir şekilde birleştirerek yüksek doğrusal karmaşıklık elde etmeye çalışırlar. Buradaki tehlike, bir veya daha fazla dahili çıktı dizisinin - genellikle sadece bireysel PrCsLOC'lerin çıktılarının - ortak bir anahtar akışı ile bağlanabilmesi ve lineer cebir kullanılarak ortaya çıkarılabilmesidir. Genellikle böyle bir hesaplaşmaya korelasyon hesaplaşması veya böl ve yönet hesaplaşması denir. Thomas Siegenthaler, korelasyon bağımsızlığının kesin olarak tanımlanabileceğini ve korelasyon bağımsızlığı ile doğrusal karmaşıklık arasında bir değiş tokuş olduğunu gösterdi.

Korelasyon açılışının ana fikri, jeneratörün çıkışı ile bileşenlerinden birinin çıkışı arasında bir miktar korelasyon bulmaktır. Daha sonra, çıktı dizisini gözlemleyerek, bu ara çıktı hakkında bilgi edinilebilir. Bu bilgi ve diğer korelasyonlar kullanılarak, jeneratör hacklenene kadar diğer ara çıktılar toplanabilir.

Hızlı korelasyon saldırıları gibi korelasyon saldırıları ve bunların varyasyonları, hesaplama karmaşıklığı ve verimlilik arasında bir denge sağlayarak birçok PgCsLOC tabanlı anahtar akışı oluşturucusuna karşı başarıyla kullanılmıştır.

1.5. Oluşturulan sözde rasgele sayı dizisini açmanın diğer yöntemleri hakkında PgCsLOS

Anahtar akışı oluşturucularını kırmanın başka yolları da vardır. Doğrusal tutarlılık testi, matris tekniğini kullanarak şifreleme anahtarının bir alt kümesini bulmaya çalışır. Ayrıca doğruluk konusunda bir orta-karşılaşma tutarlılığı saldırısı da vardır. Doğrusal sendrom algoritması, çıktı dizisinin bir parçasını doğrusal bir denklem olarak yazma yeteneğine dayanır. En iyi afin yaklaşım saldırısı ve türetilmiş dizi saldırısı vardır. Diferansiyel ve doğrusal kriptanaliz yöntemleri, akış şifrelerine de uygulanabilir.

2. PrCsLOS'un sözde rastgele dizi oluşturucu olarak yazılım uygulamasının açıklaması

2.1 Algoritmanın genelleştirilmiş şeması

2.2 Yazılım modüllerinin ve arayüzün tanımı

Aşağıdaki Şekil 3, program penceresini göstermektedir.

Şekil Program arayüzü

Menü aşağıdaki işlevlere sahiptir:

• Dosya->Raporu Kaydet

Bu fonksiyon, PrCsLOS'un başlangıç ​​durumunun, tap dizisinin, alınan sözde rastgele bit dizisinin periyodunun, dizinin kendisinin ve durum tablosunun yazıldığı bir rapor dosyası oluşturur. Dosya başarıyla kaydedildiyse, başarılı kaydetme ile ilgili bir mesaj görüntülenir (Şekil 4). Rapor için önerilen dosya uzantısı *. Txt.

Resim

• Dosya->Çıkış

Bu işlev, uygulamanın kapalı olmasını sağlar.

• Kaçış sırasını ayarla

Bu fonksiyon, kullanıcının ekran formunda işaretlediği hücrelerden değerleri okuyarak bir musluk dizisi oluşturur. Bundan sonra, bir musluk dizisinin oluşturulması hakkında kullanıcıyı bilgilendirir (Şekil 5). Dokunma sırası, hangi vardiya kaydı parmak arası terliklerinin geri bildirim alacağını belirler. XOR bir ofset biti oluşturmak için. Varsayılan olarak, ilk tetikleyiciden gelen geri bildirim her zaman açıktır, diğer bağlantıların yokluğunda, en az anlamlı bitin en önemli olanın konumuna değiştirilmesiyle sola bir kaydırma yapılacaktır.

Resim

• Başlangıç ​​değerini ayarla

Bu fonksiyon, pencereden kullanıcı tarafından girilen kaydın başlangıç ​​değerini okur. Düzenlemek 1 ve girilen değeri belirtilen koşullara göre kontrol eder: girilen dize boş değil (Şekil 6), girilen dize sekiz uzunlukta (8bit=1bayt, Şekil 7) girilen dize sadece sıfır içeriyor ve/veya (Şekil 8), girilen dize sıfır değildir (Şekil 9). Aksi takdirde hata mesajları görüntülenir, kullanıcının bunları düzeltmesi ve tekrar düğmeye basması gerekir. Başarılı bir kontrol durumunda "Initial" satırındaki durum tablosuna başlangıç ​​değeri yazılacak ve bir bildirim yapılacaktır (Şekil 10).

Resim

Resim

Resim

Resim

Resim

• Bir kayıt vardiyası gerçekleştirin

Bu işlev, bir kaydırma yazmacının çalışmasına öykünür. Sıralı olarak 256 kaydırma yaparak, her kaydırma, sözde rasgele dizinin bir çıkış bitini ve kaydın yeni bir durumunu üretir. Kaydın durumu ilk duruma eşit olur olmaz, periyot hesaplanır ve alanda görüntülenir. hafıza 1 sözde rastgele dizi aldı.

• Yardım-> Hakkında

Bu işlev, programın kısa bir açıklamasını ve talimatları görüntüler (Şekil 11).

Resim

• Yardım-> Yazar Hakkında

Bu fonksiyon, programın yazarı hakkında bilgi görüntüler (Şekil 12).

Resim

2.3 Kullanım kılavuzu

1. İlk önce kaydın başlangıç ​​durumunu ayarlayın. Sekiz ikili karakter içermelidir. Aksi takdirde bir hata mesajı görüntülenecek ve girilen değeri düzeltmeniz gerekecektir. "Başlangıç ​​Değerini Ayarla" menü öğesine basın.
2. Ardından, kayıt geri bildirimleri için onay kutularını işaretleyin (Sıraya dokunun). "Tap Sırasını Ayarla" menü öğesine basın.
3. Ardından, "Kayıt Vardiyası" menü öğesini tıklayın. Bunu yapmadan önce 1. ve 2. adımları tamamladığınızdan emin olun, aksi takdirde bir yazılım hatası oluşur.
4. Sonuçları aldıktan sonra, "Dosya->Raporu Kaydet" menü öğesine tıklayarak bunları kaydedebilirsiniz. Bunu yapmadan önce 1-3 arasındaki adımları tamamladığınızdan emin olun, aksi takdirde bir yazılım hatası oluşur.
5. Yardım almak için "Dosya->Hakkında", "Dosya->Yazar Hakkında" menü öğelerine tıklayın.
6. Kayıt sırasının diğer değerleriyle ve kaydın ilk durumuyla birlikte kaydın çalışmasını görmek için, diğer parametreleri girerek 1-3 adımlarındaki adımları sırayla tekrarlayın.

ÇÖZÜM

Bu yazıda, RgCsLOS, sözde rasgele sayı üreteçleri olarak kabul edildi. Program, doğrusal geri beslemeli vardiyalı yazmaçların çalışma prensiplerinin görsel bir gösterimi olarak hizmet edebilir. XOR . Üzerinde, sözde rastgele bir bit dizisi oluşturma ilkesini, kaydın ilk değeri ile sözde rastgele dizinin değeri arasındaki ilişkiyi, kademe dizisini ve noktayı inceleyebilirsiniz. Ortaya çıkan sözde rastgele gama, başka bir yazılım uygulamasında kullanılabilir (örneğin, bir gama şifresinin bir yazılım uygulaması).

Bugüne kadar, bu kayıtlar bağımsız sözde rasgele sayı üreteçleri olarak kullanılmamaktadır, ancak daha karmaşık cihazların bir parçasıdır. Bununla birlikte, matematikte yeni yönler açan onlardı (sonlu alanlarda ilkel polinomları, sözde rasgele sayı üreteçlerini kırmak için matematiksel yöntemler). Jeneratörlerin RgCsLOS üzerinde çalışma prensiplerini bilmeden, daha karmaşık cihazların çalışmasını anlamak mümkün değildir. Basit donanım uygulamaları nedeniyle, teknolojide yaygın olarak kullanılırlar. PrCsOS araştırması, bu tür kayıtlara dayalı yeni şifrelerin - blok ve akış - ortaya çıkmasına yol açtı (kayan permütasyon şifresi, DES vb.; EDS, karma fonksiyonlar).

Genel olarak, bu alandaki araştırmalar, kriptografi ve kriptanalistlerin, bilgisayarların ve cihazların gelişimini ciddi şekilde teşvik etti ve ayrıca bir dizi başka yararlı işlevin (örneğin, döngüsel kodların düzeltilmesi) uygulanmasını mümkün kıldı.

KAYNAKÇA

1. Schneier Bruce. Uygulamalı kriptografi. C dilinde protokoller, algoritmalar, kaynak metinler. - E.: Zafer, 2002
2. Babash A.V. Modern bilgi güvenliğinin kriptografik ve otomat teorik yönleri. Cilt 1 - M.: Ed. Merkez EAOI, 2009. - 414 s.
3. E.S. Selmer. Monografi: "Sonlu bir alanda doğrusal özyineleme". Bergen Üniversitesi, Norveç, 1966.
4. N. Zierler ve J. Brillhart. "İlkel Trinomials Modulo 2 Üzerine", Journal of Information and Control, Cilt 13 Sayı 6 Aralık 1968, sayfa 541-544.
5. K.Kh. Meyer ve W.L. Tuchman. "Sözde rastgele kodlar kırılabilir," Electronic Design dergisi, no. 23 Kasım 1972.
6. J.L. Massey. "Vardiya yazmaçlarının genelleştirilmesi ve Bose-Chowdhury-Hokvingham kodunun kodunun çözülmesi", Bilgi Teorisi Üzerine IEEE İşlemleri, v. IT-15, n . 1 Ocak 1969, s. 122-127.
7. S.Ü. Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (Aigean Park Press, 1982 tarafından yeniden basılmıştır).

Ek A

Bazı ilkel polinomların tablosu modulo 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

İlk durum girişi (IS)

giriş doğrulama

Bir hata mesajı verme

Dokunma sırasını ayarlama

IP'yi durum tablosuna kaydetme

ben kaydet -th durum kaydı ve durum tablosuna çıkış biti

IS==Mevcut durum

Sonuçları kaydetme

Sözde rastgele dizi çıkışı

çıkış

başlatmak

Evet

Evet

Değil

Tanım

Doğrusal bir geri besleme kaydırma kaydı iki bölümden oluşur: kaydırma kaydının kendisi ve geri besleme işlevi. Bir kayıt, bitlerden oluşur ve uzunluğu bu bitlerin sayısıdır. Bir bit alınacağı zaman, kayıttaki tüm bitler bir konum sağa kaydırılır. En soldaki yeni bit, kalan bitlerin işlevi tarafından belirlenir. Kayıt çıktısı bir, genellikle en az anlamlı bittir. Kaydırmalı yazmaç periyodu, ortaya çıkan dizinin tekrar etmeye başlamadan önceki uzunluğudur.

LFSR için geri besleme işlevi, bazı kayıt bitlerinin modulo 2 (xor) toplamıdır. kıvrımlar.

Doğrusal uzunluk geri besleme kaydırmalı yazmacı, her biri bir bit depolayabilen ve bir giriş ve bir çıkışa sahip olan numaralı hücrelerden ve ayrıca veri ofsetini kontrol eden bir saat sinyalinden oluşur. Her bir zaman biriminde 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:

Özellikleri

LFSR tarafından üretilen dizinin özellikleri, özelliklerle yakından ilişkilidir. ilişkili polinom sahanın üzerinde. 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.

periyodiklik

Kayıt defterinin sıfır olmayan farklı durumları olduğundan, LFSR tarafından sıfır olmayan herhangi bir başlangıç ​​durumu için oluşturulan dizinin periyodu 'u geçmez. Bu durumda, periyot ilişkili polinoma bağlıdır:

İlkel polinomların özellikleri

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:

Tanım

Doğrusal karmaşıklık Sonsuz bir ikili diziye sayı denir ve aşağıdaki gibi tanımlanır:

Doğrusal karmaşıklık Son ikili diziye, ilk üyeleri olan bir dizi oluşturan en kısa LFSR'nin uzunluğuna eşit olan sayı 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 (genellikle 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.

Not

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 miktar korelasyon bulmaktır. Daha sonra çıkış sırası gözlemlenerek bu ara çıkış hakkında bilgi alınabilir. Bu bilgileri ve diğer korelasyonları kullanarak, jeneratör hacklenene kadar diğer ara çıkış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

İ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:

Adım numarası	Durum	Bit oluşturuldu
0		-
1		1
2		0
3		0
4		1
5		1
6		1
7		0

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ı koşuluyla, bu, gözle görülür 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 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.

Notlar:

• İlk olarak verilen Fibonacci konfigürasyonunun ve burada verilen Galois konfigürasyonunun aynı dizileri (2³²-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.

LFSR'deki jeneratör örnekleri

dur-kalk jeneratörler

Dur-kalk 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, sadece 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 jeneratörünün 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-2 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, o zaman k LFSR'den oluşan bir sistemin lineer karmaşıklığı şuna eşittir:

Bu fikir basittir ve 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ı çözmeye ç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 yazmacından oluşur. Kayıtların çıkışlarındaki birim sayısı yarıdan fazla ise üreteç bir birim üretir. Çıkışlardaki sıfır sayısı yarıdan fazlaysa jeneratör 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ı göreceli olarak 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 doğrusal 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 jeneratör türleri

Bunları kısaca açıklayalım

Kendi kendini yok eden jeneratörler

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 beslemeli kaydırma yazmacından 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ş: saat devresinde, 0 veya 1 için bir kontrol olarak, giriş çıkış sinyalinin kendisini değil, doğrusal geri beslemeli kaydırma yazmacının belirli bitlerinin XOR'sini alır. Ne yazık ki, bu tür bir jeneratör güvenli değildir.