Қытайдың қалған теоремасын қолдана отырып құпия бөлісу - Secret sharing using the Chinese remainder theorem - Wikipedia

Құпия бөлісу құпияны қалпына келтіруден тұрады S акциялар жиынтығынан, әрқайсысында құпия туралы ішінара ақпарат бар. The Қытайдың қалған теоремасы (CRT) берілген бір мезгілде конгруенттік теңдеулер жүйесі үшін шешім кейбіреулерінде ерекше болатынын айтады З/nЗ, бірге n > 0 сәйкестікте кейбір тиісті шарттарда. Құпия бөлісу осылайша CRT-ді сәйкестік теңдеулерінде көрсетілген үлестерді шығару үшін қолдана алады және құпияны қалпына келтіру құпиясы болатын бірегей шешімді алу үшін сәйкестік жүйесін шешіп алуға болады.

Құпия бөлісу схемалары: бірнеше түрлері

Оның бірнеше түрлері бар құпия бөлісу схемалар. Ең негізгі түрлері деп аталады табалдырық схемалары, мұнда тек түпкілікті акциялар жиынтығы. Басқаша айтқанда, құпия берілген S, және n акциялар, кез келген жиынтық т акциялар - бұл ең кішісі бар жиынтық түпкілікті кез келген жиынтығы мағынасында одан құпияны алуға болады t-1 акциялар беру үшін жеткіліксіз S. Бұл а ретінде белгілі шекті қол құрылымы. Біз мұндай схемаларды (т,n) табалдырық құпия бөлісу схемалар немесе т- тысn схема.

Табалдырық құпия бөлісу схемалар бір-бірінен белгілі бір құпиядан бастап акциялар жасау әдісімен ерекшеленеді. Біріншілері Шамирдің шекті құпия бөлісу схемасы, оған негізделген көпмүшелік интерполяция табу үшін S берілген акциялар жиынтығынан және Джордж Блейкли Геометриялық құпияны бөлу схемасы, онда құпияны қалпына келтіру үшін геометриялық әдістер қолданылады S. Табалдырық құпия бөлісу CRT негізіндегі схемалар Mignotte және Asmuth-Bloom-қа байланысты, олар CRT-мен бірге бүтін сандардың арнайы тізбектерін қолданады.

Қытайдың қалған теоремасы

Келіңіздер , және . Сәйкестік жүйесі

шешімдері бар З егер және егер болса барлығына , қайда дегенді білдіреді ең үлкен ортақ бөлгіш (GCD) of ммен және мj. Сонымен қатар, осы жағдайларда жүйенің бірегей шешімі бар З/nЗ қайда , дегенді білдіреді ең кіші ортақ еселік (LCM) of .

CRT көмегімен құпия бөлісу

Бастап Қытайдың қалған теоремасы бізге санды ерекше анықтау әдісін ұсынады S модуль к-көп салыстырмалы түрде қарапайым бүтін сандар , мынадай жағдай болса , демек, құпия анықтайтын схема құру идеясы S кез келген к акциялар (бұл жағдайда, қалған S сандардың әрқайсысы бойынша модуль ммен), бірақ кем берілген құпияны ашпайды к осындай акциялардың

Сайып келгенде, біз таңдаймыз n салыстырмалы түрде қарапайым бүтін сандар осындай S кез келген таңдау өніміне қарағанда кішірек к Бұл бүтін сандардың саны, бірақ сонымен бірге кез келген таңдауға қарағанда үлкен k-1 олардың. Содан кейін акциялар арқылы анықталады үшін . Осылайша, CRT арқасында біз ерекше анықтай аламыз S кез келген жиынтығынан к немесе одан да көп акциялар, бірақ кем емес к. Бұл деп аталатын қамтамасыз етеді шекті қол құрылымы.

Бұл шарт қосулы S ретінде қарастыруға болады

Бастап S -ның ең кіші өнімінен кіші к бүтін сандардың кез келгенінің көбейтіндісінен кішірек болады к олардың. Сондай-ақ, үлкендердің өнімінен үлкен болу к − 1 бүтін сандар, ол кез-келгеннің көбейтіндісінен үлкен болады к − 1 олардың.

Олар екеу Құпия бөлісу схемалары негізінен осы идеяны қолданатын, төменде түсіндірілген Миньотта мен Асмут-Блум схемалары.

Миньотенің құпия бөлісу шегі

Бұрын айтылғандай, Миньотаның табалдырық құпия бөлісу схема CRT-мен бірге арнайы деп аталатын бүтін сандар тізбегін пайдаланады (к,n) -Минот тізбектері, олардан тұрады n бүтін сандар, копирование, ең кіші өнім болатындай к олардың көбейтіндісінен үлкен к − 1 үлкендері. Бұл шарт өте маңызды, себебі схема екі өнім арасындағы бүтін сан ретінде құпияны таңдауға негізделген және бұл шарт кем дегенде к акциялар қалай таңдалғанына қарамастан құпияны толығымен қалпына келтіру үшін қажет.

Ресми түрде, рұқсат етіңіз 2 ≤ кn бүтін сандар болуы керек. A (к,n) -Мигно тізбегі - бұл оң бүтін сандардың қатаң түрде өсетін бірізділігі , бірге барлығына 1 ≤ мен < jn, осылай . Біз бұл диапазонды рұқсат етілген диапазон деп атаймыз. Біз (к,n)-табалдырық құпия бөлісу схемасы келесідей: Біз құпияны таңдаймыз S рұқсат етілген ауқымдағы кездейсоқ бүтін сан ретінде. Біз әрқайсысы үшін есептейміз 1 ≤ менn, қысқарту модулі ммен туралы S біз атаймыз смен, бұл акциялар. Енді кез-келгені үшін к әртүрлі акциялар , біз сәйкестік жүйесін қарастырамыз:

