¿Cómo se esconde un secreto entre errores? El cifrado de McEliece

El cifrado de McEliece (1978) convierte tu mensaje en una palabra de un código corrector y le añade unos cuantos errores a propósito. Quien conoce el código secreto los corrige y lee el mensaje; para cualquier otra persona, si el código está bien disfrazado, quitar esos errores es tan difícil como decodificar un código lineal cualquiera, un problema para el que no se conoce ningún algoritmo eficiente. Sobrevive a RSA en un mundo con ordenadores cuánticos porque no se apoya en factorizar, pero en 2025 y 2026 aparecieron trabajos que estrechan su margen de seguridad. Esta página cuenta cómo funciona y qué se sabe, y qué no, de esos trabajos.

La idea

Tres papeles de los códigos correctores

En esta web, los códigos correctores hacen tres cosas distintas:

1. Proteger mensajes. Añaden redundancia para reparar daños, como en el código QR con Reed-Solomon.
2. Esconder secretos. Es el papel de este artículo: McEliece.
3. Proteger cúbits, en los ordenadores cuánticos, que es otra historia.

McEliece usa el mismo ingrediente que el QR, pero al revés. En el QR todo el mundo sabe cómo reparar. En McEliece solo lo sabe quien guarda la clave.

Cifrar es codificar y estropear

Un código lineal es una lista de palabras (cadenas de ceros y unos) que se describe con una matriz, la matriz generatriz: multiplicas tu mensaje por ella y sale la palabra del código. Si después se cambian algunos bits, un código bueno sabe encontrar la palabra más cercana, y así los repara.

McEliece hace esto:

• Clave pública: una matriz que parece una matriz cualquiera, pero que genera un código que Alicia, la receptora, conoce de verdad.
• Cifrar (Bob): codifica el mensaje con esa matriz y cambia a propósito $t$ bits, elegidos al azar. Esos errores son el «secreto escondido».
• Descifrar (Alicia): como conoce la estructura oculta del código, corrige los $t$ errores y recupera el mensaje.
• Espía (Eva): ve la matriz y el texto cifrado. Para quitar los errores tendría que decodificar un código lineal que, en la práctica, no sabe distinguir de uno cualquiera. En 1978, Berlekamp, McEliece y van Tilborg demostraron que la versión de decisión del problema general (dados una matriz de control, un síndrome y un número $w$, ¿hay un vector de error de peso como mucho $w$ con ese síndrome?) es NP-completa.

Lo de «NP-completo» necesita una advertencia: describe el peor caso de un problema general, no el caso típico, y no garantiza que sea difícil romper unas claves concretas. McEliece es seguro (o no) según lo difícil que sea reconocer y deshacer el disfraz del código escogido, no solo por esa propiedad.

Por qué el ordenador cuántico no le hace lo que a RSA

RSA se apoya en la factorización, y el algoritmo de Shor factoriza en tiempo razonable en un ordenador cuántico suficientemente grande (lo cuenta ¿Puede un ordenador cuántico romper RSA hoy?). McEliece no se apoya en la factorización ni en el logaritmo discreto, así que Shor no se aplica a él. No se conoce un algoritmo cuántico que decodifique un código lineal cualquiera con un salto comparable.

Lo que sí se aplica es el algoritmo de búsqueda de Grover, que reduce una búsqueda sin estructura de $N$ pasos a unos $\sqrt N$. Bernstein mostró en 2010 («Grover vs. McEliece») que se puede usar dentro de la decodificación por conjuntos de información, el mejor ataque genérico: su coste pasa a ser aproximadamente la raíz cuadrada del coste clásico, es decir, el exponente se divide por dos (de $c^{(1+o(1))n/\log_2 n}$ a $c^{(1/2+o(1))n/\log_2 n}$ operaciones, con $c$ una constante que depende de la tasa del código). Es un tipo de ventaja distinta: no convierte el problema en fácil, solo lo acelera, y se compensa con parámetros mayores (asintóticamente, duplicar la longitud $n$, lo que multiplica por cuatro el tamaño de la clave).

La frase justa es esta: un ordenador cuántico no le hace a McEliece lo que a RSA; lo que le preocupa hoy a los criptógrafos son los ataques clásicos a la estructura del código, y no los cuánticos.

El precio: claves enormes

La clave pública es una matriz grande. Según la especificación de Classic McEliece del 23 de octubre de 2022, la clave pública ocupa $mt\lceil k/8\rceil$ bytes (con $k=n-mt$) y el texto cifrado $\lceil mt/8\rceil$ bytes. Con los conjuntos de parámetros que la especificación define:

