Детерминистическое предварительное распределение ключей и функциональное управление ключами для сетей мобильных датчиков на теле

Детерминистическое предварительное распределение ключей и функциональное управление ключами для сетей мобильных датчиков на теле

Иллюстрации

Показать все

Реферат

Уровень техники

Последующее относится к беспроводным сетям. Оно находит конкретное применение с установкой безопасной передачи информации в пределах беспроводной сети датчиков на теле. Однако следует принять во внимание, что изобретение может также найти применение в обеспечении безопасной передачи данных между другими беспроводными устройствами и другими беспроводными повторителями сигналов.

Мобильные сети датчиков на теле (BSN) привлекли внимание из-за медицинского применения и в целом используются для контроля за пациентом и наблюдения. BSN включает в себя узлы сбора данных и, по выбору, узлы управления. Узлы датчиков питаются от аккумулятора, имеют ограниченные вычислительные возможности и память и основываются на прерывистой беспроводной связи по радиочастоте. Традиционно большая группа (например, тысячи) имеющих возможность взаимодействия узлов разворачивается в медицинском помещении, например больнице, и затем, разным образом, спонтанно соединяются для создания различных разъединенных BSN. BSN обычно состоит из небольшого подмножества (от 2 до 50 узлов) от всех узлов, например узлы, назначенные конкретному пациенту в медицинском помещении. Априори размер и членство BSN неизвестно: узлы BSN могут присутствовать в момент создания BSN или могут быть впоследствии добавлены или удалены. Некоторые узлы имеют ограниченную мобильность после создания BSN, а другие являются высоко мобильными и часто перемещаются по разным независимым BSN, созданным в том же самом помещении (например, узлы сбора данных и управления, переносимые людьми, датчики, одетые на отдельных лиц и т.д.). Некоторые узлы могут быть оставлены без присутствия оператора. Время жизни BSN ограничено несколькими днями, неделями, месяцами и т.д. Время жизни узлов датчиков обычно дольше, чем время жизни экземпляра BSN. BSN создают в общественных помещениях или помещениях с враждебной средой, где передача данных может мониторироваться и узлы датчиков подвержены захвату и манипуляции недобросовестного лица. Перекрестное взаимодействие между узлами сетей BSN, ассоциированных с различными пациентами, может подвергнуть риску медицинскую достоверность регистрируемых данных.

Эти сложные функциональные требования равным образом накладывают сложные ограничения безопасности на конструкцию BSN. Службы безопасности для BSN включают в себя аутентификацию и конфиденциальность передачи данных. Обычно службы управления ключами предоставляют и управляют основными данными безопасности для удовлетворения ранее упомянутых служб безопасности. Вычислительные ограничения и ограничения на передачу данных узлов датчиков BSN делают непрактичным использование любого решения безопасности на основе криптографии с открытым ключом. Узкоспециализированная сущность BSN и функциональные требования BSN делают обычные интерактивные решения на основе серверов неподходящими.

Управление ключами на основе схем предварительного распределения ключей (KPS) является одним вариантом для BSN. Необходимость однозначной аутентификации узла и установки ключей, независимо от членства BSN и размера, налагает строгие требования на KPS для сетей BSN. Однако существующие предложения KPS ограничены для BSN. Во-первых, предварительное распределение ключей по всей сети не предлагает достаточной безопасности или не может управляться в BSN. Во-вторых, простая KPS не является ни масштабируемой, ни управляемой в BSN. В-третьих, устойчивость и масштабируемость KPS Блундо (Blundo)

ограничена памятью и вычислительной мощностью узлов датчиков. В-четвертых, предварительное случайное распределение ключей не предлагает хороших свойств связи для BSN с ограниченным числом узлов. В конечном счете, детерминистическая KPS Кемтепа (Camtepe) и Йенера (Yener) на основе теории комбинаторной схемы

имеет соответствующие свойства связи и небольшую устойчивость для BSN, но не предоставляет уникальных парных ключей.

Басани (Basagni) и др.

