MXPA04010155A - Uso de isogenias para el diseno de criptosistemas. - Google Patents

Abstract

Se describen tecnicas para proporcionar sistemas de codificacion de clave publica. Mas particularmente, isogenias de variedades Abelian (por ejemplo, curvas elipticas en casos unidimensionales) se utilizan para proporcionar sistemas de codificacion de clave publica. Por ejemplo, las isogenias permiten el uso de curvas multiples en lugar de una curva individual para proporcionar una codificacion mas segura. Las tecnicas pueden ser aplicadas a firmas digitales y/o soluciones de codificacion basadas en identidad (IBE). Ademas, las isogenias pueden ser utilizadas en otras aplicaciones tales como firmas ciegas, sistemas jerarquicos y similares. Adicionalmente, se describen soluciones para la generacion de isogenias.

Description

USO DE ISOGENIAS PARA EL DISEÑO DE CR1PTOSISTEMAS SOLICITUD RELACIONADA La presente invención reclama prioridad de la solicitud de patente provisional de los Estados Unidos número 60/517,142, presentada el 3 de noviembre del 2003 intitulada "Uso de Isogenias para el Diseño de Criptosistemas," la descripción de la cual se incorpora aquí por referencia.

CAMPO TECNICO La presente invención se refiere en general a criptología, y más particularmente, a la utilización de isogenias para el diseño de criptosistemas.

ANTECEDENTES Ya que la comunicación digital se vuelve más un lugar común, la necesidad de asegurar los canales de comunicación asociados se convierte cada vez más importante. Por ejemplo, las tecnologías actuales permiten a un usuario a remotamente acceder las cuentas de banco, datos médicos, y otra información sensible y privada. La criptología ha sido ampliamente utilizada para proporcionar una comunicación digital segura. La criptología generalmente se refiere a cifrado (o codificación) y descifrado (descodificación) de mensajes. La codificación y descodificación utiliza alguna información secreta (tal como una clave). En diferentes métodos de codificación, una clave individual o múltiples claves pueden ser utilizadas para la codificación y descodificación. Un criptosistema de clave múltiple comúnmente utilizado es un sistema de codificación de clave pública. En un sistema de clave pública, un remitente que desea enviar un mensaje codificado a un receptor obtiene una clave pública autentificada para el receptor que es generada utilizando una clave privada. Como el nombre lo implica, la clave pública puede estar disponible de fuentes públicas. Además, para evitar un ataque de personificación, la clave pública por lo general es autentificada. La autentificación de ia clave pública puede ser hecha a través de una técnica tal como intercambiar claves a través de un canal confiable, utilizando un archivo público confiable, utilizando un servidor confiable en línea, o utilizando un servidor fuera de línea y certificados. Después de obtener la clave pública autentificada, el remitente codifica un mensaje original con la clave pública y genera un texto cifrado. El receptor pretendido entonces utiliza la clave privada para descodificar el texto cifrado para extraer el mensaje original. La descodificación del texto cifrado sin acceso a la clave privada se cree que es no factible. Por consiguiente, solamente una parte tiene que acceso a la clave privada puede exitosamente descodificar el texto cifrado.

Una ventaja importante de los sistemas de clave pública sobre los criptosistemas (tal como cifras de corriente o bloque) es que en comunicaciones de dos partes, solamente la clave privada necesita ser mantenida en secreto (mientras en los criptosistemas simétricos, la clave se mantiene secreta en ambos extremos). Un sistema de codificación de clave pública actual utiliza ciertas curvas elípticas (ECs) sobre un campo finito. Un par de valores publicados derivados de una curva elíptica se utilizan como una clave pública (incluyendo puntos en la curva y su clave pública correspondiente la cual es generada por una multiplicación simple (es decir, multiplicación entera) en la curva). La verificación se hace utilizando aparejamiento bilineal sobre la curva. Generalmente, las curvas elípticas se cree que proveen sistemas de codificación con relativamente requerimientos de comunicación más bajos que los sistemas tradicionales tales como RSA (tecnología de codificación de clave pública Rivest, Shamir y Adleman), mientras se mantienen niveles de seguridad similares. Un aspecto con los sistemas de codificación de clave pública actuales es que ninguno ha probado se seguro. Como un resultado, la seguridad de los sistemas de codificación de clave pública actuales se presume que se basan en la dificultad de un grupo de problemas número-teóricos. Por consiguiente, los sistemas de codificación de clave pública se desea que provean seguridad adicional.

COMPENDIO DE LA INVENCION Se describen técnicas para proporcionar sistemas de codificación de clave pública. Más particularmente, isogenias de variedades Abelian (por ejemplo, curvas elípticas en casos unidimensionales) se utilizan para proporcionar sistemas de codificación de clave pública. Por ejemplo, las isogenias permiten el uso de múltiples curvas en lugar de una curva individual para proporcionar una codificación más segura. Las técnicas pueden ser aplicadas a firmas digitales y/o soluciones de codificación en base a identidad (IBE). Además, las isogenias pueden ser utilizados en otras aplicaciones tales como firmas ciegas, sistemas jerárquicos, y similares. Adicionalmente, las soluciones se describen para generar las isogenias. En una ¡mplementación descrita, un método incluye la publicación de una clave pública que corresponde a una isogenia. El método además incluye la descodificación de un mensaje codificado utilizando una clave de descodificación la cual corresponde a la isogenia (por ejemplo, es una isogenia doble).

BREVE DESCRIPCION DE LOS DIBUJOS La descripción detallada se describe con referencia a las figuras que la acompañan. En las figuras, el dígito(s) más a la izquierda de un número de referencia identifica la figura en la cual la el número de referencia aparece primero. El uso de los mismos números de referencia en diferentes figuras indica características similares o idénticas. La Figura 1 ilustra un método ilustrativo para utilizar isogenias en un criptosistema. La Figura 2 ilustra un mapa ilustrativo de una isogenia entre dos curvas. La Figura 3 ilustra un método ilustrativo para señalizar un mensaje utilizando isogenias. La Figura 4 ilustra un mapa ilustrativo de una isogenia entre múltiples curvas. La Figura 5 ilustra un método ilustrativo para la identidad basada en codificación utilizando isogenias. La Figura 6 ilustra un ambiente de computadora general 600, el cual puede ser utilizado para implementar las técnicas descritas en la presente.

DESCRIPCION DETALLADA La siguiente discusión asume que el lector está familiarizado con técnicas de criptografía. Para una introducción básica de criptografía, el lector es dirigido a un texto escrito por A. Menezes, P. van Oorschot, y S. Vanstone intitulado, "Handbook of Applied Criptography," quinta edición (Agosto 2001 ), publicado por CRC Press.

