Comments 22
Огромное спасибо за статью, я врубился:) Пишите еще на тему криптографии, очень интересно. Именно то, какие возможности в принципе предоставляет современная криптография, какие задачи решает а какие нет.
Можно добавить только, что Ади Шамир — S из RSA.
А в каких библиотеках есть реализация?
Про 42 отсылка понятна. А вот откуда взялось 73?
А нам точно нужно морочиться с полиномами и тд? есть же RAID 5 (к=n-1), масштабируемый до RAID 6 (к=n-2) и большего числа теряемых блоков на контроле четности. Берем полный секретный ключ длины M, «пишем» его в нужное количество блоков длины M/k*n и раздаём каждому по кусочку. Насколько я понимаю, до сбора порогового числа блоков «рейдовая» схема не даёт никакой информации о оставшихся блоках.
Вы не поверите, но RAID5/6 — это частный случай erasure coding, для произвольных порогов существуют схемы типа кодов Рида-Соломона-Коши, и сводятся они к составлению и решению системы линейных уравнений в конечных полях, т.е. в сущности то же решение, только чуть по другому сформулированное
Да я помню про Рида-Соломона, но как-то отложилось, что там биты контрольные должны в нужных местах стоять. Ну и рассыпаны они там по всему сообщению, а в рейде как раз на куски равного размера нарезка. Ровно то, что нужно в исходной задаче.
Просто, согласно вике, код Рида — Соломона был изобретён в 1960 году. Зачем после этого схема Шамира в 1979 — не ясно.
(ладно еще законы Бойля — Мариотта, Шарля и Гей-Люссака — общее уравнение вывели последним. Но тут частный случай описанный позже имеет фамилию)
Рейды ладно, позже похоже появились. Хотя я думал что они ровесники магнитным накопителям, но похоже ошибся.
Просто, согласно вике, код Рида — Соломона был изобретён в 1960 году. Зачем после этого схема Шамира в 1979 — не ясно.
(ладно еще законы Бойля — Мариотта, Шарля и Гей-Люссака — общее уравнение вывели последним. Но тут частный случай описанный позже имеет фамилию)
Рейды ладно, позже похоже появились. Хотя я думал что они ровесники магнитным накопителям, но похоже ошибся.
В схеме Шамира знание N-1 частей никак не облегчит подбор секрета (при условии что для восстановления секрета нужно N частей), и это строго доказано. А вот для кодов Рида-Соломона, насколько я знаю, таких гарантий нет.
Если верить этой статье, то схема Шамира на самом деле и есть частный случай кодов Рида-Соломона, так что вполне возможно, что Шамир просто разработал свою схему независимо. Правда, как написал выше mrsantak он еще и строго доказал, что в его схеме знание N-1 из N частей не облегчает подбор секрета, а Рид и Соломон вроде не заморачивались на эту тему, так что научная новизна в его работе точно есть. Кстати, в той же статье есть и идеи как сделать схему Шамира более устойчивой к ситуациям когда кто-то подсовывает заведомо неверные куски, либо уменьшить амплификацию данных при разделении секрета ценой уменьшения секьюрности. Более подробно это разжевано здесь (там как раз вопрос был чем же отличаются коды Рида-Соломона от схемы Шамира с точки зрения безопасности)
В старинные времена моего раннего админства меня просили реализовать такую вещь для бэкапов. Идея была в том, что бэкап шифруется публичным ключом (который на сервере), а расшифроваться может только приватным ключом, который разделён между руководством. Схема не взлетела, потому что весь существующий софт для использования алгоритма Шамира не был способен попилить 4к блок на кусочки (слишком длинный).
С тех пор что-то поменялось?
С тех пор что-то поменялось?
Ничего не поменялось. В этом случае вам нужно зашифровать приватный ключ с помощью симметричного шифрования (например AES-256-CTR) и уже симметричный ключ делить.
А ещё лучше просто использовать PKCS#8 и разделить пароль от ключа
А, вот на это меня не хватило.
А в чём проблема использовать Шамира для больших данных? Например, секрет размером в 1Мб, чанк в 128кб. Я не думаю, что современные компьютеры взорвутся от решения уравнений с 128кб числами.
А в чём проблема использовать Шамира для больших данных? Например, секрет размером в 1Мб, чанк в 128кб. Я не думаю, что современные компьютеры взорвутся от решения уравнений с 128кб числами.
Тем, что это непрактично и небыстро. Всегда найдётся какой-то секрет, который будет длиннее имеющихся возможностей по подсчёту. Раздувая числа, которыми придётся оперировать, ёмкость растёт незначительно по меркам возможных потребностей, а затраты линейно.
Вообще это довольно типично для всех криптоалгоритмов: блочные шифры работают с блоками фиксированного размера, асимметричные схемы имеют предел длины подписываемого или шифруемого сообщения.
Поэтому блочные шифры каскадируются разными режимами, типа CBC, CTR и так далее; криптоподпись оперирует хэшом от изначального сообщения, а шифрование зашифровывает симметричный ключ, либо подписывает параметры DH.
Вообще это довольно типично для всех криптоалгоритмов: блочные шифры работают с блоками фиксированного размера, асимметричные схемы имеют предел длины подписываемого или шифруемого сообщения.
Поэтому блочные шифры каскадируются разными режимами, типа CBC, CTR и так далее; криптоподпись оперирует хэшом от изначального сообщения, а шифрование зашифровывает симметричный ключ, либо подписывает параметры DH.
И всё-таки я не понимаю. Ну вот у нас «цифры» по 1Мб каждая. В чём проблемы работать с числами такого размера?
В вот только что сделал число в питоне в 1454113 знаков (десятчных). Я его поделил на 17, это заняло примерно пол-секунды (без привлечения numpy). Если программа будет 30-40с тупить над решением уравнений никого это не смутит. Мне кажется, ограничения в этом месте весьма искуственные и не cpu/memory bound.
В вот только что сделал число в питоне в 1454113 знаков (десятчных). Я его поделил на 17, это заняло примерно пол-секунды (без привлечения numpy). Если программа будет 30-40с тупить над решением уравнений никого это не смутит. Мне кажется, ограничения в этом месте весьма искуственные и не cpu/memory bound.
Проблемы нет. Но и нужды нет.
Вообще этот вопрос аналогичен вопросу: «почему бы не использовать RSA с огромными ключами для прямого шифрования сообщения целиком?». Как и тут — можно, но не нужно.
Если программа будет 30-40с тупить над решением уравнений никого это не смутит. Мне кажется, ограничения в этом месте весьма искуственные и не cpu/memory bound.Это «никого» — очень смелое обобщение. Если для обработки всего полутора мегабайт секретных данных нужны десятки секунд, то как раз этот предел по CPU уже осязаем.
Вообще этот вопрос аналогичен вопросу: «почему бы не использовать RSA с огромными ключами для прямого шифрования сообщения целиком?». Как и тут — можно, но не нужно.
Технически, есть смысл использовать RSA напрямую как one time pad, лишь с тем уточнением, что лично я не знаю никого, кто бы всерьёз использовал его так. Теоретически, такое использование улучшает достаточно устойчивую шифросистему до абсолютно устойчивой. Ценой производительности, конечно. к тому же есть сомнения насчёт устойчивости источника случайных простых чисел.
Она не будет абсолютно устойчивой, так как здесь наиболее сомнительное звено это RSA. Да и для одноразовых шифроблокнотов RSA здесь абсолютно лишний.
Да, очевидно RSA здесь слабое звено. Вместо RSA можно использовать куда более устойчивые декодирования общих линейных кодов (МакЭлис).
RSA здесь не абсолютно лишний по той простой причине, что для одноразовых блокнотов окромя канала также потребуется некий бессмертный абсолютно честный агент, самолёт и парашют для доставки агента, наручники и бронированый кейс с, собственно, одноразовым блокнотом. Очевидно, что это решение несколько дороже, хотя и есть возможность использовать его в условиях одностороннего канала.
И да, эта криптосистема не является абсолютно юзабельной.
RSA здесь не абсолютно лишний по той простой причине, что для одноразовых блокнотов окромя канала также потребуется некий бессмертный абсолютно честный агент, самолёт и парашют для доставки агента, наручники и бронированый кейс с, собственно, одноразовым блокнотом. Очевидно, что это решение несколько дороже, хотя и есть возможность использовать его в условиях одностороннего канала.
И да, эта криптосистема не является абсолютно юзабельной.
Sign up to leave a comment.
Схема разделения секрета Шамира