Общее описание алгоритма «Квадратного корня»
Интуитивно, чтобы полностью скрыть виртуальную модель доступа, мы должны скрыть следующее:
к каким виртуальным ячейкам осуществляется доступ и в каком порядке?
сколько раз к конкретной виртуальной ячейке осуществляется доступ (в случае, если к ней обращались)?
В первом случае достаточно каким-либо образом «перемешать» память так, чтобы противник не знал, какой фактический адрес памяти соответствует данному виртуальному адресу. Во втором случае, мы должны убедиться, что к любой («перемешанной») локальной памяти осуществляется доступ более одного раза. Высокоуровневые шаги моделирования следующие.
Алгоритм КК
1. Инициализация:
Первые m+
RAM-машины расположены так, чтобы содержать m виртуальных адресов (к которым оригинальная RAM-машина обращается в процессе выполнения) и
2. Моделирование шагов RAM-машины: До тех пор пока моделирование RAM-машины не остановится, выполнить. (Моделирование выполняется за периоды, каждый из которых состоит из
2.1. Случайно переставить содержимое ячеек от 1 до m+
над целыми числами от 1 до m+
2.2. Моделировать
Доступ к памяти оригинальной RAM-машины, скажем доступ к виртуальному слову i, моделируется следующим образом:
- сканируется вся память зщт и проверяется, находится ли содержимое виртуального слова i в одном из слов памяти зщт. Подчеркнем, что здесь мы обращаемся к каждой ячейке памяти зщт в предопределенном порядке независимо от того, находится ли там виртуальное слово, которое нам надо;
- в случае, если i-тое виртуальное слово не найдено в памяти зщт, мы восстанавливаем его из фактического слова p(i), которое является текущей ячейкой i-того виртуального слова в течение этого периода;
- в противном случае (т.е., в случае, если i-тое виртуальное слово найдено в памяти зщт), мы получаем доступ к следующему «фиктивному слову» в перемешанной памяти (например, мы обращаемся к фактическому адресу p(m+j), где j
- число шагов, моделируемых в текущем периоде);
- в любом случае модифицируемое значение для i-той виртуальной ячейки записано (забывающим образом) в память зщт
посредством сканирования заново всех слов памяти зщт.
3. Модифицировать перемешанную память. В конце периода, используются значения, сохраненные в памяти зщт
для модификации забывающим образом содержимого перемешанной памяти.
Перед тем как приступить к деталям реализации вышеупомянутых шагов, сделаем несколько замечаний относительно того, почему они составляют забывающее моделирование. Далее покажем, как осуществить доступ к памяти на шаге 1 фиксированным образом а, следовательно, независимо от входа и виртуальной модели доступа оригинальной
RAM-машины. Различают два типа операций доступ к памяти, выполненных на шаге 2: полное сканирование памяти зщт (т.е., осуществление доступа к каждому из слов дважды на каждую виртуальную операцию доступа) и
 |
осуществление доступа к
