\begin{matrix}c \\ ◯ \end{matrix} Revista de Matemática: Teoría y Aplicaciones 2019 26(2) : 281–297 cimpa – ucr issn: 1409-2433 (Print), 2215-3373 (Online)

doi: https:// doi. org/ 10.15517/ rmta. v26i2. 38319

un nuevo enfoque a la criptografía

matemática usando la función discreta de ambigüedad

a new approach to mathematical cryptography using the discrete ambiguity function

Juan Pablo Soto–Quirós^{∗}  Domingo Rodríguez^{†}

Received: 23/Feb/2012; Revised: 7/Jun/2019; Accepted: 7/Jun/2019

∗Instituto Tecnológico de Costa Rica, Escuela de Matemáticas, Cartago, Costa Rica. E-Mail: jusoto@tec.ac.cr .

†Universidad de Puerto Rico en Mayagüez, Departamento de Ingeniería Eléctrica y Computadoras, Mayagüez, PR, 00681, USA. E-Mail: domingo@ece.uprm.edu

282 j.p. soto quirós — d. rodríguez

Resumen

A través de la criptografía, se desea modificar y ocultar cierta información, para que sólo algún grupo determinado de personas pueda interpretarlo por medio de una clave. Al tratar de utilizar diversos campos de la matemática para realizar este proceso, se desarrolla el concepto de criptografía matemática.

La mayoría de métodos criptográficos matemáticos se concentran en teoría de números. También exiten otros métodos criptográficos en el área de física cuántica y geometría algebraica, particularmente elíptica y curvas hyperelípticas definidas sobre cuerpos y campos finitos, finito campos, entre otros. El presente trabajo introduce una nueva modalidad del aspecto de procesamiento de señales al campo de la criptografía matemática, a través de representaciones armónicas bidimensionales como lo es la función discreta de ambigüedad. Este trabajo utiliza dos definiciones equivalentes, en módulo, de la función discreta de ambigüedad.

Este nuevo método criptográfico utiliza el concepto de clave simétrica para efectuar el proceso de cifrar y descifrar el mensaje.

Palabras clave: función discreta de ambigüedad; criptografía; claves simétricas; transformada discreta de Fourier.

Abstract

Through cryptography, be modified and hide certain information, so that only a certain group of people can interpret it through a key. When trying to use various fields of mathematics for this process, the concept of mathematical cryptography is developed.

Most mathematical cryptographic methods focus on number theory. Also, there are other cryptographic methods in the area of quantum physics and algebraic geometry, particularly hyperelliptical curves defined over finite bodies and finite fields. This paper introduces a new method of mathematical cryptography with signal processing techniques, through of a dimensional harmonic representations such as the discrete ambiguity function. This paper uses two equivalent definitions in module discrete ambiguity function.

This new cryptographic method uses the concept of symmetric key to making the process of encrypting and decrypting the message.

Keywords: discrete ambiguity function; cryptography; symmetric keys; discrete Fourier transform.

Mathematics Subject Classification: 94A60, 15A23.

un nuevo enfoque a la criptografía matemática usando … 283

1 Introducción

La palabra criptografía es un término genérico que describe todas las técnicas que permiten cifrar mensajes o hacerlos ininteligibles sin recurrir a una acción específica. La criptografía se basa en diferentes tipos de aritmética: números enteros y racionales, números complejos en campos finitos, aritmética modular, entre otros [12]. Por ejemplo, en el caso de un texto, consiste en transformar las letras que conforman el mensaje en una serie de números y luego realizar cálculos con estos números para modificarlos y hacerlos incomprensibles; además de asegurarse de que el receptor pueda descifrar tal modificación. El proceso de codificar un mensaje para que sea secreto se llama cifrado. El método inverso, que consiste en recuperar el mensaje original, se llama descifrado.

El concepto de criptografía matemática se refiere a las técnicas criptográficas que utilizan los conceptos matemáticos para su desarrollo. La criptografía matemática se basa en muchas áreas de las matemáticas, incluyendo la teoría de números, geometría algebraica, álgebra abstracta, probabilidad, estadística y teoría de la información [10].

Normalmente, el proceso de cifrar se realiza mediante una clave, denominada clave para cifrar y el proceso de descifrar requiere una clave para obtener el mensaje original; dicha clave se denomina clave para descifrar. Los métodos criptográficos para descifrar dichas claves se dividen en dos tipos:

• Simétricas: una misma clave es utilizada para cifrar y descifrar.

• Asimétricas: la clave utilizada para cifrar es diferente a la que se utiliza para descifrar.

La mayoría de métodos criptográficos matemáticos se concentran en la teoría de números. Además, otros métodos criptográficos han sido desarrollados en el área de física cuántica y geometría algebraica, particularmente elíptica y curvas hyperelípticas definidas sobre cuerpos y campos finitos, finito campos. El presente trabajo introduce una nueva modalidad del aspecto de procesamiento de señales al campo de la criptografía matemática, a través de representaciones armónicas bidimensionales, utilizando el concepto de la función discreta de ambigüedad (FDA). Este trabajo utiliza dos definiciones equivalentes, en módulo, de la FDA:

