Plan IBE de gallos

El PKG elige:

1. un módulo RSA público${\displaystyle \textstyle n=pq}$, dónde${\displaystyle \textstyle p,q,\,p\equiv q\equiv 3{\bmod {4}}}$son primordiales y se mantienen en secreto,
2. el mensaje y el espacio cifrado${\displaystyle \textstyle {\mathcal {M}}=\left\{-1,1\right\},{\mathcal {C}}=\mathbb {Z} _{n}}$y
3. una función hash pública segura${\displaystyle \textstyle f:\left\{0,1\right\}^{*}\rightarrow \mathbb {Z} _{n}}$.

Cuando el usuario${\displaystyle \textstyle ID}$Para obtener su clave privada, contacta con el PKG a través de un canal seguro . El PKG

1. deriva${\displaystyle \textstyle a}$con${\displaystyle \textstyle \left({\frac {a}{n}}\right)=1}$mediante un proceso determinista desde${\displaystyle \textstyle ID}$(por ejemplo, aplicación múltiple de${\displaystyle \textstyle f}$),
2. calcula${\displaystyle \textstyle r=a^{(n+5-pq)/8}{\pmod {n}}}$(que cumple con cualquiera de las siguientes${\displaystyle \textstyle r^{2}=a{\pmod {n}}}$o${\displaystyle \textstyle r^{2}=-a{\pmod {n}}}$(véase más abajo) y
3. transmite${\displaystyle \textstyle r}$al usuario.

Para cifrar un bit (codificado como${\displaystyle \textstyle 1}$/${\displaystyle \textstyle -1}$)${\displaystyle \textstyle m\in {\mathcal {M}}}$para${\displaystyle \textstyle ID}$, el usuario

1. elige al azar${\displaystyle \textstyle t_ {1}}$con${\displaystyle \textstyle m=\left({\frac {t_{1}}{n}}\right)}$,
2. elige al azar${\displaystyle \textstyle t_ {2}}$con${\displaystyle \textstyle m=\left({\frac {t_{2}}{n}}\right)}$, diferente de ${\displaystyle \textstyle t_ {1}}$,
3. calcula${\displaystyle \textstyle c_{1}=t_{1}+at_{1}^{-1}{\pmod {n}}}$y ${\displaystyle c_{2}=t_{2}-at_{2}^{-1}{\pmod {n}}}$y
4. envía${\displaystyle \textstyle s=(c_{1},c_{2})}$al usuario.

Para descifrar un texto cifrado${\displaystyle s=(c_{1},c_{2})}$para el usuario${\displaystyle ID}$, él

1. calcula${\displaystyle \alpha =c_{1}+2r}$si${\displaystyle r^{2}=a}$o${\displaystyle \alpha =c_{2}+2r}$de lo contrario, y
2. calcula${\displaystyle m=\left({\frac {\alpha }{n}}\right)}$.

Tenga en cuenta que aquí estamos asumiendo que la entidad que cifra no sabe si${\displaystyle ID}$tiene la raíz cuadrada${\displaystyle r}$de${\displaystyle a}$o${\displaystyle -a}$En este caso, debemos enviar un texto cifrado para ambos casos. Tan pronto como la entidad que realiza el cifrado conozca esta información, solo será necesario enviar un elemento.

En primer lugar, tenga en cuenta que desde${\displaystyle \textstyle p\equiv q\equiv 3{\pmod {4}}}$(es decir${\displaystyle \left({\frac {-1}{p}}\right)=\left({\frac {-1}{q}}\right)=-1}$) y${\displaystyle \textstyle \left({\frac {a}{n}}\right)\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right)}$, cualquiera${\displaystyle \textstyle a}$o${\displaystyle \textstyle -a}$es un residuo cuadrático módulo${\displaystyle \textstyle n}$.

Por lo tanto,${\displaystyle \textstyle r}$es una raíz cuadrada de${\displaystyle \textstyle a}$o${\displaystyle \textstyle -a}$: ^{[ 2 ]}

${\displaystyle {\begin{aligned}r^{2}&\equiv \left(a^{(n+5-pq)/8}\right)^{2}\mod {n}\\&\equiv \left(a^{(p*q+4+1-pq)/8}\right)^{2}\mod {n}\\&\equiv \left(a^{((p-1)(q-1)+4)/8}\right)^{2}\mod {n}\\&\equiv \left(a^{0.5}*a^{((p-1)(q-1))/8}\right)^{2}\mod {n}\\&\equiv a*a^{(p-1)/2}*a^{(q-1)/2}\mod {n}\\&\equiv {\begin{cases}a\mod {n}&|a{\text{ es una función cuadrática residuo}}\mod {n}\\-a\mod {n}&|-a{\text{ es un residuo cuadrático}}\mod {n}\end{cases}}\end{aligned}}}$

Donde el último paso es el resultado de una combinación del criterio de Euler y el teorema chino del resto .

Además, (para el caso de que${\displaystyle \textstyle a}$es un residuo cuadrático, la misma idea se aplica a${\displaystyle \textstyle -a}$):

${\displaystyle {\begin{aligned}\left({\frac {s+2r}{n}}\right)&=\left({\frac {t+at^{-1}+2r}{n}}\right)=\left({\frac {t\left(1+at^{-2}+2rt^{-1}\right)}{n}}\right)\\&=\left({\frac {t\left(1+r^{2}t^{-2}+2rt^{-1}\right)}{n}}\right)=\left({\frac {t\left(1+rt^{-1}\right)^{2}}{n}}\right)\\&=\left({\frac {t}{n}}\right)\left({\frac {1+rt^{-1}}{n}}\right)^{2}=\left({\frac {t}{n}}\right)(\pm 1)^{2}=\left({\frac {t}{n}}\right)\end{aligned}}}$