Döngüsel artıklık denetimi

Döngüsel artıklık denetimi (CRC: Cyclic Redundancy Check), çoğunlukla sayısal şebekelerde ve depolama cihazlarında kullanılan ve ham veride yapılan hatalı değişimleri algılayan, uygulaması kolay ve güvenliği güçlü bir hata bulma yöntemidir.
CRC'ler, denetim (veri doğrulama) değerinde (enformasyon eklenmeden gönderilen) bir artıklık ve döngüsel kodların temelini oluşturan bir algoritma olduğu için bu adla adlandırılır. İkili donanımlarda uygulaması basit, matematiksel analizi kolay ve bilhassa iletim kanallarında gürültünün neden olduğu genel hataları algılamada iyi olduğu için CRC'lerin kullanımı yaygındır. Çünkü denetim değeri sabit bir uzunluğa sahiptir. Bunu oluşturan fonksiyon nadiren bir hash fonksiyonu olarak kullanılır.

Açıklama

CRC'ler ileri hata düzeltme yöntemindeki döngüsel kodun temelini oluştururlar. Sabit uzunlukta bir denetleme değeri ekleyerek mesajların kodunu çözen sistematik döngüsel kodları kullanarak, telekomünikasyon şebekelerinde hata düzeltme ilk olarak 1961'de W. Wesley Peterson tarafından yapılmıştır. Döngüsel kodların yalnızca uygulaması kolay değil, aynı zamanda özellikle patlama hatasının düzeltilmesi için çok idealdir. Patlama hataları, manyetik ve optik veri depolama cihazlarındaki kanallar gibi çoğu iletişim kanalında yaygın bulunan hatalardır. Bir n bitlik CRC'nin tipik uygulaması, rastgele uzunluklu bir veri bloğunun, n bitten uzun olmayan herhangi tek bir patlama hatasını algılamasıdır. Patlama hatalarının tümünün uzunluğu 1 - 2⁻ⁿ ifadesinin bir kesri olarak algılanır. Gönderici her çerçeveye n bitlik FCS (Frame Check Squence) dizi ekler. CRC veri iletiminde kullanılan en yaygın hata denetimi yöntemidir. Az bir ek bilgi ile daha fazla hata tespiti sağlanır. Veri iletirken ya da saklarken ilettiğimiz/sakladığımız veri ile alınan verinin aynı olduğundan emin olmamız gerekir. Veriler iletim hattında bozunuma uğrarsa bunun fark edilmesi ve verilerin yeniden iletilmesi gerekir. CRC, bu amaçla kullanılır.
Bir CRC kodunu belirlemek için, sözde polinom kod tanımlamak gerekir. Bu polinomdaki, bölme algoritmasında, bölünen, bölen, bölüm ve kalan bulunur. Burada önemli olan polinom katsayıları, sonlu alanın aritmetiğine uygun olarak hesaplanmasıdır. Böylece toplama işlemi, (dijitler (rakamlar) arasında taşıma olmayan) bitsel paralelliği daima gerçekleştirebilir. Kalanın uzunluğu, polinom kod uzunluğundan daima daha küçüktür. Böylece sonucun hangi uzunlukta olacağı belirlenir.
Pratikte, kullanılan tüm CRC'ler, bilgisayar mimarisi ile eşleşen, 0 ve 1 olarak adlandırılan iki elemanlı GF(2) sonlu alanı ile ilgilidir.
En basit hata düzeltme sistemi, eşlik biti, 1 bitlik CRC'nin durumu ile ilgilidir. CRC-1 olarak adlandırılan ve iki terimli olan x + 1 polinom kodunu kullanır.

CRC'ler ve veri tutarlılığı

CRC'ler, özellikle iletişim kanallarında sıkça rastlanan hata türlerine karşı koruma sağlamak amacıyla tasarlanır. Teslim edilen mesajların tutarlılığını hızlı ve güvenli biçimde gerçekleştirebilirler. Fakat veride istenerek yapılan değişimlere karşı uygun değillerdir.
Birincisi, kimlik denetimi olmadığından dolayı saldırgan mesajı değiştirebilir ve bunun fark edilmeyecek şekilde CRC'yi tekrar hesaplayabilir. Veri yan yana saklandığında CRC'ler ve kriptografik hash fonksiyonları veride istenerek yapılan değişimlere karşı birbirlerini koruyamazlar. Bu tür saldırılara karşı korunmak için, (temelinde kriptografik özet fonksiyonu bulunan) mesaj doğrulama kodu veya dijital imza gibi kriptografik kimlik denetimi mekanizmaları kullanılmalıdır.
İkincisi, kriptografik özet fonksiyonu aksine, CRC kolay terslenebilir fonksiyondur. Bu da dijital imzaların kullanılmasını imkansız kılar.
Üçüncüsü, CRC aşağıdaki denkleme sahip bir doğrusal fonksiyondur. \operatorname{crc}(x \oplus y \oplus z) = \operatorname{crc}(x) \oplus \operatorname{crc}(y) \oplus \operatorname{crc}(z);
Sonuçta CRC bir dizi şifresi (veya blok şifreleme kipi) ile şifrelenmiş olsa bile, şifreleme anahtarını bilmeye gerek kalmaksızın hem mesaj hem de ilgili CRC ele geçirilebilir. Bu, WEP iletişim kuralının bilenen bir kusurudur.

