Lamport imzası

Kriptografi 'de bir 'Lamport imzası' veya 'Lamport bir defalık imza şeması' dijital imza oluşturmak için kullanılan bir yöntemdir. Lamport imzaları, kriptografik olarak güvenli herhangi bir tek yönlü fonksiyon ile oluşturulabilir; genellikle bir Kriptografik özet fonksiyonu kullanılır.
Kuantum bilgisayarı 'nın potansiyel gelişimi, RSA gibi birçok yaygın kriptografi türünün güvenliğini tehdit etse de, uzun özet fonksiyonlarına sahip Lamport imzalarının hala güvenilir olacağına inanılmaktadır. Ne yazık ki, her bir Lamport anahtarı sadece bir mesajı imzalamakta kullanılabilmektedir. Lakin özet fonksiyon ağacı ile birleştirildiğinde, birçok mesaj için tek bir anahtar kullanılabilir ve böylece oldukça verimli bir dijital imza şeması olmasını sağlar.
Lamport imzası şifre sistemi 1979 yılında bulunmuş ve adını mucidi Leslie Lamport 'tan almıştır.

Örnek

Aslı'nın 256 - bitlik kriptografik özet fonksiyonu ve bir tür güvenli rassal sayı üreticisi bulunmaktadır. Bir Lamport anahtar çifti, bir özel anahtar ve ona uygun bir genel anahtar, oluşturup kullanmak istemektedir.

Anahtar çiftinin oluşturulması

Aslı özel anahtarını oluşturabilmek için rassal sayı üreticisi ile 256 adet rassal sayı çifti üretir ( toplamda 2x256 adet ), her biri 256 bit boyutunda olmak üzere toplamda 2x256x256 bit = 16 KiB 'tan oluşmaktadır. Bu Aslı'nın özel anahtarıdır ve daha sonra kullanmak üzere güvenli bir yerde saklar.
Genel anahtarı oluşturmak için 512 rassalnumaranın hepsi için özel anahtarı ile özet fonksiyonu hesaplaması yapar, böylelikle tanesi 256 bit uzunluğunda olmak üzere 512 adet özet fonksiyonu oluşmuş olur. (16 KiB) Bu 512 adet sayı dünya ile paylaşabilmesi için Aslı'nın genel anahtarını oluşturur.

Mesajın imzalanması

Aslı bir mesaj imzalamak istemektedir. İlk olarak mesajının özet fonksiyonu hesaplaması yaparak 256-bitlik bir özet fonksiyon sonucu üretir. Daha sonra, her bir bit için, bitin değerine bağlı olarak, özel anahtarını oluşturan sayı çiftleri arasından bir sayı seçer. ( Örneğin eğer bit 0 ise, ilk sayı seçilir, 1 ise, ikincisi seçilir) Bu, 256 adet rassal sayı dizisi üretir. Her bir sayı 256 bit uzunluğunda olduğundan ötürü, imzası 256x256 bit = 8 KiB olacaktır. Bu rassal sayılar Aslı'nın imzasıdır ve mesaj ile birlikte bu sayıları da yayınlar.
Artık Aslı'nın özel anahtarının kullanıldığının ve bir daha asla kullanılmaması gerektiğinin unutulmaması gerekmektedir. İmza için kullanmadığı diğer 256 rassal sayının da yok etmesi gerekmektedir. Aksi takdirde, özel anahtarı yeniden kullanan her bir imza, güvenlik düzeyini daha sonra sahte imzalar oluşturabilecek olan rakiplere karşı yarıya indirir.

İmzanın doğrulanması

Berk Aslı'nın mesajındaki imzasını doğrulamak istemektedir. O da mesajın özet fonksiyon hesaplamasını yaparak 256-bitlik bir özet fonksiyon sonucu üretir. Ardından, Aslı'nın açık anahtarında mesaj özetlerini çıkarmak için mesaj özeti toplamındaki bitleri kullanır. Aslı'nın imza için rassal sayı seçtiği şekilde özet fonksiyonlarını seçer. Eğer mesajın ilk bitinin özet fonksiyonu 0 ise, ilk çiftteki ilk özet fonksiyonunu seçer.
Berk Aslı'nın imzasındaki 256 rassal sayıdan her birini alır. Bu ona 256 adet özet fonksiyonu vermiş olur. Bu 256 özet fonksiyonu, Aslı'nın genel anahtarından aldığı 256 özet fonksiyonu ile tam olarak eşleşiyorsa, imza doğru sayılır. Eğer değil ise imza yanlıştır.
Aslı mesajın imzasını yayınlamadan önce, özel anahtardaki 2 × 256 rassal sayıyı başka kimse bilemez. Bundan ötürü kimse imza için doğru 256 rassal sayıyı oluşturamaz. Aslı imzayı yayınladıktan sonra, diğer 256 rassal sayıyı hala kimse bilememekte ve diğer mesajlara uyabilecek imzaları oluşturamaz.

