permutaciones simples en excel - parte 1

El presente tema viene dado por la siguiente consulta: "...puedo desarrollar una macro que intente averiguar la contraseña de una hoja de cálculos?" Y desde ya que sí, y no es complicado.

Sobre permutaciones y combinaciones encontrán infinidad de artículos en Google, muy técnicos, poco técnicos, resueltos, fáciles, difíciles... hay una cantidad impresionante para todo aquel que quiera o necesite profundizar en la materia. Yo, como siempre, partiré de cero y la teoría será breve y concreta, manejandonos luego con ejemplos.

Empecemos con algo: tenemos una noción bastante desarcertada (en general) de lo que es una combinación o permutación. Recuerdan la cerradura de combinación de los maletines... aquella que posee casi siempre 3 tambores giratorios?... bueno, recuerdan mal, por que eso está erróneamente llamado "combinación", ya que en realidad nos encontramos ante una "cerradura de permutación".

Y cual es la diferencia entre ambas? Que en la permutación tiene relevancia, e importa mucho, el orden con el cual efectuamos la combinación de los datos. Una permutación es una combinación ordenada.

Clarifiquemos volviendo al ejemplo de la cerradura del maletín: son tres tambores, con números del 0 al 9 cada uno. Permutados correctamente, es decir colocando cada uno en su respectivo orden, lograremos dar con la contraseña indicada, pudiendo así abrirlo:

estos 3 números, en ese orden, abren la cerradura del maletín.

[+/-] Ver el resto / Ocultar

Hasta aquí estamos completamente de acuerdo que ese 5 2 9 de arriba es el orden correcto. Si tuviese, por ejemplo, esto:

el maletín no abre. si bien son los mismos números, no están ordenados de igual forma.

Entonces, quedó desmostrado que la permutación es una combinación ordenada.

Habiendo superado el primer paso, vamos al segundo. Cuantas formas existen de permutar los números de la cerradura, teniendo en cuenta que dichos números se pueden repetir? Y recalco "se pueden repetir", dado que la contraseña puede contener numeros repetidos: 229, 333, 668, 772, 999, etc, etc, etc/

El cálculo es en extremo sencillo:

1) cuantos tambores tiene la cerradura? Respuesta: 3

2) cuantos numeros puedo ingresar por tambor? Respuesta: 10 (del 0 al 9)

Entonces, la posible cantidad de permutaciones de nuestro ejemplo es: 10 x 10 x 10 = 1000. Tenemos 1000 formas distintas de permutar esos valores. Y utilicé este ejemplo para que "a cabeza" podamos calcular que entre 000 y 999... efectivamente, hay 1000 números.

en cada tambor podemos poner un valor entre 0 y 9 (10 numeros). 10*10*10=1000 permutaciones

Si dejamos de lado a la cerradura y pasamos a como sería averiguar un password, tendremos otro ejemplo que nos ayudará a tener una imagen mas precisa sobre este asunto. Para no complicarla, supongamos que el password tiene 3 caracteres de longitud, y existen 50 posibles dígitos, entre letras, numeros y caracteres especiales, a permutar. Entonces:

1) que longitud tiene la contraseña? 3 digitos

2) cuantos caracteres puedo alternar en cada posición? 50 (entre letras, nros y caracteres especiales)

La solución: 50 x 50 x 50 = 125.000 posibles permutaciones.

en cada dígito podemos poner hasta 50 caracteres distintos. 50*50*50=125.000 permutaciones

Y ahora algo que nos dispara la cantidad de combinaciones de forma espectacular. Miren si el password tuviese 4 caracteres de longitud:

si, de "pocas" 125.000 permutaciones del ejemplo anterior, y con tan solo agregar una letra a la longitud del mismo, pasamos a seis millones doscientos cincuenta mil permutaciones.

Mas allá de los números, espero que haya quedado en claro el concepto. Cuando permutamos estamos combinando, pero de una forma en que le damos importancia al orden de cada elemento.

