CRIPTO I - PLACAS 02 - CRIPTOGRAFIA CLASICA.pdf

Introducción a la criptografía 1-2

1. CRIPTOGRAFÍA I
Curso 2024
CRIPTOGRAFÍA CLÁSICA
CLASE 3
. Dr. Hugo Scolnik
Cripto I -Scolnik 1

2. PLACAS 03
CRIPTOGRAFIA CLASICA
2Cripto I -Scolnik

3. DESARROLLO
Módulo I –Criptografía clásica
Definición,objetivosyfundamentosdecriptología.
Introducciónaloscriptosistemas.Definiciones.
Necesidades.Seguridadteóricaypráctica.Criptografía
porsoftwareyporhardware.Ataquescriptográficos.
Clasificacióngeneraldesistemascriptográficos.Principios
deKerckhoff.Procedimientosclásicosdecifrado:métodos
históricos(escítalaespartana,etc.).Primalidad,aritmética
modular(Z
n,Z*
n)yfuncionesnuméricaselementales(MCD,
mcm).ClavedeJulioCésar.Métodosgeneralesde
transposiciónysustitución.Cifradorafín.CifradordeHill.
Clavespolialfabéticas(Vigenère).Otrosmétodos
especiales(Playfair,Autokey,etc.).Criptoanálisis
elemental:ataqueestadístico.MétododeKasiski.Índice
decoincidenciaeÍndicedecoincidenciamutuo.
3
Cripto I -Scolnik

4. CRIPTOGRAFIA HISTÓRICA -1
THE CODEBREAKERS David Kahn Scribner Rev.Ed. (1966)
EGIPTO (1900 AC)
•Jeroglíficos especiales
MESOPOTAMIA (asirios-babilonios)
•Colofones cuneiformes
ASIA (India)
•Clave de sustitución
GRECIA (Esparta-500AC)–criptografía militar
•Escítala (1er aparato criptográfico)

4Cripto I -Scolnik

5. CRIPTOGRAFIA HISTÓRICA -2
THE CODEBREAKERS David Kahn Scribner Rev.Ed. (1966)
GRECIA (Aeneas el táctico)
•Esteganografía –x agujeros en
Astrágalos como clave
GRECIA (Polybius)
•Clave de sustitución matricial
ROMA (Julio César)
•Clave de sustitución modular
ROT(3)
ITALIA (Simeone de Crema –1401)
•Primera clave de sustitución
homofónica
5Cripto I -Scolnik

6. CRIPTOGRAFIA HISTÓRICA -3
THE CODEBREAKERS David Kahn Scribner Rev.Ed. (1966)
•León Battista Alberti (Siglo XV)-Primer
clave de sustitución polialfabética por
“hardware” (2 discos concéntricos)
ITALIA (Florencia –1550)
•Primer Nomenclador conocido
ITALIA (Sforza-Medici) FRANCIA-ALEMANIA-
ESPAÑA-INGLATERRA –Siglo XVI y
siguientes
•Nacen los criptoanalistas profesionales
•Florecen las claves de sustitución mono y
polialfabéticas, poligráficas, de permutación
y nomencladores de toda clase
6Cripto I -Scolnik

7. CRIPTOGRAFIA HISTÓRICA -4
THE CODEBREAKERS David Kahn Scribner Rev.Ed. (1966)
ALEMANIA (Abad Johannes Trithemius –1518)
•Primer Libro sobre Criptología (latín)
(“Polygraphiae Libri Sex”)
•Clave AVE MARIA polialfabética
ITALIA (Cardano –1550 Vigenére -1570)
•Clave auto-retroalimentada (autokey)
•Vigenére: clave sustitución polialfabética
EUROPA (Siglos XVII-XVIII-XIX)
•“Gabinetes Oscuros” (Viéte, von Marnix,..)
•Se consolida la criptografía clásica
7Cripto I -Scolnik

8. CRIPTOGRAFIA HISTÓRICA -5
THE CODEBREAKERS David Kahn Scribner Rev.Ed. (1966)
EUROPA-EEUU (XIX)
•Beaufort: clave matricial (tipo Polybius)
•Kasiski: criptoanálisis científico: módulos y ataques
estadísticos (etaoin)
•Babbage: criptología computacional
SIGLO XX
•Alan Turing (1941/2)-Código Enigma
•1976: Nace la criptografía asimétrica y de clave pública
(Diffie-Hellman)(Pohlig-Hellman) (Hellman-Merkle)
•1977: DES-56 standard NIST (Feistel)
•1978: RSA (“plagio parcial” de Hellman-Pohlig)
8Cripto I -Scolnik

