Criptografía de clave pública
Gerardo Rodríguez Sánchez
Departamento de Matemática Aplicada
Universidad de Salamanca
E-mail: [email protected]
1
Problemas de la Clave Secreta
 La clave secreta ha de intercambiarse de forma segura
(¿entrevista?).
 La clave secreta ha de modificarse con frecuencia.
 Problema de almacenamiento de las claves: para
comunicarse con n usuarios, cada uno de ellos necesita
n(n – 1)/2 claves.
 Imposibilidad de firmar digitalmente los mensajes.
2
Criptografía de Clave Pública
 Se utiliza diferente clave para cifrar mensajes que para
descifrarlos (Internet, empresas, usuarios).
 Protocolo de cambio de clave de Diffie-Hellman
3
Criptografía de Clave Pública
 RSA
Basado en la dificultad de factorizar números enteros.
Claves de 1024 bits.
 ElGamal
Basado en la dificultad de calcular logaritmos discretos.
Claves de 1024 bits.
4
Cambio de clave Diffie-Hellman (1)
o
A y B seleccionan públicamente un grupo cíclico finito
G, |G| = n, y un generador .
o
A genera un número aleatorio a, calcula a y lo envía a B.
o
B genera un número aleatorio b, calcula b y lo envía a A.
5
Cambio de clave Diffie-Hellman (2)
o
A recibe b y calcula (b)a = ba.
o
B recibe a y calcula (a)b = ab.
o
CONCLUSIÓN: A y B comparten el mismo elemento
secreto del grupo: ab.
6
Seguridad del cambio de clave DiffieHellman (3)
Son públicos los siguientes elementos:
el grupo G, su orden n, el generador 
Se pueden intervenir los siguientes datos:
a, b
Se pretende calcular el valor de:
ab
Se supone que es un problema intratable
(Teoría de la complejidad computacional).
7
Ejemplo de cambio de clave Diffie-Hellman
(1)
1.
A y B seleccionan (Z53)* y un generador  = 2.
2.
A genera a = 29, calcula a = 229 (mod 53) = 45 y lo
envía a B.
3.
B genera b = 19, calcula b = 219 (mod 53) = 12 y lo
envía a A.
4.
A recibe b = 12 y calcula (b)a = 1229 (mod 53) = 21.
8
Ejemplo de cambio de clave Diffie-Hellman
(2)
5.
B recibe a = 45 y calcula (a)b = 4519 (mod 53) = 21.
A y B comparten el mismo elemento secreto del grupo:
ab = 21.
Conociendo (Z53)*,  = 2, a = 45, b = 12, calcular ab.
9
Criptosistema RSA: claves (1)
Generación de claves:
Se eligen dos números primos distintos, grandes y
cercanos: p, q, y se calcula n = p · q.
Se considera el grupo (Zn)*, cuyo orden es
(n) = (p – 1)(q – 1).
Se elige un número e primo con (n).
Se calcula el inverso de e en (Zn)*: d, es decir,
e · d  1 mod. (n).
10
Criptosistema RSA: claves (2)
Generación de claves :
La clave pública es el par (n, e).
La clave privada es el número d.
Se deben mantener ocultos también los valores de p, q y
(n).
11
Criptosistema RSA: cifrado y descifrado
Cifrado:
1. B obtiene la clave pública de A: (n, e).
2. B representa el mensaje que quiere enviar, m, en el
conjunto (Zn)*, troceándolo si es preciso.
3. B calcula me (mod. n)  c, que envía a A.
12
Criptosistema RSA: cifrado y descifrado
Descifrado:
1. A utiliza su clave privada, d, para calcular
cd (mod. n)  med (mod. n)  m.
13
Criptosistema RSA: seguridad
Dado un entero positivo, n, producto de dos primos
distintos grandes de tamaño parecido: p y q, un entero
positivo e, tal que MCD(e, (n)) = 1, y un entero c,
encontrar otro entero m tal que
me  c (mod. n).
Hipótesis: La seguridad del RSA es equivalente al
problema de factorizar.
14
Ejemplo de RSA
Determinación de la clave
 Elegimos dos números primos p y q, los multiplicamos
para obtener el módulo RSA, n, y determinamos (n)
p =383
q = 521
n = p · q = 383 · 521 = 199543
(n) = (p-1)(q-1) = 382 · 520 = 198640
 Elegimos el exponente de cifrado, 2< e <198640, primo
con (n), por ejemplo, e=3.
15
Ejemplo de RSA
Determinación de la clave
 Calculamos el exponente de descifrado d, que es el
inverso de e módulo (n): d = 132427
 Damos a conocer nuestra clave pública: (199543, 3).
 Ocultamos nuestra clave privada: d=132427, así como
los restantes valores p = 383, q = 521 y (n) =
198640.
16
Ejemplo de RSA
Cifrado del mensaje
Supongamos que un usuario B desea enviarnos el
mensaje RSA. Los pasos a seguir serán los siguientes:
 Localiza nuestra clave pública: (199543, 3).
 B escribe el mensaje a enviar como un número menor
que 199543
y primo con él. Por ejemplo,
puede considerar la siguiente representación de letras
por números (sin la Ñ):
A0, B1, C2,..., Y24, Z25
y emplear la base 26 para representar cualquier
palabra.
17
Ejemplo de RSA
Cifrado del mensaje
En nuestro ejemplo: R17, S18, A0 con lo que el
mensaje sería:
m = 17 · 262+18 · 26+0 = 911
 B cifra el mensaje anterior calculando:
c  me (mod. n)  9113 (mod. 199543)  189147
que es el criptograma a enviar.
 Este valor puede convertirse de nuevo en base 26 para
convertirlo en letras:
c =189147 = 10 · 263+19 · 262+ 20 · 26+ 23 
KTUX
18
Ejemplo de RSA
Descifrado del mensaje
 Una vez hemos recibido el criptograma (189147 o KTUX),
utilizamos nuestra clave privada d = 132427 para calcular:
m  cd (mod. n)  189147132427(mod. 199543).
 El cálculo de este número se realiza con la siguiente
estrategia:
d=132427=(100000010101001011)2=217+210+28+26+23+
2+1
19
Ejemplo de RSA
Descifrado del mensaje
 Calculamos las siguientes potencias, cada una de las cuales
es el cuadrado de la anterior y hacemos módulo 199543:
1891472124053 1891474191106 1891478145661
18914716118817
1891473211782
18914764133139 189147128189545 189147256 188504
189147512 138291 189147102418
1891472048 324
1891474096
104976
1891478192198401
18914716384106906 1891473276867511
18914765536  173001 18914713107290974
20
Ejemplo de RSA
Descifrado del mensaje
 Ahora basta multiplicar las potencias de la expresión en base
