Merkle imza algoritması

**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ı kriptografidir ve Merkle ağacı da denen özet değeri ağacını kullanmaktadır. Verileri Lampart imza algoritması gibi tek kullanımlık şekilde imzalar. Ralph Merkle tarafından 1970 sonu itibarıyla geliştirilmiştir ve RSA, Dijital İmza Algoritması gibi geleneksel dijital imzalara alternatif olmuştur.

Merkle imza algoritmasının avantajı kuantum bilgisayarı algoritmalarına karşı dirençli olduğuna inanılıyor olmasıdır.&nbsp;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 geldi. Merkle imza algoritması sadece güvenilir bir&nbsp;özet değeri fonksiyonunun varlığına dayanmaktadır. Bu özelliği de Merkle imza algoritmasının çok esnek ve kuantum bilgisayarlarına dirençli olmasını sağlamaktadır. 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 fonskiyonunun icadı), Merkle benzeri imzaların tam bir imza algoritmasına dönüşmesine yol açmıştır.

## 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<sup>n</sup>** 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<sub>i</sub>,Y<sub>i</sub>)** üretilmelidir. Her **1<= I <= 2<sup>n</sup> &nbsp;için**, ortak anahtarın özet değeri **h<sub>i</sub> =** **H(Y<sub>i</sub>)** &nbsp;hesaplanır.
Bütün&nbsp;h_i2^n&nbsp;yaprak özet değeri özyineli bir şekilde özet değerleri alınarak ikili ağaç formasyonunda Merkle ağacı oluşturulur. &nbsp;a_{i,j}&nbsp;ifadesinde yükseklik için&nbsp;i&nbsp;ve sağ sol pozisyonu göstermek içinse&nbsp;j. Buna istinaden,&nbsp;h_i = a_{0,i}&nbsp;ö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, a_{1,0} = H(a_{0,0} || a_{0,1})&nbsp;ve&nbsp;a_{2,0} = H(a_{1,0} || a_{1,1}). Bu şekilde,&nbsp;2^n&nbsp;yapraklı bir ağaçta&nbsp;2^{n+1} - 1&nbsp;düğüm oluşturulmaktadır.

Merkle imza algoritmasının özel anahtarı bütün **(X<sub>i</sub>,Y<sub>i</sub>)** ç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 **=a<sub>n, 0</sub> &nbsp;**değeridir. Tek açık anahtar **Y<sub>i</sub>** '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<sub>i</sub>,Y<sub>i</sub>)**  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<sub>i</sub>,Y<sub>i</sub>)** ç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<sub>i</sub>,Y<sub>i</sub>)** ç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<sub>i</sub>=a<sub>0,i</sub>** 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 . **a<sub>0,i</sub>** değerinden kök değerine giden yolda n+1 düğüm bulunur ve bunların her birini A0,...., An şeklinde ifade ederiz. **A<sub>0</sub> = a<sub>0,i</sub> = H(Y<sub>i</sub>)** yaprak değeri ve **A<sub>n</sub> = a<sub>n, 0</sub> = pub** ise kök değeri olmuş olur.

A_i&nbsp;düğümünün&nbsp;A_{i+1}.Alıcının önceki verilmiş olanla bir sonraki düğüm&nbsp;A_{i+1} A_{i+1}.Bu düğüme&nbsp;\text{auth}_i, böylece&nbsp;A_{i+1} = H(A_i || \text{auth}_i). Bu sebeple,\text{auth}_0, \ldots, \text{auth}_{n-1}A_n = a_{n,0} = \text{pub}A_0 = a_{0,i}&nbsp;bir kimlik doğrulama yolu sağ taraftaki şekilde gösterilmektedir.

Bu düğümler **auth<sub>0</sub>,...,auth<sub>n-1</sub>, Y<sub>i</sub>** ve tek kullanımlık imza olan **sig**' birlikte Merkle imza algoritması kullanarak bir **M** imzası oluştururlar:

**sig = (sig' || Y<sub>i</sub>** || **auth<sub>0</sub>|| auth<sub>1</sub>** ||...|| **auth<sub>n-1</sub>)**

Ayrıca unutulmamalıdır ki Lamport imza algoritması imza için kullanılırken, **sig**' özel anahtar **X<sub>i</sub>**'nin bir bölümünü içerir.

## İmza doğrulaması
Alıcı açık anahtar **pub**, mesaj **M** ve imza **sig = (sig' || Y<sub>i</sub>** || **auth<sub>0</sub>|| auth<sub>1</sub>** ||...|| **auth<sub>n-1</sub>)** bilmektedir.İlk olarak alıcı tek kullanımlık imza açık anahtarı **Y<sub>i</sub>** 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<sub>0</sub> = H(Y<sub>i</sub>)** hesaplar. &nbsp;**j = 1,..., n-1 &nbsp;**değerleri için, yol üzerindeki **A<sub>j</sub>** düğümleri **A<sub>j</sub> = H(A<sub>j-1</sub> || auth<sub>j-1</sub>)** ile hesaplanır. Eğer **A<sub>n</sub>** Merkle anahtar algoritmasına ait açık anahtar **pub**’a eşit ise &nbsp;imza geçerlidir.

## Kaynakça

* G. Becker. "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis", seminar 'Post Quantum Cryptology' at the Ruhr-University Bochum, Germany.
* E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, L.C. Coronado Garca. "CMSS - an improved merkle signature scheme". Progress in Cryptology - Indocrypt 2006, 2006.
* E. Klintsevich, K. Okeya, C.Vuillaume, J. Buchmann, E.Dahmen. "Merkle signatures with virtually unlimited signature capacity". 5th International Conference on Applied Cryptography and Network Security - ACNS07, 2007.
* Ralph Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979. http://www.merkle.com/papers/Thesis1979.pdf 
* Moni Naor, Moti Yung: Universal One-Way Hash Functions and their Cryptographic Applications .STOC 1989: 33-43
* S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal merkle tree representation and traversal". RSA-CT 03, 2003

## Dış bağlantılar

* Efficient Use of Merkle Trees  -Merkle ağaçlarının asıl amacı olan birden fazla tek kullanımlık Lambort imzasının ele alınmasının RSA Labs tarafından açıklanması
* An introduction to hash-based signatures and Merkle signatures by Adam Langley. 
* A 4 parts series on hash-based signatures by David Wong.