Merkle-Hellman kripto sistemi

Merkle-Hellman kripto sistemi, 1978 yılında Martin Hellman ve Ralph Merkle tarafından geliştirilen ilk açık anahtarlı kriptosistemlerden biridir. RSA'dan daha hızlı gerçekleştirilebilmesine rağmen Adi Shamir tarafından 1982'de güvensiz olduğu gösterilmiştir.Merkle-Hellman asimetrik anahtarlı bir kripto sistemdir; bunun anlamı, iletişim için iki anahtara ihtiyaç vardır. Bir Açık ve bir Gizli Anahtar. Ayrıca, RSA'dan farklı olarak, tek yönlüdür -Açık Anahtar sadece şifreleme, ve Gizli Anahtar sadece deşifreleme için kullanılır. Böylece bu yöntem Dijital imzalama tarafından kimlik kanıtlama için kullanılamaz.Merkle-Hellman sistemi altküme toplamı problemini (sırt çantası probleminin özel bir durumu) temel alır.Problem şu şekilde devam eder:Belirlenmiş A kümesi ve bir b sayısı, b nin toplamlarından oluşan A nın bir altkümesi.Bununla birlikte eğer sayı kümesi süper artan ise -şöyle ki; sayı kümesinin her bir elemanı önceki sayıların tamamının toplamından daha büyük olmalı - problem Greedy algoritması ile beklenen zamanda ve kolayca çözülebilir.Merkle-Hellman algoritmasında, anahtarlar birer sırt çantalarıdır. Açık anahtar A nın "kolayca kırılamayan" sırt çantasıdır veGizli Anahtar da B nin "basit" ya da süper artan bir sırt çantası, bir çarpan ve bir modülden oluşan iki ek sayının birleşimidir.Çarpan ve modül, süper artan sırt çantasından kolay kırılamayan sırt çantasına çevirmede kullanılabilir. Eğer, problembeklenen zamanda çözülebilirse; Aynı sayılar kolay kırılamayan sırt çantasının altküme toplamının basit sırt çantasınınMesajı şifrelemek için; A'nın kolay kırılamayan sırt çantasının altkümesinden seçilen anahtar uzunluğunda bit kümesi ile karşılastırılır.Açık anahtardaki her bir terim,   düz metindeki bir elemanı A_m altkümesinin bir elemanını karşılar, düz metindeki 0 A_m kümesinin inşa edilmesiniDeşifreleme mümkündür; çünkü çarpan ve modül kolayca çevrilebilir, süper artan sırt çantasındaki acık anahtar,böylecesüper artan sırt çantasındaki elemanların karşılandığı toplamdaki şifreli metin sayı dönüştürme çevrimindekullanılabilir. Sonra; basit bir Greedy Algoritması kullanılarak, basit sırt çantası Büyük o gösterimindeki aritmetik operatörler kullanılarakq nun böyle seçilmesi şifrelenmiş metnin benzersiz olmasını sağlar. Eğer q düz metinden daha küçük seçilirse, aynı şifrelenmiş metinler elde edilebilir. r ile q aralarında asal olmalıdır yoksa mod q göre tersine çevrilemeyecektir. q nun tersinin olması gereklidir. Böylece deşifreleme yapılabilir.βi rastgele değerler aldığından dolayı bu zor bir problem olabilir. Çünkü alıcı alt küme probleminin örnek bir çözümüne sahip olmalıdır. Anahtar Şifreleme, s tam sayılarını r mod q nun modüler tersinden bulmaktır. Bunun anlamı, s r mod q=1 den s yi  ya da s'r=k'q+1 k gibi bir tam sayı bulmaktır. r,  Ortak bölen(r,q) = 1 den seçildiğinden Extended Euclidean algorithm kullanılarak k ve s bulunabilir. Alıcı c şifreli metnini hesaplar:Bütün wi değerlerinin toplamı q dan küçüktür ve bu yüzden  , [0,q-1] aralığındadır. Böylece alıcı alt küme problemini çözmüş olur.β kümesi ile Açık Anahtarımızı oluşturmuş olduk. Ayşe  "a" yı şifrelemek istediğini söylesin. İlk önce Ayşe "a" nın ikili tabandaki değerini bulmalıdır(bu durumda, ASCII ya da UTF-8 kullanılmalıdır).Bunu alıcıya göndermelidir. Ali, deşifrelerken bu sayıyı r −1 mod  ile çarpmalıdır (Modular multiplicative inverse).Şimdi Ali, 372 den;  w kümesinden seçilen 372 ye eşit ya da 372 den küçük en büyük sayıyı çıkararak en son fark  oluncaya kadar işleme devam edilir.