Criptografia II - A. Moreno

8/19/2019 Criptografia II - A. Moreno

1/243

El alfabeto de denici´on Los conjuntos Z n Criptograf́ıa Sistema de desplazamiento con MatLab

Criptograf́ıa II

A. Moreno

A. Moreno Universidad Nacional de ColombiaCriptograf́ıa II

http://find/


2/243


Contenido

1 El alfabeto de denición

2 Los conjuntos Zn

3 Criptograf́ıa

4 Sistema de desplazamiento con MatLab


http://find/


3/243


Contenido


2 Los conjuntos Zn

3 Criptograf́ıa



http://find/http://goback/


4/243


Contenido


2 Los conjuntos Zn

3 Criptograf́ıa



http://find/


5/243


Contenido


2 Los conjuntos Zn

3 Criptograf́ıa





6/243


Digital Watermarking-Marcas de agua digitales


l lf b d d ´ f́ d d l b

http://find/


7/243


Congruencia

El concepto de relación de congruencia es uno de los másimportantes en Criptograf́ıa.

El papel fundamental de una relación de congruencia denida enun conjunto es el de clasicar sus elementos. Frecuentemente, talclasicación permite estudiar las propiedades de un conjunto deforma eciente.

En Criptograf́ıa se usan principalmente relaciones de congruencia,denidas en el conjunto de los números enterosZ = {. . . , − 3, − 2, − 1, 0, 1, 2, 3, . . . } y en el conjunto de lospolinomios con coecientes, en unas estructuras algebraicasespeciales que denominamos anillos. De hecho Z , con la suma y lamultiplicación usuales constituye un anillo.


El lf b t d d i i´ L j t Z C i t f́ Si t d d l i t M tL b

http://find/


8/243


Congruencia





El alfabeto de denici´on Los conjuntos Z Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


9/243

El alfabeto de denici on Los conjuntos Z n Criptografıa Sistema de desplazamiento con MatLab

Congruencia





El alfabeto de denici´on Los conjuntos Z Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


10/243


Congruencia








11/243


Congruencia






http://find/


12/243

El alfabeto de denici on Los conjuntos n Criptografıa Sistema de desplazamiento con MatLab

Ejemplo

Por ejemplo p (x ) = x 3 + 12

x + 34

, es un polinomio con coecientesen el conjunto de los números racionales que notamos Q .



http://find/


13/243

j n p g p

DeniciónSi a, b ∈Z entonces notamos a | b si a divide b . En cuyo casoexiste un t ∈Z , tal que b = ta .

Si notamos Z+ el conjunto de los enteros positivos y p ∈Z + , estal que p solo es divisible por si mismo o 1 entonces p es unnúmero primo.



http://find/


14/243

j n p g p





http://find/


15/243





http://find/


16/243

Ejemplo

2, 3, 5, 7, 17, 19, 61, 89 son números primos y sus correspondientesprimos de Mersenne. Esto es, de la forma 2n − 1.

2305843009213693951, el último encontrado de este tipo(12/04/2009), tiene la forma 2 43112609 − 1, con 12837064, diǵıtos.



http://find/


17/243

Ejemplo





http://find/


18/243

Ejemplo





http://find/


19/243

Ejemplo





http://find/


20/243

El algoritmo AKS

Determinar de forma eciente, que números son primos es unproblema de gran trascendencia en Matemáticas y Ciencias de laComputación.

Muchos de los algoritmos que realizan este tipo cálculo son de tipoprobab́ılistico, como el de Solovay-Strassen.

Debemos anotar que la primera solución a este problema se ladebemos a Agrawal, Saxena y Kayal (U. Kanpur-2002) quienes

encontraron el algoritmo que ahora conocemos como el algoritmoAKS, el cual determina de manera eciente la primalidad de unnúmero n dado.



http://find/


21/243

El algoritmo AKS







http://find/


22/243

El algoritmo AKS







http://find/


23/243

El algoritmo AKS







http://find/


24/243

DeniciónSi a, b ∈Z entonces a ≡ b mod n, (se lee, a es congruente con b módulo n), si y solo si existe un entero t , tal que a − b = tn .



http://find/


25/243

Partici ón de ZLa relación de congruencia denida en Z , podemos decir que parte

