¿Cómo se usa el álgebra lineal en criptografía?

Voy a ampliar mi respuesta para centrarme en la criptología como un todo dado que el lineal tiene grandes aplicaciones en ambos lados del cifrado.

En criptografía (escritura de códigos) usamos lineal en varios sistemas criptográficos geométricos. Por ejemplo, algunos tipos de criptografía de curva elíptica (ECC) incorporan una serie de transformaciones matriciales como parte del descifrado y el cifrado.

En el criptoanálisis (descifrar matemáticamente los códigos) utilizamos sistemas lineales para resolver ecuaciones relacionadas tanto con la gramática como con el lenguaje en texto cifrado y la correspondiente incidencia / probabilidad de dicho lenguaje dado nuestro conocimiento de ese criptosistema.

Este es en realidad un campo completo de criptoanálisis llamado criptoanálisis lineal , llamado así por su uso de álgebra lineal.

Estoy seguro de que también usarías lineal de alguna otra manera. Por ejemplo, me imagino que usa lineal para probar algunas cosas sobre el tamaño del conjunto de claves potenciales o la probabilidad de que el bruto fuerce algún texto cifrado.

Podría dar cualquier número de ejemplos específicos, por ejemplo:

Las curvas elípticas se usan en criptografía. Puede mostrar que una curva elíptica es isomorfa a un cociente del plano complejo por alguna red en el plano complejo. La forma más fácil de codificar una red bidimensional es proporcionar un par de generadores para la red y, en última instancia, esto nos permitirá parametrizar todas las curvas elípticas, pero, por supuesto, puede especificar la misma red con diferentes pares de generadores. Entonces, necesitamos usar álgebra lineal para entender cuándo son lo mismo.

Sin embargo, cualquier ejemplo particular que pueda dar sería engañoso. El punto es que la criptografía es algo que entiendes con las matemáticas, y el álgebra lineal es la herramienta básica que usamos para hacer esencialmente todas las matemáticas. Se utiliza en múltiples formas totalmente no relacionadas para resolver básicamente cualquier problema matemático no trivial.

El cifrado Hill es (diría) el primer criptosistema matemático, en el sentido de que fue la primera vez que un criptosistema se basó en principios matemáticos (multiplicación de matrices):

Es criptográficamente débil; sin embargo, cuando se combina con otros sistemas, puede producir un cifrado fuerte y práctico desde el punto de vista computacional.