Entender RSA

Imagen de Agustín
Enviado por Agustín en

Foros: 

Por Agustín

Todos tenemos una idea de cómo funciona el cifrado asimétrico RSA, que se basa en unos números primos muy largos para generar una clave pública, con la que cualquiera puede cifrar un documento dirigido a ti, y una clave privada, con la que sólo tú puedes descifrarlo. Pero a mí siempre se me ha resistido la comprensión última, las tuercas y tornillos del algoritmo, sobre todo porque mi conocimiento de la Teoría de los Números deja mucho que desear. Por eso he decidido hacer un auto-cursillo sobre este tema, con la esperanza de haber captado, si no los fundamentos profundos, al menos la mecánica detallada del procedimiento. También espero que ese estudio le sirva a alguien que vaya igual de despistado en este asunto. A los que estáis más puestos en esta materia os ruego benevolencia, incluso alguna colaboración o, si os aburre, que miréis para otro lado.

Me ha servido bastante la explicación que he encontrado en Clay Mathematics Institute, pero cualquiera de las que hay por ahí serviría igualmente, si se mira con atención.

Para facilitar la comprensión he confeccionado una versión de juguete, que usa números primos pequeños, con lo que no se consigue fortaleza alguna, pero quizá se vea más claro el intríngulis.

 

 

Para empezar, se codifican los caracteres del mensaje en claro mediante una tabla como ésta:

* 0  1  2  3  4  5  6  7  8  9
0 XX XX XX XX XX XX XX XX XX XX
1 SP A  B  C  D  E  F  G  H  I
2 J  K  L  M  N  O  P  Q  R  S
3 T  U  V  W  X  Y  Z  a  b  c
4 d  e  f  g  h  i  j  k  l  m
5 n  o  p  q  r  s  t  u  v  w
6 x  y  z  .  ,  :  ;  '  "  `
7 !  @  #  $  %  ^  &  *  -  +
8 (  )  [  ]  {  }  ?  /  <  >
9 0  1  2  3  4  5  6  7  8  9

en la que cada carácter se representa por el par de números de su fila y su columna. Por ejemplo, la palabra KRIPTOPOLIS se codificaría por el número

K R I P T O P O L I S = 21 28 19 26 30 25 26 25 22 19 29
KRIPTOPOLIS = 2128192630252625221929

Supongo que también podría usarse una tabla en la que tengan cabida los acentos y la Ñ, aprovechando los caracteres no utilizados, pero esto ahora no nos preocupa.

El siguiente paso es generar dos números primos p y q, tan grandes como sea posible, aunque en nuestra versión de juguete nos limitaremos a dos primos diminutos:

p = 439
q = 449
N = p*q = 197111

Después se fabrica número m a partir de los primos:

m = (p – 1) * (q – 1) = 196244

cuya utilidad se verá luego.

Este número se descompone en sus factores primos

m = 196244 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 7 * 73

Ahora necesitamos un número e que no tenga ningún factor común con m, es decir, que sea primo con respecto a él. En esto hay que tener cierto arte, porque luego tendremos que calcular otro número que va a depender de éste. Pongamos que construimos un número de esta forma:

e = 5 * 11 * 19 = 1045

Llegamos a la parte final de esta tarea, y es obtener otro núnero d que, junto con e, cumpla esta curiosa propiedad:

e * d - 1  = múltiplo de m
es decir:
e * d – 1  = m  *  y
e * d =  m * y + 1
d = (m * y  + 1)/e

Para calcular d hay que ir dando valores enteros a y desde 1 en adelante, hasta que el resultado sea entero, de aquí la importancia de elegir “bien” el número e anterior. Para esta operación puede servirnos una hoja de cálculo, como la que se ve en la figura. En nuestro caso, el primer valor entero de d aparece para y = 31

y = 31
d = 5821

Ya tenemos la tarea hecha, salvo el cifrado, claro. Ahora podemos presentar N y e como clave pública, con la que cualquiera podrá mandarnos un mensaje cifrado, mediante la operación

c = x^e modulo N

donde x es el mensaje convertido en un número por el procedimiento antes descrito

Por nuestra parte, con la clave privada -guardada a buen recaudo- que es básicamente el número d, sólo tenemos que descifrar mediante la operación

x = c^d modulo N

y ya está.

Para aplicar este algoritmo se necesita una herramienta que maneje enteros de longitud arbitrariamente larga, incluso para nuestra versión de juguete. Mediante Python, que no es demasiado eficiente, los cálculos son:

Imaginemos que nuestro mensaje es una sola letra, la K de KRIPTOPOLIS, cuyo código es el 21, según la tabla. La operación de cifrado será:

Cifrado
c = 21^e modulo N
c = 21^1045 modulo 197111 =  63202

Si tuviéramos un número par de dígitos se podría presentar como 63 20 etc, es decir .J (punto jota, etc)

Para descifrar sólo tenemos que calcular:

Descifrado
x = c^d modulo N
x =63202^5821 modulo 197111 = 21 = K

Ahora viene la pregunta fundamental: ¿Cómo es posible que la operación de descifrado deshaga lo que hace la de cifrado, siendo tan distintas? Y la respuesta es: Debido al Pequeño Teorema de Fermat: Si a no es divisible por p, siendo p primo, entonces a^(p-1) - 1 es divisible por p

Ahí queda eso. Si no veis la conexión entre ambas cosas, tened paciencia, y seguid estudiando, que mi trabajo ha terminado. Uf.

La fortaleza del sistema, como ya sabéis, radica en que la factorización de un número N grande requiere mucho tiempo de computación, pero algunos opinan que los avances en hardware y, sobre todo los cálculos con GPUs en paralelo, van a traer pronto la muerte de RSA. La gente malpensada cree que alguna Agencia ya lo ha conseguido, y se calla, la muy zorra.

 

Imágenes: 

Didáctico

Muy didáctico. Los conceptos funcionales de la criptografía de clave pública están explicados en multitud de sitios, pero la aplicación concreta de la teoría matemática en que se apoya RSA en muy pocos. Creo, sin embargo y sin ánimo de desmerecer el esfuerzo, que hay alguna e bailada más en tu explicación (normal con tantos números danzando). Concretamente, donde dices

con la clave privada -guardada a buen recaudo- que es básicamente el número e,

Creo que debería decir

con la clave privada -guardada a buen recaudo- que es básicamente el número d,

Sí, es verdad

Ya he reportado alguno de esos errores. Es lo que tiene trabajar compulsivamente hasta altas horas de la madrugada. Por favor, admin, a ver si puedes corregir este par de errores.

Estudiar las matemáticas del RSA

Gracias, Agustín. Ahora mismo estoy con un folio en blanco delante y un lápiz siguiendo los pasos que nos sugieres para entender la mecánica matemática inherente al algoritmo de cifrado asimétrico RSA; es incluso más entretenido que hacer un crucigrama y, lo mejor, es que se puede ir haciendo cuantas veces se desee. Ya tengo la tabla, ahora seguiré con el resto un poco hoy y otro poco mañana... supongo que en unas cuantas semanas habré memorizado el proceso y podré hacerlo sin necesidad de consultar el artículo. Gracias una vez más, es un gran regalo el que nos haces.

