Lamport imzası - Lamport signature

İçinde kriptografi, bir Lamport imzası veya Lamport tek seferlik imza şeması oluşturmak için bir yöntemdir elektronik imza. Lamport imzaları herhangi bir kriptografik açıdan güvenli tek yönlü işlev; genellikle bir kriptografik karma işlevi kullanıldı.

Potansiyel gelişimi olmasına rağmen kuantum bilgisayarlar gibi birçok yaygın şifreleme biçiminin güvenliğini tehdit eder RSA, büyük karma işlevlere sahip Lamport imzalarının bu durumda hala güvenli olacağına inanılmaktadır. Ne yazık ki, her Lamport anahtarı yalnızca tek bir mesajı imzalamak için kullanılabilir. Bununla birlikte haşhaş ağaçları, birçok mesaj için tek bir anahtar kullanılabilir, bu da bunu oldukça verimli bir dijital imza şeması haline getirir.

Lamport imzalı şifreleme sistemi 1979'da icat edildi ve mucidinin adını aldı, Leslie Lamport.

Misal

Alice 256 bitlik bir kriptografik hash işlevine ve bir tür güvenli rastgele numara üreticisi. Bir Lamport anahtar çifti, yani bir özel anahtar ve karşılık gelen bir genel anahtar oluşturmak ve kullanmak istiyor.

Anahtar çifti yapmak

Özel anahtarı oluşturmak için Alice, 256 çift rastgele sayı (toplamda 2 × 256 sayı) üretmek için rasgele sayı üretecini kullanır, her sayı 256 bit boyutundadır, yani toplam 2 × 256 × 256 bit = 128 Kibit toplamda. Bu onun özel anahtarıdır ve daha sonra kullanmak üzere güvenli bir yerde saklayacaktır.

Açık anahtarı oluşturmak için, özel anahtardaki 512 rasgele sayının her birini hashler, böylece her biri 256 bit boyutunda 512 karma oluşturur. (Ayrıca toplamda 128 Kbit.) Bu 512 numara, onun dünya ile paylaşacağı açık anahtarını oluşturur.

Mesajı imzalamak

Alice daha sonra bir mesaj imzalamak ister. Önce mesajı 256 bitlik bir hash toplamına hash eder. Daha sonra, karmadaki her bit için, bitin değerine bağlı olarak, özel anahtarını oluşturan karşılık gelen sayı çiftlerinden bir sayı seçer (yani, bit 0 ise, ilk sayı seçilir ve eğer bit 1, ikincisi seçilir). Bu, 256 sayılık bir dizi oluşturur. Her sayının kendisi 256 bit uzunluğunda olduğundan, imzasının toplam boyutu 256 × 256 bit = 64 KiB olacaktır. Bu (başlangıçta rastgele seçilen) numaralar onun imzasıdır ve bunları mesajla birlikte yayınlar.

Artık Alice'in özel anahtarı kullanıldığına göre, bir daha asla kullanılmaması gerektiğini unutmayın. İmza için kullanmadığı diğer 256 numarayı imha etmek zorundadır. Aksi takdirde, özel anahtarı yeniden kullanan her ek imza, Güvenlik seviyesi daha sonra onlardan sahte imzalar yaratabilecek düşmanlara karşı.^[1]

İmzayı doğrulama

Sonra Bob, Alice'in mesajdaki imzasını doğrulamak ister. Ayrıca 256 bitlik bir hash toplamı almak için mesajı karma hale getirir. Daha sonra, Alice'in açık anahtarındaki 256 hash değerini seçmek için hash toplamındaki bitleri kullanır. Karmaları, Alice'in imza için rastgele sayıları seçtiği şekilde seçer. Yani, mesaj özetinin ilk biti 0 ise, ilk karma ilk çiftte vb.

Ardından Bob, Alice'in imzasındaki 256 rastgele sayının her birini hashler. Bu ona 256 karma verir. Bu 256 hash, Alice'in genel anahtarından seçtiği 256 hash ile tam olarak eşleşiyorsa, imza tamamdır. Değilse, imza yanlıştır.

Alice mesajın imzasını yayınlamadan önce, özel anahtardaki 2 × 256 rastgele sayıyı kimsenin bilmediğini unutmayın. Bu nedenle, imza için 256 rasgele sayıdan oluşan uygun bir liste oluşturamaz. Ve Alice imzayı yayınladıktan sonra, diğerleri hala diğer 256 rasgele sayıyı bilmiyorlar ve bu nedenle diğer mesaj karmalarına uyan imzalar oluşturamıyorlar.

Resmi açıklama

