Секретний розподіл Шаміра: Розбиття секрету так, щоб жодна людина самостійно не могла його відновити

Задача: Довіра без єдиної точки відмови

Чутливі секрети, як-от головний ключ, який розблоковує весь зашифрований базис даних компанії, створюють незручну дилему. Якщо надати ключ одній людині, то у вас є єдина точка відмови: людина може втратити його, бути підкупом або зловживати ним. Якщо надати повну копію кільком людям, ви множите ризик замість того, щоб зменшити його, оскільки тепер будь-хто з них окремо може розголосити або зловживати секретом. Те, що організації насправді хочуть, це схема порогу: розділити секрет на частини, які називаються частками, і розподілити одну частку серед кількох довірених людей таким чином, щоб будь-яка група принаймні у певній кількості (наприклад, будь-які три з п’яти акціонерів) могла об'єднати свої частки для відновлення оригінального секрету, але менша група, навіть дві з п’яти акціонерів, ні в якому разі не отримує жодної переваги, навіть часткового уявлення про те, що це за секрет. Це набагато сильніша гарантія, ніж звичайне розділення паролів або шифрування, оскільки воно має діяти навіть проти акціонерів, які готові поділитися всьому, що вони знають, і спробувати всі трюки, щоб відгадати решту. До 1979 року паперу Шаміра, побудови такої схеми з непохитними математичними гарантіями, а не просто неформальною невизначеністю, було очевидно.

Прорив полягав у визнанні того, що класичний інструмент з алгебри, той факт, що криві визначаються певним числом точок, може бути переосмислений як криптографічна первинна, з доведеною безпекою.

Витончений трюк: Приховування таємниці всередині полінома

Ідея Шаміра полягала в тому, щоб закодувати таємницю як одне число і потім приховати це число як коефіцієнт випадково згенерованого полінома. Щоб побудувати схему, за якої будь-яка група k частів може відновити таємницю, генерується випадковий поліном ступеня k мінус 1, тобто в ньому k коефіцієнтів. Постійний член цього полінома, його значення при нулю, встановлюється рівним таємниці, а всі інші коефіцієнти повністю випадково обираються. Цей поліном визначає криву, і уповноважений розробник обчислює n різних точок на цій кривій, по одній для кожної з n осіб, які будуть тримати частку; частка є просто парою вхідних значень та вихідним значенням полінома при цьому значенні. Розповсюдження цих точок - це розповсюдження частин. Це працює завдяки класичному факту з алгебри: поліном ступеня k мінус 1 унікально визначається точно k точками на його кривій. За будь-яку з k частин власники можуть виконати інтерполяцію Лагранжа, добре відомий метод для відновлення унікального полінома, що проходить через заданий набір точок, і як тільки вони відновили повний поліном, вони просто читають його постійний член, значення при нулю, щоб відновити таємницю. Усі арифметичні операції зазвичай виконуються в кінцевому полі, а не над звичайними реальними числами, що підтримує числа в межах і робить гарантії безпеки математично чистими та доведеними.

Чому k точок розкриває все і k мінус один розкриває нічого

Справді красива частина схеми Шамира полягає не тільки в тому, що k частки достатні, але й у тому, що k мінус одна частка доводиться абсолютно безглуздою. З точністю до k точок існує лише один і єдиний поліном ступеня k мінус один, який проходить через всі їх, отже реконструкція однозначна та точна. Але якщо забрати навіть одну з цих точок, залишивши лише k мінус одна частки, ситуація повністю змінюється: існує нескінченна кількість поліномів ступеня k мінус один, які проходять через ці k мінус одна точки, і, що важливо, для будь-якого можливого значення секрету існує певний поліном відповідної степені, який узгоджується з усіма відомими частками, чиєму константному члену відповідає це значення. Іншими словами, k мінус одна частки математично послідовні з абсолютно будь-яким можливим секретом, що означає, що акціонери не отримали жодної інформації, не йдеться про зміщення ймовірності, не обмежується діапазон припущень, буквально нічого, окрім того, що вони знали, побачивши будь-які частки. Ця властивість називається інформаційною безпекою, і це набагато сильніша гарантія, ніж у більшості криптографічних систем, оскільки вона тримає навіть проти супротивника з необмеженими обчислювальними можливостями. Немає ніякого хитрого обчислення, ніякого грубого пошуку, ніякого часткового скорочення, яке б допомогло групі нижче порогу; секрет не просто важко знайти, він справді невизначений інформацією, яку вони мають.