A_{x,y}^{1}[m, k] = ∑_{n∈ℤ_{N}} x[n]\overline{y}[⟨n − m⟩_{N}]e^{−i \frac{2π}{N} nk},

y

A_{x,y}^{2}[m, k] = ∑_{n∈ℤ_{N}} x[⟨n + m⟩_{N}]\overline{y}[n]e^{−i \frac{2π}{N} nk},

las cuales se explican detalladamente en la Sección 2.

Dicho método criptográfico utiliza el concepto de clave simétrica para efectuar el proceso de cifrar y descifrar los mensajes, a través de la representación matricial de la FDA, llamada matriz FDA, utilizando una fila o una columna de tal matriz como el mensaje encriptado.

Con el fin de probar los teoremas propuestos en este trabajo, se utiliza la definición y algunos resultados sobre: los productos Kronecker y Hadamard de matrices [9, 11, 14, 18], la transformada discreta de Fourier y su representación matricial [5, 7, 11, 18], matrices circulantes [6] y operadores de permutación y su representación matricial [1, 7, 11]. En las referencias mencionadas, el lector puede consultar al respecto. Además, cabe mencionar que los teoremas y sus respectivas demostraciones son propuestos y desarrollados por los autores de este artículo.

Este artículo está organizado de la siguiente manera. En la Sección 2se introduce el concepto de función continua de ambigüedad y la FDA, la representación matricial de la FDA, conocida como matriz FDA, y su cómputo en paralelo. En la Sección 3 se explica el método criptográfico: el proceso para cifrar y descifrar un mensaje, utilizando la matriz FDA. En la Sección 4 se presentan las conclusiones del trabajo.

2 Función discreta de ambigüedad

En 1953, P.M. Woodward define función de ambigüedad, la cual trata de un mecanismo formulado para describir el efecto Doppler en los receptores de filtro apareados [19]. Woodward reconoció la influencia de la teoría de la comunicación de Shannon, a partir de 1948, en sus ideas, y explicó la importancia de la “ambigüedad” en el procesamiento de señales de radares, tal vez mejor concebido en términos de una forma del principio de incertidumbre. La función de ambigüedad juega un papel clave en el campo de procesamiento de señales de tiempo-frecuencia, ya que está relacionada con la distribución de Wigner-Ville, a través de la transformada de Fourier de dos dimensiones [4].

Definición 1 (Función de ambigüedad) Sean f, g ∈ L^{2}(ℝ), entonces la función de ambigüedad de f y g se define como el mapeo A_{f,g}^{1} : L^{2}(ℝ) × L^{2}(ℝ) → L^{2}(ℝ × ℝ) tal que

A_{f,g}^{1}(t, θ) = ∫_{ℝ} f(x)\overline{g}(x − t)e^{−2iπxθ}dx,  (1)

donde \overline{g} es el conjugado complejo de y.

A_{f,g}^{1} recibe el nombre de función de ambigüedad cruzada cuando f ≠ g. En el caso f = g se conoce simplemente como función de ambigüedad. Benedetto y Donatelli [2, 3] definen la función de ambigüedad con ligeras modificaciones a la definida en la ecuación (1):

A_{f,g}^{2}(t, θ) = ∫_{ℝ} f(x + t)\overline{g}(x)e^{−2iπxθ}dx.  (2)

A pesar de las diferencias, estas dos representaciones de la función de ambigüedad mantienen una relación a nivel de módulo: |A_{f,g}^{1}(t, θ)| = |A_{f,g}^{2}(t, θ)|. Por lo tanto, las ecuaciones (1) y (2) serán consideradas representaciones equivalentes de la función de ambigüedad. A nivel de implementación, la función de ambigüedad que desarrolló Woodward admite una representación con dominio discreto y finito.

Definición 2 Sea x, y ∈ ℂ^{N}. La función discreta de ambigüedad (FDA) de x, y se define como el mapeo A_{x,y}^{1} : ℂ^{N} × ℂ^{N} → ℂ^{N×N} tal que

A_{x,y}^{1}[m, k] = ∑_{n∈ℤ_{N}} x[n]\overline{y}[⟨m − n⟩_{N}]ω_{N}^{−nk},  (3)

donde ℂ^{N} × ℂ^{N} es el espacio de matrices de dimensión N × N, \overline{y} es el conjugado complejo de y, ⟨m − n⟩_{N} = m − n mod N y ω_{N} = e^{i \frac{2π}{N}}.

Benedetto y Donatelli [2, 3] también definen una representación con dominio discreto y finito de la ecuación (2):