o particiona el conjunto de los enteros en n conjuntos los cualesdenominamos clases.

Esto es, cada clase consta de números congruentes y el conjuntode todas las clases A lo notamos Zn .

Debemos anotar que Z =[ j ]∈A

[ j ]. Lo que signica que la uni´on de

todas las clases es el conjunto de los números enteros. Además, eneste caso se tiene que

[i ] ∩ [ j ] = ∅ si i = j ,

por lo que clases distintas no tienen elementos comunes.



http://find/


26/243







[i ] ∩ [ j ] = ∅ si i = j ,




http://find/


27/243







[i ] ∩ [ j ] = ∅ si i = j ,




http://find/


28/243







[i ] ∩ [ j ] = ∅ si i = j ,






29/243







[i ] ∩ [ j ] = ∅ si i = j ,




http://find/


30/243







[i ] ∩ [ j ] = ∅ si i = j ,




http://find/


31/243

Ejemplo

Si n = 2, entonces Z2 = {[0], [1]} o simplemente escribimos

Z 2 = {0, 1}.

Note que módulo 2

[0] = {. . . , − 4, − 2, 0, 2, 4, . . . }

[1] = {. . . , − 5, − 3, − 1, 1, 3, . . . }.

Z 3 = {[0], [1], [2]},

[0] = {. . . , − 6, − 3, 0, 3, 6, . . . },

[1] = {. . . , − 5, − 2, 1, 4, 7, . . . },

[2] = {. . . , − 4, − 1, 2, 5, . . . }.A. Moreno Universidad Nacional de ColombiaCriptograf́ıa II




32/243

Ejemplo


Z 2 = {0, 1}.

Note que módulo 2

[0] = {. . . , − 4, − 2, 0, 2, 4, . . . }

[1] = {. . . , − 5, − 3, − 1, 1, 3, . . . }.

Z 3 = {[0], [1], [2]},

[0] = {. . . , − 6, − 3, 0, 3, 6, . . . },

[1] = {. . . , − 5, − 2, 1, 4, 7, . . . },





33/243

Ejemplo


Z 2 = {0, 1}.Note que módulo 2

[0] = {. . . , − 4, − 2, 0, 2, 4, . . . }

[1] = {. . . , − 5, − 3, − 1, 1, 3, . . . }.

Z 3 = {[0], [1], [2]},

[0] = {. . . , − 6, − 3, 0, 3, 6, . . . },[1] = {. . . , − 5, − 2, 1, 4, 7, . . . },



http://find/


34/243

Ejemplo



[0] = {. . . , − 4, − 2, 0, 2, 4, . . . }

[1] = {. . . , − 5, − 3, − 1, 1, 3, . . . }.

Z 3 = {[0], [1], [2]},

[0] = {. . . , − 6, − 3, 0, 3, 6, . . . },[1] = {. . . , − 5, − 2, 1, 4, 7, . . . },



http://find/


35/243

Ejemplo



[0] = {. . . , − 4, − 2, 0, 2, 4, . . . }

[1] = {. . . , − 5, − 3, − 1, 1, 3, . . . }.

Z 3 = {[0], [1], [2]},

[0] = {. . . , − 6, − 3, 0, 3, 6, . . . },[1] = {. . . , − 5, − 2, 1, 4, 7, . . . },



http://find/


36/243

Ejemplo



[0] = {. . . , − 4, − 2, 0, 2, 4, . . . }

[1] = {. . . , − 5, − 3, − 1, 1, 3, . . . }.

Z 3 = {[0], [1], [2]},

[0] = {. . . , − 6, − 3, 0, 3, 6, . . . },[1] = {. . . , − 5, − 2, 1, 4, 7, . . . },



http://find/


37/243

Z 12



http://find/


38/243

El abecedario en inglés puede ser asociado con Z26 . de forma talque :

A → 0, B → 1, C → 2, . . . Z → 25.



http://find/


39/243

El abecedario en inglés puede ser asociado con Z26 . de forma talque :

A → 0, B → 1, C → 2, . . . Z → 25.



http://find/


40/243

DeniciónPara n jo podemos denir la suma y multiplicación en Zn , deforma tal que

[i ] + [ j ] = [i + j ].

[i ] · [ j ] = [i · j ].



http://find/


41/243


[i ] + [ j ] = [i + j ].

