Розділення секрету

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

Розділення секрету (англ. Secret sharing) — термін в криптографії, під яким розуміють будь-який з способів розподілу секрету серед групи учасників, кожному з яких дістається якась своя  частка. Секрет може відтворити тільки коаліція учасників з первісної групи, причому входити в коаліцію має не менше деякого відомого спочатку числа.

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

Існуючі схеми мають дві складові: розподіл і відновлення секрету. До поділу відноситься формування частин секрету і розподіл їх між членами групи, що дозволяє розділити відповідальність за секрет між її учасниками. Зворотна схема повинна забезпечити його відновлення за умови доступності його зберігачів у деякій необхідній кількості^[1].

Приклад використання: протокол таємного голосування на основі поділу секрету^[2].

Найпростіший приклад схеми поділу секрету

Нехай є група з ${\displaystyle t}$ людей і повідомлення ${\displaystyle s}$ довжини ${\displaystyle n}$, що складається з двійкових символів. Якщо підібрати випадковим чином такі двійкові повідомлення ${\displaystyle s_{1},\ldots ,s_{t}}$, що в сумі вони будуть дорівнювати ${\displaystyle s}$ і розподілити ці сполучення між усіма членами групи, вийде, що прочитати повідомлення буде можливо тільки у випадку, якщо всі члени групи зберуться разом^[3].

В такій схемі є суттєва проблема: в разі втрати хоча б одного з членів групи, секрет буде загублений для всієї групи безповоротно.

Порогова схема

На відміну від процедури розділення секрету, де ${\displaystyle t=n}$ у процедурі поділу секрету кількість часток, які потрібні для відновлення секрету, може відрізнятися від того, на скільки часток секрет розділений. Така схема носить назви порогової схеми ${\displaystyle \left(t,n\right)}$, де ${\displaystyle n}$ — кількість часток, на які був поділений секрет, а ${\displaystyle t}$ — кількість часток, які потрібні для відновлення секрету. Ідеї схем ${\displaystyle t\neq n}$ були незалежно запропоновані в 1979 році Аді Шаміром і Джорджем Блеклі. Крім цього, подібні процедури досліджувалися Гусом Сіммонсом^[4][5][6].

Якщо коаліція учасників така, що вони мають достатню кількість часток для відновлення секрету, то коаліція називається дозволеною. Схеми поділу секрету, в яких дозволені коаліції учасників можуть однозначно відновити секрет, а невирішені не отримують ніякої апостеріорної інформації про можливе значенні секрету, називаються досконалими^[7].

Схема Шаміра

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

Ідея схеми полягає в тому, що двох точок достатньо для задання прямої, трьох крапок — для завдання параболи, чотирьох точок — для кубічної параболи, і так далі. Щоб задати многочлен ступеня ${\displaystyle k}$ потрібно ${\displaystyle k+1}$ точок.

Для того, щоб після поділу секрет могли відновити тільки ${\displaystyle k}$ учасників, його «ховають» у формулу многочлена ступеня ${\displaystyle (k-1)}$ над кінцевим полем ${\displaystyle G}$. Для однозначного відновлення цього многочлена необхідно знати його значення ${\displaystyle k}$ точках, причому, використовуючи меншу кількість точок, однозначно відновити початковий многочлен не вийде. Кількість різних точок многочлена не обмежена (на практиці воно обмежується розміром числового поля ${\displaystyle G}$, в якому ведуться розрахунки).

Коротко даний алгоритм можна описати наступним чином. Нехай дано кінцеве поле ${\displaystyle G}$. Зафіксуємо ${\displaystyle n}$ різних ненульових несекретних елементів даного поля. Кожен з цих елементів приписується певному члену групи. Далі вибирається довільний набір з ${\displaystyle t}$ елементів поля ${\displaystyle G}$, з яких складається многочлен ${\displaystyle f(x)}$ над полем ${\displaystyle G}$ ступеня ${\displaystyle t-1,1<t\leq n}$. Після отримання многочлена вираховуємо його значення в несекретних точках і повідомляємо отримані результати відповідним членам групи^[1].

