Представим, что у нас есть секрет — пароль, код от сейфа, ключ от криптокошелька. Мы хотим спрятать его так, чтобы открыть могли только несколько человек вместе. В статье — схема Шамира на одних точках и линиях, без многочленов и формул.
Главное
- Любой секрет — пароль, файл, ключ — для компьютера это число; для картинок берём простую семёрку.
- Кривая проходит через секрет на оси Y; каждому — точка. K точек задают одну кривую; K − 1 — бесконечно много.
- Прямая — кворум 2; каждый изгиб добавляет одного человека в кворум (парабола → 3, два изгиба → 4).
- В настоящей криптографии считают по большому конечному полю, а не на прямой — тогда одна доля не даёт даже намёка на «окрестность».
Сначала маленькая оговорка: секрет — это всегда число
Возможно, прямо сейчас у вас в голове крутится мысль: «секрет — это же пароль qwerty123, или ключевая фраза, или PDF-файл. Какое отношение к этому имеют точки и линии?»
Дело в том, что с точки зрения компьютера всё уже является числом. Просто очень большим.
Каждая буква в памяти — это число (латинская «A» — 65, «B» — 66, и так дальше; для кириллицы и эмодзи числа крупнее). Слово — это последовательность таких чисел, склеенных в одно длинное. Файл картинки, PDF, видео — это тоже последовательности байтов, то есть одно гигантское число.
Пароль qwerty123 для компьютера — число длиной примерно в двадцать знаков. Криптокошельковый ключ — число длиной в семьдесят-восемьдесят цифр. Файл — число с миллионами цифр. Любой секрет в мире — это число. Просто большое.
Дальше в статье на месте секрета будет стоять скромная семёрка — это для наглядности картинок. Но всё, что мы с ней проделаем, точно так же работает с числом из ста цифр.
Один человек: просто бумажка
Самый простой случай: я записал секрет на бумажку и положил в карман. Если потеряю бумажку — секрет потерян навсегда. Если её найдёт кто-то посторонний — секрет украден.
Хочется чего-то получше. А именно: разделить секрет между несколькими людьми так, чтобы:
- каждый по отдельности ничего не знал;
- а собравшись вместе — могли его восстановить.
Двое: достаточно нарисовать прямую
Возьмём наш секрет — пусть это число 7 — и поместим его на координатную плоскость в точку (0, 7). То есть «секрет» — это место, где наша линия пересекает вертикальную ось.
Теперь проведём через эту точку какую-нибудь прямую. Любую. Просто наклоним её под случайным углом. И отметим на ней пару других точек — например, при x = 1, 2, 3. Раздадим эти точки трём людям.
Алиса получает (1, 11), Боб — (2, 15), Кэрол — (3, 19). Звёздочка на оси Y — это секрет, и его никто не видит.
Зачем так? А вот зачем.
Через две точки проходит ровно одна прямая
Это всё, что нам нужно знать из геометрии. Если у двух людей есть свои точки, они кладут их рядом, прикладывают линейку — и получают ровно ту самую прямую, которой мы пользовались. Продлевают её влево до оси Y, читают значение — это и есть наш секрет.
А почему один человек ничего не знает?
Вот здесь та самая магия. У Алисы есть только её точка (1, 11). И она хочет угадать секрет в одиночку. Но проблема — через одну точку можно провести бесконечно много прямых.
И каждая из этих прямых пересекает ось Y в своём месте. Какая-то даёт секрет 19, какая-то 7, какая-то −3. Алиса не знает, какая из них «настоящая» — у неё нет ни одной зацепки. Любое число одинаково правдоподобно.
Это не «мало информации» — это никакой конкретной зацепки. Угадывать секрет, имея одну точку, ничем не лучше, чем выбирать наугад из всей бесконечной числовой прямой. (Небольшая оговорка к этому утверждению будет в конце — но она ничего не ломает.)
Можно делить на сколько угодно частей
Заметьте: мы можем отметить на той же прямой не три точки, а пять, или десять, или сто. И раздать их сотне людей. Любые двое из них смогут восстановить прямую и достать секрет. А любой один по-прежнему не знает ничего.
Так мы получили схему «2 из N»: сколько бы людей ни было — кворум всегда 2.
Хочется кворум побольше
А что, если мы хотим, чтобы для открытия секрета собирались трое, а не двое? Двух недостаточно.
Возвращаемся к геометрии. Что ломает наш трюк с прямой, если мы хотим, чтобы двое не могли договориться? Дело в том, что двое всегда могут — через любые две точки проходит одна прямая. Значит, нам нужна не прямая.
Тут включается красивый фокус: мы загибаем нашу линию.
Один изгиб — и кворум становится 3
Делаем то же самое, но рисуем не прямую, а кривую с одним изгибом — то, что в школе называли параболой. Секрет по-прежнему живёт там, где кривая пересекает ось Y. Точки раздаём людям так же.
И вот ключевой геометрический факт, на котором всё держится:
Если двое попробуют сговориться — у них всего две точки, и через них можно провести любое количество разных парабол. Каждая укажет на свой секрет:
А вот трое — найдут только одну параболу. Продлят её влево до оси Y, прочитают секрет.
Заметьте симметрию: то же самое, что было с прямой и одним человеком, теперь повторяется с параболой и двумя. Каждый «изгиб» добавляет одного человека в кворум.
А если нужны четверо? Пятеро?
Логика та же. Хочется кворум 4 — рисуем кривую с двумя изгибами. Через 4 точки такая кривая проходит ровно одна; через 3 — бесконечно много, и снова никакой информации.
Что мы получили
Совершенно понятный и наглядный способ делить любой секрет:
- Решили, сколько человек должно собираться для восстановления — например, K.
- Нарисовали кривую с нужным числом изгибов (на один меньше, чем K), проходящую через секрет на оси Y.
- Отметили на ней столько точек, сколько у нас участников — хоть три, хоть тридцать.
- Раздали каждому по точке. Саму кривую и секрет — стёрли.
Теперь любые K человек могут сложить свои точки, восстановить кривую и достать секрет. А K минус один не могут вообще ничего — у них в руках бесконечно много возможных кривых, и каждая указывает на свой ответ.
Это и есть схема Шамира — придумана в 1979 году, до сих пор используется везде, где нужно делить ключи между людьми: от криптокошельков до банковских хранилищ. И вся она держится на одном школьном наблюдении про точки и линии.
Маленькая честная оговорка
Выше я сказал, что один человек со своей точкой не знает ничего. Геометрически — это правда: подходящих прямых бесконечно много, и каждая указывает на свой секрет. Все варианты на бумаге равноправны.
Но если присмотреться, есть нюанс. Допустим, Алисе досталась точка (1, 11). Чисто математически секретом может оказаться и 7, и миллион, и минус миллиард — кривых, проходящих через её точку, бесконечно много. А вот по-человечески Алиса всё-таки кое-что подозревает: раз её собственное число — 11, то наклон кривой, вероятно, не миллион, а что-то скромное. Значит, и секрет, скорее всего, где-то рядом — не миллиард и не минус миллиард, а число того же порядка.
Это не «знание секрета», но и не полная темнота. Это догадка об окрестности — о том, в какой части числовой прямой стоит искать. Для серьёзной криптографии такой просвет уже неприемлем: представьте, что секрет — это ключ от криптокошелька на десять миллионов долларов, и у атакующего есть подсказка «ищите в диапазоне от нуля до миллиарда» вместо «ищите где угодно во вселенной чисел».
Чтобы этот последний клочок информации убрать, в настоящей криптографии работают не на обычной числовой прямой, а «по кругу» — как часы, где после двенадцати снова идёт час. Только круг очень большой: с миллиардами миллиардов делений. На таком круге понятия «большое число» и «маленькое число» теряют смысл: пройдя круг достаточное число раз, любое число оказывается в любом месте, и распределение точек становится по-настоящему равномерным. Тогда — и только тогда — одна точка действительно не несёт никакой информации о секрете, ни конкретной, ни приблизительной.
Но геометрическая суть от этого не меняется: те же кривые, те же точки, тот же принцип «через K точек проходит ровно одна, через K−1 — бесконечно много». Просто плоскость, на которой всё нарисовано, замкнули в большой круг.
Поиграйте сами
Покрутите ползунки. K — это сколько человек нужно собрать, чтобы открыть секрет. N — сколько всего участников. Кликайте на точки, чтобы «собирать» кворум: пока выбрано меньше K, видно пучок возможных кривых, и каждая «угадывает» свой секрет. Как только выбрано ровно K — единственная кривая находит настоящий секрет на оси Y.
Кривая и секрет генерируются заново при каждом изменении ползунков. Реальная геометрия Шамира — ровно эта.