Conjunto	Clave pública	Texto cifrado
mceliece348864	261 120 bytes	96 bytes
mceliece460896	524 160 bytes	156 bytes
mceliece6688128	1 044 992 bytes	208 bytes
mceliece6960119	1 047 319 bytes	194 bytes
mceliece8192128	1 357 824 bytes	208 bytes

(Calculadas con la fórmula de la especificación; el script está en el repositorio de la web.) Es decir, claves de entre un cuarto de megabyte y 1,4 MB, pero cifrados cortos. Classic McEliece es, en rigor, la variante de McEliece con síndromes (la de Niederreiter) empaquetada como mecanismo de encapsulación de claves; la idea es la misma.

Historia: 1978-2026

Por qué resistió. McEliece lo propuso en 1978, en un informe del Jet Propulsion Laboratory, con un código de Goppa binario de longitud 1024, dimensión 524 y 50 errores. Desde entonces, los ataques que recuperan la clave aprovechando la estructura del código han tenido éxito contra casi todas las alternativas:

• Reed-Solomon generalizados: Sidelnikov y Shestakov mostraron en 1992 cómo recuperar la clave en un tiempo que crece como una potencia del tamaño.
• Subcódigos de Reed-Solomon: Wieschebrink (2010) los atacó.
• Reed-Muller: Minder y Shokrollahi (2007) recuperaron la clave en tiempo subexponencial, y Chizhov y Borodin (2013) lo hicieron mucho más rápido: en tiempo polinómico cuando $\operatorname{mcd}(r,m-1)$ está acotado, para el código $\mathrm{RM}(r,m)$.
• Goppa «salvajes» sobre extensiones cuadráticas: Couvreur, Otmani y Tillich (2014).
• Variantes cuasicíclicas y cuasidiádicas (para acortar la clave): Faugère, Otmani, Perret y Tillich (2010) recuperaron la clave de la mayoría de los parámetros propuestos.

Los Goppa binarios del esquema original, no. Durante más de cuatro décadas no apareció contra ellos un ataque estructural mejor que la decodificación genérica. Eso no quiere decir que los parámetros de 1978 sigan valiendo: Bernstein, Lange y Peters (2008) los rompieron precisamente por decodificación genérica, y por eso hoy se usan códigos mucho más largos. Con matices que la historia exige: hay subclases débiles dentro de los Goppa binarios (polinomio generador binario, Loidreau-Sendrier 2001; tasa muy alta) y quedan fuera de este relato BIKE (códigos MDPC cuasicíclicos, sin estructura algebraica que recuperar) y HQC, que no esconde un código decodificable y por tanto no es McEliece en sentido estricto.

Classic McEliece. Es la propuesta de McEliece con Goppa binarios que se presentó al NIST (su especificación es del equipo de Classic McEliece). En marzo de 2025, el informe IR 8545 del NIST lo dejó fuera del proceso actual (se seleccionó HQC) y dijo que el progreso reciente en criptoanálisis «socava algo» el argumento de tratarlo como una opción especialmente conservadora. El motivo principal que da el informe es la duda sobre su adopción, no la seguridad. En junio de 2026, ISO publicó la enmienda ISO/IEC 18033-2:2006/Amd 2:2026 que lo incluye.

2025-2026: por qué ahora se estrecha el margen. Hasta entonces, lo más serio contra un Goppa binario era un distinguidor de 2011 (Faugère, Gauthier-Umaña, Otmani, Perret y Tillich) que solo valía para códigos de tasa muy alta (el régimen de las firmas CFS), no para los parámetros de Classic McEliece. Cambió con:

• El distinguidor por sicigias de Hugues Randriambololona (EUROCRYPT 2025, mejor artículo, compartido con otro): es heurístico y subexponencial, el primero que baja de la barrera exponencial en el régimen de Classic McEliece, aunque para mceliece348864 estima unas $2^{401}$ operaciones, «inalcanzable en la práctica» según el propio autor.
• GIJS (agosto de 2026): Ghoshal, Ishai, Jain y Sun publican un distinguidor cuasipolinómico demostrado (tiempo $n^{O(\log n)}$ en un régimen asintótico concreto). Para los cinco conjuntos reales, sus autores estiman entre $2^{114}$ y $2^{124}$ operaciones de bit; lo llaman mejora «aunque aún no práctica».
• Recuperación de clave heurística: el propio GIJS, y después Weis, Vedenev y Saarinen, dan estimaciones de recuperar la clave que dependen de conjeturas declaradas y probadas solo en tamaños de juguete. Van desde unos $2^{90}$ hasta unos $2^{149}$ operaciones de bit según el trabajo, la versión y el conjunto de parámetros. Todas quedan por debajo del nivel declarado ($2^{143}$, $2^{207}$ y $2^{272}$ operaciones para las categorías 1, 3 y 5) en el modelo de operaciones de bit, que no cobra el acceso a memoria. Si se cobra como hace la guía de seguridad de Classic McEliece, Weis estima en el resumen de su versión de octubre entre $2^{117}$ y $2^{128}$: las cifras suben, pero siguen por debajo del nivel declarado y de la decodificación genérica, aunque con menos diferencia.

