Yazan : Şadi Evren ŞEKER

McEliece şifrelemesi (McEliece cryptosystem), veri güvenliğinde kullanılan asimetrik şifreleme (asymmetric encryption) yöntemlerinden birisidir.

Algoritma, veri güvenliği açısından çok kullanışlı olmasa da gelişmekte olan kuvantum hesaplama (quantum computing) çalışmaları ile birlikte önem kazanmaya başlamıştır. Bilindiği üzere Shor’un çarpanlara ayırma yöntemi, klasik şifreleme algoritmalarının çoğu için bir tehdit oluşturmaktadır. Dolayısıyla McEliece yöntemi içerisinde rast gele üretilmiş değerler taşıyan şifreleme sistemleri önem kazanmıştır.

Algoritmanın üzerine kurulu olduğu matematiksel zorluk, doğrusal kod’un parçalanması (decoding of linear code) olarak özetlenebilir. Bu problem, karmaşıklık sınıfı olarak NP-Zor (NP-Hard) sınıfına karşılık gelir.

Algoritma, anahtar üretimi ve mesaj şifreleme olarak iki aşamadan oluşur.

  1. Alice ikilik tabanda bir C = (n,k) doğrusal kodu seçer. Bu koddan k x n boyutunda bir G, üreteç matrisi (generator matrix) üretilebilir. Bu matrisin t hatayı düzeltme kabiliyeti olduğunu kabul edelim.
  2. Alice rast gele içerikte S= k x k boyutlarında tersi alınamaz matris seçer (kare matrisler için tersi alınamama şartının, determinantın 0 olması gerektiğini hatırlayınız)
  3. Alice rast gele içerikte P = n x n boyutlarında bir permütasyon matrisi (permutation matrix) üretir.
  4. Alice, k x n boyutlarında G’ matrisini şu şekilde hesaplar G’ = SGP
  5. Alice G’ ve t değerlerini açık anahtar olarak yayınlar, S,G ve P değerlerini ise gizli anahtar olarak tutar.

Bob m mesajını göndermek istiyor olsun ve Alice’in (G’,t) bilgilerini görebiliyor olsun.

  1. Bob’un mesajının k uzunluğunda olduğunu kabul edelim.
  2. Bob, c’ = m G’ değerini hesaplar ( bu bir kod kelimesidir).
  3. Bob rast gele içerikli bir z vektörü üretir ve bu vektör n boyutundadır ve t adet 1 içerir.
  4. Bob şifreli mesajı c = c’+z olarak hesaplar ve Alice’e yollar

Alice c mesajını açmak için aşağıdaki yolu izler.

  1. Öncelikle P matrisinin tersini alır, buna P-1 diyelim.
  2. c’ değerini c’ = c P-1 işlemiyle bulur.
  3. Alice, C doğrusal kodunu c’ ve m’ değerlerine parçalar
  4. m = m’S-1 hesaplaması ile mesajı açar.

Algoritmanın yukarıdaki adımları, aşağıdaki şekilde görsel olarak ifade edilebilir:

Sayısal Örnek

Algoritmanın çalışmasını bir örnek üzerinden inceleyelim. Öncelikle anahtarlarımızı üretmek için gerekli olan matrisleri (masfuf) seçiyoruz:

Aşağıda verilen G, S ve P matrislerini ele alalım:

Yukarıdaki bu matrisleri kullanarak G’ = SGP matrisini aşağıdaki şekilde hesaplayabiliriz.

Yukarıdaki hesaplamalardan sonra, G ve G’ anahtarları bulunmuş olunuyor. Buna göre, G ile şifrelenen bir mesaj G’ ile açılabilir veya tam tersi şeklinde G’ ile şifrelenen mesaj da G ile açılabilmektedir.

Örneğin şifrelemek için G’ anahtarını kullanacağımızı kabul edelim.

Alice göndermek üzere mesaj olarak m = (1101) seçmiş olsun.

e=|0 0 0 0 1 0 0 | şeklinde seçtiğimiz matris ile

c= mG’ + e hesabını yapıyoruz.

|0 1 1 0 0 1 0 | + | 0 0 0 0 1 0 0 | = | 0 1 1 0 1 1 0 |

Yukarıdaki hesaplama sonucunda şifreli mesaj olarak 0110110 sonucu bulunmuştur.

Şimdi bu şifreleme işleminin sonucunda çıkan şifreli mesajın nasıl açıldığına bakalım:

Öncelikle açma işlemi için gerekli olan matrislerin tersini alalım:

Öncelikle c’ = c P-1 değerini, yukarıdaki tersi alınmış matris ile hesaplayalım:

c’ = | 1 0 0 0 1 1 1 |

Bu aşamada hamming decode yapılarak mS dğeerinin |1 0 0 0 | olduğunu buluyor.

Geriye bulunan bu değerin S matrisinin tersi olan S-1 matrisi ile çarpıyoruz.

m = | 1 0 0 0 | S-1 = | 1 1 0 1 | olarak açık mesaj bulunuyor.

Yorumlar

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


+ 2 = on