LFSR (Linear Feedback Shift Register)

Yazan :Şadi Evren ŞEKER

Bilgisayar bilimlerinde, özellikle şifreleme ve veri güvenliği konularında doğrusal ahenk sınıfı (linear congruence ) üretmek için kullanılan yöntemin ismidir. İngilizcedeki linear feedback shift register terimini Türkçede doğrusal geri beslemeli kaydırma yazmacı olarak tercüme etmek mümkündür. Bu yöntem genellikle ikili tabandaki sayılar üzerinden çalışır ve sistem iki adımdan oluşur :

1. Mevcut sayılar üzerinden yeni bir sayı üreten fonksiyonun çalışması
2. Mevcut sayıların kaydırılması (shift) ve açılan boşluğa bir önceki adımda elde edilen fonksiyon sonucunun yerleştirilmesi.
3. 1. Adımdan tekrar devam edilerek bir sonraki sayının üretilmesi.

Yukarıdaki bu adımları bir örnek üzerinden anlamaya çalışalım. Örneğin sayılarımız 4 bitten oluşsun.

Kullanacağımız fonksiyonu F = C ⊕ D olarak tanımlı olsun.

Bu durumda her adımda aşağıdaki şekilde kaydırma işlemi yapılacaktır:

F = C ⊕ D

D = C

C = B

B = A

A = F

Görüldüğü üzere her adımda bütün bitler birer kere sağa kaydırılmış açılan boşluğa, bir önceki adımda olan C ve D bitlerinin değerleri yerleştirilmiştir.

Yukarıdaki bu çizimden de anlaşılacağı üzere 4 bitlik bilginin son 2 biti fonksiyona sokulmuş (buradaki fonksiyon yahut fonksiyonu (özel veya (exclusive or)) olarak tanımlıdır) ve çıkan sonuç, kaydırma işleminden doğan boşluğa konulmuştur.

Yukarıdaki bu örneği aşağıdaki örnek sayılar için çalıştıralım. Örneğin LFSR’yi 1111 bilgisi ile besleyerek başlayalım:

1111 (son iki bit 1⊕1 = 0)

0111 (başa 0 eklendi yine son iki bit 1⊕1 = 0 )

0011 (başa yine 0 eklendi yine son iki bit 1⊕1 = 0)

0001 (başa yine 0 eklendi son iki bit 0⊕1 = 1)

1000 (başa 1 eklendi son iki bit 0⊕0 = 0)

0100

0010

1001

1100

0110

1011

0101

1010

1101

1110

1111

Yukarıdaki son adımda, başlangıçta yazmacı (register) beslerken kullandığımız ilk değeri geri elde ettik. Bu anlamda yukarıdaki sayılardan da anlaşılacağı üzere elde edilen sayılar dairesel bir grup oluşturur ( cyclic group) ve şifreleme algoritmalarından bu tip bir gruba ihtiyaç duyan sistemlerde kullanılabilir.

Yukarıdaki bu sayıların üzerinde tanımlı olan f fonksiyonun tasarımına göre güvenlik artırımı da söz konusudur.

Örneğin yukarıda verilen F fonksiyonu tasarımının bir eksik yanı bu fonksiyon sayesinde üretilen sayılarda ileri ve geri hareketin kolay olmasıdır.

F fonksiyonunda yapılacak değişikliklerle bu durum düzeltilebilir.

Öncelikle yukarıdaki F fonksiyonundaki sayılarda geri gidilebileceğini görelim:

Yukarıdaki sayılardan rast gele seçilen 1011 sayısını ele alalım.

Bu sayıdan bir önceki sayı için 011X gibi bir sayı olduğunu biliyoruz. Buradaki X değerinin hemen yanında buluna 1 değeri ile yahut işlemine sokulduğunu ve çıkan sonucun da 1 olduğunu biliyoruz. O halde denklemimiz :

1 ⊕ X = 1

Halini alır ki bu durumu veren tek X değeri 0’dır.

Gerçekten de yukarıdaki örnekte 1011 sayısından önce 0110 sayısı gelmektedir.

Görüldüğü üzere f fonksiyonun tasarımına bağlı olarak ileri gitmek kolay olurken geri gitmenin de mümkün olduğu durumlar ortaya çıkabilir.

Örneğimizi biraz değiştirerek 7 bitlik bir mesajdaki son iki bitin yahut sonucunun tekrarlı olarak baştaki 2 bit’e ekleneceğini varsayalım.

Bu durumda sayımızdaki kaydırma işlemini aşağıdaki şekilde tasarlayalım:

Yukarıdaki 7 bit için aşağıdaki kaydırma işlemini tasarlıyoruz:

F = Q ⊕ R

R = P

Q = D

P = C

D = B

C = A

B = F

A = A

Yukarıdaki bu LFSR tasarımını mantıksal bir devre olarak çizecek olursak aşağıdaki sonucu elde ederiz:

Örnek sayılar üzerinden çalışmasını görelim. Bunun için yine başlangıç olarak 1111111 gibi bir girdi ile besleyelim.

1111111 ( son iki bit 11 olduğu için QÄR = 1⊕1 = 0)

0011111 ( sayılar iki kaydırıldı ve ilk iki bite bir önceki adımda bulunan 0 konuldu)

0000111 (sayılar iki kaydırıldı ve ilk iki bite bir önceki adımda bulunan 0 konuldu)

0000001 (sayılar iki kaydırıldı ve ilk iki bite bir önceki adımda bulunan 0 konuldu)

1100000 ( bir önceki adımdaki son iki bit 0 ve 1 olduğu için 0⊕1 = 1 sonucu bulunup ilk iki bite bunlar yerleştirildi)

0011000

0000110

1100001

1111000

0011110

1100111

0011001

1100110

1111001

1111110

1111111

Görüldüğü üzere son adımda yine başlangıç değeri elde edildi ve böylelikle daire tamamlanmış oldu.

Buradaki yeni örneğin bir önceki örnekten en büyük farkı sayılar arasında iler hareket etmek mümkünken geri gidilmesinin güçlüğüdür.

Örneğin yukarıdaki sayılardan birsini rast gele seçelim ve bu iddiayı inceleyelim. Sayımı 0011110 olsun. Bu sayının serideki bir sonraki değerini hesaplamak basittir. Son iki bit yahut işlemine sokulup sayılar iki kaydırılacak ve açılan boşluğa yahut (xor) sonucu yazılacaktır. Bu durumda değer 1100111 olacaktır.

Ancak bu sayıdan (yani 0011110 sayısından) bir önceki sayının, seride hangi sayı olduğunu nasıl bulabiliriz?

Bunun için ilk iki bitin aslında bir önceki adımdaki yahut(xor) işleminde çıkan sonuç olduğunu söyleyerek bir önceki adımda bulunan sayının 11110XY gibi bir sayı olduğunu ve burada

X ⊕ Y = 0

Olduğunu söyleyebiliriz.

Şimdi sorumuz acaba X ve Y değerleri nedir? Sonuç 0 olduğu için ya X=1, Y=1 yada X=0 ve Y=0 doğru olacaktır.

Ne yazık ki hangisi olduğu söylenemez.

Görüldüğü üzere LFSR kullanılarak elde edilen serilere özel F fonksiyonları ile amaca yönelik olarak ek özellikler kazandırılabilir.