Lo que no ha pasado: nadie ha recuperado una clave ni descifrado un mensaje con parámetros reales. Lo más grande que se ha resuelto son retos de juguete del TII (con $m=8$ y $n$ alrededor de 220). El equipo de Classic McEliece contestó el 21 de agosto, antes de la versión de GIJS que añade la recuperación de clave (27 de agosto), que el ataque de GIJS es más lento que los ataques estándar para todos los conjuntos y que el algoritmo «solo detecta» si una cadena es una clave pública; no se encontraron declaraciones oficiales posteriores a esa fecha sobre los demás trabajos (la búsqueda llegó hasta el 5 de octubre). Varios trabajos de 2026 declaran haber usado modelos de IA, y el BSI avisa de que los trabajos recientes no tienen revisión por pares y de que falta comprobar el coste del acceso a memoria.

Las instituciones. El BSI alemán publicó el 1 de octubre de 2026 una nota fechada el 29 de septiembre: Classic McEliece no debería usarse en desarrollos nuevos, y recomienda FrodoKEM, ML-KEM o HQC (este cuando haya estándar). Dice a la vez que los trabajos recientes no permiten un ataque práctico con los parámetros de su guía TR-02102-1, mantiene el uso híbrido ya existente y revisará la guía a principios de 2027.

Una tesis

Resumiendo la historia: de todas las familias de códigos algebraicos propuestas para McEliece, solo los Goppa binarios genéricos de tasa moderada han resistido cuatro décadas; casi todas las demás cayeron. Con tres correcciones necesarias. Primera: dentro de los Goppa binarios hay subclases débiles (polinomio generador binario, tasa muy alta), y fuera de los códigos algebraicos sigue en pie BIKE. Segunda: «han resistido» significa que no había ataque estructural mejor que la decodificación genérica con los parámetros reales. Tercera: desde 2025 y 2026 eso ya no es cierto en el plano teórico, porque hay un distinguidor demostrado más barato que la decodificación genérica y recuperaciones de clave heurísticas que, según sus estimaciones en el modelo de operaciones de bit, también lo serían. Tienen todavía seguridad práctica, pero dejaron de ser una opción sin grietas.

Un ejemplo pequeño

Un ejemplo de juguete, con el código de Hamming $[7,4]$, que corrige un error ($t=1$). No es un código de Goppa real y se rompe a mano, pero muestra la mecánica. Las cuentas están verificadas con Python (mod 2).

Matriz generatriz del código secreto $G=(I_4\mid A)$ (su matriz de paridad es $H=(A^{\mathsf T}\mid I_3)$, con columnas $(1,1,0)$, $(1,0,1)$, $(0,1,1)$, $(1,1,1)$, $(1,0,0)$, $(0,1,0)$, $(0,0,1)$):

$$G=\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\end{pmatrix}$$

La clave secreta incluye una matriz invertible $S$ de $4\times4$ y una permutación $P$ de las 7 columnas:

$$S=\begin{pmatrix}1&1&0&1\\0&1&1&0\\0&0&1&1\\1&0&0&1\end{pmatrix},$$

y $P$ manda la columna 1 a la posición 4, la 2 a la 1, la 3 a la 7, la 4 a la 3, la 5 a la 6, la 6 a la 2 y la 7 a la 5. La clave pública es $G'=SGP$:

$$G'=\begin{pmatrix}1&0&1&1&0&1&0\\1&1&0&0&0&1&1\\0&0&1&0&0&1&1\\0&0&1&1&1&0&0\end{pmatrix}$$

Bob cifra $m=(1,0,1,1)$ con un error en la posición 5, $e=(0,0,0,0,1,0,0)$:

$$c=mG'+e=(1,0,1,0,0,0,1).$$