представляет схему управления ключами для обеспечения безопасности передач данных датчиков с помощью периодического обновления группового симметричного ключа, совместно используемого всеми узлами датчиков. Эта схема предполагает устойчивые к вмешательству датчики и инфраструктуру управления, соединенную с распределенными сетями датчиков (DSN), предположения, которые не применимы для сетей BSN (крупномасштабная DSN может рассматриваться как соединение многочисленных сетей BSN с одиночными функциональными и сетевыми отличиями. Альтернативно BSN рассматриваются как многочисленные разъединенные части крупномасштабной DSN).

Перриг (Perrig) и др.

предлагает SPINS, архитектуру безопасности, специально спроектированную для сетей датчиков. В SPINS каждый узел датчика совместно использует секретный ключ с базовой станцией. Два узла датчика не могут непосредственно установить секретный ключ. Однако они могут использовать базовую станцию как надежную третью сторону для установления секретного ключа. В сетях BSN базовая станция может не быть доступной в момент установки ключа.

Блундо и др. предлагает KPS на полиномиальной основе для извлечения групповых ключей. Для групп из двух пользователей схема предварительного распределения ключей Блундо может использоваться для установки парных ключей в BSN. Сервер настройки случайно формирует симметричный двумерный со степенью λ полином над конечным полем Fq, где q - это простое число, достаточно большое, чтобы вмещать криптографический ключ. По свойству симметрии . Сервер настройки вычисляет и распределяет полиномиальную часть для каждого датчика u, т.е. Каждый датчик u имеет уникальный идентификатор. После фазы внедрения для двух произвольных узлов u и v узел u может вычислить общий ключ , вычисляя в точке v, и узел v может вычислить тот же самый ключ , вычисляя в точке u.

Устойчивость α KPS Блундо равна , т.е. злоумышленнику необходимо осуществить взлом α датчиков, чтобы суметь сформировать парные ключи невзломанных датчиков. Каждый узел u датчика требует хранения полиномиальной части со степенью λ, которая занимает области памяти. Следует принять во внимание, что λ ограничено памятью m, доступной в датчиках, т.е. ключей. Во время процесса установки парных ключей нет коммуникационных накладных расходов. Для того, чтобы установить парный ключ, оба узла датчика должны вычислить полином в идентификаторе (ID) другого узла датчика. Это требует λ умножений по модулю и λ сложений по модулю в F_q, что может быть затратным в датчиках с ограниченными возможностями центрального процессора (CPV).

Лиу (Liu) и др.

описывают модификацию полиномиального вычисления для приспособления к ограничениям, накладываемым центральными процессорами с низкой битовой скоростью без команды деления, и, таким образом, уменьшают вычислительные требования на датчики. Это достигается уменьшением длины в битах коэффициентов двумерного полинома степени λ до logq' и с помощью выбора q' формы q'=2^k+1.

Лиу и др. показывают, что ключ из logq бит может компоноваться с помощью конкатенации t частичных ключей, сформированных с помощью двумерных полиномиальных частей степени λ с коэффициентами в Fq', где , без значительной потери безопасности, т.е. результирующий logq-битовый ключ обладает аналогичной энтропией, как если он был сформирован с помощью двумерного полинома степени λ с коэффициентами из Fq. Объединенное множество t двумерных полиномов степени λ с коэффициентами из Fq' упоминается как t-полиномиальное множество . T-полиномиальное множество , вычисленное в точке u, в дальнейшем в данном документе это часть t-полиномиального множества.

Недостатком этой методики является то, что полиномиальная функция над Fq' может вмещать только максимальное число q'-1 датчиков (вместо q-1). Конкретно, t полиномов над Fq', скомбинированных параллельно (т.е. t-полиномиальное множество) могут лишь вмещать максимум N'=q'-1 узлов. Например, для 8-битовых центральных процессоров, q'=2⁸+1 предлагает оптимальную вычислительную производительность, но тогда число N' максимальных узлов равно 256. Еще сохраняющееся свойство - это то, что каждый двумерный полином над Fq' и, таким образом, t-полиномиальное множество является устойчивым против λ- объединения. Технология полиномиального разбиения может применяться к любой основанной на полиномах KPS при некоторой нижней границе по λ, налагаемой q, q' и полным числом полиномов над Fq', используемым схемой KPS.