2 de la clave privada y reducir mod. 199543 tras cada
producto:
189147 · 124053  190964
190964 · 145661  112090
112090 · 133139  128626
128626· 188504 45574
45574· 18  22160
22160 · 90974  911
que coincide con el número enviado.
21
Ejemplo de RSA real: determinación de la clave
Elegimos dos números primos de 512 bits cada uno:
p=
99139 39965 46089 30824 88909 93861 03286 96951
12542 27785 63290 53802 69243 59622 97966 62570
51166 31784 15643 33030 16752 83735 31885 76891
66571 64285 73232 22921 38706 46645 4667
q=
13136 91819 25708 96843 02581 72409 47022 42864
58333 11752 43481 96993 06139 88470 36911 06258
28665 95507 45575 89427 96421 73663 31154 90105
78349 59036 89416 42907 63853 18510 41021
22
Ejemplo de RSA real: determinación de la clave
Calculamos ahora n, que tiene 1024 bits:
n=
13023 86182 92318 89502 81446 21088 35570 66154
05574 73331 40682 54739 98959 56538 57163 11615
41258 54863 46136 57472 70014 83693 94664 97674
40264 93450 88904 88932 37197 32536 99623 85944
66298 94133 32414 06479 20780 49438 83915 47728
71066 51988 01638 29581 61596 27668 24197 08727
22204 06157 69033 71955 35028 37798 65973 36760
32443 19911 37588 05059 05389 5007
23
Ejemplo de RSA real: determinación de la clave
Calculamos ahora  (n)
 (n) = 13023 86182 92318 89502 81446 21088 35570 66154
05574 73331 40682 54739 98959 56538 57163 11615
41258 54863 46136 57472 70014 83693 94664 97674
40264 93450 88904 88932 37197 32536 99621 55436
08140 90954 33158 91752 02824 75927 58318 51855
25756 53877 77904 98939 17269 60590 99043 70901
35345 34755 41723 90985 14659 94363 88023 86692
77788 52514 85590 27820 73639 9320
24
Ejemplo de RSA real: determinación de la clave
Como exponente de cifrado elegimos e = 65537 = 216+1, mientras
que el exponente de descifrado es:
d=
16516 06202 03467 10050 48918 84868 90218 92489
18279 99581 50695 43180 80680 06590 48611 11408
16546 34751 39652 57374 55344 81434 97422 92471
72748 50400 58881 01914 48242 51509 06748 05656
23580 43535 93387 51598 50264 21324 46463 09835
51972 56416 71447 94037 48482 18482 95184 74535
17075 11535 81529 12320 91084 24120 45236 48596
01095 63033 24342 09716 36483 433
25
Ejemplo de RSA real: cifrado del mensaje
Supongamos que el mensaje a transmitir utilizando la clave pública
(n,e) es:
“Hasta la fecha no se ha demostrado de forma rigurosa la
equivalencia entre resolver el problema de la factorización y
romper el criptosistema RSA.”
Para transformar el mensaje en un número menor que el módulo
RSA y primo con él, se utiliza la base 256 dada por los valores
ASCII de los caracteres que componen el mensaje. Como la
longitud del mensaje no puede ser mayor que el módulo RSA, se
analiza si es preciso trocear el mensaje.
26
Ejemplo de RSA real: cifrado del mensaje
m1 =
34591 23054 20684 92221 54004 31463 55718 40131
37946 50256 99770 12379 52245 48266 91597 68390
89367 27153 70468 41774 43004 17303 60120 13102
23597 42585 57180 20667 78546 06812 75424 51035
61893 92809 52751 30985 62992 14551 08844 27863
83635 95214 39334 39345 58318 94335 36299 26978
14144 61358 60603 23404 84057 33961 81735 90951
71716 01412 29657 69676 146
m2 =
31029 37695 14888 24008 25180 81526 70973 28927
96416 57111 46496
27
Ejemplo de RSA real: cifrado del mensaje
c1 =
24283 83009 28360 92697 52894 91397 11182 33327
01972 51994 66194 67116 15452 51338 36137 91948
61510 99909 69538 57591 62731 96550 16598 26516
28223 74514 60203 01145 55449 76420 73563 67035
62024 22363 16254 50805 03386 81854 29313 76893
22373 92781 30286 52114 52126 18961 46028 71599
71878 80429 73749 97653 74787 98609 84624 04766
58549 16062 48613 00369 22093 872
28
Ejemplo de RSA real: cifrado del mensaje
c2 =
38682 54957 70121 92903 21010 10135 17239 71957
23710 93292 77161 21301 87357 13461 04331 73889
57425 36031 34884 61661 51664 31071 46625 14562
56910 77963 89701 42435 54123 55176 62692 53475
35346 82015 24635 33695 20098 88439 34168 44397
93387 91590 76644 51408 56154 28962 22028 65447
75223 55380 20368 32538 03134 56525 82206 82408
11962 36481 98184 80787 46237 430
29
Ejemplo de RSA real: descifrado del mensaje
El mensaje descifrado correspondiente a cada uno de los bloques
enviados es el siguiente:
“Hasta la fecha no se ha demostrado de forma rigurosa la
equivalencia entre resolver el problema de la factorización y
romper”
“el criptosistema RSA.”
30
Precursores de la criptografía de clave pública y
del RSA
1976: Protocolo de cambio de clave de Diffie-Hellman
1978: Criptosistema RSA
1997: Criptógrafos del Cuartel General de Comunicaciones del
Gobierno Británico
1973 Cocks
1970 Ellis
1974 Williamson
31
Firma digital RSA
Sean (nB,eB) y dB las claves pública y privada de un usuario B y sean
(nA,eA) y dA las claves correspondientes del usuario A.
Si B quiere mandar junto con el criptograma c correspondiente al
mensaje m, su firma digital para dicho mensaje, el protocolo a seguir
es:
 B calcula el valor de su firma r  mdB (mod. nB) con su
exponente de descifrado dB.
 B cifra el valor anterior
con la clave pública de A,
s  reA (mod.nA) y transmite a A el par (c,s).
32
Firma digital RSA
Para que A pueda verificar que la firma corresponde a B sólo tiene
que ejecutar los siguientes pasos:
 A recupera la firma de B para el mensaje m calculando
sdA r (mod. nA).
 A comprueba si la firma cifrada coincide con el mensaje
reB  m (mod. nB).
33
Elección de los primos p y q.
 p y q deben ser de la misma longitud.
En la actualidad se recomienda que p y q tengan cada uno una
longitud mínima de 512 bits y, por tanto, n tenga al menos 1024
bits (alrededor de 309 dígitos).
 p y q no deben estar demasiado cercanos.
Si no fuera así se podría factorizar n encontrando x e y tales
que x2-n=y2, pues entonces p = x-y, q = x+y.
34
Elección de los primos p y q.

