Shamirs Gizli Paylaşımı - Shamirs Secret Sharing - Wikipedia

Shamir'in Gizli Paylaşımı bir algoritma içinde kriptografi tarafından yaratıldı Adi Shamir. Bu bir biçimdir gizli paylaşım, bir sırrın parçalara bölündüğü ve her katılımcıya kendi benzersiz bölümünü verdiği.

Orijinal sırrı yeniden oluşturmak için minimum sayıda parça gereklidir. Eşik şemasında bu sayı, toplam parça sayısından azdır. Aksi takdirde, tüm katılımcıların orijinal sırrı yeniden oluşturması gerekir.

Üst düzey açıklama

Shamir'in Gizli Paylaşımı, bir sırrı dağıtılmış bir şekilde korumak için, çoğunlukla diğer şifreleme anahtarlarının güvenliğini sağlamak için kullanılır. Sır, adı verilen birden fazla parçaya bölünmüştür hisse. Bu hisseler, orijinal sırrı yeniden yapılandırmak için kullanılır.

Shamir'in gizli paylaşımı yoluyla sırrın kilidini açmak için minimum sayıda paylaşıma ihtiyacınız var. Bu denir eşikve sırrın kilidini açmak için gereken minimum paylaşım sayısını belirtmek için kullanılır. Bir örnek üzerinden geçelim:

Sorun: XYZ şirketinin kasasının şifresini güvence altına alması gerekiyor. AES gibi standart bir şey kullanabilirler, ama ya anahtarın sahibi yoksa veya ölürse? Ya anahtar kötü niyetli bir bilgisayar korsanı tarafından ele geçirilirse veya anahtarın sahibi haydut olur ve kasa üzerindeki gücünü kendi yararına kullanırsa?

Burası SSS'nin devreye girdiği yerdir. Kasanın şifresini şifrelemek ve XYZ Şirketi içindeki her bir yöneticiye belirli sayıda hisse tahsis edilebilen belirli sayıda hisse oluşturmak için kullanılabilir. Şimdi, yalnızca hisselerini bir araya getirirlerse kasanın kilidini açabilirler. Eşik, yönetici sayısı için uygun şekilde ayarlanabilir, böylece kasaya her zaman yetkili kişiler tarafından erişilebilir. Bir veya iki hisse yanlış ellere geçerse, diğer yöneticiler işbirliği yapmadıkça şifreyi açamazlar.

Matematiksel tanım

Amaç sırrı bölmek (örneğin, bir kasa ) içine veri parçaları öyle bir şekilde:

  1. Herhangi bir bilgi yada daha fazla parçalar yapar hesaplaması kolay. Yani tam sır herhangi bir kombinasyonundan yeniden yapılandırılabilir veri parçaları.
  2. Herhangi birinin bilgisi veya daha az adet yapraklar tamamen belirsiz olduğu için olası değerler bilgisiyle olduğu kadar muhtemel görünüyor adet. Başka bir yol söyledin, sır daha azı ile yeniden inşa edilemez adet.

Bu şemaya bir eşik şeması. eğer sonra orijinal sırrın her parçası sırrı yeniden yapılandırmak için gereklidir.

Shamir'in gizli paylaşım planı

2'den 2'ye kadar olan sonsuz sayıda polinom çizilebilir. Derece 2'nin benzersiz bir polinomunu tanımlamak için 3 nokta gereklidir. Bu görüntü yalnızca örnekleme amaçlıdır - Shamir'in şeması, polinomları bir sonlu alan, 2 boyutlu bir düzlemde gösterilemez.

Temel fikir Adi Shamir eşik şeması şudur: 2 puan tanımlamak için yeterlidir hat 3 nokta, bir parabol, Bir tanımlamak için 4 nokta kübik eğri ve bunun gibi. bir tanımlamak için noktalar polinom nın-nin derece .

Bir kullanmak istediğimizi varsayalım sırrımızı paylaşmak için eşik şeması , genellik kaybı olmaksızın, bir unsurun bir unsuru olduğu varsayılır. sonlu alan boyut nerede ve asal sayıdır.

Rastgele seç pozitif tam sayılar ile ve izin ver . Polinomu oluşturun . Herhangi birini inşa edelim bunun dışında, örneğin set almak . Her katılımcıya kullanılacak sonlu alanı tanımlayan asal ile birlikte bir nokta (polinom için sıfır olmayan bir tam sayı girdisi ve karşılık gelen tamsayı çıktısı) verilir. Bu çiftlerden polinomun katsayılarını kullanarak bulabiliriz interpolasyon. Sır, sabit terimdir .