Сбалансированная схема неполных блоков (BIBD) является расположением v отдельных объектов в b блоках из условия, что каждый блок содержит точно k отдельных объектов, каждый объект присутствует точно в r разных блоках, и каждая пара отдельных объектов присутствует вместе в точно t блоках. Схема может быть выражена как (v, k, t) или эквивалентно (v, b, r, k, t), где: r(v-1)=r(k-1) и bk=vr.

В симметричной BIBD (SPIBD) b=v и, таким образом, k=r. SPIBD имеет четыре свойства: каждый блок содержит k=r элементов, каждый элемент присутствует в k=r блоках, каждая пара элементов присутствует в t блоках и каждая пара блоков пересекается в t элементах.

При заданной схеме D=(v, k, t) блока с множеством S из │S│=v объектов и множеством B ={B₁, B₂,…B_b} из │B│=b блоков, где каждый блок включает в себя в точности k объектов, комплементарная схема имеет комплементарные блоки в качестве своих блоков для 1≤i≤b. является BIBD с параметрами (v, b, b-r, v-k, b-2r+t), где b-2r+t>0. Если D=(v, k, t) является SBIBD, тогда является также SBIBD.

Конечные проективные плоскости (FPP) являются подмножеством SPIBD особого интереса для предварительного распределения ключей. FPP является SPIBD с параметрами (n²+n+1, n+1, 1). FPP существует для любой простой степени n, где n≥2. FPP порядка n имеет четыре свойства: (i) каждый блок содержит в точности n+1 точек, (ii) каждая точка присутствует в точности в n+1 блоках, (iii) существует в точности n²+n+1 точек, и (iv) существует в точности n²+n+1 блоков. Камтеп и Йенер

применяют схему SBIBD для предварительного распределения ключей в SN.

Рассмотрим FPP с параметрами (n²+n+1, n+1, 1), с элементами, принадлежащими множеству S, где │S│=n²+n+1. Используя терминологию Эсченауэра (Eschenauer) и Глигора (Gligor)

S ассоциируется с совокупностью ключей, т.е. каждый элемент в S ассоциируется с отдельным случайным ключом. Дополнительно каждый блок FPP ассоциируется с кольцом ключей. Свойства FPP гарантируют, что любая пара колец ключей (блоков) имеет 1 случайный ключ (элемент) совместно.

Для сети датчиков (SN) из N узлов с общим числом N колец ключей, FPP с n²+n+1≥N блоков должна строиться посредством использования множества S. Это предоставляет n²+n+1≥N колец ключей, при этом каждое имеет K=n+1 ключей и один ключ совместно. Размер памяти, необходимый на узлах, равен тогда (n+1)×logq (эквивалентно m=n+1). Умному злоумышленнику нужно захватить α=K=n+1 узлов, чтобы суметь взломать SN.

Каждый узел датчика SN численности N принимает разное кольцо ключей. Заметим, что каждые два узла совместно используют совместный конкретный ключ. Действительно, из-за свойств плоскостей FPP, каждые n+1 датчиков совместно используют один и тот же конкретный ключ. Следовательно, ключи этой KPS не могут использоваться для однозначной аутентификации узла. Второй связанной проблемой является то, что не всегда возможно отыскать FPP, в которой (i) n является простой степенью и (ii) n²+n+1≥N, с ограничением m≥n+1.

Камтеп и Йенер решают вышеуказанную проблему созданием гибридной схемы, которая включает в себя n²+n+1 блоков плоскости FPP (n²+n+1, n+1, 1), где n<m-1 (т.е. теперь размер кольца ключей m≥K>n+1) и N-n²+n+1 произвольно выбранных (n+1) - элементных подблоков плоскости (n²+n+1, n², n²-n). Побочными эффектами являются: (i) K>n+1, (ii) некоторые конкретные ключи совместно используются более, чем n+1 узлами, (iii) некоторые пары узлов могут совместно использовать до совместных n²-n ключей и (iv), по меньшей мере, N-n²+n+1 блоков не имеют совместного ключа. Таким образом, из-за (iv), по меньшей мере, N-n²+n+1 не могут непосредственно установить совместный ключ, и из-за (i), (ii) и (iii) α≤n+1<K≤m, т.е. устойчивость сети снижается.