MCD(p-1,q-1) debe ser pequeño.

p-1 y q-1 deben contener factores primos grandes.

p y q deben ser robustos.
Un primo impar p se dice robusto si verifica:
p-1 tiene un factor primo grande r.
p+1 tiene un factor primo grande s.
r-1 tiene un factor primo grande t.
35
.
Elección del exponente de cifrado e.
Una vez que se ha seleccionado un valor grande para el módulo
RSA se recomienda seleccionar un exponente de cifrado e pequeño
para facilitar la tarea de cifrado me (mod. n).
Por esta razón se recomienda que el exponente de cifrado sea
e = 3 ó e = 65537
Sin embargo no se debe usar valores pequeños de e al enviar un
mismo mensaje m a varios destinatarios.
36
Elección del exponente de descifrado d.
El exponente de descifrado d debe ser de longitud aproximada a la
de n.
Si longitud en bits (d)  (1/4) longitud en bits (n) existe un
algoritmo eficiente para calcular d.
37
Mensajes inocultables.
Un mensaje m es inocultable si se cifra a sí mismo, es decir:
me  m (mod. n)
El número de mensajes inocultables es
(1+mcd(e-1,p-1)) · (1+mcd(e-1,q-1))
Al menos hay 9 mensajes inocultables. No afecta a la seguridad
del RSA.
38
Récord de factorización.
El récord del módulo RSA más grande factorizado lo logró el 9 de
Mayo de 2005 un equipo de investigadores alemanes, dirigidos por
J. Franke, de la Agencia Alemana para la Seguridad de las
Tecnologías de la Información (BSI).
Dicho equipo ostentaba el anterior récord al lograr factorizar en
Diciembre de 2003 el módulo RSA-576 de 174 dígitos.
El número factorizado ahora es el RSA-200 de 200 dígitos.
39
Récord de factorización.
El RSA-200 factorizado es:
n=
2799783391 1221327870 8294676387 2260162107
0446786955 4285375600 0992932612 8400107609
3456710529 5536085606 1822351910 9513657886
3710595448 2006576775 0985805576 1357909873
4950144178 8631789462 9518723786 9221823983
40
Récord de factorización.
p=
3532461934 4027701212 7260497819 8464368671
1974001976 2502364930 3468776121 2536794232
0005854795 6528088349
q=
7925869954 4683330333 4708584148 0059687737
9758573642 1996073433 0341455767 8728181521
3538140930 4740185467
41
Récord de factorización.
La siguiente tabla recoge algunos de los módulos RSA por
factorizar y los premios ofrecidos. Pueden consultarse las
siguientes direcciones para una completa información sobre este
asunto:
http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
http://www.rsasecurity.com/rsalabs/challenges/factoring
http://www.npac.syr.edu/factoring/overview/RSAFCAList.txt
42
Número
Dígitos
RSA-200
RSA-576
200
174
RSA-640
RSA-704
RSA-768
193
212
232
RSA-896
RSA-1024
RSA-1536
270
309
463
RSA-2048
617
Premio
10000$
20000$
30000$
50000$
75000$
100000$
150000$
200000$
Fecha
9-5-2005
3-12-2003
Abierto
Abierto
Abierto
Abierto
Abierto
Abierto
Abierto
43
Consideraciones finales.
 No se ha demostrado si los procesos de factorizar el módulo
RSA y romper el criptosistema son equivalentes.
 Hay otros criptosistemas del estilo RSA para los que sí se ha
demostrado dicha equivalencia: criptosistemas de Williams
(1980), Kurosawa (1988), Loxton (1992),...
44
Criptosistema de ElGamal: claves
Generación de claves:
1. Se elige un número primo grande: p.
2. Se considera el grupo (Zp)* (en general, se puede considerar un
grupo finito G) cuyo orden es (p – 1).
3. Se elige un generador del grupo .
4. Se selecciona un número aleatorio 0 < a < p – 1 y se calcula
a (mod p)
45
Criptosistema de ElGamal: claves
Generación de claves:
La clave pública es (p, , a).
La clave privada es el número a.
46
Criptosistema de ElGamal: cifrado y descifrado
Cifrado:
1.
B obtiene la clave pública de A: (p, , a),
2.
B representa el mensaje que quiere enviar, m, en el conjunto
{0, 1, ..., p – 1}, troceándolo si es preciso,
3.
B genera un número aleatorio v, 0 < v < p – 1,
4.
B calcula   v (mod. p), y   m ·(a)v (mod. p).
5.
B envía a A el par (,).
47
Criptosistema de ElGamal: cifrado y descifrado
Descifrado:
1.
A utiliza su clave privada, a, para calcular
 a  (v)a (mod. p) en G y su inverso p – 1 – a (mod. p)
2.
El resultado lo multiplica por  para obtener m:
p – 1 – a    – a m a (mod. p)  m (mod. p)
48
Criptosistema de ElGamal: seguridad
Por seguridad y eficacia, el grupo G y el elemento  deben
elegirse de forma que se verifiquen las siguientes condiciones:
La operación en G debería ser “fácil” de aplicar.
Por seguridad el problema del logaritmo discreto en el subgrupo
cíclico de G generado por  debería ser “difícil”.
49
Ejemplo ElGamal: determinación de la clave.
Consideremos p = 15485863, el grupo (Z15485863)* y un generador
de dicho grupo  = 7.
 A elige a=28236 y calcula
a  728236 12506884 (mod. 15485863)
Este par es la clave privada y pública de A.
 B elige b=21702 y calcula
b 721702 8890431 (mod. 15485863)
Este par es la clave privada y pública de B.
50
Ejemplo ElGamal: cifrado del mensaje.
Supongamos que A quiere mandar a B el mensaje m=HIJO
Codificamos el mensaje utilizando el alfabeto de 26 letras:
H7, I8, J9,O 14
con lo que el mensaje sería:
m = 7 · 263+8 · 262+9 · 26+14 = 128688
51
Ejemplo ElGamal: cifrado del mensaje.
A elige el número v = 480 y calcula
  7480 (mod. 15485863)  12001315 (mod. 15485863)
(b)v  8890431480  9846598 (mod. 15485863)
  m ·(a)v  1286688 · 9846598  8263449 (mod. 15485863)
