La criptografía y el álgebra lineal

Desde que la humanidad inventó el lenguaje escrito, ha tratado de compartir información de manera secreta. Este es, básicamente, el objetivo de la criptografía, el estudio de las técnicas para proteger las comunicaciones sensibles por medio de encriptación de datos y su posterior descifrado. El cifrado es la transformación de los datos en una forma ilegible, de manera que, incluso aquellos que puedan ver los datos cifrados, no puedan entender la información oculta. El descifrado es el proceso inverso; es la transformación de los datos cifrados de nuevo en una forma comprensible.

Hay algunos conceptos básicos relativos a la criptografía.

- Cifrado: El procedimiento que generará un mensaje ininteligible para el receptor. También se usa para recrear el mensaje original, según el mecanismo de cifrado que se utilice.

- Texto Plano: El mensaje o información que se va a codificar.

- Texto cifrado: El mensaje o información que se obtiene después que se ha utilizado el Cifrado.

Aunque existen diferentes métodos para cifrar y descifrar mensajes, nos centraremos en un sistema de cifrado basado en el álgebra lineal, el sistema de cifrado Hill, que utiliza una matriz como un sistema de cifrado para codificar un mensaje, y es extremadamente difícil de romper cuando se utiliza una matriz de gran tamaño. El receptor decodifica el mensaje utilizando la inversa de la matriz. La primera matriz se llama la matriz de codificación y su inversa se llama la matriz de decodificación.

¿Cómo funciona este método?

Supongamos que tenemos una matriz invertible A (la matriz de codificación) y un texto que queremos cifrar.

Transformamos el texto a una secuencia de números, dando a cada carácter un valor numérico único; a continuación, formamos una matriz mediante la agrupación de los números en columnas de acuerdo al orden de la matriz A (la cantidad de elementos en cada columna debe ser igual al orden de la matriz). Llamemos a esta matriz B (la matriz plana). Multipliquemos la matriz A por la matriz B:

C = A•B

La matriz C es la matriz cifrada.

Para descifrar el mensaje, sólo debe multiplicarse Inv(A)•C, donde Inv(A) es la matriz inversa de A.

Nótese que:

Inv(A)•C = Inv(A)•A•B = I•B = B

El texto plano original se puede hallar nuevamente tomando la matriz resultante y uniendo sus vectores columna, de manera que formen una secuencia, para luego convertir los números en los caracteres respectivos.

En muchos artículos, los autores utilizan solamente las 26 letras del alfabeto Inglés, a veces 29 si se incluye el espacio, el signo de interrogación y el punto. En estos casos una sencilla asignación de las letras y símbolos adicionales a los primeros números enteros, y el uso de la aritmética modular, permite con el uso de este método, obtener un mensaje cifrado compuesto por los mismos números enteros, que se pueden asignar nuevamente a sus correspondientes letras y símbolos.

En este post no vamos a hacer ninguna consideración sobre cuales letras o símbolos se pueden utilizar, de esta manera cualquier texto, sin importar idiomas o símbolos, se pueden cifrar utilizando este método. Para transformar caracteres en números, vamos a utilizar el valor Unicode del carácter.

La matriz cifrada C, se puede mostrar como una secuencia de números, uniendo sus vectores columna, de la misma manera que hay que hacer para obtener el texto plano original; pero no se pueden convertir los números a letras utilizando el método anterior, debido a que los números resultantes pueden oscilar en un conjunto numérico más amplio. Si lo prefiere, se puede transformar en un texto asociando los dígitos, el signo de menos y el separador de listas a diferentes caracteres. Es este ejemplo utilizamos sencillas funciones de mapeo para hacer eso.

Ejemplo

Veamos un ejemplo:

Usaremos el siguiente mensaje

La contraseña es: NCS-2014

En primer lugar, hay que asignar a cada letra un equivalente numérico. Como se indica más arriba, vamos a utilizar el valor Unicode de cada carácter. Para el mensaje a cifrar, se obtiene la siguiente secuencia de números:

76 97 32 99 111 110 116 114 97 115 101 241 97 32 101 115 58 32 78 67 83 45 50 48 49 52