Saludos cordiales,

Pedro Fernández
--

P.S. Por cierto, en el primer párrafo, donde dice «...,con la que cualquiera pu[e]de cifrar un documento...» parece faltar una letra que, una vez más, podría ser una 'e'... por si lo queréis corregir aunque en este caso no tiene mayor importancia, creo. Parece como si el gato se te hubiera comido la 'e', ¿eh? ;-)

De lo mejor que he visto

Un trabajo excelente, claro y didáctico, mis felicitaciones.

"Copyleft Fernando Acero Martí­n. Verbatim copying, translation and distribution of this entire article is permitted in any digital medium, provided this notice is preserved. Quotation is allowed."

Muchas gracias por el trabajo

Muchas gracias por el trabajo, la verdad es que siempre me había quedado a la mitad de todas las explicaciones sobre este cifrado, y sólo tenía un conocimiento superficial, auqnue siempre me prometía que al día siguiente iba a buscar una explicación mejor para entederlo cabalmente de una puñetera vez. Mira por donde de lo dan a mantel puesto, vaya lujo.

Veo que las gafas del sr Torner permiten trabajar a Agustín hasta altas horas de la madrugada sin interferencias, están levantando la productividad de Kriptópolis...

Abrumado

Abrumado estoy por vuestra amabilidad. La única forma de que yo pudiera entenderlo era mediante un DIY. Me alegro de que os parezca interesante.

Por si alguien quiere manejar la hoja de cálculo, la tenéis en versión ODS y XLS

El cálculo numérico

Como ya dije, se necesita una herramienta que maneje números enteros largos. A falta de otra cosa, basta invocar el intérprete de Python y escribir los comandos que aparecen en la figura, con su sintaxis característica, donde el operador "**" equivale a la potencia, y el "%" al módulo o resto

Imágenes: 

Excelente trabajo

¡Ese figura!. Cómo se nota que no te ponen la tele en la clínica. Ah, y cómo se te nota también la deformación profesional: tanto tiempo tratando con marujas en la tienda de embutidos ha desarrollado en tí una habilidad especial para hacer comprensible lo incomprensible. Seguro que hasta ellas acabaron entendiendo los mapas.

Descargado el artículo y guardado a buen recaudo.

Cálculo con números largos SOLUCIÓN

No sé si os percatais del todo de la trascendencia de lo que nos ha traído Agustín. Podemos hacer nuestras propias implementaciones de RSA, sin la necesidad de confiar en un software con posibles puertas traseras. Tampoco tendremos la necesidad de confiar en un código abierto pero que, por su longitud, jamás vamos a analizar y que nunca seremos capaces de asegurar al 100% que hace lo que tiene que hacer.

El único problemilla para la implementación real eran los cálculos con números extra-grandes, pues bien gracias a las funciones que vienen en este magnífico artículo, por las que hay que felicitar al autor, el problema queda resuelto.

Las cinco primeras funciones las añadí yo para adaptar el trabajo a Excel (o a Open Office)

Public Function potencio(j1 As String, j2 As String) As String
 
 
Dim X(2) As String
Dim n As Integer, test As Double
 
n = Len(test) - 1
 
X(1) = j1
X(2) = j2
 
potencio = Potencias(X(), n)
 
End Function
 
Public Function divide(j1 As String, j2 As String) As String
Dim X(2) As String
Dim CR() As String
Dim cociente As String
Dim resto As String
 
Dim n As Integer, test As Double
 
Dim Producto As String
 
n = Len(test) - 1
 
X(1) = j1
X(2) = j2
 
CR() = DivisionEuclidea(X(), n)
 
divide = CR(1) & " resto " & CR(2)
 
End Function
 
Public Function resta(j1 As String, j2 As String) As String
Dim X(2) As String
Dim n As Integer, test As Double
 
 
n = Len(test) - 1
 
X(1) = j1
X(2) = j2
 
resta = Restar(X(), n)
 
End Function
 
Public Function suma(j1 As String, j2 As String) As String
Dim X(2) As String
Dim n As Integer, test As Double
 
 
n = Len(test) - 1
 
X(1) = j1
X(2) = j2
 
suma = Sumar(X(), n)
 
End Function
 
Public Function multiplica(j1 As String, j2 As String) As String
Dim X(2) As String
Dim n As Integer, test As Double
 
n = Len(test) - 1
 
X(1) = j1
X(2) = j2
 
multiplica = Multiplicar(X(), n)
 
 
End Function
 
 
Public Function Multiplicar(ByRef xa() As String, ByVal n As Integer) As String
 
 Dim i As Integer, j As Integer, k As Integer, l(2) As Double
Dim m() As Double, a() As Double, X(2) As String, r1() As Double, r2() As Double
Dim prod As Double, p As Double, p0 As String, at As String
Dim sg1 As String, sg2 As String, sg As String, bt As String
Dim xx As String, ll As Double, da As Integer, c As Integer, f As Integer
For i = 1 To 2: X(i) = xa(i): Next i
'---------------- RutinaSigno
sg = "": sg1 = "": sg2 = "": at = "": bt = ""
For i = 1 To 2
If Left$(X(i), 1) = " " Then X(i) = Mid$(X(i), 2)
If Left$(X(i), 1) = "-" Then
sg = "-"
X(i) = Mid$(X(i), 2)
End If
If i = 1 Then sg1 = sg Else sg2 = sg
l(i) = Len(X(i)): sg = ""
Next i
'……………………… Multiplicacion
If l(1) + l(2) <= 2 * n Then
prod = Val(X(1)) * Val(X(2))
If prod <> 0 Then
If sg1 <> sg2 Then
 at = "-"
End If
at = at + Mid$(Str$(prod), 2)
Else
at = "0"
End If
Else
Dim nb As Integer, nc As Integer
If l(1) > l(2) Then
xx = X(1): X(1) = X(2): X(2) = xx 'Cambio
ll = l(1): l(1) = l(2): l(2) = ll
End If
r1() = FormacionBloques(X(1), l(1), n)
c = UBound(r1())
r2() = FormacionBloques(X(2), l(2), n)
f = UBound(r2())
ReDim m(f, c, 2), a(c + f)
k = 1
For j = 1 To f
For i = 1 To c
p = r1(i) * r2(j)
p0 = Right$(Str$(p), 2 * n)
If Left$(p0, 1) = " " Then
p0 = Mid$(p0, 2)
End If
nb = Len(p0)
If nb = 2 * n Then
nc = n
Else
nc = nb - n
End If
If nc < 0 Then nc = 0
m(k, c - i + 1, 2) = Val(Left$(p0, nc))
m(k, c - i + 1, 1) = Val(Right$(p0, n))
Next i
k = k + 1
Next j
For k = 1 To c + f - 1
If k < c + 1 Then
i = 1: j = c - k + 1
Else
i = k - c + 1: j = 1
End If
Do While i <= f
a(k) = a(k) + m(i, j, 1)
a(k + 1) = a(k + 1) + m(i, j, 2)
If j <> c Then
i = i + 1: j = j + 1
Else
Exit Do
End If
Loop
Next k
da = c + f - 1
bt = Desbloqueo(a(), da, n)
If sg1 = sg2 Then
at = bt
Else
at = "-" + bt
End If
 
 End If
