Bir banka kasasını güvence altına almanız gereken bir senaryoyu düşünün. İşinizin ilk gününde size verilen anahtar olmadan kesinlikle zaptedilemez kabul edilir. Amacınız anahtarı güvenli bir şekilde saklamaktır.

Diyelim ki, gerektiğinde depolamaya erişim sağlayarak anahtarı her zaman yanınızda tutmaya karar verdiniz. Ancak böyle bir çözümün pratikte pek iyi ölçeklenmediğini hemen fark edeceksiniz, çünkü depolamayı her açtığınızda fiziksel varlığınız gerekli olacaktır. Peki ya sana söz verilen tatil? Üstelik soru daha da korkutucu: Ya tek anahtarınızı kaybederseniz?

Tatilinizi aklınızda tutarak anahtarın bir kopyasını alıp onu başka bir çalışana emanet etmeye karar veriyorsunuz. Ancak bunun da ideal olmadığını anlıyorsunuz. Anahtar sayısını iki katına çıkararak anahtar hırsızlığı olasılığını da iki katına çıkarırsınız.

Çaresizlik içinde kopyayı yok edersiniz ve orijinal anahtarı ikiye bölmeye karar verirsiniz. Şimdi, anahtarı almak ve kasayı açmak için anahtar parçalarına sahip iki güvenilir kişinin fiziksel olarak orada olması gerektiğini düşünürsünüz. Bu, bir hırsızın iki parçayı çalması gerektiği anlamına gelir ki bu, bir anahtarı çalmaktan iki kat daha zordur. Ancak çok geçmeden bu planın tek bir anahtardan çok daha iyi olmadığını anlarsınız çünkü birisi anahtarın yarısını kaybederse anahtarın tamamı kurtarılamaz.

Sorun bir dizi ek anahtar ve kilitle çözülebilir, ancak bu yaklaşım hızlı bir şekilde gerekli olacaktır. çok anahtarlar ve kilitler. Güvenliğin tamamen tek bir kişiye bağlı olmaması için ideal tasarımın anahtarı paylaşmak olduğuna karar veriyorsunuz. Ayrıca, bir parça kaybolursa (veya bir kişi tatile çıkarsa) anahtarın tamamının işlevsel kalması için parça sayısı için bir eşik olması gerektiği sonucuna varırsınız.

Bir sır nasıl paylaşılır

Bu tür bir anahtar yönetim şeması, Adi Shamir tarafından 1979'da çalışmasını yayınladığında düşünülmüştü. "Bir sır nasıl paylaşılır". Makale kısaca sözde açıklıyor Gizli bir değeri (şifreleme anahtarı gibi) verimli bir şekilde bölmek için eşik şeması parçalar. O zaman, ne zaman ve yalnızca en azından ne zaman arasında parçalar monte edildiğinde sırrı kolayca geri yükleyebilirsiniz .

Güvenlik açısından bakıldığında, bu planın önemli bir özelliği, saldırganın en azından bilgi sahibi olmadığı sürece kesinlikle hiçbir şey bilmemesidir. parçalar. Varlığı bile parçalar herhangi bir bilgi vermemelidir. Biz bu mülk diyoruz anlamsal güvenlik.

Polinom enterpolasyonu

Shamir eşik şeması konsept etrafında inşa edilmiş polinom enterpolasyonu. Bu kavrama aşina değilseniz, aslında oldukça basittir. Aslında, eğer bir grafik üzerinde noktalar çizdiyseniz ve bunları çizgiler veya eğrilerle birleştirdiyseniz, bunu zaten kullanmışsınız demektir!

İki noktadan sınırsız sayıda 2. derece polinom çizebilirsiniz. Bunlardan tek olanı seçmek için üçüncü bir noktaya ihtiyacınız vardır. İllüstrasyon: Vikipedi

Derecesi bir olan bir polinomu düşünün, . Bu fonksiyonu bir grafik üzerinde çizmek istiyorsanız kaç noktaya ihtiyacınız var? Bunun bir doğru oluşturan doğrusal bir fonksiyon olduğunu ve bu nedenle en az iki noktaya ihtiyaç duyduğunu biliyoruz. Daha sonra ikinci dereceden bir polinom fonksiyonunu düşünün, . Bu ikinci dereceden bir fonksiyon olduğundan grafiği çizmek için en az üç nokta gereklidir. Üçüncü dereceli bir polinoma ne dersiniz? En az dört puan. Ve benzeri.