[i ] · [ j ] = [i · j ].



http://find/


42/243


[i ] + [ j ] = [i + j ].

[i ] · [ j ] = [i · j ].



http://find/


43/243


[i ] + [ j ] = [i + j ].

[i ] · [ j ] = [i · j ].



http://find/


44/243

Ejemplo

En Z2 y Z3, se tiene que :

+ 0 10 0 11 1 0

,+ 0 1 20 0 1 21 1 2 0



http://find/


45/243

Ejemplo

En Z3 y Z4, se tiene que :

· 1 21 1 22 2 1

· 1 2 31 1 2 32 2 0 2

3 1 2 1


El alfabeto de denici´on Los conjuntos Z

n Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


46/243

EjemploEn Z6 :

· 1 2 3 4 51 1 2 3 4 52 2 4 0 2 43 3 0 3 0 34 4 2 0 4 25 5 4 3 2 1






47/243

Propiedades de las operaciones +, · en ZnPara n jo

1 Si a, b ∈Z n entonces a + b ∈Z n ,

2 a + ( b + c ) = ( a + b ) + c , para todo a, b , c ∈Z n ,

3 a + 0 = a, para todo a ∈Z n ,

4 a + ( − a) = 0, en donde [− a] = − [a] = [n − a], para todoa ∈Z n ,

5 a + b = b + a, para todo a, b ∈Z n .




http://find/


48/243










http://find/


49/243










http://find/


50/243












51/243










d d d l

http://find/


52/243










P i d d d l i Z

http://find/


53/243










P i d d d l i Z

http://find/


54/243








El alfabeto de denici´on Los conjuntos Zn

Criptograf́ıa Sistema de desplazamiento con MatLab

P i d d d l i + Z



55/243










Propiedades de las operaciones + en Z

http://find/


56/243










Propiedades de las operaciones + · en Z

http://find/


57/243









http://find/


58/243

Estructura algebraica de Zn

Las 5 propiedades anteriores, permiten que Zn , con esta operación

constituya un grupo abeliano.



http://find/


59/243

Propiedades de la multiplicación

1 Si a, b ∈Z n entonces a · b ∈Z n ,

2 a · (b · c ) = ( a · b ) · c , para todo a, b , c ∈Z n ,

3 a · 1 = a, para todo a ∈Z n ,

4 a · b = b · a, para todo a, b ∈Z n ,

5 a · (b + c ) = a · b + a · c .

Estas propiedades junto con aquellas de la suma logran que Zn ,sea un anillo conmutativo con unidad.



http://find/


60/243






5 a · (b + c ) = a · b + a · c .




P i d d d l l i li i´

http://find/


61/243






5 a · (b + c ) = a · b + a · c .




P i d d d l l i li i´

http://find/


62/243


1 Si a, b ∈

Zn entonces a · b ∈

Zn ,




5 a · (b + c ) = a · b + a · c .




P i d d d l lti li i´

http://find/


63/243

Propiedades de la multiplicacion

1 Si a, b ∈


Zn ,




5 a · (b + c ) = a · b + a · c .


A. Moreno Universidad Nacional de Colombia

Criptograf́ıa II



http://find/


64/243


1 Si a, b ∈


Zn ,




5 a · (b + c ) = a · b + a · c .



Criptograf́ıa II



http://find/


65/243


1 Si

a,b

∈Z

n entonces a

·b

∈Z

n ,2 a · (b · c ) = ( a · b ) · c , para todo a, b , c ∈Z n ,



5 a · (b + c ) = a · b + a · c .



Criptograf́ıa II



http://find/


66/243


1 Si

a,b

∈Z

n entonces a

·b

∈Z

n ,2 a · (b · c ) = ( a · b ) · c , para todo a, b , c ∈Z n ,



5 a · (b + c ) = a · b + a · c .



Criptograf́ıa II



http://find/


67/243


1 Si a, b ∈

Zn entonces a

·b

∈Z

n,




5 a · (b + c ) = a · b + a · c .



Criptograf́ıa II



http://find/


68/243


1 Si a, b ∈Zn entonces a · b ∈Z

n,




5 a · (b + c ) = a · b + a · c .



Criptograf́ıa II


http://find/


69/243