Multiplicar = at
End Function
 
 
 ' = = = = = = = = = = =
 
 
 
Public Function Sumar(ByRef xa() As String, ByVal n As Integer) As String
 
 Dim i As Integer, i0 As Integer, j As Integer, k As Integer, l(2) As Double
Dim a() As Double, rt(2) As Variant, X(2) As String, at As String, bt As String
Dim Sum As Double, p As Double, p0 As String, r1() As Double, r2() As Double
Dim sg1 As String, sg2 As String, sg As String, xq As Long
Dim xx As String, ll As Double, da As Integer, c As Integer, f As Integer
For i = 1 To 2: X(i) = xa(i): Next i
'---------------- RutinaSigno
sg = "": sg1 = "": sg2 = ""
For i = 1 To 2
If Left$(X(i), 1) = " " Then X(i) = Mid$(X(i), 2)
If Left$(X(i), 1) = "-" Then
sg = "-"
X(i) = Mid$(X(i), 2)
End If
If i = 1 Then sg1 = sg Else sg2 = sg
l(i) = Len(X(i)): sg = ""
Next i
'------------------- Suma
If l(1) <= 2 * n And l(2) <= 2 * n Then
X(1) = sg1 + X(1)
X(2) = sg2 + X(2)
Sum = Val(X(1)) + Val(X(2))
at = Str$(Sum)
If Left$(at, 1) = " " Then
at = Mid$(at, 2)
End If
Else
at = "": bt = ""
Dim cf As Integer, fr As Integer
Dim a0 As Double
If l(1) > l(2) Then
sg = sg1
Else
If l(1) < l(2) Then 'Cambio
xx = X(1): X(1) = X(2): X(2) = xx
ll = l(1): l(1) = l(2): l(2) = ll
sg = sg2
Else
If X(1) > X(2) Then
sg = sg1
Else
If X(1) = X(2) Then
sg = ""
Else 'Cambio
xx = X(1): X(1) = X(2): X(2) = xx
ll = l(1): l(1) = l(2): l(2) = ll
sg = sg2
End If
End If
End If
End If
 
 r1() = FormacionBloques(X(1), l(1), n)
c = UBound(r1())
r2() = FormacionBloques(X(2), l(2), n)
f = UBound(r2())
cf = c
If cf < f Then cf = f
ReDim a(cf + 1)
da = cf
If sg1 <> sg2 Then fr = -1 Else fr = 1
For k = c To 1 Step -1
a(k) = a(k) + r1(k)
Next k
For k = f To 1 Step -1
a(k) = a(k) + fr * r2(k)
Next k
If fr = -1 Then
For k = 1 To c
If a(k) < 0 Then
a0 = 1
For i = 1 To n
a0 = a0 * 10
Next i
a(k) = a0 + a(k)
a(k + 1) = a(k + 1) - 1
End If
Next k
End If
bt = Desbloqueo(a(), da, n)
at = sg + bt
End If
Sumar = at
End Function
 
 
 
' = = = = = = = = = = =
 
 
 
Public Function Restar(ByRef xa() As String, ByVal n As Integer) As String
 
 Dim i As Integer, i0 As Integer, j As Integer, k As Integer
Dim a() As Double, X(2) As String, at As String, bt As String, a0 As Double
Dim dif As Double, p As Double, p0 As String, r1() As Double, r2() As Double
Dim sg1 As String, sg2 As String, l(2) As Double, sg As String, xq As Long
Dim xx As String, ll As Double, da As Integer, c As Integer, f As Integer
For i = 1 To 2: X(i) = xa(i): Next i
'---------------- RutinaSigno
sg = "": sg1 = "": sg2 = ""
For i = 1 To 2
If Left$(X(i), 1) = " " Then X(i) = Mid$(X(i), 2)
If Left$(X(i), 1) = "-" Then
sg = "-"
X(i) = Mid$(X(i), 2)
End If
If i = 1 Then sg1 = sg Else sg2 = sg
l(i) = Len(X(i)): sg = ""
Next i
'----------------- Resta
at = "": bt = ""
If l(1) <= 2 * n And l(2) <= 2 * n Then
X(1) = sg1 + X(1)
X(2) = sg2 + X(2)
dif = Val(X(1)) - Val(X(2))
at = Str$(dif)
 If Left$(at, 1) = " " Then
at = Mid$(at, 2)
End If
Else
Dim cf As Integer, fr As Integer
If sg2 = "-" Then sg2 = "" Else sg2 = "-"
If l(1) > l(2) Then
sg = sg1
Else
If l(1) < l(2) Then 'Cambio
xx = X(1): X(1) = X(2): X(2) = xx
ll = l(1): l(1) = l(2): l(2) = ll
sg = sg2
Else
If X(1) > X(2) Then
sg = sg1
Else
If X(1) = X(2) Then
sg = ""
Else 'Cambio
xx = X(1): X(1) = X(2): X(2) = xx
ll = l(1): l(1) = l(2): l(2) = ll
sg = sg2
End If
End If
End If
End If
r1() = FormacionBloques(X(1), l(1), n)
c = UBound(r1())
r2() = FormacionBloques(X(2), l(2), n)
f = UBound(r2())
cf = c
If cf < f Then cf = f
ReDim a(cf + 1)
da = cf
If sg1 <> sg2 Then fr = -1 Else fr = 1
For k = c To 1 Step -1
a(k) = a(k) + r1(k)
Next k
For k = f To 1 Step -1
a(k) = a(k) + fr * r2(k)
Next k
If fr = -1 Then
For k = 1 To c
If a(k) < 0 Then
a0 = 1
For i = 1 To n
a0 = a0 * 10
Next i
a(k) = a0 + a(k)
a(k + 1) = a(k + 1) - 1
End If
Next k
End If
bt = Desbloqueo(a(), da, n)
at = sg + bt
End If
Restar = at
 
End Function
 
 
 
' = = = = = = = = = = =
 
 
 
Public Function DivisionEuclidea(ByRef xa() As String, ByVal n As Integer) As Variant
 
 Dim i As Integer, i0 As Integer, j As Integer, k As Integer
