Merkle İmza Algoritması

Anahtar Oluşturma

Merkle imza algoritması tek açık anahtar olan pub ile sınırlı sayıda mesajın imzasında kullanılabilir. Muhtemel mesajların sayısı ikinin katı olmalıdır, dolayısıyla olası mesajların sayısını N = 2ⁿ ile gösterelim.

Ortak anahtar olan pub oluşturulması için ilk aşama N tane tek kullanımlık imza algoritmalarının  (Lamport imza algoritması gibi) özel/açık anahtar çifti (Xᵢ,Yᵢ) üretilmelidir. Her  1<= I <= 2ⁿ  için, ortak anahtarın özet değeri hᵢ = H(Yᵢ)  hesaplanır.
Bütün  yaprak özet değeri özyineli bir şekilde özet değerleri alınarak ikili ağaç formasyonunda Merkle ağacı oluşturulur.   ifadesinde yükseklik için  ve sağ sol pozisyonu göstermek içinse . Buna istinaden,   özet değerleri yaprakları temsil etmektedir. Her iç düğümlerin değeri, kendi alt 2 çocuğunun değerlerinin birleşiminin özet değerlerinin alınması ile belirlenir. Örneğin,  ve . Bu şekilde,   yapraklı bir ağaçta  düğüm oluşturulmaktadır.
Merkle imza algoritmasının özel anahtarı bütün  (Xᵢ,Yᵢ) çiftleridir. Algoritmanın en büyük problemlerinden birisi bu özel anahtar kümesinin boyutunun mesaj sayısıyla doğrusal oranda büyüyor olmasıdır.
Açık anahtar pub ağacın kökü olan =an,0  değeridir. Tek açık anahtar Yᵢ 'nin genele açılması güvenliği kırmayacaktır. Ancak, bunların kullanımı genel için bir ihtiyaç değildir ve boyutlarını da küçültmek adına gizli tutmak mantıklı olacaktır.

İmza Oluşturma

Merkle imza algoritması ile M mesajını imzalamak için  imzalayan bir (Xᵢ,Yᵢ)  anahtar çifti seçer, tek kullanımlık imza algoritması kullanarak imzalar ve ardından ek bilgileri ekleyerek aslında onun orijinal anahtar çiftlerinden biri olduğunu kanıtlar (bir sahtekar tarafından yeni yaratılanın yerine).

İlk olarak, imzalayıcı daha önce başka bir mesajı imzalamak için kullanılmamış (Xᵢ,Yᵢ) çifti seçer ve tek kullanımlık imza algoritmasını mesajı imzalamak için kullanarak  sig' imzasını ve karşılık gelen Yi açık anahtarını elde eder. Mesaj alıcısına (Xᵢ,Yᵢ)  çiftinin orijinal anahtar çiftlerinden biri olduğunu kanıtlamak için Merkle ağacının ara düğümlerini dahil ederek alıcının  hᵢ=a0,i değerinin ağacın kökünde bulunan an,o açık anahtarını hesaplamak için kullanıldığını doğrulamasını sağlar .  a0,i  değerinden kök değerine giden yolda n+1 düğüm bulunur ve bunların her birini A0,....,An şeklinde ifade ederiz.  A₀ = a0,i = H(Yᵢ) yaprak değeri ve  Aₙ = an,0 = pub ise kök değeri olmuş olur.
 düğümünün .Alıcının önceki verilmiş olanla bir sonraki düğüm  .Bu düğüme , böylece . Bu sebeple, bir kimlik doğrulama yolu sağ taraftaki şekilde gösterilmektedir.
Bu düğümler auth₀,…,authₙ₋₁, Yᵢ ve tek kullanımlık imza olan sig’ birlikte Merkle imza algoritması kullanarak bir M imzası oluştururlar:
sig = (sig’ || Yᵢ || auth₀|| auth₁ ||…|| authₙ₋₁)
Ayrıca unutulmamalıdır ki Lamport imza algoritması imza için kullanılırken , sig’ özel anahtar Xᵢ'nin bir bölümünü içerir.

İmza doğrulaması

Alıcı açık anahtar pub, mesaj M, ve imza sig = (sig’ || Yᵢ || auth₀|| auth₁ ||…|| authₙ₋₁) bilmektedir.İlk olarak alıcı tek kullanımlık imza açık anahtarı Yᵢ kullanarak mesaja ait olan tek kullanımlık imza sig’ doğrular. Eğer sig’ M mesajına ait geçerli bir imza ise, alıcı tek kullanımlık imzanın açık anahtarının özet değerini alarak  A₀ = H(Yᵢ) hesaplar.  j = 1,…, n-1  değerleri için , yol üzerindeki Aⱼ düğümleri Aⱼ = H(Aⱼ₋₁ || authⱼ₋₁) ile hesaplanır. Eğer Aₙ Merkle anahtar algoritmasına ait açık anahtar pub’a eşit ise  imza geçerlidir.