InversibilidadEn general para n jo no todo elemento a ∈Z n , tiene un inversomultiplicativo. Esto es, un elemento b ∈Z n , tal que [a · b ] = [1] oa · b ≡ 1 mod n (observe Z4 y Z6).

Por lo que tenemos la siguiente proposición :

Para n jo, a ∈Z n es inversible si y solo si (a , n) = 1 , esto es a y nson primos relativos lo que signica que estos dos n´ umeros, no poseen divisores comunes distintos de 1.


Criptograf́ıa II


http://find/


70/243





Criptograf́ıa II


http://find/


71/243





Criptograf́ıa II


http://find/


72/243

Ejemplo

En Z26 , los elementos inversibles para la multiplicación son :

1−

1 = 1, 3−

1 = 9, 5−

1 = 21, 7−

1 = 15, 11−

1 = 19, 17−

1 = 23 y25− 1 = 25.


Criptograf́ıa II


http://find/


73/243

Ejemplo


1−

1 = 1, 3−

1 = 9, 5−

1 = 21, 7−

1 = 15, 11−

1 = 19, 17−

1 = 23 y25− 1 = 25.


Criptograf́ıa II


http://find/


74/243

Ejemplo


1−

1 = 1, 3−

1 = 9, 5−

1 = 21, 7−

1 = 15, 11−

1 = 19, 17−

1 = 23 y25− 1 = 25.


Criptograf́ıa II


http://find/


75/243

http://www.mersenne.org/primes/perfect/perfect1398269.txt


Criptograf́ıa II


http://find/


76/243


Criptograf́ıa II


http://find/


77/243


Criptograf́ıa II

http://find/


78/243



79/243


Criptograf́ıa II El alfabeto de denici´on Los conjuntos Z n Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


80/243



http://find/


81/243



http://find/


82/243



http://find/


83/243



http://find/


84/243


Criptograf́ıa II

http://find/


85/243



86/243



http://find/


87/243



http://find/


88/243



http://find/


89/243



http://find/


90/243





91/243





92/243



http://find/


93/243



http://find/


94/243


Criptograf́a II El alfabeto de denici´on Los conjuntos Z n Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


95/243


C i t g f́ II El alfabeto de denici´on Los conjuntos Z n Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


96/243


C i t f́ II El alfabeto de denici´on Los conjuntos Z n Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


97/243


C i t f́ II El alfabeto de denici´on Los conjuntos Z n Criptograf́ıa Sistema de desplazamiento con MatLab



98/243


C i f́ II El alfabeto de denici´on Los conjuntos Z n Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


99/243


C i f́ II El alfabeto de denici´on Los conjuntos Z n Criptograf́ıa Sistema de desplazamiento con MatLab

http://find/


100/243



http://find/


101/243



http://find/


102/243



http://find/


103/243



http://find/


104/243



http://find/


105/243



http://find/


106/243



http://find/


107/243



http://find/


108/243



http://find/


109/243



http://find/


110/243



http://find/


111/243



http://find/


112/243


http://find/


113/243



114/243



http://find/


115/243



http://find/


116/243



http://find/


117/243



http://find/


118/243



http://find/


119/243




120/243



121/243



http://find/


122/243



http://find/


123/243



http://find/


124/243



http://find/


125/243



http://find/


126/243



http://find/


127/243



http://find/


128/243



http://find/


129/243



http://find/


130/243



http://find/


131/243



http://find/


132/243



http://find/


133/243



http://find/


134/243



http://find/


135/243



http://find/


136/243



http://find/


137/243



http://find/


138/243



http://find/


139/243


http://find/


140/243



141/243



http://find/


142/243



http://find/


143/243



http://find/


144/243



http://find/


145/243



http://find/


146/243



http://find/


147/243



http://find/


148/243



http://find/


149/243



http://find/


150/243



http://find/


151/243



http://find/


152/243





153/243





154/243





155/243





156/243



http://find/


157/243



http://find/


158/243



http://find/


159/243



http://find/


160/243



http://find/


161/243



http://find/


162/243



http://find/


163/243



http://find/


164/243



http://find/


165/243



Criptograf́ıa , signica escritura secreta y se dene como el estudiode todas las técnicas matemáticas relacionadas con aspectos de la

http://find/


166/243

pseguridad de información, tales como la condencialidad,integridad de datos, autenticacion de identidad y autenticacion del