Kullanım

Misal

Aşağıdaki örnek, temel fikri göstermektedir. Bununla birlikte, örnekteki hesaplamaların tamsayı aritmetiği kullanılarak yapıldığını unutmayın. sonlu alan aritmetiği. Bu nedenle aşağıdaki örnek mükemmel bir gizlilik sağlamaz ve Shamir'in planının gerçek bir örneği değildir. Bu yüzden bu sorunu açıklayacağız ve onu uygulamanın doğru yolunu göstereceğiz (sonlu alan aritmetiği kullanarak).

Hazırlık

Farz edin ki sırrımız 1234 .

Sırrı 6 kısma bölmek istiyoruz , 3 parçadan oluşan herhangi bir alt kümenin sırrı yeniden inşa etmek için yeterlidir. Rastgele elde ederiz sayılar: 166 ve 94.

nerede sır

Gizli paylaşımlar (puanlar) üretmek için polinomumuz bu nedenle:

Altı nokta inşa ediyoruz polinomdan:

Her katılımcıya farklı bir tek nokta veriyoruz (her ikisi de ve ). Çünkü kullanıyoruz onun yerine noktalar şundan başlar ve yok . Bu gerekli çünkü sırrıdır.

Yeniden yapılanma

Sırrı yeniden inşa etmek için 3 puan yeterli olacaktır.

Düşünmek .

Hesaplayacağız Lagrange tabanlı polinomlar:

Bu nedenle

Sırrın serbest katsayı olduğunu hatırlayın, bunun anlamı ve bitirdik.

Hesaplamalı olarak verimli yaklaşım

Polinom enterpolasyonunu kullanmanın amacının bir kaynak polinomunda bir sabit bulmak olduğunu göz önünde bulundurarak kullanma Lagrange polinomları Kullanılmayan sabitler hesaplandığından "olduğu gibi" verimli değildir.

Bulmak için Lagrange polinomlarını kullanmak için optimize edilmiş bir yaklaşım aşağıdaki gibi tanımlanır:

Sorun

Yukarıda gösterilen yöntemin sonlu alan aritmetiği yerine tamsayı aritmetiği kullanan basitleştirilmiş versiyonu iyi çalışsa da, bir güvenlik sorunu vardır: Havva hakkında çok bilgi edinir hepsiyle bulduğu.

Farz edin ki 2 noktayı bulmuş ve hala sahip değil bu yüzden teoride daha fazla bilgi edinmemesi gerekiyordu Ancak 2 noktadaki bilgileri genel bilgilerle birleştiriyor: ve o :

  1. doldurur formülü ile ve değeri
  2. (i) 'yi şu değerlerle doldurur: 's ve
  3. (i) 'yi şu değerlerle doldurur: 's ve
  4. (iii) - (ii): ve bunu olarak yeniden yazar
  5. Bunu biliyor bu yüzden değiştirmeye başlar (iv) ile 0, 1, 2, 3, ... için tüm olası değerleri bulmak için :
    Sonra durur çünkü devam ederse negatif değerler alacağını düşünür. (ki bu imkansız çünkü ), şimdi sonuçlandırabilir
  6. yerine geçer (ii) 'de (iv) ile:
  7. (vi) yerine geçer (v) 'de bulunan değerlere göre bu onu bilgiye götürür:
Artık sonsuz sayıda doğal sayı yerine tahmin edilebilecek yalnızca 150 sayı var.

Çözüm

Bu, sonlu bir alan üzerinde bir polinom eğrisidir - şimdi polinomun sırasının grafiğin şekli ile pek ilgisi yoktur.

Geometrik olarak bu saldırı, polinomun sırasını bildiğimiz ve böylece bilinen noktalar arasında izleyebileceği yollara ilişkin fikir edinme gerçeğinden yararlanır. Bu, düzgün bir eğri üzerinde uzanması gerektiğinden, bilinmeyen noktaların olası değerlerini azaltır.

Bu problem sonlu alan aritmetiği kullanılarak düzeltilebilir. Bir boyut alanı kullanıldı. Grafik, sonlu bir alan üzerinde bir polinom eğrisi gösterir, normal pürüzsüz eğrinin aksine, çok düzensiz ve ayrık görünür.