9. CRIPTOSISTEMAS (SHANNON)
sustituir
permutar
9Cripto I -Scolnik

10. PRINCIPIOS DE KERCKHOFF (1883)
LOS CRIPTOSISTEMAS DEBEN SER:
1.Inquebrablesenlapráctica,sinolofuesen
teóricamente.
2.Ladifusióndelmétodonodebeafectaralos
corresponsales.
3.Laclavedebesermemorizableyfácilmente
cambiable.
4.Elcifradodebesertelegrafiable.
5.Elequipoencriptordebeserportátilyoperablepor
unasólapersona.
6.Elsistemadebesersimple,sinrequerir
memorizacióndemuchasreglasnigenerar
esfuerzomental.
10Cripto I -Scolnik

11. CRIPTOSISTEMA -1Pxxxed
PCdCPeDd
EeKk
K
C
P
DEKCP
kk
kkk
k
=
→→

))((/ biunívocas funciones
son :y : cada que talesión desencripc de
regla ientecorrespond unay encripción de regla una 4)
finito conjuntoun es claves de espacio el , 3)
cifrados textosposibles los de conjunto el es 2)
planos textosposibles los de conjunto el es 1)
que tal),,,,( quintupla una es emacriptosistUn
11Cripto I -Scolnik

12. CRIPTOSISTEMA -2niydx
yyy
nixey
nxxx
AASCIIAA
aaA
iki
n
iki
n
q
=
=
=
=
===
=
1 ),(
mediante mensaje el recuperareceptor El
...
resultando 1 ),( calculaemisor El
r. transmitia mensajeun ,1, ... Sea
español alfabeto , },1,0{ ejemplo,Por
utilizar. a alfabeto el },...,{ Sea
1
1
1
12Cripto I -Scolnik

13. k
k
d
eCP
Kk
A
P
por entonces denota se inversafunción ientecorrespond La
encripción defunción una llamada es que ,por denotada a debiyección
una teunívocamen determina elemento Cada
. alfabeto del símbolos de
cadenas de entonces consiste planos textosposibles los de conjunto El
 CRIPTOSISTEMA -3
13Cripto I -Scolnik

14. METODOS SIMETRICOS1)]log(1459.3[ ejemploPor
)( que tal
biunívoca conocidafunción cualquier usarse podría pero , Usualmente
otro elcomputar ellos, de uno dado posible, es ),(
asociadopar cada para si simétrico es que Diremos }.:{y }:{
de econsistent encripción de esquemaun osconsiderem :Definición
+=
=
=

ed
efd
de
de
KkdKke
kk
14Cripto I -Scolnik

15. uno cada an permutació la aplica le se
y letras 5 de gruposen particiona lo se mensajeun encriptar Para
. den permutació una a encripción defunción como Tomemos
}. sobre 5 longitud de cadena{y
únicamente mayúsculas letras las
de compuesto español alfabeto el Z}B,...,A,{ sea :Ejemplo
A
ACP
A
=
= ENCRIPTORES DE SUSTITUCION SIMPLE
15Cripto I -Scolnik

16. Un caso particular es la encripción de Julio César donde
se le asigna a cada letra la que figura 3 lugares adelante
en forma modular ( o sea módulo 27 que es la cantidad
de letras del alfabeto)
Ejemplo:
A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z
D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z A B C
añorar →dqrudu
ENCRIPTORES DE SUSTITUCION SIMPLE
16Cripto I -Scolnik

17. kA
ppM
CccpkpkMee
Kk
AK
AtP
qA
t
ttkk
FIJA n permutació unacon acuerdo de alfabeto del
símbolo otropor oreemplazad es upla- tuna de símbolo cadasea, O
encriptar. a mensaje el es ),...,( donde
),...,())(),...,(()( como
encripción deción transforma
la encripción deación transformla definimos cada Para
} de nespermutacio{
} de elementos de longitud de cadenas{
adcardinalidsu sea o alfabeto, del elementos de número el será
1
11
=
===

=
=
= ENCRIPTORES DE SUSTITUCION SIMPLE
17Cripto I -Scolnik

18. s.frecuencia lasconservan se pues textode
pequeña nterelativame cantidad una examinando erápidament erecuperars puede
clave la pero ,210.09.1! 27 es claves de número el español alfabeto
elen ejemplo,Por GRANDE. MUY es claves de espacio el aunque inseguros
muyson pequeño tamañode mensajes sobreón substituci de resencriptado Los
encriptar. a mensaje del tamañodel NTEINDEPENDIE esy
1.2)...1.(! esón substituci de distintos resencriptado de número El
TICA.MONOALFABE o SIMPLEón substituci una denomina se Esto
),...,())(),...,(()(y inversa
npermutació la calcula se ),...,( codificado mensaje elar desencript Para
9328
11
1
1

−=
====
=
−
qqq
MppcdcdCded
ccC
ttkkkkk
t ENCRIPTORES DE SUSTITUCION SIMPLE
18Cripto I -Scolnik

19. símbolos. los de frecuencia la disimular"" paraSirven
}1111,1101,0111,0101{
}1110,1100,0110,0100{
}1011,1001,0011,0001{
}1010,1000,0010,0000{
:elementos 4 de cadenas de disjuntos conjuntos los
de consiste 2 longitud de mensajes para encripción defunción la de codominio El
}11,01{)( },10,00{)( , ),( :Ejemplo
).( conjunto el es clave La ).( /
encontrar quehay símbolos de cadena unaar desencript Para ).(en
azar al elegida cadena unacon símbolo cada reeemplaza homofónico métodoUn
)()( , si que den restricció la
con símbolos, de cadenas de )( conjuntoun asociamos le cadaA
→
→
→
→
===

=

bb
ba
ab
aa
bHaHbaA
aHaHCAa
tCaH
a
babHaHAba
taHAa ENCRIPTORES DE
SUSTITUCION HOMOFONICA
19Cripto I -Scolnik

20. 1516 módulo 11x13158x1614311x13 en 11x13 :Ejemplo
módulo expresa se resultado
el pero usuales, lasson soperacione Las .y soperacione lascon
}1,...,0{ conjunto el sobre define se módulo aritmética la :Definición
)mod( queVer
, obteniendo ,por , dividimos que Supongamos
. módulo con
congruente es que caso esteen Decimos . a divide si )mod(
osescribirem Entonces positivo. enteroun y enteros, ,sean :Definición
modular. aritmética la de básicos conceptos losrepasar que
tenemosCiphers)(Shift ocorrimient de cifradores los generalen describir Para
16
21
2211
=→+==→
+
−=
=
+=+=
−
Z
m
x
mZm
rrmba
rmqbrmqamba
mb
aabmmba
mba
m ENCRIPTORES DE CORRIMIENTO
(SHIFT CIPHERS)
20Cripto I -Scolnik

21. abeliano es 2por y suma la a respecto grupoun es 5431
)(y )(,,
quedecir es adición, la a respectocon vadistributi esción multiplica la )10
1..1 que sea o ción,multiplica la para identidad la es 1 9)
)()(,, quedecir es ,asociativa esción multiplica la 8)
, que sea o a,conmutativ esción multiplica la )7
, quedecir es cerrada, esción multiplica la 6)
es cualquier de aditiva inversa La 5)
00 , sea o suma, la para identidad la es 0 4)
)()(,, que sea o ,asociativa es suma la 3)
,decir es a,conmutativ es suma la 2)
,decir es cerrada, es suma la 1)
:son Ellas .aritmética la de usuales reglas las
de mayoría la satisfacen en ción multiplicay suma de esdefinicion Estas
m
m
m
m
m
mm
m
m
m
m
mm
m
Z
acabcbabcaccbaZcba
aaZa
bcacabZcba
baabZba
ZabZba
amZa
aaZa
cbacbaZcba
abbaZba
ZbaZba
Z
+++
+=++=+
=
=
=