Hasta aquí vimos la permutación que permite la repetición de elementos, que es la que nos servirá para "romper" passwords. Pero no voy a dejar pasar esta oportunidad para ejemplificar la permutación que no acepta repeticiones, así cerramos el concepto y, para lo que no lo saben, se van "con algo mas".

La idea en fácil: nos interesa el orden, pero ningún elemento se puede repetir. Volviendo a la cerradura: 

a) al seleccionar el primer número tengo 10 opciones (del 0 al 9). Elijo el 3. 

b) ahora paso al segundo número, pero ya no tengo mas 10 opciones, dado que puse al 3 en el primer tambor.... o sea, tengo 9 posibles numeros (del 0 al 9, excluyendo el 3 que ya seleccioné). Elijo el 5.

c) bien, solo resta elegir un número. ya tengo dos (el 3 y el 5). Pero ahora mis opciones son menores: cualquier numero del 0 al 9, excluyendo al 3 y al 5 que ya están ingresados. o sea, 8 posibilidades. Elijo el 6. (a estas alturas, la permutación es: 3 5 6)

La formula final:

de izquierda a derecha: al comenzar a introducir los números tenía 10 opciones, luego 9 (el 3 queda excluído) y al final 8, ya que quedaron afuera el 3 y el 5. De las 1000 permutaciones con repetición pasamos a 720 sin repetición.

Espero haber sido claro hasta aquí, por que se termina (por fin) la teoría.

Preparé un código sencillo que nos hará el trabajo de permutar elementos, el cual expondré a continuación. En C1 ingresaremos los elementos a permutar; en este primer ejemplo serán las letras "abc". El resultado será:

Tenemos en la imagen superior todas las posibles formas de permutar "abc" aceptando repeticiones. 

Tres elementos (abc) con tres posibles valores en cada uno de ellos: 3*3*3=27 permutaciones, aceptando repeticiones. Todo bien hasta aquí... pero si el password tiene uno o dos caracteres solamente?
¿Si el usuario introdujo "ac" como contraseña?
Y es aquí donde debemos replantear un aspecto. En la imagen de arriba observamos las permutaciones logradas con los datos: "abc", y todas tienen 3 dígitos de longitud. O sea que si la contraseña tuviese uno o dos caracteres .... nunca la encontraríamos.
Entonces, a las permutaciones vistas hasta ahora, se nos hace necesario agregar todas las permutaciones posibles con 1 y 2 dígitos solamente. Completarían la imagen anterior la siguiente secuencia:

Bien, trabajo completo. Y antes de pasar al código, aclaremos algo: en el 99% de los casos (por una causa o la otra) necesitaremos almacenar los resultados. Esto lo llevaremos a cabo dentro del mismo Excel o en archivos externos (*.txt, *.dat, etc, etc). He optado por la segunda, dado que ya vimos la forma en que con un par de caracteres extras, alcanzamos millones y millones de registros. Y se tornaría bastante pesado guardarlos en Excel, pero es muy sencillo hacerlo en archivos de texto plano.
Quizás una alternativa al almacenamiento sería la utilización de matrices... pero no olvidemos que cada posición de la matriz ocupa memoria (2, 4, 8 bytes según el tipo de datos) y una de millones de registros seguro afectarían nuestros sistemas.
Otro punto que me alienta a trabajar de esta forma (y en efecto lo hice, con archivos de texto que guardaban decenas de millones de combinaciones/permutaciones posibles) es que, probablemente, en algún otro momento necesitemos de esos registros, y así nos evitamos perder horas y horas generando de nuevo los mismos datos.

Código VBA:

'con option base 1 hago que todas las matrices que se definan
'dentro inicialicen su primer elemento en 1 (recordemos que,
'por defecto, las matrices en VB se inicializan en 0)
Option Base 1
'la matriz en donde almacenaré las letras de la contraseña
'(que en este ejemplo están en el rango [elementos] (a2:a21) )
Dim Matrix() As String
Dim TotalElementos As Integer