A_{x,y}^{2}[m, k] = ∑_{n∈ℤ_{N}} x[⟨m + n⟩_{N}]\overline{y}[n]ω_{N}^{−nk}.  (4)

Las dos definiciones de FDA también son equivalentes a nivel de módulo; es decir, |A_{x,y}^{1}[m, k]| = |A_{x,y}^{2}[m, k]|. Al ser la FDA una función de dos dimensiones, entonces se puede expresar en notación matricial. Sea A_{x,y}^{1}, A_{x,y}^{2} ∈ ℂ^{N×N}, entonces la representación matricial de FDA de las ecuaciones (3) y (4) se define como (A_{x,y}^{1})_{m,k} =A_{x,y}^{1}[m, k] y (A_{x,y}^{2})_{m,k} =A_{x,y}^{2}[m, k]. El siguiente teorema explica un modo de expresar y computar la matriz FDA, la cual permite su cómputo en paralelo, al utilizar los productos Kronecker y Hadamard.

Teorema 1 Sea x, y ∈ ℂ^{N}. Entonces

A_{x,y}^{1} = R_{N,N}\{L_{N}^{N^{2}} [I_{N} ⊗ F_{N}] [(1_{N} ⊗ \overline{x}) ⊙ \overline{Y} ]\},  (5)
A_{x,y}^{2} = R_{N,N}\{L_{N}^{N^{2}} [I_{N} ⊗ F_{N}] [X ⊙ (1_{N} ⊗ \overline{y})]\},  (6)

donde R_{N,N} es el operador re-shape^{1}; ⊗ y ⊙ son los productos Kronecker y Hadamard de matrices, respectivamente; I_{N} ∈ ℂ^{N×N} es la matriz identidad de orden N; F_{N} ∈ ℂ^{N×N} es la matriz de la transformada discreta de Fourier de orden N; L_{N}^{N^{2}} ∈ ℂ^{N^{2}×N^{2}} es la matriz de permutación de paso N y orden N^{2}; 1_{N} ∈ ℂ^{N} es el vector tal que todas sus entradas son iguales a 1 y X, Y ∈ ℂ^{N^{2}} son vectores de orden N^{2} tal que

Y = ( Y_{0} ; Y_{1} ; ⋮ ; Y_{N−1} ) , X = ( X_{0} ; X_{1} ; ⋮ ; X_{N−1} ) ,

donde X_{m}, Y_{m} ∈ ℂ^{N} tal que X_{m}[n] = x[⟨m + n⟩_{N}] y Y_{m}[n] = y[⟨m − n⟩_{N}], para m, n ∈ ℤ_{N}.

Demostración. Se realizará la demostración de la ecuación (5). La demostración de la ecuación (6) se desarrolla de forma similar.

Sea a_{x,y} = L_{N}^{N^{2}} [I_{N} ⊗ F_{N}] [(1_{N} ⊗ \overline{y}) ⊙ \overline{Y} ]. Entonces

a_{x,y} = L_{N}^{N^{2}} ( H_{0} ; H_{1} ; ⋮ ; H_{N−1} ) , H_{m} ∈ ℂ^{N},  (7)

tal que H_{m} = F_{N}(x ⊙ \overline{Y_{m}}). Aplicando el operador R_{N,N} a ambos lados de la ecuación (7) y utilizando la propiedad R_{N,N} {L_{N}^{N^{2}}v} = (R_{N,N} {v})^{T}, para

cualquier v ∈ ℂ^{N^{2}}, se obtiene

R_{N,N}{a_{x,y}} = R_{N,N} {L_{N}^{N^{2}} ( H_{0} ; H_{1} ; ⋮ ; H_{N−1} )} = (R_{N,N} {( H_{0} ; H_{1} ; ⋮ ; H_{N−1} )})^{T} .

1R_{N,N} : ℂ^{N^{2}} → ℂ^{N×N} reordena un vector de orden N^{2} en una matriz de orden N × N, dividiendo el vector en N bloques y acomodando cada bloque como una columna. Más detalles en [13].

Rev.Mate.Teor.Aplic. (ISSN print: 1409-2433; online: 2215-3373) Vol. 26(2): 281–297, Jul–Dec 2019

Sea

H = R_{N,N} {( H_{0} ; H_{1} ; ⋮ ; H_{N−1} )} ,

es decir, H = (H_{0} H_{1} ... H_{N−1}), donde H ∈ ℂ^{N×N} y H_{m} representa la columna m de la matriz H. Entonces,

(H_{m,k})^{T} = H_{k,m} = H_{m}[k] = ∑_{n∈ℤ_{N}} x[n]\overline{y}[⟨m − n⟩_{N}]ω_{N}^{−nk} = A_{x,y}^{1}[m, k].

Nota: Existen otras formas de realizar el computo de la función discreta de ambiguedad, la cual no involucra productos Kronecker y Hadamard, los cuales no utilizan computo en paralelo [15]. El objetivo de usar las ecuaciones (5) y (6), es realizar un eficiente computo usando procesamiento en paralelo, el cual se puede utilizar en una computadora con varios procesadores [16].

