Построение идеальной (t + 1, n) пороговой схемы - Применение хэш-функций для схемы разделения секрета, основанной на латинском квадрате

Продолжим идею примера, представленного выше и возьмем секрет, являющийся хэш-значением латинского квадрата. Предложим способ применения хэш-функции f для создания (t + 1, n) пороговой схемы разделения секрета.

Во-первых, случайно сгенерируем участникам части более или менее одинакового размера с хэш-значением. Затем, выделим различные санкционированные подмножества такие, что каждое подмножество состоит из (t + 1) или более различных участников.

Пусть N - размер структуры доступа, то есть общее число санкционированных подмножеств: N = C (n, t + 1) + C (n, t+2) + ... + C (n, n),

Где

Таким образом нам необходимо иметь N сообщений для N санкционированных подмножеств.

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

Предположим, что санкционированная группа состоит из участников P1, P2, ..., PBИ их части m1, m2, ..., mBВ свою очередь являются отдельными частями сообщения M. Когда они соберутся вместе, они смогут сформировать закрытое сообщение MPriv = m1 || ... || mB и найти соответствующее связывающее открытое сообщение MPub, как показано на рисунке 3. Затем они смогут восстановить секрет g, применяя хэш-функцию к MPriv || MPub, то есть f(MPriv || MPub) = h.

сообщение m и его части

Рисунок 3. Сообщение M и его части.

В атаке Нострадамуса нам необходимо следующее:

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

Но в нашем случае этого делать не нужно, так как мы уже знаем хэш-значения этих N сообщений. Это снижает затраты на вычисления во много раз.

Для любого сообщения MPriv, полученного комбинацией частей участников санкционированной группы, есть соответствующее сообщение MPub в дереве хэш-значений. Их соединение приведет нас к итоговому хэш-значению. Таким образом у нас есть (t + 1, n) пороговая схема, построенная с помощью техники "подгона" хэш-значения. Связывающие сообщения могут храниться в месте, доступном свободно для любого из участников. Когда любая группа участников числом t + 1 или более соберется вместе, они смогут использовать соответствующее связывающее сообщение и свои части для восстановления секрета.

Свойства предложенной схемы:

    - Схема совершенна. Одно из основных свойств криптографических хэш-функций - это их случайность. Имея сообщение, мы не сможем получить никакой информации о его хэш-значении. Таким образом исключается вероятность обнаружения частичной информации кем бы то ни было из участников. Когда все участники соберутся вместе, они смогут восстановить секрет, применяя хэш-функцию f к сообщению M = MPriv || MPub. Чтобы поддержать необходимый уровень безопасности, длина каждой части должна быть как минимум равна длине хэш-значения. С другой стороны, увеличение длины части не увеличивает уровень безопасности. Поэтому желательно иметь случайно сгенерированные части, длиной примерно равной хэш-значению. Это будет выполнятся в случае, если сообщение сгенерировано случайно, что обеспечивает совершенную схему, потому что если отсутствует хоть один из участников, то его часть не сможет быть восстановлена и не удастся получить никакой информации о самом секрете. - Схема идеальна. Каждый участник имеет часть, равную длине хэш-значения. - Быстрое восстановление секрета. Значение хэш-функции вычисляется достаточно быстро, что обеспечивает быстрое восстановление частичного латинского квадрата и, следовательно, полного. - Отсутствие критических множеств. С использованием новой схемы отсутствует необходимость в поиске критических множеств. Это делает схему более эффективной и контролируемой.

Похожие статьи




Построение идеальной (t + 1, n) пороговой схемы - Применение хэш-функций для схемы разделения секрета, основанной на латинском квадрате

Предыдущая | Следующая