CRIPTOGRAFIA

ASIMÉTRICA
ALGORITMO RSA

SILER AMADOR DONADO

LOS CREADORES DEL RSA

RON R IVEST ADI S HAMIR LEONARD A DLEMAN

SILER AMADOR DONADO

Q ué es R S A ?
El RSA es un sistema de clave pública
implementado por R ivest, S hamir y
A dleman basado en la exponenciación
modular desarrollada por Diffie-Hellman,
donde la clave pública son pares de
números (e,n) formados por un exponente e
y un módulo n que es el producto de dos
grandísimos números primos p y q tales
que mcd(e,fi(n))=1 (donde fi(n) es el
número de enteros menores que n y primos
con él)

SILER AMADOR DONADO

Definición del
criptosistema RSA?
Sea f una función unidireccional definida
así: M C
f : M C
m1
m2
f(m) = c c1
c2
m3 c3
m4 c4
. .
. .
. .

Donde M es el conjunto de todos los mensajes en

texto claro, para todo m Є M. Donde C es el
conjunto de todos los mensajes cifrados, para
todo c Є C. Luego f(m) = c
SILER AMADOR DONADO
 Definición del
criptosistema RSA?
Sea f una función unidireccional inversa
-1
definida así: C M
f-1 :C M
c1 -1 m1
c2 f (c) = m m2
c3 m3
c4 m4
. .
. .
. .

Donde M es el conjunto de todos los mensajes en

texto claro, para todo m Є M. Donde C es el conjunto
de todos los mensajes cifrados, para todo c Є C.
Luego f-1 (c) = m
SILER AMADOR DONADO
 El algoritmo RSA
Si un usuario A desea enviar un mensaje m=cuy al


usuario B.


 fb(m) = c f-1 b(c) = f-1 b(fb(m)) = m

 fb(cuy) = go f-1 b(go) = f-1 b(fb(cuy)) = cuy
 Usuario A Usuario
A en B
ví

Π β λ ι χ Π β λ ι
α ( ε α , na) a χ α (ε β ,
 Π ρ ι ϖα δ Πρ ι ϖα
nδb)α ( δ )

α (δ α )
Π β λ ι go Π  β λβ ι
χ α (ε β , a χ α (ε α ,

nb) B na)



SILER AMADOR DONADO
 El algoritmo RSA
Pasos a seguir para cada usuario A y B, a continuación


solo se calcula para el usuario A, lo mismo se debe

realizar para el usuario B:


1. El usuario A elige 2 números primos pa y qa

2. Calculamos el Grupo Z *n , entonces na = pa * qa

a

3. C a lcu la m o s e l Orden del Grupo (na) = (pa - 1 )* ( qa -1 )

4. S e le ccio n a m o s u n e n te ro p o sitivo ea, 1<= ε α <
φ (na), | σ ε α π ρ ι µ ο χ ο ν ε λ Ο ρ δ ε ν
δ ε λ Γ ρ υ π ο , ε σ δ ε χ ι ρ µ χ δ (ε α ,
φ (na))= 1
5. B a sa d o e n e l a lg o ritm o d e Euclides extendido
SILER AMADOR DONADO
calculamos δ que es el inverso modular de
 Cómo cifrar y descifrar con el
algoritmo RSA?
Si un usuario A desea enviar cifrado un


mensaje m Є Zn a lu su a rio B , A utilizala

lla ve p ú b lica d e B , ( ε β , nb), π α ρ α
ε λ ϖαλ ο ρ δ ε µ
ε β

χ αλ χ υ λ αρ
( µ ο δ nb) = χ , θ υ ε λ υ ε γ ο
ε ν ϖ α α Β .


Πα ρ α δ ε σ χ ι φ ρ α ρ ε λ


µ ε ν σαϕε ο ρ ι γ ι ν αλ µ , Β
δ ε β ε υ σ αρ λ α λ λ αϖε
SILER AMADOR DONADO
 Cómo firmar un mensaje con el
algoritmo RSA?
A cuenta con la llave pública ( ε α , na) ψ σ υ λ λ α ϖε


π ρ ι ϖ α δ α ( δ α ). Si un usuario A d e se a e n via r la
firm a d ig ita l d e u n m e n sa je m Є Zn a lu su a rio B :
1. Χ α λ χ υ λ α ε λ ϖα λ ο ρ δ ε σ υ ρ β ρ ι χ α
ρ ≡ µ ( µ ο δ na) .
δ
α

2. ∆ ε τ ε ρ µ ι ν α λ α φ ι ρ µ α χ ι φ ρ α ν δ ο
χ ο ν λ α λ λ αϖε π  β λ ι χ α δ ε Β λ α
ρ  β ρ ι χ α . σ ≡ ρ ( µ ο δ nb) .
ε
β

Ε λ µ ε ν σ α ϕ ε φ ι ρ µ α δ ο θ υ ε Α ε ν ϖα α
Β ε σ λ α π α ρ ε ϕ α φ ο ρ µ α δ α π ο ρ ( χ ,σ ),
δ ο ν δ ε χ ε σ ε λ µ ε ν σαϕε µ χ ι φ ρ αδ ο .
Πα ρ α θ υ ε Β π υ ε δ α ϖε ρ ι φ ι χ α ρ λ α
φ ι ρ µ α δ ε Α , δ εSILER
β AMADOR
ε χ DONADO
ο µ π ρ ο β αρ θ υ ε :
 E je m p lo d e la lg o ritm o R S A ( ½ )