Недавно было предложено множество схем управления случайными ключами на основе предварительного распределения ключей для обеспечения безопасности инфраструктуры передачи данных крупномасштабных DSN. Такие схемы управления предполагают возможность соединения со всей DSN на основе предположений, что узел датчика может беспроводным образом соединяться с минимальным уровнем соседних узлов (например, узлами в диапазоне беспроводной передачи данных) и что узлы датчиков имеют очень ограниченную мобильность после применения. Эти схемы нацелены на максимальную безопасную связь по всей DSN и устойчивость сети при удовлетворении функциональным ограничениям сетей DSN. В схемах управления предварительным распределением случайных ключей каждый узел принимает до применения случайное подмножество ключей из большой совокупности ключей. Для того чтобы согласовать ключ для безопасной передачи данных с некоторой вероятностью, два соседних узла находят один общий ключ в их подмножествах и используют этот ключ как их совместно используемый секретный ключ. Два узла датчиков, которые не находят общий ключ, используют другие надежные узлы в своем окружении и даже некоторые непрямые передачи, чтобы помогать устанавливать общий ключ. Схемы предварительного распределения случайных парных ключей, основанные на схемах Блома (Blom)

или Блундо, улучшают предшествующее с помощью повышения устойчивости сети и дополнительного предоставления аутентификации узлов.

Однако схемы предварительного распределения случайных ключей не подходят для обеспечения безопасности BSN. Во-первых, из-за малой степени соседствующих узлов, BSN не всегда позволяет двум произвольным узлам прямо или косвенно устанавливать общий ключ. Во-вторых, из-за возможности захватов узлов, аутентификация узлов должна выполняться напрямую без каких-либо посредников.

Так как независимые BSN не соединены, централизованные или распределенные глобальные системы обнаружения проникновения (IDS), предлагаемые для DSN или для специальных сетей, не могут использоваться в BSN. Взломанный узел может быть обнаружен в BSN, но традиционные системы и способы не распространяют эффективно эту информацию остальным узлам в других BSN. Следовательно, BSN намного более уязвимы к атакам репликации узлов, чем крупномасштабная DSN. В больницах, например, атаки интеллектуального злоумышленника являются наибольшей угрозой для безопасности BSN. Хотя в литературе не четко сформулировано, устойчивость сети в отношении захватов узлов и репликации узлов предыдущих схем предварительного распределения ключей сильно зависит от существования IDS, эффективной по всей DNS. Отсутствие устойчивости сети определяется как число λ узлов, которые злоумышленнику необходимо захватить, чтобы взломать некоторую часть всех передач данных DSN. Интеллектуальный злоумышленник не беспокоится о захвате и вмешательстве в λ узлов, чтобы осуществить атаку. Интеллектуальный злоумышленник лишь захватывает один или малую часть узлов и использует расшифрованные ключи для атаки на сеть. В действительности, чтобы продолжать быть необнаруженным, злоумышленник не пытается прерывать сетевые операции сети, но пытается считать или модифицировать конфиденциальную информацию или даже ввести ложные сообщения. Таким способом злоумышленник может получить и/или ввести требуемую информацию даже без необходимости затрат своих собственных ресурсов, чтобы взломать другие сетевые передачи данных.

В конечном итоге механизм установки ключей, поддерживаемый соседями, необходим в некоторых схемах для достижения высокой степени безопасного соединения DSN. Злоумышленник с соответствующими ключами может получить помощь от одного или более прилегающих узлов, узлов, смежных с такими узлами, и так далее, чтобы установить ключи с полным окружением соседей. Если безопасное соединение жертвуется, чтобы улучшить безопасность посредством ограничения помощи установки ключей для окрестности соседей узла, злоумышленник все еще может продвигаться и пытаться атаковать настолько много соседних узлов, насколько это возможно. Эффективная и безопасная схема управления ключами должна принимать во внимание интеллектуального злоумышленника, особенно в установках BSN.