Matriz de codificación

Elegimos la siguiente matriz invertible A de orden 4:

    ┌               ┐
    │  1  -1  -1  1 │
    │  2  -3  -5  4 │
A = │ -2  -1  -2  2 │
    │  3  -3  -1  2 │
    └               ┘

Cifrando el mensaje

Convertimos la secuencia de números asociada al texto plano en una matriz, dividiéndola en vectores columna de 4 elementos (el orden de la matriz de codificación). Rellenamos la última columna con ceros para completar los 4 elementos.

    ┌                               ┐
    │ 76  111   97   97  58  83  49 │
    │ 97  110  115   32  32  45  52 │
B = │ 32  116  101  101  78  50   0 │
    │ 99  114  241  115  67  48   0 │
    └                               ┘

Ahora codificamos el mensaje multiplicando la matriz de codificación A por la matriz de arriba B. El resultado es la matriz cifrada C:

          ┌                                         ┐
          │   46    -1  122    79    15    36    -3 │
          │   97  -232  308    53  -102   -27   -58 │
C = A•B = │ -115  -336  -29  -198  -170  -215  -150 │
          │  103   115  327   324   134   160    -9 │
          └                                         ┘

Las columnas de esta matriz proporcionan el mensaje codificado. El mensaje puede ser transmitido de la siguiente forma lineal:

46 -1 122 79 15 36 -3 97 -232 308 53 -102 -27 -58 -115 -336 -29 -198 -170 -215 -150 103 115 327 324 134 160 -9

Descifrando el mensaje

Para descifrar el mensaje, escriba la secuencia de números que ha recibido como una matriz, disponiendo los números como vectores columna de 4 elementos. La matriz resultante de este proceso será igual a la matriz cifrada C. Debe conocer la inversa de la matriz de codificación:

         ┌               ┐
         │  6  -1  0  -1 │
         │ 22  -4  1  -4 │
Inv(A) = │ 14  -3  1  -2 │
         │ 31  -6  2  -5 │
         └               ┘

Multiplique esa matriz (matriz de decodificación) por la matriz cifrada C. Utilizando la matriz resultante (que va a ser igual a la matriz B), forme nuevamente una secuencia continua de números y mapee dichos números a los respectivos caracteres, para obtener el mensaje original.

Ejemplo demostrativo en JavaScript

Hemos desarrollado todos los algoritmos de cifrado y descifrado, utilizando las matrices de codificación y decodificación seleccionadas en el ejemplo anterior, donde se puede cifrar el texto que desee. Hemos incluido también una casilla para especificar si desea ver el texto cifrado como una secuencia de números o como una secuencia de caracteres (mapear los números a caracteres).

Códigos en JavaScript