Aşağıda Lamport imzalarının nasıl çalıştığına dair kısa bir açıklama bulunmaktadır. matematiksel gösterim. Bu açıklamadaki "mesaj" ın, muhtemelen (ancak zorunlu olmamakla birlikte) imzalanan keyfi bir uzun mesajın karma sonucunun sabit boyutlu bir blok olduğunu unutmayın.

Anahtarlar

İzin Vermek ${ displaystyle k}$ pozitif bir tamsayı olsun ve ${ displaystyle P = {0,1 } ^ {k}}$ mesaj seti olun. İzin Vermek ${ displaystyle f: , Y sağ Z}$ olmak tek yönlü işlev.

İçin ${ displaystyle 1 leq i leq k}$ ve ${ displaystyle j in {0,1 }}$ imzalayan seçer ${ displaystyle y_ {i, j} Y'de}$ rastgele ve hesaplar ${ displaystyle z_ {i, j} = f (y_ {i, j})}$.

Özel anahtar, ${ displaystyle K}$, içerir ${ displaystyle 2k}$ değerler ${ displaystyle y_ {i, j}}$. Genel anahtar şunlardan oluşur: ${ displaystyle 2k}$ değerler ${ displaystyle z_ {i, j}}$.

Bir mesajı imzalamak

İzin Vermek ${ displaystyle m = m_ {1} ldots m_ {k} in {0,1 } ^ {k}}$ mesaj ol.

Mesajın imzası

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

Bir imzayı doğrulama

Doğrulayıcı, bir imzayı kontrol ederek doğrular. ${ displaystyle f (s_ {i}) = z_ {i, m_ {i}}}$ hepsi için ${ displaystyle 1 leq i leq k}$.

Bir mesajı taklit etmek için Havva tek yönlü işlevi tersine çevirmek zorunda kalacaktı ${ displaystyle f}$. Bunun uygun boyuttaki girdi ve çıktılar için inatçı olduğu varsayılır.

Güvenlik parametreleri

Lamport imzalarının güvenliği, tek yönlü hash fonksiyonunun güvenliğine ve çıktısının uzunluğuna bağlıdır.

Bir n-bit ileti özeti oluşturan bir karma işlevi için ideal ön görüntü ve 2. ön görüntü tek bir hash işlevi çağrısında direnç, 2 sırasını ifade ederⁿ klasik bir hesaplama modeli altında bir çarpışma bulma işlemleri. Göre Grover algoritması, ideal bir hash fonksiyonunun tek bir çağrılmasında bir ön görüntü çarpışması bulmak, O (2^n/2) bir kuantum hesaplama modeli altındaki işlemler. Lamport imzalarında, genel anahtarın ve imzanın her bir biti, karma işlev için yalnızca tek bir çağrı gerektiren kısa mesajlara dayanır.

Her özel anahtar için y_{ben, j} ve karşılık gelen z_{ben, j} açık anahtar çifti için özel anahtar uzunluğu seçilmelidir, böylece girişin uzunluğuna bir ön görüntü saldırısı gerçekleştirmek, çıktının uzunluğuna bir ön görüntü saldırısı gerçekleştirmekten daha hızlı değildir. Örneğin, dejenere bir durumda, her bir özel anahtar y_{ben, j} öğesi yalnızca 16 bit uzunluğundaydı, tüm 2'yi kapsamlı bir şekilde aramak önemsizdir.¹⁶ 2'de olası özel anahtar kombinasyonları¹⁶ mesaj özeti uzunluğuna bakılmaksızın çıktıyla bir eşleşme bulma işlemleri. 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, kuantum güvenli bir sisteme, genel anahtar öğelerin uzunluğuna dayanır z_{ben, j}özel anahtar öğeler y_{ben, j} ve imza unsurları s_{ben, j} sistemin güvenlik derecelendirmesinin 2 katından az olmamalıdır. Yani:

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

Bununla birlikte, yukarıdaki idealist çalışma tahminleri ideal (mükemmel) bir hash işlevi varsaydığından ve bir seferde yalnızca tek bir ön görüntüyü hedefleyen saldırılarla sınırlı olduğundan dikkatli olunmalıdır. Geleneksel bir hesaplama modeli altında, eğer 2^3n/5 ön görüntüler aranır, ön görüntü başına tam maliyet 2'den düşer^n/2 2'ye^2n/5.^[2] Birden çok mesaj özetinin toplanmasını hesaba katarak optimum öğe boyutunu seçmek açık bir sorundur. Daha büyük öğe boyutlarının ve 512 bit öğeler ve SHA-512 gibi daha güçlü karma işlevlerin seçimi, bu bilinmeyenleri yönetmek için daha fazla güvenlik marjı sağlar.

Optimizasyonlar ve varyantlar

Kısa özel anahtar

Özel anahtarın tüm rasgele sayılarını oluşturmak ve depolamak yerine, yeterli büyüklükte tek bir anahtar saklanabilir. (Genellikle özel anahtardaki rastgele sayılardan biriyle aynı boyuttadır.) Tek anahtar daha sonra bir kriptografik olarak güvenli sözde rasgele sayı üreteci (CSPRNG) gerektiğinde özel anahtarda tüm rastgele sayıları oluşturmak için. Kriptografik olarak güvenli bir hash'in (veya en azından çıktısı tohumla XOR'lanmayan) CSPRNG yerine kullanılamayacağına dikkat edin, çünkü bir mesajı imzalamak özel anahtardan ek rastgele değerler ortaya çıkaracaktır. Düşman, imzaya hedeflenen alıcılardan önce erişebilirse, özel anahtardan açığa çıkan rastgele değerlerin her ikiye katlanması için güvenlik düzeyini yarıya indiren bir imza oluşturabilir.