Bu özellik hakkında gerçekten harika olan şey, polinom fonksiyonunun derecesi göz önüne alındığında ve en azından Bu polinom fonksiyonu için ek noktalar türetebiliriz. Bu ek noktaların ekstrapolasyonunu diyoruz. polinom enterpolasyonu.

Bir sır uydurmak

Shamir'in zekice planının burada devreye girdiğini zaten fark etmiş olabilirsiniz. Hadi sırrımızı söyleyelim - Mı . Dönebiliriz grafikte bir noktaya ve dereceli bir polinom fonksiyonu bulun bu noktayı tatmin ediyor. Bunu hatırlayalım gerekli parçaların eşiğimiz olacaktır, dolayısıyla eşiği üç parçaya ayarlarsak, ikinci dereceli bir polinom fonksiyonu seçmeliyiz.

Polinomumuz şu forma sahip olacak: Nerede и — rastgele seçilmiş pozitif tam sayılar. Sadece dereceli bir polinom inşa ediyoruz burada serbest katsayı  - Bu bizim sırrımız ve sonrakilerin her biri için terimlerinde rastgele seçilmiş bir pozitif katsayı vardır. Orijinal örneğe dönersek ve şunu varsayarsak , sonra fonksiyonu elde ederiz .

Bu noktada bağlanarak parçalar oluşturabiliriz. benzersiz tamsayılar Nerede (çünkü bu bizim sırrımız). Bu örnekte, dört parçayı üç eşikle dağıtmak istiyoruz, böylece rastgele noktalar üretiyoruz ve anahtarın koruyucuları olan dört güvenilir kişiden her birine bir puan gönderin. Bunu da insanlara bildiriyoruz , çünkü bu kamuya açık bilgi olarak kabul edilir ve kurtarma için gereklidir .

Sırrı kurtarmak

Polinom enterpolasyonu kavramını ve bunun Shamir'in eşik şemasının temelini nasıl oluşturduğunu daha önce tartışmıştık. . Dört mütevelliden herhangi üçü eski durumuna dönmek istediğinde , yalnızca enterpolasyon yapmaları gerekir kendine özgü noktalarıyla. Bunu yapmak için puanlarını belirleyebilirler. ve aşağıdaki formülü kullanarak Lagrange enterpolasyon polinomunu hesaplayın. Eğer programlama sizin için matematikten daha anlaşılırsa pi aslında bir operatördür for, tüm sonuçları çarpar ve sigma for, bu da her şeyi topluyor.

at bunu şu şekilde çözebilir ve orijinal polinom fonksiyonumuzu döndürebiliriz:

Çünkü bunu biliyoruz , iyileşmek basitçe yapılır:

Güvenli olmayan tamsayı aritmetiği kullanma

Her ne kadar Shamir'in temel fikrini başarıyla uygulamış olsak da Şu ana kadar görmezden geldiğimiz bir sorunla karşı karşıyayız. Polinom fonksiyonumuz güvenli olmayan tamsayı aritmetiği kullanıyor. Bir saldırganın fonksiyonumuzun grafiğinde elde ettiği her ek puan için, diğer noktalar için daha az olasılık bulunduğunu unutmayın. Tamsayı aritmetiğini kullanarak bir polinom fonksiyonu için artan sayıda nokta çizdiğinizde bunu kendi gözlerinizle görebilirsiniz. Bu, belirtilen güvenlik hedefimize ters etki yapar çünkü saldırganın en azından bilgi sahibi olana kadar kesinlikle hiçbir şey bilmemesi gerekir. parça.

Tamsayı aritmetik devresinin ne kadar zayıf olduğunu göstermek için bir saldırganın iki puan elde ettiği bir senaryoyu düşünün. ve kamuya açık bilgileri biliyor . Bu bilgiden şu sonucu çıkarabilir ikiye eşit ve bilinen değerleri formüle yerleştir и .

Saldırgan daha sonra bulabilir , sayma :

Tanımladığımızdan beri Rastgele seçilen pozitif tam sayılar olduğundan sınırlı sayıda olası vardır. . Bir saldırgan bu bilgiyi kullanarak şu sonucu çıkarabilir: , çünkü 5'ten büyük herhangi bir şey işe yarayacaktır olumsuz. Biz belirlediğimiz için bu doğru çıkıyor

Saldırgan daha sonra olası değerleri hesaplayabilir yerine в :

Sınırlı seçeneklerle değerleri seçmenin ve kontrol etmenin ne kadar kolay olduğu anlaşılıyor . Burada sadece beş seçenek var.

Sorunu güvenli olmayan tamsayı aritmetiğiyle çözme