Щоб відновити секрет можна скористатися інтерполяційної формули, наприклад формулою Лагранжа.

Важливою перевагою схеми Шаміра є те, що вона легко масштабована^[6]. Щоб збільшити число користувачів в групі, необхідно лише додати відповідне число несекретних елементів до вже існуючих, при цьому має виконуватися умова ${\displaystyle r_{i}\neq r_{j}}$ при ${\displaystyle i\neq j}$. У той же час, компрометація однієї частини секрету переводить схему з ${\displaystyle (n,t)}$ -порогової в ${\displaystyle (n-1,t-1)}$-порогову.

Схема Блеклі

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

Схема Блеклі у трьох вимірах: кожна частка секрету — це площина, а секрет — це одна з координат точки перетину площин. Двох площин недостатньо для визначення точки перетину.

З допомогою схеми Блеклі^[5] можна створити (t, n)-схему розподілу секрету для будь-яких t і n: для цього треба покласти розмірність простору дорівнює t, і кожному з n гравців дати одну гіперплощина, що проходить через секретну точку. Тоді будь — t з n гіперплощин будуть однозначно перетинатися в секретній точці.

Схема Блеклі менш ефективна, ніж схема Шаміра: у схемі Шаміра кожна частка такого ж розміру, як і секрет, а в схемі Блеклі кожна частка в t разів більше. Існують поліпшення схеми Блеклі, що дозволяють підвищити її ефективність.

Схеми, засновані на китайській теоремі про залишки

У 1983 році Моріс Миньотт, Асмут і Блум запропонували дві схеми поділу секрету, засновані на китайській теоремі про залишки. Для деякого числа (у схемі Міньотта це сам секрет, у схемі Асмута — Блума — деяке похідне число) обчислюються залишки від ділення на послідовність чисел, які роздаються сторонам. Завдяки обмеженням на послідовність чисел, відновити секрет може тільки певне число сторін^[8][9].

Нехай кількість користувачів в групі дорівнює ${\displaystyle n}$. У схемі Міньотта вибирається деяка множина попарно взаємно простих чисел ${\displaystyle \{m_{1},m_{2},...,m_{n}\}}$ таких, що добуток ${\displaystyle k-1}$менше, ніж добуток ${\displaystyle k}$ найменших з цих чтсел. Нехай ці добутки рівні ${\displaystyle M}$${\displaystyle N}$, відповідно. Число ${\displaystyle k}$ називається порогом для схеми, що конструюється по множині${\displaystyle \{m_{1},m_{2},...,m_{n}\}}$. В якості секрету обирається число ${\displaystyle S}$ таке, для якого виконується співвідношення ${\displaystyle M<S<N}$. Частини секрету розподіляються між учасниками групи наступним чином: кожному учаснику видається пара чисел ${\displaystyle (r_{i},m_{i})}$, де ${\displaystyle r_{i}\equiv S{\pmod {m_{i}}}}$.

Щоб відновити секрет, необхідно об'єднати ${\displaystyle t\geq k}$ фрагментів. В цьому випадку отримаємо систему порівнянь виду ${\displaystyle x\equiv r_{i}{\pmod {m_{i}}}}$, множину рішень якої можна знайти, використовуючи китайську теорему про залишки. Секретне число ${\displaystyle S}$${\displaystyle S<m_{1}\cdot m_{2}\cdot ...\cdot m_{t}}$. Також не складно показати, що якщо число фрагментів менше ${\displaystyle k}$, то, для того щоб знайти секрет ${\displaystyle S}$, необхідно перебрати близько ${\displaystyle {\frac {N}{M}}}$ цілих чисел. При правильному виборі чисел ${\displaystyle m_{i}}$ такий перебір практично неможливо реалізувати. Наприклад, якщо розрядність ${\displaystyle m_{i}}$ буде від 129 до 130 біт, а ${\displaystyle k<15}$, то відношення ${\displaystyle {\frac {N}{M}}}$ буде мати порядок ${\displaystyle 2^{100}}$^[10].

