Bir senaryoyu düşünelim, bankacılık oturumunun güvenliğini sağlamak gerekiyor. Bu, size işe başladığınız gün verilen anahtar olmadan tamamen erişilemez kabul edilir. Amacınız, anahtarı güvenli bir şekilde saklamaktır.

Diyelim ki anahtarı her zaman yanınızda tutmaya karar verdiniz, gerektiğinde oturuma erişim sağlayarak. Ancak, oturumu açmak için her seferinde fiziksel varlığınızın gerektiğini fark edeceksiniz ki bu pratikte ölçeklenebilir bir çözüm değil. Peki, size vaat edilen tatile ne olacak? Ayrıca, tek anahtarınızı kaybetmeniz durumunda daha korkutucu bir soru ortaya çıkıyor.

Tatil düşüncesiyle, anahtarın bir kopyasını yapmaya ve başka bir çalışana emanet etmeye karar verdiniz. Ancak bunun da ideal olmadığını anlıyorsunuz. Anahtar sayısını iki katına çıkardığınızda, anahtarın çalınma olasılığını da artırmış oluyorsunuz.

Umutsuzca, kopyayı yok ediyorsunuz ve asıl anahtarı iki parçaya ayırmaya karar veriyorsunuz. Artık düşünüyorsunuz ki, anahtarın parçalarını taşıyan iki güvenilir kişinin fiziksel olarak bulunması gerekiyor ki anahtarı birleştirip oturumu açsınlar. Bu, birinin iki parça çalmasını gerektiriyor ki bu da bir anahtar çalmaktan iki kat daha zor. Ancak, birinin anahtarın yarısını kaybetmesi durumunda, tam anahtarın geri kazanılamayacağını anlamakta gecikmiyorsunuz.

Bu sorunu bir dizi ek anahtar ve kilit ile çözmek mümkündür, ancak bu yaklaşımda hızla birçok anahtar ve kilide ihtiyaç duyulacaktır. İdeal şemanızın anahtarı bölmek olduğunu düşünüyorsunuz, böylece güvenlik tamamen tek bir kişiye bağlı kalmamalı. Ayrıca, bir parçayı kaybettiğinizde (ya da bir kişi tatile gittiğinde) tüm anahtarın işlevsel kalabilmesi için belli bir parça sayısının olması gerektiğini düşünüyorusunuz.

Gizli bir sır nasıl paylaşılır

Bu tür bir anahtar yönetim şeması hakkında Adi Shamir, 1979 yılında yayınladığı çalışmasında düşünmüştür. «Gizli Paylaşım»başlıklı makalesinde anlatılmıştır. Makalede, sözde eşik şeması açıklanmakta ve gizli bir değeri (örneğin, kriptografik anahtar) etkin bir şekilde parçalara ayırma yöntemini açıklamaktadır. Daha sonra, ancak en az biz parça toplandığında, sır kolayca geri kazanılabilir. .

Güvenlik açısından, bu şemanın önemli bir özelliği, bir saldırganın en az parça yoksa tamamen hiçbir şey öğrenmemesidir. Hatta parça varlığının herhangi bir bilgi vermemesi gerekmektedir. Bu özelliğe anlamsal güvenlik.

denir.

Polinom interpolasyonu Şamir’in eşik şeması, polinom interpolasyonu kavramı etrafında inşa edilmiştir.Bu konseptlə tanış deyilsinizsə, əslində o, olduqca sadədir. Ümumiyyətlə, əgər heç vaxt qrafikdə nöqtələr çəkib, sonra onları xət və ya əyrilərlə birləşdirmisinizsə, artıq onu istifadə etmisiniz!

İki nöqtədən sonsuz sayda 2-ci dərəcəli polinom keçmək mümkündür. Onlardan yalnız birini seçmək üçün üçüncü bir nöqtə lazımdır. İllüstrasiya: Vikipediya

1-ci dərəcəli bir polinomu nəzərdən keçirək, . Əgər bu funksiyanı qrafikdə qurmaq istəyirsinizsə, neçə nöqtəyə ehtiyacınız var? Bilirik ki, bu, xətti bir funksiyadır, bu da deməkdir ki, ən azı iki nöqtə lazımdır. İndi isə 2-ci dərəcəli polinomiya baxaq, . Bu, kvadrat funksiyadır, buna görə də qrafiki qurmaq üçün ən azı üç nöqtə lazımdır. Üçüncü dərəcəli polinom haqqında necə? Ən azı dörd nöqtə. Və belə davam edir.

