METHOD DEVELOPMENT NOISEPROOF SECRET SHARING BASED ON THE APPLICATION OF TWO-STAGE SYSTEM, THE RESIDUAL CLASSES

Abstract

The article presents a group method of secret sharing, based on a residue number system. When using this method increases the ability to scan for code that is increasing the number of detected errors.

Full Text

Ведение Схемы пространственного разделения секрета позволяют делить информацию на n частей и распространять ее среди территориально распределенных n участников, и при восстановлении информации необходимо соединять все части. Схемами разделения секрета, которым для восстановления необходимо k из n частей, называются пороговые схемы разделения секрета. Изначально такие схемы применялись для хранения секретных ключей и распределенного доступа к стратегическим ресурсам. Такие схемы применяются, если нет доверия одному из участников обмена информации. В работе проведено исследование метода разделения секрета на группы частей, показано, чем групповое разделение лучше линейного. При работе схемы пространственного разделения секрета могут подвергается атакам, при которых если злоумышленник является одним из абонентов схемы разделения секрета, то он сможет получить тайную информацию или исказить ее таким образом, что она не сможет быть восстановлена. Рассмотрим несколько видов таких атак: - один из участников предоставляет ложную информацию, следовательно, секрет будет восстановлен неверно и определить, кто из участников предоставил неверную часть, невозможно; - один из участников фальсифицирует запрос на восстановление секрета, когда остальные участники отправляют данные, он восстанавливает секрет; - один из участников является злоумышленником, он предоставляет свою часть секрета, только узнав все остальные, он может вычислить и отправить свою долю информации, так что секрет восстановится верно и определить, кто «злоумышленник», невозможно. Отсутствие возможности предупреждения участников разделения секрета о некорректном восстановлении информации может привести к достижению злоумышленником поставленных целей: - легальные участники восстановили неверный секрет; - злоумышленник получил правильный секрет. Из рассмотренных видов атак следует, что для повышения достоверности восстановления информации следует использовать алгоритмы разделения информации с возможностью контроля ошибок. К таким алгоритмам можно отнести алгоритм разделения информации в обычных вычислениях, основанных на системе остаточных классов (СОК), которая глубоко изучена в теории чисел [7] и активно применяется в цифровой обработке сигналов, обработке изображений, кодах с обнаружением и коррекцией ошибок и криптографических системах [1-3]. Обзор методов преобразования СОК-ПСС Для кодов, от которых требуется, чтобы они обладали возможностью обнаружения и коррекции ошибок, необходимо наличие двух групп чисел: информационных и контрольных. В информационную группу входят числа, составляющие значение закодированной величины, а в контрольную дополнительные числа, вводимые для обнаружения и исправления ошибок при передаче. Система счисления в остаточных классах открывает возможность использования единого помехоустойчивого кода для борьбы с ошибками, возникающими при передаче информации по ка «Инфокоммуникационные технологии» Том 11, № 4, 2013 Кочеров Ю.Н., Червяков Н.И. 5 налам связи и при ее обработке в цифровых системах обработки данных. Различают избыточную и неизбыточную СОК: последняя должна удовлетворять условию л-1 я Пл<я< I J р. где n - число оснований СОК; 1=1 /—1 A - число, представляемое в СОК. Для получения избыточной СОК к числу рабочих оснований n добавляют k избыточных оснований к >1, тогда п+к А< Па . Используя избыточную СОК, можно обнаружить k ошибок. Пример 1. Рассмотрим пример избыточной и неизбыточной СОК. Пусть дано число А = 66 и система оснований рх=2, р2 = 5, ръ = 7, Ра = 13- Так как неизбыточная СОК должна Л-1 Л удовлетворять условию Pi< А< РР рх, то г=1 i=1 основания рабочего диапазона будут рх=2, р2=5, р3=1, а избыточным рА = 13 . Представим это число в СОК А = (0,1,3,1), для обратного преобразования из системы остаточных классов в позиционную систему счисления СОК —— ПСС достаточно иметь три остатка из четырех. Также в данном примере можно обнаружить одну ошибку. Для этого необходимо найти проекции числа А по каждому модулю. Для восстановления числа из СОК в ПСС можно использовать метод, основанный на китайской теореме об остатках, метод Гарнера или метод совместного использования СОК и ОПСС. Пример 2. Восстановление числа с использованием китайской теоремы об остатках. Восстановление числа из системы остаточных классов в позиционный код при использовании метода, основанного на китайской теореме об остатках [4], необходимо вычислить ортогональные базисы. Для этого рассчитываются величины Pt : Р 910 Р 910 Д= —= —= 455; Р2= — = — = 182; Pi 2 2 р2 5 Р 910 Р 910 Р3= — = — = 130; р - А-= = 70. Рг 7 Ра 13 Ищем веса базисов: -из 455-тх = l(mod2) вычисляем тх = 1; -из 182-т2 = l(mod5) вычисляем т2= 3; -из 130-m3 = l(mod7) вычисляем т3 = 2; -из 70-m4 =l(modl3) вычисляем т4 = 8. Далее вычислим сами базисы: Вх=тх-Рх =1-455=455; В1=т1-Р1 =3-182=546; В3 = т3 Р3 =2-130=260; В4 = т4-Р4 =8-70 = 560. Имея значения базисов, вычислим А: А = \ах ■ Вх + а2 ■ В2 + а3 • В3 + а4 ■ В41 А = \0- 455 +1 • 546 + 3 • 260 +1 • 560І = 910 = 18861 ,=66. І І910 Недостаток метода, основанного на китайской теореме об остатках заключается в том, что для обратного преобразования требуется умножение и сложение больших чисел, а также операция взятия остатка по модулю большого числа. В методе Гарнера используется полиадическая система счисления, он основывается на идее, что любое число может быть представлено в системе взаимно простых чисел рх ... рп как [4]: S = ax+a2-px+a3-px-p2+... + ап-1 • А • Pi ■- '■ Рп-2 +ап 'Pi 'Pi • —• Рп-1 • Значения ап вычисляются таким образом: ах ^(mod^) ; а2 = (s2-ах) TX2(moàp2) ; «з = (С*з ~аі) Чз~а2)Т2з (modр3) ; ап =((—(^» ~ai) Тш ~а-^2п (mod/Ü ■ Константы Tkj можно записать как Рк где 1 <к< j <п. Подставив значения Tkj в предыдущие выражения, получим: ах = ах (mod рх ) ; а2 = ((Р\ 1)m°dp2 ■ (s2 -ax))modp2 ; а3 = ((р2 )modр3 ■ ((рх~ )modрЗ х x(s3 -ах)-а2))modр3\ a4=((p{l)moàp4-{(p2l)moàp4x x(Oi_1)mod^4 ■(s4-ax)-a2)-a3))modp3, Пример 3. Восстановление числа с использованием метода Гарнера. Для восстановления числа необходимо найти константы Tkj : «Инфокоммуникационные технологии» Том 11, № 4, 2013 6 Кочеров Ю.Н., Червяков Н.И. 1 1 1 712 = 2 — 3 ; г13 — 5 2 =4;7i4 = 7 2 = 7; 13 — 3 ; т2л — 13 = 2. 13 Ьхх ЪХ2 О h 22 О о Ля 2п XСОК i*ii Г 1 111А |«1*12 + Pi ' • l«l*l„ + Рп 0 1^2*22 + Pi ' • |«1*2„ + Рп 0 0 • |«1 Kn + Рп Найдем значения ап : ах = = 0 ; a2=((pl~l)™oàp2-(s2-ax))modp2 = = (3 • (1 - 0))mod5 = 3 ; «з =((P2“1)mod^3 -((pr^modA x х(5'з - ax) - a2))mod p3 -= (3-(4-(3-0)-3))mod7 = 6; «4 = ((Л-1)™0^ x x((/>i_1)mod/J4-(j4-ax)-a2)-a3))modp3 = = (2 • (8 • (7 • (1 - 0) - 3) - 6)) mod 13 = 0. Тогда 5 = ^ +a2-px + a3-px •p2+a3 • px ■ p2 ■ p3 = = 0 + 3- 2 + 6- 2- 5 + 0- 2- 5- 7 = 66. Рассмотрим метод совместного использования КТО и ОПСС[5]. Для этого представим ортогональные базисы в ОПСС Ві = Ва + Вп ’Pi +Віз ’Pi 'Pi +••• + Bi„’Pl’Pl’-’P„-l> где By коэффициенты ОПСС; i,j = l;2...n. Тогда коэффициенты ОПС рассчитываются следующим образом Хопсс = аЖх,ЬХ2,...,Ъх„) + oc2(b2X,b22,...,b2n) + ■■■+an(PniA2>-An)- Секрет восстанавливается по формуле S = ax+a2-px+a3-px-p2+... + an-1 ’Pi ’Pi ’■■■■Pn-2+an ’Pi ’Pi ■■■■’Pn-i- Так как Bt mod px =0,\/j>i, то перед первым значащим разрядом будет i - 1 нулей. Для удобства вычислений базисы можно представить в виде матрицы при этом at — 1>А /=1 2=1 ШОСІРі Пример 4. Восстановление числа с совместным использованием КТО и ОПСС. Представим базисы Вх в ОПСС, тогда by : *12 =2 *22 =3 *15 = 6 *13 =3; *23 = ^ ’ *25 = ^ *33 — ^ » *43 = 0; 25 *35 = 3 *45=8. о >—к U. + м; м; м;3 0 мі; м; МГ, 0 0 м; Мі+з 0 0 0 + 2 00 i-H *11 = 1; *21 =0; Ьзх — 0; Ь32 — 0 *41=0; *42=0 Тогда Х-СОК ~ 0 0 0 0 0 3 5 7 0 0 1 11 0 0 0 8 ах — 0, а2—Ъ, а3 = 6, а4 — 0, S = ax+a2 ■рх+а3 ■ рх ■р2+а4-рх ■ р2 ■ ръ = = 0 + 3- 2 + 6- 2- 5 + 0- 2- 5- 7 = 66. Групповой метод разделения секрета Для увеличения стойкости схемы разделения секрета на основе СОК можно использовать схему с групповым двухступенчатым разделением секрета, рис. 1. Тогда Рис. 1. Структурная схема группового разделения секрета «Инфокоммуникационные технологии» Том 11, № 4, 2013 Кочеров Ю.Н., Червяков Н.И. 7 Работу схемы можно разделить на два этапа. 1. Исходная информация S делится на n частей и распределяется среди лидеров групп Fx-F2...Fn. 2. Информация, принадлежащая лидеру каждой группы Fl\F1 — Fn, разделяется на m частей К Л "Л К-р2, "Л. Ж ^ -F: )■ Далее эти части могут быть переданы либо по беспроводным сетям передачи данных либо храниться на удаленных серверах. Исходную информацию предлагается хранить или передавать в виде набора частей, количество которых равно количеству оснований СОК. Введя избыточность среди лидеров групп и среди частей, принадлежащих им, получим пороговую схему, где для восстановления информации достаточно получить от k групп k частей. Уменьшение размера частей, а также их территориальное распределение приведет к снижению нагрузки на линии передачи данных, на серверы для хранения или на ретрансляторы для передачи данных по беспроводным сенсорным сетям. Также с помощью введенной избыточности мы можем локализовать места хранения ошибочных частей и не использовать их для восстановления информации. Для того чтобы вывести из строя линейную одноуровневую схему, достаточно фальсифицировать k+1 абонентов, а для двухступенчатой необходимо фальсифицировать до (к +1 )К, где K необходимое число групп для восстановления информации. Мера обнаруживающей способности линейной схемы может быть вычислена со- Рп~Рк Рп~ 1 гласно [1J как —- = —-. Р Р П П Используя меру формулу для обнаруживающей способности линейной схемы, модернизируем ее для групповой схемы ИІ ‘il + ■ ■п2 кт ■ п2 + Рп-Рк где m - номер группы. Таблица 1. Реализация схемы с групповым разделением секрета Секрет А —12752322 Группы Л = 229 F1 = 228 Pi = 233 Fj = 232 ръ=2Ъ9 F3 =238 Ра = 241 F4=48 А =251 Fs =16 Части секрета А..* =3 0 1 1 0 1 Рх..52 =5 3 2 3 3 3 Рі.,5 з = 17 7 11 0 14 13 А..* =!9 0 4 10 10 13 A..J, “23 21 2 8 2 13 В таблице 1 показан пример реализации схемы с групповым разделением секрета. Рассмотрим пример восстановления групповой схемы с применение метода совместного использования КТО и ОПСС для оснований P\„5l = 3, Pi„s = 5, Р\..5г =17’ Р\..5г =19’ P\..5S =23, рассчитаем базисы, как показано в первом примере: Р = 3 • 5 • 17 ■ 19 • 23 = 111435 ; Р 111435 Р2= — = 3 111435 = 37145: />=- = Р\ Р^ Р2 Рз=Р=Ш435=6555; = 22287; Ръ 17 л=Р =111435 Ра 19 Р=Ш43_5 Р5 23 Затем ищем веса базисов: -из 37145'wîj =l(mod3) вычисляем щ=2; - из 22287-т2 = l(mod5) вычисляем т2=Ъ\ -из 6555'щ — l(modl7) вычисляем щ=\2', - из 5865-т4 = l(modl9) вычисляем т4=3; - из 4845- т5 = l(mod23) вычисляем т5 = 20. Далее вычислим сами базисы: Ву=щ-Рх= 2-37145=74290; В2=т2-Р2=Ъ• 22287= 66861; Въ=щ-Ръ =12-6555=78660, «Инфокоммуникационные технологии» Том 11, № 4, 2013 8 Кочеров Ю.Н., Червяков Н.И. В4=т4-Р4 = 3-5865=17595, В5-т5-Р5- 20-4845= 96900. Найдем константы zkj : Г12 — — 2 ; т13 — = 6; г14 = 17 = 13; 19 45 1 1 1 3 = 1 23 ? ; 723 — 5 il ■»t t> II C-- 5 :4; 19 Т25 — 1 1 5 = 14; 23 II 17 Т35 — -19 ; т45 - 23 = 9; 19 = 17; 23 Y1 — л 1COfC к m; 0-5 + 17 Mi+9 |0T5|* 1 123 0 m; 3-3 + 17 з-і5і;9 nc 0 0 7-8 + 17 ÏK, І7Т6Ґ 1 123 0 0 0 0-12Ii+9 І0-ЗҐ 1 123 0 0 0 0 І21-20Ґ 1 123 0 0 0 0 0' 0 1 10 7 18 0 0 5 12 21 9 0 0 0 0 0 ° 0 0 0 6 «i=0, a2 = 1, a 3 15, = 0 ,a5 = : 0; pi=<h + a2-px+a3 'Pi 'P2+a3 Pi + + a4-p1-p2-p3 + a5-pl-p2-p3 = 228; t-COK ~ ni; ni; 1-5 + 17 ni;» І1-15Ґ 1 І23 0 m; 2-3 + 17 |2-i5i;9 2-13Ґ 1 123 0 0 м-8і;7 І1М6Ґ 1 123 0 0 0 |4-ч; NIL 0 0 0 0 2-20Ґ 1 123 1 3 5 6 15 0 4 6 11 4 0 0 3 11 17 0 0 0 10 14 0 0 0 0 17 а1 =1 ,а2 =2 ,а3 =15 ,а4 =0 ,а5 =0; Fl=al+a2-pl + a3-pl-p2 + a3-pl + + а4-р1-Р2-Рз + а5-РгР2-Рз = тI СОК ~ к ni; І1’5 + 17 K. І1-15Г 1 123 0 м; 3-3 + 17 із-IC |з-ізГ 1 123 0 0 0-8 | + 17 їм; І0-16Ґ 1 123 0 0 0 Ію-зГ 1 123 0 0 0 0 8-20Ґ 1 І23 1 3 5 6 15' 0 1 10 7 18 0 0 0 0 0 9 0 0 0 6 13 0 0 0 0 22 öj — 1, — 4, öj —15, Ö4 — 0, ög — 0 î Fi =fl1+e2-/»1 + e3-p1-p2 + e3-/>1 + + а4-р1-р2-Рз + а5-р1-р2-Рз = 238; *сок ~ к мі; м;7 м; |0Т5|* 1 І23 0 м; ni; |з-і5і; Із-ізГ 1 123 0 0 NC І14-С 14-16;. 1 123 0 0 0 ію-ч; ііо-зі: 1 123 0 0 0 0 І2'2С 1 123 0 0 0 0 0' 0 1 10 7 18 0 0 10 5 19 9 0 0 0 6 13 0 0 0 0 17 öj =0,a2 =l,a3 =3 ,a4 =0,a5 =0; Fj =a1+ö2-j51 + a3-JPr/,2 + ü!3-A+«4-JPr/,2-/?3 + + a5 "P\'P2,773-48; a, = 1, a2 = 0, a3 = 1, a4 — 0, a5 =0 Fi = ai+a2'Pi + <h'Pi'P2+a3'Pi + + а4-р1-р2-Рз + а5-Рі-Р2-Рз=4%’ «Инфокоммуникационные технологии» Том 11, № 4, 2013 Кочеров Ю.Н., Червяков Н.И. 9 Х4 = л ^ сок К Ni; ni; їм; MC. 1 123 '1 3 5 6 21" 0 ni; ni; Ий MC, 1 123 0 2 3 15 13 0 0 |іб-8і; 116-с І16-16Ґ 1 123 = 0 0 9 14 6 0 0 0 мм; І16-ЗҐ 1 І23 0 0 0 2 11 0 0 0 0 16-20Ґ 1 123 _ 0 0 0 0 2! Далее таким же образом восстанавливаем и сам секрет из остатков принадлежащих лидерам групп: 42 ^14 = 1 229 1 : 291;т13 233 229 = 261; г15 = 241 1 229 1 ■ 454: 239 229 = 308; 251 23 Т25 1 233 1 :438;г, 24 ' 239 1 233 1 — 237; т"з4 233 1 : 271; 241 251 251 = 230; г45 = 251 239 1 = 361; 241 241 = 276; 251 Хссо — |228 • 1| О О о о 229 228-175 233 |57 • 58[ О 0 О 1233 228 57 173 54 47 0 175 69 129 243 0 0 235 238 208 0 0 0 60 6 0 0 0 0 245 «і = 228,a2 = 232, a3 = 238,a4 |228 • 65 І57-169І 239 |173 - 4| 0 о 1239 239 |228 -186 |57 -111 |173 • 2| |54 -182 О 6Г, 228 • 202Ґ , І241 1 І251 | + 57 • 6l+ '241 1 1251 + 173 • 42 Г 241 1 І251 і + 54 •219 Г '241 1 1251 I48-31!!,. Для обнаружения и коррекции ошибок необходимо иметь избыточные основания СОК. Выделим из таблицы 1 информационные и дополнительные основания, таблица 2. Моделирование группового метода разделения секрета Данная групповая схема реализована в среде разработки Borland C++ Builder. В качестве объекта разделения было принято 8-битное изображение с разрешением 220^220 точек. Каждый пиксель изображения последовательно переводился в СОК по основаниям рх =229, р2 =233, ръ =239, Рб, =24І, р5 =251, где Рі>Р2>Рз>Р4’Р5 - это основания лидеров групп. Основания рх,р2,р2 являются рабочи ми, а Р4’Р5 - избыточными. Далее основание каждого лидера группы повторно преобразовывалось в СОК по основаниям рпХ = 3, рп2 = 5, рпЪ=М, р„А = 19, рп5 =23, где n - это номер группы п = 1...5. Основания СОК были подобраны таким образом, чтобы три основания были рабочими, а два избыточными. На избыточные основания частей каждой группы накладываем условие абсолютной надежности, что гарантирует достоверность избыточных оснований СОК. На рис. 2 приведен пример программной реализации группового метода разделения секрета. На нем показано, как исходное изображение делится на пять частей для лидеров групп, и каждый лидер группы затем делится так же на пять частей, после чего изображение восстанавливается. Система остаточных классов - это система счисления, которая имеет возможность обнару «Инфокоммуникационные технологии» Том 11, № 4, 2013 10 Кочеров Ю.Н., Червяков Н.И. Таблица 2. Групповая СОК с избыточными основаниями частями и группами Секрет ^4 = 12752322 Группы Pl = 229 Fx= 228 р2 =233 Fx= 232 р3 = 239 F3= 238 />4=241 F4= 48 />5=251 /^ =16 Информационные Дополнительные Части секрета А...5, =3 Информационные 0 1 1 0 1 А..* =5 3 2 3 3 1 Pl.5 з =17 7 11 0 14 16 А..* =19 Дополнительные 0 4 10 10 16 Pl..5s =23 21 2 8 2 16 жения и коррекции ошибок. При восстановлении изображения А из системы остаточных классов если А> Р!, то А является ошибочным. Рассмотрим пример выполнения программы, когда часть информации потеряна. На рис. 3 по Рис. 2. Моделирование группового метода разделения секрета казано, что часть информации потеряна, но для локализации достаточно оставшихся изображений. Поиск локализация ошибок осуществляется путем вычисления проекций числа A по всем осно- Рис. 3. Восстановление секрета без локализации ошибок «Инфокоммуникационные технологии» Том 11, № 4, 2013 Кочеров Ю.Н., Червяков Н.И. 11 ваниям. Так как два основания являются избыточными, то можно найти две ошибки. Рассмотрим численный пример поиска восстановления секрета, если от лидеров групп придет две ошибки. Пусть дан секрет Л = 300, рх-\Ъ, р2-П, />з=19, /?4=23, р5= 29. Представим число A в СОК, тогда А = (1,11,15,1,10). Введем ошибку в число, представленное в СОК Л = (0,2,15,1,10), тогда при восстановлении А —1736501, так как А> Р1, Р1 = 2800733, то можно сказать, что число А ошибочно. Найдем проекции числа A по двум основаниям: - по основаниям рх =13, р2-\1, Р1 =12673, АХ2 = 300 ; - по основаниям рх —13, рг= 19, Р1 = 11339, А13 = 6556; - по основаниям р2-\1, р3 =19, Р1 =8671, А2ъ = 6970. Проекции по всем основаниям, кроме проекции по модулям рх —13, р2=П, больше рабочего диапазона секрета, следовательно, части по основаниям рх=\Ъ, р2—\1 являются неверными, поэтому ошибку можно локализовать и восстановить секрет по основаниям р3 =19, Ра =23, р5 =29. Рис. 4. Локализация ошибок в СОК На рис. 4 показано, как при потери части информации, достаточной, для потери группы, секрет восстанавливается. Для восстановления секрета необходимо, чтобы в k группах были рабочими K частей, то есть для данного примера достаточно, чтобы в трех группах работало по три клиента. Необходимым условием является также то, чтобы СОК была упорядочена: при неупорядоченной СОК не все пиксели могут быть локализованы. На рис. 5 показано, как при потере информации, большей, чем это достаточно для восстановления, выглядит восстановленный секрет. Рис. 5. Восстановление секрета при потере избыточной информации Вывод В статье представлен метод группового разделения секрета, основанный на системе остаточных классов. Показана его большая обнаруживающая способность в отличие от ли- ,Рп~Рк Рп-1 нейного метода (-=-для линейного и р р п п ( р _ р р _ р р _ Р А р _ р п\ к\ і п2 kl і і пт кт \ п ^ р р р р \ п\ п2 пт у п для группового), при этом уменьшение размерности частей приводит к снижению нагрузки на линии передачи данных либо на серверы их хранения. Приведены методы локализации оши «Инфокоммуникационные технологии» Том 11, № 4, 2013 12 бок в СОК, показан способ восстановления информации без коррекции ошибок. Разработано программное обеспечение для моделирования группового разделения секрета на примере разделения цветного изображения с локализацией ошибок. На программной модели показано, что для восстановления секрета групповым методом допустимо потерять больше частей информации, чем при использовании линейного метода. Показана возможность применения разработ