¿Es posible hacer criptografía de curva elíptica $\mathbb{Q}$ en vez de un campo finito?

Question

Cada vez que leo sobre criptografía de curva elíptica (ECC), el escritor trabaja siempre sobre un campo finito. Pero según tengo entendido no hay ninguna razón teórica de grupo para no utilizar $\mathbb{Q}$ como el campo subyacente (aún obtiene un Grupo abeliano, un montón de cosas sobre este grupo se desconoce).

¿Hay alguna razón por qué nadie hace ECC $\mathbb{Q}$? ¿Hay algún ataque conocido que hace que sea inseguro? ¿Es demasiado ineficiente?

Answer 1

Estoy asumiendo que significa estrictamente haciendo todo lo en $\Bbb Q$, incluyendo la transmisión. No es sensato hacer cálculos en $\Bbb Q$ y la reducción de a $\mathbb F_p$ antes de enviar hacia fuera, ya que es más difícil de hacer y no se gana nada. El resumen de la discusión siguiente es que usted no puede utilizar cualquier generado puntos a tener secretos.

---

Puntos de $P$ en una Curva Elíptica $E$ $\Bbb Q$ son de la forma $$P=T+k_1Q_1+k_2Q_2+\cdots+k_rQ_r \quad k_1,\dots,k_r\in\Bbb Z$$ donde $r$ es el rango de $E$ $T$ es un punto de torsión.

Es bien sabido que en la mayoría de los 16 posibles $T$ por Mazur de la Torsión de Teorema.
El valor máximo de $r$ es desconocido: el mejor resultado es 18.
Hay ejemplos conocidos que tiene rango de al menos 28 pero para los que no sabemos exactamente $r$.
Esto significa que a la hora de construir Curvas Elípticas sobre $\Bbb Q$, más o menos es generado por $\leq 18$ de los puntos, por la elección de $k_1,\dots,k_r$. es decir, no hay muchas posibilidades de $Q_i$'s, por lo que necesita $k_i$'s difícil de adivinar.

Ahora el problema es que, dado $P$, por lo general usted puede encontrar $k_1,\dots,k_r$ fácilmente.
Cada vez que agregue algunos de los $Q_i$, los valores en el punto de $(X,Y)$ aumenta de manera significativa.
Por otra parte, el tamaño es estrictamente creciente después de que el pequeño de los valores y el crecimiento es predecible.
Esto significa mirar al $P$, se puede decir que el rango de valores de $k_i$ y va a ser trivial para probar estos valores.

Veamos un ejemplo.

La Curva Elíptica $$E:=Y^2=X^3-27X+90$$ tiene rango 2 generado por $Q_1=(-5,10),Q_2=(-3,12)$.
Tome $P=(-5,10)$ y considerar la posibilidad de $\varphi(P)=\{P,[2]P,[3]P,\dots\}$.
Vamos a conseguir: $$\left\{(-5,10),\left(\dfrac{394}{25}, \dfrac{-7478}{125} \right), \left(\dfrac{148795}{269361},\dfrac{1212735770}{139798359} \right), \left(\dfrac{25189696321}{5592048400},\dfrac{-3233187530793631}{418173379352000}\right),\left(\dfrac{41697179388698395}{10487471993072881}, \dfrac{7244632674771290918438950}{1074004796869053110612279}\right),\dots\right\}$$

Observe que el crecimiento es exponencial. Más precisamente, el valor máximo de numerador y el denominador de $x$-coordenadas es escuadrada cuando se pasa de $P\to 2P$. Así que si, de hecho, un generadas $P$ es de la forma $P=k_1Q_1$, entonces el uso de esta referencia es fácil decir lo $k_1$ es igual. En la práctica hay fórmula para el tamaño.

El mismo método puede ser generalizado para incluir todos los $Q_i$'s, así que si miro un generadas $P$, los tamaños de las coordenadas ya me dirá qué tipo de $k_i$'s son utilizados para generarla. Por lo tanto no se puede utilizar para guardar secretos, ya que son fáciles de averiguar. Esto no sucede en campos finitos ya que los valores se envuelven alrededor y que no se puede saber cuántas veces se produce.

Answer 2

Estás en lo correcto. El cálculo es demasiado ineficiente. El más conocido de ataque en ECDLP, la rho de pollard ataque, sería inútil contra curvas elípticas sobre los racionales.

Considere esto, si usted fuera a hacer los cálculos sobre un campo finito de decir 512-bits, sólo tendrá que lidiar con 512-bit valores intermedios a lo largo del camino. Considerando la misma curva elíptica sobre los racionales y el uso de las mismas operaciones (computing $[k]P$, por ejemplo) nos daría el mismo nivel de seguridad (informática $[k]P$ sobre un campo finito y computación $[k]P$ sobre los racionales, a continuación, la conversión en el campo finito equivalente es el mismo!).

Aunque estoy de acuerdo en que durante los racionales, no son muy deseables cualidades, tales como un infinito abelian grupo, es demasiado pesado para ser implementado.