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. 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

$k$ pozitif bir integer ve $P=\{0,1\}^{k}$ bir mesaj kümesi olsun. $f:\,Y\rightarrow Z$ ise bir tek yönlü fonksiyon olsun.

$1\leq i\leq k$ and $j\in \{0,1\}$ için, imzayı atacak kişi $y_{i,j}\in Y$ gelişigüzel seçer ve $z_{i,j}=f(y_{i,j})$ fonksiyonunu hesaplar.

Özel anahtar, $K$, $2k$ değerleri $y_{i,j}$ 'dan oluşur. Genel anahtar $2k$ değerleri $z_{i,j}$'dan oluşur.

Mesaj İmzalamak

$m=m_{1}\ldots m_{k}\in \{0,1\}^{k}$ bir mesaj olsun.

Mesajın imzası:

$\operatorname {sig} (m_{1}\ldots m_{k})=(y_{1,m_{1}},\ldots ,y_{k,m_{k}})=(s_{1},\ldots ,s_{k})$.

İmzayı Doğrulamak

Doğrulayan bir imzayı $f(s_{i})=z_{i,m_{i}}$ her bir $1\leq i\leq k$ için kontrol ederek doğrular.

Bir mesajı taklit edebilmek için Ece tek yön fonksiyon $f$ 'yi tersine çevirmelidir. Bu uygun boyutlu giriş ve çıkışlar için zorlu kabul edilir.

Güvenlik Değişkenleri

Lamport imzalarının güvenliği, tek yönlü karma işlevinin güvenliğine, çıktısının uzunluğuna ve girdinin kalitesine dayanır.

n bitlik mesaj özeti üreten bir özet fonksiyonu için, tek bir özet fonksiyonu üzerindeki ideal öngörüntü ve 2. öngörüntü direnci, klasik bir hesaplama modeli altında bir çakışma bulmak için 2ⁿ sayıda işlem gerektirir.

Grover'in algoritmasına göre, ideal bir özet fonksiyonunun tek bir çağrımında bir öngörüntü çakışması bulmanın bir quantum hesaplama modelindeki üst limiti O(2^n/2) işlemdir. Lamport imzalarında, ortak anahtarın ve imzanın her bir biti, yalnızca tek bir özet fonksiyonu çağrılması gerektiren kısa mesajlara dayanır.

Her özel anahtar y_i,j ve karşılık gelen z_i,j açık anahtar çifti için, özel anahtar uzunluğu, girişin uzunluğuna yapılan bir öngörüntü çakışması saldırısı çıkışa yapılandan daha hızlı olmayacak şekilde seçilmelidir. Örnek olarak, eğer her bir özel anahtar y_i,j elemanı sadece 16 bit uzunluğundaysa, 2¹⁶ mesajın tüm 2¹⁶ olası özel tuş kombinasyonunu, mesaj özeti uzunluğuna bakılmaksızın, çıktıyla bir eşleşme bulmak için çok çabalamak önemsizdir.

Bu nedenle dengeli bir sistem tasarımı, her iki uzunluğun da yaklaşık olarak eşit olmasını sağlar.

Grover'ın algoritmasına dayanan kuantum emniyetli bir sistem, genel anahtar elemanların uzunluğu z_i,j, özel anahtar elemanlar y_i,j ve imza elemanları s_i,j sistemin güvenlik derecesinin 2 katından daha az olmamalıdır. Yani:

• 80 bitlik bir güvenli sistem, 160 bitten az olmayan eleman uzunluklarını kullanır;
• 128 bitlik bir güvenli sistem, 256 bitten az olmayan eleman uzunluklarını kullanır;

Fakat ideal çalışma tahminleri, ideal (mükemmel) bir özet fonksiyonu işlevi üstlendiğinden ve bir seferde sadece tek bir öngörüntüyü hedef alan saldırılarla sınırlı olduğundan dikkatli olunmalıdır.

Geleneksel bir hesaplama modelinde, 2^3n/5 öngörüntü aranırsa, öngörüntü başına maliyetin 2^n/2'den 2^2n/5'e düştüğü bilinmektedir. Çoklu mesaj özetlerinin toplanması dikkate alınarak optimum eleman boyutunun seçilmesi açık bir sorundur. Daha büyük eleman boyutları ve 512 bit elemanlar ve SHA-512 gibi daha güçlü özet fonksiyonları, bu bilinmeyenlerin yönetilmesi için daha fazla güvenlik aralığı sağlar.

İyileştirmeler ve Çeşitleri

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 $2k$ değerleri yerine $z_{ij}$ 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 $j\neq m_{i}$ için $(z_{ij})$ 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 $2\langle {\text{chunk size in bits}}\rangle$ biraz daha azı kadar ve imza için bu değerin yarısı kadar düşürür. Hesaplama $2^{\langle {\text{blok büyüklüğü, bit cinsinden}}\rangle }/\langle {\text{blok büyüklüğü, bit cinsinden}}\rangle$ 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.