#!/usr/bin/python

# PoC de cracker de password privada a partir de la publica (en RSA)
# Primero : se factoriza el modulo N
# Segundo : se calcula el phi(N)
# Tercero : se busca el inverso de e en modulo phi(N) (esta es d)
# Cuarto : se muestra todo.

import sys, math

def usage():
  print sys.argv[0]," <e> <N> "

def factorizar(numero, listaDeDivisores):
  for testNumber in range(2,int(math.sqrt(float(numero))+1))[::-1]:
    if numero%testNumber == 0:
       listaDeDivisores.append(testNumber)
       return factorizar(numero/testNumber, listaDeDivisores)
  listaDeDivisores.append(numero)
  return listaDeDivisores

if len(sys.argv) != 3 :
  usage()
  exit()
try:
  KeyE = int(sys.argv[1])
  KeyN = int(sys.argv[2])
except:
  print "Ambos <e> y <N> tienen que ser numeros"

#### Factorizacion de N #######
print "[+] Factorizando N ..."
factoresDeN = factorizar(KeyN, [])
print "[+] Factorizacion completada "
if (len(factoresDeN) != 2):
  print "El numero N que suministraste no es el producto de dos primos "
  print "Finalizando ... "
  exit()
#### Fin de factorizacion de N #####


##### Calculo de phi(N) ########
# print "Los factores {primos} son ",factoresDeN[0]," y ",factoresDeN[1]
PhiN =  (factoresDeN[0]-1)*(factoresDeN[1]-1)
print "[+] phi(N) calculado"
# print "Phi(N)= ",PhiN
##### Fin del calculo de phi(N) #####
# ed = 1 mod PhiN
# ed = PhiNk + 1


#### Busqueda del inverso modular de e en phi(N) ####
kMaximo = KeyE*PhiN/PhiN-1
print "[+] Buscando el inverso modular de ",KeyE," en modulo ", PhiN
for posibleK in range(kMaximo):
  test = ((posibleK*PhiN)+1)/KeyE
  if (test*KeyE)%PhiN == 1:
    KeyD = test
    print "[+] Inverso modular encontrado"
    print ""
    print "Conseguido! la clave privada esta formada por la dupla (",KeyD,",",KeyN,")"
    exit()
print "Lo siento, fue imposible calcular la clave privada"