Бойынша Қытайдың қалған теоремасы, бері болып табылады копирование, жүйе ерекше шешім модуліне ие . Біздің акцияларымыздың құрылысы бойынша бұл шешім құпиядан басқа ештеңе емес S қалпына келтіру

Asmuth-Bloom шекті құпия бөлісу схемасы

Бұл схемада бүтін сандардың арнайы тізбектері де қолданылады. Келіңіздер 2 ≤ кn бүтін сандар болуы керек. Біз тізбегін қарастырамыз копирование натурал сандар осындай . Осы берілген дәйектілік үшін жиынтықтағы кездейсоқ бүтін сан ретінде S құпиясын таңдаймыз З/м0З.

Содан кейін кездейсоқ бүтін санды таңдаймыз α осындай . Редукция модулін есептейміз ммен туралы , барлығына 1 ≤ менn, бұл акциялар . Енді кез-келгені үшін к әртүрлі акциялар , біз сәйкестік жүйесін қарастырамыз:

Бойынша Қытайдың қалған теоремасы, бері болып табылады копирование, жүйенің ерекше шешімі бар S0 модуль . Біздің акциялардың құрылуы бойынша S құпиясы - бұл төмендету модулі м0 туралы S0.

Mignotte (к,n)-табалдырық құпия бөлісу схемасы кем мағынасында толық емес к акциялар құпия туралы кейбір ақпаратты қамтиды. Асмут-Блум схемасы өте жақсы: α құпияға тәуелді емес S және

Сондықтан α кез келген бүтін модуль болуы мүмкін

Бұл өнім к − 1 модульдер n таңдаулардың ішіндегі ең үлкені к − 1 мүмкін өнімдер, сондықтан кез-келген жиынтық к − 1 эквиваленттер оның көбейтіндісі кез-келген бүтін модуль бола алады және ешқандай ақпарат алмайды S ағып кетті.

Мысал

Төменде Асмут-Блум схемасында мысал келтірілген. Практикалық мақсаттар үшін біз барлық параметрлер үшін кішігірім мәндерді таңдаймыз. Біз таңдаймыз k = 3 және n = 4. Біздің копирование бүтін сандар және . Олар Asmuth-Bloom талап етілетін реттілігін қанағаттандырады, өйткені .

Біздің құпиямызды айтыңыз S 2. таңдау , Асмут-Блум схемасы үшін қажетті шартты қанағаттандыру. Содан кейін және біз 11, 13, 17 және 19 сандарының әрқайсысы үшін үлестерді есептейміз. Олар сәйкесінше 1, 12, 2 және 3 болып табылады. Біз 3 үлестің бір мүмкін жиынтығын қарастырамыз: 3 акциялардың мүмкін болатын 4 жиынтығының ішінен біз жиынтығын аламыз {1,12,2} және оның S = 2 құпиясын қалпына келтіретінін көрсетіңіз. Келесі сәйкестік жүйесін қарастырыңыз:

Жүйені шешу үшін рұқсат етіңіз . Мұндай жүйені шешудің сындарлы алгоритмінен біз жүйеге шешім екенін білеміз , әрқайсысы қайда eмен келесідей:

Авторы Безуттың жеке басы, бері , оң сандар бар рмен және смен, көмегімен табуға болады Евклидтің кеңейтілген алгоритмі, осылай . Орнатыңыз .

Тұлғалардан , біз мұны аламыз және ерекше шешім модулі бұл 155. Соңында, .

Сондай-ақ қараңыз

Әдебиеттер тізімі

  • Oded Goldreich, Дана Рон және Мадху Судан, Қытайлықтарды қателіктермен қалпына келтіру, IEEE ақпарат теориясы бойынша операциялар, т. 46, No4, 2000 жылғы шілде, 1330-1338 беттер.
  • Mignotte M. (1983) Құпияны қалай бөлісуге болады. Бет Т. (ред.) Криптография. EUROCRYPT 1982. Информатикадағы дәрістер, 149 том. Спрингер, Берлин, Гейдельберг.
  • C.A. Асмут және Дж.Блум. Кілттерді қорғауға арналған модульдік тәсіл. Ақпарат теориясы бойынша IEEE мәмілелері, IT-29 (2): 208-210, 1983
  • Сорин Ифтене. Электрондық дауыс беруде қосымшалары бар қытайлық теорема негізінде жалпы құпияны бөлісу. Теориялық информатикадағы электрондық жазбалар (ENTCS). 186 том, (шілде 2007). 67–84 беттер. Басылым жылы: 2007 ж. ISSN  1571-0661.
  • Томас Х. Кормен, Чарльз Э. Лейзерсон, Роналд Л. Ривест, және Клиффорд Штайн. Алгоритмдерге кіріспе, екінші басылым. MIT Press және McGraw-Hill, 2001 ж. ISBN  0-262-03293-7. 31.5 бөлім: Қытайдың қалған теоремасы, 873-876 беттер.
  • Рональд Крамер. Негізгі құпиямен бөлісу (1-2 дәрістер), сынып ескертулері. 2008 ж. Қазан, 1.1 нұсқасы.

Сыртқы сілтемелер