ПРОВЕРКА КОМПОНЕНТОВ В СХЕМЕ РАСПРЕДЕЛЕНИЯ СЕКРЕТА НА ОСНОВЕ КОДОВ, ИСПРАВЛЯЮЩИХ ОШИБКИ

​VERIFICATION OF COMPONENTS IN SECRET SHARING SCHEME BASED ON ERROR-CORRECTING CODES

Artak Khemchyan Ararat

Candidate of Science, assistant professor in Information Security and Software Development Department, National Polytechnic University of Armenia,

Armenia, Yerevan

АННОТАЦИЯ

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

ABSTRACT

Secret sharing schemes are intended for the safe storage of information. Recently, the subject of studies has been secret sharing schemes based on error-correcting codes. The relationship between the secret sharing schemes and error-correcting codes were discussed in 1981. The advantage of these schemes is their performance. In addition to the possibilities of sharing and recovery, the sharing process requires verification of components, the recovery of the damaged or lost component, as well as the ability to upgrade the existing components. This article provides a method of verification of components for this scheme. In the secret sharing schemes, participants do not trust each other and each of them, including the dealer, can be in the role of an opponent. The method of component verification for secret sharing schemes based on error-correcting codes. The above method is based on the method of verification for Shamir threshold scheme is also introduced. We also consider the safety of the proposed method.

Ключевые слова: распределение секрета; пороговая схема; коды, исправляющие ошибки; проверка компонента; восстановление компонента; обновление компонента.

Keywords: secret sharing, threshold scheme, error-correcting codes, component verification, component recovery, component update.

Схемы распределения секрета были созданы для надежного хранения информации. В первые такая схема была предложена в 1979 году одновременно и Шамиром [1, с. 612] и Блеклием [2, с. 313]. В настоящее время наиболее популярными являются так называемые пороговые схемы. В таких схемах секрет делится между участниками таким образом, чтобы сочетанием некоторого количества компонентов можно было восстановить секретную информацию, а при меньшем количестве компонентов не было возможности восстановить секретную информацию. Схемы с такими свойствами называются пороговыми.

В последнее время предметом исследований являются схемы распределения секрета на основе кодов, исправляющих ошибки. О связи схем распределения секрета и кодов, исправляющих ошибки, говорили еще в 1981 году [3, с. 583]. Преимуществом этих схем является их скорость.

Как и в других схемах, в схемах распределения секрета, могут возникнуть непредвиденные обстоятельства. Однако возможности восстановления и распределения секрета недостаточно. В таких системах планируются проверка компонентов, восстановление утраченного или поврежденного компонента, получение новых компонентов, обновление компонентов и другие возможности. Например, в известной схеме Шамира все эти возможности доступны. В данной статье представлены методы проверки подлинности и восстановления утерянного или испорченного компонента.

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

Предлагаемый метод проверки компонентов основан на методе Шамира, поэтому рассмотрим этот метод более подробно. Суть этого алгоритма заключается в следующем:

• Как известно, в схеме разделения секрета секрет разделяется с помощью сгенерированного многочлена, в котором свободный член сам секрет [4, с. 43]:

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

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

Для описания метода проверки компонентов для схемы, представленной в [5, с. 62], в первую очередь следует рассмотреть структуру компонента файла. Структура файла представлена на рисунок 1.

Рисунок 1. Структура компонента файла

• Part number – номер компонента.
• Number of components – количество всех компонентов.
• Threshold – значение порога.
• Shamir size – длина Shamir Sharing сектора, выраженных в байтах.
• Shamir CRC - CRC32 значение Shamir size сектора.
• Content CRC – CRC32 значение распределенной части.
• Code ID – номер кода, который использовался при распределение.
• Table ID – номер таблицы, который использовался при распределении
• ID1ID2…IDn – пароль, использованный при перестановке таблицы
• Content – распределенные данные

