FBE- Telekomünikasyon Mühendisliği Lisansüstü Programı - Doktora
Bu koleksiyon için kalıcı URI
Gözat
Yazar "Apohan, A. Murat" ile FBE- Telekomünikasyon Mühendisliği Lisansüstü Programı - Doktora'a göz atma
Sayfa başına sonuç
Sıralama Seçenekleri
-
ÖgeA New Cryptanalsis Method Of Cellular Automata Based Encryption Systems(Fen Bilimleri Enstitüsü, 2000) Apohan, A. Murat ; Çelebi, M. Ertuğrul ; 100793 ; Telekomünikasyon Mühendisliği ; Telecommunication EngineeringŞifreleme haberleşme ağlarıyla gönderilen veya elektronik ortamlarda depolanan bilgileri korumayla ilgilenen bilimsel bir disiplindir. Aynı zamanda mesajın orijinalliğini kontrol etmek, dijital imza üretmek, para transferi için elektronik kimlik oluşturmak, kredi kartı bilgileri göndermek ve programlan virüslerden korumak için kullanılır. Şifrelemedeki temel problem açık mesajları şifreli mesajlara dönüştürecek ve şifre analize (şifrelenmiş mesaja ulaşarak açık mesajı elde etme tekniği) dayanabilecek bir yöntem geliştirmektir. Şifreleme dünyası şifreleme algoritmaları için bir güvenlik ölçütü araya gelmiştir. Claude Shannon ilk kez şifreleme sistemleri için bu amaçla bir matematiksel model vermiştir. Şifre analiz, anahtara sahip olmadan açık mesaja ulaşmak için yapılan çalışmaların tümüdür. Genel kabul şifre analizcinin kullanılan şifreleme sisteminin tüm detaylarını anahtar hariç bildiği şeklindedir. Bu Kerckhoff kuralı olarak bilinmektedir. Eğer şifre analizci kullanılan şifre sistemini bilmiyor ise işi güçleşecektir. Ancak şifreleme sisteminin güvenliği buna dayandırılamaz. Böylece şifreleme sistemleri Kerckhoff kuralı esas alınarak tasarlanır. Yapılabilecek saldırılar şu şekilde sınıflanabilir: 1. Şifreli metin saldırısı (Ciphertext Only- Attack): Şifre analizci sadece şifreli metine sahiptir. 2. Bilinen açık metin saldırısı (Known-Plaintext Attack): Şifre analizci aynı anahtar için bazı açık ve şifreli metin çiftlerini bilir. 3. Seçilmiş açık metin saldırısı (Chosen-Plaintext Attack): Şifre analizci geçici olarak şifreleme cihazına erişebilir ve kendi seçmiş olduğu bazı açık metinler için şifrelenmiş metinler elde edebilir. 4. Seçilmiş şifreli metin saldırısı (Chosen-Ciphertext Attack): Şifre analizci geçici olarak şifre çözme cihazına erişebilir ve seçtiği bazı şifrelenmiş metinler için açık metinler elde edebilir. İş yükü (work factor), bir algoritmayı kırmak için gereken bütün analizlerin bir ölçütüdür. İş yükünü tanımlamak için belirlenmiş bir kurallar kümesi yoktur. Genel olarak ölçüt şifre analiz için geçen süre ve gerekli matematiksel işlem adedi veya gerekli donanım ve yazılımların miktarı ile verilebilir. Gerekli olan para miktarı da genel bir karşılaştırma ölçütü olarak alınabilir XV Eksiksiz şifre analiz (exhaustive search) metodunda, anahtar veya açık mesaj mümkün bütün çözümler tek tek denenerek bulunur. Elde şifrelenmiş ve buna karşı düşen açık mesaj çifti varsa, mümkün bütün anahtarlar şifrelenmiş mesaj eldeki doğru mesajı verinceye kadar denenerek doğru anahtar bulunur. Elde sadece şifrelenmiş mesaj varsa, anlamlı bir mesaja ulaşıncaya kadar bütün anahtarlar sırasıyla denenerek aday anahtar bulunur. Eksiksiz şifre analizi için iş yükü deneme sayısıyla doğrudan orantılıdır. Bu tür saldın yapılacak deneme sayısı çok fazla yapılarak engellenir. Bir diğer tür şifre analizi ise şifre algoritmasından faydalanarak bazı parametrelere göre açık mesajı veya anahtarı (veya anahtarın bir kısmını) veren matematiksel denklemlerin çıkarılmasıdır. Bunu önlemek için bu tür denklemler oluşturulduğunda bunların çok karmaşık olmasını sağlayacak şekilde şifre algoritması tasarlanmakta, böylece algoritmanın analiz edilmesi pratikte mümkün olmamaktadır. Walsh dönüşümü ve fonksiyonları, işaret işleme, görüntü işleme, haberleşme, lojik tasarım ve analiz konularında geniş bir biçimde kullanılmıştır. Daha sonraları bu uygulama alanlarına şifreleme de katılmış, ilk kez Rueppel tarafından DES isimli şifreleme algoritmasının S-kutulanndan ikincisine yaklaşık bir fonksiyon bulmak amacıyla kullanılmıştır. Bu tezde bir şifre analiz aracı olarak kullanılan en iyi doğrusal yaklaşığın (best affine approximation - BAA) tanımı Walsh fonksiyonları esas alınarak aşağıda verilen şekilde hesaplanmaktadır. Walsh fonksiyonu, iki vektör w, z e GF(2") (GF Galois field) için ö(w,z) = (-l)wz, w z = w1zl@---®wnzn, şeklinde tanımlanır (© işlemi modulo 2 toplamayı göstermektedir). Her hangi bir boole fonksiyonunun Walsh dönüşümü S(/)(w) = 2~" ^(-l)fiz) Q(w,z) şeklinde zeGF(2)" ifade edilebilir ve bu gösterilim kullanılarak bu boole fonksiyonuna en yakın affine (doğrusal ve doğrusal fonksiyonların komplementlerinin oluşturduğu küme) fonksiyon, Pf(wx) =- +- S(f)(w), w,zeGF(2)" şeklinde bulunabilir. Bu tezde de affine yaklaşıklık, CA yerel fonksiyonuna (local function) doğrusal yaklaşıklık elde etmek için kullanılmıştır. Hücresel otomata (Cellular automata-CA), ilk kez Stanislav Ulam'in önerileri ardından, karmaşık sistemlerin davranışlarım modellemek için, John Von Neuman tarafından ortaya atılmıştır. Bir boyutlu CA, doğrusal bir dizi şeklinde birbirine bağlanmış n hücreden oluşmuş olup her hücre 0 veya 1 değerini alır. q=2r+l değişkenli bir boole fonksiyonu olan _/(*), hücre değerlerini günceller (şekil 1). Her hücre değeri paralel ve senkron olarak, xt+1 = f(xt ) fonksiyonu ile de ifade edildiği gibi, t=l,2,...,n değerleri için ayrık zamanda güncellenir. Sınır değerleri, indeksin mod n'e göre hesaplanması ile elde edilir, yani, doğrusal olarak birbirine bağlanmış bu dizi, aslmda, dairesel bir kaydedicidir (register), r, fix) fonksiyonun çapı olarak adlandırılmaktadır. Her hangi bir hücrenin yeni değeri hesaplanırken o hücrenin kendi değeri ve r komşuluğunda olan q hücrenin değeri kullanılır. q=3 için CA aşağıdaki şekilde gösterilmiştir. Mümkün n hücre olması ve her birinin 0 veya 1 değeri alabilmesi nedeni ile mümkün 2" tane durum vektörü vardır. S*, k. andaki durum vektörünü göstersin. Bu durumda CA, fc=0'da Sq başlangıç vektöründen başlayarak k = 1, 2, 3, için Sı, S2, S3, xvı sk Sk+ı Şekil 1: 1 boyutlu, 1 yançaplı fonksiyonlu hücresel otomata. vektörlerini izleyecektir. Bu sistemin zaman içindeki iterasyonu doğal olarak bir çevrime girecektir, Sk=Sk+p- Burada, P periyodu göstermekte olup, f[x) fonksiyonunun, başlangıç koşulunun ve hücre sayısının bir fonksiyonudur, fix) fonksiyonuna yerel fonksiyon (local map), S* durumunu (state) Sk+ı durumuna götüren fonksiyona genel fonksiyon (global map) adı verilir. Açıktır ki, CA'nın genel fonksiyonu 1-1 ve üzerine (onto) ise, CA'nın tersi vardır, dolayısıyla, ICA'dır. CA kullanılarak oluşturulmuş üreteçlerin şifreleme amacı ile kullanılabilmesi için başlangıç değerinin (başlangıç durum vektörü So) verilen durum vektörlerinden bulunması güç olmalıdır. Wolfram, bu problemin NP-tam (nondeterministic polynomial) sınıfından olduğunu ve şu ana kadar n'ye üstel (exponansiyel) olarak bağlı olan algoritmalardan daha iyi bir algoritma bulunamadığını göstermiştir.30 numaralı kurala sahip CA rasgele sayı üreteci olarak ilk kez Wolfram tarafından önerilmiştir. Bu sistem yardımı ile üretilen durum vektörlerinin, rasgelelik özelliklerini sağladığı görülmüştür. Önerilen Zikzak Algoritmasının Tanımlanması: Önerilen algoritma yaptığı iterasyonlar nedeniyle zikzak algoritması olarak isimlendirilmiştir. Zikzak algoritması, ^-değişkenli fix) fonksiyonunun en iyi doğrusal yaklaşıklığını (Best Affine Approximation-BAA) kullanmaktadır. j{x) fonksiyonunun BAA'sı olan g-değişkenli affine g(x) fonksiyonu, boole fonksiyonlarının spektral analiz araçları kullanılarak elde edilebilir. Bir başka deyişle, g(x), f[x) ile doğrusal fonksiyonlar arasındaki en düşük Hamming uzaklığına sahip olan affine fonksiyondur. İki fonksiyon arasındaki Hamming uzaklığı bu tezde şöyle verilmiştir: Fonksiyonların mümkün bütün girişlerinin, xeZg, bu fonksiyonlara uygulanmasıyla elde edilen 29 uzunluklu vektörlerin Hamming uzaklığına, fonksiyonların Hamming uzaklığı denir. xvıı Önerilen zikzak algoritması şekil 2 yardımıyla şöyle açıklanabilir. Durum vektörü Sit+ı, fix) fonksiyonunun 5* vektörüne uygulanması sonucunda oluşturulmuştur. Amaç S* vektörünü bulmaktır, ancak, fix) genel halde doğrusal olmayan bir fonksiyon olup, tüm çözümleri tek tek denemek dışmda analitik bir çözüm bilinmemektedir. Algoritmada ilk olarak fix) yerine, fix)'in en iyi doğrusal yaklaşığı olan g(x) doğrusal fonksiyonu kullanılarak, Sk vektörüyle yaklaşık olarak aynı olan S^ vektörü hesaplanır. Bu işlem g(x) vektörü kullanılarak oluşturulan bant matrisin tanımladığı doğrusal denklem sisteminin, Sk+ı kullanılarak çözülmesiyle kolayca gerçeklenir. Ancak elde edilen Si vektörünün geçerli bir çözüm olduğunun kontrol edilmesi, yani fix) uygulandığında Sjt+ı'i üretmesi, yani, Sl+1=Sk+ı olması gerekmektedir. Aksi durumda, geçerli bir çözüm üretilememiş olup, elde edilen 5^'da hata düzeltmesi yapılmalıdır. Bu düzeltme, 5^+1 ve Sji+ı'in aynı olmayan noktalan dikkate alınarak, S*k üzerinde yapılır. Bu işlemin sonucunda geçerli bir S*k elde edilir. Şekil 2: Algoritmanın bir kısmının şematik gösterilimi. Önerilen Zikzak Algoritmasının Analizi: Zaman karmaşıklığı bu şifre analiz metodu için temel ölçüttür. Önerilen zikzak algoritmasının anlamlı olması için zaman karmaşıklığının, eksiksiz denemenin zaman karmaşıklığından daha az olmalıdır. Eksiksiz deneme n genişlikli bir CA için 0(2") şeklinde verilir. Her güncelleme fonksiyonu yeni bir sistem tanımladığı için analitik bir karmaşıklık fonksiyonu vermek çok güçtür. Bu nedenle ancak 11. adıma kadar olan kısım için bir üst şuur verilebilmiştir. Analitik üst sınır 0((l+a)n) 0.5