<script type="text/javascript">

  var encodingMatrix = [[1,-1,-1,1],[2,-3,-5,4],[-2,-1,-2,2],[3, -3,-1,2]];
  var decodingMatrix = [[6,-1,0,-1],[22,-4,1,-4],[14,-3,1,-2],[31,-6,2,-5]];

  function getMatrixFromArray(arr, rows){
    var matrix = new Array();
    for (var i=0; i<rows; i++)
      matrix[i] = new Array();

    for (var i=0; i<arr.length; i++)
      matrix[i % rows][Math.floor(i/rows)] = arr[i];

    if (arr.length % rows != 0)
      for (var i=arr.length % rows; i<rows; i++)
        matrix[i][Math.floor((arr.length - 1)/rows)] = 0;

    return matrix;
  }

  function getMatrixFromText(text, rows){
    var arr = new Array();
    for (var i=0; i<text.length; i++)
      arr[i] = text.charCodeAt(i);
    return getMatrixFromArray(arr, rows);
  }

  function getTextFromMatrix(matrix){
    var text = new String();
    for (var j=0; j<matrix[0].length; j++)
      for (var i=0; i<matrix.length; i++)
        text += matrix[i][j]>0 ? String.fromCharCode(matrix[i][j]) : "";
    return text;
  }

  function getMatrixFromNumbers(text, rows){
    var i = 0;
    var numbers = text.split(" ");
    while (i<numbers.length){
      if (numbers[i].replace(/s+/g, "") == "")
        numbers.splice(i, 1);
      else i++;
    }
    var arr = new Array();
    for (var i=0; i<numbers.length; i++)
      arr[i] = parseInt(numbers[i]);

    return getMatrixFromArray(arr, rows);
  }

  function getNumbersFromMatrix(matrix){
    var text = "";
    for (var j=0; j<matrix[0].length; j++)
      for (var i=0; i<matrix.length; i++)
        text += matrix[i][j].toString() + " ";
    return text;
  }

  function multiplyMatrices(m1, m2){
    var matrix = new Array();
    for (var i=0; i<m1.length; i++)
      matrix[i] = new Array();

    for (var i=0; i<m1.length; i++)
      for (var j=0; j<m2[0].length; j++){
        matrix[i][j] = 0;
        for (var k=0; k<m1[0].length; k++)
          matrix[i][j] += m1[i][k]*m2[k][j];
      }
    return matrix;
  }

  function numberToChar(text){
    var result = new String();
    for (var i=0; i<text.length; i++)
      result += String.fromCharCode(text.charCodeAt(i) + (text.charCodeAt(i)==32 ? 33 : 21));
    return result;
  }

  function charToNumber(text){
    var result = new String();
    for (var i=0; i<text.length; i++)
      result += String.fromCharCode(text.charCodeAt(i)-(text.charCodeAt(i)==65 ? 33 : 21));
    return result;
  }

  function encryptText(){
    var plainText = document.getElementById("plainText").value;
    var plainMatrix = getMatrixFromText(plainText, 4);
    var cipherMatrix = multiplyMatrices(encodingMatrix,plainMatrix);
    var cipherText = getNumbersFromMatrix(cipherMatrix);
    if (document.getElementById("mapNumbers").checked)
      cipherText = numberToChar(cipherText);
    document.getElementById("cypherText").value = cipherText;
  }

  function decryptText(){
    var cipherText = document.getElementById("cypherText").value;
    if (document.getElementById("mapNumbers").checked)
    var cipherText = charToNumber(cipherText);
    var cipherMatrix = getMatrixFromNumbers(cipherText, 4);
    var plainMatrix = multiplyMatrices(decodingMatrix,cipherMatrix)
    document.getElementById("decryptedText").value = getTextFromMatrix(plainMatrix);
  }

  window.onload = function(){
    document.getElementById("encrypt").onclick = encryptText;
    document.getElementById("decrypt").onclick = decryptText;
  };
</script>

Códigos en C#

A continuación una implementación de una clase en C# para utilizar este método criptográfico. Note que se precisan de ambas matrices, la matriz de codificación y decodificación. Aunque la matriz de decodificación puede obtenerse a partir de la matriz de codificación, simplemente hallando su inversa, no es objetivo implementar la inversa de una matriz, por tal motivo es necesario instanciar la clase con ambas matrices. En algunos de los métodos pudo utilizarse Linq y obtener una solución más sencilla, pero no se usó para mantener la mayor similitud con el código implementedo en JavaScript.

using System.Collections.Generic;
using System.Text;

public class HillCipher
{
    public HillCipher(int[,] encodingMatrix, int[,] decodingMatrix, bool mapNumbers = true)
    {
        this.EncodingMatrix = encodingMatrix;
        this.DecodingMatrix = decodingMatrix;
        this.MapNumbers = mapNumbers;
    }

    private int[,] EncodingMatrix { get; set; }
    private int[,] DecodingMatrix { get; set; }
    private bool MapNumbers { get; set; }

    public string EncryptText(string plainText)
    {
        var plainMatrix = this.GetMatrixFromText(plainText);
        var cipherMatrix = MultiplyMatrices(this.EncodingMatrix, plainMatrix);
        var cipherText = GetNumbersFromMatrix(cipherMatrix);
        if (this.MapNumbers)
          cipherText = NumberToChar(cipherText);

        return cipherText;
    }

    public string DecryptText(string cipherText)
    {
        if (this.MapNumbers)
           cipherText = CharToNumber(cipherText);

        var cipherMatrix = this.GetMatrixFromNumbers(cipherText);
        var plainMatrix = MultiplyMatrices(this.DecodingMatrix, cipherMatrix);
        return GetTextFromMatrix(plainMatrix);
    }

