Розглянемо сценарій, коли необхідно забезпечити безпеку банківського сховища. Воно вважається абсолютно неприступним без ключа, який вам видають у перший день роботи. Ваша мета – надійно зберегти ключ.

Припустимо, ви вирішили постійно зберігати ключ при собі, надаючи доступ до сховища при необхідності. Але ви швидко зрозумієте, що таке рішення практично нормально не масштабується, тому що кожного разу для відкриття сховища потрібна ваша фізична присутність. А як щодо відпустки, які вам обіцяли? Крім того, ще більше лякає питання: а що якщо ви втратили єдиний ключ?

З думкою про відпустку ви вирішили зробити копію ключа та довірити її іншому співробітнику. Однак ви розумієте, що це також не ідеально. Подвоюючи кількість ключів, ви також подвоїли можливості крадіжки ключа.

Зневірившись, ви знищуєте дублікат і вирішуєте розділити вихідний ключ навпіл. Тепер, ви думаєте, дві довірені особи з фрагментами ключів повинні фізично бути присутніми, щоб зібрати ключ і відкрити сховище. Це означає, що злодіїві необхідно вкрасти два фрагменти, що вдвічі важче за крадіжку одного ключа. Однак незабаром ви розумієте, що ця схема не набагато краща, ніж просто один ключ, тому що якщо хтось втратить половину ключа, повний ключ не можна відновити.

Проблему можна вирішити за допомогою серії додаткових ключів та замків, але при такому підході швидко буде потрібно багато ключів та замків. Ви вирішуєте, що в ідеальній схемі потрібно розділити ключ, щоб безпека не покладалася повністю на одну людину. Ви також робите висновок, що повинен існувати якийсь поріг кількості фрагментів, щоб при втраті одного фрагмента (або якщо людина пішла у відпустку) весь ключ залишався функціональним.

Як поділити секрет

Про такий тип схеми управління ключами думав Аді Шамір у 1979 році, коли опублікував свою роботу "Як розділити секрет". У статті коротко пояснюється так звана порогова схема для ефективного поділу секретного значення (наприклад, криптографічного ключа) на частин. Потім, коли і тільки коли хоча б з частин зібрані, можна легко відновити секрет .

З погляду безпеки важливою властивістю цієї схеми є те, що зловмисник не повинен дізнатися абсолютно нічого, якщо у нього немає хоча б частин. Навіть наявність частин не повинно давати жодної інформації. Ми називаємо цю властивість семантичною безпекою.

Поліноміальна інтерполяція

Порогова схема Шаміра побудована навколо концепції поліноміальної інтерполяції. Якщо ви не знайомі з цією концепцією, вона насправді є досить простою. Взагалі, якщо ви коли-небудь малювали крапки на графіці, а потім з'єднували їх лініями чи кривими, то вже використовували її!

Через дві точки можна провести необмежену кількість поліномів ступеня 2. Щоб вибрати з них єдиний, потрібна третя точка. Ілюстрація: Вікіпедія

Розглянемо поліном зі ступенем один, . Якщо ви хочете побудувати цю функцію на графіку, скільки точок потрібно? Ну, ми знаємо, що це лінійна функція, яка утворює лінію і тому потрібно принаймні дві точки. Далі розглянемо поліноміальну функцію зі ступенем два, . Це квадратична функція, для побудови графіка потрібно щонайменше трьох точок. Як щодо багаточлена зі ступенем три? Принаймні чотири точки. І так далі і тому подібне.

Дійсно класна річ у цій властивості полягає в тому, що, враховуючи ступінь поліноміальної функції та, принаймні, точок, ми можемо вивести додаткові точки для цієї поліноміальної функції. Екстраполяцію цих додаткових точок ми називаємо поліноміальною інтерполяцією.

Складання секрету

Можливо, ви вже зрозуміли, що тут входить у гру розумна схема Шаміра. Припустимо, що наш секрет - це . Ми можемо перетворити у точку на графіку та придумати поліноміальну функцію зі ступенем , яка задовольняє цю точку. Нагадаємо, що буде нашим порогом необхідних фрагментів, тому якщо ми встановити поріг у три фрагменти, то маємо вибрати поліноміальну функцію зі ступенем два.

Наш поліном матиме форму , Де и — випадково обрані позитивні цілі числа. Ми лише будуємо поліном зі ступенем , де вільний коефіцієнт  - це наш секрет , а у кожного з наступних членів є випадковим чином вибраний позитивний коефіцієнт. Якщо повернутися до початкового прикладу і припустити, що тоді ми отримаємо функцію .

На цьому етапі ми можемо генерувати фрагменти, підключивши унікальних цілих чисел у , Де (Бо це наш секрет). У цьому прикладі ми хочемо роздати чотири фрагменти з порогом три, тому випадково генеруємо точки і відправляємо по одній точці кожному із чотирьох довірених осіб, зберігачів ключа. Ми також повідомляємо людям, що , оскільки це вважається публічною інформацією і необхідно для відновлення .

Відновлення секрету

