- Introducción
- Funcionamiento de RSA
- OllyDbg
- Calculando la clave privada (d)
- Ejemplo operacional
- Keygen
- Links
Introducción
Segunda crackme con RSA que afrontamos. Esta vez se trata de un crackme realizado en VC++ 7.0 y en sus entrañas utiliza RSA-127. Una cosa que no comenté en la entrega anterior (RSA-200), es que conviene utilizar el plugin Kanal de PEiD para localizar cuando se utilizan números grandes o determinados hashes como MD5 o SHA1.
Otra cosa es que os quería comentar es la coletilla 127. Esta lo determina el módulo n e indica el número de bits de éste.
Funcionamiento de RSA
- Inicialmente es necesario generar aleatoriamente dos números primos grandes, a los que llamaremos p y q.
- A continuación calcularemos n como producto de p y q:
n = p * q
- Se calcula fi:
fi(n)=(p-1)(q-1)
- Se calcula un número natural e de manera que MCD(e, fi(n))=1 , es decir e debe ser primo relativo de fi(n). Es lo mismo que buscar un numero impar por el que dividir fi(n) que de cero como resto.
- Mediante el algoritmo extendido de Euclides se calcula d que es el inverso modular de e.
Puede calcularse d=((Y*fi(n))+1)/e para Y=1,2,3,... hasta encontrar un d entero.
- El par de números (e,n) son la clave pública.
- El par de números (d,n) son la clave privada.
- Cifrado: La función de cifrado es.
c = m^e mod n
- Descifrado: La función de descifrado es.
m = c^d mod n
OllyDbg
Con OllyDbg analizamos la parte del código que nos interesa.
0040109B . 68 00010000 PUSH 100 ; /Count = 100 (256.) 004010A0 . 52 PUSH EDX ; |Buffer = RSA127.<ModuleEntryPoint> 004010A1 . 68 EA030000 PUSH 3EA ; |ControlID = 3EA (1002.) 004010A6 . 8B8C24 28020000 MOV ECX,DWORD PTR SS:[ESP+228] ; | 004010AD . 51 PUSH ECX ; |hWnd = NULL 004010AE . FF15 F0B04000 CALL DWORD PTR DS:[<&USER32.GetDlgItemTex>; \GetDlgItemTextA 004010B4 . 8D5424 04 LEA EDX,DWORD PTR SS:[ESP+4] 004010B8 . 57 PUSH EDI 004010B9 . 52 PUSH EDX ; RSA127.<ModuleEntryPoint> 004010BA . 50 PUSH EAX ; kernel32.BaseThreadInitThunk 004010BB . E8 201E0000 CALL RSA127.00402EE0 004010C0 . 83C4 0C ADD ESP,0C 004010C3 . 8D9424 04010000 LEA EDX,DWORD PTR SS:[ESP+104] 004010CA . 68 00010000 PUSH 100 ; /Count = 100 (256.) 004010CF . 52 PUSH EDX ; |Buffer = RSA127.<ModuleEntryPoint> 004010D0 . 68 EB030000 PUSH 3EB ; |ControlID = 3EB (1003.) 004010D5 . 8B8C24 28020000 MOV ECX,DWORD PTR SS:[ESP+228] ; | 004010DC . 51 PUSH ECX ; |hWnd = NULL 004010DD . FF15 F0B04000 CALL DWORD PTR DS:[<&USER32.GetDlgItemTex>; \GetDlgItemTextA 004010E3 . 8D9424 04010000 LEA EDX,DWORD PTR SS:[ESP+104] 004010EA . 52 PUSH EDX ; RSA127.<ModuleEntryPoint> 004010EB . 8B4C24 04 MOV ECX,DWORD PTR SS:[ESP+4] 004010EF . 51 PUSH ECX 004010F0 . E8 5B1F0000 CALL RSA127.00403050 004010F5 . 68 08B14000 PUSH RSA127.0040B108 ; ASCII "666AAA422FDF79E1D4E41EDDC4D42C51" 004010FA . 55 PUSH EBP 004010FB . E8 501F0000 CALL RSA127.00403050 00401100 . 68 2CB14000 PUSH RSA127.0040B12C ; ASCII "29F8EEDBC262484C2E3F60952B73D067" 00401105 . 56 PUSH ESI 00401106 . E8 451F0000 CALL RSA127.00403050 0040110B . 53 PUSH EBX 0040110C . 55 PUSH EBP 0040110D . 56 PUSH ESI 0040110E . 8B5424 24 MOV EDX,DWORD PTR SS:[ESP+24] 00401112 . 52 PUSH EDX ; RSA127.<ModuleEntryPoint> 00401113 . E8 38250000 CALL RSA127.00403650 00401118 . 53 PUSH EBX 00401119 . 57 PUSH EDI 0040111A . E8 31130000 CALL RSA127.00402450 0040111F . 83C4 30 ADD ESP,30 00401122 . 85C0 TEST EAX,EAX ; kernel32.BaseThreadInitThunk 00401124 . 74 12 JE SHORT RSA127.00401138 00401126 . B8 01000000 MOV EAX,1 0040112B . 81C4 08020000 ADD ESP,208 00401131 . 5B POP EBX ; kernel32.7590EE1C 00401132 . 5D POP EBP ; kernel32.7590EE1C 00401133 . 5E POP ESI ; kernel32.7590EE1C 00401134 . 5F POP EDI ; kernel32.7590EE1C 00401135 . C2 1000 RETN 10 00401138 > 6A 40 PUSH 40 ; /Style = MB_OK|MB_ICONASTERISK|MB_APPLMODAL 0040113A . 68 5CB14000 PUSH RSA127.0040B15C ; |Title = "Yeah!" 0040113F . 68 50B14000 PUSH RSA127.0040B150 ; |Text = "Nice job!!!" 00401144 . 6A 00 PUSH 0 ; |hOwner = NULL 00401146 . FF15 F4B04000 CALL DWORD PTR DS:[<&USER32.MessageBoxA>] ; \MessageBoxA
El código nos proporciona el exponente público (e) y el módulo (n).
- e = 29F8EEDBC262484C2E3F60952B73D067
- n = 666AAA422FDF79E1D4E41EDDC4D42C51
Finalmente realiza un PowMod con el número de serie del disco C y el par de claves (e,n).
Calculando la clave privada (d)
Una vez localizados los datos anteriores lo siguiente es factorizar para obtener los primos p y q y finalmente d.
d = 65537
Ejemplo operacional
Nº serie disco C = -1295811883 Serial = hdd.getBytes()^d mod n Serial = 2d31323935383131383833^65537 mod 666AAA422FDF79E1D4E41EDDC4D42C51 Serial = 1698B6CE6BE0D388C31E8E7895AF445A
Keygen
El keygen está hecho en Java ya que permite trabajar con números grandes de forma sencilla.
JButton btnNewButton = new JButton("Generar");
btnNewButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
BigInteger serial = new BigInteger("0");
BigInteger n = new BigInteger("136135092290573418981810449482425576529");
BigInteger d = new BigInteger("415031");
String hdd = t1.getText();
BigInteger tmp = new BigInteger(hdd.getBytes());
serial = tmp.modPow(d, n);
t2.setText(serial.toString(16).toUpperCase());
}
});
Links
- RSA (wikipedia)
- El algoritmo RSA y la factorización de números grandes (recomendable)
- Exponenciación modular (wikipedia)
- RSA Tool
- Big Integer Calculator v1.14
- Crackme y Keygen