Pratikte bu sadece küçük bir değişikliktir, sadece bir asal seçmemiz gerektiği anlamına gelir. bu katılımcı sayısından daha büyük ve (dahil olmak üzere ) ve noktaları şu şekilde hesaplamalıyız onun yerine .

Puan alan herkesin değerini de bilmek zorunda olduğu için , kamuya açık olarak bilindiği düşünülebilir. Bu nedenle, kişi için bir değer seçilmelidir bu çok düşük değil.

Bu örnek için seçiyoruz , böylece polinomumuz hangi puanları verir:

Bu sefer Eve bir (o sahip olana kadar puan).

Tekrar varsayalım ki, Havva ve , bu sefer genel bilgi: yani o:

  1. doldurur formülü ile ve değeri ve :
  2. (i) 'yi şu değerlerle doldurur: 's ve
  3. (i) 'yi şu değerlerle doldurur: 's ve
  4. (iii) - (ii): ve bunu olarak yeniden yazar
  5. Bunu biliyor bu yüzden değiştirmeye başlar (iv) ile 0, 1, 2, 3, ... için tüm olası değerleri bulmak için :

Bu sefer duramaz çünkü herhangi bir tam sayı olabilir (negatif olsa bile ) böylece sonsuz miktarda olası değer vardır . Bunu biliyor her zaman 3 azalır, bu nedenle ile bölünebilirdi sonuçlandırabilirdi ama asal olduğu için bunu bile bitiremiyor ve bu yüzden herhangi bir bilgi kazanmadı.

Python örneği

"""Shamir'in Gizli Paylaşımının aşağıdaki Python uygulaması şöyledir:CC0 ve OWFa koşulları altında Public Domain'de yayınlanmıştır:https://creativecommons.org/publicdomain/zero/1.0/http://www.openwebfoundation.org/legal/the-owf-1-0-agreements/owfa-1-0Kullanım için alt birkaç satıra bakın. Python 2 ve 3 üzerinde test edilmiştir."""itibaren __ gelecek__ ithalat bölünmeitibaren __ gelecek__ ithalat print_functionithalat rastgeleithalat functools# 12. Mersenne Prime# (bu uygulama için en yakın bilinen bir asal sayı istiyoruz# güvenlik seviyemize mümkün; Örneğin. 128 istenen güvenlik seviyesi# bit - çok büyük ve tüm şifreli metin büyük; çok küçük ve# güvenlik ihlal edildi)_ÖNEMLİ = 2 ** 127 - 113. Mersenne Prime 2 ** 521 - 1'dir_RINT = functools.kısmi(rastgele.SystemRandom().randint, 0)def _eval_at(poli, x, önemli):    "" "X'teki polinomu (katsayı demeti) değerlendirir, bir    aşağıdaki make_random_shares içindeki shamir havuzu.    """    biriktirmek = 0    için katsayı içinde ters(poli):        biriktirmek *= x        biriktirmek += katsayı        biriktirmek %= önemli    dönüş biriktirmekdef make_random_shares(minimum, hisse, önemli=_ÖNEMLİ):    """    Rastgele bir shamir havuzu oluşturur, sırrı ve paylaşımı döndürür    puan.    """    Eğer minimum > hisse:        yükseltmek Değer Hatası("Havuz sırrı kurtarılamaz.")    poli = [_RINT(önemli - 1) için ben içinde Aralık(minimum)]    puan = [(ben, _eval_at(poli, ben, önemli))              için ben içinde Aralık(1, hisse + 1)]    dönüş poli[0], puandef _extended_gcd(a, b):    """    P tamsayı modülündeki bölme, p'nin tersini bulmak anlamına gelir    payda modulo p ve ardından pay bunun ile çarpılması    ters (Not: A'nın tersi B'dir, öyle ki A * B% p == 1)    genişletilmiş Öklid algoritması ile hesaplanabilir    http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation    """    x = 0    last_x = 1    y = 1    last_y = 0    süre b != 0:        alıntı = a // b        a, b = b, a % b        x, last_x = last_x - alıntı * x, x        y, last_y = last_y - alıntı * y, y    dönüş last_x, last_ydef _divmod(num, den, p):    "" "Hesaplama numarası / den modulo asal p    Bunun ne anlama geldiğini açıklamak için, dönüş değeri şöyle olacaktır:    aşağıdaki doğrudur: den * _divmod (num, den, p)% p == num    """    inv, _ = _extended_gcd(den, p)    dönüş num * invdef _lagrange_interpolate(x, x_s, y_s, p):    """    Verilen x için, n (x, y) puanı verildiğinde y değerini bulun;    k puan, kinci sıraya kadar bir polinomu tanımlayacaktır.    """    k = len(x_s)    iddia etmek k == len(Ayarlamak(x_s)), "puanlar farklı olmalıdır"    def PI(vals):  # büyük harfli PI - girişlerin çarpımı        biriktirmek = 1        için v içinde vals:            biriktirmek *= v        dönüş biriktirmek    Nums = []  # kesin olmayan bölmeden kaçının    dens = []    için ben içinde Aralık(k):        diğerleri = liste(x_s)        cur = diğerleri.pop(ben)        Nums.eklemek(PI(x - Ö için Ö içinde diğerleri))        dens.eklemek(PI(cur - Ö için Ö içinde diğerleri))    den = PI(dens)    num = toplam([_divmod(Nums[ben] * den * y_s[ben] % p, dens[ben], p)               için ben içinde Aralık(k)])    dönüş (_divmod(num, den, p) + p) % pdef recovery_secret(hisse, önemli=_ÖNEMLİ):    """    Paylaşım noktalarından sırrı kurtarın    (polinom üzerinde x, y noktaları).    """    Eğer len(hisse) < 2:        yükseltmek Değer Hatası("en az iki paylaşıma ihtiyaç var")    x_s, y_s = zip(*hisse)    dönüş _lagrange_interpolate(0, x_s, y_s, önemli)def ana():    """Ana işlev"""    gizli, hisse = make_random_shares(minimum=3, hisse=6)    Yazdır('Sır:',          gizli)    Yazdır("Paylar:")    Eğer hisse:        için Paylaş içinde hisse:            Yazdır('  ', Paylaş)    Yazdır('Sır, minimum hisse alt kümesinden kurtarıldı:',          recovery_secret(hisse[:3]))    Yazdır("Sır, farklı bir minimum hisse alt kümesinden kurtarıldı:",          recovery_secret(hisse[-3:]))Eğer __name__ == '__ana__':    ana()