Bu xüsusiyyətin həqiqətən də maraqlı tərəfi ondan ibarətdir ki, polinom funksiyasının dərəcəsini və ən azı nöqtəni nəzərdən keçirərək, bu polinom funksiyası üçün əlavə nöqtələri çıxara bilərik. Bu əlavə nöqtələrin ekstrapolyasiyasına polinomial interpolasiya.

Sirrinin tərtibi

Bəlkə də burada Şamir ssenarisi işə düşür. Fərz edək ki, bizim sirrimiz — bu . Biz bunu qrafikdə bir nöqtəyə çevirə bilərik və bu nöqtəyə uyğun olan dərəcədən bir polinomiya funksiyası icad edə bilərik. Qeyd edək ki, lazım olan parça sayının eşik nöqtəsini təmin edəcək, buna görə də əgər eşiği üç parçaya qoysak, iki dərəcəli bir polinomiya funksiyası seçməliyik.

Bizim polinomumuz aşağıdakı formada olacaq: , burada və — təsadüfi seçilmiş müsbət tam ədədlər. Biz yalnız dərəcəli bir polinom qururuq, burada sabit əmsal  bizim sirrimizdir, sonrakı hər bir üzvün təsadüfi seçilmiş müsbət əmsalı var. Əvvəlki misala qayıdaraq, əgər olsalar, o zaman aşağıdakı funksiya əldə edərik: .

Bu mərhələdə biz parçalara yaratmaq üçün unikal tam ədədləri birləşdirərək , burada (çünki bu, bizim sirrimizdir). Bu nümunədə dörd parça paylaşmaq istəyirik, eşik isə üçdür, buna görə də təsadüfi nöqtələr yaradaraq bu dörd etibarlı insan, açar mühafizəçilərinə bir nöqtə göndəririk. Həmçinin insanlara bildiririk ki, çünki bu, ictimai məlumat sayılır və bərpa etmək üçün lazımdır. .

Sirrinin bərpası

Biz artıq polinomial interpolasiya anlayışını və onun Şamir infrastrukturunun əsasını müzakirə etmişik. İstənilən üç dörd etibarlı şəxslər sirrini bərpa etmək istədikdə, yalnız öz unikal nöqtələri ilə interpolasiya etmələri lazımdır. Bunun üçün onlar öz nöqtələrini müəyyən edə bilərlər. və Lagrange interpolasiya polinomunu aşağıdakı formuldan istifadə edərək hesablamaq. Əgər proqramlaşdırma sizin üçün riyaziyyatdan daha aydındırsa, onda pi əslində operatoru təsvir edir. for, bütün nəticələri çarpan, sigma isə for, hər şeyi toplayandır.

İstifadə bunu aşağıdakı kimi həll edə bilərik və ilkin polinom funksiyamızı qaytara bilərik:

Çünki bilirik ki, , bərpa sadəcə həyata keçirilir:

Təhlükəsiz olmayan tam ədəd arifmetikasından istifadə

Bizi Şamirinin əsas ideyasını uğurla tətbiq etmiş olsaq da, , indiyə qədər yaddaqalan bir problemin qaldığını görürük. Bizim polinom funksiyamız təhlükəsiz olmayan tam ədəd arifmetikasını istifadə edir. Hər əlavə nöqtə üçün, hücum edənlər bizim funksiyanın qrafikində əldə etdiyi zamana, digər nöqtələr üçün azı imkanlar qalır. Bunu tam ədədi arifmetika istifadə edərək polinom funksiyasının nöqtə sayını artırdıqca qrafik çizəndə öz gözlərinizlə görə bilərsiniz. Bu, bizə təhlükəsizliyi nəzərdə tutduğumuz məqsədə ziddir, çünki hücum edən heç bir şey bilməməlidir, nə zamana qədər ən azı fragments.

Tam ədəd arifmetikasının zəifliyi ilə bağlı bir ssenari göstərə bilərik. Hücum edən iki nöqtə əldə edərsə və ictimai məlumatların olduğunu bilir ki, . Bu məlumatdan o, , iki bərabər olmaq üzrə və məlum dəyərləri formulaya qoymaq üçün istifadə edə bilər. və .

Sonra, hücum edən tapmaq üçün :

hesablaya bilər. Çünki təsadüfi seçilmiş tam ədəd müsbət ədədlər kimi müəyyən etdiyimiz üçün, mümkün olan sayı məhduddur. Bu məlumatla, hücum edən tapmaq imkanına malikdir, çünki beşdən böyük olan hər şey

mənfi edir. Bu doğrudur, çünki biz Sonra, hücum edən mümkün dəyərləri hesablaya bilər daxilindədir. :

, üçün məhdud seçim təqdim edilərkən necə asanlıqla uyğun dəyərləri tapmaq və yoxlamaq mümkün olduğunu göstərir.

