- Katılım
- 7 Eyl 2009
- Konular
- 6,986
- Mesajlar
- 38,038
- Çözüm
- 1
- Online süresi
- 7d 22h
- Reaksiyon Skoru
- 1,833
- Altın Konu
- 0
- Başarım Puanı
- 494
- MmoLira
- 6,600
- DevLira
- 0
HERAKLES Otomatik Avlı kalıcı sunucu. 19 Haziran'da açılıyor. Atius & Wizard güvencesiyle hemen kayıt ol, ön kayıt ödülleri aktif. HEMEN TIKLA!
Tanım
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ı problem(sırt çantası probleminin özel bir durumu)ini 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.
Anahtar üretimi
Merkle-Hellman da, anahtarlar birer sırt çantalarıdır. Açık anahtar A nın "kolayca kırılamayan" sırt çantasıdır ve Gizli 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, problem beklenen 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ın altküme toplamına çevrilmesinde kullanılabilir.
Şifreleme
Mesajı ş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 edilmesini gözardı eder.Bu altkümenin elemanları toplanmış ve toplamanın sonucu şifrelenmiş metindir.
Deşifreleme
Deşifreleme mümkündür; çünkü çarpan ve modül kolayca çevrilebilir, süper artan sırt çantasındaki acık anahtar,böylece süper artan sırt çantasındaki elemanların karşılandığı toplamdaki şifreli metin sayı dönüştürme çevriminde kullanılabilir. Sonra; basit bir Greedy Algoritması kullanılarak, basit sırt çantası Büyük o gösterimindeki aritmetik operatörler kullanılarak çözülür. Böylece mesaj deşifrelenmiş olur.
Matematiksel Metod
Anahtar üretimi
n bitten olusan mesajı şifrelemek için süperartan bir dizi seçilir:
w = (w1, w2, ..., wn) n sıfırdan farklı doğal sayı.
q gibi bir rastgele sayı seçilir:
q>\sum_{i = 1}^n w_i ve r gibi rastgele bir sayı seçilir:
Ortak bölen(r,q) = 1 ( r ve q Aralarında asal)
q 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.
Şimdi diziyi hesaplayalım:
β = (β1, β2, ..., βn)
βi = rwi mod q.
Açık Anahtar β ve Gizli Anahtarlar (w, q, r) dir.
Şifreleme
n bit mesajı şifrelemek için
α = (α1, α2, ..., αn),
\alpha_i mesajın i. biti ve \alpha_i \boldsymbol{\in}{0, 1}
c = \sum_{i = 1}^n \alpha_i \beta_i.
Şifrelenmiş metin c dir.
Deşifreleme
Deşifreleme amacıyla alınan bir c şifreli mesajı, \alpha_i gibi bir biti ile şu şekilde uyuşur.
c = \sum_{i = 1}^n \alpha_i \beta_i.
β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 tamsayı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 tamsayı 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:
c'\equiv cs \pmod{q}. Bu yüzden
c' \equiv cs \equiv \sum_{i = 1}^n \alpha_i \beta_i s \pmod{q}.
Çünkü rs mod q = 1 ve βi = rwi mod q
\beta_i s\equiv w_i r s\equiv w_i\pmod{q}. Bu yüzden
c' \equiv \sum_{i = 1}^n \alpha_i w_i\pmod{q}.
Bütün wi değerlerinin toplamı q dan küçüktür ve bu yüzden \sum_{i = 1}^n \alpha_i w_i , [0,q-1] aralığındadır. Böylece alıcı alt küme problemini çözmüş olur.
c' = \sum_{i = 1}^n \alpha_i w_i.
Örnek
İlk olarak süper artan bir dizi olan w yi oluşturalım:
w = {2, 7, 11, 21, 42, 89, 180, 354}
Bu Gizli Anahtar için temeldir. Buradan toplamı hesaplayalım:
\sum w = 706
Sonra toplamdan büyük bir q sayısı seçelim:
q = 881
Ayrıca, [1, q) aralığında q ile Aralarında asal bir r sayısı seçelim:
r = 588
q, w ve r den oluşan Gizli anahtarımız oluşmuş oldu.
w kümesinin her bir elemanını rmodq ile çarparak β kümesini üretiyoruz:
β = {295, 592, 301, 14, 28, 353, 120, 236}
Çünkü
2 * 588 mod 881 = 295
7 * 588 mod 881 = 592
11 * 588 mod 881 = 301
21 * 588 mod 881 = 14
42 * 588 mod 881 = 28
89 * 588 mod 881 = 353
180 * 588 mod 881 = 120
354 * 588 mod 881 = 236
β 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).
01100001
Ayşe sırasıyla her bir biti β kümesindeki eşleşen her bir elemanla çarpmalıdır.
a = 01100001
0 * 295
+ 1 * 592
+ 1 * 301
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
= 1129
Bunu alıcıya göndermelidir. Ali, deşifrelerken bu sayıyı r −1 mod q ile çarpmalıdır(Modular multiplicative inverse).
1129 * 442 mod 881 = 372
Şimdi Ali, 372 den; w kümesinden seçilen 372 ye eşit yada 372 den küçük en büyük sayıyı çıkararak en son fark 0 oluncaya kadar işleme devam edilir.
372 - 354 = 18
18 - 11 = 7
7 - 7 = 0
Seçtiğimiz elemanların yerine 1 yazdığımızda ortaya gönderilen mesajın ikili karşılığı çıkmış olur.
01100001
Bu ikili kod geri çevrildiğinde, Ayşe'nin Ali'ye yolladığı "a" mesajına ulaşmış oluruz.
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ı problem(sırt çantası probleminin özel bir durumu)ini 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.
Anahtar üretimi
Merkle-Hellman da, anahtarlar birer sırt çantalarıdır. Açık anahtar A nın "kolayca kırılamayan" sırt çantasıdır ve Gizli 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, problem beklenen 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ın altküme toplamına çevrilmesinde kullanılabilir.
Şifreleme
Mesajı ş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 edilmesini gözardı eder.Bu altkümenin elemanları toplanmış ve toplamanın sonucu şifrelenmiş metindir.
Deşifreleme
Deşifreleme mümkündür; çünkü çarpan ve modül kolayca çevrilebilir, süper artan sırt çantasındaki acık anahtar,böylece süper artan sırt çantasındaki elemanların karşılandığı toplamdaki şifreli metin sayı dönüştürme çevriminde kullanılabilir. Sonra; basit bir Greedy Algoritması kullanılarak, basit sırt çantası Büyük o gösterimindeki aritmetik operatörler kullanılarak çözülür. Böylece mesaj deşifrelenmiş olur.
Matematiksel Metod
Anahtar üretimi
n bitten olusan mesajı şifrelemek için süperartan bir dizi seçilir:
w = (w1, w2, ..., wn) n sıfırdan farklı doğal sayı.
q gibi bir rastgele sayı seçilir:
q>\sum_{i = 1}^n w_i ve r gibi rastgele bir sayı seçilir:
Ortak bölen(r,q) = 1 ( r ve q Aralarında asal)
q 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.
Şimdi diziyi hesaplayalım:
β = (β1, β2, ..., βn)
βi = rwi mod q.
Açık Anahtar β ve Gizli Anahtarlar (w, q, r) dir.
Şifreleme
n bit mesajı şifrelemek için
α = (α1, α2, ..., αn),
\alpha_i mesajın i. biti ve \alpha_i \boldsymbol{\in}{0, 1}
c = \sum_{i = 1}^n \alpha_i \beta_i.
Şifrelenmiş metin c dir.
Deşifreleme
Deşifreleme amacıyla alınan bir c şifreli mesajı, \alpha_i gibi bir biti ile şu şekilde uyuşur.
c = \sum_{i = 1}^n \alpha_i \beta_i.
β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 tamsayı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 tamsayı 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:
c'\equiv cs \pmod{q}. Bu yüzden
c' \equiv cs \equiv \sum_{i = 1}^n \alpha_i \beta_i s \pmod{q}.
Çünkü rs mod q = 1 ve βi = rwi mod q
\beta_i s\equiv w_i r s\equiv w_i\pmod{q}. Bu yüzden
c' \equiv \sum_{i = 1}^n \alpha_i w_i\pmod{q}.
Bütün wi değerlerinin toplamı q dan küçüktür ve bu yüzden \sum_{i = 1}^n \alpha_i w_i , [0,q-1] aralığındadır. Böylece alıcı alt küme problemini çözmüş olur.
c' = \sum_{i = 1}^n \alpha_i w_i.
Örnek
İlk olarak süper artan bir dizi olan w yi oluşturalım:
w = {2, 7, 11, 21, 42, 89, 180, 354}
Bu Gizli Anahtar için temeldir. Buradan toplamı hesaplayalım:
\sum w = 706
Sonra toplamdan büyük bir q sayısı seçelim:
q = 881
Ayrıca, [1, q) aralığında q ile Aralarında asal bir r sayısı seçelim:
r = 588
q, w ve r den oluşan Gizli anahtarımız oluşmuş oldu.
w kümesinin her bir elemanını rmodq ile çarparak β kümesini üretiyoruz:
β = {295, 592, 301, 14, 28, 353, 120, 236}
Çünkü
2 * 588 mod 881 = 295
7 * 588 mod 881 = 592
11 * 588 mod 881 = 301
21 * 588 mod 881 = 14
42 * 588 mod 881 = 28
89 * 588 mod 881 = 353
180 * 588 mod 881 = 120
354 * 588 mod 881 = 236
β 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).
01100001
Ayşe sırasıyla her bir biti β kümesindeki eşleşen her bir elemanla çarpmalıdır.
a = 01100001
0 * 295
+ 1 * 592
+ 1 * 301
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
= 1129
Bunu alıcıya göndermelidir. Ali, deşifrelerken bu sayıyı r −1 mod q ile çarpmalıdır(Modular multiplicative inverse).
1129 * 442 mod 881 = 372
Şimdi Ali, 372 den; w kümesinden seçilen 372 ye eşit yada 372 den küçük en büyük sayıyı çıkararak en son fark 0 oluncaya kadar işleme devam edilir.
372 - 354 = 18
18 - 11 = 7
7 - 7 = 0
Seçtiğimiz elemanların yerine 1 yazdığımızda ortaya gönderilen mesajın ikili karşılığı çıkmış olur.
01100001
Bu ikili kod geri çevrildiğinde, Ayşe'nin Ali'ye yolladığı "a" mesajına ulaşmış oluruz.
