capítulo 3: encripción
TRANSCRIPT
![Page 1: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/1.jpg)
Prhshntffciccn pffrff lff clffsh:MFFTH 6800 CrkptccgrffFka
Dr. fflvffrcc LhCccmpth Mccnths
Rccsff h. Pffdkllff Tccrrhs30 dh hnhrcc dh 2012
![Page 2: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/2.jpg)
hl mhtccdcc dh hstwdkcc dh lff shgwrkdffd dh lccs CkFrffdccs hn blccqwhs Cccnsksth dhlhstwdkcc dh sws prccpkhdffdhs fflghbrffkCffs.
Cffdff FwnCkccn dh hnCrkpCkccn hs wnhlhmhntcc dcc wn grwpcc dh phrmwtffCkccnhs.
Sk lff FwnCkccn hs dh mhnccr ccrdhn hl dhsCkFrffdcc pwhdh shr rhfflkzffdccknthrffCtwffndcc vffrkffs vhchs Cccn lffFwnCkccn dh hnCrkpCkccn.
![Page 3: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/3.jpg)
wn Crkptccsksthmff hs llffmffdcc CkFrffdcc hnblccquh sk hl hspffckcc dh thxtcc plffncc y swhspffckcc dh tffxtccCkFrff sccn hl Cccnjwntcc dhΣn pfflffbrffs dh wn lffrgcc fkjcc n sccbrh wnfflFffbhtcc Σ.
hl lffrgc dhl blccqwh n hs wn hnthrcc pccsktkvcc.
hjhmplcc:CkFrff Chsffr
hstff hs wn blccqwh dh lffrgcc 1
hs llffmffdcc CkFrffs dh swstktwCkccn
![Page 4: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/4.jpg)
Thccrhmff:Lff FwnCkccn dh CccdkFkcffCkccn dh wn CkFrffdcchn blccqwcc sccn phrmwtffCkccnhs.
DhmccstrffCkccn:hl thccrhmff sh dhmwhstrff pffrhffndcc Cffdff FwnCkffndh CccdkFkCffCkccn Cccn sw FwnCkccn dh dhsCkFrffdccCccrrhspccndkhnths.
hstffs sccn knjhctkvffs
hl mffpff Σn → Σn hs bkjhCtkvff
![Page 5: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/5.jpg)
Pwhdh ffplkcffrsh vffrkffs vhchs pffrffffwmhntffr lff shgwrkdffd.
Cccn Frhcwhnckff sh wtklkzff lff hnCrkpCkccnh-D-h.
wn thxtcc plffncc p hs CccdkFkcffdcc Cccmcc:
hstcc rhswltff hn wn hspffCkcc Clffvhprccbffblhmhnth grffndh.
pEDEc kkk 22
![Page 6: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/6.jpg)
Presentación para la clase:MATH 6800 Criptografía
Dr. Álvaro Lecompte Montes
Rosa E. Padilla Torres30 de enero de 2012
![Page 7: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/7.jpg)
Un criptosistema es llamado cifrado en bloque si el espacio de texto plano y su espacio de textocifra son el conjunto de Σn palabras de un largo fijo n sobre un alfabeto Σ.
El largo del bloque n es un entero positivo.
Ejemplo:Cifra César
Esta es un bloque de largo 1
Es llamado cifras de sustitución
![Page 8: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/8.jpg)
Teorema:La función de codificación de un cifrado en bloque son permutaciones.
Demostración:El teorema se demuestra pareando cada función de codificación con su función de descifrado correspondientes.
Éstas son injectivas
El mapa Σn → Σn es bijectiva
![Page 9: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/9.jpg)
El método de estudio de la seguridad de los cifrados en bloques consiste del estudio de suspropiedades algebraicas.
Cada función de encripción es un elemento de un grupo de permutaciones.
Si la función es de menor orden el descifradopuede ser realizado interactuando varias vecescon la función de encripción.
![Page 10: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/10.jpg)
Puede aplicarse varias veces para aumentar la seguridad.
Con frecuencia se utiliza la encripción E-D-E.
Un texto plano p es codificado como:
Esto resulta un espacio clave probablemente grande.
pEDEc kkk 22
![Page 11: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/11.jpg)
![Page 12: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/12.jpg)
ECB Electronic Codebook Mode
Arbitrariamente los textos planos largos se descomponen en bloques de largo n.
El suplemento consiste en seleccionar símbolos aleatoriamente.
El texto plano debe ser de largo divisible por n.
Se utiliza la clave de encripción e.
Cada bloque de largo n se codifica con la función de encripción Ee.
![Page 13: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/13.jpg)
Los textos cifrados se descifran aplicando la función de descifrado Dd.
La clave de descifrado d corresponde a la clave de cifrado e.
Es utilizada para algoritmos de codificación de bloques de mapas con largo n o mayores.
Esto facilita los ataques estadísticos.
También se atacan con sustitución de texto cifrado.
![Page 14: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/14.jpg)
La manipulación del texto cifrado es muy difícil de detectar por el receptor.
La seguridad aumenta en cierta parte de cada bloque aleatoriamente y más bloques son generados.
![Page 15: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/15.jpg)
Modo de encadenado de bloques cifrados.
Sólo depende de la clave y los bloques previos.
La codificación depende del contexto dependiente.
Bloques iguales con diferentes contextos son encriptados de forma diferente.
![Page 16: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/16.jpg)
Utilizamos bloques cifrados con alfabeto ∑ = {0, 1}
Bloques con largo n
Espacio clave k
Funciones de encripción y descifrar Ek y Dk
respectivamente.
k є K
![Page 17: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/17.jpg)
El mapa : {0, 1}² {0, 1}, (b, c) b c
Se define como la siguiente tabla:
• Es llamado OR exclusivo
• Forma acortada XOR
• Es muy adecuado para encriptarmensajes largos
Para k є , b=(b1, b2,…, bn) y c=(c1, c2, …, cn) є{0, 1}k fijamos:
b c =(b1 c1, b2 c2, … , bk ck)
b c b c
0 0 0
1 0 1
0 1 1
1 1 0
![Page 18: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/18.jpg)
CFB Cipher feedback mode
Modo de retroalimentación de cifra
Las funciones de codificación y descifrado son secuenciales.
No se utiliza directamente la codificación de bloques de texto plano.
![Page 19: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/19.jpg)
Generan una secuencia de bloques claves.
El texto plano se codifica añadiendo los bloques claves mod 2.
El texto cifrado se descifra sumándole el mismo bloque clave mod 2.
Los bloques claves pueden ser generados simultáneamente por el que lo envía.
![Page 20: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/20.jpg)
Para codificar utilizando el modo CFB:1. Oj = Ek (Ij)
2. Establecemos tj a la secuencia del primer bit de Oj.
3. Cj = mj tj
4. Ij+1 = 2r Ij + cj mod 2
![Page 21: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/21.jpg)
OFB Output feedback mode
Modo de retroalimentación de salida.
Es muy similar al modo CFB.
Utiliza:Bloques cifrados de largo n.
Otro bloque de largo r.
Vector de inicialización Ii
Se codifica un texto plano usando la clave e.
Se descompone en bloques de largo r como en CBF.
![Page 22: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/22.jpg)
Para codificar utilizando el modo OFB:1. Oj = Ek (Ij)
2. Fijanos tj a la cadena que consiste en los primero bits de Oj.
3. Cj = mj tj
4. Ij+1 = Oj
• Para descifrar, trabajamos análogamente sustituyendo el paso 3 por mj = cj tj
![Page 23: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/23.jpg)
Si un bit es transmitido incorrectamente, puede llevar a que el texto plano esté en la misma posición.
El bloque clave sólo depende del vector de inicialización.
Tiene la ventaja de que puede ser computada tanto por el remitente como por el destinatario al mismo tiempo.
![Page 24: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/24.jpg)
Es mucho mejor que el modo CBF.
La encripción no depende de los bloques de texto plano anteriores.
![Page 25: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/25.jpg)
Es utilizado para codificar arbitrariamente texto planos largos como si fueran bloques individuales dependientes.
Utiliza la recursión lineal de grado n:
La función de codificación Ek está dada por:
La función para descifrar está dada por:
2mod1
ji
n
j
ji zcz
mmk zzwE ,...,11
mmk zzwD ,...,11
![Page 26: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/26.jpg)
Una cifra afín con alfabeto de texto plano m es un cifrado en bloques con bloques de largo n = 1.
El espacio de las claves consiste en pares (a, b) є m2
para los cuales m es primo para α.
La función de codificación Ek para la clave k = (a, b) es:Ek : ∑ → ∑, x → ax + b mod m
La función de descifrar para k = (a’, b) es:Dk : ∑ → ∑, x → a’(x – b) mod n
![Page 27: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/27.jpg)
Para encontrar la clave de descifrado que correspondea la clave de encripción k(a, b) resolvemos la congruencia aa’1 mod m utilizando el algoritmoeuclidiano extendido.
De ahí surge la clave (a’, b).
![Page 28: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/28.jpg)
Sea R un anillo conmutativo con un elemento unitario 1.
Ejemplo:R = / mpara algunos enteros positivos m
![Page 29: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/29.jpg)
Una matriz k × m sobre R es una combinación rectangular:
knkk
n
n
aaa
aaa
aaa
A
...
....
...
...
21
22221
11211
![Page 30: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/30.jpg)
Si n = k la matriz es cuadrada.
La fila i es el vector (ai1, ai1, …, ain), 1 ≤ j ≤ k
La columna j corresponde al vector(a1j, a2j, …, axj), 1 ≤ j ≤ n
La entrada de la fila i y la columna j es aij
El conjunto de todas las matrices k × n sobre R se denotan por R(k, n)
![Page 31: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/31.jpg)
Si A = (aij) є R(k, n) y v = (v1,…, vn) є Rn entoncesel producto Av se define como el vector:
i
n
j
ii vaw1
![Page 32: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/32.jpg)
Sea n є y A,B є R(n, n), A = (aji), B = (bji)
La suma de A y B es:A + B = (aji + bji)
El producto entre A y B es A ∙ B = AB = (cji) con:
n
k
kjikij bac1
![Page 33: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/33.jpg)
La matriz identidad n × n sobre R es:En= (eij) con eij = 1 para i = j
0 para i ≠ j
La matriz cero n × n sobre R es aquella matriz donde todas sus entradas son cero.
![Page 34: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/34.jpg)
El determinante de la matriz A (det A) A є R(n, n)
se define recursivamente.
n
j
ijij
ji AaA1
det)1(det
![Page 35: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/35.jpg)
Una matriz A є R(n, n) tiene un inversomultiplicativo sí y sólo sí el det A es una unidaden R.
Si n = 1, entonces (a1,1-1) es el inverso de A.
El adjunto de A es una matriz n × n definidacomo:
adj A = (-1)i+j det Aij
La inversa de A es:A-1 = (det A)-1 adj A
![Page 36: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/36.jpg)
![Page 37: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/37.jpg)
Función lineal afín:Una función f: Rn
Rn se le llama lineal afín si posee una matriz A R(l,n) y un vector b є Rl talque:
Si b = 0 entonces la función es llamada lineal.
Las funciones lineales afines nmn
m son definidas análogamente.
bvAvf )(
![Page 38: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/38.jpg)
Una función f: nmn
l se le llama lineal afín si allí existe una matriz A є (l, n) y un vector b є l tal que:
para todo v є nm.
Si b 0 mod m, la función es lineal.
mbvAvf mod)(
![Page 39: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/39.jpg)
Un mapa afín lineal de esbijectivo sí y sólo sí l = n y el det A es unidaden R.
es bijectiva sí y sólo sí
l = n y el det A es primo para m.
mbvAvf mod)(
bvAvf )(
![Page 40: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/40.jpg)
Una función f: Rn Rn es lineal sí y sólo sí
para todo v, w є Rn y todo a, b є R.
Es una lineal a fin, sí y sólo sí la función Rn Rn,
v f(v) - f(v) es lineal.
)()()( wbfvafwbvAvf
![Page 41: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/41.jpg)
Un cifrado en bloque con largo n, texto plano y espacio de texto cifrado n es llamado afín lineal si todas sus funciones de encripción son lineales afines.
Son de la forma:E: n
mn
m , v A v + b mod m
Su correspondiente función de decodificación es:
D: nmn
m , v A-1 (v – b) mod m
Donde A’= (a’adj A) mod m y a’ es la inversa de (det A) mod m
![Page 42: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/42.jpg)
![Page 43: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/43.jpg)
Son llamadas así por Blaise de Vigenére
El espacio clave es K = nm
Si k nm , entonces:
Ek = nmn
m , v v + k mod m
Dk = nmn
m , v v - k mod m
![Page 44: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/44.jpg)
Obtiene su nombre por Lester Sanders Hill (1929).
Es otro criptosistema clásico.
Espacio clave k es el conjunto de todas las matrices A (n, n) con mcd(det A, m) = 1
La clave A K es:EA = n
mn
m , v Av mod m
La permutación de cifras es lineal.
![Page 45: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/45.jpg)
Sea Sn y ei , 1 ≤ i ≤ n los vectores filas en la matriz identidad.
Obtenemos la matriz identidad mediante la permutación de sus filas de acuerdo con la permutación .
(v(1), … , v(n)) = Ev
La permutación de cifras y una cifra lineal.
![Page 46: Capítulo 3: Encripción](https://reader034.vdocumento.com/reader034/viewer/2022042715/55a1e09a1a28ab0c778b4796/html5/thumbnails/46.jpg)
Buchmann, Johannes A. (2000). Introduction toCryptography. Capítulo 3: Encripción, páginas 69 a 101.