Redeye Crypto

getHash.py

#!/usr/bin/python
from Crypto.Util.number import *
from hashlib import md5
#redeye{flag}

def conv(d):
    return bytes_to_long(d)

def add_padd(FLAG,H):
    x = 0
    for c in FLAG:
        x += H
        x *= ord(c)
    return x

FLAG = ""
XH = conv(md5(FLAG).digest())
  
print str(add_padd(FLAG,XH)) # output: 27680346842550922509933685002354044605811561366528421414998951571

output.txt

λ python solve.py
N=27680346842550922509933685002354044605811561366528421414998951571
[+] factoring N
factors = [3, 23, 29, 29, 29, 97, 103, 223, 311, 443, 733, 1399, 3583, 6689, 134
96140451, 65522619611, 2465584954291]
[+] trying different values for H
[  2000/131072   1%]
[  4000/131072   3%]
[  6000/131072   4%]
[  8000/131072   6%]
[ 10000/131072   7%]
[ 12000/131072   9%]
[ 14000/131072  10%]
[ 16000/131072  12%]
[ 18000/131072  13%]
[ 20000/131072  15%]
[ 22000/131072  16%]
[ 24000/131072  18%]
[ 26000/131072  19%]
[ 28000/131072  21%]
[ 30000/131072  22%]
[ 32000/131072  24%]
[ 34000/131072  25%]
[ 36000/131072  27%]
[ 38000/131072  28%]
[ 40000/131072  30%]
[ 42000/131072  32%]
[ 44000/131072  33%]
[ 46000/131072  35%]
[+] found 'R3verseM4thAlg' H = 11861308874247834548682942435005747613
[+] took 14.44s

solve.py

from itertools import *
from Crypto.Util.number import *
from math import gcd
from random import randint
from hashlib import md5
from functools import reduce
import time

# http://code.activestate.com/recipes/579049-prime-factors-of-an-integer-by-brent-algorithm/
def brent(N):
  # brent returns a divisor not guaranteed to be prime, returns n if n prime
  if N%2==0: return 2
  y,c,m = randint(1, N-1),randint(1, N-1),randint(1, N-1)
  g,r,q = 1,1,1
  while g==1:
    x = y
    for i in range(r):
      y = ((y*y)%N+c)%N
    k = 0
    while (k<r and g==1):
      ys = y
      for i in range(min(m,r-k)):
        y = ((y*y)%N+c)%N
        q = q*(abs(x-y))%N
      g = gcd(q,N)
      k = k + m
    r = r*2
  if g==N:
    while True:
      ys = ((ys*ys)%N+c)%N
      g = gcd(abs(x-ys),N)
      if g>1:  break
  return g

def factorize(n1):
  if n1<=0: return []
  if n1==1: return [1]
  n=n1
  b=[]
  p=0
  mx=1000000
  while n % 2 ==0 : b.append(2);n//=2
  while n % 3 ==0 : b.append(3);n//=3
  i=5
  inc=2
  #use trial division for factors below 1M
  while i <=mx:
    while n % i == 0 : b.append(i); n//=i
    i+=inc
    inc=6-inc
  #use brent for factors >1M
  while n>mx:
    p1=n
    #iterate until n=brent(n) => n is prime
    while p1!=p:
      p=p1
      p1=brent(p)
    b.append(p1);n//=p1
  if n!=1:b.append(n)
  b.sort()
  return b

# https://docs.python.org/3/library/itertools.html#itertools-recipes
def powerset(iterable):
  "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
  s = list(iterable)
  return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

def main():
  N = 27680346842550922509933685002354044605811561366528421414998951571
  print(f"N={N}\n[+] factoring N")
  factors = factorize(N)
  print(f"factors = {factors}\n[+] trying different values for H")
  possibleH = powerset(factors)
  count = 1;
  for s in sorted(possibleH):
    H = reduce(lambda x, y: x * y, s, 1)
    if count % 2000 == 0:
      print(f"[{count:6}/{2**len(factors)} {(count*100)//2**len(factors):3}%]")
    count += 1

    if N % H == 0:
      states = [(N // H, "")]
      while len(states):
        currN, currStr = states.pop()
        if currN == 0:
          XH = bytes_to_long(md5(currStr.encode()).digest())
          if XH == H:
            print(f"[+] found '{currStr}' H = {H}")
            return
        else:
          for c in range(0x30, 0x7b):
            if currN % c == 0:
              states.append((currN // c - 1, chr(c) + currStr))

if __name__ == '__main__':
  startTime = time.time()
  main()
  print(f"[+] took {(time.time() - startTime):4.2f}s")