Dim m() As Double, a() As Double, rt(2) As String, X(2) As String
Dim dif As String, coci As Double, qx As String
Dim sg1 As String, sg2 As String, l(2) As Double, sg As String, xq As Long
Dim ll As Double, da As Integer, rx As String, at As String, bt As String
For i = 1 To 2: X(i) = xa(i): Next i
'---------------- RutinaSigno
sg = "": sg1 = "": sg2 = ""
For i = 1 To 2
If Left$(X(i), 1) = " " Then X(i) = Mid$(X(i), 2)
If Left$(X(i), 1) = "-" Then
sg = "-"
X(i) = Mid$(X(i), 2)
End If
If i = 1 Then sg1 = sg Else sg2 = sg
l(i) = Len(X(i)): sg = ""
Next i
'--------------- Division Euclidea
If l(1) < l(2) Or (l(1) = l(2) And X(1) < X(2)) Then
rt(1) = "0": rt(2) = xa(1)
DivisionEuclidea = rt()
Exit Function
End If
If l(1) < 2 * n + 2 And (l(1) > l(2) Or (l(1) = l(2) And X(1) >= X(2))) Then
coci = Int(Val(X(1)) / Val(X(2)))
qx = Mid$(Str$(coci), 2)
rx = Mid$(Str$(Val(X(1)) - coci * Val(X(2))), 2)
Else
Dim dl As Integer
Dim zz As String
qx = "": rx = "": xq = 0
dl = Abs(l(1) - l(2))
If dl <> 0 Then
If X(1) < X(2) Then
dl = dl - 1
If dl <> 0 Then
For k = 1 To dl
X(2) = X(2) + "0"
Next k
l(2) = l(2) + dl
End If
Else
For k = 1 To dl
X(2) = X(2) + "0"
Next k
l(2) = l(2) + dl
End If
End If
Do
Do
dif = Restar(X(), n)
If Left$(dif, 1) = "-" Then
X(1) = Mid$(dif, 2)
Else
X(1) = dif
 
 End If
xq = xq + 1
If Len(X(1)) < Len(X(2)) Then Exit Do
If Len(X(1)) = Len(X(2)) And X(1) < X(2) Then
Exit Do
Else
at = "": bt = ""
l(1) = Len(X(1))
End If
Loop
zz = Str(xq): xq = 0
Do
If Left$(zz, 1) = " " Then
zz = Mid$(zz, 2)
Else
Exit Do
End If
Loop
Do
qx = qx + zz
If dl = 0 Then
rx = X(1)
Exit Do
End If
X(2) = Mid$(X(2), 1, Len(X(2)) - 1)
If Len(X(1)) > Len(X(2)) Then Exit Do
If Len(X(1)) = Len(X(2)) And X(1) >= X(2) Then
Exit Do
Else
dl = dl - 1: zz = "0"
End If
Loop
If dl = 0 Then Exit Do
dl = dl - 1
l(1) = Len(X(1)): l(2) = Len(X(2))
Loop
End If
If qx <> "0" Then
If sg1 = "" And sg2 = "" Then
rt(1) = qx: rt(2) = rx
End If
If sg1 = "-" And sg2 = "-" Then
rt(1) = qx: rt(2) = "-" + rx
End If
If sg1 = "" And sg2 = "-" Then
rt(1) = "-" + qx: rt(2) = rx
End If
If sg1 = "-" And sg2 = "" Then
rt(1) = "-" + qx: rt(2) = "-" + rx
End If
Else
rt(1) = "0" And rt(2) = xa(2)
End If
DivisionEuclidea = rt()
End Function
 
 
' = = = = = = = = = = =
 
 
Public Function Potencias(ByRef xa() As String, ByVal n As Integer) As String
 
 Dim i As Long, X(2) As String, sgb As Integer, pexp As Integer
 
 Dim ed As String, j As String, pr As String, y(2) As String, z(2) As String
 
 For i = 1 To 2
 
 X(i) = xa(i)
 
 If Left$(X(i), 1) = " " Then X(i) = Mid$(X(i), 2)
 
 Next i
 
 If Left$(X(1), 1) = "-" Then
 
 X(1) = Mid$(X(1), 2): sgb = 1
 
 End If
 
 If Left$(X(2), 1) = "-" Then
 
 X(2) = Mid$(xa(2), 2) ' el exponente no puede ser negativo
 
 End If
 
 If X(1) = "0" And X(2) = "0" Then
 
 Potencias = "Resultado indeterminado"
 
 Exit Function
 
 End If
 
 If X(1) = "0" And X(2) <> "0" Then
 
 Potencias = "0"
 
 Exit Function
 
 End If
 
 If X(2) = "0" And X(1) <> "0" Then
 
 Potencias = "1"
 
 Exit Function
 
 End If
 
 If X(2) = "1" Then
 
 Potencias = X(1)
 
 Exit Function
 
 End If
 
 ed = Right$(X(2), 1)
 
 pexp = Val(ed) Mod 2
 
 y(1) = X(1): y(2) = X(1): j = "1"
 
 Do
 
 pr = Multiplicar(y(), n)
 
 y(1) = pr: z(1) = j: z(2) = "1"
 
 j = Sumar(z(), n)
 
 If j = X(2) Then Exit Do
 
 Loop
 
 If sgb = 0 Then
 
 Potencias = pr
 
 Else
 
 If pexp = 0 Then Potencias = pr Else Potencias = "-" + pr
 
 End If
 
End Function
 
 
 
'= = = = = = = = = = =
 
 
 
Public Function MaxComDiv(ByRef xa() As String, ByVal n As Integer) As String
 
 Dim i As Integer, j As Integer, k As Integer
Dim X(2) As String, l(2) As Double, rr() As String
Dim xx As String, ll As Double, rr0 As String
Dim q0 As Double, q1 As Double, r0 As Double, r1 As Double
For i = 1 To 2: X(i) = xa(i): Next i
'---------------- RutinaSigno
For i = 1 To 2
If Left$(X(i), 1) = " " Then X(i) = Mid$(X(i), 2)
If Left$(X(i), 1) = "-" Then X(i) = Mid$(X(i), 2)
l(i) = Len(X(i))
Next i
'Máximo Común Divisor
 
 
 If l(1) <= l(2) Then
If l(1) < l(2) Then 'Cambio
xx = X(1): X(1) = X(2): X(2) = xx
ll = l(1): l(1) = l(2): l(2) = ll
Else
If X(1) < X(2) Then 'Cambio
xx = X(1): X(1) = X(2): X(2) = xx
ll = l(1): l(1) = l(2): l(2) = ll
End If
End If
End If
Do
If l(1) <= 2 * n And l(2) <= 2 * n Then
q0 = Val(X(1)): r0 = Val(X(2))
Do
q1 = q0 / r0
q1 = Int(q1)
r1 = q0 - q1 * r0
If r1 = 0 Then Exit Do
q0 = r0: r0 = r1
Loop
rr0 = Mid$(Str(r0), 2)
MaxComDiv = rr0
Exit Function
Else
y0 = X(2)
rr() = DivisionEuclidea(X(), n)
If rr(2) = "0" Then
rr0 = y0
MaxComDiv = rr0
Exit Function
Else
X(1) = y0: l(1) = Len(X(1))
X(2) = rr(2): l(2) = Len(X(2))
End If
End If
Loop
End Function
 
 
' = = = = = = = = = = =
 
 
 
Public Function MinComMult(ByRef xa() As String, ByVal n As Integer) As String
 
 Dim i As Integer, X(2) As String, rr0 As String, x2 As String, rr() As String
For i = 1 To 2: X(i) = xa(i): Next i
'---------------- RutinaSigno
For i = 1 To 2
If Left$(X(i), 1) = " " Then X(i) = Mid$(X(i), 2)
If Left$(X(i), 1) = "-" Then X(i) = Mid$(X(i), 2)
Next i
'Mínimo Común Múltiplo
rr0 = MaxComDiv(X(), n) 'MaximoComunDivisor
If Len(X(1)) <= 2 * n Then
X(1) = Mid$(Str$(Val(X(1)) / Val(rr0)), 2)
Else
x2 = X(2): X(2) = rr0
rr() = DivisionEuclidea(X(), n)
X(1) = rr(1): X(2) = x2
End If
 
 
 MinComMult = Multiplicar(X(), n)