52
Ejemplo ElGamal: cifrado del mensaje.
A codifica la pareja (12001315, 8263449) en base 26:
12001315= 1 · 265 +0 · 264 +6 · 263+21 · 262+11 · 26+1 BAGVLB
8263449= 18 · 264 +2 · 263+4 · 262+0 · 26+25  SCEAZ
y envía a B la pareja (BAGVLB, SCEAZ).
53
Ejemplo ElGamal: descifrado del mensaje.
B codifica la pareja (BAGVLB, SCEAZ) en base 26:
BAGVLB = 1·265+0·264+6·263+21·262+11·26+1 = 12001315 = 
SCEAZ= 18·264+2·263+4·262+0·26+25 = 8263449 = 
B calcula  b  1200131521702  9846598 (mod. 15485863)
y su inverso 
p–1–b
1200131515464160 14823281 (mod.
15485863)
54
Ejemplo ElGamal: descifrado del mensaje.
Finalmente B calcula el mensaje inicial:
p – 1 – a   14823281 · 8263449  128688 (mod. 15485863)
que codificado en base 26 es el mensaje inicial:
128688 = 7 · 263+8 · 262+9 · 26+14  HIJO
55
Firma digital ElGamal.
El esquema diseñado por ElGamal para firmar digitalmente un
mensaje es el siguiente:
 A genera un número aleatorio h tal que MCD(h,p-1)=1.
 A calcula el elemento r h (mod. p) .
 A resuelve la congruencia m  a · r +h ·s (mod. p-1).
La firma digital de A para el mensaje m es el par (r,s).
56
Firma digital ElGamal.
Para que el receptor B del mensaje compruebe la firma de A
realiza el siguiente protocolo:
 B calcula rs (h)s (mod. p)
 B calcula el elemento (a)r (mod. p)
 B calcula (a)r · (h)s (mod. p) y comprueba que es igual a
m (mod. p)
57
Firma digital ElGamal.
Para conseguir la falsificación de la firma de A en el mensaje m,
un escucha tendría que resolver la ecuación
m =(a)r · rs
con las incógnitas r y s. Si fija r y trata de resolver la ecuación en
s se encontraría con un problema de logaritmo discreto, mientras
que si fija s e intenta resolver la ecuación para r se encontraría
con una congruencia exponencial mixta para la que no hay
algoritmo conocido (Problema de la firma digital de ElGamal)
58
Problema del Logaritmo Discreto
 Sea G un grupo multiplicativo cíclico de orden n. Dados un
generador g  G, y un elemento e  G, el problema del logaritmo
discreto (PLD) en G consiste en calcular un entero x , 0  x  n - 1,
de modo que gx = e.
 Este problema (computacionalmente difícil) es la base de varios
criptosistemas (cambio de clave de Diffie-Hellman, ElGamal) y de
varios esquemas de firma digital (ElGamal y Digital Signature
Standard, DSS).
59
Grupos para el PLD
 Grupo multiplicativo de un cuerpo finito: Zp*.
 Grupo multiplicativo de un cuerpo finito de característica 2.
 Subgrupo propio del grupo multiplicativo de un cuerpo finito.
 El grupo de las unidadades de Zn*, siendo n un entero
compuesto.
 El grupo de puntos de una curva elíptica definida sobre un
cuerpo finito.
 El jacobiano de una curva hiperelíptica definida sobre un
cuerpo finito.
60
Grupos para el PLD

Se puede resolver en PLD sobre Zp* en un tiempo subexponencial:
exp((1.923 + o(1))(log p)1/3(log log p)2/3), por lo que p debería
elegirse muy grande (210 bits), lo que lleva a problemas
computacionales (tiempo y espacio).

Se debe mantener la dificultad computacional del problema,
reducir el tamaño de las claves para utilizar menor tiempo de
computación y utilizar menor espacio físico (menor amplitud de
banda para facilitar la implementación en tarjetas inteligentes,
teléfonos móviles, localizadores personales, etc.)
61
Bibliografía (1)
 W.
Diffie and M. Hellman, New directions in Cryptography,
IEEE Trans. Inform. Theory 22 (1976), 644-654.
 R. Durán Díaz, L. Hernández Encinas y J. Muñoz Masqué, El
criptosistema RSA, RA-MA, Madrid, 2005.
 T. ElGamal, A public key cryptosystem and a signature scheme
based on discrete logarithms, IEEE Trans. Inform. Theory 31
(1985), 469-472.
 A. Fúster Sabater, D. Guía Martínez, L. Hernández Encinas, F.
Montoya Vitini y J. Muñoz Masqué, Técnicas criptográficas de
protección de datos, RA-MA, Madrid, 3ª ed., 2004.
62
Bibliografía (2)
 N.
Koblitz, A course in number theory and cryptography,
Springer-Verlag, 2ª ed., Berlín, 1994.
 A. Menezes, P. van Oorschot and S. Vanstone, Handbook of
applied Cryptography, CRC Press, Boca Raton, FL., 1997.
 R. Rivest, A. Shamir and L. Adleman, A method for obtaining
digital signatures and public-key cryptosystems, Comm. of the
ACM 21 (1978), 120-126.
 S. Singh, Los códigos secretos, Debate, Barcelona, 2000.
63
Esquema de la charla
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
Introducción
Identificación amigo-enemigo
Lanzamiento de una moneda por teléfono
Póquer por teléfono
El problema del millonario
Venta de secretos
Conocimiento nulo
Transferencia inconsciente
Intercambio de secretos
Firma de un contrato
Correo con acuse de recibo
Voto electrónico
Otros protocolos
64
Introducción: definición

Protocolo. (Del b. lat. protocollum, y este del gr.
πρωτκολλον). Plan escrito y detallado de un experimento
científico, un ensayo clínico o una actuación médica.
(Diccionario de la Real Academia Española de la Lengua)
 Protocolo. Es el conjunto de acciones coordinadas que
realizan dos o más partes o entidades con el objeto de llevar a
cabo un intercambio de datos o información.
 Los Protocolos criptográficos serán aquellos que cumplen
esta función usando para ello algoritmos y métodos
criptográficos.
 Su objetivo es dar una solución a distintos problemas de la