Alicia deshace la permutación: $cP^{-1}=(0,1,1,1,0,0,0)$, que es $mSG$ con el error movido de sitio. El síndrome es $(0,0,1)$, igual que la columna 7 de $H$, así que el error está en la coordenada 7. Corrige y obtiene $(0,1,1,1,0,0,1)$. Sus cuatro primeras coordenadas son $mS=(0,1,1,1)$, y al multiplicar por $S^{-1}$ aparece $m=(1,0,1,1)$.

¿Por qué esto es de juguete? Porque con solo 16 mensajes y 7 posiciones de error posibles, Eva prueba los $16\times7$ casos y encuentra el único que cuadra. Con parámetros reales ($n$ de miles, $t$ de decenas o centenares) eso es imposible. El curso de códigos correctores explica la decodificación por síndrome que se usa aquí.

Las matemáticas de verdad

El código de Goppa

Sea $F=\mathbb F_{2^m}$. Se escogen $L=(\alpha_1,\dots,\alpha_n)$, elementos distintos de $F$ (el soporte), y un polinomio $g\in F[x]$ de grado $t$, mónico, irreducible y por tanto sin raíces en $L$. El código de Goppa binario es

$$\Gamma(L,g)=\Bigl\{c\in\mathbb F_2^{\,n}\;:\;\sum_{i=1}^{n}\frac{c_i}{x-\alpha_i}\equiv 0 \pmod{g(x)}\Bigr\}.$$

Su matriz de control sobre $F$ es

$$H=\Bigl(\frac{\alpha_j^{\,i}}{g(\alpha_j)}\Bigr)_{0\le i<t,\;1\le j\le n}.$$

Escribiendo cada entrada de $F$ como $m$ bits sale una matriz binaria de $mt$ filas, de modo que la dimensión es $k\ge n-mt$. Como $g$ es irreducible, no tiene factores repetidos (es libre de cuadrados), y para un Goppa binario eso basta: la distancia mínima es al menos $2t+1$ y el algoritmo de Patterson (1975) corrige hasta $t$ errores en tiempo razonable usando $g$ y $L$.

El esquema

Con $G$ generatriz de $\Gamma(L,g)$, $S$ invertible $k\times k$ y $P$ matriz de permutación $n\times n$, la clave pública es $G'=SGP$ y la secreta $(L,g,S,P)$. Para cifrar $m\in\mathbb F_2^k$ se elige $e$ de peso $t$:

$$c=mG'+e.$$

Para descifrar:

$$cP^{-1}=(mS)G+eP^{-1},$$

y como $eP^{-1}$ también tiene peso $t$, Patterson devuelve la palabra $(mS)G$; de ella se lee $mS$ (si $G$ es sistemática, son sus $k$ primeras coordenadas) y se multiplica por $S^{-1}$. (Classic McEliece usa la forma equivalente de Niederreiter: la clave pública es $T$, con $H=(I_{mt}\mid T)$, y el texto cifrado es el síndrome $C=He$ de un vector $e$ de peso $t$.)

Goppa dentro de Reed-Solomon, y por qué importa

Un código de Reed-Solomon generalizado (GRS) de dimensión $r$ sobre $F$ es el conjunto de vectores $(v_1f(\alpha_1),\dots,v_nf(\alpha_n))$ con $f\in F[x]$ de grado menor que $r$ y $v_i\ne0$. Todo código de Goppa binario $\Gamma(L,g)$ es el subcódigo sobre el subcuerpo $\mathbb F_2$ de un GRS de dimensión $n-t$: los vectores binarios de ese GRS (por eso se dice que es un código alternante). Cuando $g$ no tiene factores repetidos (y $2t<n$), además $\Gamma(L,g)=\Gamma(L,g^2)$, así que queda contenido en un GRS más pequeño, de dimensión $n-2t$. Es una propiedad conocida del código, no un defecto del esquema, pero tiene dos consecuencias.

1. Por qué cayeron las variantes. Los GRS tienen una estructura muy rígida y Sidelnikov y Shestakov (1992) la usaron para recuperar la clave. Las variantes que conservaban o añadían estructura (subcódigos de GRS, Goppa sobre extensiones cuadráticas, versiones cuasicíclicas y cuasidiádicas) cayeron una tras otra. Que la causa común sea haber dejado demasiada estructura a la vista es la lectura que sugiere la historia, no un teorema. En los Goppa binarios de tasa moderada, pasar al subcuerpo $\mathbb F_2$ esconde bien esa estructura, o lo hacía.
2. Por qué el distinguidor ataca justo ahí. La prueba del distinguidor de GIJS usa exactamente esa contención: un Goppa binario con $g$ libre de cuadrados está en un GRS de dimensión $n-2t$, y al componer con una curva oculta se obtiene un polinomio de una variable, de grado acotado, con $n-1$ ceros de multiplicidad $s$; por interpolación de Hermite ese polinomio es cero, y por eso un cierto núcleo se anula siempre en una columna reservada. Con una matriz uniforme, el test lo acepta con probabilidad como mucho $1-2^{-d}$, de modo que distingue. El régimen en que es cuasipolinómico ($m$ del orden de $\log n$, $t$ del orden de $n/\log n$) no es el de los parámetros reales, donde se usan $d=8$ y $s=7$ fijos tras acortar el código, con una estimación de $2^{114}$ a $2^{124}$ operaciones de bit.