End Function
 
' = = = = = = = = = = =
 
 
 
Public Function FormacionBloques(xx As String, lx As Double, ByVal n As Integer) As Variant
 
 ' --------- FORMACIÓN DE LOS BLOQUES
Dim l1 As Single, k As Double, r() As Double
Dim li As Double, lm As Double, na As Integer
l1 = lx / n
If l1 = Int(l1) Then lm = l1 Else lm = Int(l1) + 1
ReDim r(lm)
na = n
For k = 1 To lm
li = lx - k * n + 1
If li < 1 Then
na = na - (1 - li)
li = 1
End If
r(k) = Val(Mid$(xx, li, na))
Next k
FormacionBloques = r()
End Function
 
 
' = = = = = = = = = = =
 
 
 
Public Function Desbloqueo(ByRef a() As Double, ByVal da As Integer, ByVal n As Integer) As String
 
' ----------------DESBLOQUEO
Dim la As Integer, lp As Integer, lr As Double, w As Integer, at As String
Dim aa As String, a1 As String, a2 As String, k As Integer, i As Integer, bt As String
For k = 1 To da
aa = Str$(a(k)): la = Len(aa)
a1 = Right$(aa, n)
a(k) = Val(a1)
If la > n Then
a2 = Left$(aa, la - n)
a(k + 1) = a(k + 1) + Val(a2)
End If
Next k
w = da + 1
Do
If a(w) <> 0 Then Exit Do
If w = 0 Then
Desbloqueo = "0"
Exit Function
End If
w = w - 1
Loop
For k = w To 1 Step -1
aa = Str$(a(k)): lp = Len(aa) - 1
For i = 1 To n - lp
at = at + "0"
Next i
at = at + Right$(aa, lp)
Next k
Do Until Mid$(at, 1, 1) <> "0"
at = Mid$(at, 2)
Loop
lr = Len(at)
Desbloqueo = Mid$(at, 1, lr)
End Function

La forma de utilizarlas desde Excel es muy sencilla, veáse algún ejemplo como el cálculo de potencias:

Imágenes: 

Utilización de las funciones

Cuidado con las implementaciones personales de RSA

Para que la codificación RSA sea segura, los primos "p" y "q" elegidos deben cumplir ciertas condiciones. De lo contrario, puede romperse fácilmente el sistema, independientemente de lo grandes que sean "p" y "q". Ahora mismo sólo recuerdo dos de esas condiciones. Una es que "p" y "q" deben ser de tamaños en bits parecidos, pero deben tener una diferencia lo suficientemente grande como para impedir su descomposición prima con el método de factorización de Fermat. Otra creo recordar que "p-1" y "q-1" deben estar compuestos por primos grandes (no cuenta el 2, por supuesto), que si no se cumple, puede romperse el código también. Hay más condiciones, pero ahora no recuerdo, que si no se cumplen, facilitan el descifrado

Tienes razón.

Es totalmente cierto lo que dice el compañero, fácilmente si no se tiene cuidado con la elección de p y q se puede factórizar en un tiempo razonable N = p*q. Los invito a que miren este documentos http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html o para una información mas profunda pueden buscar en su biblioteca un libro llamado "Cryptanalytic Attacks on RSA" o "Cryptanalysis of RSA and its Variants".

Saludos.

Excelente trabajo

Tanto el de Aladár Péter Sántha como el tuyo, con tu implementación para las hojas de cálculo.

Atendiendo a las fundamentadas advertencias de Sqrmatrix, quizá no fuera prudente utilizar un RSA casero como programa "profesional", a menos que un equipo de sabios -entre los que sin duda estaría él- se encargue de confeccionarlo con todas las garantías. Lo que sí sería factible es alguna implementación para uso doméstico, como retos, etc, con lo que todos acabaríamos aprendiendo algo más.

De todas maneras, mi objetivo era mucho más modesto, ya que sólo pretendía entender la base del sistema. Y aún me quedan cosas pendientes, Por ejemplo, no tengo clara la relación entre la longitud del texto a cifrar y el tamaño que deben tener los números primos. También veo alguna dificultad en la conversión del número cifrado a texto cifrado, si no se obtiene un número par de dígitos, y no sé de que depende esta circunstancia. Pero son cosas que de momento no me preocupan.

Gracias por tu interés y por tu aportación.

P.S:
¿Podrías poner un enlace a tu hoja de cálculo?

Respuesta.

No se si sea el indicado para responder, pero intentare.

La longitud de los números primos p y q depende mas de que no sea fácil encontrarlos teniendo N = p*q, como sabemos la criba general de campo numérico es el algoritmo de factorización mas "rápido" para números menores a 400 bits de longitud. Obviamente p y q deben cumplir ciertas relaciones.

La longitud del texto a cifrar, si mas no recuerdo dependía era del método de codificación usado, y por lo general cuando el texto sobrepasaba una longitud máxima, que depende de N, se prefería realizar el cifrado partiendo el texto en bloques y cifrando cada bloque.

La verdad no recuerdo si era así, de todos modos este puede ser un buen documento para leer: ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf

Saludos.

Curiosidad curiosa

Cuando leía este comentario, aparte del interés de todo el artículo en sí, me llamó la atención un pequeño detalle del que envío captura convenientemente "anonimizada".

Admin, ¿dónde está alojado el servidor? porque o está en una zona que queda fuera del GMT+1 o aquí hay gato encerrado. ¿En qué clase de secreta conspiración os habéis metido? :-D

Imágenes: 

Obviamente...

País predefinido: España
Zona horaria predefinida: Euopa/Madrid
Los usuarios pueden establecer su zona horaria.
------------------
La hora y fecha son correctas y exactas. Comprobado.

Interesante artículo

Está muy bien, sobre todo porque gente que no tiene muchos conocimientos podrá entender la base del sistema.

Sólo me gustaría añadir una cosa. El valor de "d" es la solución de la congruencia e*x=1(mod m), la cual se resuelve con el algoritmo inverso de Euclides (aplicado a la ecuación e*x+m*y=1), que es un método rápido y eficiente, por lo que no hay que ir buscando el valor uno a uno

Pues estaría bien poner en el

Pues estaría bien poner en el propio artículo la fórmula de calcular d, para no andar buscándola en los comentarios, y recopilar esas condiciones que han de cumplir p y q, para que las implementaciones realizadas sean buenas.

Algoritmo de Euclides inverso

Aquí pongo el algoritmo inverso de Euclides tal y como lo tengo codificado en Java, aunque le he quitado los comentarios explicativos, que ocupan un montón y quizá pueden liar.

Lo que yo hago es resolver la ecuación diofántica a*x+m*y=mcd(a,m), de tal forma que sólo necesito especificar "a" y "m", y tengo asegurado que voy a encontrar la solución, porque en una ecuación diofántica del tipo a*x+b*y=c, es necesario y suficiente que mcd(a,b) divida a "c" para que tenga solución. Si luego quiero obtener la solución de la ecuación a*x+m*y=k, bastará multiplicar las soluciones encontradas antes por k/mcd(a,m) (por supuesto, "k" ha de ser divisible por mcd(a,m)).

