Epónimos relacionados con las matemáticas

 Esquema de firma ElGamal es un esquema de firma digital basado en la complejidad del cálculo del logaritmo discreto. Fue descrito por Taher ElGamal en 1984. El algoritmo de firma ElGamal descrito en su artículo es raramente utilizado en la práctica. Con más frecuencia se utiliza una de sus variantes llamada Algoritmo de firma digital (DSA). El esquema de firma ElGamal no debe confundirse con el cifrado ElGamal también propuesto por Taher ElGamal.

El esquema de firma ElGamal permite que un verificador pueda confirmar la autenticidad de un mensaje m enviado por un emisor sobre un canal de comunicación inseguro.

Parámetros

Los parámetros utilizados por el esquema ElGamal son:

• Una función de hash H resistente a colisiones.
• Un número primo p muy grande tal que el cómputo de logaritmos discretos módulo p sea difícil.
• un generador pseudoaleatorio g para el grupo multiplicativo ${\displaystyle Z_{p}^{*}}$.

Los parámetros utilizados pueden ser compartidos entre usuarios.

Generación de claves

• Se selecciona un clave secreta x de forma aleatoria tal que ${\displaystyle 1$.
• Se calcula ${\displaystyle y=g^{x}{\pmod {p}}}$.
• La clave pública será (p,g,y).
• La clave secreta será x.

Estos pasos son realizados una sola vez por el firmante.

Generación de una firma

Para firmar un mensaje m el firmante realiza los pasos siguientes.

• Selecciona un número aleatorio k tal que ${\displaystyle 0$ y ${\displaystyle mcd(k,p-1)=1}$.
• Calcula ${\displaystyle r\,\equiv \,g^{k}{\pmod {p}}}$.
• Calcula ${\displaystyle s\,\equiv \,(H(m)-xr)k^{-1}{\pmod {p-1}}}$.
• Si ${\displaystyle s=0}$ reinicia el proceso.

El par (r,s) así obtenido es la firma digital de m. El firmante repite estos pasos para cada mensaje m que desea firmar.

Verificación

La firma (r,s) de un mensaje m proveniente de un firmante con clave pública (p,g,y) y que utilizó una función de Hash H se verifica de la siguiente forma:

• Se verifica que ${\displaystyle 0$ y que ${\displaystyle 0$.
• Se verifica que ${\displaystyle g^{H(m)}\,\equiv \,y^{r}r^{s}{\pmod {p}}.}$.

El verificante acepta el mensaje únicamente si estas tres condiciones se cumplen.

Corrección

El algoritmo es correcto en el sentido que una firma generada con este algoritmo de firma siempre será aceptada por un verificador.

La generación de firmas incluye

${\displaystyle H(m)\,\equiv \,xr+sk{\pmod {p-1}}.}$

Del pequeño teorema de Fermat se tiene

${\displaystyle {\begin{matrix}g^{H(m)}&\equiv &g^{xr}g^{ks}\\&\equiv &(g^{x})^{r}(g^{k})^{s}\\&\equiv &(y)^{r}(r)^{s}{\pmod {p}}.\\\end{matrix}}}$

Seguridad

Un tercero puede falsificar firmas si encuentra la clave secreta x del firmante o si encuentra colisiones en la función de Hash ${\displaystyle H(m)\equiv H(M){\pmod {p-1}}}$. Se considera que ambos problemas son suficientemente difíciles.

El firmante debe tener cuidado y escoger una k diferente de forma uniformemente aleatoria para cada firma. Así asegura que k o aún información parcial sobre k no es deducible. Malas selecciones de k pueden representar fugas de información que facilitan el que un atacante deduzca la clave secreta x. En particular, si dos mensajes son enviados con el mismo valor de k entonces es factible deducir el valor de la clave secreta x.

Esquema ElGamal

Recordamos que todo usuario posee una llave pública (p_U,x_U,y_U) y una llave secreta z_U, donde p es primo, x_U es un elemento primitivo de  e . Se tiene pues:

• Para un entero k aleatorio:  donde  ¡Atención! Si se mostrase k entonces podría calcularse la llave secreta z_U a partir de la firma: 
• ,
  pues en el caso de que (u,e) resultase del proceso de firmar, necesariamente:
  
  
  y_U^u u^e=x_U^z_U ux_U^ke=x_U^m
  
  
  ya que .

Un intruso S que conociese el mensaje m buscaría generar los correspondientes coeficientes (u,e) de la firma. Si conociese u, el exponente e podría conocerse calculando . Si conociese e, el elemento u podría conocerse tratando de reslver la ecuación: . Algún otro intento consistiría en tratar de calcular simultáneamente u,e. No se conoce de un algoritmo eficiente que lo haga. Tampoco se ha demostrado que no exista tal algoritmo. Sn embargo, de manera aleatoria un intruso podría generar mensajes firmados: Sean  tales que j y p-1 sean primos relativos. Definamos: 

Entonces (u,e) es una firma de m con la llave pública (p,x,y). En efecto, módulo p valen las igualadades siguientes: 

Un segundo procedimiento para generar firmas legítimas sobre ciertos mensajes es el siguiente: Supongamos conocido unmensaje m con su firma correspondiente (u,e). Sean  tales que hu-je y p-1 sean primos relativos. Definamos: 

Entonces (u',e') es una firma de m' con la llave pública (p,x,y).

El sistema de compartición de secretos de Shamir es un algoritmo criptográfico. Es una forma de compartición de secretos donde un secreto se divide en partes y se da a cada participante una sola: todas o parte de ellas son necesarias para reconstruir el secreto.

El algoritmo basa su funcionamiento en una propiedad de los polinomios interpoladores¹ y fue desarrollado por el criptógrafo israelí Adi Shamir, que lo presentó en 1979.

Definición matemática

Formalmente, nuestro objetivo es dividir un conjunto de datos ${\displaystyle D\,\!}$ (por ejemplo, una clave) en ${\displaystyle n\,\!}$ partes ${\displaystyle D_{1},\cdots ,D_{n}\,\!}$ de manera que:

1. El conocimiento de ${\displaystyle k\,\!}$ o más ${\displaystyle D_{i}\,\!}$ partes hace que ${\displaystyle D\,\!}$ sea fácilmente computable.³
2. El conocimiento de ${\displaystyle k-1\,\!}$ o menos ${\displaystyle D_{i}\,\!}$ partes hace que ${\displaystyle D\,\!}$ esté indeterminado, en el sentido de que todos sus valores posibles tienen la misma probabilidad de ser verdaderos.

Esta combinación se denomina combinación o esquema de umbral ${\displaystyle \left(k,n\right)\,\!}$.² Si ${\displaystyle k=n\,\!}$ se requiere la concurrencia de todos los participantes para reconstruir el secreto.

Sistema de compartición de secretos de Shamir

Se pueden dibujar infinitos polinomios de grado 2 que pasen por 2 puntos. Se necesitan 3 puntos para definir un polinomio único de grado 2. Esta imagen sólo tiene fines ilustrativos - El esquema de Shamir utiliza polinómios en un conjunto finito, no representable en un plano bidimensional.

La idea esencial de la combinación de umbral de Shamir es que dos puntos son suficientes para definir una línea recta, tres puntos lo son para definir una parábola, cuatro para definir una curva cúbica y así sucesivamente. Es decir, son necesarios ${\displaystyle n+1\,\!}$ puntos para definir un polinomio de grado ${\displaystyle n\,\!}$.

Supongamos que queremos trabajar con un umbral de ${\displaystyle \left(k,n\right)\,\!}$ para compartir un secreto ${\displaystyle S\,\!}$ (cualquier número, sin pérdida de generalidad) siendo ${\displaystyle k$. La elección de los valores de ${\displaystyle k\,\!}$ y ${\displaystyle n\,\!}$ determina la fortaleza del sistema.

Eligiendo al azar ${\displaystyle \left(k-1\right)\,\!}$ coeficientes ${\displaystyle a_{1},\cdots ,a_{k-1}\,\!}$, y siendo ${\displaystyle a_{0}=S\,\!}$, se construye el polinomio ${\displaystyle f\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{k-1}x^{k-1}\,\!}$. Calculamos cualesquiera ${\displaystyle n\,\!}$ puntos a partir del mismo, por ejemplo determinamos que ${\displaystyle i=1,\cdots ,n\,\!}$ de lo que se deriva ${\displaystyle \left(i,f\left(i\right)\right)\,\!}$. A todo participante en el secreto se le da un punto (un par de valores, el de entrada y el de salida para el polinomio)

Dado cualquier subconjunto de ${\displaystyle k\,\!}$ entre estos pares, podemos calcular los coeficientes del polinomio mediante interpolación y luego despejar ${\displaystyle a_{0}\,\!}$, que es el secreto.

Ejemplo de uso

Preparación

Supongamos que el secreto es el número de una tarjeta de crédito: 1234 ${\displaystyle (S=1234)\,\!}$.

Queremos dividir el secreto en seis partes ${\displaystyle (n=6)\,\!}$, de forma que cualquier subconjunto ${\displaystyle (k=3)\,\!}$ sea suficiente para reconstruir el secreto. Al azar obtenemos ${\displaystyle k-1}$ números: por ejemplo, 166 y 94.

${\displaystyle (a_{1}=166;a_{2}=94)\,\!}$

El polinomio con el que operaremos será por lo tanto:

${\displaystyle f\left(x\right)=1234+166x+94x^{2}\,\!}$

Calculamos seis puntos a partir del polinomio:

${\displaystyle \left(1,1494\right);\left(2,1942\right);\left(3,2578\right);\left(4,3402\right);\left(5,4414\right);\left(6,5614\right)\,\!}$

Damos a cada partícipe un único punto, que comprende el valor ${\displaystyle x\,\!}$ y ${\displaystyle f\left(x\right)\,\!}$).

Reconstrucción

Para reconstruir el secreto bastará con tres puntos.

Considérese

${\displaystyle \left(x_{0},y_{0}\right)=\left(2,1942\right);\left(x_{1},y_{1}\right)=\left(4,3402\right);\left(x_{2},y_{2}\right)=\left(5,4414\right)\,\!}$.

Usamos la interpolación polinómica de Lagrange:

${\displaystyle \ell _{0}={\frac {x-x_{1}}{x_{0}-x_{1}}}\cdot {\frac {x-x_{2}}{x_{0}-x_{2}}}={\frac {x-4}{2-4}}\cdot {\frac {x-5}{2-5}}={\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}\,\!}$

${\displaystyle \ell _{1}={\frac {x-x_{0}}{x_{1}-x_{0}}}\cdot {\frac {x-x_{2}}{x_{1}-x_{2}}}={\frac {x-2}{4-2}}\cdot {\frac {x-5}{4-5}}=-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5\,\!}$

${\displaystyle \ell _{2}={\frac {x-x_{0}}{x_{2}-x_{0}}}\cdot {\frac {x-x_{1}}{x_{2}-x_{1}}}={\frac {x-2}{5-2}}\cdot {\frac {x-4}{5-4}}={\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}\,\!}$

Por lo tanto,

${\displaystyle f(x)=\sum _{j=0}^{2}y_{j}\cdot \ell _{j}(x)\,\!}$

${\displaystyle =1942\cdot \left({\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}\right)+3402\cdot \left(-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5\right)+4414\cdot \left({\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}\right)\,\!}$

${\displaystyle =1234+166x+94x^{2}\,\!}$

Teniendo en cuenta que el secreto es el coeficiente de ${\displaystyle x^{0}\,\!}$, el secreto original es ${\displaystyle S=1234\,\!}$.

La estructura de Weaire-Phelan es una estructura tridimensional compleja. En 1993, Denis Weaire y Robert Phelan, dos físicos del Trinity College (Dublín), descubrieron que en simulaciones informáticas de la espuma, esta estructura era una mejor solución al "problema de Kelvin" que la otra solución conocida, la estructura de Kelvin.

La estructura de Kelvin

Espuma poliédrica por octaedros truncados.

En 1887, Lord Kelvin se preguntó cómo podría particionarse el espacio en celdas de igual volumen con el área más pequeña de contacto entre ellas, por ejemplo, ¿cuál es la espuma de pompas de jabón más eficaz?² Este problema fue llamado desde entonces el problema de Kelvin.

Propuso la espuma del panal cúbico bitruncado, que se conoce como estructura de Kelvin. Se trata de un panal uniforme convexo formado por un octaedro truncado, un poliedro que llena el espacio con 14 lados (un tetracaidecaedro): seis lados cuadrados y ocho hexagonales. Para adecuarse a las leyes de Plateau que gobiernan las estructuras de las espumas, las caras hexagonales están ligeramente curvadas.

La conjetura de Kelvin es que la estructura de Kelvin resuelve el problema de Kelvin: la espuma del panal cúbico bitruncado es la espuma más eficaz. La conjetura de Kelvin fue aceptada y durante más de 100 años no se pudieron encontrar contra-ejemplos, hasta que fue descubierta la estructura de Weaire-Phelan.

Compárese con la conjetura de Kepler (sobre empacado (packing) más denso de esferas), que se considera que ha sido probada en 1998.

Descripción de la estructura de Weaire-Phelan

La estructura de Weaire-Phelan utiliza dos tipos de celdas de igual volumen; un dodecaedro pentagonal irregular y un tetracaidecaedro con dos hexágonos y doce pentágonos, otra vez con caras ligeramente curvadas. El área de superficie es 0.3% menos que la de la estructura de Kelvin, en este contexto una diferencia considerable. No ha sido probado que la estructura de Weaire-Phelan sea óptima, pero se considera que es la más apropiada: el problema de Kelvin está todavía abierto, pero se conjetura con que la estructura de Weaire-Phelan sea la solución.

La estructura de Clatrato

El panal asociado a la estructura de Weaire-Phelan (obtenido mediante el aplanamiento de las caras y el enderazamiento de las aristas) es conocido también de forma general como la estructura de Weaire-Phelan, y ya era bien conocido antes de la estructura fuese descubierta, aunque su aplicación al problema de Kelvin fue pasada por alto.³

Se encuentra como estructura de cristal en química, donde es habitualmente conocida con el nombre de 'Tipo I de estructura de clatrato'. Los hidratos de gas formados por metano, propano y dióxido de carbono a baja temperaturas tienen una estructura en la que las moléculas de agua reposan en los nudos de la estructura de Weaire-Phelan y se enlazan entre sí mediante puentes de hidrógeno, y las moléculas de gas más grandes son atrapadas en las jaulas poliédricas.

Algunos silicios y germanios alcalinos forman también esta estructura (Si/Ge en nudos, los alcalinos en jaulas), como hace el mineral de óxido de silicio melanoflogita (el silicio en nudos, enlazado por oxígenos por los lados). La melanoflogita es una forma metaestable de SiO₂que se estabiliza en esta estructura porque las moléculas de gas quedan atrapadas en las jaulas. La International Zeolite Association utiliza el símbolo MEP para indicar la topología marco del melanophlogite.

Aplicaciones

La estructura de Weaire-Phelan es la inspiración del diseño del Centro Acuático Nacional de Beijing construido con motivo de los Juegos Olímpicos de 2008 en China.

Estructura de Weaire–Phelan
Grupo espacial Notación fibrifold Notación de Coxeter	Pm3n (223) 2o [[4,3,4]+]