Что необходимо, это схема предварительного распределения ключей, которая дает возможность аутентификации, конфиденциальности и целостных услуг и обеспечивает улучшенное безопасное сетевое соединение, устойчивость и масштабируемость, связанные с оптимальным уровнем производительности. Также необходима схема управления ключами, которая управляет использованием предварительно распределяемых ключей, подходящая для функциональных условий BSN. Настоящее изобретение рассматривает улучшенное устройство и способ, которые преодолевают вышеупомянутые ограничения и другие.

Краткое описание изобретения

Согласно одному аспекту беспроводная сеть для контроля пациента содержит сеть датчиков на теле, состоит из одного или более беспроводных датчиков, оперативно соединенных с пациентом, которые собирают и передают информацию, связанную со здоровьем пациента, в беспроводную сеть. Сервер настройки конфигурирует один или более беспроводных датчиков с помощью материала ключей до того, как один или более датчиков будут использованы в беспроводной сети. Мобильная базовая станция распределяет сертификат ключа в один или более датчиков, ассоциированных с сетью датчиков не теле, при этом два датчика формируют уникальный парный ключ, базируясь, по меньшей мере, частично на предварительно распределенном материале ключей и сертификате ключей, распределяемом базовой станцией.

Согласно другому аспекту беспроводная сеть включает в себя сеть, которая состоит из одного или более беспроводных узлов, и сервер настройки, который конфигурирует один или более беспроводных узлов с помощью материала ключей до того, как один или более узлов будут использоваться в беспроводной сети. Базовая станция распределяет сертификат ключей в один или более датчиков, ассоциированных с сетью, при этом два узла формируют уникальный парный ключ, базируясь частично, по меньшей мере, на предварительно распределенном материале ключей и сертификате ключей, распределяемом базовой станцией.

Согласно другому аспекту способ вычисляет и распределяет части t-полиномиальных множеств, используя комбинаторное распределение, для того, чтобы максимизировать масштабируемость, устойчивость и уровень производительности беспроводной системы, которая включает в себя предварительное распределение ключа безопасности через сервер настройки в узел u датчика и узел v датчика, которые передают данные в беспроводной системе.

Согласно еще одному аспекту способ определяет датчик u в системе мобильных датчиков, что включает в себя образование конечной проективной плоскости (n²+n+1, n+1, 1) из множества n-1 взаимно ортогональных Латинских квадратов порядка n, где n является простой степенью. Общая часть t-полиномиального множества эффективно обнаруживается, и точка вычисления части t-полиномиального множества эффективно выводится датчиком v из идентификатора датчика u.

Одним преимуществом настоящего изобретения является то, что оно предоставляет ключи безопасности большому множеству узлов датчиков, оптимизируя передачу данных, эффективность вычислений и хранения для аккумулятора, мощности центрального процессора и узлов с ограниченной памятью.

Другим преимуществом является то, что оно обеспечивает улучшенную силу защиты для предварительно распределяемых безопасных ключей большому множеству узлов датчиков.

Другим преимуществом является то, что безопасность предусмотрена прозрачной для пользователей беспроводной сети.

Другим преимуществом является то, что обеспечивается безопасность, которая допускает однозначную идентификацию идентичности любой произвольной пары узлов датчиков (большого множества датчиков) и установку надежных связей независимо от плотности беспроводного окружения соседей датчиков или размера.

Другим преимуществом является то, что безопасность уменьшает степень, до которой может быть взломана беспроводная сеть.

Многочисленные дополнительные преимущества и выгоды станут видны специалистам в данной области техники при прочтении последующего подробного описания предпочтительных вариантов осуществления.

Краткое описание чертежей