Por otro lado, teniendo en cuenta que la congruencia a*x=b(mod m), por definición de congruencia, implica que "m" divida a a*x-b, lo que a su vez significa que existirá un "y" tal que a*x-b=m*y, desarrollando obtenemos la ecuación diofántica a*x+m*(-y)=b, que puede resolverse por el método que se va a exponer a continuación. Por cierto, la solución obtenida es solución módulo "m", es decir, que existen infinitas soluciones, pero nos basta una de ellas (normalmente la que se calcula haciendo módulo "m") para tenerlas todas definidas.

Hay que tener en cuenta que este método sólo nos consigue una solución módulo "m". Si la congruencia tiene más soluciones, hay que hacer otras operaciones para obtenerlas todas ellas.

El método que tengo para números arbitrariamente grandes es:

 //Se devuelve un array de 2 elementos, el primero de ellos contiene la solución de "x", y el
 //segundo la solución de "y"
 public BigInteger[] euclidesInverso(BigInteger a,BigInteger b)
 {
  //Necesitamos que "a>b". Si tenemos que intercambiarlos, las variables "x" e "y" también se
  //intercambiarán en el cálculo. El flag "intercambio" nos indicará si se intercambiaron para
  //devolver las variables correctamente
  boolean intercambio=false;
  if(a.compareTo(b)<0)
  {
   BigInteger aux=b;
   b=a;
   a=aux;
   intercambio=true;
  }
 
  BigInteger mcd=a.gcd(b);
 
  //Variables para la primera igualdad. Les damos el valor 0
  BigInteger x1=BigInteger.ZERO,y1=BigInteger.ZERO,r1=BigInteger.ZERO;
 
  //Variables para la segunda igualdad
  BigInteger x2=BigInteger.ONE; //x2=1
  BigInteger y2=a.divide(b).negate(); //y2=-int(a/b)
  BigInteger r2=a.multiply(x2).add(b.multiply(y2)); //r2=a·x2+b·y2
 
  //Si "r2=0", significa que mcd(a,b)=b y, por tanto, "0·a+1·b=mcd(a,b)", es decir, que "x=0" y
  //"y=1"
  if(r2.equals(BigInteger.ZERO))
  {
   if(intercambio)
    return new BigInteger[]{BigInteger.ONE,BigInteger.ZERO};
   return new BigInteger[]{BigInteger.ZERO,BigInteger.ONE};
  }
 
  //Si r2=mcd(a,b), ya tenemos los valores de "x" y de "y" (x=1)
  if(r2.equals(mcd))
  {
   if(intercambio)
    return new BigInteger[]{y2,BigInteger.ONE};
   return new BigInteger[]{BigInteger.ONE,y2};
  }
 
  //Declaramos las variables y les damos los valores para el primer paso
  BigInteger k=b.divide(r2); //k=b/r2
  BigInteger x3=k.negate(); //x3=-k
  BigInteger y3=BigInteger.ONE.subtract(y2.multiply(k)); //y3=1-y2*k
  BigInteger r3=a.multiply(x3).add(b.multiply(y3)); //r3=a*x3+b*y3
 
  //Algoritmo de Euclides inverso. Terminará cuando hallamos obtenido el máximo común divisor
  while(!r3.equals(mcd))
  {
   x1=x2;
   y1=y2;
   r1=r2;
   x2=x3;
   y2=y3;
   r2=r3;
   k=r1.divide(r2); //k=int(r1/r2)
   x3=x1.subtract(k.multiply(x2)); //x3=x1-k*x2
   y3=y1.subtract(k.multiply(y2)); //y3=y1-k*y2;
   r3=a.multiply(x3).add(b.multiply(y3)); //r3=a*x3+b*y3;
  }
 
  if(intercambio)
   return new BigInteger[]{y3,x3};
  return new BigInteger[]{x3,y3};
 }

El método que tengo para enteros de tipo "long" (64 bits si no me equivoco) es:

 //Como antes, se devuelven "x" e "y" en un array, "x" ocupando la primera posición, "y" la
 //segunda
 public static long[] euclidesInverso(long a,long b)
 {
  //Necesitamos que "a>b". Si tenemos que intercambiarlos, las variables "x" e "y" también se
  //intercambiarán en el cálculo. El flag "intercambio" nos indicará si se intercambiaron para
  //devolver las variables correctamente
  boolean intercambio=false;
  if(a<b)
  {
   long aux=b;
   b=a;
   a=aux;
   intercambio=true;
  }
 
  long mcd=mcd(a,b); //Se especifica este método más adelante
 
  //Variables para la primera igualdad. Les damos el valor 0
  long x1=0,y1=0,r1=0;
 
  //Las variables con sufijo "2" tomarán los valores del primer paso de este algoritmo
  long x2=1;
  long y2=-a/b;
  long r2=a*x2+b*y2;
 
  //Si "r2=0", significa que mcd(a,b)=b y, por tanto, "0·a+1·b=mcd(a,b)", es decir, que "x=0" y
  //"y=1"
  if(r2==0)
  {
   if(intercambio)
    return new long[]{1,0};
   return new long[]{0,1};
  }
 
  //Si r2=mcd(a,b), ya tenemos los valores de "x" y de "y" (x=1)
  if(r2==mcd)
  {
   if(intercambio)
    return new long[]{y2,1};
   return new long[]{1,y2};
  }
 
  //Declaramos las variables y les damos los valores para el primer paso
  long k=b/r2;
  long x3=-k;
  long y3=1-y2*k;
  long r3=a*x3+b*y3;
 
  //Algoritmo de Euclides inverso. Terminará cuando hallamos obtenido el máximo común divisor
  while(r3!=mcd)
  {
   x1=x2;
   y1=y2;
   r1=r2;
   x2=x3;
   y2=y3;
   r2=r3;
   k=r1/r2;
   x3=x1-k*x2;
   y3=y1-k*y2;
   r3=a*x3+b*y3;
  }
 
  if(intercambio)
   return new long[]{y3,x3};
  return new long[]{x3,y3};
 }
 
 //Éste es algoritmo para el cálculo de máximo común divisor
 public long mcd(long a,long b)
 {
  //El máximo común divisor será positivo, por definición (si fuera negativo, el valor positivo
  //sería mayor y, por tanto, el valor negativo no sería máximo)
  if(a<0)
   a=-a;
  if(b<0)
   b=-b;
 
  //mcd(n,0)=mcd(0,n)=n
  if(a==0)
   return b;
  if(b==0)
   return a;
 
  //mcd(n,1)=mcd(1,n)=1
  if(a==1 || b==1)
   return 1;
 
  //Preparamos los valores para que a>b, pues es necesario en el algoritmo
  if(a<b)
  {
   long c=a;
   a=b;
   b=c;
  }
 
  //Algoritmo de Euclides
  long r;
  do
  {
   r=a%b;
   a=b;
   b=r;
  }
  while(r!=0);
 
  return a;
 }

Bueno, espero que se entienda. Si no, ya sabéis, preguntad