3 Nuevo método criptográfico

En esta sección se desarrolla el nuevo método criptográfico, utilizando la función discreta de ambigüedad. Se explicará el proceso para cifrar un mensaje utilizando una clave simétrica, la cual se puede generar de forma aleatoria. Para este proceso se utiliza la matriz FDA, la cual genera el mensaje cifrado, seleccionando una fila o una columna de dicha matriz. Luego, se explicará el proceso para descifrar el mensaje, el cual depende de la selección de una fila o una columna para el mensaje cifrado, ya que son dos procesos distintos.

3.1 Proceso para cifrar el mensaje

Este proceso necesita computar la matriz FDA. El proceso es independiente de cuál definición de la función discreta de ambigüedad se utilice; ya sea la definición original (ecuación (3)) o la definición modificada (ecuación (4)). Para eso se utilizará el símbolo de A_{x,y}, la cual representará a las dos definiciones de la FDA.

Sea y ∈ ℂ^{N} el mensaje a encriptar y sea x ∈ ℂ^{N} parte de la clave simétrica, que se puede generar de forma aleatoria. El mensaje y es cifrado, calculando la matriz FDA de x, y, utilizando una fila o una columna de la matriz FDA de x, y. Para esto, se generan dos números enteros, c_{0}, c_{1}, de forma aleatoria:

• c_{0} ∈ ℤ_{2} representa la selección de una fila o una columna de la matriz FDA. En este caso, si c_{0} = 0, entonces se escoge una fila, y si c_{0} = 1 se escoge una columna.

• c_{1} ∈ ℤ_{N} representa el número de fila o columna a seleccionar.

Posteriormente, se genera el vector z ∈ ℂ^{N} que contiene el mensaje cifrado^{2}: si c_{0} = 0, entonces z = A_{x,y}[c_{1},:]^{T}; si c_{0} = 1, entonces z = A_{x,y}[:, c_{1}]. Finalmente, se genera la clave simétrica, w ∈ ℂ^{N+2} tal que w[0] = c_{0}, w[1] = c_{1} y w[n] = x[n − 2] para n = 2, 3, …, N + 1. El vector w será la información disponible al público (clave pública). El Algoritmo 1 muestra el pseudo-código de lo explicado anteriormente.

Algoritmo 1 Proceso para cifrar el mensaje y. Entrada: y ∈ ℂ^{N} (mensaje original). Salida: w ∈ ℂ^{N+2} (clave), z ∈ ℂ^{N} (mensaje cifrado). 1: x ← Rand(ℂ^{N}) 2: A ← A_{x,y} 3: c_{0} ← Rand(ℤ_{2}), c_{1} ← Rand(ℤ_{N}) 4: si c_{0} = 0 entonces 5: z ← A[c_{1},:]^{T} 6: si no 7: z ← A[:, c_{1}] 8: fin si 9: w[0] ← c_{0}, w[1] ← c_{1}, w[2 : N + 1] ← x

3.2 Proceso para descifrar el mensaje

El proceso para descifrar el mensaje z ∈ ℂ^{N} depende de si el vector z representa una fila o una columna de la matriz FDA. A continuación se explicarán los métodos para recuperar el mensaje original. En el caso de que el mensaje cifrado representa una fila de la matriz FDA, se explicará el procedimiento utilizando la definición original de la función discreta de ambigüedad, es decir, la ecuación (3). Para el caso cuando el mensaje cifrado representa una columna de la matriz FDA, se explicará el procedimiento utilizando la definición modificada de la función discreta de ambigüedad propuesta por Benedetto y Donatelli en [2, 3], es decir, la ecuación (4). La decisión de utilizar una definición u otra de la FDA para explicar los métodos de recuperación del mensaje original ha sido arbitraria y no influye en el resultado final.

2Dado una matriz A, la notación A[m,:] y A[:, n] representan la fila m y la columna n de la matriz A, respectivamente.

Rev.Mate.Teor.Aplic. (ISSN print: 1409-2433; online: 2215-3373) Vol. 26(2): 281–297, Jul–Dec 2019

3.2.1 Caso 1: El mensaje cifrado representa una fila de la matriz FDA

Sin pérdida de generalidad, el siguiente procedimiento se explicará utilizando la definición original de la función discreta de ambigüedad, es decir, la ecuación (3). Para la ecuación (4), propuesta por Benedetto y Donatelli, se prosigue de forma similar y el resultado se presenta al final.

Sea w ∈ ℂ^{N+2} la clave simétrica y z ∈ ℂ^{N} el mensaje cifrado. Considere el caso w[0] = 0, es decir, el vector z contiene una fila de la matriz FDA y el número de fila que representa está dado por w[1]=m; entonces w =A_{x,y}^{1}[m,:]^{T}, para m ∈ ℤ_{N}. Por lo tanto, para m fijo,