−
+=+
++=++
+=+
+ ENCRIPTORES DE CORRIMIENTO
(SHIFT CIPHERS)
21Cripto I -Scolnik

22. César Julio der encriptado el obtenemos 3 si :Nota
mod )(y mod )(
definimos 10 Para Sea
:ocorrimient decifrador El
24183111 comocalcular puede se en 1811 :Ejemplo
.mod reducirlo luegoy
calcular puede se emente,equivalent o, mod como en
definimos ello Para .en restar podemos aditivas, inversasexisten Como
finito. anilloun es que establecen 10 a 1 spropiedade Las
31
=
−=+=
−===
=−+−
−
−+−
k
mkyydmkxxe
mkZKCP
Z
mba
mbmaZba
Z
Z
kk
m
m
m
m ENCRIPTORES DE CORRIMIENTO
(SHIFT CIPHERS)
22Cripto I -Scolnik

23. Veamos un ejemplo en inglés ( 26)
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Te
m=
xto plano: wewillmeetatmidnight
Este texto escrito numéricamente según la correspondencia anterior es:
22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19
Si la clave es 11, le sumamk= os ese valor a cada elemento y tomamos mod 26
obteniendo
7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4
que, en carácteres alfabéticos, se escribe
HPHTWWXPPELEXTOYTRSE
Para desencriptar se escribe este texto como números, se le resta 11, y se toma
mod 26
Basta probar las claves posibles y se desencripta. Además conserva
las frecuencias.
m 23Cripto I -Scolnik

24. Ha sido muy usado, la mayor parte de los criptogramas que aparecen en revistas y diarios
son de esta clase.
Algoritmo: Sea
conjunto de claves consiste de todas las permutaciones de
Par
m
P C Z
Km
==
=
1
a cada permutación definimos ( ) ( )
siendo la correspondiente desencripción ( ) ( )
Ejemplo de permutación:
a b c d e f g h i j k l m n ñ o p q r s t u
K e x x
d y y




−
=
=
v w x y z
X Z Y W V U R S T P Q O Ñ M N K I L F E D H G J B A CB
Entonces (a) X, (b) Z, etc
Permutando las filas de la tabla anterior y ordenandola en forma alfabética,
se obtiene la
ee==
permutación inversa ENCRIPTORES DE SUSTITUCION
24Cripto I -Scolnik

25. .1)27,( si sóloy si
todoparasolución única una tieneacongruenci esta que es esencial resultado El
).(con 27 mod acongruenci la
estudiarcon basta tantoloPor . hace lo también en varía como
27 mod a
eequivalent es acongruenci Esta solución. única una tenga27 mod
acongruenci la que queremos palabras, otrasEn inyectiva. esafín
función una cuando epreguntars necesario esar desencript posible sea que Para
o)corrimient
decifrador un es 1 si que(observar ,con , 27mod )(
sea o afín, es encripción defunción la que elen afín,cifrador el es
especial caso Otro nes.permutacio 27! las de 27 sólo a incluye queón substituci
decifrador del especial casoun es Cipher)(Shift ocorrimient decifrador El
27
27
27
27
=

−
−
+

=+=
aMCDy
Zyyax
byZy
byax
ybax
Zy
aZbabaxxe ENCRIPTORES AFINES
25Cripto I -Scolnik

26. . parasolución única una tiene27 mod acongruenci
la que a conduce esoy vezuna eexactament valor cada tomaque significa
que lo 27, mod distintos valores27 toma27 mod entonces sobre varía
si que sea O .en solución una sumo lo a tiene27 mod forma la de
acongruenci una entonces ,1)27,( si que probado hemos tantoloPor
27 mod )/(271)27,(y )(/27 Como
//y 1),( si
:división la de propiedad una ahora Usamos
)(/27 27 mod 0)( 27, mod
verificase ,par algún para quey 1)27,( que ahora Supongamos
.encripción defunción como usarse puede
no tantolopor y inyectiva es no 27 mod )(función la caso eseEn
/27y 0 , en distintas soluciones dos menos al tiene27 mod 0
acongruenci la Entonces .1)27,( que contrario lopor Supongamos
27
27
27
212121
212121
21
27
Zybax
axZx
Zyax
aMCD
xxxxaMCDxxa
cabcabaMCD
xxaxxaaxax
xxaMCD
baxxe
dxxZax
daMCD


=
−=−
=
−−
=
+=
==
= 26Cripto I -Scolnik

27. inglés)en function totient
oEuler defunción la (llamada )( por denota se con relativos primos
son que 1}-m{0,...,en enteros de número El relativos. primosson
y que diremos 1),( Si enteros. 2y 1Sean :Definición
:números
de teoríala de resultado otro snecesitamo claves de número elcalcular Para
.1),( si sóloy si todopara
solución única una tienem mod acongruenci la :Teorema
:generalEn .particular de nada tieneno 27 número el que supuestoPor
mm
Z
mamaMCDma
maMCDZb
Zxbax
m
m
m

=
=
=
 ENCRIPTORES AFINES
27Cripto I -Scolnik

28. única. es existe siy ,1),( si sóloy si m mod tivamultiplica
inversa una tiene que probarse puede similares argumentos Usando
m mod 1.. que
tal elementoun es de tivamultiplica inversa La . sea :Definición
:snecesitamo ello Para . calcular como dijimos no
pero factible sea esto que para scondicione las dimosy 27, mod de
solución laencontrar snecesitamo ar desencript para que ahora hasta Dijimos
inyectiva.ser debefunción la que a debido )( es
paray es para desposibilida de cantidad la que dado )( esafín
cifrador elen distintas claves de número el que deduce seexpresión esta De
)()(
Entonces .1 ,0y distintos primosson los
donde , de primos factoresen ción descomposi la sea :Teorema
11
1.
1
1
1
=


+
−=

=
−−
−
maMCD
a
aaaa
aaZa
x
baxy
y
ma
mbmm
ppm
niep
mpm
m
ie
i
ie
i
n
ii
n
ie
i


 
 28Cripto I -Scolnik

29. 27 mod )()(
y 27 mod )( definimos ),(K Para
}1)27,( / x),{( seay
:afíncifrador del algoritmo el entonces Tenemos
3 17, ,7 ,13
de existen) (si tivasmultiplica inversas lasencontrar :Ejemplo
error.y ensayopor resolver
puede se ,27 de simple caso el para tanto,Mientras tivas.multiplica
inversascalcular para eficazmuy algoritmoun veráse adelante Más
cuerpo)un llama se cumple se esto que elen anillo(un tivamultiplica
inversa una tiene de nulo no elemento todoentonces primo, es Si
1
K
K
272727
byayd
baxxeKba
aMCDZZbaKZCP
a
m
Zp
m
−=
+==
====
=
=
− ENCRIPTORES AFINES
29Cripto I -Scolnik

30. )(en 12)325(1312)(13))((
:osVerifiquem
)(en 1213)3(13)(
que así en 13 es 25 de tivamultiplica inversa La
325)(
es encripción defunción la (25,3)K sea :Ejemplo
27KKK
27K
27
1
K
Zxxxexed
Zyyyd
Zaa
xxe
=−+=−=
−=−=
==
+=
=
− ENCRIPTORES AFINES
30Cripto I -Scolnik

31. ENCRIPTORES DE SUSTITUCION
POLIALFABETICA (VIGENERE)IZITWZTWPUBTTMJPWVPXZGIAXIV
19 25 22
--------
15 8 2
4 17 20
19 8 25 8 22 15 9 12 19 19 1 20 15 22 21 8 23 0 8 6 25 23 15 21
-----------------------------------------------------------
17 4 7 15 8 2 17 4 7 15 8 2 17 4 7 15 8 2 17 4 7 15 8 2
2 4 18 19 14 13 18 8 12 4 19 18 24 18 14 19 15 24 17 2 18 8 7 19
ntenuméricame textoel Escribimos
remisnotsecuryptosyste thisc
plano textoely 4,17)(2,8,15,7,CIPHERK clave lay 6 Sea
:inglésen ejemploun Veamos .carácteres de cadena unacon asocia se clave cada que
es idea La XVI). (siglo Vigénere de Blaise a debido clase, esta de es no que métodoun ahora Veremos
TICOS.MONOALFABEllaman se métodos estos esopor y carácter, únicoun a dotransforma
es alfabeto del elemento cada ón,substituci de losen y ocorrimient de cifradores losen que Vimos
===m
m
31Cripto I -Scolnik

32. ENCRIPTORES DE FLUJO),...,,(
sea o plano, textodel elementos 1 primeros
losy clave la mediante genera quefunción una Sea clave. la y
plano textoel ... sea :modo siguiente del opera flujos decifrador Un
)...()(...
que talmodo de ... claves desucesión unagenerar de la
es básica idea la donde flujo, de cifradores los de el es oalternativ enfoqueUn
bloques de cifradores llamados losSon
)...()(... sea o clave, misma la usando
n encriptaba se plano textodel sucesivos carácteres los ahora hasta vimosque métodos losEn
11
21
2121
21
2121
21
−=
−

=
==
=
==
iii
ii
kk
kk
xxkfk
i
kkfKk
xxx
xexeyyy
kkk
xexeyyy
32Cripto I -Scolnik