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

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

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

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

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

Как разделить секрет

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

С точки зрения безопасности важным свойством этой схемы является то, что злоумышленник не должен узнать абсолютно ничего, если у него нет хотя бы частей. Даже наличие частей не должно давать никакой информации. Мы называем это свойство семантичною безпекою.

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

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

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

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

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

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

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

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

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

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

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

При мы можем это решить следующим образом и вернуть нашу исходную полиномиальную функцию:

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

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

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

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

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

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

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

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

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

Чтобы устранить эту уязвимость, Шамир предлагает использовать модульную арифметику, заменив на , Де и - Багато простих чисел.

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

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

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

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

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

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

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

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

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

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

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

демо

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

Джерело: habr.com