Aplicaciones de la recursión

Si nos cuestionamos para qué sirve la matemática, podemos responder que para
muchas cosas. En esta lectura, veremos un sistema de encriptación que hace uso de
la teoría de los números para garantizar que los mensajes lleguen de un punto a otro
sin ser interceptados.

A lo largo de las lecturas, hemos ido realizando análisis de distintos algoritmos que
responden a diferentes modelos. Tal es el caso de la técnica divide y vencerás, que
usamos cuando explicamos una búsqueda binaria. Analizaremos estos modelos,
que nos proveen de estrategias algorítmicas para resolver una gran variedad de
problemas.

Aplicaciones de la recursión

Referencias
LECCIÓN 1 de 2

Aplicaciones de la recursión

RSA

Como mencionamos en la lectura anterior, la teoría de los números es una

rama de la matemática que estudia las propiedades de los números,
particularmente, de los números enteros. Al principio, se creía que no era de
utilidad, pero en los últimos años comenzó a ser usada para los procesos
criptográficos. A continuación, explicaremos de manera simplificada en qué
consiste el método RSA.

Conceptos iniciales

La criptografía es una disciplina que se ocupa del cifrado o el codificado de

los mensajes que viajan por un medio susceptible de ser intervenido por un
agente no autorizado (en general, en la actualidad, cualquier medio es
vulnerable). Esto genera alteraciones lingüísticas, de manera que el
interceptor no pueda comprenderlo.

Una comunicación se caracteriza por la presencia de un emisor, que está

interesado en enviar un mensaje, a través de un canal de comunicación, a un
receptor.

Un mensaje está compuesto por un conjunto de caracteres que, en definitiva,

son un conjunto de bits. Por ende, un mensaje es un conjunto o una
secuencia de bits.

Interceptación

En general, la comunicación entre un emisor y receptor puede ser

amenazada de varias maneras:

Interceptación: a continuación, la abordaremos con más detalles.

Modificación: si un emisor envía un mensaje a un receptor, el

mensaje le llega alterado a este último. Un usuario no autorizado
intercepta el mensaje en el canal de la comunicación, lo modifica y
se lo entrega al receptor con dichas modificaciones. La
modificación afecta a la integridad de los datos.

Interrupción: si un emisor envía un mensaje a un receptor, el

mensaje nunca le llega a este último. Un usuario no autorizado
intercepta el mensaje y lo elimina del canal, para que no le llegue al
receptor. La interrupción afecta a la disponibilidad de los datos.

Fabricación: un usuario no autorizado genera un mensaje a nombre

de otra persona (suplantación) y se lo envía a un receptor. El
receptor, que desconoce dicha situación, recibe el mensaje y
 piensa que el emisor aparente se la envió, cuando, en realidad, fue
el usuario no autorizado. La fabricación afecta a la autenticación.

Analicemos otra situación: la interceptación. Tenemos un emisor A que se

quiere comunicar con un receptor B y que envía un mensaje. Un usuario no
autorizado interviene en el canal de la comunicación y accede al mensaje. No
lo altera, solo accede a la información del mensaje. Tampoco interrumpe la
comunicación, por lo cual el receptor recibe el mensaje. Ni el emisor ni el
receptor se enteran de que el mensaje fue visto por un tercero. La
interceptación afecta a la confidencialidad (necesidad de que la información
sea accesible, únicamente, para las entidades autorizadas).

La interceptación es un ataque a la confidencialidad, en donde un usuario no

autorizado accede a un recurso sin modificarlo ni alterar el canal de la
comunicación.

Cifrado

Si se hace uso de la criptografía, se pueden cifrar los mensajes que se

envíen, de manera que si un usuario no autorizado accede al mensaje, no
podrá interpretar nada. Este proceso consiste, primeramente, en un cifrado
realizado por el emisor y, luego, un descifrado realizado por el receptor.
Únicamente el receptor autorizado podrá realizar el descifrado del mensaje.
Como mencionamos anteriormente, un mensaje es una secuencia de bits.
Este conjunto de bits puede ser descompuesto en bloques de cierta cantidad
de bits, por lo que el mensaje se constituye de una serie de números
grandes. Por esto, se deberá cifrar estos números grandes, y luego descifrar
el valor arrojado por el cifrado (Weiss, 2013).

Constantes RSA

El algoritmo RSA impone que el receptor determine algunas constantes. Se

enumeran los pasos que el receptor debe seguir:

1 Inicialmente, se determina aleatoriamente el valor de dos números

primos grandes p y q (de, al menos, 100 dígitos).

2 Luego, el receptor debe calcular: N = pq y N’ = (p - 1) (q - 1).

3 El receptor debe calcular algún valor que cumpla la condición

siguiente: mcd(e, N’) = 1. Matemáticamente, esta condición sirve
para obtener un valor e que se considera relativamente primo de
N’.

4 El receptor debe calcular un valor d, correspondiente al inverso

multiplicativo de e, mod N’, es decir, (e/d) mod N´= 1

5 El receptor debe destruir los valores p, q y N’. Se queda con los

valores e, N y d. Los valores e y N serán la clave pública, que será
 entregada a todos aquellos emisores que deseen comunicarse con
el receptor. El valor d se mantiene en secreto, ya que es la clave
privada.

Proceso de cifrado y descifrado

CIFRADO: para cifrar un mensaje en texto plano M a un mensaje cifrado C, el
mejor emisor, que tiene en su poder es la clave pública (e, N), deberá realizar

el cálculo: C=𝑀𝑒 𝑚𝑜𝑑 𝑁

DESCIFRADO: para obtener el mensaje original M de un mensaje cifrado

como C, el receptor, que además de conocer la clave pública (e, N) también

tiene la clave privada d, deberá realizar el cálculo: M=Cd 𝑚𝑜𝑑 𝑁

Es evidente que este método funciona gracias al uso de la exponenciación

modular. La elección de los valores e, d y N garantiza que:

Med = M(𝑚𝑜𝑑 𝑁)

si se tiene en cuenta que M y N no tienen ningún factor en común.

Para poder realizar el descifrado, es necesario conocer d. Podemos llegar al

valor de d conociendo N y e, ya que ellos determinan de manera unívoca a d.
Si factorizáramos a N, podríamos obtener los valores p y q que, en definitiva,
permiten calcular a d. Pero, como mencionamos en la lectura anterior, la
factorización es una operación difícil de realizar si los números son grandes.
Consideremos que N asumirá los valores de 100, 200, 300 o más dígitos y la
capacidad computacional no será capaz de factorizar un número así de
grande. Esto es lo que permite que el algoritmo RSA sea seguro.

Limitaciones
El problema del algoritmo RSA es el tiempo que demora para los mensajes
de gran tamaño. Para ello, surge otro algoritmo denominado DES. Este
consta de una clave única usada tanto para cifrado como para descifrado.
Por consiguiente, el emisor y receptor deberán compartirse la clave.

Para ello, se implementó una dinámica muy usada en varios protocolos.

Consiste en:

1 El emisor debe generar, aleatoriamente, una clave para el cifrado

DES.

2 El emisor debe cifrar el mensaje con la clave DES generada. De

esta manera, lo logra de forma más rápida que si hubiera usado
RSA.

3 El emisor cifra la clave DES usando RSA (la clave DES es

relativamente corta).

4 El emisor envía al receptor el mensaje cifrado con la clave DES y la

clave DES cifrada con RSA.
 5 El receptor descifra la clave DES.

6 El receptor usa la clave DES obtenida para descifrar el mensaje.

Divide y vencerás
Un algoritmo divide y vencerás es una técnica recursiva de resolución de
problemas, que se caracteriza por dividir un problema en subproblemas más
sencillos, hasta que se llegue a un nivel donde se realice una resolución
recursiva de subproblemas triviales. Finalmente, se reconstruye la solución
general con las subsoluciones calculadas.

Los subproblemas componen conjuntos disjuntos, con el objetivo de no

hacerlo tan costoso (evitar realizar los mismos cálculos que ya se hacen en
otro subproblema). Cada subproblema es un conjunto menor de datos para
procesar por parte del algoritmo.

En general, se consideran algoritmos de tipo divide y vencerás a aquellas

rutinas que contengan, al menos, dos llamadas recursivas (Weiss, 2013).

Un ejemplo de un algoritmo divide y vencerás, visto en lecturas anteriores, es

el algoritmo de búsqueda binaria. Este algoritmo partía de una estructura de
datos a la mitad, en iteraciones sucesivas, y descartaba las mitades donde,
seguramente, no estaba el valor que se deseaba encontrar. Hay otros
ejemplos que analizaremos en la próxima lectura, como los algoritmos de
ordenamiento quicksort y mergesort.
Programación dinámica
La programación dinámica es un enfoque que nos permite encontrar una
solución a los problemas complejos, a través de una desagregación de estos
en una secuencia de problemas más pequeños y más sencillos. De esta
manera, se podrá localizar la combinación de decisiones que optimice la
efectividad global.

Podemos definir la programación dinámica basándonos en el principio de

optimalidad enunciado por Bellman: “en una secuencia de decisiones óptima,
toda subsecuencia debe ser óptima también” (Sznajdleder, 2012, p. 596).

Una política óptima tiene como característica que, independientemente de

las decisiones tomadas para arribar a un estado específico en una etapa
particular, el resto de las decisiones que dependen de esta, también son
óptimas.

Sabemos que la técnica divide y vencerás también divide el problema en

subproblemas más sencillos. Sin embargo, se diferencian entre sí en que, en
la programación dinámica, los subproblemas no son independientes entre sí.

Como lo que se quiere lograr es reducir el tiempo de ejecución de un

algoritmo, en vez de repetir los cálculos que ya se hicieron, estos deben ser
almacenados en una tabla. Así, se logra una disminución del tiempo de
ejecución, pero se aumenta la complejidad espacial.
Algoritmo de vuelta atrás
El algoritmo de vuelta atrás o backtracking es una estrategia para los
problemas que satisfacen las restricciones. Permite comprobar,
exhaustivamente, todas las posibilidades, con el objetivo de encontrar las
soluciones.

La forma en que trabaja este algoritmo es a través de probar combinaciones

y encontrar aquella que sea la mejor para un momento dado. La búsqueda
(también conocida como búsqueda en profundidad) va realizando
comprobaciones sucesivas, de manera que si se encuentra una alternativa
incorrecta, se vuelve atrás y se continúa con la comprobación de otra
alternativa.

Estos algoritmos se ejecutan dentro de distintas estructuras. Por ejemplo, si

fuera un árbol, se transitan los nodos, de manera que cada nodo contendrá
un estado: los nodos interiores serán soluciones parciales y se arribará a una
solución total cuando dicho nodo sea hoja. Cuando no quedan más
alternativas y ninguna es correcta, significa que no se encontró una solución.
La búsqueda falló.

Estos algoritmos suelen implementarse de manera recursiva. Por esto, se

realizan sucesivas llamadas a los procedimientos, que toman una variable, le
asignan distintos valores posibles, y crean nuevos estados que también
llamarán a un nuevo procedimiento.
Algunos ejemplos de problemas en los que se usa el algoritmo de vuelta
atrás son los juegos tic-tac-toe, sudoku, 8 reinas, entre otros.

C O NT I NU A R
LECCIÓN 2 de 2

Referencias

Sznajdleder, P. A. (2012). Estrategia algorítmica. En Autor, Algoritmos a

fondo. Con implementaciones en C y JAVA (pp. 549-551). Buenos Aires, AR:
Alfaomega.

Weiss, M. (2013). Recursión. En Autor, Estructuras de datos en Java (pp. 287-

340). Madrid, ES: Pearson.