La siguiente descripción describe técnicas para mejorar sistemas de clave pública que están basados en curvas elípticas múltiples (o variedades Abelian en general). Las varias técnicas se describen para la generación de isogenias (o mapeos) entre las curvas. Las isogenias generados permiten el uso de curvas múltiples en lugar de una curva individual para proporcionar codificación pública. Además, la técnicas pueden ser aplicadas a firmas digitales relativamente cortas (por ejemplo, mecanografiadas por un usuario o enviadas a través de un canai de ancho de banda bajo) y/o soluciones de codificación basada en la identidad (IBE) (por ejemplo, permitiendo claves públicas memorizables). Las firmas cortas también pueden proveer una eficiencia adicional a través de verificación agregada.

VISION GENERAL DE CRIPTOSISTEMAS CON ISOGENIAS La Figura 1 ilustra un método ilustrativo 100 para utilizar isogenias en un criptosistema. Una etapa 102 genera isogenias (o curvas elípticas, o más generalmente variedades Abelian). Las isogenias pueden ser generadas mediante una parte que recibe u otra parte (tal como una parte confiable discutida adicionalmente con referencia a la Figura 5). La etapa 102 también puede generar la isogenia doble correspondiente para cada uno de las isogenias generados (como se discutirá adicionalmente más adelante). Varios métodos para generar isogenias se detallan más adelante bajo el mismo título. Adicionalmente, como se detallará más adelante con referencia a las Figuras 3 y 5, las isogenias generadas son utilizadas para proporcionar claves públicas y las claves públicas se publican (104). Las claves públicas pueden ser publicadas por la parte remitente o una autoridad confiable (ver, por ejemplo, discusión de Figuras 3 y 5). Una parte remitente entonces codifica (o firma) los mensajes utilizando una clave de codificación (106). Los mensajes codificados de la etapa 106 pueden ser verificados/descodificados por la parte receptora utilizando una clave de descodificación para determinar la autenticidad de la codificación o señalización (108). En una implementación , se utiliza el aparejamiento Weil para verificar los mensajes codificados (tal como se discute más adelante bajo el mismo título). Sin embargo, el aparejamiento Weil es solamente un ejemplo de aparejamiento que puede ser utilizado para la verificación o descodificación. Por ejemplo, otras técnicas de aparejamiento büineales y/o no degeneradas pueden ser utilizadas tal como el aparejamiento Tate y aparejamiento de cuadro.

VISION GLOBAL DE ISOGENIAS La Figura 2 ilustra un mapa ilustrativo de una isogenia 200 entre dos curvas (por ejemplo, curvas elípticas). Como se ilustró, una curva ?·,, puede ser trazada en un mapa en una curva E2, a través de una isogenia ø (en donde 0:E1 ? E2). La Figura 1 también ilustra la isogenia doble ™ (en donde E2 ? E,). En varias implementaciones, el uso de isogenias en criptosistemas es visualizado para proporcionar propiedades tales como: dada una curva E generar un par (ø, E2) es relativamente eficiente, en donde 0:E1? E2 es una isogenia, pero dado un par (E E2) de curvas isogenias, se cree que es relativamente duro construir cualquier isogenia no de cero E2, mucho menos una isogenia específica. Por lo tanto, si una distinción entre lo dibujado entre una ruptura global (definida como una computación que permite cualquier mensaje subsiguiente que sea interrumpido en un tiempo de polinomio) y una interrupción por instancia, entonces el mejor conocido ataca en este momento contra los criptosistemas basados en isogenias toma ya sea substancialmente más tiempo que el registro discreta para una interrupción global o de otra manera una computación del registro discreto por mensaje para el ataque por instancia "ingenuo". Por ejemplo, considerando un sistema de fichas en donde al cliente se le está dando un mensaje firmado específico que otorga acceso a algún servicio (el cual puede ser un valor bajo), el cliente puede tener que leer la ficha a través del teléfono a un representante, y de esta manera las firmas pueden ser relativamente cortas. Será razonable utilizar parámetros que son suficientemente amplios para hacer un ataque por mensaje más costoso que el servicio provisto, mientras se mantiene una interrupción global prohibitivamente costosa.

DETALLES DE ISOGENIAS Un campo k puede ser establecido con características p con q elementos teniendo un cierre algebraico k. Dejar que Elk sea una curva elíptica definida sobre un campo k y E(k) ser un grupo definido sobre k, y dejar que d(E) denote el campo de función de la curva elíptica. También dejar que ¡JTJ_E O [n] denote el mapa P? n P en E y E[n] denote el kernel (módulo central de sistema operativo) de este mapa. Una isogenia ø:£¦,? E2 es un morfismo no constante que envía el elemento de identidad de E1 a aquel de E2. Cuando dicha isogenia existe, se puede decir que E-i y E2 son isogenios. La isogenia se define sobre k si ø tienen ecuaciones definidas con coeficientes en k. Cualquier isogenia se convierte en el homomorfismo de grupo, es decir, 0(P+Q) = 0(P) + 0(Q) para todos las P, QeE en donde la adición en el lado de la mano izquierda es la regla del grupo £, y la adición en el lado de la mano derecha es aquel de E2. Por lo tanto el kernel de ø es un subgrupo de E-,. Dejar que Homk(E 1 E2) denote el grupo de isogenias de E-¡ a E2 que están definidas sobre k. Homk(E1tE2) está denotado por Hom(E1t E2). Para cualquier isogenia 0:E?? E2, existe una isogenia doble E-, tal como: en donde n=deg(0) es el grado de isogenia. La isogenia doble satisface las propiedades estándares: f =f,f + ? =f + ?,f°? = ?°f, [«] = [«].

En una implementación , el grado de ø como un mapa finito puede además definirse como: el grado de la extensión de k(E-,) sobre el obstáculo (por ø) del campo k(E2) en donde ø se define sobre k. Puede ser conveniente pensar en términos del tamaño de su kernel (asumiendo que la extensión del campo de función es separable) o a través de la ecuación anterior. Por lo tanto, se dice que la isogenia es B-lisa si su grado es B-lisa (es decir, los divisores principales de deg(0) son menores que o iguales a B). El grupo Hom(E,E) de endomorf ismos de una curva elíptica E es denotada por Fin(E); este grupo tiene la estructura de un anillo dado a través de la definición : (0+?)(?) = 0(?) + ?(?),(0??)(?) = 0(?(?)).