    private static string GetTextFromMatrix(int[,] matrix)
    {
        var text = new StringBuilder();
        for (var j = 0; j < matrix.GetLength(1); j++)
            for (var i = 0; i < matrix.GetLength(0); i++)
                text.Append(matrix[i, j] > 0 ? ((char)matrix[i, j]).ToString() : string.Empty);

        return text.ToString();
    }

    private static string GetNumbersFromMatrix(int[,] matrix)
    {
        var text = new StringBuilder();
        for (var j = 0; j < matrix.GetLength(1); j++)
            for (var i = 0; i < matrix.GetLength(0); i++)
                text.Append(matrix[i, j].ToString("0") + " ");

        return text.ToString();
    }

    private static int[,] MultiplyMatrices(int[,] m1, int[,] m2)
    {
        var rows = m1.GetLength(0);
        var columns = m2.GetLength(1);
        var matrix = new int[rows, columns];

        for (var i = 0; i < rows; i++)
            for (var j = 0; j < columns; j++)
                for (var k = 0; k < m1.GetLength(1); k++)
                    matrix[i, j] += m1[i, k] * m2[k, j];

        return matrix;
    }

    private static string NumberToChar(string text)
    {
        var result = new StringBuilder();
        foreach (var t in text)
           result.Append((char)(t + ((int)t == 32 ? 33 : 21)));

        return result.ToString();
    }

    private static string CharToNumber(string text)
    {
        var result = new StringBuilder();
        foreach (var t in text)
            result.Append((char)(t - ((int)t == 65 ? 33 : 21)));
        return result.ToString();
    }

    private int[,] GetMatrixFromArray(IList arr)
    {
        var rows = this.EncodingMatrix.GetLength(0);
        var columns = arr.Count % rows == 0 ? arr.Count / rows : (arr.Count / rows) + 1;
        var matrix = new int[rows, columns];

        for (var i = 0; i < arr.Count; i++)
            matrix[i % rows, i / rows] = arr[i];

        if (arr.Count % rows != 0)
            for (var i = arr.Count % rows; i < rows; i++)
                matrix[i, (arr.Count - 1) / rows] = 0;

        return matrix;
    }

    private int[,] GetMatrixFromText(string text)
    {
        var arr = new int[text.Length];
        for (var i = 0; i < text.Length; i++)
            arr[i] = text[i];

        return this.GetMatrixFromArray(arr);
    }

    private int[,] GetMatrixFromNumbers(string text)
    {
        var numbers = text.Split(' ');
        var arr = new List();
        foreach (var t in numbers)
          if (!string.IsNullOrWhiteSpace(t))
              arr.Add(int.Parse(t));
        return this.GetMatrixFromArray(arr);
    }
}

Un ejemplo de cómo utilizar esta clase.

public void TestHillCipher()
{
    var encodingMatrix = new[,] { { 1, -1, -1, 1 }, { 2, -3, -5, 4 }, { -2, -1, -2, 2 }, { 3, -3, -1, 2 } };
    var decodingMatrix = new[,] { { 6, -1, 0, -1 }, { 22, -4, 1, -4 }, { 14, -3, 1, -2 }, { 31, -6, 2, -5 } };
    var hillCipher = new HillCipher(encodingMatrix, decodingMatrix, true);
    const string PlainText = "Lorem ipsum dolor sit amet, quis phasellus diam, nunc duis. Odio magna amet wisi duis sit iaculis, ac sodales dolores pellentesque orci vestibulum, nulla et quis id iaculis lorem, vestibulum massa sociis in, mauris ac vestibulum sociis hendrerit eros a. Mauris varius molestie in sem mi, id mattis purus, dolor vitae euismod nisl mauris nulla varius, ut libero sem, quam velit vestibulum quam.";
    var cipherText = hillCipher.EncryptText(PlainText);
    Console.WriteLine(cipherText);
    var decryptedText = hillCipher.DecryptText(cipherText);
    Console.WriteLine(decryptedText);
}