Упрощенная схема аутентификации с нулевой передачей знаний

Эта схема была предложена в 1986 году У. Фейге, А. Фиатом и А. Шамиром. Она является наиболее известным доказательством идентичности с нулевой передачей конфиденциальной информации.

Изначально, случайным образом задаются два больших простых числа и вычисляется их произведение – модуль Р, который должен иметь размерность 512…1024 бит. Это значение Р передается всем членам корпоративной компьютерной сети. Значения же двух больших простых чисел не передаются никому и хранятся в секрете.

В частном случае, в процессе аутентификации участвуют две стороны:

- пользователь «А», доказывающий свою подлинность;

- пользователь «В», проверяющий представляемое пользователем «А» доказательство.

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

Некоторое число а < Р, где Р – простое число сравнимо с квадратом некоторого числа X по модулю Р, т.е. выполняется сравнение вида

X²=а modP, тогда число а является квадратичным вычетом по модулю Р. Если это условие не соблюдается, то число а является квадратичным невычетом по модулю Р.

В случае, если «а» является квадратичным вычетом по модулю Р, то сравнение X²=а modP имеет два решения + X_i; - X_i, т.е. число «а» по модулю Р имеет два квадратных корня по модулю Р. Множества квадратичных вычетов находятся вычислением квадратов чисел 1, 2, 3, …, по модулю Р. Например, при Р =11 множество квадратичных определится как:

1²=1=1mod11; 2²=4=4mod11; 3²=9=9mod11; 4²=16=16mod11=5mod11;

5²=25=25mod11=3mod11; 6²=36=36mod11=3mod11; 7²=49=49mod11=5mod11;

8²=64=64mod11=9mod11; 9²=81=81mod11=4mod11; 10²=100=100mod11=

=1mod11; 11²=121=121mod11=0mod11.

Числа 1, 3, 4, 5, 9 являются квадратичными вычетами по модулю Р при Р = 11. Число таких вычетов определяется как m = ; для рассмотренного примера при Р = 11 число вычетов будет равно m = ,

m_i → {m₁=1; m₂=3; m₃=4; m₄=5; m₅=9}. В свою очередь не существует никаких значений X_i, которые удовлетворяли бы (для рассматриваемого примера) любому из следующих сравнений: X²=2 mod11; X²=6mod11; X²=7 mod11; X²=8 mod11; X²=10 mod11. Следовательно, числа 2, 6, 7, 8, 10 являются квадратичными невычетами по модулю Р = 11. Число таких невычетов определится как к = , для рассматриваемого примера к = Таким образом, если Р простое число, то число квадратичных вычетов и квадратичных невычетов по заданному модулю Р одинаково.

Для случая, если модуль Р будет определяться как произведение двух простых чисел P = N × L, где N и L простые числа, то число элементов множества квадратичных вычетов по модулю Р определится как:

m =

и это множество характерно тем, что каждый его элемент взаимно простой с Р.

Для примера рассмотрим случай при N=7 и L=5, следовательно множество квадратичных вычетов определится как:

m = = 6.

Производится вычисления элементов множества квадратичных вычетов для Р=35 (N=7 и L=5)

X	X2 mod P
	X2 mod P = 1 mod 35
	X2 mod P = 4 mod 35
	X2 mod P = 9 mod 35
	X2 mod P = 16 mod 35
	X2 mod P = 25 mod 35
	X2 mod P = 36 mod 35 = 1 mod35
	X2 mod P = 49 mod 35 = 14 mod35
	X2 mod P = 64 mod 35 = 29 mod35
	X2 mod P = 81 mod 35 = 11 mod35
	X2 mod P = 100 mod 35 = 30 mod35
	X2 mod P = 121 mod 35 = 16 mod35
	X2 mod P = 144 mod 35 = 4 mod35
	X2 mod P = 169 mod 35 = 29 mod35
	X2 mod P = 196 mod 35 = 21 mod35
	X2 mod P = 225 mod 35 =15 mod35
	X2 mod P = 256 mod 35 = 11 mod35
	X2 mod P = 289 mod 35 = 9 mod35
	X2 mod P = 324 mod 35 = 9 mod35
	X2 mod P = 361 mod 35 = 11 mod35
	X2 mod P = 400 mod 35 = 15 mod35
	X2 mod P = 441 mod 35 = 21 mod35
	X2 mod P = 484 mod 35 =29 mod35
	X2 mod P = 529 mod 35 = 4 mod35
	X2 mod P = 576 mod 35 = 16 mod35
	X2 mod P = 625 mod 35 = 30 mod35
	X2 mod P = 676 mod 35 = 11 mod35
	X2 mod P = 729 mod 35 = 29 mod35
	X2 mod P = 784 mod 35 = 14 mod35
	X2 mod P = 841 mod 35 = 1 mod35
	X2 mod P = 900 mod 35 = 25 mod35
	X2 mod P = 961 mod 35 = 16 mod35
	X2 mod P = 1024 mod 35 = 9 mod35
	X2 mod P = 1089 mod 35 = 4 mod35
	X2 mod P = 1156 mod 35 = 1 mod35
	X2 mod P = 1225 mod 35 = 0 mod35

