Threshold MRMA schemes of secret sharing

Full Text

Неотъемлемой составляющей современного процесса развития распределенных систем обработки данных различного назначения является обеспечение безопасности при хранении, обработке и передаче информации. Для решения обозначенной задачи криптография предоставляет весьма обширный функциональный инструментарий, охватывающий многообразные локальные и распределенные средства [1-10] такие, например, как электронная цифровая подпись, идентификация и аутентификация абонентов, безопасное хранение ключей и т. п. Криптографический ключ фактически представляет собой главный секрет во всем процессе дешифрования [3]. Внедрение механизма ключей предполагает использование специальной операционной базы, которая обеспечивает генерирование и надежное хранение ключей, декомпозицию ключей на компоненты в целях распределения их между абонентами, а также восстановление ключей по их составным частям. Настоящая статья посвящена развитию нового подхода к выполнению указанных операций в рамках пороговых криптосхем модулярного типа, ориентированных на нейросетевые реализации [1; 3; 11-12]. Как известно, компьютерно-арифметическую базу средств криптографической защиты информации составляет арифметика больших целых чисел (ЦЧ) [1-3; 13-17], поэтому эффективность криптографических преобразований на практике в решающей мере определяется реализационными свойствами применяемой технологии перевода осуществляемых вычислений из диапазона больших чисел (ДБЧ) в диапазоны ЦЧ стандартной разрядности. Ввиду кодового параллелизма кольцевых операций в модулярной системе счислений (МСС), с одной стороны, и благодаря высокому уровню модульности криптографических процедур, с другой, в свете сказанного в качестве компьютерно-арифметической основы для приложений рассматриваемого класса целесообразно принять модулярную арифметику (МА). Важнейшим дополнительным фактором, указывающим на целесообразность применения МСС для построения пороговых криптосхем разделения секретной информации, является обеспечение возможности использования модулярной системы доступа, которая обладает естественным кодовым параллелизмом, идеально согласуясь с принципами нейросетевых МА-реализаций [1; 3; 18-21]. Одной из наиболее трудоемких операций, выполняемых в модулярной пороговой системе разделения секрета, является восстановление криптографического ключа по его составным частям. Данная операция относится к разряду немодульных. Ее сложность определяется используемой интегрально-характеристической базой, то есть применяемыми интегральными характеристиками модулярного кода и связанными с ними формами представления элементов рассматриваемых диапазонов. Фундаментальные преимущества МА наиболее полно удается реализовать в рамках так называемого минимально избыточного модулярного кодирования [1; 21], ассоциированного с интервально-модулярной формой чисел и связанными с ней интервально-индексными характеристиками кода. В рассматриваемой конфигурации пороговой криптосхемы разделения секрета в качестве базовой используется минимально избыточная МА (МИМА). Это позволяет существенно уменьшить как временные, так и аппаратные затраты на нейросетевую реализацию процесса декодирования в криптосхеме модулярного кода пространственно разделяемого секрета. Маскирующее позиционно-модулярное преобразование исходного секрета Введем обозначения: Z - множество всех ЦЧ; a   и a  - наибольшее и наименьшее ЦЧ: соответственно не большее и не меньшее вещественной величины a; m = Z 0, 1, 1 , {} , m …- а также m - =Z {} /2 , /2 1, , /2 1 m m m - - + … -      =       - множества наименьших неотрицательных и абсолютно наименьших вычетов по натуральному модулю m; ( ) modm a A m = - элемент множества , mZ сравнимый с ЦЧ А по модулю m; / m AB - элемент χ множества , mZ удовлетворяющий сравнению: ( ) mod B A m χ≡ (A (A ( и B - ЦЧ, 0); mB ≠ ( ) ( ) 1212 , , , , , , ss m m m X X X χ χ … χ = … - представление ЦЧ Х (модулярный код) в МСС Х (модулярный код) в МСС Х с основаниями 1, m 2, m , … , sm составляющими ее базис 1 {, m 2, m , … } sm ( 1). s> Пусть 1, p 2, p , … n p - упорядоченные по возрастанию попарно простые большие натуральные числа () 1;n > 1 l i il Pp == ∏ ( 1, ); in = причем 1 1 _/ kj n k n n j j P p P P = -+ - =∏= ( 1, ) jn = Построение рассматриваемой модулярной пороговой (t, n)-схемы разделения секрета с базисом { } 12 , , , , n p p p = …P которая рассчитана на полное (общее) число n и пороговое число t разделяt разделяt ющих секрет сторон (абонентов), осуществляется в рамках следующих определяющих условий. А. Исходный секрет, разделяемый n сторонами (абонентами), представляет собой целое число { } 0, 1, , 1 ,p Sp ∈ = … - Z где р - мощность диапазона секрета, являющаяся большим числом, взаимно простым с основаниями 1, p 2, p , … n p схемы. Б. Секрет S разделяется S разделяется S n сторонами путем его модулярной декомпозиции, то есть по правилу ii pSσ= ( 1, ). in = При этом i-я сторона имеет часть i σ секрета S, которая неизвестна другим сторонам. В. В целях исключения явной передачи секрета S по каналам связи над ним выполняется S по каналам связи над ним выполняется S маскирующее преобразование ( ) S F S = с помощью некоторой псевдослучайной функции F, F, F и результат маскирования подвергается модулярной декомпозиции: ( ) ( ) ii i ii pp S F S F σ = = = σ  ( ). 1, in = (1) Цифры модулярного кода 1 ( , σ  2, σ  , … ) nσ  рассматриваются как модифицированные частичные секреты, принадлежащие соответствующим абонентам. Как видно из (1), маскирующая функция F обладает свойством F обладает свойством F ( ) 1 1 2 2 ( ) ( ), ( ), , ( ) , nnF S F F F = σ σ … σ    где ( ) ( ) ( . ) ii ii i pp F F S F σ = = σ   Г. Любые t или более абонентов могут восt или более абонентов могут восt становить секрет S по принадлежащим им модиS по принадлежащим им модиS фицированным частичным секретам. Но никакая группа, включающая меньше порогового числа t абонентов, сделать этого не может. Построение теоретико-методологической, алгоритмической и инструментальной базы, обеспечивающей оптимальную реализацию перечисленных основополагающих принципов порогового разделения секретной информации в распределенных системах обработки данных, является важнейшим направлением развития технологии активной безопасности [1; 3]. Следуя методологии, изложенной в [3], для маскирования секрета S воспользуемся преобраS воспользуемся преобраS зованием вида ( ) ; , S F S C S Cp = = + (2) где С - псевдослучайный целочисленный паС - псевдослучайный целочисленный паС раметр. Остановимся на проблеме выбора диапазонов изменения параметра С и получаемого С и получаемого С по правилу (2) модифицированного (маскирующего) секрета S  при использовании оснований модулярного базиса { } 12 , , , . n p p p = …P Рассмотрим два класса МСС, определяемых базисами ( ) { } 1212 , , , , , , n l i i i i i i p p p … = …P ( ) 12 1; l i i i n t l n ≤ < <…< ≤ ≤ ≤ и ( ) { } 1212 , , , , , , k k j j j j j j p p p … = …P 12(1 ;2 ). k j j j n k t ≤ < <…< ≤ ≤ ≤ К первому классу относятся МСС, отвечающие группам абонентов, число l которых не l которых не l меньше порогового значения t, а ко второму - МСС, используемые группами из kt < абонентов (см. п. Г). Ключевым аспектом указанной выше проблемы является поиск условий, обеспечивающих непересекаемость множеств (диапазонов) изменения целых чисел ( ) 1 mod j j i l Sp =∏ и ( ) 1 mod , ii j k Sp =∏ имеющих в МСС с базисами 12( , , , ) l i i i …P () tln ≤≤ и 12 ( , , , ) k j j j …P (2 ) kt ≤< соответственно коды 1(, iσ  2, iσ  , … )liσ  и 1(, jσ  2, jσ  , … ). kjσ  Предположим, что секрет S намерены разS намерены разS делить между собой любых l участников сеанса l участников сеанса l связи, за которыми закреплены основания базиса 12 ( , , , ) l i i i …P ( ). tln ≤≤ Поскольку модули базиса Р криптосхемы упорядочены по возрастанию, то при всех рассматриваемых l выполняется неl выполняется неl равенство 1 ( , ).j l ti j P p l t n = ≤= ∏ (3) Маскирующий секрет (2) должен принадлежать диапазонам МСС с основаниями 1, ip 2, ip , … lip - множествам { } 1 0,1, , 1 jj i l p =∏ …- при всех , . l t n = Ввиду (3) для этого достаточно потребовать выполнения условия .tS S Cp P = + < (4) Что касается модулей 1, jp 2, jp , … kjp базиса ( ) 12 , , , , k j j j …P отвечающих группам участников сеанса связи, число k которых меньше пороk которых меньше пороk гового значения t (2 ), kt ≤< то они удовлетво ряют неравенству 1 1 _.i k jt i pP - = ≤∏ (5) Как следует из (1)-(5), рабочий диапазон конструируемой пороговой схемы (по переменной ) S легко может быть ориентирован исключительно только на значения , S  отвечающие кодам 1 (, iσ  2, iσ  , … ) liσ  МСС с базисами 12( , , , ) l i i i …P ( ). tln ≤≤ Соответствующее множество значений модифицированного секрета S  описывается неравенством 1_ . tt P S Cp P - < + < (6) Ввиду (5) диапазоны МСС с базисами 12 ( , , , ) k j j j …P находятся вне промежутка 1 (_ ; ). tt PP - Кодам 1(, jσ  2, jσ  , … ) σ  k j указанных МСС отвечают вычеты ( ) 1 mod i i j k Sp =∏ по модулям 1 1 _ ,ik i jt pP= -∏ ≤ то есть ЦЧ, не принадлежащие диапазону изменения S  - см. формулу (6). Таким образом, ограничение (6) для S  обеспечивает непересекаемость множества результатов S  маскирования секрета S по правилу (2) с диаS по правилу (2) с диаS пазонами { } 1 0,1, , 1 ii j k p =∏ …- всех МСС, определяемых базисами 12 ( , , , ). k j j j …P Изложенное позволяет сформулировать следующее утверждение. Теорема 1. Пусть основания базиса = P 12 { , , , } n p p p = … модулярной (t, n)-схемы разде ления секрета p S∈Z упорядочены по возрастанию и взаимно просты с р. Для того чтобы диапазоны { } 1 0,1, , 1 ii j k p =∏ …- изменения вычетов ( ) 12 1 mod ( , , , ) iki j j j j k Sp = = σ σ … σ∏    в МСС с базисами 12 ( , , , ) k j j j …P (2 ) kt ≤< не пересекались с множеством значений маскирующего секрета S  (результата маскирования S), имеющего в МСС с S), имеющего в МСС с S базисами 12( , , , ) l i i i …P () tln ≤≤ коды 1(, iσ  2, iσ  ,… ) liσ  достаточно выполнения условия ( ) 1 _ ; . tt S P P -∈ (7) В случае применения маскирующего преобразования (2) область изменения псевдослучайного параметра C, которая отвечает условию (7), составляют все ЦЧ, удовлетворяющие неравенству 1 _ / / . tt P p C P p - ≤≤ (8) Согласование рабочего диапазона пороговой криптосхемы разделения секрета с принципом минимально избыточного модулярного кодирования Из вышеизложенного следует, что диапазон { } 1 0,1, , 1 j l ij p=∏ …- всех МСС, определяемых базисами { емых базисами { 12 ( , , , ) l i i i …P 12 (1 ii ≤ < <… ;l in <≤ ), ≤≤ tln включают диапазон {0, 1, …, 1 _, t P- 1 _ 1, t P- + , … 1} t P - МСС с базисом (1,2, , ) t …=P { } 12 , , , t p p p … 1( 1, i = 2 2, i = , … ).t it = Это позволяет рассматривать подмножество 1 {_ , t P- 1 _ 1, t P- + , … 1} t P - этого диапазона как рабочий диапазон модулярной пороговой (t, n)-криптосхемы разделения секрета с основаниями 1, p 2, p , … n p по переменной . S S Cp = + Поскольку восстановление секрета-оригинала S по кодам 1(, iσ  2, iσ  , … ) liσ  маскирующего секрета S  в МСС с базисами 12( , , , ) l i i i …P является немодульной операцией, которая весьма сложна, особенно на диапазонах больших чисел, то ее целесообразно выполнять в рамках минимально избыточного кодирования [1; 9; 21], обеспечивающего минимизацию реализационных затрат. Предлагаемый подход предусматривает использование для выполнения необходимых немодульных операций МСС с базисами 12( , , , ) l i i i …P и диапазонами {0, 1, …, 1 0 1 1} j l ij pp - =∏ -⊂{0, 1, …, 1 1}, j l ij p=∏ - где 0 p - вспомогательный модуль, удовлетворяющий условию: ( ) 00 2 2ii p p l p t ≥ + - ≥ - (9) при всех , . l t n = Такие МСС называются минимально избыточными [1]. Переход от неизбыточных к соответствующим избыточным минимально избыточным МСС (МИМСС) влечет за собой замену рабочего диапазона пороговой (t, n)-схемы разделения секрета на множество { } 1 1 0 1 _ , _ 1, , 1 , - - - = + … - t t t P P p PS (10) которое является составной частью диапазонов всех введенных МИМСС. Сущность принципа минимально избыточного модулярного кодирования для пороговой (t, n)криптосхемы разделения секрета раскрывает нижеследующая теорема. Теорема 2. Пусть 1 1 , i mp = 22 , i mp = , … ; l li mp = 1 , 1 , 1 j j l j l jm M- -- σ = σ  ( 1, 1); jl = - () l IS  - интегральная характеристика модулярного кода j интегральная характеристика модулярного кода j 1 ( , σ  2, σ  , … ) lσ  по базису { } 12 , , , , l m m m = …M определяемая равенством 1 , 1 , 1 1 1 () l j l j l l l j S M M I S - - - - = = σ + ∑   (11) и называемая интервальным индексом (ИИ) числа S  по базису М. Для того чтобы в МСС с попарно простыми основаниями 1, m 2, m , … l m ИИ () l IS  каждого элемента 1 ( , S = σ  2, σ  , … ) lσ  диапазона (10) полностью определялся компьютерным ИИ-вычетом  ( ) ( ) , l ll m I S I S =  необходимо и достаточно, чтобы l-е основание удовлетворяло условию (9). l -е основание удовлетворяло условию (9). lm -е основание удовлетворяло условию (9). m При этом для () l IS  верны расчетные соотношения:     0 0 ( ), ( ) , () () ( ) ;  < =  -≥     , åñëè åñëè ll l l l l I S I S p IS I S m I S p (12)  , ( ) ( ) ; j=1 l l l j l j m I S R = σ ∑  (13) 11 , ,1 1 ,1 () ( ) . , ( ), j l l j l j j j l jm m l l l l lm R m M j l R M -- - - - σ = - σ ≠ σ = σ   (14) Позиционная форма (11) числа S  называется его интервально-модулярной формой по базису М. Применение минимально избыточного модулярного кодирования, сущность которого раскрывает теорема 2, снижает сложность расчета базовых интервально-индексных характеристик - см. формулы (12)-(14) практически до теоретического минимума. Это открывает принципиально новые возможности для повышения производительности пороговых МА-криптосхем разделения секрета. В полной мере сказанное относится и к нейросетевым реализациям процедур восстановления исходного секрета S исходного секрета S исходного секрета по минимально избыточным S по минимально избыточным S модулярным кодам маскирующего секрета , S  синтезируемых на основе интервально-модулярной формы и расчетных соотношений (12)-(14). Проблема корректности порогового принципа модулярного разделения секрета Общая формула для восстановления секрета S по S по S S  вытекает непосредственно из (2) и имеет вид: p SS =  . (15) В МИСС с базисами 12( , , , ) l i i i …P () tln ≤≤ и диапазонами { } 10 1 0,1 , , 1 , j l ij pp = -∏ …- содержащими множество (10) всех маскирующих секретов S  (см. теорему 1), преобразование SS → осуществляется корректно. Найдем ограничение на область изменения , S  исключающее возможность восстановления S по S по S ( ) 1 mod i i j k Sp = =∏ 12 ( , , , ) k j j j = σ σ … σ    любыми k абонентами k абонентами k (2 ), kt ≤< за которыми закреплены модули 1, jp 2,jp , … . kjp Справедлива следующая теорема. Теорема 3. Маскирующий (модифицированный) секрет S  и вычет ( ) 1 mod i i j k Sp =∏ являются равноостаточными по модулю р, то есть дающими при делении на р один и тот же остаток S, тогда и только тогда, когда целое число ( ) 1 12 ; , , , i kk i j SQ Q S j j j p =  = … =    ∏  (16) кратно модулю р. Доказательство. Предположим, что число S  и вычет ( ) 1 mod i i j k Sp =∏ по модулю 1 i i j k p =∏ при делении на р дают один и тот же остаток. Ввиду (15) в этом случае 1 mod . i k j p i p S p S S =  = =   ∏  При этом ( ) 1 mod mod . i k j i S S p p =  ≡   ∏ Отсюда следует, что разность ( ) 1mod i k i j S S p =- ∏ нацело делится на р. Согласно лемме Эвклида из теории делимости [1] ЦЧ S  с учетом обозначения (17) представимо в виде ( ) 11 1 12 11 mod mod ; , , , . ii i ii kk jj k ii ji kk j kj ii SS S p p p S p Q S j j j p = = = = =   = + =    = + …   ∏∏ ∏ ∏∏   Следовательно ∏ ∏   (17) Так как левая часть равенства (17) при принятом предположении нацело делится на р, а модуль р взаимно прост со всеми основаниями базиса Р криптосхемы, ЦЧ ( ) 12 ; , , , k Q S j j j … кратно р. Пусть теперь ЦЧ ( ) 12 ; , , , k Q S j j j … нацело делится на р, тогда из (17) вытекает делимость разности ( ) 1mod i k i j S S p =- ∏ на модуль р. Это означает, что ( )( ) 1 mod mod . ij k i S S p p =∏≡  Таким образом, из кратности числа ( ) 12 ; , , , k Q S j j j … модулю р следует равноостаточность по данному модулю S  и ( ) 1 mod . ij k i Sp =∏ Теорема доказана. Как показывает теорема 3, непересекаемость диапазона (10) принадлежности результатов S  маскирования секрета S с диапазонами S с диапазонами S { } 1 0,1, , 1 ii j k p =∏ …- МСС, определяемых базисами 12 ( , , , ), k j j j …P полностью не исключает возможность восстановления k абонентами k абонентами k (2) kt ≤< секрета S по соответствующим маскиS по соответствующим маскиS рующим аналогам - по модулярным кодам 1(, jσ  2,jσ  , … ) kjσ  вычетов ( ) 1 mod . ij k i Sp =∏ Это обеспечивает нейтрализация элементов диапазона = C { } , 1, , ÍÏ ÍÏ ÂÏ C C C +… изменения псевдослучайного параметра С ( ÍÏ C и ÂÏ C - нижний и верхний пороги для С), которые поС), которые поС рождают ЦЧ ( ) 12 ; , , , k Q S j j j … вида (16), кратные модулю р. Искомые достаточные условия того, чтобы рассматриваемая (t, n)-криптосхема разделения секрета была пороговой, дает нижеследующая теорема. Теорема 4. Пусть 1, p 2, p , … n p - упорядоченные по возрастанию попарно простые большие натуральные числа, используемые в качестве оснований модулярной криптосхемы разделения секрета p S∈= Z { } 0,1 , , 1 p …- (p (p ( - большое число, взаимно простое со всеми 1, p 2, p , … ) np между n абонентами путем наделения их модифицированными (маскирующими) частичными секретами i i p Sσ=  ( 1, ), in = где ; S S Cp = + C - C - C псевдослучайный целочисленный параметр. Для того, чтобы любые l абонентов l абонентов l (2 ; tln ≤≤≤ t - t - t фиксированное ЦЧ), за которыми закреплены основания 1, ip 2, ip , … lip 12 (1 ii ≤ < <… ), <≤ l in могли восстановить секрет S по набору принадS по набору принадS лежащих им частичных секретов - модулярному коду 1(, iσ  2, iσ  , … ) liσ  маскирующего секрета , S  но никакая группа, включающая kt < абонентов, которым отвечают основания 1, jp 2, jp , … kjp 12(1 jj ≤ < <… ), <≤ k jn не имели возможности восстановления S по коду S по коду S 1(, jσ  2, jσ  , … ) kjσ  достаточно выполнения системы условий: { } { } ( ) 1 1 0 1 , 1, , _ ,_ 1, , 1 , \\ , ÍÏ ÍÏ ÂÏ t t t p S S S S P P p P C - - -  ∈ + … ⊆  ⊆ + … -   ∈   CC     (18) где ÍÏ S  и ÂÏ S  - используемые нижнее и верхнее значения секрета-маски  ; S р - делитель ЦЧ, а также 2 1 0 _; t t ns s Pp - -- = =∏ 1 1 1 ; t ts s Pp - - = =∏ { } , 1, , , ÍÏ ÍÏ ÂÏ C C C = + …C ( / ; ÍÏ ÍÏ C S p =   / ); ÂÏ ÂÏ C S p =   ( ){ | ; ; ÍÏ ÂÏp C S cp S S = ∈ + ∈ CC  ( ) 12 1 ; , , , , i k k j i SQ S j j j p =  …=    ∏  12(1 ; k j j j n ≤ < <…< ≤ } 2 ) . kt ≤< Сформулированная теорема 4 фактически является следствием теорем 1-3. Элементы множества p C из (18) могут быть рассчитаны предварительно и записаны в память. Сложность операции проверки принадлежности к p C значений псевдослучайного параметра С при их генерировании в процессе маскирования секрета S по правилу (2), как того требует теореS по правилу (2), как того требует теореS ма 4, в решающей мере определяется мощностью pC множества . pC В свете сказанного важнейшим оптимизационным аспектом проблемы синтеза модулярной пороговой (t, n)-криптосхемы разделения секрета, базирующейся на теореме 4, является минимизация характеристики . pC Заключение Основные результаты представленных в статье исследований по проблематике построения модулярных пороговых криптосхем разделения секрета в распределенных системах обработки данных состоят в нижеследующем. 1. Проведена математическая формализация модели пороговой криптосхемы разделения секрета, компьютерно-арифметическую базу которой составляет МИМА. Благодаря семантическому сходству расчетных соотношений формального нейрона и интервально-модулярной формы ЦЧ реализация фундаментальных свойств параллелизма нейросетевых модулярных вычислительных структур в рамках исследуемой модели позволяет выйти на новый, более высокий (в сравнении с традиционными решениями) уровень производительности и криптостойкости базовой схемы при существенно меньшей ее сложности. 2. Исходя из критерия простоты нейросетевой реализации, для маскирования секрета-оригинала в целях исключения его непосредственной передачи по каналам связи выбрана линейная функция с аддитивной вариационной компонентой псевдослучайного типа. Показано, что адаптивное согласование диапазона изменения псевдослучайного параметра этой функции с диапазоном маскирующего секрета (рабочим диапазоном криптосхемы) позволяет осуществлять минимально избыточную модулярную декомпозицию функции маскирования при любом заданном базисе оснований. Обеспечение возможности применения МИМА дает эффективный инструментарий для создания качественно новой реализационной базы для выполнения всех необходимых процедур как при маскировании исходного секрета, так и в процессе его восстановления по модулярным кодам маскирующего аналога. 3. Для модулярной пороговой (t, n)криптосхемы разделения секрета, где t и t и t n - соответственно пороговое число и полное число абонентов, получены достаточные условия непересекаемости рабочего диапазона схемы с диапазонами МСС, определяемых k-компонентными k-компонентными k базисами (2 ), kt ≤< а также необходимое и достаточное условие равноостаточности по модулю р (р (р ( - мощность диапазона исходного секрета) маскирующего секрета и отвечающего ему в некоторой k-модульной МСС. Доказанные теоретиk-модульной МСС. Доказанные теоретиk ческие положения составляют основу корректной модулярной реализации порогового принципа разделения секретной информации. Исследования выполнены при финансовой поддержке БРФФИ (Договор № Ф18-005 от 30 мая 2018 г.) и ГПНИ «Информатика, космос и безопасность» (2016-2020 гг.).

About the authors

A. A Kolyada

Institute of Applied Physical Problems named after А.N. Sevchenko of Belarusian State University

Minsk, Belarus

P. V Kuchynsky

Institute of Applied Physical Problems named after А.N. Sevchenko of Belarusian State University

Minsk, Belarus

N. I Chervyakov

North-Caucasus Federal University

Stavropol, Russian Federation

References

Supplementary files