Sub Iniciar()
'variables de uso local
Dim indexArrastre As Long
Dim contLetra As Long
Dim Letra, Resultado, Parcial As String
Dim Contador
'guardo la cantidad de letras ingresadas en el rango [elementos]
TotalElementos = Application.WorksheetFunction.CountA([elementos])
'y redimensiono a Matrix
ReDim Matrix(TotalElementos)


indexArrastre = 1
Contador = 1
contLetra = 1

'por si existe algún archivo previo con datos almacenados
EliminarArchivoDeTexto
[b1].ClearContents
'abro el archivo en modo Random (aleatorio) ya que necesi
'taré escribir y leer al mismo tiempo
Open ActiveWorkbook.Path & "\permuta.txt" For Random As #1

While Len(Parcial) < TotalElementos
    For x = 1 To TotalElementos
        Letra = Trim([elementos].Cells(contLetra))
        Resultado = Trim(Parcial & Letra)
        Put #1, Contador, Resultado
        'llamo a la funcion que desbloquea la hoja. le paso
        'los dos argumentos: el nombre de la hoja que deseo
        'desbloquear y el pass que armé:
        If DesbloquearHoja("protegida", Resultado) = True Then
            MsgBox "La hoja fué desprotegida con el pass: " & Resultado _
            & vbCrLf & "cant de procesos: " & Contador
            [b1] = Resultado
            bandera = 1
            GoTo MeVoy
        End If
        Contador = Contador + 1
        contLetra = contLetra + 1
    Next x
    Get #1, indexArrastre, Resultado
    Parcial = Trim(Resultado)
    indexArrastre = indexArrastre + 1
    contLetra = 1
Wend
MeVoy:
If bandera <> 1 Then
    MsgBox "el pass no fué encontrado" _
    & vbCrLf & "cant de procesos: " & Contador
End If
Close #1
Erase Matrix()
End
End Sub


Sub EliminarArchivoDeTexto()
If Dir(ActiveWorkbook.Path & "\permuta.txt") <> "" Then
    Kill ActiveWorkbook.Path & "\permuta.txt"
End If
End Sub
Function DesbloquearHoja(NombreHoja As String, Pass) As Boolean
'primero, x las dudas, pongo en false a la funcion
DesbloquearHoja = False
'ahora un controlador de errores. si se produce un error, la
'contraseña es incorrecta. Si no se produce ninguno, el pass
'word fué descubierto y pongo a la funcion en True, para
'dar aviso de ello al Sub llamador
On Error GoTo Salida:
    With Sheets(NombreHoja)
        .Unprotect Password:=Pass
        DesbloquearHoja = True
        Exit Function
    End With
Exit Function

Salida:
If Err.Number <> 0 Then
    DesbloquearHoja = False
End If
End Function

Les aconsejo colocar un punto de interrupcion en el "While..." y hacer el paso a paso (F8) para comprender como el código va armando la cadena de texto con los caracteres. Dentro de dicho bucle observarán que llamo a una función externa (booleana) que se encarga de probar el password armado y ver si puede desbloquear la hoja con el.

El formato de la hoja es muy sencillo:

en el rango "elementos" cargamos una por una los caracteres. en B1 la macro nos pondrá el password, si es que lo encontró.

 Como siempre en estos casos, aqui tienen el archivo para la descarga.

 Ahora que tengo este tema de las permutaciones y combinaciones dentro del Blog, vamos a tratar en la próxima entrada una forma de optimización (muy utilizada en ambientes comerciales e industriales) que nos servirá en la toma de decisiones cuando existen varias alternativas en juego..... y echando mano practicamente del mismo código.

El ejemplo que les brindo toma hasta 20 caracteres, cosa que pueden modificar facilmente cambiando el tamaño del rango [elementos].... Pero ojo: vean muy bien la cantidad de permutaciones en juego, por que de unos pocos milisegundos, el ordenador puede pasar a minutos, horas, dias, etc, etc, calculando. Un solo caracter mas nos eleva las posibles combinaciones/permutaciones a millones y millones. De allí que el "ataque por fuerza bruta" sea poco utilizado, y en su reemplazo actúen diccionarios de ataque, probabilidades y algunas otras herramientas.