La contención dice que el código es «casi» un GRS. Los esquemas con Goppa funcionan porque pasar a $\mathbb F_2$ esconde casi toda esa estructura. Los ataques de 2025 y 2026 miden cuánta queda.

Y ahora, ¿qué?

Si quieres ver los ingredientes, el curso de códigos correctores llega a Reed-Solomon y a la decodificación por síndrome. Para el lado cuántico, ¿Puede un ordenador cuántico romper RSA hoy? cuenta qué haría falta para romper RSA con Shor. Cuánto margen queda a McEliece se verá cuando salgan las revisiones por pares y la reevaluación del BSI, prevista para principios de 2027.

Fuentes

• R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, DSN Progress Report 42-44, JPL, 1978.
• E. R. Berlekamp, R. J. McEliece y H. C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory 24(3), 1978.
• D. J. Bernstein, T. Lange y C. Peters, Attacking and Defending the McEliece Cryptosystem, PQCrypto 2008 (ePrint 2008/318).
• N. J. Patterson, The algebraic decoding of Goppa codes, IEEE Trans. Inform. Theory 21(2), 1975.
• V. M. Sidelnikov y S. O. Shestakov, On insecurity of cryptosystems based on generalized Reed-Solomon codes, 1992.
• L. Minder y A. Shokrollahi, Cryptanalysis of the Sidelnikov Cryptosystem, EUROCRYPT 2007; I. V. Chizhov y M. A. Borodin, The failure of McEliece PKC based on Reed-Muller codes, ePrint 2013/287.
• J.-C. Faugère, A. Otmani, L. Perret y J.-P. Tillich, Algebraic cryptanalysis of McEliece variants with compact keys, EUROCRYPT 2010.
• A. Couvreur, A. Otmani y J.-P. Tillich, Polynomial time attack on wild McEliece over quadratic extensions, IEEE Trans. Inform. Theory 63(1), 2017.
• P. Loidreau y N. Sendrier, Weak keys in the McEliece public-key cryptosystem, IEEE Trans. Inform. Theory 47(3), 2001.
• J.-C. Faugère, V. Gauthier-Umaña, A. Otmani, L. Perret y J.-P. Tillich, A Distinguisher for High-Rate McEliece Cryptosystems, IEEE Trans. Inform. Theory 59(10), 2013 (versión previa en ITW 2011).
• H. Randriambololona, The syzygy distinguisher, EUROCRYPT 2025.
• A. Ghoshal, Y. Ishai, A. Jain y N. Sun, Quasipolynomial Cryptanalysis of the McEliece Cryptosystem, ePrint 2026/1630, versión del 27/08/2026.
• S. A. Weis, Improving GIJS Key Recovery for Classic McEliece, ePrint 2026/1984; M.-J. O. Saarinen, Bit Operation Cost of “Holdout” Key-Recovery Attacks Against Classic McEliece, ePrint 2026/1786; K. Vedenev, Extending Distinguishing to Key Recovery for Subfield Subcodes of GRS codes, ePrint 2026/1747; Hemmert y Wiemers, ePrint 2025/1661; Briaud, Lemoine, Randriambololona y Tillich, ePrint 2026/1232.
• Equipo de Classic McEliece, especificación, 23 de octubre de 2022. De aquí salen los conjuntos de parámetros y los tamaños.
• BSI, Notes on Classic McEliece (29/09/2026) y nota de prensa (01/10/2026).
• ISO, ISO/IEC 18033-2:2006/Amd 2:2026.
• NIST, IR 8545, marzo de 2025.
• P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, 1997; L. K. Grover, A fast quantum mechanical algorithm for database search, 1996; D. J. Bernstein, Grover vs. McEliece, PQCrypto 2010.
• Cálculos propios con Python (ejemplo de juguete y tamaños de clave), en el repositorio de la web.