Реферат Отчет 97 с., 4 ч., 11 рис., 11 табл., 4 прил., 40 источников. Шифрование с возможностью поиска, зашифрованный индекс




страница5/10
Дата06.06.2016
Размер0.53 Mb.
1   2   3   4   5   6   7   8   9   10

2.3.Компоненты алгоритма

2.3.1.Используемые криптопримитивы


Основой для функционирования схемы SSE является криптосистема с закрытым ключом, которая состоит из трех алгоритмов: . Алгоритм генерирует секретный ключ на основе некоторого параметра безопасности. Алгоритм с помощью секретного ключа шифрует документ. В свою очередь алгоритм расшифровывает полученное зашифрованное сообщение с помощью закрытого ключа. Выбор является частным вопросом реализации, однако рекомендуется выбирать схему, которая соответствует нотации безопасности CPA-secure [24].

Кроме в SSE применяются псевдо случайные функции . Каждая из этих функций принимает на вход битовую строку и возвращает определенную битовую последовательность некоторой длины: . Псевдо-случайные функции используются в схеме в процессе шифрования индекса файловой коллекции.

2.3.2.Секретный ключ


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

2.3.3.Зашифрованный индекс


Зашифрованный индекс – это структура, которая позволяет серверу производить поиск по хранящимся на нем документам в зашифрованном виде, не зная, что они представляют собой. Зашифрованный индекс основан на инвертированном индексе [4], который представляет собой структуру данных, где каждому отдельному слову ставится в соответствие документы, в которых оно содержится. В схеме SSE зашифрованный индекс представляет собой совокупность четырех структур данных: поисковый массив, поисковая таблица, массив удаления и таблица удаления.

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

2.4.Работа алгоритма

2.4.1.Построение зашифрованного индекса


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

Построение поискового массива

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



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

Построение поисковой таблицы

Каждый список узлов имеет соответствующую запись в поисковой таблице :



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

Построение массива удаления

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



,

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

Построение таблицы удаления

Каждый список узлов имеет соответствующую запись в таблице удаления :



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

Запись свободных ячеек

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

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



В заносятся данные о первом элементе списка свободных ячеек :



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

2.4.2.Поиск по ключевому слову


Когда клиент хочет отправить поисковый запрос со словом , он формирует поисковый токен . Поисковый токен состоит из трех элементов: . Затем токен отправляется серверу.

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

2.4.3.Добавление файла в коллекцию


Генерация токена для добавления

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



где и – генераторы случайных чисел от ключей и и файла , а содержит информацию об -м уникальном слове в (Номер формулы).





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

После генерации токена клиент шифрует добавляемый файл и отправляет его серверу вместе с .

Добавление файла

Получив токен для добавления, сервер разделяет его на составляющие:



Далее для каждого сервер производит следующие действия:

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





  1. Обновляет ссылку в поисковой таблице на следующий свободный узел:



  1. Находит ссылку на для слова :



  1. Записывает новый элемент в , соответствующий слову и добавляемому файлу :



  1. Обновляет поисковую таблицу:



  1. Обновляет парный узел :





  1. Обновляет парный узел нового записанного элемента:



  1. Если , то обновляет таблицу удаления:



Далее сервер добавляет зашифрованный файл в коллекцию файлов, хранимую на сервере.

2.4.4.Удаление файла из коллекции


Генерация токена для удаления

Для удаления файла из коллекции файлов, хранимой на сервере, пользователь генерирует токен для удаления :



где , и – генераторы случайных чисел на основе удаляемого файла и ключей , и , а – уникальный идентификатор файла .

Удаление файла

Получив токен для удаления, сервер разделяет его на составляющие:



Далее сервер ищет первый элемент списка :



Далее для каждого сервер производит следующие действия:

  1. Расшифровывает элемент :





  1. Удаляет , присваивая случайную строку элементу .

  2. Находит адрес первого свободного узла :



  1. Обновляет поисковую таблицу :



  1. Делает ячейку парного узла свободной:



  1. – узел, предшествующий парному узлу . Сервер обновляет указатель узла на следующий элемент в :









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





  1. Присваивает

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


1   2   3   4   5   6   7   8   9   10


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница