La experiencia no consiste en
el número de cosas que se han visto, sino en el número
de cosas en que se han reflexionado.
(Jose M. de Pereda. Escritor español
nacido en Polanco, Cantabria)
En el anterior apartado
comenzamos a hablar del cifrado exponencial, un método
realmente resistente al criptoanálisis como ya vimos, comparable
al conocido RSA.
Nos corresponde ahora
explicar algunos puntos que dejamos sin tratar y comentar una
aplicación interesante porque aparentemente es imposible:
como conseguir que dos personas puedan jugar al poker a distancia
sin que ninguno de los dos pueda hacer trampa.
Recordemos que el cifrado
era del tipo P=C^e (mod p) donde p es un número primo y
e, la clave, un entero primo con p-1.
Decíamos que
con los últimos métodos conocidos un entero de 100
dígitos podría dar trabajo durante decenas de años
al criptoanalista. Hay que mencionar sin embargo que para primos
p tales que p-1 tiene sólo factores primos pequeños,
es posible utilizar técnicas especiales para encontrar
logaritmos módulo p usando un tiempo claramente inferior,
proporcional al cuadrado del logaritmo de p. Así pues no
debemos escoger un primo de este tipo; eligiendo p=2q+1 donde
q es también primo evitaremos este problema.
Los cifrados basados
en exponenciación modular son útiles para establecer
"claves comunes" para el uso de dos o más individuos.
Este tipo de claves pueden ser utilizadas para establecer comunicaciones
entre un grupo de personas en una red sin temer intrusiones.
Para establecer una
clave común, tomemos un gran primo p y un entero a que
sea primo con p. Cada individuo en la red escoge una clave k que
sea primo con p-1 (k y p-1 no tienen factores comunes). Cuando
dos personas con claves k1 y k2 quieren intercambiar una clave
hacen lo siguiente: el primero manda al segundo un entero y1 donde
y1=a^k1 (mod p)
y el segundo encuentra la clave común K calculando:
K=y1^k2=a^(k1.k2) (mod p)
(observemos que el segundo no necesita conocer k1). Recíprocamente
el segundo individuo manda al primero el entero y2 siendo
y2=a^k2 (mod p)
y así el primer individuo encontrará a su vez la
clave común K calculando
K=y2^k1=a^(k1.k2) (mod p)
Desde este momento la
clave K sirve para intercambiar información entre estos
dos individuos y ninguno más en la red puede acceder a
ella pues tendría que calcular logaritmos en base p para
encontrar K.
Es sencillo generalizar
esto para que n individuos escojan sus claves k1, k2... kn y encuentren
individualmente la clave común
K=a^(k1...Kn) (mod p)
Y pasamos ya a describir
la aplicación que comentabamos al comienzo del artículo.
Se basa en los trabajos de Rivest Shamir y Adleman (R. S. A. ¿te
suena?).
Supongamos que Alex
y Beatriz quieren jugar al poker a distancia. Empiezan por escoger
juntos un primo p lo mayor posible. Despues por separado eligen
claves secretas e1 y e2, de manera que tendremos las transformaciones:
E1(M)=M^e1 (mod p)
E2(M)=M^e2 (mod p)
donde M es el mensaje sin cifrar. Si ahora d1, d2 son los inversos
de e1, e2 módulo p las transformaciones de descifrado serán
D1(C)=C^d1 (mod p)
D2(C)=C^d2 (mod p)
ahora C es el mensaje cifrado. Bien para jugar al poker la baraja
será representada por 52 mensajes M1='AS DE DIAMANTES',
M2='DOS DE DIAMANTES', ... M52='REY DE CORAZONES' por ejemplo.
Supongamos que Beatriz
va a repartir las cartas.