vida real, especialmente aquellos en donde puede existir un
grado de desconfianza entre las partes.
65
Introducción: ejemplos
1.- El problema de la identificación del usuario
¿Cómo permitir que un usuario se identifique y autentique ante
una máquina -y viceversa- con una clave, password y no pueda
ser suplantado por un tercero?
2.- El problema del lanzamiento de la moneda
¿Cómo permitir que dos usuarios realicen una prueba con
probabilidad ½ -como es el lanzamiento de una moneda- si éstos
no se encuentran físicamente frente a frente y, a la vez, asegurar
que ninguno de los dos hace trampa?
66
Introducción: ejemplos
3.- El problema de la firma de contratos
¿Cómo permitir que dos o más usuarios que se encuentran
físicamente alejados puedan realizar la firma de un contrato,
asegurando que ninguno de los firmantes va a modificar las
condiciones ni negarse a última hora a dicha firma?
4.- El problema del descubrimiento mínimo de un secreto
¿Cómo poder demostrar y convencer a otra persona o a un
sistema que uno está en posesión de un secreto, sin por ello tener
que desvelarlo ni a ella ni a un tercero?
67
Introducción: ejemplos
5.- El problema del juego de póquer mental o por teléfono
¿Cómo permitir que dos o más usuarios puedan jugar a través de la
red una partida de póquer -o de cualquier otro juego de cartas - si
no están físicamente en una misma mesa de juego y asegurando, al
mismo tiempo, que ninguno de ellos va a hacer trampa?
6.- El problema de la división de un secreto o del umbral
Si tenemos un único secreto, y por tanto muy vulnerable,
¿cómo permitir que ese secreto sea dividido en n partes,
de forma que juntando al menos k < n partes sea posible
reconstruirlo y, en cambio, con k - 1 partes, sea imposible
su reconstrucción?
68
Introducción: ejemplos
7.- El problema del esquema electoral o voto electrónico
¿Cómo realizar unas elecciones a través de una red, de forma que
pueda asegurarse que el voto es único y secreto, que los votantes y
mesas estén autenticados, y se pueda comprobar que el voto se
contabiliza adecuadamente?
8.- El problema de la transmisión por canales subliminales
Dos usuarios desean intercambiar información a través de un
tercero del cual desconfían. ¿Cómo pueden hacerlo sin cifrar la
información de forma que este tercero sólo vea un mensaje con
texto en claro aparentemente inocente?
69
Introducción: ejemplos
9.- El problema del millonario
Dos usuarios desean conocer cuál de los dos tiene más dinero en su
cuenta corriente. ¿Cómo pueden hacerlo de forma que, una vez
terminado el protocolo, ambos sepan quién de los dos es más rico
sin por ello desvelar el dinero que tiene el otro?
10.- El problema del correo electrónico con acuse de recibo
¿Cómo hacer que una vez recibido un correo electrónico, éste sólo
pueda ser leído (abierto) si el receptor envía, con anterioridad al
emisor, un acuse de recibo como sucede de forma similar con el
correo ordinario certificado?
70
Introducción: ejemplos
¿Cómo podemos calcular la edad media de un grupo de personas
sin conocer la edad de cada una de las personas?
...
A  E1
A  10
aleatorio
( A  E1 )  E 2
3
...
( A  E 1    E n 1 )  E n
( A  E1    E n )  A
 media
n
71
Identificación Amigo-Enemigo
¿?
El avión A le envía un reto al avión B, sabiendo que sólo lo
puede resolver si cuenta con alguna información que sólo
comparte con sus aliados. Si es capaz de devolverle el reto
resuelto le considerará amigo, en otro caso supondrá que es
un enemigo.
Podemos utilizar la clave pública para desarrollar un
protocolo de identificación amigo-enemigo
72
Identificación Amigo-Enemigo
 Cada usuario Ui , i = 1,..., k, posee en su terminal sus claves
RSA, pública y privada: pi y si, y las claves públicas de todos sus
aliados: pj , j = 1,..., k, j  i .
 Si el usuario Ui quiere verificar la identidad del usuario Uj
procede como sigue:
 Ui genera un mensaje aleatorio, m, lo cifra utilizando la
clave pública de Uj , c = Epj(m) y se lo envía.
 Uj descifra el mensaje recibido m ≡ Dsj(c) y se lo devuelve a
Ui, en un plazo previamente acordado.
 Ui compara el mensaje recibido con el mensaje original. En
caso de coincidencia, Uj es amigo y en otro caso, enemigo.
73
Lanzamiento de una moneda por
teléfono
Dos personas han de tomar una decisión por teléfono y para
ello una de ellas lanza una moneda al aire. ¿Es posible diseñar
algún protocolo que evite hacer trampas?
74
Lanzamiento de una moneda por
teléfono
 A elige dos números primos grandes, p y q, y comunica su
producto, n = p·q, a B.
 B elige un número aleatorio u (1, n/2), y comunica a A el valor
z = u2(mod n) .
 A calcula las cuatro raíces de z módulo n:  x,  y. Si x e y son
los mínimos valores para  x,  y, respectivamente, se tiene que u
= x y v = y.
 A hace la hipótesis de si u = x o u = y, es decir, halla el menor i
de modo que el i-ésimo bit de x es distinto del i-ésimo bit de y, y le
comunica a B su hipótesis: “el i-ésimo bit de u es 0” ó “el i-ésimo
bit de u es 1”.
75
Lanzamiento de una moneda por
teléfono
 B responde a A si su hipótesis es correcta o no.
 B da a conocer a A el número u.
 A muestra a B la factorización de n.
Nota: A no puede saber el valor de u; por tanto, la probabilidad de
que su hipótesis sea cierta es del 50%. Si B quisiera hacer trampa
cambiando u después de conocer la hipótesis de A, es porque
conocería x e y, por lo que podría factorizar n. Para evitarlo A no
comunica x ó y a B, sino un solo bit de su hipótesis.
76
Póquer por teléfono
A y B quieren jugar una partida de póquer por teléfono sin trampas
y sin que haya un árbitro.
Las condiciones de la partida de póquer son las siguientes:
1. Uno de ellos baraja y el otro reparte.
2. Cada mano tiene 5 cartas y todas ellas son equiprobables.
3. Las manos de A y B son disjuntas.
4. Cada jugador conoce sus cartas pero no las del adversario.
5. Cada jugador debe poder conocer si el adversario hace trampa.
77
Póquer por teléfono
Sean (pA , sA) y (pB , sB) las parejas de claves pública/privada de los
usuarios A y B, de tal forma que el criptosistema de clave pública
sea conmutativo:
EpA (EpB(m)) = EpB (EpA(m)) .
El protocolo es como sigue:
 B cifra (baraja) las 52 cartas con su clave pública y las envía a A
ordenadas de manera aleatoria:
c1 = EpB(cp(1)) ,..., c52 = EpB(cp(52)) .
 A elige sus cinco cartas, cj1,...,cj5, las cifra con su clave pública y
se las envía a B:
EpA(cj1) ,..., EpA(cj5)
78
Póquer por teléfono
 B descifra con su clave privada las 5 cartas y se las devuelve a A:
ESB(EpA(cj1)) = EpA(cj1) ,..., ESB(EpA(cj5)) = EpA(cj5) .
 A descifra con su clave privada las 5 cartas recibidas y conoce su
mano:
ESA(EpA(cj1)) = cj1 ,..., ESA(EpA(cj5)) = cj5.
 A elige la mano de B (de entre las cartas cifradas por A y no
pertenecientes a su mano) y le envía las cartas a B: ci1,...,ci5 .
 B descrifra con su clave secreta estas 5 cartas, obteniendo así su
