Merkle İmza Algoritması: Tek Kullanımlık İmzalardan Kuantum Dirençli İmza Yapısına.

Merkle İmza Yapısının Temel Tanımı

Merkle imzası, anahtarlama ağaçları ve sayısal imza şemalarını birleştiren bir veri doğrulama yapısıdır. Özet değeri tabanlı bir kriptografik yapı olup, Merkle ağacı olarak da bilinen özet değeri ağacını kullanmaktadır. Veriler Lampart imza algoritması gibi tek kullanımlık şekilde imzalanmaktadır. Ralph Merkle tarafından 1970 sonu itibarıyla geliştirilen bu yapı, RSA ve Dijital İmza Algoritması gibi geleneksel dijital imzalara alternatif olmuştur.

Kuantum Bilgisayarlara Dirençlilik İddiası

Merkle imza algoritmasının avantajı, kuantum bilgisayarları algoritmalarına karşı dirençli olduğuna inanılmasıdır. Geleneksel açık anahtar algoritmaları olan RSA ve ElGamal gibi algoritmalar, efektif kuantum bilgisayarlarının tasarlanabilir olmasıyla birlikte Shor’un algoritmasına dayanarak güvensiz hale gelmektedir. Merkle imza algoritması ise sadece güvenilir bir özet değeri fonksiyonunun varlığına dayanmaktadır. Bu özelliği, Merkle imza algoritmasının çok esnek ve kuantum bilgisayarlarına dirençli olmasını sağlamaktadır.

Ancak Merkle imzasının sonlu imza potansiyeli olan tek kullanımlık bir imza olduğu unutulmamalıdır. Moni Maor ve Moti Yung’un imza tabanlı tek yölü permütasyonlar üzerindeki çalışması ve fonksiyonlar (ve evrensel tek yönlü özet değeri fonksiyonunun icadı), Merkle benzeri imzaların tam bir imza algoritmasına dönüşmesine yol açmıştır.

Anahtar Oluşturma Süreci

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 = 2n 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 (Xi,Yi) üretilmelidir. Her 1<= I <= 2n için, ortak anahtarın özet değeri hi = H(Yi) hesaplanır. Bütün hi 2^n yaprak özet değeri özyineli bir şekilde özet değerleri alınarak ikili ağaç formasyonunda Merkle ağacı oluşturulur. ai,j ifadesinde yükseklik için i ve sağ sol pozisyonu göstermek için j kullanılır. Buna istinaden hi=a0,i ö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 a1,0=H(a0,0||a0,1) ve a2,0=H(a1,0||a1,1). Bu şekilde, 2^n yapraklı bir ağaçta 2^(n+1)-1 düğüm oluşturulmaktadır.

Merkle imza algoritmasının özel anahtarı bütün (Xi,Yi) ç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. Light anahtar pub ağacın kökü olan an,0 değeridir. Tek açık anahtar Yi’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 ve Doğrulama

Merkle imza algoritması ile M mesajını imzalamak için imzalayan bir (Xi,Yi) 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. İmzalayıcı daha önce başka bir mesajı imzalamak için kullanılmamış (Xi,Yi) ç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 (Xi,Yi) ç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 hi=a0,i değerinin ağacın kökünde bulunan an,0 açık anahtarını hesaplamak için kullanıldığını doğrulamasını sağlar.

Bu düğümler auth0,…,authn-1, Yi ve tek kullanımlık imza olan sig’ birlikte Merkle imza algoritması kullanarak bir M imzası oluştururlar: sig = (sig’ || Yi || auth0|| auth1 ||…|| authn-1). Ayrıca unutulmamalıdır ki Lamport imza algoritması imza için kullanılırken, sig’ özel anahtar Xi’nin bir bölümünü içerir.

Alıcı açık anahtar pub, mesaj M ve imza sig bilgisini bilmektedir. İlk olarak alıcı tek kullanımlık imza açık anahtarı Yi 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 A0 = H(Yi) hesaplar. j = 1,…, n-1 değerleri için, yol üzerindeki Aj düğümleri Aj = H(Aj-1 || authj-1) ile hesaplanır. Eğer An Merkle anahtar algoritmasına ait açık anahtar pub’a eşit ise imza geçerlidir.

Bu açıklama Vikipedi kaynaklarından uyarlanmıştır ve şu lisans altında sunulur: CC BY-SA 4.0.