Generalmente, el grupo Hom(E1,E2) es una torsión libre extremo izquierdo End(E2)- módulo y extremo derecho End(Ei)-módulo. Cuando E1 - E2 = E, la estructura algebraica es más rica: ??????t,?S) - End(E) es un anillo (no solamente un módulo) con divisores no de cero y tiene característica cero. En una implementación, esto se puede pensar como una cuadrícula: Dejar que £ sea una curva elíptica definida sobre algún campo k. Entonces, End(E) es isomórfica a cualquier Z, un orden e un campo imaginario cuadrático, o un orden máximo en álgebra en serie. Para cada dos curvas elípticas E1tE2, el grupo Hom(E E2) es un módulo Z libre de rango máximo 4. Cuando End(E) es mayor que Z, se dice que aquella E tiene multiplicación compleja. El elemento en End(E) correspondiente al endomorfismo Frobenius (x,y)? (xp,y ) está denotado por n, y éste satisface la ecuación característica x2 -tr(E)x+q =0. El conductor de la curva elíptica c es [End(E):Z[ ]].

APAREJAMIENTO WEIL El aparejamiento Weil en: E[n]xE[n]? µ? es un mapa bilineal, no degenerado con valores en el grupo de nav0 raíces de la unidad en k. En una implementación, el aparejamiento Weil se utiliza para realizar la etapa de verificación/descodificación 108 de la Figura 1. Sin embargo, el aparejamiento Weil es solamente un ejemplo de aparejamiento que puede ser utilizado para la verificación o descodificación. Por ejemplo, otras técnicas aparejamiento bilineales y/o no degeneradas pueden ser utilizadas tales como el aparejamiento Tate y aparejamiento de cuadro. El aparejamiento Weil satisface la siguiente propiedad: e E2[n] Aquí, ^OS^CO) es una computación de aparejamiento en , mientras en(0(S),T) es sobre E2. Observar que ambas curvas tienen puntos de torsión n, los cuales ponen un límite sobre sus órdenes de grupo. Esto no presenta un problema, ya que a través de teorema de Tate, E-i(k) y E2(k) son isogenias sobre k si y solamente si los dos grupos de puntos tienen el mismo orden. El aparejamiento Weil evalúa la identidad de todos los pares de capturas las cuales son linealmente dependientes. Consecuentemente, un mecanismo podría ser benéfico para asegurar que los puntos de entrada no son escalones múltiples uno del otro. Un método es utilizar una curva E2 definida sobre un campo finito k el cual es suficientemente grande para el grupo completo E2[n]=(Z/nZ)2 de puntos de torsión n se define sobre k. En esta situación, la probabilidad de que dos elementos aleatorios del grupo E2[n] sean üneaimente dependientes es insignificante, en el orden de 1/A?, por lo que el valor del aparejamiento Weil puede ser no trivial con alta probabilidad. La ecuación anterior asegura que la distribución de los valores de aparejamiento en E1 coincidirá con aquellos de E2. Alternativamente, una función de aparejamiento modificada e(P,Q) = en(Á(P),Q) puede ser utilizada en donde ? es cualquier endomorfismo no escalable, por lo que P y ?(?) son linealmente independientes y e(P,P)?i. Dicho mapa ? es llamado una distorsión o torsión de E. o GENERACION DE ISOGENIAS En varias implementaciones, un número de métodos pueden ser utilizados para construir isogenias de alto grado (por ejemplo, curvas elípticas, o más generalmente variedades Albelian) y sus dobles tales como se discutió con referencia a la etapa 102 de la Figura 1. La firma digital corta y los criptosistemas IBE discutidos en la presente pueden seguir la convención que coloca en pares los valores (P,0(P)) que son publicados como la clave pública, mientras que la evaluación de la F doble constituye la clave privada. En una implementación, las construcciones pueden ser resumidas como: dado cualquier E, existe un algoritmo para la construcciones de las isogenias E? E cuyo grado n es aleatoriamente distribuido, y es un primo con probabilidad ~1/log(n); dando una curva E-, a objetivos aleatorios en el tiempo 0(B3); y dando E1:E2 y dos isogenias linealmente independientes en Homk(E1,E2) que tienen relativamente un grado primo, existe un algoritmo para construir isogenias del grado primo (ver, por ejemplo, la discusión a continuación con respecto a las isogenias independientes).

ISOGENIAS DE MULTIPLICACION COMPLEJA Dejar que E^-E2 como antes y asumir que E1 tiene una multiplicación compleja (CM) a través del orden cuadrático imaginario 0P de D<0 discriminante. Un algoritmo probabil ística puede ser descrito para producir dicha curva E junto con un endomorfismo ø de E-¡ de grado primo grande, en un polinomio de tiempo esperado en |D|. 1. Calcular el polinomio de clase Hilbert HD(X) de D discriminante. Dejar que K denote el campo de división de HD(X) sobre Q. 2. Seleccionar cualquier raíz x de HD(X) y construir una curva elíptica E sobre C teniendo una invariante j igual a x. Observar que £ se define sobre el campo de número K. 3. A través de la construcción, la curva E tiene una multiplicación compleja a través de . Al utilizar álgebra lineal en las expansiones q, encontrar explícitamente la función racional l(X,Y) con coeficientes en K correspondientes a la isogenia € EndE . 4. Seleccionar enteros aleatorios a y b hasta que a2 - b2D sean primos. Entonces, la isogenia a + b-Jü . ser¿ un endomorfismo de E que tienen un grado primo. 5. Seleccionar cualquier primo ideal P de K y reducir los coeficientes de E y de I del módulo P. Dejar que E1 denote la reducción de E y dejar que ø sea la reducción de ct + b^ÍD . Las etapas 1-3 del algoritmo son tiempo determinista y de polinomio en \D\. Como para la etapa 4, el teorema del número primo para los campos de número implica que a2 - bzD tiene la probabilidad 1/log(a2 - b2D) del ser primo, por lo que para los enteros a y b de tamaño n se puede esperar que la etapa 4 termine después de los ensayos de \og(Dn2l). El endomorfismo resultante ø es un endomorf ismo Ei de grado primo. Ambos, ø y su ^-a-bsÍD pueden ser evaluados teniendo el conocimiento de a y b, utilizando solamente ia función racional l(X,Y) junto con la multiplicación y adición escalable. Dicha isogenia ø puede ser llamada una isogenia CM.