A_{x,y}^{1}[m, k] = ∑_{n∈ℤ_{N}} x[n]\overline{y}[⟨n − m⟩_{N}]ω_{N}^{−nk}, k ∈ ℤ_{N}.  (8)

Usando la ecuación (8), considere los siguientes pasos:

Paso 1: Aplicar la inversa de la transformada discreta de Fourier:

F^{−1}\{A_{x,y}^{1}\}[n] = x[n]\overline{y}[⟨n − m⟩_{N}].

Paso 2: Dividir por x[n], asumiendo que x[n] ≠ 0, para todo n ∈ ℤ_{N}:

\frac{F^{−1}\{A_{x,y}^{1}\}[n]}{x[n]} = \overline{y}[⟨n − m⟩_{N}].

Paso 3: Aplicar operador de traslación S_{−m}^{3}:

S_{−m} \{\frac{F^{−1}\{A_{x,y}^{1}\}[n]}{x[n]}\} = \overline{y}[n], para todo n ∈ ℤ_{N}.

Paso 4: Aplicar el conjugado complejo:

\overline{\{S_{−m} \{\frac{F^{−1}\{A_{x,y}^{1}\}[n]}{x[n]}\}\}} = y[n].

3El operador de traslación se define como el mapeo S_{m} : ℂ^{N} → ℂ^{N} tal que S_{m}{x}[n] = x[⟨n − m⟩_{N}]. Ver [1] para más detalles.

Rev.Mate.Teor.Aplic. (ISSN print: 1409-2433; online: 2215-3373) Vol. 26(2): 281–297, Jul–Dec 2019

En el Paso 2, es necesario que x[n] ≠ 0, para todo n ∈ ℤ_{N}. Por lo tanto, para recuperar el mensaje original, una condición necesaria es que la clave, representada por el vector x, no posea entradas nulas. Lo anterior prueba el siguiente teorema:

Teorema 2 Sea x, y ∈ ℂ^{N}, tal que x[n] ≠ 0, para n ∈ ℤ_{N}, y A_{x,y}^{1} ∈ ℂ^{N×N} la matriz FDA (ecuación (5)). Entonces,

y = \frac{1}{N} S_{−m}\overline{D}F_{N} \overline{b_{m}},  (9)

donde

• F_{N} ∈ ℂ^{N×N} es la matriz de la transformada discreta de Fourier de orden N.

• S_{−m} ∈ ℂ^{N×N} es la representación matricial del operador de traslación S_{−m}.

• D ∈ ℂ^{N×N} tal que D = diag (\frac{1}{x[0]}, \frac{1}{x[1]}, …, \frac{1}{x[N−1]}).

• b_{m} ∈ ℂ^{N} tal que b_{m}[k] = (A_{x,y}^{1})_{m,k}, para k ∈ ℤ_{N}.

El Algoritmo 2 muestra la implementación del método explicado anteriormente.

Algoritmo 2 Proceso para descifrar el mensaje z. Entrada: w ∈ ℂ^{N+2} (clave), z ∈ ℂ^{N} (mensaje cifrado). Salida: y ∈ ℂ^{N} (mensaje original). 1: v_{0} ← \overline{z} 2: v_{1} ← F{v_{0}} (transformada discreta de Fourier) 3: v_{2} ← w[2 : N + 1] 4: v_{3} ← v_{1} ⊙ v_{4}, donde v_{4}[n] = \frac{1}{\overline{v_{2}}[n]} 5: m ← w[1] 6: y ← \frac{1}{N} S_{−m}\{v_{3}\}

Para la matriz FDA que se genera a partir de la ecuación (4), se obtiene un resultado equivalente con un procedimiento similar, el cual se expresa en el teorema 3.

Teorema 3 Sea x, y ∈ ℂ^{N}, tal que x[n] ≠ 0, para todo n ∈ ℤ_{N}, y A_{x,y}^{2} ∈ ℂ^{N×N} representa a la matriz FDA (ecuación (6)). Entonces,

y = \frac{1}{N} S_{−m}\overline{D}S_{m}F_{N} \overline{b_{m}},  (10)

donde

• F_{N} ∈ ℂ^{N×N} es la matriz de la transformada discreta de Fourier de orden N.

• S_{m}, S_{−m} ∈ ℂ^{N×N} son las representaciones matriciales de los operadores de traslación S_{m} y S_{−m}, respectivamente.

• D ∈ ℂ^{N×N} tal que D = diag (\frac{1}{x[0]}, \frac{1}{x[1]}, …, \frac{1}{x[N−1]}).

• b_{m} ∈ ℂ^{N} tal que b_{m}[k] = (A_{x,y}^{2})_{m,k}, para k ∈ ℤ_{N}.

3.2.2 Caso 2: El mensaje cifrado representa una columna de la matriz FDA