Изобретение может принимать форму в различных компонентах и конфигурациях компонентов и в различных этапах и конфигурациях этапов. Чертежи приводятся лишь для целей иллюстрации предпочтительных вариантов осуществления и не должны толковаться как ограничивающие изобретение.

Фиг.1 иллюстрирует систему мобильных датчиков, которая использует сервер настройки для конфигурирования материала ключей во множестве датчиков во время фазы предварительного применения.

Фиг.2 иллюстрирует способ для обеспечения безопасной передачи данных между парой беспроводных датчиков, используя уникальные парные ключи.

Фиг.3 также показывает, как использовать идентификатор датчика в системе мобильных датчиков, например системе на фиг.1.

Фиг.4 иллюстрирует другой способ для идентификации датчика в системе мобильных датчиков, например в системе на фиг.1. Фиг.4 также показывает, как использовать идентификатор датчика в системе мобильных датчиков, например в системе на фиг.1.

Фиг.5 иллюстрирует способ обнаружения общей части t-полиномиального множества.

Фиг.6 иллюстрирует способ для извлечения точки вычисления части t-полиномиального множества.

Фиг.7 иллюстрирует систему мобильных датчиков, которая использует сервер настройки для конфигурирования материала ключей во множестве датчиков во время фазы предварительного применения.

Фиг.8 иллюстрирует систему мобильных датчиков, которая использует сервер безопасности и базовые станции, чтобы делать возможной безопасную передачу данных между множеством датчиков и соответствующими сетями датчиков на теле в системе мобильных датчиков во время фазы последующего применения.

Фиг.9 иллюстрирует способ предварительного распределения ключей, который использует симметричную схему Блома предварительного распределения ключей.

Фиг.10 иллюстрирует способ предварительного распределения ключей, который использует схему Блундо для предварительного распределения ключей.

Фиг.11 иллюстрирует способ для сертификации предварительно распределенных ключей.

Фиг.12 иллюстрирует способ управления предварительно распределенными ключами.

Фиг.13 иллюстрирует способ управления предварительно распределенными ключами.

Фиг.14 иллюстрирует способ управления предварительно распределенными ключами.

Фиг.15 иллюстрирует способ управления предварительно распределенными ключами.

Подробное описание предпочтительных вариантов осуществления

Система детерминистического предварительного распределения парных ключей (DPKPS) и способы

Фиг.1 иллюстрирует систему 2 мобильных датчиков, которая включает в себя сервер 4 настройки, множество беспроводных датчиков 6, 8, 10, 12, 14, 16, 18 и 20 и множество сетей 22, 24 и 26 датчиков на теле. Сервер 4 настройки является выделенным сервером безопасности, который активно участвует в безопасности лишь до применения датчиков. Беспроводные датчики 6-20 соединяются с сервером 4 настройки в начальной фазе конфигурирования (например, предварительного применения) до того, как используются датчики 6-20. Сервер 4 настройки обычно постоянно находится в пределах физически защищенного периметра, доступный лишь авторизованному персоналу. Во время фазы применения беспроводные датчики не имеют никакого средства соединения с сервером настройки. Обычно участок применения публично доступен. Беспроводные датчики 6-20 являются узлами, отвечающими за сбор и перемещение медицинских данных пациентов. Любой из датчиков 6-20 устанавливает беспроводные передачи данных с одним или более датчиков 6-20. Узлы датчиков имеют ограничения памяти, аккумуляторов и центрального процессора (CPV). Сети 22-26 датчиков на теле (BSN) являются множеством беспроводных сетевых узлов датчиков, которые могут присоединяться к одному или более пациентам (не показаны). BSN 22-26 обычно ограничены по пропускной способности из-за большого числа узлов в системе. Например, в среде больницы могут быть сотни или тысячи BSN (например, одна для каждого пациента).

Применение BSN требует ключей из logq бит. Согласно варианту осуществления , при этом t≥1. При фиксированном q для требуемого уровня безопасности (например, 64 бита), полиномы в Fq' могут вычисляться и применяют оптимизацию полиномов Лиу и др. для получения ключа из logq бит. Объединенное множество из t двумерных полиномов степени λ с коэффициентами над Fq' упоминается как t-полиномиальное множество . T-полиномиальное множество , вычисленное в точке u, в дальнейшем является частью t-полиномиального множества.

