Yazan: Şadi Evren ŞEKER
Merkle-Hellman bir açık anahtar şifreleme yöntemidir. Bu yönteme göre bir umumî anahtar bir de hususî anahtar bulunması gerekir. RSA’den farklı olarak şifreleme işlemi tek yönlü çalışır. Yani umumî anahtar sadece şifreleme (encryption) hususî anahtar ise sadece açma (decryption) işlemleri için kullanılabilir.
Anahtar üretme safhâsı:
Pozitif doğal sayılardan oluşan hızla aratan (superincreasing) bir seri (sequence) alınır.
Bu seriye S= (s1,s2,…sn) diyelim.
Bu serideki sayıların toplamından daha büyük bir p sayısı alalım.
Rasgele bir r sayısı alalım ancak bu r sayısı p sayısı ile aralarında asal olsun.
Yukarıda bulunan bu sayıların tamamı (p ve r sayıları) ile S serisi hususî şifre olarak saklanacaktır.
Şimdi umumî şifre hesabı için:
B=(B1,B1,…Bn) sayılarını hesaplayabiliriz. Bu serinin hesabında:
Bi = r Si mod p
formülü kullanılır ve bütün seri S serisine bağlı olarak hesaplanır.
Sonuçta elde edilen B serisi umumî anahtar olarak kullanılır.
Şifreleme safhâsı:
n-bitlik bir mesajı şifrelerken (bu mesaj a olsun) her bit ayrı ayrı ele alınır. Buna göre:
a= (a1,a2,…an) olarak düşünülsün. Buradaki her a terimi mesajın ilgili bitidir (örneğin a13, mesajın 13. biti olacaktır) ve her bit(ikil) 1 veya 0 olabilmektedir. Yani a serisinin iligli elemanı 0 veya 1 olabilir.
olarak serinin toplamını veren c değeri hesaplanır ve şifreli metin olarak karşı tarafa yollanır.
Açma safhâsı:
Daha önceden toplam değeri içeren c değeri aşağıdaki şekilde hesaplanmıştı:
Bu mesaja saldırmak isteyen kişinin uğraşması gereken zorluk alt küme toplam problemi zorluğudur çünkü saldıran kişi B değerlerini bilmemektedir ve tahmin etmesinin tek yolu NP-Complete olarak saldırmaktır.
Ancak hususî anahtarlar olan B r ve p değerleri biliniyorsa bu şifrenin açılması oldukça basittir. Açmak için r ve p değerleri kullanılarak modüler tersi olan f değeri bulunur. (Bu işlem örneğin uzatılmış öklit algoritması (extended euclid algorithm) ile kolayca yapılabilir)
Sonuç olarak her a değeri ( c / Si ) x f mod p formülü ile hesaplanabilir.
Yani problemde her sayı grubu farklı bir çarpanla çarpılmakta ve daha önceki çarpanlarla karıştırılmaması için bu çarpanlar serisi hızlı artan bir seri seçilmektedir.
Merkle-Hellman yönteminin dayandığı zorluk alt küme toplam problemi (subset sum problem)’dir (knapsack(torba) algoritmasının özel bir halidir). Problem genel olarak bir Belirsiz Çokterimli Tam Problemi (NP-Complete) yapısındadır. Bu problem tipi tanımı gereği çözüm zamanı önceden kestirilemezdir. Ancak Merkle-Hellman şifrelemesinde şayet her üretilen sayı kümesi, kendinden önceki kümelerden daha büyükse (superincreasing, hızlı artan) bu durumda problemin çözümü çokterimli zamanda (polynomial time) kestirilebilir ve bu kestirme işlemi için açgözlü yaklaşımı (greedy approach) kullanılabilir.