No es que lo haya entendido...

...todavía, pero considero que el rigor de tus razonamientos es imprescindible en esta página. Lo que no dejo de pensar, desde mi punto de vista, algo simplón, es que la solución de la ecuación diofántica, buscando los menores enteros, por una simple iteración, tampoco me parece una mala solución. De hecho, para un planteamiento (auto)didáctico me parece más accesible que el algoritmo de Eucilides inverso. Pero que conste que reconozco la superioridad de tu planteamiento.

Gracias por tu aportación.

A mi lo que me intriga del

A mi lo que me intriga del algoritmo RSA es precisamente la eleccion de p y q. ¿Como se buscan? ¿Como se que un numero p muy grande es primo? ¿Hay acaso un "mercado" de numeros primos? O hay maneras de construirlos.

Los sistemas de comunicación basados en RSA, siempre tienen la misma clave publica o van actualizandola. Por ejemplo, cuando nos conectamos a una pagina https es mediante RSA no? Y en ese caso, el servidor web siempre usa la misma clave publica para todas las conexiones? De donde ha sacado el administrador los Ps i Qs correspondientes.

Por otra parte, me sumo a las felicitaciones a Agustin por su articulo y a las contribuciones de los demás en forma de comentarios.

Interesante cuestión

Hay gigantescas bases de datos con gigantescos números primos descritos mediante su fórmula generatriz, pero la cuestión de cómo se eligen es complicada, según nos contaba sqrmatrix. Espero que alguien como él amplíe el tema. Gracias por tu post.

Respecto al https

Básicamente la idea es que cuando haces una petición https a un servidor éste te un certificado X.509 entre cuyos campos se encuentra su clave pública. Ésta ha de ser fija puesto que ese certificado debería haber sido emitido por una autoridad de confianza para el sitio quien a su vez lo ha firmado con su clave privada para permitir su verificación.

Ahora bien, RSA, como es muy costoso en cálculo, sólo se usará para asegurar la comunicación posterior. Así cuando un cliente recibe el certificado del servidor lo usa sólo para cifrar una clave simétrica que envía al servidor (quien la descifra con la privada) que será la que efectivamente se usará en el resto de las comunicaciones.

De tu explicación entiendo

De tu explicación entiendo que si yo quiero implementar un servidor web que soporte https, tengo que ir a una entidad certificadora a que me emita un certificado para mi clave publica. Pero entonces la pregunta es: ¿De donde saco los p y q para generar mi clave publica? Si la respuesta es que me lo proporciona la entidad certificadora, entonces ¿De donde los saca ella?

No lo he hecho nunca, pero tengo entendido (y corregidme si me equivoco) que me puedo instalar un apache em mi ordenador de casa con los modulos correspondientes para poder hacer conexiones https y pasar de entidades certificadoras no? El unico "inconveniente" es que al cliente que se conecte el navegador le avisará que como hay entidad certificadora, no soy de "fiar" (con lo buena persona que soy). Es decir, mi flamante instalacion de Apache generará un par de claves publica/privada y por tanto necesitara los correspondientes p y q. De donde los saca?

Entiendo que hay por tanto algoritmos para generar numeros primos grandes no?

Generar un número primo

Generar un número primo nuevo es todo un acontecimiento, aunque no tenga el record de longitud. Por otra parte, no hay algoritmos sencillos -ni creo que complejos- que garanticen al 100% que un numero es primo, sino que hay que pasarle luego muchas pruebas para conseguir establecer la primalidad. De manera que dudo mucho que se utilicen esos algorimos -aunque puedo estar equivocado-. Yo diría que se recurre al arsenal de primos ya establecidos. Pero como ya hemos comentado, esperamos que los que sepan más de esto nos lo amplíen.

Si no recuerdo mal

Si no recuerdo mal, el problema no está en generar números primos (que hay algoritmos conocidos. El más simple creo que venía siendo 2^n-1 con la particularidad de que n sea primo (números primos de Mersenne)) si no en la operación inversa, dado un número suficientemente grande saber si es primo o no (problema de la factorización). Los algoritmos de generación de números primos te dan algunos de los disponibles, pero no todos.

Pues yo sigo pensando que

Pues yo sigo pensando que igual era buena idea que hiciésemos un RSA Open Source aquí, en Kriptópolis. Inicialmente seguro que tendría muchos problemillas, pero se podrían ir corrigiendo sobre la marcha con aportaciones de la concurrencia.

Vale, pero

Yo lo veo como un ejercicio, es decir, como una una manera de aprender, al menos para algunos, más que como la producción de un sofware profesional.

Antes que eso me gustaría entender los entresijos del ECC (Elliptic Curve Cipher), que también es interesante en el panorama del cifrado de clave pública.

[Curso UPM] Completado desde ayer

Gracias, LlamameX, por haber dado con este curso de lujo y por compartirlo aquí, en Kriptópolis.

Este MOOC Crypt4you de la Universidad Politécnica de Madrid también a mí me parece fantástico y estoy de acuerdo en que no tiene desperdicio ;-)

Ayer mismo ha sido publicada la lección 10, que es la última lección y lo deja completado, aunque al final dice que los creadores siguen trabajando y han decidido dejar el apartado 10.3 pendiente hasta concluir y publicar un nuevo trabajo de documentación y detalle que están elaborando.

Sólo piden que, por favor, se ayude a mejorar estos cursos completando la encuesta:

http://www.criptored.upm.es/crypt4you/encuesta/index.php

Imágenes: 

mooc-rsa.png

Sobre obtener números primos

No se utilizan tablas de números primos, porque de ser así, si un atacante accede a ellas, descifraría cualquier código con n=p*q, sabiendo que los números primos p y q están en esa tabla. Con una simple búsqueda puede encontrar uno de ellos rápidamente, sin importar lo grande que sea esa tabla (se tarda más en hacer esa tabla que en buscar primos en ella, con lo que si queremos que la búsqueda consuma un determinado tiempo "t", esa tabla tardará en construirse más tiempo), y el otro lo encontrará dividiendo n por dicho primo.

Para generar un número primo, basta obtener un número aleatorio impar de los dígitos deseados, y aplicar tests de primalidad, con los cuales se obtiene una certeza tan cercana al 100% como se desee (a costa de aumentar los cálculos y, por tanto, el tiempo de ejecución, pero un tiempo razonable). Si resulta que el número no es primo, podemos elegir entre repetir el proceso con otro número aleatorio, o entre sumarle (o restarle) 2 al anterior número y volver a probar. Esta suma y resta no tomará mucho tiempo, porque los números primos no están "demasiado lejos" unos de otros.

Lenguajes como Java ofrecen tests de primalidad y generadores pseudoaleatorios con los que se pueden buscar números primos por el procedimiento descrito. También ofrecen un generador de números aleatorios de k dígitos probablemente primos, especificando la certeza que queremos tener de que sea primo

Gracias por la información

Si no se hicieran los suficientes tests de primalidad se correría el riesgo de que el número no fuera primo.

Sin embargo, para los números Mersenne existe un test eficiente y seguro, el de Lucas-Lehmer. Imagino que una forma más segura -y más eficiente- sería generar números de Mersenne, en vez de números aleatorios, ¿no?