Фиг.2 иллюстрирует способ 30, который состоит из способа 32 настройки, способа 34 предварительного применения ключей, способа 36 обнаружения частей t-полиномиального множества и способа 38 установки ключей, используемого для установки уникальных парных ключей между датчиками, например, с помощью системы 2, приведенной выше. В 32, сервер настройки формирует части t-полиномиального множества и комбинаторную схему, которая может использоваться, чтобы вмещать N датчиков, где N является размером группы узлов, имеющих возможность взаимодействовать, и является целым числом, большим, чем или равным единице. В 34 сервер настройки распределяет части t-полиномиального множества в каждый датчик согласно комбинаторному распределению. Если были применены на 36, два произвольных датчика u и v обнаруживают, какую часть t-полиномиального множества они имеют совместно. На 38 два произвольных датчика u и v формируют уникальный парный ключ K_uv с помощью вычисления их общей части t-полиномиального множества.

Один аспект настоящего варианта осуществления увеличивает масштабируемость KPS на основе t-полиномиальных множеств без снижения ее устойчивости при поддержке оптимального узлового уровня производительности. В одном подходе n+1 t-полиномиальных множеств распределяются в каждый узел u, следуя FPP (n²+n+1, n+1, 1), т.е. с помощью ассоциирования N'/(n+1) отдельных частей каждого t-полиномиального множества с каждым элементом , j=1…n+1, принадлежащим блокам B_i, i=n²+n+1, плоскости FPP. Из-за свойств FPP два произвольных узла u и v относительно n+1 частей t-полиномиальных множеств, распределяемых согласно элементам различных блоков B_i, , i≠j, совместно используют одно t-полиномиальное множество F_k(x,y), которое они могут использовать для вычисления уникального парного ключа из logq бит. Аналогично, два узла с соответствующими n+1 частями t-полиномиального множества, распределяемыми согласно элементам одного и того же блока , имеют n+1 частей t-полиномиального множества совместно. Таким образом, узлы могут использовать любую из n+1 частей t-полиномиального множества для вычисления уникального парного ключа из logq бит.

Этот способ разрешает увеличивать масштабируемость схем KPS Блундо и др., а также Кемтепа и Йенера без какой-либо потери в сетевой устойчивости и в то время как сохраняют вычислительную производительность на оптимуме и вероятность единица совместного использования уникального парного ключа. Кроме того, подобный подход решает проблему существования плоскости FPP схемы KPS Кемтепа и Йенера без понижения в сетевой устойчивости или прямом надежном соединении.

В 32 сервер настройки случайно формирует множество из двумерных полиномов степени λ над Fq'. Впоследствии для j=1…n²+n+1 сервер настройки последовательно выбирает полиномы из и формирует n²+n+1 t-полиномиальных множеств F_j(x,y). Затем он формирует FPP (n²+n+1, n+1, 1) с элементами, которые принадлежат множеству S, где │S│=n²+n+1. Множество S ассоциировано связано с полиномиальной совокупностью, т.е. каждый элемент j в S ассоциирован с отдельным t-полиномиальным множеством F_j(x,y). Дополнительно, каждый блок FPP ассоциирован с полиномиальным кольцом. Свойства FPP гарантируют, что любая пара полиномиальных колец (блоков FPP) имеет одно t-полиномиальное множество F_k(x,y) (элемент к) совместно.