mano:
ESB(ci1) = ci1 ,..., ESB(ci5) = ci5.
79
El problema del millonario
Dos millonarios quieren saber cuál de los dos es más rico pero
sin que ninguno conozca la fortuna del otro.
Supongamos que FA es la fortuna de A y que FB es la fortuna de
B. Utilizaremos el criptosistema RSA para diseñar un protocolo
que permita llevar a cabo el deseo de los millonarios.
Supongamos, además, que FA, FB < 100.
80
El problema del millonario
Sean (nA, eA), dA y (nB, eB), dB las claves públicas y privadas de A
y B, respectivamente.
El protocolo es como sigue:
 B elige un número aleatorio grande x, acotado por un valor
fijado de antemano, y lo cifra con la clave pública de A:
k  x
eA
 mod n A  .
 B da a conocer a A el valor del número k - FB .
 A calcula de manera secreta los números:
y i  k  F B  i 
dA
 mod n A  , 1  i  100 .
81
El problema del millonario
 A elige un número primo grande p < x , y calcula los números:
z i  y i  mod p  ,
1  i  100 .
Para cada uno de estos valores, A verifica que
 zi  z j  2

 0  zi  p
i ,j  i ,
En caso contrario, A elegiría otro número primo p.
 A da a conocer a B la siguiente sucesión ordenada de números:
z1 , z 2 ,  , z F , z F
A
A
1
 1, z F
A
2
 1,  , z 100  1, p .
 B prueba si el FB-ésimo número de la sucesión es congruente
con x módulo p. Si es así, entonces FA  FB; en caso contrario se
tendrá que FB > FA.
82
Venta de secretos
Imaginemos que una persona decide crear un negocio de venta
de secretos de tal forma que cuando alguien le compra uno,
sabe que ha hecho una venta pero no sabe qué secreto en
concreto ha vendido. ¿Es posible diseñar un protocolo para
conseguir tal fin?
83
Venta de secretos
 Supongamos que A posee varios secretos para vender: s1,...,sk ,
e imaginemos que B quiere comprarle uno de ellos: sj .
El protocolo es como sigue:
 A construye k criptosistemas RSA de claves (ni, ei) y di, de tal
forma que pi, qi ≡ 3 (mod 4).
 A dice a B las k claves públicas, (ni, ei), y los secretos cifrados
c i  s i  mod n i  .
ei
B elige al azar k números x1,..., xk , calcula sus cuadrados
módulo ni , x i2  mod n i  , y sus símbolos de Jacobi:
 xi 
 
 ni 
84
Venta de secretos
 B comunica a A los siguientes valores:
x 1  mod n 1 
2
 x1 
 
 n1 


x j mod n j  
2
 xj

n
 j





x k  mod n k 
2
 xk 


n
 k
 A calcula las raíces cuadradas de los valores recibidos y
comunica a B las que corresponden a los símbolos de Jacobi de
la lista.
 Entonces B posee dos raíces cuadradas diferentes de
x j mod n j 
2
por lo que puede factorizar el módulo nj y obtener el secreto sj.
85
Descubrimiento mínimo
Debemos convencer a una persona de que
poseemos cierta información secreta sin
revelarle nada de dicha información
(Conocimiento nulo)
86
Descubrimiento mínimo
 A posee una información y desea convencer a B de ello, pero sin
darle tal información. Determinar cuál es la mínima cantidad de
información que A debe revelar a B para que este último se
convenza de que el primero posee la información que dice
El protocolo es como sigue:
 A comunica a B que conoce la factorización del módulo RSA n =
p·q.
 B elige un número entero aleatorio x y comunica a A el valor de
x4(mod n) .
 A calcula las raíces cuadradas de x4(mod n) y comunica a B el
valor de una de ellas: x2(mod n) .
 B comprueba que el valor enviado por A es una raíz cuadrada de
x4(mod n) , elevando al cuadrado tal valor.
87
Transferencia inconsciente
Supongamos que la persona A conoce un secreto.
Vamos a diseñar un protocolo (basado en el criptosistema RSA)
mediante el cual A da a conocer a otra persona B dicho secreto
con una probabilidad del 50%, sin que al finalizar el mismo, A
sepa si B conoce el secreto o no.
88
Transferencia inconsciente
Sin pérdida de generalidad podemos suponer que el secreto que
A posee es la factorización del módulo RSA, n = p·q.
El protocolo es como sigue:
 B elige un número x y da a conocer a A el valor de x2 (mod n).
 A calcula las cuatro raíces cuadradas de x2 (mod n), que son  x
y  y, y da a conocer sólo una de ellas, u, a B. (Obsérvese que A
no sabe cuál de ellas es x)
 B comprueba si u es congruente con  x (mod n). Si es así, B
no obtiene ninguna información nueva; en caso contrario, B
obtendría dos raíces cuadradas diferentes de n, y podría
factorizarlo.
 A no sabe cuál de las dos situaciones es en la que se encuentra
B, por lo que no sabe si al final B consiguió o no el secreto.
89
Intercambio de secretos
Supongamos que dos personas, A y B, conocen sendos secretos
de tal forma que quieren intercambiarlos de modo que ninguno
dé a conocer su secreto sin recibir el secreto del otro.
Diseñaremos un método basado en el criptosistema RSA que nos
permita implementar dicho protocolo.
90
Intercambio de secretos
El protocolo es como sigue:
 A y B se ponen de acuerdo en el tamaño de sus claves RSA:
(nA, eA), dA, y (nB, eB), dB, de tal forma que pA, qA, pB, qB ≡ 3
(mod 4).
 A y B cifran sus secretos y los intercambian con sus claves
públicas.
 A y B eligen, respectivamente:
a i  Z n
bi  Z  n
A
B
1  / 2
,
1  i  100
1  / 2
,
1  i  100
 A y B se intercambian los valores de:
a i  mod n B  ,
1  i  100
b i  mod n A  ,
1  i  100
2
2
91
Intercambio de secretos
 A y B calculan las cuatro raíces cuadradas módulo nA y nB de
cada valor recibido y seleccionan las dos más pequeñas.
 A y B se intercambian los 100 pares de raíces cuadradas,
enviando 100 pares de bits cada vez, comenzando por los bits
más significativos y verificando que los valores recibidos son
restos cuadráticos (para evitar trampas).
 A y B conocen dos raíces distintas de cada bi y ai, con lo que
pueden factorizar el módulo RSA del otro y descubrir el secreto
que cifró.
92
Firma de un contrato
Dos personas quieren firmar un contrato a través de una red,
de modo que ninguno de ellos pueda romper el protocolo con
la firma del otro y sin firmar su parte.
Se puede utilizar los criptosistemas de clave pública para
diseñar un protocolo que les permita firmar el contrato de
manera segura.
93
Firma de un contrato
El protocolo es como sigue:
 A y B se ponen de acuerdo en el tamaño de los módulos RSA
