WikiDer > Схема петухов МБП

Схема петухов МБП является шифрование на основе личности система, предложенная Клиффорд Кокс в 2001.^[1] Безопасность схемы основана на жесткости квадратичная проблема остаточности.

Протокол

Настроить

PKG выбирает:

1. публичный RSA-модуль ${displaystyle extstyle n = pq}$, где ${displaystyle extstyle p, q ,, pequiv qequiv 3 {mod {4}}}$ главные и держатся в секрете,
2. сообщение и зашифрованное пространство ${displaystyle extstyle {mathcal {M}} = left {-1,1ight}, {mathcal {C}} = mathbb {Z} _ {n}}$ и
3. безопасная публичная хеш-функция ${displaystyle extstyle f: left {0,1ight} ^ {*} ightarrow mathbb {Z} _ {n}}$.

Извлечь

Когда пользователь ${displaystyle extstyle ID}$ хочет получить свой закрытый ключ, он связывается с PKG через безопасный канал. PKG

1. происходит ${displaystyle extstyle a}$ с участием ${displaystyle extstyle left ({frac {a} {n}} ight) = 1}$ детерминированным процессом из ${displaystyle extstyle ID}$ (например, многократное применение ${displaystyle extstyle f}$),
2. вычисляет ${displaystyle extstyle r = a ^ {(n + 5-p-q) / 8} {pmod {n}}}$ (который выполняет либо ${displaystyle extstyle r ^ {2} = a {pmod {n}}}$ или ${displaystyle extstyle r ^ {2} = - а {pmod {n}}}$см. ниже) и
3. передает ${displaystyle extstyle r}$ пользователю.

Зашифровать

Чтобы зашифровать бит (кодируется как ${displaystyle extstyle 1}$/${displaystyle extstyle -1}$) ${displaystyle extstyle min {mathcal {M}}}$ для ${displaystyle extstyle ID}$, Пользователь

1. выбирает случайный ${displaystyle extstyle t_ {1}}$ с участием ${displaystyle extstyle m = left ({frac {t_ {1}} {n}} ight)}$,
2. выбирает случайный ${displaystyle extstyle t_ {2}}$ с участием ${displaystyle extstyle m = left ({frac {t_ {2}} {n}} ight)}$, отличный от ${displaystyle extstyle t_ {1}}$,
3. вычисляет ${displaystyle extstyle c_ {1} = t_ {1} + at_ {1} ^ {- 1} {pmod {n}}}$ и ${displaystyle c_ {2} = t_ {2} -at_ {2} ^ {- 1} {pmod {n}}}$ и
4. отправляет ${displaystyle extstyle s = (c_ {1}, c_ {2})}$ пользователю.

Расшифровать

Расшифровать зашифрованный текст ${displaystyle s = (c_ {1}, c_ {2})}$ для пользователя ${displaystyle ID}$, он

1. вычисляет ${displaystyle alpha = c_ {1} + 2r}$ если ${displaystyle r ^ {2} = a}$ или ${displaystyle alpha = c_ {2} + 2r}$ в противном случае и
2. вычисляет ${displaystyle m = left ({frac {alpha} {n}} ight)}$.

Обратите внимание, что здесь мы предполагаем, что объект шифрования не знает, ${displaystyle ID}$ имеет квадратный корень ${displaystyle r}$ из ${displaystyle a}$ или ${displaystyle -a}$. В этом случае мы должны отправить зашифрованный текст для обоих случаев. Как только эта информация известна шифровальному объекту, необходимо отправить только один элемент.

Правильность

Сначала обратите внимание, что, поскольку ${displaystyle extstyle pequiv qequiv 3 {pmod {4}}}$ (т.е. ${displaystyle left ({frac {-1} {p}} ight) = left ({frac {-1} {q}} ight) = - 1}$) и ${displaystyle extstyle left ({frac {a} {n}} ight) Стрелка вправо влево ({frac {a} {p}} ight) = left ({frac {a} {q}} ight)}$, либо ${displaystyle extstyle a}$ или ${displaystyle extstyle -a}$ это квадратичный вычет по модулю ${displaystyle extstyle n}$.

Следовательно, ${displaystyle extstyle r}$ квадратный корень из ${displaystyle extstyle a}$ или ${displaystyle extstyle -a}$:

${displaystyle {начало {выровнено} r ^ {2} & = left (a ^ {(n + 5-pq) / 8} ight) ^ {2} & = left (a ^ {(n + 5-pq- Phi (n)) / 8} ight) ^ {2} & = left (a ^ {(n + 5-pq- (p-1) (q-1)) / 8} ight) ^ {2} & = left (a ^ {(n + 5-pq-n + p + q-1) / 8} ight) ^ {2} & = left (a ^ {4/8} ight) ^ {2} & = pm aend {выровнено}}}$

Более того, (для случая, когда ${displaystyle extstyle a}$ квадратичный вычет, та же идея верна для ${displaystyle extstyle -a}$):

${displaystyle {egin {align} left ({frac {s + 2r} {n}} ight) & = left ({frac {t + at ^ {- 1} + 2r} {n}} ight) = left ({ frac {tleft (1 + at ^ {- 2} + 2rt ^ {- 1} ight)} {n}} ight) & = left ({frac {tleft (1 + r ^ {2} t ^ {- 2 } + 2rt ^ {- 1} ight)} {n}} ight) = left ({frac {tleft (1 + rt ^ {- 1} ight) ^ {2}} {n}} ight) & = left ({frac {t} {n}} ight) left ({frac {1 + rt ^ {- 1}} {n}} ight) ^ {2} = left ({frac {t} {n}} ight) (pm 1) ^ {2} = left ({frac {t} {n}} ight) конец {выровнено}}}$

Безопасность

Можно показать, что нарушение схемы равносильно решению проблемы квадратичной остаточности, которая считается очень сложной. Общие правила выбора Модуль RSA удерживать: используйте безопасный ${displaystyle extstyle n}$, сделайте выбор ${displaystyle extstyle t}$ единообразные и случайные, и, кроме того, включают некоторые проверки подлинности для ${displaystyle extstyle t}$ (в противном случае адаптивная атака по выбранному зашифрованному тексту может быть установлен путем изменения пакетов, которые передают один бит, и использования оракул чтобы наблюдать влияние на расшифрованный бит).

Проблемы

Основным недостатком этой схемы является то, что она может шифровать сообщения только бит на бит, поэтому она подходит только для небольших пакетов данных, таких как сеансовый ключ. Для иллюстрации рассмотрим 128-битный ключ, который передается с использованием 1024-битного модуля. Затем нужно отправить 2 × 128 × 1024 бит = 32 КБ (когда неизвестно, ${displaystyle r}$ это квадрат а или -а), что допустимо только для сред, в которых ключи сеанса меняются нечасто.

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

использованная литература