Need help with a virus tales-from-the-crypt 2.0 - Msieve

[LaurV]

Originally Posted by Dubslow

I think you are looking for "overhead" rather than "overload"? In the sense of a minimum constant effort for any job, no matter how small (while for larger jobs the constant-size overhead becomes insignificant).

You are perfectly right, thanks for correction!

[jux]

Originally Posted by LaurV

How about "a graph worth a thousand words"?
Attachment 13677

Wow, that is a nice visual! I would add rough composite size estimates (I believe ~100 digits for SIQS/GNFS crossover) but I don't know the crossover points for other methods.

[darkskysofrenia]

maybe not the good place to ask but as you probably know this ransomware infected a lot of pepole.
googulator post on github some great tools to recover encrypted files but a lot of users are in trouble with the procedure. I'm trying to "automatise" and i'm searching a way to query factordb with python for faster factorisation.
is there a member of factordb team, or have you a way to query/post result on factordb directly by SQL from python ?
i can query with urlib2 but i'm not advanced python dev and it's boring to read the page and catch out the result.

[Dubslow]

I have some experience reading information from the FactorDB site via Python, mostly via regex parsing of HTML (I know, I know!)

FactorDB is incapable of producing factorizations though, it merely records them. You must use Yafu to obtain the factorizations.

[darkskysofrenia]

this is the goal but i was just thinking why launch YAFU until ask factordb, idealy i will have some kind of askfactordb function with this behavior :

ask factordb :
"fully factored" = register factors then go next step
"semi factored" = register know factor, use YAFU to factor the rest -> post result onfactor db -> go next step
" not factored " = launch YAFU and popup user " Go drink some beer it's will take a while "



idealy it's better factoring time for user and due to the number of "infected" pepole probably a lot of new factor for factordb satff

[Dubslow]

https://github.com/dubslow/MersenneF...drivers.py#L70
https://github.com/dubslow/MersenneF...drivers.py#L39
https://github.com/dubslow/MersenneF...yutils.py#L161

This is a decent place to start. One of the things on my long todo list coding wise is making my FDB interaction code available as a library -- alas, it's near the bottom of the list, and I don't see doing it anytime in the near future, so for now, you'll just have to read and borrow (GPL) the non-library code I've written.

Note that it is Python 3.

Edit: Perhaps it's best if a mod moves this discussion to a new thread so the two of us can discourse without polluting this thread

[EdH]

Just a thought in case you haven't considered this:

If you ask the db for an aliquot elf file in raw text for your number, it will provide the original number and small factors in an easily parsable text file. If it is already factored, it will also show a line 1.

Try the following to see if it is helpful:

http://factordb.com/search.php?se=1&aq=#################&action=last&text=Text&raw=1

As an example, here's one that's already factored:

http://factordb.com/search.php?se=1&aq=182378885427208016627889182085825389812715357063165092190820103554171162334048354441035155820663235444823539622054374755803572667155380450460387789753173&action=last&text=Text&raw=1

returns:

0 .   182378885427208016627889182085825389812715357063165092190820103554171162334048354441035155820663235444823539622054374755803572667155380450460387789753173 = 3^2 * 23 * 951297681044367341 * 13423646096483088059611483 * 380007556054726662513732347002603 * 181562037479789636721205815122013037335539058114593751995217924199463364271
1 .   92511028839888124665428634304061375305457104306609811366294829425365456021445650998585008554388215709561413985984442163477862386999951579401237106074795 = 3^2 * 5 * 123289

[darkskysofrenia]

thanks again for help, this one seems working, if someone had idea to post result of factor from pyhon i can implement too ;)

# !usr/bin/python
# -*- coding: utf-8 -*-

import urllib2
global fdbresponse
fdbresponse = {'status':'','primes':''}

def askfactordb(integer)
#integerFF = '779638116667556961714044187717419970949255491753237423271126932167233539198080655197984708553344793459104065027474177189109408389571778510312767094950880'
#integerCF = '2319690622702313576007568130052248753146155270200599609075527112759288888157911415683396078817506704507315137947891932143881436398314244178001467667392476'
#integerC = '485877477784603494129692554469497123828134955873543997990750036005347714610399355229931353950865321893713713240988424903296425663666632769855513008520217'

    query = 'http://factordb.com/search.php?se=1&aq=' + integer + '&action=last&text=Text&raw='
    request = urllib2.Request(query)
    response = urllib2.urlopen(request)
    html = response.read()
    htm = html.replace(integer,'')
    #print 'html = ' + htm
    if not htm.find("\r\n1") == -1 :
        fdbresponse['status'] = 'FF'
        #print 'FF'
    else :
        #print 'CF'
    fdbresponse['status'] = 'CF'
    position_first_ = html.find("=")
    html1 = html[position_first_:]
    print 'html1 = ' + html1
    position_point = html1.find(".")
    html2 = html1[:position_point]
    html3 = html2.replace('= ', '')
    html4 = html3.replace(' * ', ' ')
    list_of_primes = html4.split(' ')
    list_of_primes = [ x.replace("\r\n1","") for x in list_of_primes ]
    list_for_unfactor = []
    for data in list_of_primes :
        if not data.find("^") == -1 :
            position =  data.find("^")
            prime = data[:position]
            number = data[position+1:]
            repeat = int(number)
            while repeat > 0 :
                list_for_unfactor.append(str(prime))
                repeat -= 1
        else :
            list_for_unfactor.append(data)        
    trythis = ' '.join(list_for_unfactor).strip()
    if trythis == '':
        fdbresponse['status'] = 'C'
    fdbresponse['primes']  = trythis
    #print fdbresponse
    return fdbresponse