que van a utilizar y se intercambian sus respectivas claves
públicas: (nA, eA) y (nB, eB),
 A envía a B un contrato firmado utilizando su firma digital
(es decir, firmado mediante su clave privada, dA), en el que
asegura que el contrato es válido si B sabe cómo factorizar nA.
 B procede de manera análoga enviando su contrato firmado
digitalmente mediante su clave privada dB .
 Una vez que cada participante ha leído el contrato firmado
digitalmente por la otra parte y ha verificado la firma digital,
se intercambian los factores primos de los respectivos módulos
haciendo uso del protocolo de intercambio de secretos.
94
Correo con acuse de recibo
Una persona A quiere enviar un correo, m, a
otra persona B, de modo que B pueda leer
dicho correo sólo si A obtiene la
confirmación de recepción por parte de B.
Utilizaremos el criptosistema RSA para
diseñar un protocolo que le permita a B leer
el mensaje una vez que A obtiene el acuse de
recibo.
95
Correo con acuse de recibo
El protocolo es como sigue:
 A envía a B su clave pública.
 B envía a A su clave pública junto con el acuerdo firmado
digitalmente (con su clave privada) de que si A puede factorizar
nB, entonces B factoriza nA y obtiene cualquier correo, m, que
esté cifrado por A.
 A y B se intercambian los factores primos de sus módulos
mediante el protocolo de intercambio de secretos.
 Cuando B factoriza nA, puede leer el correo enviado por A.
 Como A factoriza nB, obtiene el certificado firmado por B.
96
Voto electrónico
Todos tenemos de una u otra forma una idea
intuitiva, aunque quizás no completa, sobre
cómo se desarrolla un proceso electoral.
La pregunta es si es posible realizar este tipo de
eventos desde Internet, lo que se conoce como
esquema electoral.
La respuesta es sí con la ayuda de técnicas y
protocolos criptográficos aunque no se trata sólo
de un problema de implementación técnica; es
menester tener en cuenta otros factores
importantes,
a
saber:
Socio-políticos,
económicos, jurídicos, legislativos...
97
Voto electrónico
“Un esquema de votación electrónica es una aplicación
distribuida y constituida por un conjunto de mecanismos
criptográficos y protocolos que, de forma conjunta, permiten
que se realicen elecciones en una red de computadores, de
forma segura, incluso suponiendo que los electores legítimos
pueden tener un comportamiento malicioso.”
Andreu Riera
Tesis Doctoral
Universidad Autónoma de Barcelona, España, 1999.
98
Voto electrónico
Requisitos de un esquema electoral:
 Sólo pueden votar quienes estén censados.
 El voto debe ser secreto.
 El voto debe ser único por cada votante.
 Se contabilizarán todos los votos válidos.
 El recuento parcial no debe afectar a votos que se emitan con
posterioridad.
 Cada votante debe poder comprobar que su voto ha sido tenido
en cuenta en el escrutinio.
 Se debe proteger el proceso contra ataques en red.
 El proceso debe ser factible, práctico y, dentro de lo posible, de
uso universal.
99
Voto electrónico
Primera aproximación del voto electrónico
MCV = Mesa Central de Votación
 El votante cifra su voto con la clave pública de MCV.
 El votante envía su voto a la MCV.
 La MCV descifra el voto y lo contabiliza.
 La MCV hace público el resultado.
¿Qué problemas presenta este esquema? TODOS...
La MCV no sabe de dónde vienen los votos, si éstos son válidos o
no y si alguien vota más de una vez. Además puede conocer la
identidad del votante por lo que se vulnera el secreto del voto. Lo
único que aquí se protege es el secreto del voto ante terceros.
100
Voto electrónico
Segunda aproximación del voto electrónico
 El votante firma su voto con su clave privada y lo cifra luego con
la clave pública de MCV.
 El votante envía su voto a la MCV.
 La MCV descifra el voto, lo contabiliza y hace público el
resultado.
¿Qué problema tenemos ahora?
En este nuevo esquema se satisface que cada votante autorizado
vote una sola vez, no obstante seguimos vulnerando el secreto del
voto ante la MCV.
101
Voto electrónico
Tercera aproximación del voto electrónico
El tercer esquema contempla dos mesas:
MCV = Mesa Central de Votación
MCL = Mesa Central de Legitimación
 La MCL evita que la MCV conozca a quién ha votado el votante,
mediante un protocolo entre ambas, y además gestionan una lista
de votantes censados.
 La MCL y la MCV deben ser organismos diferentes.
102
Voto electrónico
El protocolo es como sigue:
 El votante A envía a la MCL el mensaje: “Buenos días, soy A
y vengo a votar”
 La MCL verifica si A está censado. Si no es un votante
legítimo rechaza la solicitud. Si es legítimo, le envía un
número aleatorio de identificación único i(A) y le borra de la
lista para impedir que vuelva a votar.
Nota. El número i(A) debe ser mucho mayor que el número de
votantes. Por ejemplo, para un millón de votantes, unos 10100
números.
 La MCL envía a la MCV la lista de números de validación.
103
Voto electrónico
 El votante A escoge una identificación secreta s(A) y envía a la