origen de datos.



Los principales metas que se persiguen al construir un sistema deseguridad son las siguientes :

Condencialidad

http://find/


167/243

Condencialidad,Integridad de los datos,Autenticación y autenticación del origen de los datos,No-rechazo.




Condencialidad

http://find/


168/243





Condencialidad

http://find/


169/243





Condencialidad

http://find/


170/243



http://find/


171/243


La autenticaci´ on es un servicio relacionado con la identicaci´on.Esta función es aplicada tanto a las partes que están compartiendouna información como a la información misma. Una parte debepoderse identicar con la otra. La información entregada a travésde un canal debe ser autenticada aśı como su procedencia, elorigen de los datos, su contenido, el tiempo del env́ıo de los datos,etc. La autenticaci ón del origen de los datos asegura


172/243

g gimpĺıcitamente la integridad de los datos.

No-rechazo , es un servicio que previene a una entidad de accionesde desconocimiento. Esto es, en el caso de que existan disputasdebido a que ciertas acciones realizadas producen la negación deuna entidad, es necesario tener los medios que las resuelvan. Porejemplo, si una entidad da autorizacion a un agente de

intermediacion para comprar una propiedad y después talautorizacion es negada se debe resolver la disputa por medio de unprocedimiento que involucre una tercera parte.



DeniciónUn sistema Criptográco o Criptosistema S es una sextupla

(A, P , C , K, E , D).

A es el alfabeto de denición (ejemplo {0, 1}),

http://find/


173/243

P es un conjunto nito de textos en claro, el cual consta de listas

nitas de elementos del alfabeto,C es un conjunto nito de textos cifrados (consta de listas nitasde un alfabeto no necesariamente A),

K es el conjunto o espacio nito de claves o llaves,




(A, P , C , K, E , D).


http://find/


174/243







(A, P , C , K, E , D).


http://find/


175/243







(A, P , C , K, E , D).


http://find/


176/243







(A, P , C , K, E , D).


http://find/


177/243

P es un conjunto nito de textos en claro, el cual consta de listasnitas de elementos del alfabeto,

C es un conjunto nito de textos cifrados (consta de listas nitasde un alfabeto no necesariamente A),





(A, P , C , K, E , D).


http://find/


178/243







(A, P , C , K, E , D).


http://find/


179/243






Reglas de ciframiento

Para K ∈ K, existe una regla de ciframiento e K : P → C ∈ E y unacorrespondiente regla de desciframiento

http://find/


180/243

d K : C → P ∈ D, tales que

d K (e K (x )) = x , para todo texto en claro x .





http://find/


181/243







http://find/


182/243







http://find/


183/243





El cifrado por desplazamiento

Este cifrado es una generalización del cifrado Cesar. En este caso

P = C = K = Z n , n jo

http://find/


184/243

Para K ∈Z n se tiene que

e k (x ) = x + K mod n,

d k (x ) = x − K mod n.





P = C = K = Z n , n jo

http://find/


185/243


e k (x ) = x + K mod n,

d k (x ) = x − K mod n.


http://find/


186/243




P = C = K = Z n , n jo


187/243


e k (x ) = x + K mod n,

d k (x ) = x − K mod n.





P = C = K = Z n , n jo

http://find/


188/243


e k (x ) = x + K mod n,

d k (x ) = x − K mod n.





P = C = K = Z n , n jo

http://find/


189/243


e k (x ) = x + K mod n,

d k (x ) = x − K mod n.



Ejemplo

Si K = 11 y n = 26, entonces el texto en claro

wewillmeetatmidnight

Se cifra convirtiendo el texto en una sucesión de enteros

http://find/


190/243

22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19.

Adicionamos 11 a cada valor para obtener

7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4.

HPHTWWXPPELEXTOYTRSE es el texto cifrado.



Ejemplo




http://find/


191/243

22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19.


7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4.




Ejemplo




http://find/


192/243

22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19.


7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4.




Ejemplo




http://find/


193/243

22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19.


7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4.




Ejemplo




http://find/


194/243

22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19.


7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4.




Ejemplo




http://find/


195/243

22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19.


7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4.




Ejemplo




http://find/


196/243

22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19.


7 15

Documents

Criptografia II - A. Moreno