Un saludo.

No es una buena idea utilizar

No es una buena idea utilizar números primos de Mersenne. El problema de los números primos de Mersenne es que son extraordinariamente difíciles de encontrar, y a medida que encontramos más, van creciendo extraordinariamente. Según la Wikipedia, sólo se conocen 47 primos de Mersenne, el mayor de ellos con casi 13 millones de dígitos decimales. Encontrar un nuevo primo de Mersenne es un acontecimiento a nivel mundial (dentro de los círculos científicos, claro).

Los test de primalidad que existen que se ejecutan en un tiempo aceptable, aunque no ofrecen garantías al 100%, ofrecen suficientes garantías como para confiar en ellos. También existen tests que nos aseguran al 100% la primalidad de un entero, pero son excesivamente lentos.

Por ejemplo, hay un test (ahora no recuerdo cuál, y puede que haya más de un test así) en el que cada testeo reduce a la mitad la probabilidad de que el entero haya pasado el test siendo compuesto. Esto significa que si testeamos 100 veces el número, la probabilidad de que sea compuesto es de 1/2^100. Es más fácil que te toque la lotería a que el número sea compuesto si pasa el test después de 100 rondas. Java tiene un testeador así, y puede hacerse el test de 100 rondas (o las que se elijan) en un tiempo razonable. Me imagino que otros lenguajes tendrán testeadores similares.

Tienes razón

Precisamente le recordaba eso a Squirrel -lo de los 47 Mersennes- no hace mucho, en cambio no lo he tenido presente al contestarte. Despistes que tiene uno.

Gracias de nuevo.

Ni lo había visto

Lo siento, me sonaba lo del 2^n-1 y simplemente busqué de donde salía, no me paré a comprobar el artículo completo y ver que eran tan pocos. Me disculpo si he inducido a alguien a error.

Tu pregunta

No entendí bien tu pregunta, hasta que me la aclaraste por el telefonillo. En efecto, parece que RSA con claves de 1024 bits ya no se considera seguro. En la página antigua de Kriptópolis se debatió el tema en diversos hilos. Puedes consultar este excelente post de Fernando Acero

por que dices que practicamente ninguno?

Se supone que es un sistema de cifrado, si existe la manera de descifrarlo en poco tiempo el sistema carece de sentido, no?
Según he leido los sistemas de seguridad mundial se basan en el sistema RSA, por lo tanto si fueran capaces de resolverlo en poco tiempo cualquier seguridad sería hakeada y creo que supondria un problema no?

Ten en cuenta

Ten en cuenta que se trata del Factorizador Loco. Si es capaz de factorizar con rapidez numeros monstruosos, el problema está resuelto. Claro que tendría que demostrarlo.

Restricción de longitud de clave RSA

Como bien señala Agustín más arriba, en esta misma entrada, el tema ya fue excelentemente debatido en la entrada Supuesta rotura de la clave privada RSA de 1024-bits, enviada por ghostDancer el 05 de marzo de 2010, sábado, y de la que además de la explicación proporcionada por Fernando Acero; también destacaría la de kevin mitnick. Cito ambas por ser en mi opinión de sumo interés y porque no ocupan demasiado espacio aunque creo merece la pena leer la entrada en su totalidad por aclaratoria y oportuna:

Esto es antiguo
============
kevin mitnick 7 Marzo 2010 - 5:37am
.
es un típico "side channel attack" como por ejemplo www-cs.stanford.edu/~dabo/papers/ssl-timing.pdf.
.
sin embargo las claves de 1024 ya no son seguras, Bruce Schneier lo lleva diciendo desde hace 10 años, para el las claves deberian ser de 4096 bits que es el equivalente a las claves de 128 bits en cifrados simetricos.
.
1024 bits equivale a 80 bits...

Esto es lo que dice el NIST al respecto
=============================
Fernando Acero 6 Marzo 2010 - 9:24pm
.
Hay un interesante DRAFT del NIST americano, que dice que las claves RSA con una longitud de 1024, no se deberían usar más allá del año 2010. Para el caso del transporte de claves, las condiciones se endurecen todavía más.
.
Desde mi punto de vista, no solamente se debería hacer una transición a claves de mayor tamaño, posiblemente mayores de 2048, si queremos que nuestros secretos sigan siendo secretos durante un tiempo razonablemente alto, también se debería usar curvas elípticas en lugar de números primos para generar las claves.
.
Por cierto, hay un pequeño problema con las claves generadas mediante números primos industriales. Antes, el algoritmo para comprobar la primalidad era heurístico y desgraciadamente se sigue usando en la mayoría de los sistemas criptográficos (Miller-Rabin o test fuerte de pseudoprimos), es decir, que no había certeza absoluta de que los primos industriales elegidos para crear las claves eran primos de verdad, aunque sí con un elevado grado de fiabilidad, que era función de las iteraciones que se realizasen del test. Es decir, se puede mejorar la seguridad aumentando el número de iteraciones de forma arbitraria, lo que también supondrá un mayor tiempo para la generación de las claves.
.
Sin embargo, ahora existe un sistema determinista en tiempo polinómico (AKS - Agrawal, Kayal y Saxena), es decir, que permite saber si un número primo es o no primo, con una fiabilidad del 100%. El uso de AKS permitiría mejorar algo la seguridad teniendo la certeza absoluta que los números elegidos para generar las claves, son primos de verdad.
.
Un saludo, Fernando Acero

No obstante es necesario señalar que de momento la longitud de las claves de cifrado asimétrico -o llaves de encriptación asimétrica si se prefiere una traducción más literal del inglés también correcta pero algo más confusa en nuestro idioma-, autenticación o firma digital de documentos electrónicos está sujeta a las leyes y restricciones de exportación de los EEUU que limitan a las empresas con base en dicho país a la hora de exportar sus productos criptográficos las longitudes máximas de dichas claves de cifrado asimétrico a 1024 bits y a determinados algoritmos; aunque sus productos puedan trabajar, si se configuran adecuadamente, con claves de mayor longitud y fuera necesario eliminar la restricción de longitud de clave por no ser de aplicación o por ser inconviente en el país de destino.

Es el caso de Oracle, por ejemplo, que como actual propietaria de Sun Microsystems también lo es de su extendido producto Java por lo que el usuario de un navegador web que necesite dicho producto deberá añadir los ficheros de políticas de seguridad que evitan estas limitaciones. Son las extensiones denominadas Java Cryptography Extension (JCE) Unlimited Strength Jurisdiction Policy Files y la versión a utilizar dependerá del navegador, del sistema operativo y de la versión de Java que tenga instalada el usuario por lo que es necesario que éste siga los pasos indicados para su instalación si los sitios visitados o el mismo usuario necesitan un cifrado más fuerte que el permitido por defecto.

Saludos cordiales,

Pedro Fernández
--

Páginas

opinar

Más información sobre los formatos de texto

Texto puro

  • No se permiten etiquetas HTML.
  • Las direcciones de las páginas web y las de correo se convierten en enlaces automáticamente.
  • Saltos automáticos de líneas y de párrafos.
By submitting this form, you accept the Mollom privacy policy.
Cifrando tus datos...