MCV el mensaje formado por el trío [i(A), v(A), s(A), donde i(A)
es su identificación, v(A) es su voto y s(A) es su número secreto.
Nota. Puede generarlo internamente con su sistema de cifra. Será
también un valor de muchos dígitos.
 La MCV verifica que el número i(A) de identificación se
encuentra en el conjunto N de los números censados y cruza los
datos para evitar que se vote más de una vez.
 Seguidamente quita i(A) del conjunto N y añade s(A) al conjunto
de electores que han optado por la opción v(A).
 La MCV contabiliza los votos y hace público el resultado, junto
con la lista de números secretos s(A) que han votado a la opción
v(A).
104
Voto electrónico
Algunas consideraciones sobre este protocolo
 Obsérvese que cada elector puede comprobar si su voto ha sido
contabilizado sin hacer pública su opción.
 ¿Qué pasa si MCV y MCL no son independientes?
Si las dos mesas, MCV y MCL, no tienen la idoneidad y la
integridad que se presume, la solución está en el uso de una
diversidad de esquemas más desarrollados que evitan esta
anomalía mediante protocolos, entre ellos ANDOS (All-orNothing Disclosure Of Secrets) Distribución Anónima de
Números de Validación.
105
Voto electrónico
Otros esquemas de mesas electorales
Hay muchos otros esquemas con dos mesas, una única mesa e
incluso ninguna, cada uno con sus características propias. Entre
ellos tenemos:
- Modelo de Cohen y Fisher (1985)
- Modelo de Fujioka y otros (1992)
- Modelo de Park y otros (1993)
- Modelo de Sako y Killian (1995)
- Modelo de Borrel y Rifà (1996)
106
Voto electrónico
Estado del arte
 Existen diversos modelos y esquemas, algunos de ellos
probados con éxito con un número reducido de electores.
 No está todavía bien solucionado el problema de la protección
física y lógica de la red ante ataques masivos, denegación de
servicio, etc. Es el principal problema al que se enfrentan estos
esquemas, su difícil escalabilidad en sistemas grandes y
abiertos.
 No obstante, el proceso de unas elecciones vía Internet
realizable, práctico y seguro en cuanto a la privacidad y
autenticidad, es completamente factible.
107
Otros protocolos: esquemas
umbrales
Existen otros protocolos criptográficos que no hacen uso de las
técnicas proporcionadas por la clave pública en su diseño, y no
por ello son menos importantes.
Entre ellos podemos señalar de manera destacada a los protocolos
para el reparto de secretos y, más concretamente, a los esquemas
(k, n)-umbrales.
Estos protocolos tienen un amplio abanico de aplicaciones:
• Apertura de cajas fuertes
• Lanzamiento de misiles
• Almacenamiento seguro de
claves criptográficas
108
Otros protocolos: esquemas
umbrales
 Grosso modo, un esquema (k, n)-umbral para el reparto de un
secreto, S, es un procedimiento por el cual, a partir del secreto S
se computan n sombras, S1 ,..., Sn , de tal forma que para poder
recuperar el secreto original es necesario juntar, al menos, k de
dichas sombras y no menos. De hecho, si se juntaran k – 1
sombras no se obtendría ninguna información sobre el secreto S.
 Las sombras son creadas por una persona de confianza mútua
(PCM).
 El esquema se dice que es ideal cuando el tamaño de las
sombras es igual o inferior al tamaño del secreto.
 El esquema (k, n)-umbral más famoso es el debido a Shamir
(1979) y está basado en la interpolación de Lagrange.
109
Otros protocolos: esquemas
umbrales
El esquema de Shamir es como sigue:
 Sea SZ el secreto a ser repartido.
 La PCM selecciona un primo p > max(S, n).
 Selecciona de manera aleatoria los números enteros:
a1, a2,…,ak1  Zp .
 Construye el polinomio: S + a1x + a2x2 +…+ak-1 x k1 Zp[x] .
 Las sombras a repartir son: Si = P(i) (mod p), 1 ≤ i ≤ n.
 Para recuperar el secreto se han de juntar, al menos, k sombras:
S1,…, Sk. En este caso tendríamos k puntos: (i, Si ), 1 ≤ i ≤ k, de
tal forma que el término independiente del polinomio
interpolador que pasa por ellos es S.
110
Otros protocolos: esquemas
umbrales
Como ejemplo, construiremos un esquema (3, 6)-umbral.
 Sea S = 16 el secreto a ser repartido.
 Se selecciona el primo p = 23 > max(16, 6).
 Se elige de forma aleatoria los enteros 2  Z23 , 23 Z23.
 Se construye el polinomio P(x) = 16 + 2x + 19x2  Z23[x] .
 Construimos las sombras:
S1 = P(1) = 14, S2 = P(2) = 4, S3 = P(3) = 9,
S4 = P(4) = 6, S5 = P(5) = 18, S6 = P(6) = 22.
 Juntando al menos tres sombras, S1, S3 y S6, el polinomio
interpolador que pasa por esos puntos es:
16 + 2x + 9x2  Z23[x].
111
Otros protocolos: criptografía visual
 Una variante de los esquemas umbrales es la denominada
criptográfia visual (Naor y Shamir, 1994).
 La imagen secreta se divide en 2 sombras que son repartidas
entre sendos participantes.
 Superponiendo dichas sombras se obtiene la imagen original
(con algo de “ruido”).
 Este esquema (2, n)-umbral se puede extender a un esquema (k,
n)-umbral cualquiera.
 Inicialmente la imagen secreta era en blanco y negro. Más
recientemente se han desarrollado protocolos similares para
imágenes en tonos de grises o en color.
112
Otros protocolos: criptografía visual
 La imagen secreta no es más que rectángulo dividido en
pixeles,
 Los pixeles que definen la imagen secreta son blancos y
negros.
 El esquema (2, 2)-umbral para dividir la imagen secreta
consiste en obtener de cada uno de los píxeles de la imagen
original, dos píxeles, cada uno de los cuales ocupará en lugar
del píxel original pero en cada una de las sombras.
 Cada uno de los píxeles de cada una de las sombras se
separará en otros cuatro píxeles, dos blancos y dos negros.
113
Otros protocolos: criptografía visual
El protocolo es como sigue:
 Se lanza una moneda al aire:
 Si el resultado es cara, se elige como píxeles para cada
una de las sombras los dos píxeles de la línea superior.
 Si es cruz elige como píxeles para cada sombra los dos
píxeles de la línea inferior.
114
Otros protocolos: criptografía visual
Obsérvese que:
 Cada pixel de la imagen original da lugar a dos pixeles,
uno para cada sombra.
 Los píxeles blancos pierden contraste al recuperar la
imagen original secreta.
 La obtención del cuádruple pixel blanco-negro o negroblanco de la sombra tiene la misma probabilidad (p = 0'5), y
no depende del color del pixel original,
 El proceso es aleatorio (lanzar una moneda) y los
resultados obtenidos en cada prueba son independientes (no
se obtiene información adicional si se observa un grupo de
píxeles en cualquiera de las sombras).
115
Otros protocolos: criptografía visual
Imagen original
Imagen recuperada
lanzamientos
c
x
c
c
x
x
c
c
c
x
c
c
x
x
x
c
x
c
x
x
c
c
x
c
x
c
x
c
c
c
c
x
x
x
c
x
x
x
x
x
c
x
c
c
c
c
x
c
x
x
x
c
x
x
x
c
c
x
c
x
c
c
c
x
Sombras
116
Otros protocolos: criptografía visual
117
Bibliografía

R. Durán Díaz, L. Hernández Encinas y J. Muñoz Masqué, El
criptosistema RSA, RA-MA, Madrid, 2005.
 A. Fúster Sabater, D. Guía Martínez, L. Hernández Encinas,
F. Montoya Vitini y J. Muñoz Masqué, Técnicas criptográficas
de protección de datos, RA-MA, Madrid, 3ª ed., 2004.
 A. Menezes, P. van Oorschot and S. Vanstone, Handbook of
applied Cryptography, CRC Press, Boca Raton, FL., 1997.
 J. Ramió Aguirre. Seguridad informática y Criptografía.
Material docente de libre distribución. Madrid 2005
118
Descargar

Universidad de Salamanca