ISOGENIAS MODULARES Para cualquier primo {, la curva modular X0{t) parametriza clases de isomorfismo de isogenias Et? E2 de grado L Más específicamente, existe una ecuación de polinomio F,(?,?) para X0(f) con la propiedad de que E1 y E2 son isogenias f si y solamente si Al utilizar el polinomio F?(?,?), se puede calcular para cualquier £, un curva isogenia t- E2 junto con una ecuación de polinomio explícita para el grado de isogenia t E-¡? E2. Debido a que el polinomio modular es simétrico en X y en Y el cálculo con las invariantes j inversas puede ser utilizado para encontrar la isogenia doble. En la práctica, no se pueden utilizar los polinomios F?(?,?) para cálculos actuales debido a que los coeficientes de estos polinomios son en su lugar más grandes. En su lugar, se pueden utilizar modelos de polinomios equivalentes para X0(t) teniendo coeficientes más pequeños. Con respecto al modelo preciso utilizado para los cálculos, una ¡sogenia derivada en esta forma puede ser referida como una ¡sogenia modular. Los algoritmos actualmente conocidos para el cálculo de isogenias modulares son generalmente factibles para valores pequeños de /. Por sí mismo, el uso de isogenias modulares de grado pequeño no agregar mucha seguridad, debido a que un atacantes que conoce las curvas E1 y E2 podría verificar cada / si las curvas son isogenias / y recuperar la isogenia / en el cado de que si sean. Sin embargo, se pueden componer muchas isogenias modulares (por ejemplo, para diferentes selecciones de /) en una isogenia ø de grado suave alto y utilizar ø como una isogenia sin revelar las curvas intermedias. Un atacante que tiene la habilidad de evaluar ø sobre puntos arbitrarios puede aún deducir las / primas calculando todos los puntos de torsión / de £? y viendo si cualquiera de ellos es aniquilado por ø. Sin embargo, bajo la suposición de que el problema del cálculo de la isogenia doble es difícil, el atacante no será capaz de evaluar ø en los puntos de su selección. Como una buena medida, también se puede componer la isogenia resultante ya sea con isogenias escalables o con isogenias CM con el fin de introducir factores no suaves grandes en el grado de una implementacion.

ISOGENIAS LINEAL ENTE INDEPENDIENTES En una implementacion, las isogenias linealmente independientes ø y ? son dadas de E-, a E2 relativamente de grado primo. Como un resultado, la combinación lineal ae+by/ tienen un grado dado por la forma cuadrática a2f + ad(f? + ? ) + ^?? ef| |gs dQS variables a y b. Observar que los coeficientes de esta forma cuadrática son enteros, ya que los coeficientes externos son los grados de ø y ? y el término de en medio es igual a deg(0 + p) -deg(ty). Ya que la forma cuadrática es primitiva, retiene los valores primos indefinidamente por lo general como a y b que varían sobre todos los pares (a,b) eZ2. En esta forma, muchas isogenias Ei? E2 de grado no liso grande (o aún primo) puede ser obtenida. La probabilidad de que el grado resultante sea no suave también puede ser estimada.

ESQUEMAS DE FIRMA CORTA UTILIZANDO ISOGENIAS En una ¡mplementación, las técnicas discutidas en la presente puede ser aplicadas a esquemas de firmas relativamente cortos (por ejemplo, mecanografiadas por el usuario o enviadas a través de un canal de ancho de banda bajo). Dos esquemas de firmas serán discutidos a continuación los cuales están parcialmente basados en propiedades matemáticas de isogenias y aparejamientos sobre curvas elípticas.

FIRMAS VARIANTES GALOIS Dejar que Fq"/Fq sea una extensión de los campos finitos del grado n. Tomar una curva elíptica E-, definida sobre Fq junto con una isogenia 0.??? ?2 definida sobre Fqn, en donde E2 es una curva elíptica definida sobre Fqn. En una implementación, la curva E2 está definida sobre L en lugar de sobre un subcampo de L, pero es imposible tomar £2 definida sobre L en lugar de sobre un subcampo. Sin embargo, por razones de seguridad, la isogenia ø puede no estar definida sobre cualquier subcampo apropiado de Fqn. Además, la isogenia ø puede ser generada de acuerdo con varias técnicas, tales como aquellas discutidas anteriormente. La Figura 3 ilustra un método ilustrativo 300 para firmar un mensaje utilizando isogenias. El método 300 incluye las siguientes etapas: Clave Pública. Seleccionar de manera aleatoria PeEi(Fq) y publicar (P,Q) (302), en donde Q = 0(P). Observar que P se define sobre Fq pero Q no está definida sobre Fq, debido a que ø tampoco está.

Clave Secreta. La isogenia doble F de F . Firma. Dejar que H sea un oráculo aleatorio (público) del espacio del mensaje al grupo de puntos de torsión k sobre E2. Dado mensaje m, calcula (etapa 304, la cual proporciona una firma utilizando la clave secreta/privada generada como se discutió anteriormente), en donde p es el mapa Frobenius de energía qava y la suma denota la suma de la curva elíptica ? . Por conveniencia, se denota el operador ¿~n=o a través de Tr (lo que significa "trazo"). La salida SsE^Fq) como la firma. La firma es entonces enviada a y recibida por una parte receptora (306 y 308, respectivamente). Observar que el grupo Galois de Fqn/Fq es {1 , p, ... p?'? }, por lo que S es una invariante Galois y de esta manera se define sobre Fq. Verificación. Dejar que y e2 denoten los aparejamientos Weil sobre E?[/] y E2[k], respectivamente. Dada una clave pública (P,Q) y un par de mensaje-firma (m,S), verificar si 310> ,g cua) verifica la f¡rma recibida utilizando la clave pública generada como se discutió anteriormente). Por consiguiente, una firma válida satisface esta ecuación, como sigue: También, el mapa de trazos puede ser utilizado como un campo base para acortar puntos en una curva elíptica (o más generalmente sobre cualquier variedad Abelian). En otras palabras, la salida de una mapa de trazos sobre curvas elípticas (o variedades Abelian dimensionales más altas) puede ser utilizada como un método para acortar la representación de un punto sobre un campo de extensión utilizando datos en el campo inferior.

FIRMANDO CON MULTIPLES CURVAS ELIPTICAS Otra forma de mejorar la resistencia de los esquemas de firma corta es utilizar claves públicas múltiples y agregar las firmas ^ resultantes. Esta modificación puede ser utilizada por sí misma o combinada con el mejoramiento de la invariante Galois discutida anteriormente. Con referencia a la Figura 4, se sume que existe una familia de isogenias ø,;£? E¡ y una familia de funciones criptográficas H¡, cada una trazando un mapa de un mensaje m en un punto en la curva elíptica E¡. Similar a las etapas discutidas con referencia a la Figura 3. Clave pública. Seleccionar P e E aleatoriamente y publicar P,Q7,Q2, ...,Qn (ver, por ejemplo, 302), en donde Q, = 0(P). Clave secreta. La familia de isogenias ø,.

Firma. Para cada mensaje m , la firma de m (S) es ?.=i ^¿^'^W^ (ver, por ejemplo, 304). El mensaje firmado entonces es enviado a una parte receptora (ver, por ejemplo 306). Verificación. Dado un par (mensaje, firma) (m,S), verificar si (ver, por ejemplo, etapa 310 discutida con referencia a la Figura 3). Para una firma válida esta ecuación se mantiene ya que: J i-l -i=l El sistema se cree que es por lo menos tan seguro como el uso de solo una isogenia individual, ya que cualquiera que pueda interrumpir la versión de isogenias múltiples puede convertir la versión de isogenia individual en la versión de isogenias múltiples agregando las isogenias ø?, ...,ø„ según determinado por ellos. Además, para dicho sistema, cualquier ataque exitoso sobre la versión de isogenias múltiples requiere una interrupción simultánea de todas las isogenias individuales f a ø„.

ESQUEMA DE CODIFICACIÓN BASADO EN IDENTIDAD (IBE) CON ISOGENIAS La Figura 5 ilustra un método ejemplar 500 para codificación basada en identidad (IBE) utilizando isogenias. La isogenia en una sola dirección entre las curvas elípticas se cree que produce un esquema de codificación basado en identidad (IBE) potencialmente seguro contra los cálculos Diffie-Hellman (CDH). El esquema IBE puede ser definido como sigue. MAPA A UN PUNTO. Define la operación ID ? P e E para alguna curva E. Más específicamente, se puede calcular H(id) y utilizarla para definir un punto. Se puede asumir que H se comporta como un oráculo aleatorio. Alternativamente, se puede mantener un cuadro puntos e ID criptográfico dentro de una cadena aleatoria de pesos y después tomar una suma ponderada. También se puede asumir que existe una autoridad confiable y un grupo finito de usuarios, cada uno con algún ID a partir del cual se puede calcular la clave pública correspondiente. Cada usuario obtiene su clave privada después de la identificación adecuada a través de la autoridad confiable. Clave Pública para la Autoridad Confiable. aeE ß-ß(&). Por consiguiente, una autoridad confiable (u otra entidad tal como una parle receptora) proporciona y publica claves públicas (502). Se está utilizando un giro X, se puede asumir que a-X(a) es la imagen girada de algún punto a.

Clave Privada para la Autoridad Confiable. Una F calculable eficientemente. Por ejemplo, los datos codificados de Bob y Alicia pueden ser implementados como sigue- Clave pública para Alicia. TeE2 es provista, por ejemplo, a través de la función mapa a punto ID? 7 (503) a través de una autoridad confiable (u otra entidad tal como una parte receptora).

Clave privada para Alicia. ^~ · Observar que al atacar para obtener una clave privada rápidamente para cada cliente tomará un tiempo similar al de la interrupción global en el sistema de firma (discutido más adelante). Como un resultado, estos sistemas también pueden ser referidos como sistemas de dos-filas. Codificación de Bob. Calcular ALICE ? 7 (etapa 504, las cual codifica un mensaje con ia clave pública generada). Dejar que el mensaje sea m. Seleccionar un entero aleatorio r. Enviar a Alicia el par (506): [?F?(?(ß,G?)),Ga] Descodificación a través de Alicia. Dejar que el texto cifra sea [c,7"]. El mensaje codificado enviado es descodificado (508) utilizando una clave privada (510) provista por una autoridad confiable (u otra entidad tales como una parte receptora) después de una identificación adecuada. Como un resultado, el texto claro es: c®H(e(ra,S)) Esto funciona porque la cantidad que se está criptografiando en la etapa de codificación es: e{fi,rT) = ß(f{?),t? = e( ,}(rT)) = e(a,r (T) = e(a,rS = e(r ,S), la cual es igual a la cantidad que se está criptografiando en la etapa de codificación. Una isogenia puede ser representada como se discutió anteriormente (por ejemplo, para utilizar un método probabilístico que involucra un cuadro de entradas).

ESPECIFICACION DE UNA ISOGENIA Si la isogenia es suave, puede estar representada como una composición de isogenias de grado pequeño dadas por un programa de línea recta representando cálculos de polinomio. Para curvas sobre extensiones de interés, un pequeño cuadro de pares de entrada-salida es suficiente en una implementación.

Tomando End(E) = Endk (E), las expresiones finitas de k pueden ser consideradas y la extensión puede ser especificada como apropiada. En una implementación, una isogenia es especificada a través de su acción sobre el grupo de puntos a través de alguna extensión finita del campo base. Observar que dos isogenias pueden coincidir hasta algunas extensiones, pero pueden ser distintas en un campo más grande. Por consiguiente, es suficiente para especificar 0 en un grupo de generadores S. Generalmente, el grupo es cíclico, o como anteriormente |S| = 2. No se considera fácil encontrar los generadores, pero se puede seleccionar S aleatoriamente. Más particularmente, como un grupo Abelian E(k) (recupera: k es un campo finito de elementos q) es isomórfico a Z/mZxZ/nZ, en donde mn=#E(k),n\m y además n\D,D=(mn,q-1) . Se puede calcular mn = #E(k) utilizando el algoritmo de Schoof y si la factorizacion de D es conocida, n puede ser obtenida utilizando un algoritmo de tiempo de polinomio aleatorizado. Si ^ y Q son del orden de n y m respectivamente de tal manera que cualquier punto puede ser escrito como aP + bQ, estas son llamadas generadores en forma de escalón y un algoritmo Ofq½+£) puede ser utilizado para su construcción. Cambiando ahora a opciones aleatorias (Erdos-Renyi), dejar que G sea un grupo Abelian finito y gi,...,gk sean elementos aleatorios de G. Ahí existe una pequeña constante c, tal como sus sumas de subgrupo son casi uniformemente distribuidas sobre G, si k =c-log|G|. En particular, la g, puede generar G. Para reducir el tamaño del cuadro, se pueden utilizar las sumas de subgrupo ponderadas fortalecidas en lugar de las sumas de subgrupos cuando el orden del grupo es primo. Esto se extiende a órdenes arbitrarios con alguna pequeña pérdida de los parámetros. Además, la estructura de E(k) puede ser utilizada para obtener información más detallada. Se pueden seleccionar puntos aleatorios P,,/'=2 y escribirlos como P¡ = a, P + Más particularmente, se puede expresar cada uno de los generadores de escalón a través de a, a, [ ] combinaciones lineales de P, si la matriz ¾ es la última m ¡nvertible (observar que n\m). Cuando esto sucede, {P,} generará el grupo. Observar que la probabilidad (ambas P1 y P2) cae en el grupo generado por es m . Similarmente, la probabilidad para el grupo generado por es n'2. De esta manera, cualquiera de estos dos eventos no suceden con probabilidad ( 1 -m~2)('\ -n'2)- 1 +(#E)"2-(m"2 + n~ 2).

IMPLEMENTACION DE HARDWARE La Figura 6 ¡lustra un ambiente de computadora general 600, el cual puede ser utilizado para ¡mplementar las técnicas descritas aquí. Por ejemplo, el ambiente de computadora 600 puede ser utilizado para ejecutar instrucciones asociadas con la desarrollo de tareas discutidas con referencia a los dibujos previos. Además, cada entidad discutida aquí (por ejemplo, con respecto a las Figuras 1, 3 y 5, tales como la parte confiable, la parte receptora, y/o la parte remitente) puede cada una tener acceso a un ambiente de computadora general. El ambiente de computadora 600 es solamente un ejemplo de un ambiente de computación y no pretende sugerir ninguna limitación al alcance del uso o funcionalidad de las arquitecturas de la computadora y de la red. Tampoco debería el ambiente de computadora 600 ser interpretado como teniendo ninguna dependencia o requerimiento relacionado con ninguno o una combinaciones de componentes ilustrados en el ambiente de computación ilustrativo 600. El ambiente de computadora 600 incluye un dispositivo de computación de propósito general en la forma de una computadora 602. Los componentes de la computadora 602 pueden incluir, pero no se limitan a, uno o más procesadores o unidades de procesamiento 604 (opcionalmente incluyendo un procesador criptográfico o co-procesador), una memoria del sistema 606, y un conductor común del sistema 608 que acopla varios componentes del sistema incluyendo el procesador 604 a la memoria del sistema 606. El conductor común del sistema 608 representa uno o más de varios tipos de estructuras de conductores comunes, incluyendo un conductor común de memoria o controlador de memoria, un conductor común periférico, un puerto de gráficos acelerado, y un procesador o conductor común local utilizando cualquiera de una variedad de arquitecturas de conductor común. A manera de ejemplo, dichas arquitecturas pueden incluir un conductor común de la Arquitectura Estándar de la Industria (ISA), un conductor común de la Arquitectura del Canal Micro (MCA), un conductor común ISA Mejorado (EISA), un conductor común local de la Asociación de Estándares Electrónicos de Video (VESA) y un conductor común de Interconexiones del Componente Periférico (PCI) también conocido como conductor común Mezanine. La computadora 602 típicamente incluye una variedad de medios legibles por computadora. Dichos medios legibles por computadora puede ser cualquier medio disponible que es accesible a través de computadora 602 e incluyen medios volátiles y no volátiles, medios removibles y no removibles. La memoria del sistema 606 incluye medios legibles por computadora en la forma de memoria volátil tal como la memoria de acceso aleatorio (RAM) 610, y/o memoria no volátil, tal como memoria de solo lectura (ROM) 612. Un sistema de entrada/salida básico (BIOS) 614, conteniendo las rutinas básicas que ayudan a la transferencia de información entre elementos dentro de la computadora 602, tales como durante el arranque, se almacenan en ROM 612. RAM 610 típicamente contiene datos y/o módulos de programa que son Inmediatamente accesibles para y/o actualmente operados por la unidad de procesamiento 604. La computadora 602 también puede incluir otros medios de almacenamiento por computadora removibles/no removibles, volátiles/no volátiles. A manera de ejemplo solamente, la Figura 6 ¡lustra una unidad de disco duro 616 para leer de y escribir en un medio magnético no removióle, no volátil (no mostrado), una unidad de disco duro magnético 618 para leer de o escribir en un disco magnético removible, no volátil 620 (por ejemplo, un "disco flexible"), y una unidad de disco óptico 622 para leer de o escribir en disco óptico removible, no volátil 624, tal como un CD ROM, DVD-ROM, u otro medio óptico. La unidad de disco duro 616, unidad de disco magnético 618 y la unidad de disco óptico 622 cada una está conectada al conductor común del sistema 608 a través de una o más ¡nterfases de medios de datos 626. Alternativamente, la unidad de disco duro 616, la unidad de disco magnético 618 y la unidad de disco óptico 622 pueden estar conectadas al conductor común del sistema 608 a través de una o más interfases (no mostradas). Las unidades de disco y sus medios legibles por computadora asociados, proporcionan almacenamiento no volátil de instrucciones legibles por computadora, estructuras de datos, módulos de programa y otros datos para la computadora 602. Aunque el ejemplo ilustra una unidad de disco duro 616, un disco magnético removible 620 y un disco óptico removible 624, se apreciará que otros tipos de medios legibles por computadora que pueden almacenar datos que son accesibles a través de una computadora, tales como casetes magnéticos u otros dispositivos de almacenamiento magnético, tarjetas de memoria no volátil, CD-ROM, discos versátiles digitales (DVD) u otro almacenamiento óptico, memorias de acceso aleatorio (RAM), memorias de sólo lectura (ROM), memoria de solo lectura programable eléctricamente borrable (EEPROM), y similares, también pueden ser utilizados para ¡mplementar el sistema y ambiente de computación ilustrativo. Cualquier número de módulos de programa pueden ser almacenados en el disco duro 616, disco magnético 620, disco óptico 624, ROM 612, y/o RAM 610, incluyendo a manera de ejemplo, un sistema operativo 625, uno o más programas de aplicación 628, otros módulos de programa 630, y datos de programa 632. Cada sistema operativo 625, uno o más programas de aplicación 628, otros módulos de programa 630, y datos de programa 632 (o una combinación de los mismos) puede implementar todos o parte de los componentes residentes que soportan el sistema de archivo distribuido. Un usuario puede capturar comandos e información en la computadora 602 a través de los dispositivos de entrada tales como un teclado 634 y un dispositivo de apuntamiento 636 (por ejemplo, un "ratón"). Otros dispositivos de entrada 638 (no mostrados específicamente) pueden incluir un micrófono, palanca de mandos, almohadillas de juegos, antena parabólica, escáner y/o similar. Estos y otros dispositivos de entrada están conectados a la unidad de procesamiento 604 a través de interfases de entrada/salida 640 que están acopladas al conductor común del sistema 608, pero pueden estar conectados a través de otras interfases y estructuras de conductores comunes, tales como un puerto paralelo, un puerto de juego o conductor común serial universal (USB).

Un monitor 642 u otro tipo de dispositivo de pantalla también está conectado al conductor común del sistema 608 a través de una interfase, tal como un adaptador de video 644. Además del monitor 642, otros dispositivos de salida periféricos pueden incluir componentes tales como bocinas (no mostradas) y una impresora 646, los cuales pueden conectarse a la computadora 602 a través de interfases de entrada/salida 640. La computadora 602 opera en un ambiente conectado en red utilizando conexiones lógicas a una o más computadoras remotas, tal como el dispositivo de computación remoto 648. A manera de ejemplo, el dispositivo de computación remoto 648 puede ser una computadora personal, computadora portátil, un servidor, un direccionador, una computadora en red, un dispositivo par, u oro nodo de red común, consola de juego, y similar. El dispositivo de computación remoto 648 se ilustra como un computadora portátil que puede incluir muchos o todos los elementos y características descritas aquí con relación a la computadora 602. La conexiones lógicas entre la computadora 602 y la computadora remota 648 se describen como una red de área local (LAN) 650 y una red de área amplia general (WAN) 652. Dichos ambientes en red son lugares comunes en las oficinas, redes de computadora amplias de empresa, intranets y el Internet. Cuando se implementa en un ambiente conectado en red, la computadora 602 está conectada a una red local 650 a través de una interfase de red o adaptador 654. Cuando se implementa en un ambiente conectado en red WAN, la computadora 602 típicamente incluye un módem 656 u otros medios para establecer comunicaciones a través de una red amplia 652. El módem 656, el cual puede ser interno o externo a la computadora 602, puede estar conectado al conductor común del sistema 608 a través de interfases de entrada/salida 640 u otros mecanismos apropiados. Se apreciará que las conexiones de red ilustradas son ilustrativas y que otros medios para establecer un enlace(s) de comunicaciones entre las computadoras 602 y 648 pueden ser empleados. En un ambiente conectado en red, tal como aquel que se ilustra con el ambiente de computación 600, los módulos de programa descritos con relación a la computadora 602, o porciones de los mismos, puede estar almacenados en un dispositivo de almacenamiento de memoria remoto. A manera de ejemplo, los programas de aplicación remotos 658 residen en un dispositivo de memoria de la computadora remota 648. Para propósitos de ilustración, los programas de aplicación y otros componentes de programa ejecutables tales como el sistema operativo se ilustran en la presente como bloques discretos, aunque se reconoce que dichos programas y componentes residen en varios tiempos en diferentes componentes de almacenamiento del dispositivo de computación 602, y se ejecutan a través del procesador(es) de datos de la computadora. Varios módulos y técnicas pueden ser descritos aquí en el contexto general de instrucciones ejecutables por computadora, tales como módulos de programa, ejecutados por una o más computadoras u otros dispositivos. Generalmente, los módulos de programa incluyen rutinas, objetos de programa, componentes, estructuras de datos, etc. que realizan tareas particulares o implementan tipos de datos abstractos. Típicamente, la funcionalidad de los módulos de programa puede ser combinada o distribuida según se desee en varias implementaciones. Una ¡mplementación de estos módulos y técnicas puede ser almacenada en o transmitida a través de alguna forma de medio legible por computadora. Los medios legibles por computadora pueden ser cualquier medio disponible que pueda ser accedido por una computadora. A manera de ejemplo, y no limitación, los medios legibles por computadora pueden comprender "medios de almacenamiento por computadora" y "medios de comunicaciones". Los "medios de almacenamiento por computadora" incluyen medios volátiles y no volátiles, removibles y no removibles implementados en cualquier método o tecnología para almacenar información tal como instrucciones legibles por computadora, estructura de datos, módulos de programa, u otros datos. Los medios de almacenamiento por computadora incluyen, pero no se limitan a, RAM, ROM, EEPROM, memoria no volátil u otra tecnología de memoria, CD-ROM, discos versátiles digitales (DVD), u otro almacenamiento óptico, casetes magnéticos, cinta magnética, almacenamiento en disco magnético, u otros dispositivos de almacenamiento magnético, o cualquier otro medio que puede ser utilizado para almacenar información y el cual puede ser accedido a través de una computadora. Los "medios de comunicación" típicamente incluyen instrucciones legibles por computadora, estructura de datos, módulos de programa u otros datos en una señal de datos modulada, tales como una onda portadora u otro mecanismo de transporte. Los medios de comunicación también incluyen cualquier medio de distribución de información. El término "señal de datos modulada" significa una señal que tiene una o más de sus características establecidas o cambiadas en dicha forma que codifican información en la señal. A manera de ejemplo, y no limitación, los medios de comunicación incluyen medios cableados tales como una red cableada, o conexión cableada directa y medios inalámbricos, tales acústicos, de radio frecuencia (RF), infrarrojos (IF), fidelidad inalámbrica (por ejemplo, conexión en red inalámbrica IEEE 802.11 b) (Wi-Fi), celular, habilitado para Bluetooth, y otros medios inalámbricos. Las combinaciones de cualquiera de los anteriores también están incluidas dentro del alcance de los medios legibles por computadora.

CONCLUSION Aunque la invención ha sido descrita en un lenguaje específico a las características estructurales y/o acciones metodológicas, se entenderá que la invención definida en las reivindicaciones anexas no está necesariamente limitada a las características específicas o acciones descritas. En su lugar, las características específicas y acciones se describen como formas ilustrativas de implementación de la invención reclamada. Por ejemplo, las curvas elípticas descritas aquí son un caso unidimensional de variedades Abelian. También, las isogénias pueden ser utilizadas en otras aplicaciones tales como firmas ciegas, sistemas jerárquicos, y similares. Es decir, las técnicas descritas aquí pueden ser aplicadas a variedades Abelian de dimensión más alta.

Claims (39)

REIVINDICACIONES

1. Un método que comprende: generar una isogenia que delinea un mapa de una pluralidad de puntos a partir de una primera curva elíptica en una segunda curva elíptica; publicar una clave pública correspondiente a la isogenia; codificar un mensaje utilizando una clave de codificación correspondiente a la isogenia; y descodificar el mensaje codificado utilizando una clave de descodificación correspondiente a la isogenia.

2. Un método de acuerdo con la reivindicación 1, en donde por lo menos una de la clave de codificación y la clave de descodificación es una clave privada, la clave privada siendo una isogenia doble de la isogenia.

3. Un método de acuerdo con la reivindicación 1, en donde la isogenia es generada utilizando una técnica seleccionada del grupo que comprende generación de una multiplicación compleja, generación modular, generación linealmente independiente, y combinaciones de las mismas.

4. Un método de acuerdo con la reivindicación 1 , en donde se generan mapas de una pluralidad de puntos de una primera curva elíptica en una pluralidad de curvas elípticas.

5. Un método de acuerdo con la reivindicación 1, en donde la descodificación se lleva a cabo a través de aparejamiento bilineal.

6. Un método de acuerdo con la reivindicación 5, en donde el aparejamiento bilineal es un aparejamiento seleccionado de un grupo que comprende aparejamiento Weil, aparejamiento Tate, y aparejamiento de cuadrado.

7. Un método de acuerdo con la reivindicación 1, en donde el método se aplica utilizando variedades Abelian.

8. Un método de acuerdo con la reivindicación 1, en donde el método firma el mensaje.

9. Un método de acuerdo con la reivindicación 1, en donde el método proporciona codificación basada en la identidad.

10. Un método de acuerdo con la reivindicación 1, que comprende además la composición de una pluralidad de isogenias modulares para proporcionar la isogenia sin revelar ninguna curva intermedia.

11. Un método de acuerdo con la reivindicación 1, que comprende además el uso de un mapa de trazos a lo largo de un campo base de puntos acortados en una curva elíptica trazada en un mapa a través de la isogenia.

12. Un método de acuerdo con la reivindicación 1, que comprende además utilizar un mapa de trazos para puntos acortados en una variedad Abelian.

13. Un método que comprende: publicar una clave pública correspondiente a una isogenia que traza un mapa de una pluralidad de puntos de una primera curva elíptica en una segunda curva elíptica; y descodificar un mensaje codificado utilizando una clave de descodificación correspondiente a la isogenia.

14. Un método de acuerdo con la reivindicación 13, en donde la clave de descodificación es una isogenia doble de la isogenia.

15. Un método de acuerdo con la reivindicación 13, en donde la isogenia se genera utilizando una técnica seleccionada del grupo que comprende una generación de multiplicación compleja, una generación modular, una generación independientemente lineal, y combinaciones de las mismas.

16. Un método de acuerdo con la reivindicación 13, en donde la isogenia traza un mapa de una pluralidad de puntos de una primera curva elíptica en una pluralidad de curvas elípticas.

17. Un método de acuerdo con la reivindicación 13, en donde la descodificación se lleva a cabo a través de aparejamiento bilineal.

18. Un método de acuerdo con la reivindicación 17, en donde el aparejamiento bilineal es un aparejamiento seleccionado de un grupo que comprende aparejamiento Weil, aparejamiento Tate, y aparejamiento de cuadrado.

19. Un método de acuerdo con la reivindicación 13, en donde el método se aplica utilizando variedades Abelian.

20. Un método de acuerdo con la reivindicación 13, en donde el método firma el mensaje.

21. Un método de acuerdo con la reivindicación 13, en donde el método proporciona codificación basada en la identidad.

22. Un método de acuerdo con la reivindicación 13, que comprende además el uso de un mapa de trazos a lo largo de un campo bajo para puntos acortados en una curva elíptica trazada sobre un mapa a través de la isogenia.

23. Un sistema que comprende: un primer procesador; una primera memoria del sistema acoplada al primer procesador, la primera memoria del sistema almacenando una clave pública correspondiente a una isogenia que traza un mapa de una pluralidad de puntos de una primera curva elíptica en una segunda curva elíptica; un segundo procesador; una segunda memoria del sistema acoplada al segundo procesador, la segunda memoria del sistema almacenando un mensaje codificado y una clave de descodificación correspondiente a la isogenia para descodificar el mensaje codificado, en donde el mensaje codificado se codifica utilizando una clave de codificación.

24. Un sistema de acuerdo con la reivindicación 23, en donde por lo menos una de la clave de codificación o la clave de descodificación es una clave privada, la clave privada siendo una isogenia doble de la isogenia.

25. Un sistema de acuerdo con la reivindicación 23, en donde la isogenia traza un mapa de una pluralidad de puntos de una primera curva elíptica en una pluralidad de curvas elípticas.

26. Un sistema de acuerdo con la reivindicación 23, en donde la descod ificación se lleva a cabo a través de aparejamiento bilineal.

27. Un sistema de acuerdo con la reivindicación 26, en donde el aparejamiento bilineal es un aparejamiento seleccionado de un grupo que comprende aparejamiento Weil, aparejamiento Tate, y aparejamiento de cuadrado.

28. Uno o más medios legibles por computadora que tienen instrucciones almacenadas en la misma que, cuando se ejecutan, dirigen una máquina a que realice las acciones que comprenden: publicar una clave pública correspondiente a una isogenia que traza un mapa de una pluralidad de puntos de una primera curva elíptica en una segunda curva elíptica; y descodificar un mensaje codificado utilizando una clave de descodificación correspondiente a la isogenia.

29. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde la clave de descodificación es una clave privada, la clave privada, la clave privada siendo una isogenia doble de la isogenia.

30. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde la isogenia se genera utilizando una técnica seleccionada del grupo que comprende la generación de una multiplicación compleja, generación modular, generación linealmente independiente, y combinaciones de las mismas.

31. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde la isogenia traza un mapa de una pluralidad de puntos de una primera curva elíptica en una pluralidad de curvas elípticas.

32. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde la descodificación se realiza a través de aparejamiento bilineal.

33. Uno o más medios legibles por computadora de acuerdo con la reivindicación 32, en donde el aparejamiento bilineal es un aparejamiento seleccionado de un grupo que comprende aparejamiento Weil, aparejamiento Tate, y aparejamiento de cuadrado.

34. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde las acciones se aplican utilizando variedades Abelian.

35. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde las acciones además comprenden el uso de un mapa a lo largo de un campo base para puntos acortados en una curva elíptica trazada en un mapa a través de la isogenia.

36. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde las acciones además comprenden componer una pluralidad de isogenías modulares para proveer la isogenia sin revelar ninguna curva intermedia.

37. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde las acciones además comprende el uso de un mapa de trazos para puntos acortados en una variedad Abelian.

38. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde las acciones firman el mensaje.

39. Uno o más medios legibles por computadora de acuerdo con la reivindicación 28, en donde las acciones proveen codificación basada en la identidad.