Схема Асмута — Блума є доопрацьованою схемою Міньотта. На відміну від схеми Міньотта, її можна побудувати в такому вигляді, щоб вона була досконалою^[11].

Схеми, засновані на вирішенні систем рівнянь

У 1983 році Карнін, Грін і Хеллман запропонували свою схему розподілу секрету, яка ґрунтувалася на неможливості вирішити систему з ${\displaystyle m}$ невідомими, маючи менше ${\displaystyle m}$ рівнянь^[12].

У рамках даної схеми вибираються ${\displaystyle n+1}$ ${\displaystyle m}$-мірних векторів ${\displaystyle V_{0},V_{1},...,V_{n}}$ так, щоб будь-яка матриця розміром ${\displaystyle m\times m}$, складена з цих векторів, мала ранг${\displaystyle m}$. Нехай вектор ${\displaystyle U}$ має розмірність ${\displaystyle m}$.

Секретом в схемі є матричний добуток ${\displaystyle U^{T}\cdot V_{0}}$. Частками секрету є добуток ${\displaystyle U^{T}\cdot V_{i},1\leq i\leq n}$.

Маючи будь-які ${\displaystyle m}$ часток, можна скласти систему лінійних рівнянь розмірності ${\displaystyle m\times m}$, невідомими якої є коефіцієнти ${\displaystyle U}$. Розв'язавши дану систему, можна знайти ${\displaystyle U}$, а маючи ${\displaystyle U}$ можна знайти секрет. При цьому система рівнянь не має рішення в разі, якщо часток менше, ніж ${\displaystyle m}$^[13].

Способи обману порогової схеми

Існуює кілька способів порушити протокол роботи порогової схеми:

• власник однієї з часток може перешкодити відновленню загального секрету, віддавши в потрібний момент невірну (випадкову) частку^[14];
• зловмисник, не маючи частки, може бути присутнім при відновленні секрету. Дочекавшись оголошення потрібного числа часток, він швидко відновлює секрет самостійно і породжує ще одну частку, після чого пред'являє її іншим учасникам. В результаті він отримує доступ до секрету і залишається не пійманим^[15].

Також існують інші можливості порушення роботи, не пов'язані з особливостями реалізації схеми:

• зловмисник може зімітувати ситуацію, при якій необхідно розкриття секрету, тим самим вивідавши частки учасників^[15].

Примітки

1. Алферов, Зубов, Кузьмин и др., 2002.
2. Schoenmakers, 1999.
3. Алферов, Зубов, Кузьмин и др., 2002, с. 401.
4. C. J. Simmons.  // Contemporary Cryptology. — IEEE Press, 1991. — P. 441—497.
5. Blakley, 1979.
6. Shamir, 1979.
7. Блэкли, Кабатянский, 1997.
8. Mignotte, 1982.
9. Asmuth, Bloom, 1983.
10. Молдовян, Молдовян, 2005.
11. Шенец, 2011.
12. Karnin, Greene, Hellman, 1983.
13. Шнайер Б. Прикладная криптография. — 2-е изд. — Триумф. — С. 590. — ISBN 5-89392-055-4.
14. Pasailă, Alexa, Iftene, 2010.
15. Шнайер, 2002.

Література

• Шнайер Б. 3.7. Розділення секрету // Прикладна криптографія. Протоколи, алгоритми, вихідні тексти на мові Сі = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Тріумф, 2002. — С. 93-96. — 816 с. — 3000 екз. — ISBN 5-89392-055-4.
• Шнайер Б. 23.2 Алгоритми поділу секрету // Прикладна криптографія. Протоколи, алгоритми, вихідні тексти на мові Сі = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Тріумф, 2002. — С. 588—591. — 816 с. — 3000 екз. — ISBN 5-89392-055-4.