Анализ полученных квадратичных вычетов по модулю Р = 35 позволяет сформировать идентичные группы, имеющими решения при определенных значениях X_i.

Таблица 1.

N рупппы	Квадратичные вычеты	Имеет решение при Xi =
	X2 = 1 mod 35	X=1; X=6; X=29; X=34
	X2 = 4 mod 35	X=2; X=12; X=23; X=33
	X2 = 9 mod 35	X=3; X=17; X=18; X=32
	X2 = 11 mod 35	X=9; X=16; X=19; X=26
	X2 = 14 mod 35	X=7; X=28
	X2 = 15 mod 35	X=15; X=20
	X2 = 16 mod 35	X=4; X=11; X=24; X=31
Л.18	X2 = 21 mod 35	X=14; X=21
	X2 = 25 mod 35	X=5; X=30
	X2 = 29 mod 35	X=8; X=13; X=22; X=27
	X2 = 30 mod 35	X=10; X=25

Из полученных групп составляется множество квадратичных вычетов взаимнопростых с Р=35, их число определяется как

m = = 6.

Элементы этого множества определятся как: V_i →{1, 4, 9. 11, 16, 29}.

Так как элементы множества V_i взаимнопросты с Р=35, то для их значений существуют обратные значения V_i^-1 mod P.

Обратные значения V_i^-1 mod P определяются из условия, что известна функция Эйлера φ(Р) = =6 × 4 = 24.

V_i^-1 mod P = V_i ^φ(Р)-1 mod P

Для V_i = 1 mod P V_i^-1 mod P = 1²³ mod 35 =1 mod 35

Для V_i = 4 mod P V_i^-1 mod P = 4²³ mod 35 =9 mod 35

Для V_i = 9 mod P V_i^-1 mod P = 9²³ mod 35 =4 mod 35

Для V_i = 11 mod P V_i^-1 mod P = 11²³ mod 35 =16 mod 35

Для V_i = 16 mod P V_i^-1 mod P = 16²³ mod 35 =11 mod 35

Для V_i = 29 mod P V_i^-1 mod P = 29²³ mod 35 =29 mod 35

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

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

Для генерации открытого и секретного ключей для пользователя «А» корпоративный доверенный центр выбирает некоторое число V, которое является квадратичным вычетом по заданному модулю Р. Выбранное значение V будет определено как открытый ключ для пользователя «А». Из представленного множества квадратичных вычетов при Р=35 (Таблица 1) только 6 квадратичных вычетов удовлетворяют условию взаимной простоты с Р=35.

V_i → {1; 4; 9; 11; 16; 29} → {V₁=1; V₂=4; V₃=9; V₄=11; V₅=16; V₆=29}

Для данного подмножества V_i определяются обратные значения его элементов V_i ^-1 mod P.

Так как значение модуля Р определено как произведение двух простых чисел N и L, то функция Эйлера примет значение (P) = (N-1)×(L-1) = = (7-1) ×(5-1) = 24, следовательно:

V_i ^-1 = V_i ^φ(P)-1 mod P = V_i ^24-1 mod 35 = V_i ²³ mod 35

V₁ ^-1 = V₁ ²³ mod 35 = 1²³ mod 35 = 1 mod 35 → 1;

V₂ ^-1 = V₂ ²³ mod 35 = 4²³ mod 35 = 9 mod 35 → 9;

V₃ ^-1 = V₃ ²³ mod 35 = 9²³ mod 35 = 4 mod 35 → 4;

V₄ ^-1 = V₄ ²³ mod 35 = 11²³ mod 35 = 16 mod 35 → 16;

V₅ ^-1 = V₅ ²³ mod 35 = 16²³ mod 35 = 11 mod 35 → 11;

V₆ ^-1 = V₆ ²³ mod 35 = 29²³ mod 35 = 29 mod 35 → 29;

Из полученного подмножества V_i → {1; 4; 9; 11; 16; 29} → {V₁=1; V₂=4; V₃=9; V₄=11; V₅=16; V₆=29} случайным образом выбирается число, которое и будет являться открытым ключом абонента «А». Для примера принимается V₅=16. Для случая V₅=16 вычисляется наименьшее значение квадратного корня S = sgrt V₅^-1 mod P.

Покажем, как производятся вычисления S для подмножества V_i^-1 mod P, приведенного выше V_i → {1; 4; 9; 11; 16; 29} → {V₁=1; V₂=4; V₃=9; V₄=11; V₅=16; V₆=29}.

S_i = sgrt V_i^-1 mod P