При данном методе распределения проверка подлинности компонентов основана на проверке отрезков Shamir size и Content на подлинность. Дилер перед распределением определяет числа ,  и , затем вычисляет  и публикует их. Далее для распределения выбирает код, исправляющий ошибки, и ту таблицу, с помощью которой должны быть произведены распределения секретных данных. Далее дилер генерирует пароль, добавляет номер кода, исправляющего ошибки, номер использованной таблицы и, считая его в качестве секрета, выполняет распределение отрезков по схеме Шамира. В качестве данных распределения принимаются те данные компонентов и порогового значения, которые используются во время распространения секретного файлов с помощью кодов. После этого приступает к распределению секрета по способу, описанному в [5]. После распределения секретные данные уничтожаются. В последнем шаге дилер рассчитывает и публикует CRC32 значения (CRC1, CRC2, ..., CRCt) компонент файлов. Учитывая, что CRC32 является односторонней функцией, можем утверждать, что ее публикация ничего не раскрывает о компоненте и, следовательно, не вызывает никаких проблем с точки зрения безопасности. Таким образом, процесс распределения дилером заканчивается.

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

1. После приема компонента необходимо отделить Shamir sharing сектор и описанным выше алгоритмом проверить подлинность этого сектора (с использованием данных, опубликованных дилером). Если ошибка не обнаружена, то владелец компонента должен продолжить проверку подлинности сектора Content. В противном случае компонент считается фальсифицированным (изменен или поврежден).
2. В случае положительного результата первого пункта владелец компонента вычисляет значение CRC32 сектора Content и сравнивает его с соответствующим значением CRC дилера. При совпадении считается, что изменений не было сделано, и этот процесс должен быть завершен.

Как видно из вышеизложенного, в процессе не участвовали сегменты Part number, Number of components, Threshold, Shamir size и Shamir CRC. Причина их неучастия в следующем:

1. Сектора Part number, Number of components и Threshold считаются известными, и для их проверки каких-либо дополнительных алгоритмических решений не требуются. Следует прочитать и сравнить их с ранее известными данными и в случае каких-либо расхождений считать содержание сегмента измененными и непригодным.
2. В проверке сектаров Shamir size и Shamir CRC нет необходимости, так как изменение хотя бы одного из них привело бы к неправильному результату при проверке сектора Shamir sharing.

Таким образом, процесс проверки подлинности компонентов можно считать завершенным.

Теперь рассмотрим надежность проверки компонентов этим методом. Можно ли "обмануть" этот метод? Так как процесс проверки делится на две части, рассмотрим каждую часть отдельно.

Проверка сектора Shamir sharing основана на методе Шамира, и считается что этот метод обеспечивает полную безопасность. Поэтому проверка подлинности этого сектора не вызывает сомнений.

Во время проверки сектора Content используется значение CRC32, которое можно считать хэш-функцией. Конечно, есть конфликт хэш-функции и теоретически есть вероятность, что там будет другой сектор Content у которого то же значение CRC32. Однако, учитывая, что Content большого объема, и объем этого сектора не секрет, то проблемы противника значительно осложняются. Он должен попытаться найти другую последовательность той же длины, которая имела бы такое же значение CRC32. Хотя эта операция довольно сложное и занимает много времени, но в случае необходимости, можно заменить CRC32 на более длинные хеш-функции для более высокого уровня безопасности, при которых будет трудно (практически невозможно) найти битовую последовательность такого же размера, который имел бы эту хеш значение.

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

Список литературы:

1. Shamir A. How to share a secret // Commun. ACM 1979. - Vol. 22, no. 11 - P.612-613.
2. Blakley G.R. Safeguarding cryptographic keys // Proc. NCC AFIPS - 1979. - P. 313-317.
3. McEliece R, J., Sarwate D.V. On sharing secrets and Reed-Solomon codes // Comm. ACM 1981. – 24 – P.583-584.
4. Margarov G.I., Markarov V.G., Khachaturov A.G. Steganographic system with dynamically reconfigurable structure // Proceedings of the 2009 International Conference on Security & management, SAM'09 // Las Vegas: CSREA Press, 2009. - Vol.1 - P. 43-45.
5. Khemchyan A.A., Margarov G.I. Secret sharing based on error-correcting codes // Procedings of information technologies, electronics, radio engineering // NPUA Armenia, 2015. - Vol.1 - P.62-67.