• Blakley G. R. Safeguarding cryptographic keys [Архівовано 3 березня 2016 у Wayback Machine.] // Proceedings of the 1979 AFIPS National Computer Conference — Montvale: AFIPS Press, 1979. — P. 313–317. — doi:10.1109/AFIPS.1979.98
• Shamir A. How to share a secret [Архівовано 2 лютого 2020 у Wayback Machine.] // Commun. ACM — New York City: ACM, 1979. — Vol. 22, Iss. 11. — P. 612–613. — ISSN 0001-0782 [Архівовано 3 жовтня 2009 у Wayback Machine.] — doi:10.1145/359168.359176
• Mignotte M. How to Share a Secret // Cryptography: Proceedings of the Workshop on Cryptography Burg Feuerstein, Germany, March 29–April 2, 1982 / T. Beth — Springer Berlin Heidelberg, 1983. — P. 371–375. — (Lecture Notes in Computer Science^[en]; Vol. 149) — ISBN 978-3-540-11993-7 — ISSN 0302-9743 [Архівовано 8 лютого 2009 у Wayback Machine.] — doi:10.1007/3-540-39466-4_27
• Asmuth C., Bloom J. A modular approach to key safeguarding // IEEE Trans. Inf. Theory^[en] / F. Kschischang^[en] — IEEE, 1983. — Vol. 29, Iss. 2. — P. 208–210. — ISSN 0018-9448 [Архівовано 11 грудня 2011 у Wayback Machine.] — doi:10.1109/TIT.1983.1056651
• Karnin E. D., Greene J. W., Hellman M. E. On Secret Sharing Systems [Архівовано 10 серпня 2017 у Wayback Machine.] // IEEE Trans. Inf. Theory^[en] / F. Kschischang^[en] — IEEE, 1983. — Vol. 29, Iss. 1. — P. 35–41. — ISSN 0018-9448 [Архівовано 11 грудня 2011 у Wayback Machine.] — doi:10.1109/TIT.1983.1056621
• Блэкли Д., Кабатянский Г. А. Обобщенные идеальные схемы, разделяющие секрет, и матроиды [Архівовано 21 червня 2018 у Wayback Machine.] // Пробл. передачи информ. — 1997. — Т. 33, вып. 3. — С. 102–110.
• Schoenmakers B. A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting [Архівовано 21 червня 2018 у Wayback Machine.] // Advances in Cryptology — CRYPTO’ 99: 19th Annual International Cryptology Conference Santa Barbara, California, USA, August 15–19, 1999 Proceedings / M. Wiener — Springer Berlin Heidelberg, 1999. — P. 148–164. — ISBN 978-3-540-66347-8 — doi:10.1007/3-540-48405-1_10
• Алферов А. П., Зубов А. Ю., Кузьмин А. С. и др. Основы криптографии: Учебное пособие — 2-е изд., испр. и доп. — М.: Гелиос АРВ, 2002. — ISBN 978-5-85438-137-6
• Молдовян Н. А., Молдовян А. А. Введение в криптосистемы с открытым ключом — СПб.: БХВ-Петербург, 2005. — 288 с. — (Учебное пособие) — ISBN 978-5-94157-563-3
• Pasailă D., Alexa V., Iftene S. Cheating Detection and Cheater Identification in CRT-based Secret Sharing Schemes [Архівовано 21 червня 2018 у Wayback Machine.] // International Journal of Computing — 2010. — Vol. 9, Iss. 2. — P. 107–117. — ISSN 2312-5381 [Архівовано 21 червня 2018 у Wayback Machine.]
• Шенец Н. Н. Об идеальных модулярных схемах разделения секрета в кольцах многочленов от нескольких переменных [Архівовано 3 квітня 2016 у Wayback Machine.] // Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. — Минск: БГУ, 2011. — Т. 1. Статьи факультета прикладной математики и информатики. — С. 169–173. — ISBN 978-985-518-563-6