1. S₁ = sgrt V₁^-1 mod P = sgrt 1^-1 mod 35 = sgrt 1 mod 35 → 1mod 35 → 1;

2. S₂ = sgrt V₂^-1 mod P = sgrt 4^-1 mod 35 = sgrt 9 mod 35 → 3 mod 35 → 3;

3. S₃ = sgrt V₃^-1 mod P = sgrt 9^-1 mod 35 = sgrt 4 mod 35 → 2 mod 35 → 2;

4. S₄ = sgrt V₄^-1 mod P = sgrt 11^-1 mod 35 = sgrt 16 mod 35 → 4 mod 35 → 4;

5. S₅ = sgrt V₅^-1 mod P = sgrt 16^-1 mod 35 = sgrt 11 mod 35 = sgrt 46 mod 35 =

= sgrt 46 mod 35 = sgrt 81 mod 35 = 9 mod 35 → 9;

6. S₆ = sgrt V₆^-1 mod P = sgrt 29^-1 mod 35 = sgrt 64 mod 35 = 8 mod 35 → 8;

В качестве секретного ключа абонента «А» выбирается одно из значений квадратного корня из представленного подмножества S_i = sgrt V_i^-1 mod P для выбранного ранее случайным образом значения V_i →V₅=16 mod 35 →16, т.е. выбирается S_i → S₅ = 9 mod 35 → 9, которое является наименьшим значением S_i, для которого существует sgrt S mod P. Например, для случая пункт 5 S₅ = 9 mod 35 → 9. Следовательно, секретный ключ для абонента «А» будет равен S₅ = 9 mod 35 → 9.

Таким образом, значение открытого ключа абонента»А» - К_ОА определится как V₅=16, а значение секретного ключа абонента «А» определено как К_ЗА и будет равно S₅ = 9 mod 35 → 9.

На следующем выполняются позиции протокола аутентификации абонента «А» при организации доверительного обмена информацией в режиме удаленного теледоступа с абонентом «В». Для чего:

1. Абонент «А» выбирает некоторое случайное число r < P и производит вычисление числа x = r² mod P. Допустим абонент «А» выбирает значение r = 12. В этом случае значение числа x = r² mod P при r = 12 и P = 35 определится как: x = r² mod P = 12² mod 35 = 144 mod 35 = 4 mod 35 → 4.

Абонент «А» отправляет значение x = 4 абоненту «В».

2. Абонент «В», в свою очередь, отправляет абоненту «А» случайный бит «b» равный «1» или «0» (b = 1 ˅ 0).

3. Получив от абонента «В» значение b = 0, абонент «А» отправляет значение r = 12 абоненту «В». Если абонент «А» получил от абонента «В» значение b = 1, тогда абонент «А» вычисляет значение y = r × S mod P. Для рассматриваемого примера y = r × S mod P = 12 × 9 mod 35 = 108 mod 35 =

= 3 mod 35 → 3. После указанных вычислений абонент «А» отправляет абоненту «В» значение y = 3.

4. Если абонентом «В» принято значение b = 0, то абонент «В» проверяет равенство x = r² mod P, чтобы убедиться, что сторона «А» знает значение sgrt x mod P: x = 144 mod 35 = 4, т.е. 4 = 4, так как принятое значение

х = 4 абонентом «В» от абонента «А» равно вычисленному абонентом «В» значению r² mod P = 12² mod 35 = 144 mod 35 = 4 mod 35 по принятому значению r = 12.

Если абонентом «В» принято от абонента «А» значение бита b = 1, то абонент «В» проверяет условие, что x = y² × V mod P (для рассматриваемого примера y² × V mod P = 3² × V₅ mod 35 = 9 × 16 mod 35 = 144 mod 35 =

= 4 mod 35 → 4). Следовательно, принятое от абонента «А» значение х = 4 совпадает с вычисленным абонентом «В» значением y² × V₅ mod P =4 mod35 → 4, т.е 4=4. Проведенные абонентом «В» вычисления убеждает его в том, что абонент «А» знает значение sgrt V^-1 mod P, т.е. знает, что абонент «А» владеет секретным ключом S = sgrt V^-1 mod P.

В рассматриваемом примере y = r × S mod P = 12 × 9 mod 35 = 108 mod 35 = 3 mod 35 → 3, а значение секретного ключа абонента «А» равно

S₅ = sgrt V₅^-1 mod P = sgrt 16^-1 mod 35 = sgrt 11 mod 35 = sgrt 46 mod 35 =

= sgrt 46 mod 35 = sgrt 81 mod 35 = 9 mod 35 → 9;

Указанная последовательность расчетов образует один цикл протокола признания доверительности абонента связи, называемый аккредитацией. Для повышения достоверности процесса аутентификации абоненты «А» и «В» повторяют этот цикл t раз при различных случайных значениях r и b.