Burada yalnız beş variant var.

Təhlükəsiz olmayan tam ədəd arifmetikasının problemini həll etmək buna , burada və Bu zəifliyi aradan qaldırmaq üçün, Şamir modulyar arifmetikadan istifadə etməyi təklif edir,

— bütün sadə ədədlərin cəmidir. Modulyar arifmetikanın necə işlədiyini tez yadıma salaq. Saatlar — artıq tanış konsepsiyadır. Bu, saatları istifadə edir, hansı ki, olar ki, onlardir. Saat göstəricisi on iki keçəndə birə qayıdır. Bu sistemin maraqlı xüsusiyyəti odur ki, sadəcə saatlara baxaraq, saat göstəricisi neçə dövr keçdiyini bilmək olmur. Ancaq əgər biz bilsək ki, saat göstəricisi 12-dən dörd dəfə keçib, sadə bir formulla keçən saatların sayını tam müəyyən etmək mümkündür. , burada  — bu bizim bölücümüzdür (burada ),  — bu katsayıdır (bölücü, tam olarak kaç kez ana sayıya geçer, burada ), və  — bu genellikle mod operatörü çağrısının döndürdüğü kalandır (burada ). Bu değerlerin hepsini bilmek, denklemi çözmemizi sağlar, , ancak katsayıyı atlarsak, başlangıç değerini asla geri kazanamayız.

Bunun, önceki örneğimize uygulayarak ve güvenliğimizi nasıl artırdığını gösterebiliriz. Yeni polinom fonksiyonumuz , yeni noktalar ise . Artık anahtar sahipleri, toplama ve çarpma işlemlerinin mod alarak gerçekleştirilmesi gerektiği bu sefer polinom interpolasyonunu yeniden kullanabilirler (örneğin, ).

Bu yeni örneği kullanarak, varsayalım ki bir saldırgan bu yeni noktalardan ikisini öğrendi, , ve kamuya açık bilgi . Bu sefer saldırgan, elindeki tüm bilgilere dayanarak şu işlevleri çıkarıyor, burada  — tüm pozitif tam sayıların kümesi, ve modülün katsayısını temsil eder. .

Şimdi saldırganımız tekrar şunları buluyor, , hesaplayarak :

Sonra tekrar çıkarmaya çalışıyor, Sonra, hücum edən mümkün dəyərləri hesablaya bilər daxilindədir. :

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

Güvenlik düşünceleri

Shamir'in gizli paylaşım şeması, bilgi teorisi açısından güvenlik sunar.. Bu, matematiğin sınırsız hesaplama gücüne sahip bir saldırgana karşı bile dayanıklı olduğu anlamına gelir. Ancak şemanın hala bilinen bazı sorunları vardır.

Örneğin, Shamir'in şeması, doğrulanabilir parçalaroluşturmaz, yani insanlar sahte parçaları serbestçe sunabilir ve doğru sırrın kurtarılmasını engelleyebilir. Yeterli bilgiye sahip olan düşman bir parça bile üretebilir, istediği şekilde değiştirerek. Bu sorun, doğrulanabilir gizli paylaşım şemaları, Feldman şeması gibi, kullanılarak çözülür.

Başka bir sorun ise, herhangi bir parçanın uzunluğunun ilgili sıranın uzunluğuna eşit olmasıdır; böylece sıranın uzunluğu kolayca belirlenebilir. Bu sorun, sırayı sabit bir uzunluğa kadar rastgele sayılarla doldurarak basitçe çözülür. şəkil uzunluğuna qədər təsadüfi ədədlərin sirri.

Nəhayət, bizim təhlükəsizliklə bağlı narahatlıqlarımız yalnız əsas sxemlə kifayətlənmir. Həqiqi kriptoqrafiya tətbiqlərində çox vaxt xarici kanallar vasitəsilə hücumlar təhlükəsi var, burada hücumçu proqramın icra müddətindən, keşləmə, qəza və s. məlumatları əldə etməyə çalışır. Əgər bu narahatlıq doğurursa, inkişaf zamanı mühafizə tədbirlərinin istifadəsini diqqətlə nəzərdən keçirmək, məsələn, sabit icra müddətinə əsaslanan funksiyaları nəzərə almaq, yaddaşı diske saxlamağı qarşısını almaq və bu məqalədən kənarda bir sıra digər məsələləri düşünmək lazımdır.

Demo

Üçün bu səhifədə Şamirin gizli bölüşdürmə sxeminin interaktiv nümayişi var. Nümayiş ssss-js, populyar proqramın JavaScript portu olan ssssdır. Böyük dəyərləri hesablamaq üçün , və biraz vaxt lazım ola bilər.

Mənbə: habr.com