[Dubslow]

That seems rather more complex than my regex version, but if it works :shrug:

Anyways, as for reporting factors to the db, here's the gist:

1) yafu will print factors in the factor.log file

2) If you look at a number in the FDB, either via index.php or search.php, you will notice that the page has an HTML form. You can create Python code to "submit forms".

For instance http://factordb.com/index.php?id=1100000000812760330

It has the following HTML form:

<form action="index.php?id=1100000000812760330" method="POST"><center><table border=0 width="800"><tr><td align="center" bgcolor="#BBBBBB"><b>Report factors</b></td>
</tr><tr><td align="center" bgcolor="#DDDDDD"><textarea name="report" rows=4 cols=110></textarea></td>
</tr><tr><td align="center">Format: <select name="format" size=1>
<option value="0">Auto detect (slow)
<option value="1">One factor per line, base 2
<option value="2">One factor per line, base 8
<option value="3">One factor per line, base 10 (accepts terms)
<option value="4">One factor per line, base 16 
<option value="5">Multiple factors per line, base 2
<option value="6">Multiple factors per line, base 8
<option value="7">Multiple factors per line, base 10
<option value="8">Multiple factors per line, base 16 
<option value="9">GMP-ECM output
<option value="10">Msieve output
<option value="11">Yafu output
</select></td>
</tr><tr><td align="center" bgcolor="#DDDDDD"><input type="submit" value="Report"></td>
</tr></table></center></form>

If we remove the extraneous visual details:

<form action="index.php?id=1100000000812760330" method="POST">
<textarea name="report" rows=4 cols=110></textarea>
<select name="format" size=1>
<option value="0">Auto detect (slow)
<option value="1">One factor per line, base 2
<option value="2">One factor per line, base 8
<option value="3">One factor per line, base 10 (accepts terms)
<option value="4">One factor per line, base 16 
<option value="5">Multiple factors per line, base 2
<option value="6">Multiple factors per line, base 8
<option value="7">Multiple factors per line, base 10
<option value="8">Multiple factors per line, base 16 
<option value="9">GMP-ECM output
<option value="10">Msieve output
<option value="11">Yafu output
</select>
<input type="submit" value="Report">
</form>

That means, in my code I would do the following:

formdata = {'report': <string of factor to be reported>, 'format': '0'}
page = blogotubes('http://factordb.com/index.php?id=1100000000812760330', data=formdata) # Sending a dictionary of data will submit a POST request, as the form does
# Now we can parse the response page to verify whether or not the factor was accepted

The blogotubes function does this to send the data to the relevant Python library:

# Python 3 stdlib modules, some translation may be needed for Python 2
from urllib import request, parse, error
def blogotubes(url, data=None):
     if data is not None:
          data = parse.urlencode(data, encoding=encoding)
          data = data.encode(encoding)
     req = request.Request(url, headers=hdrs)
     try:
          page = request.urlopen(req, data).read().decode(encoding)
     ... # blah blah handle errors return page

[EdH]

Here's a bash script that takes its input from the command line, if anyone would like to look it over. It does not include any error checking and it does not report factors to the db, but it might be of interest:

#!/bin/bash

once=0
factored=0
test1=$(wget -O tempFile "http://factordb.com/search.php?se=1&aq=${1}&action=last&text=Text&raw=1")

exec < "tempFile"
  while read -n 1 charIn ; do
      if [ "$charIn" = . -a $once -gt 0 ]; then
        factored=1
        break
      fi
      temp1+=${charIn}
      if [ "$charIn" = = -a $once -lt 1 ]; then
        temp1=""
        once=1
      fi
  done

if [ $factored -gt 0 ]; then
  echo Already factored:
  printf ${temp1//\*/\\n}"\n"
else
  printf "${1}/(${temp1})\n" > in.txt
  cat factor.log >> savedLogs
  rm factor.log
  ./yafu < in.txt
  printf "\nFactors:\n"${temp1//\*/\\n}"\n"
  exec < "factor.log"
    while read line ; do
      case $line in
        *"prp"*) pos=`expr index "$line" ,`
        len=${line:pos+4:3}
        echo ${line:pos+9:len};;
      esac
    done
fi

Use the following command line:

bash bashFile.sh <composite>

Place the saved script file in the same directory as yafu and call it from there. As an example, with the above script saved as bashFile.sh:

bash bashFile.sh 182378885427208016627889182085825389812715357063165092190820103554171162334048354441035155820663235444823539622054374755803572667155380450460387789753173

Result for already factored number in db (if working):

Already factored:
3^2
23
951297681044367341
13423646096483088059611483
380007556054726662513732347002603
181562037479789636721205815122013037335539058114593751995217924199463364271

If you enter an unfactored number it should invoke YAFU using any known factors. When YAFU finishes all factors are displayed.

All comments welcome...

[wombatman]

Very nice! Anything that can simplify the process is a good thing for a situation such as this.