Cifrando
Alfabeto español:y Descifrando
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
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26
Elm usuario
≡ CUY, Bentonces 23, 2q)+U(27
elige p b =C(27 1
b =97, )+Y(27
0) ≡ 1458+567+
Usuario A elige 25 = 2050 < 2231 y
n b =2231 2050p a <
=101 ,q a =29,φ ( n a ) = 2800,e a =17
2929
El orden del Grupo es φ ( n b ) = 2112 n a = 2929, ya realizó sus cálculos
Β ε λ ι γ ε ε λ ν  µ ε ρ ο e b = obteniendo:
17 λ α λ λ α ϖε π ρ ι ϖα δ α δ ε
Α ε σ δm αcon
Ciframos = la
1153 llave pública de B:
µ χ δ (17,2112) = 1 Ο Κ Χ
Ε ν=τ µο ν(µχ οε δσ nλb)αε λν λ
ε
β

τ ο
α νϖ χε ε σ
Χα λ χ υ λ α µ ο σ ε λ π  = β 2050
λ ι 17χ (µ
α οδ δε 2231)Α ( 17=, 2929)
ι ν ϖε ρ σ ο µ ο δ υ λ αρ : Χ 177,
ε β ∗ δ β ≡ 1 (µ ο δ φ (nb)) χ ο ν ε ν τ ο ν χ ε σ
Χ = 6(271) + 15(270) ≡ Γ Ο
1<= δ β < φ (nb) , λ υ ε γ ο Πα ρ α δ ε σ χ ι φ ρ α ρ
17 ∗ δ β ≡ 1 (µ ο δ 2112) χ ο ν υ σ αµ ο σ λ α λ λ αϖε
1<= δ β <2112 π ρ ι ϖ α δ α δ ε Β (δ β )
Λ υ ε γ ο λ α λ λ α ϖε µ = χ (µ ο δ nb)= 177497 (µ ο δ 2231),
δ
β

π ρ ι ϖα δ α δ ε Β ε σ δ β = λ υ ε γ ο
497 mensaje m descifrado es: 2050 ≡
El DONADO
SILER AMADOR
Ε ν τ ο ν χ ε σ λ α λ λ α ϖε
 E je m p lo d e la lg o ritm o R S A
( 2 / 2 )
Alfabeto español:


A Firmando
 B C D E F G y HVerificando
I J K L M N Ñ O P Q R
S T U V W X Y Z
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
20 21 22 B23elige
El usuario 24 25 26
p b= 23, q b =97, Usuario A elige
nm
b =2231
≡ CUY, entonces C(272)+U(271)+Y(27 p a =101,0q)a≡=29 ,φ ( n a ) = 2800,e a =17
1458+567+25 = 2050 <
El orden del Grupo es φ ( n b ) = 2112
2231 y 2050n a = 2929,
< 2929ya realizó sus cálculos
Β ε λ ι γ ε ε λ ν  µ ε ρ ο e b  = obteniendo:
17 λ α λ λ α ϖε π ρ ι ϖα δ α δ ε
El
Α usuario
ε σ δ αA = calcula
1153 su rúbrica para

µ χ δ (17,2112) = 1 Ο Κ el
Ε νmensaje
τ ο ν .χ ε σ λ α λ λ α ϖ ε
Χα λ χ υ λ α µ ο σ ε λ ρ
π  =β µλ ι ( µχ οα δ δ εn a ) Α= ( 17, 2929)
δ
α

ι ν ϖε ρ σ ο µ ο δ υ λ αρ :
ε β ∗ δ β ≡ 1 (µ ο δ φ (nb)) χ ο ν 2050 1153 (µ ο δ 2929) = 1851

σ = ρ ( µ ο δ n b ) = 1851 17 (µ ο δ
ε
β

1<= δ β < φ (nb) , λ υ ε γ ο

2231) = 1463
17 ∗ δ β ≡ 1 (µ ο δ 2112) χ ο ν σ = 2(272) + 0(271) + 5(270) ≡ Χ Α Φ ,
1<= δ β <2112 ε ν τ ο ν χ ε σ Β ρ ε χ ι β ε λ α
Λ υ ε γ ο λ α λ λ α ϖε π α ρ ε ϕ α : ( χ ,σ ) ≡ ( Γ Ο , Χ Α Φ ),
π ρ ι ϖα δ α δ ε Β ε σ δ β = λ υ ε γ ο θ υ ε Β ηα
497 SILER AMADOR σχ ι φ ρ αδ ο χ ,
δ εDONADO
ϖ ε ρ ι φ ι χ α σ = 1463, entonces:
CRIPTOANALISIS

ALGORITMO RSA

SILER AMADOR DONADO

 ANTECEDENTES DEL RSA
• 1976 – Propuesta por Diffie y Hellman. Se
basa en la dificultad de calcular
logaritmos discretos (resolver ax = b mod
n para x).
• 1977 – Algoritmo RSA desarrollado por
Rivest, Shamir y Adleman. Se basa en la
dificultad de factorizar números grandes.
RSA129 (129 dígitos) publicado como
desafío.
• 1994 – RSA129 roto con 1600 ordenadores
en red.
• 1999 – RSA140 roto con 185 ordenadores en
red en 8,9 años- CPU.
• 1999 – RSA155 (clave de 512 bits) roto con
SILER AMADOR DONADO
300 equipos en red.
 CRIPTOANALISIS DEL RSA
• Factorizar n, que es público, y así
obtienes p y q
• Calcular φ (n) = (p-1)(q-1)
• Calcular d tal que d(e)modφ (n) = 1 (e
es público)
• La clave privada es = d
Ejemplo: Conocemos n =2231,
b
entonces hallamos sus factores primos
pb=23, qb=97, luego se calcula
φ (nb)=(22)(96)=2112, luego se calcula
SILER AMADOR DONADO