Приклад Розрахунку: Двоє з Трьох Обмінюють Інформацією За Допомогою Прямої Лінії

Найпростіша версія схеми використовує поріг у два, тобто достатньо будь-яких двох з трьох обмінних частин, і не потребує складнішого, ніж пряма лінія, оскільки лінія є поліномом ступеня один та унікально визначається точно двома точками. Припустимо, секрет – це число 10. Уповноважений випадковим чином обирає пряму лінію, значення якої при нулі дорівнює 10, наприклад, лінію, задану рівнянням y = 10 + 3x. Зверніть увагу, що 3 тут є випадково обраним коефіцієнтом, а 10, значення при нулі, – це прихований секрет. Уповноважений обчислює три обмінні частини шляхом оцінки цієї лінії в трьох різних значеннях x: при x = 1, y = 13, що дає обмінну точку одну, тринадцять; при x = 2, y = 16, що дає обмінну точку дві, шістнадцять; і при x = 3, y = 19, що дає обмінну точку три, дев'ятнадцять. Кожен з трьох людей отримує точно одну з цих трьох точок та нічого іншого. Якщо будь-які дві обмінні частини зустрічаються, наприклад, власники однієї, тринадцяти та трьох, дев’ятнадцять, вони можуть підібрати унікальну лінію, що проходить через ці дві точки, використовуючи просту алгебру, дізнатися, що її значення при нулі дорівнює 10 і таким чином відновити секрет. Але якщо доступна лише одна обмінна частина, наприклад, власник двох, шістнадцять, то ця єдина точка лежить на нескінченній кількості можливих ліній, кожна з яких передбачає різний секрет, тому жодна інформація про число 10 не розкривається.

Практичне застосування: захист кореневих ключів та цифрових багатств

Метод Шамира у секретному розподілі значно виходить за межі академічного інтересу та впроваджується в сучасну інфраструктуру, де окремий кореневий ключ просто надто небезпечний довірити одній особі або машині. Поширений шаблон – це розділення головного криптографічного ключа між кількома керівниками або довіреними адміністраторами, щоб жодна людина, навіть якщо вона буде скомпрометована, недбалою чи підданою тиску, не могла самостійно розблокувати критичні системи; відновлення ключа вимагає консенсусу кількох осіб, що також захищає від втрати або забуття ключа однією особою. HashiCorp Vault, широко використовуваний інструмент для керування секретами та шифрувальними ключами в сучасній інфраструктурі, використовує цю саму схему для процесу розблокування, розподіляючи частини ключів кільком операторам так, щоб розблокувати шафу після перезавантаження вимагало б певної кількості їхньої співпраці. У світі криптовалют рішення щодо зберігання великих коштів часто застосовують ту ж логіку до приватних ключів або насіння гаманців, розділяючи їх між географічно віддаленими частинами або обладнанням так, щоб окремо вкрадений пристрій, зламаний ноутбук або зловмисний внутрішній працівник не могли вичерпати кошти, тоді як законні власники все ще можуть отримати доступ до них, об'єднавши достатню кількість частин. Та сама основна логіка також проявляється у захищених багатосторонніх обчисленнях, плануванні аварійного відновлення секретів організації та будь-якій ситуації, де розподілена довіра потребує математичного фундаменту замість простого процедурного політики.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Shamir's Secret Sharing: Splitting a Secret So No Single Person Can Reconstruct It Alone і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.