> It looks like A_ROM has an extra byte tagged onto the
> end that never gets used.
Correct. A_ROM (aka Z) is 120 bytes, just like X & Y.
> So, I'm under the impression that if we can factor this
> puppy, we can reverse the 7800 encryption scheme.
That's what Tim Grove wrote:
] Even though you know Z and Y, solving for X is
] impossible, unless you can factor Z.
I still don't see the connection. Maybe someone could
explain this?
X^2modZ=Y
X^2 Y
--- = C + -
Z Z
X^2 = CZ + Y
where
X is an unknown value
C is an unknown value
Z is a known value
Y is a partially known value (all but 8 bits)
> So I've been having gp try to factor it for a while...
> No luck yet though ;-).
I tried using the 'FACTOR' program supplied with the MIRACL
"big number" library and it didn't find the factors (I give
up - composite factor). Of course it has pre-defined limits
which -I guess- need to be increased due to the size of Z...
> I wonder if there's a way to split up the work of doing the
> factorization, along the lines of Brad's suggestion?
Anything's possible but the question is - will it help to factor
Z in order to speed up deriving X?
----
> One thing that interests me is that the comparison done on
> the checksum doesn't include every bit of result.
Yeah, from the coding I've done, it has helped but the
"machine time" is still in 'years' even for what I'm
working on.
> Does this mean maybe you don't need to factor Z...maybe a
> slightly smaller number?
Beats me...
----
Here's a quick update of what I've done...
First I tried modifying CRYPT78 to get X. There were
two possiblities:
1) increment X until valid
2) put random values in for X
This was way too slow so I starting searching.
Using MIRACL
http://indigo.ie/~mscott/
ftp://ftp.compapp.dcu.ie/pub/crypto
And using the MONITOR cart's X & Y values I verified
everything for
// X^2modZ=Y
multiply(X,X,X); // X = X^2
divide(X,Z,Z); // X = XmodZ
return ( compare(X,Y) );
I then started different approaches at the above formula
with unknown values. My current bruteforce search method is
// Y = X^2 - NEWZ
multiply(C,Z,NEWZ); // NEWZ = C * Z
add(NEWZ,Y,NEWZ); // NEWZ = NEWZ + Y
loop1: if ( nroot(NEWZ,2,X) ) // X =
sqroot(NEWZ)
goto check_it;
loop2: incr(X,1,X); // X = X + 1
multiply(X,X,SAVEX); // SAVEX = X^2
subtract(SAVEX,NEWZ,TEMP); // TEMP = SAVEX -
NEWZ
if ( size(TEMP) < 0 ) // negative value?
goto loop2;
if ( numdig(TEMP) > 232 )
{
add(NEWZ,OLDZ,NEWZ); // NEWZ = NEWZ +
OLDZ
goto loop1;
}
putdig(0,TEMP,240-8); // TEMP[8] = 0
putdig(0,TEMP,240-9); // TEMP[9] = 0
if ( size(TEMP) ) // TEMP==0?
goto loop2;
NEWY = X^2 - (C*Z) - OLDY
NEWY = 00000000##0000.... {hex}
X = ####....
C = c_min..c_max
Z = z
OLDY = y
I created a 4K image and used CRYPT78 to get Y from
MungeCart(). This value can then be used for Y in
MungeChecksum() [aka X^2modZ=Y]. I calculated c_min,
and then started on X for this 4K image.
BTW, looking at some cart images, X seems to always be in
the range 0001.... to 0008.... -- not that it matters! ;-)
----
FWIW, I found two other libraries:
gmp
freelip
I used MIRACL since it was supposed to be faster. It's
definitely easy to setup and use under DOS. Plus I had
a couple of questions and received a prompt reply.
I assume GP/PARI could also be used.
--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
