GROUP METHOD OF SECRET SHARING ON THE BASIS OF APPLICATION OF TWO-STAGE RESIDUE NUMBER SYSTEM

Abstract

The article presents a new method of threshold secret sharing, which is based on a residue number system. The developed method is resistant to internal attacks, provides a relatively low cost hardware implementation.

Full Text

Под схемами разделения секрета понимается способ распространения частей информации среди нескольких участников, каждому из которых достается своя доля информации, причем восстановить информацию можно, только имея все части секрета. Имея только одну или несколько частей секрета, восстановить информацию невозможно. Схемы, которым для восстановления секрета необходимо k из n частей секрета, называются пороговыми схемами. Схемы с разделением секрета на части первоначально применялись для надежного хранения секретных ключей и обеспечения распределенного доступа к ресурсам. Также схемы разделения секрета используются в тех случаях, если нет доверия одному из участников передачи или хранения информации. В [1] показан один из способов компрометации пороговой схемы Шамира, который можно применить против любой линейной схемы разделения секрета. Данный способ является реализацией внутренней угрозы, в случае которой злоумышленник является одним из участников схемы обмена информацией. На этапе восстановления секрета злоумышленник предоставляет участнику ложную часть секрета, собирая правильные части и, следовательно, получает верный секрет. В общем случае некоторые участники Pt предоставляют ложную информацию вместо истинной информации f (xt ) . Рассмотрим несколько видов атак, когда «злоумышленник» является одним из участников схемы обмена информации с разделением секрета: - один из участников предоставляет ложную информацию, следовательно, секрет будет вос становлен неверно и определить, кто из участников предоставил неверную часть, невозможно; - один из участников фальсифицирует запрос на восстановление секрета, когда остальные участники отправляют данные, он восстанавливает секрет; - один из участников является злоумышленником, он предоставляет свою часть секрета, только узнав все остальные, он может вычислить и отправить свою долю информации, так что секрет восстановится верно и определить кто «злоумышленник» невозможно. Отсутствие возможности предупреждения участников разделения секрета о некорректном восстановлении информации может привести к достижению злоумышленником поставленных целей: - легальные участники восстановили неверный секрет; - злоумышленник получил правильный секрет. Для исключения возможности проведения подобных атак следует при восстановлении информации использовать алгоритмы проверки подлинности входных блоков, то есть проверить информацию на целостность. К таким алгоритмам можно отнести такие как: - помехоустойчивое кодирование; - использование хеш-функций; - метод «циклического контрольного кода». Рассмотрим подробнее эти алгоритмы. Главной задачей помехоустойчивого кодирования является обеспечения достоверности информации за счет использования в сети передачи данных устройств кодирования и декодирования. Достоверность обеспечивается путем введения в информацию избыточного кода по заданному алгоритму, то есть не все символы кодовой комбинации используются для передачи данных. Алгоритмы, обеспечивающие избыточность информации, называются избыточными или корректирующими. «Инфокоммуникационные технологии» Том 11, № 3, 2013 Кочеров Ю.Н., Червяков Н.И. 5 Алгоритмы, использующие хеш-функции, основаны на преобразовании входного массива данных произвольной длинны в массив данных фиксированной длины. Задача хеш-функции заключается в получении признака входного значения, по которому анализируются различные прообразы при решении обратной задачи. Частным случаем хеш-функции является контрольная сумма. Контрольной суммой называется значение, рассчитанное по входному набору данных с применением определенного алгоритма и используемое для проверки целостности данных для передач и хранении. Метод «циклического контрольного кода» широко используется в аппаратных устройствах для верификации входной и выходной информации, а также в программных продуктах для выявления ошибок при передаче данных по каналам связи. Этот метод основывается на понятии полинома, или многочлена. Каждый бит некоторого блока данных соответствует одному из коэффициентов двоичного полинома. У представленных методов аутентификации существует ряд недостатков. Например, во всех представленных методах равенство контрольных сумм и полученных значений не дает гарантии неизменности информации, так как существует множество массивов, имеющих одинаковое содержание, но дающих разные коды, так называемые коллизии. Также недостатком является необходимость хранения хеш-функций. В представленных первом и третьем методах при известной контрольной сумме не составит труда «подобрать» данные, чтобы получилось корректное значение. Для исключения выявленных недостатков можно использовать схемы с групповым разделением секрета. В таких схемах если один из абонентов является злоумышленником, то он сможет восстановить одну из n групп, но не сам секрет. Структурная схема с групповым разделением секрета представлена на рис. 1. Рис. 1. Структурная схема группового разделения секрета Работу схемы можно разделить на два следующих этапа. 1. Исходная информация S делится на п частей и распределяется среди лидеров групп Fi;F2...Fn. 2. Информация, принадлежащая лидеру каждой группы F{,F2 ...Fn, разделяется на к частей и распределяется среди абонентов К ;Fh- Fh Ж ; ^ Fh ^ F„ ). Рассмотрим пример использования системы остаточных классов (СОК) для разделения и восстановления секрета [2-4]. Пример 1. Для простоты вычислений возьмем небольшие числа. Дан секрет S = 66 и дана система оснований рх=2, р2=5, р3=7. Рабочий диапазон будет равняться Р = рхр2р3 =2-5-7 = 70, добавим избыточный модуль р4 =13. Тогда полный диапазон будет равен Р = рхр2РъРа, = 2- 5- 7-13 = 910. Так как рабочий диапазон состоит из трех оснований, а полный из четырех, то может быть реализована пороговая схема, в которой для восстановления секрета достаточно трех из четырех частей. Представим секрет в СОК по основаниям рх, Р2, рг и р4 £ = (0;1;3;1). Для преобразования из системы остаточных классов в позиционную систему счислений (СОК ^ ПСС) можно использовать методы, основанные на китайской теореме об остатках, обобщенной полиадической системе счисления [3], или метод на основе совместного использования КТО и ОПСС [6]. Рассмотрим примеры восстановления секрета, используя эти методы. Пример 2. При восстановлении числа из системы остаточных классов в позиционный код используется метод, основанный на китайской теореме об остатках, для реализации которого необходимо вычислить ортогональные базисы. Для этого рассчитываются величины Pt : Ч=^ = М = 455./>2=^ = ™=182. 1 л 5 £. т 9 Pi 2 р2 5 Р_ Ръ 910 - 130 : Р. = - = 910 Ра 13 = 70 Ищем веса базисов: - из 455 -тх = l(mod2) вычисляем тх= 1 ; - из 182-т2 = l(mod5) вычисляем т2=Ъ\ - из 130- щ = l(mod7) вычисляем т3 = 2 ; - из 70 -т4 =l(modl3) вычисляем т4 = 8. «Инфокоммуникационные технологии» Том 11, № 3, 2013 6 Кочеров Ю.Н., Червяков Н.И. Далее вычислим сами базисы: Bl = тх-Рх =1-455 = 455; В2-т2-Р2 =3-182 = 546 Тп - 1 1 Г13 2 = 4;ri4 = 7 2 = 7- 13 Въ = т3 Р3 =2-130=260; 1 1 1 В4=т4-Р4 = 8 • 70 = 560. Т23 - 5 = 3 7 II TI CS 5 = 8 23 ; гз4 - 7 Имея значения базисов, вычислим A: А = I ах Вх +а2 В2+а3 В3+а4 В41 ; ^4 = І0 - 455 +1 • 546 + 3 • 260 +1 • 560І„ = 910 = 18861, =66. I 1910 Недостаток метода, основанного на китайской теореме об остатках, заключается в том, что для обратного преобразования требуется умножение и сложение больших чисел, а также операция взятия остатка по модулю большого числа. Метод на базе полиадической системы счисления основывается на идее, что любое число может быть представлено в системе взаимно простых чисел рх‘, р2 Р„, как [5]: S = al+a2p1+a3pl р2+... + <*п-1 Р\ Pi • - • Рп-2 +anPl Pi Pn-l • Значения ап вычисляются следующим образом: ах = 5j(modрх) ; а2 = (s2 - ах) r12(mod р2) ; аъ - ((s3 - ах ) г13 - а2 )г23 (modjp3 ) ; ап s((-(*» ~ai) тіп ~аіУіп k-i« (modpj Константы Tkj- можно записать как ТЫ = Рк где 1 < к < j <п. Подставив значения тк}- в предыдущие выражения, получим: ах = ах (mod рх ) ; а2 = (OrVod^ ' (s2 - ax))moàp2 ; «з = ((P2_1)modp3 - ((A”1) mod/ij X X (s3 - ax) - a2))modръ ; «4 = ((ft_1)modP4 • (02_1)m°d/>4 X X((Pj 1 )modp4 ■ (s4 -ax)-a2)-a3))modp3. Пример 3. Восстановим секрет, используя полиадическую систему счисления, используя основания рх, р2, р3 и р4. Найдем константы Tkj- : = 2. із Найдем значения ап : ах = = 0 ; «2 = ((^1_1)то<1 • (-^2 - öfi))mod /?2 = = (3 • (1 - 0)) mod 5 = 3; «з =((/>2_1)modÄ -((PiV)moàPi --ax)-a2))modp3 = (3-(4-(3-0)-3))mod7 = 6; «4 =((P3"1)modP4 •((Р2"1)тоФ,4 х^4 -«1 )-02)-«3))modA = = (2-(8-(7-(l-0)-3)-6))modl3 = 0. Тогда S = ax +a2 px +a3 px p2 +a3 px p2 p3 = = 0 + 3- 2 + 6- 2- 5 + 0- 2- 5- 7 = 66. Рассмотрим метод совместного использования КТО и ОПСС. Для этого представим ортогональные базисы в ОПСС ві ~Вп +Ва Pi +Ва Pi Pi + -Bin Pi Pi-Pn-I, где By коэффициенты ОПСС; і, j - 1; 2 .... п . Тогда коэффициенты ОПС рассчитываются следующим образом ХоПСС = °ч(^115^12 ""Ь1п) + аіФц:>^22 - Ь2п) + - ■■■ + <Xn(Kl>bn2--bm)- Секрет восстанавливается по формуле S = ах+а2рх+а3 рх р2 +... + а„_х рх р2... -Рп-2+ап Рх Р2 Рп-І • Так как Bt modpx = 0, V/ >і, то перед первым значащим разрядом будет і - 1 нулей. Для удобства вычислений базисы можно представить в виде матрицы Тогда Uu 0 0 12 Ь22 о Чи \ахЪхх\+ і * \аМ+Р2 ■ X СОК 0 \a2b2l\p2 . \а,Ь2Х 1 1 2и| Рп 0 0 • «і Ът\ 1 1 ш\рп «Инфокоммуникационные технологии» Том 11, № 3, 2013 Кочеров Ю.Н., Червяков Н.И. 7 При этом ai - /=і ]=і mod Pi Пример 4. Рассмотрим пример восстановления секрета с применением метода совместного использования КТО и ОПСС. Значения базисов возьмем из примера 2. Представим базисы Bt в ОПСС, тогда by : Z?11 - 1, Ьх 2 - 2, - 3, - 6 ft21 = 0; b22 = 3; ô23 = 5; b25 = 7 63i = 0, 632 = 0, Ô33 = 5, ô35 = 3 b4X = 0; b42 = 0; Ь4г = 0; b.5 = 8. Тогда X. сок + iri 0 їм; мі; IM» 0 im; im; и; 0 0 im; IM!, 0 0 0 Iі ■< 0 0 0 0 0 3 5 7 0 0 1 11 0 0 0 8 a1 0;âf2 =3;ûf3 =6;fl4 =0 5 = ôj +a2 ^ +a3 ^ p2 +a3 pi p2 ръ = = 0 + 3- 2 + 6- 2- 5 + 0- 2- 5- 7 = 66. Рассмотрим эти методы с точки зрения реализации их на ПЛИС (программируемая логическая интегральная схема). Для эксперимента была выбрана отладочная плата Altera de2-70, оснащенная процессором Cyclone II EP2C70F896C6N, емкостью 68416 логических вентилей. Результаты эксперимента представлены в таблице 1. Таблица 1. Сравнение методов преобразования СОК ^ ПСС Методы преобразования Используемые логические вентили Китайская теорема об остатках 43 Обобщенная полиадическая система 40 КТО и ОПСС 40 Из таблицы 1 видно, что использование обобщенной полиадической системы счисления для преобразования СОК ^ ПСС более целесообразно, так как необходимо меньшее количество логических вентилей. Пример 5. Рассмотрим ситуацию, когда для восстановления секрета достаточно трех из четырех частей. Восстановим секрет, имея части по основаниям рх, р2 и р4 : S = (0; 1; 1). Тогда ах = sx = 0; «2 =((A_1)mod/?2 '(*2 ~а\))т0^Р2 = = (3 • (1 - 0))mod5 = 3 ; «з =((/?2"1)mod7?4 ■((A"1)mod/,4x x03-ai)-a2))modp4 = = (8 • (7 • (1 -0) -3))modl3 = 6 ; S = ax +a2 px +a3 px p2 +a3 px p2 ръ -= 0 + 3-2 + 6-2-5 = 66. Рассмотрим пример реализации схемы с групповым разделением секрета на основе системы остаточных классов [2-3] и атаки на нее. Пример 6. Для уменьшения количества расчетов пример будет рассмотрен для одной группы. Дан секрет S = 6000 , дана система оснований для «лидеров групп» Р\ =17, />2=19> ръ-'1Ъ,р/х='1'^,ръ=Ъ\ и дана система оснований для клиентов первой группы Р\ = 2> Ph =3, ph =5, ри =7, ph =11. Предста вим секрет S в системе остаточных классов по основаниям рх, р2, р3, р4 и р5: S - (16; 15; 20; 26; 17), каждый остаток распределяется среди «лидеров групп». Тогда информация, принадлежащая лидерам групп, будет следующая: 7^=16, 7^ =15, F3=20, F4-26, Fs =17. Далее информация каждой группы разделяется среди клиентов. Для основания рх клиентами будут д , ph , ph , ри , Ph, и тогда частями первой группы будут Sx = (0; 1; 1; 2; 5) соответственно Fx =0, Fx =1, Fx =1, Fx =2, Fx =5. 1 L2 h 4 L5 К основаниям СОК применимы следующие требования: .JL. р=Пр. - размер рабочего диапазона i=1 должен удовлетворять следующему условию - чем больше разряд каждого основания, тем меньше вероятность того, что злоумышленник сможет подобрать части секрета. Соответствен «Инфокоммуникационные технологии» Том 11, № 3, 2013 8 Кочеров Ю.Н., Червяков Н.И. но, для разрядности основания 10 bit диапазон части секрета будет лежать [0; 210]. Если при восстановлении секрета произойдет ошибка или одним из клиентов окажется злоумышленник, то ошибка может быть обнаружена и исключена. Групповое разделение секрета имеет следующие преимущества по отношению к одноуровневым схемам: - при взломе злоумышленником механизма аутентификации при восстановлении секрета, принадлежащего одной группе, ошибочным будет лишь секрет «лидера группы». Следовательно, при восстановлении всего секрета эта ошибка может быть обнаружена и группа или клиент могут быть исключены из работы схемы. Рассмотрим численный пример. Значения оснований СОК и значение секрета возьмем такие же, как и в предыдущем примере. Злоумышленник взломал алгоритм аутентификации и заменил =0 на = 1 , тогда Si - (1; 1; 1; 2; 5) , и, следовательно, «лидер группы» восстановит неверный секрет и не будет знать об этом: Fx =1171 S = (1171; 15; 20; 26; 17). Так как рабочий диапазон состоит из трех оснований, а полный из пяти, то ошибка может быть найдена и исправлена. Для обнаружения ошибочного основания вычислим проекции числа Fl по каждому из оснований, как показано в [7]: F,1 = 16, Fj2 = 401, Fl3 = 247, F,4 = 181, F1 =121. Все проекции кроме ^ 1 = 16 больше рабочего диапазона, Р = 30, следовательно ошибка - это цифра по основанию рх = 0. Если ошибочных оснований больше, чем избыточных, то ошибка не может быть обнаружена «лидером группы» и секрет «лидера группы» будет также неверен. Тогда ошибка может быть обнаружена при восстановлении секрета. Алгоритм обнаружения ошибки при восстановлении секрета такой же, как и у «лидера группы»; - при атаке на пороговую схему злоумышленником путем «прослушки» сети он сможет узнать только часть секрета, эта часть никакой информации о самом секрете нести не будет, следовательно, она будет для него бесполезна. Рассмотрим пример. Злоумышленник прослушивает сеть группы pv следовательно, он может узнать части только этой группы S1 = (0; 1; 1; 2; 5), и, восстановив информацию, он узнает только, что Fx = 16, остальная информация ему будет недоступна; - компрометация только части секрета подгруппы, а не всего секрета. Рассмотрим пример. Допустим, один из клиентов группы злоумыш ленник. При фальсификации запроса на восстановление секрета злоумышленником будут отправлены части, принадлежащие только той группе, в которой он находится. Следовательно, если в нашем примере злоумышленником окажется клиент, то он сможет получить только iSj = (0; 1; 1; 2; 5), восстановить только часть секрета, принадлежащего основанию, рх =16, но сам секрет не будет ему доступен. Выводы В статье представлен групповой метод разделения секрета на основе двухступенчатой системы остаточных классов. Показана его эффективность к атакам по отношению к одноуровневой схеме разделения секрета.