Ми вже обговорювали концепцію поліноміальної інтерполяції та те, що вона лежить в основі порогової схеми Шаміра . Коли будь-які три з чотирьох довірених осіб хочуть відновити їм потрібно тільки інтерполювати зі своїми унікальними точками. Для цього вони можуть визначити свої точки та розрахувати інтерполяційний поліном Лагранжа, використовуючи таку формулу. Якщо програмування вам зрозуміліше, ніж математика, то пі — це насправді оператор for, який множить усі результати, а сигма - це for, що все складає.

При ми можемо це вирішити так і повернути нашу початкову поліноміальну функцію:

Оскільки ми знаємо, що , відновлення здійснюється просто:

Використання небезпечної цілочисленної арифметики

Хоча ми успішно застосували основну ідею Шаміра , у нас залишається проблема, яку ми ігнорували досі. Наша поліноміальна функція використовує небезпечну цілу арифметику. Врахуйте, що для кожної додаткової точки, яку атакуючий отримує на графіку нашої функції, залишається менше можливостей для інших точок. Ви можете побачити це на власні очі, коли будуєте графік зі збільшенням кількості точок для поліноміальної функції за допомогою цілочисленної арифметики. Це контрпродуктивно для нашої заявленої мети безпеки, тому що зловмисник не повинен абсолютно нічого дізнатися, доки у них не буде хоча б фрагментів.

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

Потім зловмисник може знайти , порахувавши :

Оскільки ми визначили як випадково вибрані цілі позитивні числа, є обмежена кількість можливих . За допомогою цієї інформації зловмисник може вивести , оскільки все, що більше 5, зробить негативним. Це виявляється правдою, оскільки ми визначили

Потім зловмисник може розрахувати можливі значення , замінивши в :

З обмеженим набором варіантів для стає зрозуміло, наскільки легко підібрати та перевірити значення . Тут лише п'ять варіантів.

Вирішення проблеми з небезпечною цілочисленною арифметикою

Щоб усунути цю вразливість, Шамір пропонує використовувати модульну арифметику, замінивши на , Де и - Багато простих чисел.

Швидко згадаємо, як працює модульна арифметика. Годинник зі стрілками вже знайома концепція. Вона використовує годинник, який є . Щойно годинна стрілка проходить повз дванадцять, вона повертається до одного. Цікавою властивістю цієї системи є те, що просто подивившись на годинник, ми не можемо вивести, скільки обертів зробила стрілка годинника. Однак якщо ми знаємо, що годинникова стрілка чотири рази минула 12, можна повністю визначити кількість минулих годин за допомогою простої формули , Де  - це наш дільник (тут ),  - Це коефіцієнт (кілька разів дільник без залишку переходить у вихідне число, тут ), А  — це залишок, який зазвичай і повертає виклик оператора за модулем (тут ). Знання всіх цих значень дозволяє нам вирішити рівняння для але якщо ми пропустимо коефіцієнт, то ніколи не зможемо відновити вихідне значення.

Можна продемонструвати, як це покращує безпеку нашої схеми, застосувавши схему до нашого попереднього прикладу та використовуючи . Наша нова поліноміальна функція , а нові точки . Тепер зберігачі ключа можуть ще раз використовувати поліноміальну інтерполяцію для відновлення нашої функції, тільки цього разу операції додавання та множення повинні супроводжуватися скороченням по модулю (напр ).

Використовуючи цей новий приклад, припустимо, що зловмисник дізнався дві з цих нових точок, , а публічна інформація . На цей раз атакуючий на основі всієї наявної в нього інформації виводить такі функції, де  - Набір всіх позитивних цілих чисел, а представляє коефіцієнт модуля .

Тепер наш зловмисник знову знаходить , вирахувавши :

Потім він знову намагається вивести , замінивши в :

На цей раз у нього серйозна проблема. У формулі відсутні значення , и . Оскільки існує нескінченна кількість комбінацій цих змінних, вона може отримати ніякої додаткової інформації.

міркування безпеки

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

Наприклад, схема Шаміра не створює фрагментів, що перевіряютьсятобто люди можуть вільно пред'являти підроблені фрагменти і заважати відновленню правильного секрету. Ворожий зберігач фрагментів з достатньою інформацією може навіть зробити інший фрагмент, змінивши на свій розсуд. Ця проблема вирішується за допомогою схем поділу секрету, що перевіряються, такі як схема Фельдмана.

Інша проблема полягає в тому, що довжина будь-якого фрагмента дорівнює довжині відповідного секрету, тому довжину секрету легко визначити. Ця проблема вирішується тривіальною набивкою секрету довільними числами до фіксованої довжини

Нарешті, важливо зазначити, що наші побоювання щодо безпеки можуть виходити за межі самої схеми. Для реальних криптографічних додатків часто існує загроза атак сторонніми каналами, коли зловмисник намагається витягти корисну інформацію з часу виконання програми, кешування, збоїв і т.д. Якщо це викликає занепокоєння, слід під час розробки ретельно розглянути використання захисних заходів, таких як функції та пошук із постійним часом виконання, запобігти збереженню пам'яті на диску та продумати ряд інших речей, які виходять за рамки цієї статті.

демо

На цій сторінці є інтерактивна демонстрація cхема поділу секрету Шаміра. Демонстрація зроблена на базі бібліотеки ssss-jsяка сама по собі є JavaScript-портом популярної програми SSSS. Зауважте, що обчислення великих значень , и може зайняти деякий час.

Джерело: habr.com