В 34 каждый узел u датчика принимает от сервера настройки n+1 частей t-полиномиального множества, где , и j=1…n+1. Точка p_u,j должна браться из конечного поля Fq'. Это ограничивает p_u,j до q'-1 различных возможных значений. Однако число датчиков N для вмещения может быть больше, чем q'-1. Для того, чтобы гарантировать уникальность парных ключей, два различных датчика u и v не могут иметь то же самое t-полиномиальное множество F_k(x,y), вычисляемое в той же самой точке p_k. Так как каждое t-полиномиальное множество F_j(x,y), j=1…n²+n+1, может быть вычислено в N'=q'-1 различных точках и индекс j от F_j(x,y) появляется в n+1 блоках FPP, то каждый из этих блоков (где встречается j) используется для предварительного распределения отдельных частей F_j(x,y) не в более чем N'/(n+1) различных датчиках. Процесс предварительного распределения ключей для смещения N≤N'n(1-1/(n+1))+N' узлов использует следующие этапы:

1. Начиная с первого блока B₁ плоскости FPP с элементами первый узел (u₁) принимает части по t-полиномиального множества, вычисленные в точке p₁ из Fq'; второй датчик (u₂) принимает по , вычисленные в точке p₂; и так далее; до тех пор, когда N'/(n+1)-ый датчик (u_N'/(n+1)) принимает по вычисленные в точке p_N'/(n+1).

2. Следуя со вторым блоком B₂ из FPP с элементами , предположим, что , датчик u_1+N'/(n+1) принимает , которая вычисляется в точке p_1+N'/(n+1) (так как уже вычислено в нижних точках для датчиков u₁ … u_N'/(n+1)), и по вычислены в точке p₁; и так далее, и

3. Повтор первого и второго этапов, чтобы вместить N узлов системы, используя все блоки FPP.

В 36 обнаруживаются части t-полиномиального множества. После применения до установки парного ключа каждый узел u датчика должен обнаружить, какое t-полиномиальное множество он совместно использует с его соседним узлом v. Для этого узлы u и v обмениваются своими идентификаторами (ID), которые явно содержат индексы n+1 частей t-полиномиального множества, которые они несут с собой и точки , , где вычисляются соответствующие n+1 частей t-полиномиального множества. В конечном итоге, они находят индекс к (соответствующий общему t-полиномиальному множеству F_k(x,y) и соответствующие точки p_u и p_v вычисления.

В 38 устанавливается ключ. Для того, чтобы вычислить парный ключ K_uv, узел u вычисляет t двумерных полиномов степени λ (включенных в F_k(p_u,y) для i=1…t в точке p_v (т.е. для получения t частичных ключей. Затем узел u усекает упомянутые t частичных ключей до logq' бит и конкатенирует t сегментов ключей для образования конечного парного ключа K_uv из logq бит.

Простой ID датчика

Фиг.3 иллюстрирует способ 50, который определяет датчик u в DPKPS. В 52 n+1 индексов b_i,1,…b_i,n+1 n+1 частей t-полиномиального множества, которые он несет, конкатенируются с n+1 точками , где они вычисляются. В 54 такой ID однозначно определяет датчик u и в 56 делает возможным очень простое обнаружение общих частей t-полиномиального множества и точки вычисления части t-полиномиального множества.

В 58 общая часть t-полиномиального множества обнаруживается с помощью использования простого ID датчика, два датчика u и v находят, какой индекс является общим в соответствующих ID, например индекс k. В 60 точка части t-полиномиального множества вычисления выводится получением k-той точки, включенной в простой ID датчика.

Оптимизированный ID датчика

Так как использование простых ID датчика значительно увеличивает затраты на хранение и передачу данных DPKPS, когда возрастает n, может применяться альтернативный способ оптимизированного ID датчика с помощью использования свойств FPP, основанных на взаимно ортогональных латинских квадратах (MOLS). Этот оптимизированный способ строит ID датчиков с очень короткой длиной для фактических значений n.

Фиг.4 показывает способ 70, используемый для идентификации датчика в системе мобильных датчиков, например системе 2 выше.

выводится из множества n-1 взаимно ортогональных латинских квадратов (MOLS) порядка n. Латинский квадрат является квадратной n×n матрицей L, элементы которой состоят из n символов так, что каждый символ появляется точно один раз в каждой строке и каждом столбце. Символы используются как целые значения от 1…n. Очень простым способом построить L является размещение целых чисел 1,2,…n в их обычном порядке в первой строке и для последовательных строк с помощ