Özellikleri

Shamir'in faydalı özelliklerinden bazıları eşik şeması:

  1. Güvenli: Bilgi teorik güvenliği.
  2. En az: Her bir parçanın boyutu orijinal verilerin boyutunu aşmaz.
  3. Genişletilebilir: Ne zaman sabit tutulur, parçalar diğer parçaları etkilemeden dinamik olarak eklenebilir veya silinebilir.
  4. Dinamik: Güvenlik, sırrı değiştirmeden, ancak ara sıra polinomu değiştirerek (aynı serbest terimi koruyarak) ve katılımcılara yeni paylaşımlar oluşturarak kolayca artırılabilir.
  5. Esnek: Hiyerarşinin önemli olduğu organizasyonlarda her katılımcıya organizasyon içindeki önemine göre farklı sayıda parça temin edebiliriz. Örneğin, başkan kasayı tek başına açabilir, oysa kilidi açmak için 3 sekreterin birlikte olması gerekir.

Shamir'in Gizli Paylaşım planındaki bilinen bir sorun, yeniden yapılanma sürecinde alınan hisselerin doğruluğunun doğrulanmasıdır. doğrulanabilir gizli paylaşım. Doğrulanabilir gizli paylaşım, hissedarların dürüst olduklarını ve sahte paylaşımlar vermediklerini doğrulamayı amaçlar.

Ayrıca bakınız

Referanslar

  • Shamir, Adi (1979), "Sır nasıl paylaşılır", ACM'nin iletişimi, 22 (11): 612–613, doi:10.1145/359168.359176, S2CID  16321225.
  • Benzekki, K. (2017), "Güvenli MultiCloud Depolama İçin Doğrulanabilir Bir Gizli Paylaşım Yaklaşımı", Yaygın Ağ Oluşturmada, Bilgisayar Bilimleri Ders Notları, Kazablanka: Springer, 10542: 225–234, doi:10.1007/978-3-319-68179-5_20, ISBN  978-3-319-68178-8.

Dış bağlantılar