Aynı şekilde, birçok Lamport anahtarı oluşturmak için bir CSPRNG ile birlikte tek bir anahtar kullanılabilir. Tercihen o zaman bir çeşit rasgele erişim CSPRNG, aşağıdaki gibi kullanılmalıdır: BBS.

Kısa genel anahtar

Lamport imzası, bir karma liste, genel anahtardaki tüm karmalar yerine yalnızca tek üst karmanın yayınlanmasını mümkün kılar. Yani, yerine ${ displaystyle 2k}$ değerler ${ displaystyle z_ {ij}}$. Tek üst hash'e göre doğrulama yapmak için, imza rastgele sayıları ve genel anahtarın karma listesinden kullanılmayan karmaları içermeli ve bu da yaklaşık iki kat büyüklüğünde imzalarla sonuçlanmalıdır. Yani değerler ${ displaystyle (z_ {ij})}$ hepsi için ${ displaystyle j neq m_ {i}}$ dahil edilmesi gerekiyor.

Bir kriptografik ise, kullanılmayan karmaların imzaya dahil edilmesine gerek yoktur. akümülatör karma liste yerine kullanılır.^[3] Bununla birlikte, eğer toplayıcı sayı-teorik varsayımlara dayanıyorsa, bu muhtemelen Lamport imzalarını kullanmanın yararını ortadan kaldırır, ör. kuantum hesaplama direnci.

Kısa anahtarlar ve imza

Winternitz imza sıkıştırması, özel anahtarın ve genel anahtarın boyutunu, bir faktörden biraz daha az azaltır. ${ displaystyle 2 langle { text {bit cinsinden yığın boyutu}} rangle}$ve imza için bu faktörün yarısı. Hesaplama, bir faktörden biraz daha fazla artar ${ displaystyle 2 ^ { langle { text {bit cinsinden yığın boyutu}} rangle} / langle { text {bit cinsinden yığın boyutu}} rangle}$. Bir CSPRNG gereksinimi yerine kriptografik olarak güvenli bir hash yeterlidir.^[4]

Bir karma liste, önceki bölümde açıklandığı gibi imzanın boyutunu iki katına çıkarma pahasına, genel anahtarı tek bir değere kısaltmak için de kullanılabilir.

Birden çok mesaj için genel anahtar

Her Lamport genel anahtarı yalnızca tek bir mesajı imzalamak için kullanılabilir; bu, birçok mesajın imzalanması için birçok anahtarın yayınlanması gerektiği anlamına gelir. Ancak karma ağaç bu genel anahtarlarda kullanılabilir, bunun yerine karma ağacının en üst karma değerini yayınlar. Bu, hash ağacının bazı kısımlarının imzaya dahil edilmesi gerektiğinden, sonuçta ortaya çıkan imzanın boyutunu artırır, ancak daha sonra herhangi bir sayıda gelecekteki imzayı doğrulamak için kullanılabilecek tek bir karma yayınlamayı mümkün kılar.

Ayrıca bakınız

• S / ANAHTAR

Referanslar

daha fazla okuma

• L. Lamport, Tek yönlü bir işlevden dijital imzalar oluşturma, Teknik Rapor SRI-CSL-98, SRI Uluslararası Bilgisayar Bilimleri Laboratuvarı, Ekim 1979.
• Merkle Ağaçlarının Verimli Kullanımı - RSA laboratuvarları verimli bir defalık imza şeması olarak Merkle ağaçları + Lamport imzalarının orijinal amacının açıklaması.
• Adam Langley tarafından karma tabanlı imzalara ve Merkle imzalarına giriş.
• BLAKE2b (C ++) üzerine Lamport şemasının referans uygulaması
• SHA256, SHA512 veya Blake2b (Rust) üzerine Lamport İmzalarının Referans Uygulaması