Açıklama

Aşağıda, matematiksel notasyon ile yazılan Lamport imzalarının nasıl çalıştığına dair kısa bir açıklama bulunmaktadır.
Bu açıklamadaki "mesaj" makul büyüklükte bir sabit boyutta, muhtemelen ( ancak zorunlu olarak değil) imzalanan uzun bir mesajın özet fonksiyon sonucudur.

Anahtarlar

pozitif bir integer ve  bir mesaj kümesi olsun.  ise bir tek yönlü fonksiyon olsun.
 and  için, imzayı atacak kişi  gelişigüzel seçer ve  fonksiyonunu hesaplar.
Özel anahtar, ,  değerleri  'dan oluşur. Genel anahtar  değerleri 'dan oluşur.

İmzayı Doğrulamak

Doğrulayan bir imzayı  her bir  için kontrol ederek doğrular.
Bir mesajı taklit edebilmek için Ece tek yön fonksiyon  'yi tersine çevirmelidir. Bu uygun boyutlu giriş ve çıkışlar için zorlu kabul edilir.

Kısa özel anahtar

Özel anahtarın tüm rassal sayılarını oluşturmak ve saklamak yerine, yeterli boyuttaki tek bir anahtar saklanabilir.(Genellikle, özel anahtardaki rassal sayılardan biriyle aynı boyuttadır.) Tek anahtar, daha sonra gerektiğinde özel anahtardaki tüm rassal sayıları oluşturmak için kriptografik olarak güvenli rassal sayı üretici için tohum olarak kullanılabilir. Bir iletiyi imzalamak, özel anahtardan ek rassal değerleri açığa çıkaracağından, şifreli olarak güvenli bir özet fonksiyonun (veya en azından çıktısı tohumla XORlanmamış olan) rassal sayı üreticiyerine kullanılamayacağı unutulmamalıdır.
Eğer Ece istenilen alıcılar imzayı almadan önce imzaya erişebiliyorsa, özel anahtarın her açığa çıkmış rassal sayının iki katına çıkışı için yarıya düşen güvenlik seviyesi ile bir sahte imza üretebilir.
Aynı şekilde, birçok Lamport anahtarı oluşturmak için bir rassal sayı üreticisiyle birlikte tek bir anahtar kullanılabilir. Tercihen bir tür rastgele erişim rassal sayı üreticisi kullanılmalıdır, Blum Blum Shub gibi.

Kısa genel anahtar

Bir Lamport imzası bir özet fonksiyon listeli ile birleştirilebilir; böylece genel anahtardaki tüm özet mesaj özeti yerine yalnızca tek ana özet fonksiyonu çıktısı yazılabilir. Bu  değerleri yerine  anlamına gelir. Tek ana özet fonksiyonuna karşı doğrulama yapmak için, imza genel anahtarın kullanılmayan özet mesaj özetinı ve rassal sayıları içermelidir. Bu durum iki kat büyük imzalar oluşturur. Tüm  için  değerleri dahil edilmelidir.
Bir özet mesaj özeti listesi yerine bir şifreleme biriktiricisinin kullanılması durumunda kullanılmayan özet mesaj özetinın imzaya dahil edilmesine gerek yoktur. Ancak, biriktirici teorik varsayımlara dayanıyorsa, bu muhtemelen Lamport imzalarının kullanılmasının yararını ortadan kaldırmaktadır, örnek quantum hesaplama direnci.

Kısa anahtarlar ve imza

Winternitz imza sıkıştırması, özel anahtarın ve genel anahtarın boyutunu, imzanın  biraz daha azı kadar ve imza için bu değerin yarısı kadar düşürür. Hesaplama  biraz daha fazlası kadar artış gösterir. Bir kriptografik olarak güvenli rassal sayı oluşturucusu gereksinimi yerine kriptografik olarak güvenli bir özet fonksiyonu yeterlidir.
Bir önceki bölümde de açıklandığı gibi imzanın büyüklüğünü ikiye katlamak pahasına genel anahtarı tek bir değere kısaltmak için bir karma listesi de kullanılabilir.

Birden çok mesaj için genel anahtar

Her bir Lamport ortak anahtarı sadece bir tek mesajın imzalanması için kullanılabilir, bu da birçok mesajın imzalanması durumunda birçok anahtarın yayınlanması gerektiği anlamına gelir. Ama bir Merkle ağacı bu genel anahtarlarda kullanarak, sadece ana özet mesaj özetinı yayınlayabilir. Bu, ortaya çıkan imzanın büyüklüğünü artırır, çünkü fonksiyon özet ağacının bazı kısımları imzanın içine dahil edilmek zorundadır, ancak daha sonra herhangi bir sayıda gelecekteki imzaları doğrulamak için kullanılabilecek tek bir fonksiyon özet çıktısının yayınlanmasını mümkün kılar.