sistema criptografico paillier
DESCRIPTION
Descripción del sistema de PaillierTRANSCRIPT
![Page 1: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/1.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Sistema criptografico de Paillier
Andres Arevalo, Marcio Abreu, Richar Contreras
Universidad Nacional de Colombia
18 de noviembre de 2014
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 2: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/2.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Contenido
1 Introduccion
2 El sistemaGeneracion de la llaveCifradoDescifrado
3 Ejemplo
4 PropiedadesPropiedades homomorficasAuto-cegamiento
5 Aplicaciones
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 3: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/3.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Introduccion
El sistema criptografico de Paillier, llamado ası e inventando por elinvestigador Frances Pascal Paillier en 1999, es un algoritmocriptografico de llave publica.La reconocida tecnica usada en la criptografıa de llave publica, esel uso de algoritmos de llaves asimetricas, donde la llave utilizadapara cifrar un mensaje no es la misma que se usa para descifrarlo.Cada usuario tiene un par de llaves – una llave publica y una llaveprivada. La llave privada se mantiene en secreto, mientras que lallave publica puede darse a conocer a cualquier persona. Losmensajes se cifran con la clave publica del destina
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 4: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/4.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Generacion de la llaveCifradoDescifrado
Generacion de la llave
Sea p y q dos numeros primos grandes, generados aleatoria eindependientemente. Tales que: gcd(pq, (p − 1)(q − 1)) = 1
Se calcula n = pq y λ = lcm(p − 1, q − 1)
Se selecciona un entero aleatorio g , tal que g ∈ Z∗n2
Se calcula:
µ = (L(gλ mod n2)−1) mod n
Donde, L(u) = u−1n
Se deja (n, g) como llave publica.
Se deja (λ, µ) como llave privada.
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 5: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/5.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Generacion de la llaveCifradoDescifrado
Cifrado
Sea m < n el mensaje que se desea cifrar.
Sea r un numero aleatorio, tal que r ∈ Z∗n
Entonces c = gmrn (mod n2)
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 6: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/6.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Generacion de la llaveCifradoDescifrado
Descifrado
Dado que el mensaje cifrado c ∈ Z∗n2
Entonces m = L(cλ (mod n2)) · µ (mod n)
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 7: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/7.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Ejemplo
Sea p = 97 y q = 101. gcd(97 ∗ 101, 96 ∗ 100) = 1
n = 97 ∗ 101 = 9797
λ = lcm(96, 100) = 2400
Se escoge un g = 3087.
Se calcula:
µ = (L(30872400 mod 97972)−1) mod 9797
2575−1 mod 9797 = 7674
Se deja (n, g) = (9797, 3087) como llave publica.
Se deja (λ, µ) = (2400, 7674) como llave privada.
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 8: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/8.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Ejemplo
r ∈ Z∗9797 c m
2363 56115403 7777
9619 61219314 7777
8199 48963276 7777
1181 61877860 7777
4395 1966977 7777
8190 87545516 7777
4128 48810041 7777
9483 17759524 7777
856 79558228 7777
3652 76319150 7777
Cuadro 1 : El mismo mensaje cifrado con diferentes r aleatorios
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 9: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/9.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Propiedades homomorficasAuto-cegamiento
Propiedades homomorficas
La funcion de cifrado m↔ gmrn mod n2 es adictivamentehomomorfica en Zn. El sistema obedece a las siguientesidentidades:
∀m,m1,m2 ∈ Zn y k ∈ N
D(E (m1)E (m2) mod n2) = m1 + m2 mod n
D(E (m)k mod n2) = km mod n
D(E (m1)gm2 mod n2) = m1 + m2 mod n
D(E (m1)m2 mod n2) = m1m2 mod n
D(E (m2)m1 mod n2) = m1m2 mod n
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 10: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/10.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Propiedades homomorficasAuto-cegamiento
Sistemas totalmente homomorficos
Los sistemas homomorficos anaden ”Ruido” cada vez que serealiza una operacion sobre el ciphertext, como consecuencia seesta limitado a un numero determinado de operecaciones antes deque el ruido interfiera demasiado en los datos reales.Un sistema totalmente homomorfico es aquel que cumple lapropiedad de homomorfismo tanto sobre la suma, como sobre elproducto, dichos sistemas existen y eliminan el problema del ruido.Craig consiguio evitar que el ruido quedara fuera de controlporque, tras realiazar un numero determinado de operaciones, losdatos se vuelven a cifrar (Sin descifrarlos previamente, es decir, elcifrado homomorfico realiza su propio cifrado).
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 11: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/11.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Propiedades homomorficasAuto-cegamiento
Sistemas totalmente homomorficos
Estamos muy lejos de ver esto implementado en las tecnologıasactuales, porque actualmente no estan preparadas para soportarlo.La razon es sencilla, el sistema homomorfico a secas, no elTotalmente cifrado (Fully Homomorfic) requiere para el sistemamas pequeno, el de 512 dimensiones, un ancho de palabra de200.000 bits, lo cual es enorme. La clave publica usada en elsistema totalmente homomorfico tiene un tamano de 17MB ynecesita 2.4 segundos para generarse usando la maquina estandarmas potente. El sistema mayor, el de 215, de 32768 dimensionesrequiere dos horas para generar la clave y ocupa 2.3GB.
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 12: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/12.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Propiedades homomorficasAuto-cegamiento
Auto-cegamiento
Cualquier texto cifrado puede ser cambiado publicamente por otrosin alterar el mensaje original.
∀m ∈ Zn y r ∈ N
D(E (m)rn mod n2) = m mod n
D(E (m)g rn mod n2) = m mod n
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier
![Page 13: Sistema Criptografico Paillier](https://reader036.vdocumento.com/reader036/viewer/2022072108/55cf8ec8550346703b958c65/html5/thumbnails/13.jpg)
IntroduccionEl sistema
EjemploPropiedadesAplicaciones
Aplicaciones
Voto electronico
Dinero electronico
El objetivo del sistema es garantizar que la informacion es valida,mientras que al mismo tiempo no se pueda revelar la identidad dela persona con la que se asocia dicha informacion.
Andres Arevalo, Marcio Abreu, Richar Contreras Sistema criptografico de Paillier