Bu güvenlik açığını ortadan kaldırmak için Shamir, modüler aritmetik kullanılmasını öneriyor. üzerinde Nerede и — tüm asal sayılar kümesi.

Modüler aritmetiğin nasıl çalıştığını hemen hatırlayalım. İbreli bir saat tanıdık bir kavramdır. O bir saat kullanıyor . Akrep on ikiyi geçer geçmez bire döner. Bu sistemin ilginç bir özelliği, sadece saate bakarak akrebin kaç devir yaptığını çıkaramamamızdır. Ancak akrebin 12'yi dört kez geçtiğini biliyorsak, geçen saat sayısını basit bir formül kullanarak tamamen belirleyebiliriz. Nerede  bölenimiz (burada ),  katsayıdır (bölenin orijinal sayıya kalansız kaç kez girdiği, burada ), Ve  genellikle modulo operatör çağrısını döndüren geri kalan kısımdır (burada ). Tüm bu değerleri bilmek denklemi çözmemizi sağlar , ancak katsayıyı kaçırırsak hiçbir zaman orijinal değeri geri yükleyemeyiz.

Şemayı önceki örneğimize uygulayarak ve şunu kullanarak, bunun şemamızın güvenliğini nasıl artırdığını gösterebiliriz. . Yeni polinom fonksiyonumuz ve yeni noktalar . Artık anahtar koruyucular fonksiyonumuzu yeniden yapılandırmak için bir kez daha polinom enterpolasyonunu kullanabilirler, ancak bu sefer toplama ve çarpma işlemlerine modulo indirgeme eşlik etmelidir (Örneğin ).

Bu yeni örneği kullanarak, saldırganın bu yeni noktalardan ikisini öğrendiğini varsayalım: ve kamuya açık bilgiler . Bu kez saldırgan, sahip olduğu tüm bilgilere dayanarak aşağıdaki işlevleri çıktı olarak verir:  tüm pozitif tam sayıların kümesidir ve modül katsayısını temsil eder .

Şimdi saldırganımız tekrar buluyor , Hesaplanıyor :

Sonra tekrar dener yerine в :

Bu sefer ciddi bir sorunu var. Formülde eksik değerler , и . Bu değişkenlerin sonsuz sayıda kombinasyonu olduğundan herhangi bir ek bilgi elde edemez.

Güvenlik Hususları

Shamir'in gizli paylaşım planı şunu gösteriyor bilgi teorisi açısından güvenlik. Bu, matematiğin sınırsız bilgi işlem gücüne sahip bir saldırgana karşı bile dayanıklı olduğu anlamına gelir. Ancak devrede hala bilinen birkaç sorun bulunmaktadır.

Örneğin Shamir'in planı şunu yaratmıyor: kontrol edilecek parçalaryani insanlar sahte parçaları özgürce sunabilir ve doğru sırrın kurtarılmasına müdahale edebilir. Yeterli bilgiye sahip düşmanca bir parça saklayıcısı, değişiklik yaparak başka bir parça bile üretebilir. kendi takdirinize bağlı olarak. Bu sorun kullanılarak çözüldü doğrulanabilir gizli paylaşım şemalarıFeldman'ın planı gibi.

Diğer bir sorun ise herhangi bir parçanın uzunluğunun karşılık gelen sırrın uzunluğuna eşit olması, dolayısıyla sırrın uzunluğunun belirlenmesinin kolay olmasıdır. Bu sorun önemsiz şeylerle çözülebilir dolgu malzemesi sabit bir uzunluğa kadar rastgele sayılarla sır.

Son olarak, güvenlik endişelerimizin tasarımın ötesine geçebileceğini unutmamak önemlidir. Gerçek dünyadaki kriptografik uygulamalar için, genellikle bir saldırganın uygulama yürütme süresi, önbellekleme, çökmeler vb. gibi konulardan yararlı bilgiler elde etmeye çalıştığı yan kanal saldırıları tehdidi vardır. Bu bir endişe ise, geliştirme sırasında işlevler ve sabit zamanlı aramalar gibi koruyucu önlemlerin kullanılması, belleğin diske kaydedilmesinin önlenmesi ve bu makalenin kapsamı dışında kalan diğer bazı hususlara dikkatli bir şekilde dikkat edilmelidir.

Demo

Üzerinde Bu sayfa Shamir'in gizli paylaşım planının interaktif bir gösterimi var. Kütüphaneye dayalı gösteri ssss-jskendisi de popüler programın JavaScript bağlantı noktasıdır ssss. Büyük değerlerin hesaplanmasına dikkat edin , и biraz zaman alabilir.

Kaynak: habr.com