Sin pérdida de generalidad, el siguiente procedimiento se explicará utilizando la definición de la función discreta de ambigüedad propuesta por Benedetto y Donatelli, es decir, la ecuación (4). Para la ecuación (3), la definición original, prosigue de forma similar, y el resultado se presenta al final.

Sea w ∈ ℂ^{N+2} la clave simétrica y z ∈ ℂ^{N} el mensaje cifrado. Considere el caso w[0] = 1, es decir, el vector z contiene una columna de la matriz FDA y el número de columna que representa está dado por w[1] = k; entonces z[2 : N + 1] = A_{x,y}^{2}[:, k], para k ∈ ℤ_{N}. Por lo tanto, para k fijo,

A_{x,y}^{2}[m, k] = ∑_{n∈ℤ_{N}} x[⟨n + m⟩_{N}]\overline{y}[n]ω_{N}^{−nk}, m ∈ ℤ_{N}.  (11)

Ahora, considere el sistema de N ecuaciones, generado de la ecuación (11), variando el valor de la primera entrada (m):

\{ \begin{matrix}x[0]\overline{y}[0] & + & ⋯ & + & x[N − 1]\overline{y}[N − 1]ω_{N}^{−(N−1)k} & =A_{x,y}^{2}[0, k], \\ x[1]\overline{y}[0] & + & ⋯ & + & x[0]\overline{y}[N − 1]ω_{N}^{−(N−1)k} & =A_{x,y}^{2}[1, k], \\ & & ⋮ & & & ⋮ \\ x[N − 1]\overline{y}[0] & + & ⋯ & + & x[N − 2]\overline{y}[N − 1]ω_{N}^{−(N−1)k} & =A_{x,y}^{2}[N −1, k]. \end{matrix}

292 j.p. soto quirós — d. rodríguez La representación matricial del sistema de ecuaciones anterior es

\underbrace{(\begin{matrix}x[0] & x[1]ω_{N}^{−k} & ⋯ & x[N − 1]ω_{N}^{−(N−1)k} \\ x[1] & x[2]ω_{N}^{−k} & ⋯ & x[0]ω_{N}^{−(N−1)k} \\ ⋮ & ⋮ & ... & ⋮ \\ x[N − 1] & x[0]ω_{N}^{−k} & ⋯ & x[N − 2]ω_{N}^{−(N−1)k} \end{matrix})}_{Z}( \overline{y}[0] ; \overline{y}[1] ; ⋮ ; \overline{y}[N − 1])=( A_{x,y}^{2}[0, k] ; A_{x,y}^{2}[1, k] ; ⋮ ; A_{x,y}^{2}[N − 1, k]).

Ahora, sea W ∈ ℂ^{N×N} tal que W = diag(1, ω_{N}^{−k}, ..., ω_{N}^{−(N−1)k}), entonces

Z =ZW^{−1}W  (12)

=\underbrace{(\begin{matrix}x[0] & x[1] & ⋯ & x[N − 1] \\ x[1] & x[2] & ⋯ & x[0] \\ ⋮ & ⋮ & ... & ⋮ \\ x[N − 1] & x[0] & ⋯ & x[N − 2] \end{matrix})}_{G=ZW^{−1}}\underbrace{(\begin{matrix}1 & 0 & ⋯ & 0 \\ 0 & ω_{N}^{−k} & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & ω_{N}^{−(N−1)k} \end{matrix} )}_{W}.

Por lo tanto, de la ecuación (12), se obtiene

\underbrace{( \begin{matrix}x[0] & x[1] & ⋯ & x[N − 1] \\ x[1] & x[2] & ⋯ & x[0] \\ ⋮ & ⋮ & ... & ⋮ \\ x[N − 1] & x[0] & ⋯ & x[N − 2] \end{matrix} )}_{G}\underbrace{( \begin{matrix}1 & 0 & ⋯ & 0 \\ 0 & ω_{N}^{−k} & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & ω_{N}^{−(N−1)k} \end{matrix} )}_{W}\underbrace{( \overline{y}[0] ; \overline{y}[1] ; ⋮ ; \overline{y}[N − 1] )}_{\overline{y}}=

\underbrace{( A_{x,y}^{2}[0, k] ; A_{x,y}^{2}[1, k] ; ⋮ ; A_{x,y}^{2}[N − 1, k] )}_{b_{k}},

por lo tanto

GW \overline{y} = b_{k}.  (13)

Ahora, sea R_{N} ∈ ℂ^{N×N} una matriz de reflexión. Para este caso, una propiedad de una matriz de reflexión es R_{N}G = C_{x}, donde C_{x} es una matriz circulante con respecto al vector x. Entonces, de la ecuación (13) se obtiene

R_{N}GW \overline{y} = R_{N}b_{k} ⇒ C_{x}W \overline{y} = R_{N}b_{k}.  (14)

Asumiendo que F_{x}[n] ≠ 0, para todo n ∈ ℤ_{N}, entonces C_{x} es invertible [8], y su inversa se representa por C_{x}^{−1} = \frac{1}{N} F_{N}D\overline{F_{N}}, donde D ∈ ℂ^{N×N} es una matriz diagonal tal que

D = (\frac{1}{F_{x}[0]}, \frac{1}{F_{x}[1]}, …, \frac{1}{F_{x}[N − 1]}) .

Por lo tanto

\begin{aligned}C_{x}W \overline{y} = R_{N}b_{k} & ⇒ & y = \overline{W^{−1}C_{x}^{−1}R_{N}b_{k}} \\ & ⇒ & y = \frac{1}{N} W \overline{F_{N}} \overline{D}F_{N}R_{N} \overline{b_{k}}. \end{aligned}

Lo anterior prueba el siguiente resultado:

Teorema 4 Sea x, y ∈ℂ^{N} tal que F_{x}[k]≠0, para todo k ∈ℤ_{N} y A_{x,y}^{2} ∈ ℂ^{N×N} representa a la matriz FDA (ecuación 6). Entonces

y = \frac{1}{N} W \overline{F_{N}} \overline{D}F_{N}R_{N} \overline{b_{k}},  (15)

donde

• W ∈ ℂ^{N×N} tal que W = diag (1, ω_{N}^{−k}, …, ω_{N}^{−(N−1)k}).

• D ∈ ℂ^{N×N} tal que D = (\frac{1}{F_{x}[0]}, \frac{1}{F_{x}[1]}, …, \frac{1}{F_{x}[N−1]}).

• R_{N} ∈ ℂ^{N×N} es la matriz de reflexión de orden N.

• b_{k} ∈ ℂ^{N} tal que b_{k}[m] = (A_{x,y}^{2})_{m,k}.

El Algoritmo 3 muestra la implementación del método explicado anteriormente.

Algoritmo 3 Proceso para descifrar el mensaje z. Entrada: w ∈ ℂ^{N+2} (clave), z ∈ ℂ^{N} (mensaje cifrado). Salida: y ∈ ℂ^{N} (mensaje original). 1: v_{0} ← \overline{z} 2: v_{1} ← R{v_{0}} (Operador de reflexión) 3: v_{2} ← F{v_{1}} 4: v_{3} ← w[2 : N + 1] 5: v_{4} ← F_{v_{3}} 6: v_{6} ← v_{2} ⊙ v_{5}, donde v_{5}[n] = \frac{1}{\overline{v_{4}}[n]} 7: v_{7} ← F^{−1}{v_{6}} 8: k ← w[1] 9: y ← v_{7} ⊙ v_{8}, donde v_{8}[n] = ω_{N}^{−nk}

Para la matriz FDA que se genera a partir de la ecuación (3), se obtiene un resultado equivalente con un procedimiento similar, el cual se expresa en el siguiente teorema.

Teorema 5 Sea x, y ∈ ℂ^{N} tal que F_{x}[k] ≠ 0, para todo k ∈ ℤ_{N} y A_{x,y}^{1} ∈ ℂ^{N×N} representa a la matriz FDA (ecuación (5)). Entonces

y = \frac{1}{N} \overline{F_{N}} S_{−k}\overline{D}S_{k}F_{N}R_{N} \overline{b_{k}},  (16)

donde

• F_{N}∈ℂ^{N×N}es la matriz de la transformada discreta deFourier de orden N.

• S_{k}, S_{−k} ∈ ℂ^{N×N} son la representación matricial de los operadores de traslación S_{k} y S_{−k} respectivamente.

• D ∈ ℂ^{N×N} tal que D = (\frac{1}{F_{x}[0]}, \frac{1}{F_{x}[1]}, …, \frac{1}{F_{x}[N−1]}).

• R_{N} ∈ ℂ^{N×N} es la matriz de reflexión de orden N.

• b_{k} ∈ ℂ^{N} tal que b_{k}[m] = (A_{x,y}^{1})_{m,k}.

4 Conclusiones

Este trabajo ha presentado un nuevo procedimiento de codificación criptográfica a través del diseño de algoritmos para cifrar y descifrar mensajes utilizando técnicas de Procesamiento Computacional de Señales. En particular, se ha presentado un nuevo método criptográfico basado en representaciones armónicas bidimensionales como entes codificadores de mensajes. La finalidad del procedimiento de codificación tiene como objetivo fundamental el intercambio de mensajes desde un punto a otro en espacio-tiempo, de tal manera que la información contenida en estos mensajes no pueda ser extraída por usuarios no autorizados.

El trabajo presentado se ha contextualizado bajo el esquema de Teoría de Información la cual estudia técnicas de codificación que permitan la transmisión y recepción de mensajes desde un punto a otro en espacio-tiempo. Bajo este contexto, el procedimiento de cifrar un mensaje se puede presentar como el envío de este mensaje a través de un canal de comunicación el que tendrá como entrada al mensaje no cifrado y el cual procederá a cifrar dicho mensaje. La salida del canal se convertirá, entonces, en el mensaje cifrado. Esta modalidad permitirá en el futuro combinar el uso de herramientas del área de Teoría de Información, tales como entropía no aditiva y funcionales de mínima divergencia, con herramientas del área de Procesamiento Computacional de Señales, tales como álgebra tensorial de señales y campos aleatorios generalizados, para abordar problemas relacionados con el uso de este nuevo método criptográfico en la comunicación sobre canales de dispersión en tiempo-frecuencia de múltiples entradas y múltiples salidas.

Una ventaja de este enfoque es que se puede utilizar una implementación en paralelo, y así, reducir el tiempo de computo [17, 16]. Además, la implementación del computo de la transformada discreta de Fourier, los productos Kronecker y Hadamard pueden realizarse de una forma eficiente, ver por ejemplo [8]. Por lo tanto, el computo matricial de todos resultados obtenidos en los teoremas presentados anteriormente, pueden ser calculados de una manera eficiente.

Finalmente destacar que el nuevo procedimiento criptográfico presentado en este trabajo podría abarcar aplicaciones en el área que actualmente se conoce como Criptografía Visual y la cual consiste en el intercambio de mensajes en donde cada mensaje está conformado por una imagen compuesta por píxeles negros y blancos.

Agradecimientos

Este artículo fue financiado por el Instituto Tecnológico de Costa Rica, a través de la Vicerrectoría de Investigación y Extensión.

Referencias

[1] M. An, A. K. Brodzik, R. Tolimieri, Ideal Sequence Design in Time-Frequency Space: Applications to Radar, Sonar, and Communication Systems, Applied and Numerical Harmonic Analysis, Birkhäuser, 2008.

[2] J. J. Benedetto, J. J. Donatelli, Frames and a vector-valued ambiguity function, 42nd Asilomar Conference on Signals, Systems and Computers, 2008, pp. 8–12.

[3] J. J. Benedetto, I. Konstantinidis and M. Rangaswamy, Phase-coded waveforms and their design, IEEE Signal Processing Magazine 26 (2009), no. 1, 22–31.

[4] B. Boashash, Time Frequency Signal Analysis and Processing: A Comprehensive Reference, Elsevier, 2003.

[5] J. W. Cooley, J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation 19 (1965), no. 90, 297–301.

[6] P. J. Davis, Circulant Matrices (Pure & Applied Mathematics), Chelsea Publishing Series, Chelsea, 1994.

[7] F. Franchetti, M. Puschel, Y. Voronenko, S. Chellappa, J. M. F. Moura, Discrete fourier transform on multicore, IEEE Signal Processing Magazine 26 (2009), no. 6, 90–102.

[8] G. H. Golub, C. F. Van Loan, Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, 1996.

[9] A. Graham, Kronecker products and matrix calculus with applications, Ellis Horwood series in mathematics and its applications, Horwood, 1981.

[10] J. Hoffstein, J. Piphe, J. H. Silverman, An Introduction to Mathematical Cryptography, Undergraduate texts in mathematics, Springer, New York, 2008.

[11] J. R. Johnson, R. W. Johnson, D. Rodriguez, R. Tolimieri, A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures, Circuits, Systems, and Signal Processing 9 (1990), no.4, 449–500.

[12] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, Discrete Mathematics and Its Applications, CRC Press, 1996.

[13] C. D. Moravitz, C. F. Van Loan, A jacobi-type method for computing orthogonal tensor decompositions, SIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 1219–1232.

[14] P. A. Regalia and S. K. Mitra, Kronecker products, unitary matrices, and signal processing applications, SIAM Rev. 31 (1989), no. 4, 586–613.

[15] M. S. Richman, T. W. Parks, R. G. Shenoy, Discrete-time, discretefrequency, time-frequency analysis, IEEE Transactions on Signal Processing 46 (1998), no. 6, 1517–1527.

[16] P. Soto-Quirós, A mathematical framework for parallel computing of discrete-time discrete-frequency transforms in multi-core processors, Applied Mathematics & Information Sciences 8 (2014), no. 6, 2795–2801.

[17] J. P. Soto-Quirós, D. Rodríguez, Representación matricial de algoritmos en paralelo de la transformada discreta de Fourier, la función discreta de ambiguedad y la distribución discreta de Cohen, Gaceta de la Real Sociedad Matematica Española 16 (2013), no. 3, 479–500.

[18] R. Tolimieri, M. An, C. Lu, Algorithms for Discrete Fourier Transform and Convolution, Signal Processing and Digital Filtering, Springer, New York, 1997.

[19] P. M. Woodward, Probability and Information Theory: with Applications to Radar, McGraw-Hill, New York, 1953.