CRC hesaplama

n bitlik ikili CRC'yi hesaplamak için, bir satırdaki girişi ifade eden bitler ve (polinom olarak adlandırılan) CRC'nin bölenini ifade eden (n+1) bitlik dizinin konumu satırın sol alt köşesindedir.

İkili sayı sistemine örnek

Aşağıdaki örnekte 14 bitlik mesajın kodunu 3 bitlik CRC ve x³+x+1 polinomu ile çözeceğiz. 3.dereceden bir polinomdur ve dört katsayıya sahiptir. Bu polinom ikili sayı sisteminde katsayılarla şöyle yazılır; 1x³+0x²+1x+1. Bu durumda katsayılar; 1, 0, 1 ve 1'dir. Hesaplama sonucu 3 bit uzunluğundadır.
Mesaj şu kod çözülerek başlar:

11010011101100
CRC'nin n bit uzunluğuna uygun olarak ilk önce sıfırlar eklenir. 3 bitlik bir CRC'yi hesaplamak için ilk hesaplama adımı şöyledir:

11010011101100 000 <--- 3 bit girişin sağına eklenir
1011               <--- bölen (4 bit) = x³+x+1
------------------
01100011101100 000 <--- sonuç
Her bir adımda bitlere yukarıdaki bölen doğrudan etki eder. Bu yineleme için sonuç, yukarıdaki bitlere sahip bitsel XOR bölen polinomudur. Yukarıda olmayan bitler için bölen basitçe doğrudan bu adımın altına kopyalanır. Bölen sağa bir bit kaydırılır. Bölen, giriş satırının en sağ köşesine ulaşıncaya kadar bu işlem tekrarlanır. İşlemin tamamı şöyledir:

11010011101100 000 <--- 3 bit girişin sağına eklenir
1011               <--- bölen
01100011101100 000 <--- sonuç (ilk dört bitin, altındaki bölen ile aynı ve XOR olduğuna dikkat edin, bitlerin geri kalanı değiştirilmedi)
 1011              <--- bölen ...
00111011101100 000
  1011
00010111101100 000
   1011
00000001101100 000 <--- bölümdeki sonraki 1 ile hizalanması için bölenin taşındığına dikkat edin (çünkü burada bölüm sıfır idi)
       1011             (yani her yinelemede yalnızca bir bit kaydırma gereksizdir)
00000000110100 000
        1011
00000000011000 000
         1011
00000000001110 000
          1011
00000000000101 000 
           101 1
-----------------
00000000000000 100 <--- kalan (3 bit). Bölme algoritması burada durduruldu. Çünkü bölüm sıfıra eşittir.
Bölenin en solundaki bit 1 olduğundan dolayı her bir girişte en soldaki bölüm biti sıfırlanır. Yalnızca giriş satırının (bölümün) en sağındaki n bit sıfırlanamadığında bu işlem sonlandırılır. n bit, bölme adımındaki kalandır. Bunlar aynı zamanda CRC fonksiyonunun değeri olur.
Alınan bir mesajın geçerliliği, yukarıdaki hesaplama tekrar gerçekleştirilerek kolayca doğrulanabilir. Burada sıfırlar yerine denetleme değeri konur. Eğer hata algılanmazsa kalan sıfıra eşitlenir.

11010011101100 100 <--- denetleme değerli giriş
1011               <--- bölen
01100011101100 100 <--- sonuç
 1011              <--- bölen ...
00111011101100 100

......
  
00000000001110 100
          1011
00000000000101 100 
           101 1
------------------
                 0 <--- kalan

Karışık örnek

11100101011 bit dizisini içeren CRC bitini hesaplayalım
1-) P(x) =x¹⁰+X⁹+X⁸+X⁵+X³+X+1
2-)Üreteç fonksiyon: G(x)= x⁴+x²+x+1 => Xᴾ = x⁴ olur.

    x⁴.P(x)= x⁴(x¹⁰+X⁹+X⁸+X⁵+X³+X+1)
           = x¹⁴+x¹³+X¹²+X⁹+X⁷+X⁵+X⁴
3-) x⁴.P(x)’i üreteç fonksiyona bölme

  
    Xᴾ.P(x)= x¹⁴+x¹³+X¹²+X⁹+X⁷+X⁵+X⁴     
       G(x)= x⁴+x²+x+1   
       Q(x)= x¹⁰+x⁹+X³
       R(x)= X³
4-) Q(x).G(x)= Xᴾ.P(x)+ R(x)

           =  x¹⁴+x¹³+X¹²+X⁹+X⁷+X⁵+X⁴+X³
           =(11100101011 - 1000)  
               P(x)     - CRC biti

CRC matematiği

Bu bölme benzeri işlemde, iyi hata düzeltme özelliklerini garanti altına almak için nasıl bir bölen seçilmesi gerektiğinde matematik analizin önemi açığa çıkar. Bu analizde, bit dizisindeki rakamlar, x—değişkenine sahip bir polinomun katsayılarıdır. Bunlar, bilinen sayılar yerine, daha çok GF(2) sonlu alanının elemanlarıdır. İkili polinomlar kümesi, bir matematik halkasıdır.