Fun Number Theory Facts

[Lionel Debroux]

Well, neither squalyl's V200 nor my 89 seem to have 073x or 071x fields...
They would certainly have such fields if additional certificates (.xxq files) had been added, though: there are 073x and 071x fields in my own developer certificate.

The certificate memory of my 89 HW2 contains only the following fields:
* 032(6) 090(4) nnnnnnnn
this is a timestamp, that of the SuperStart Flashapp, stored at 0x340000. There's also OurWorld (an older FlashApp) and GTC (a more recent FlashApp, with an invalid signature, it installed fine thanks to Flashappy), but the timestamp contained in the Certificate memory is that of sstart. God knows why.
* 020(D 40) [64 octets]:
mirrors the same field of SuperStart. This is supposed to be an encryption of the MD5 of 0326 0904 [timestamp], so that can't be the key we're looking for.
* 033(D 4A): container for two sub-fields
* 0A1(5) xx xx xx xx xx: serial number.
* 0A2(D 40) [...]: used directly, as a third argument (N) to BN_power17Mod, by a subroutine of the about dialog to compute the last four digits of the ID#.
If what we're looking for is located in the certificate memory, then 0A2 is the only choice, I believe :)

Now, perhaps the certificate memory isn't the place to look. I posted about that on yAronet today, pointing at the boot code. Finding the key in more than 24 KB of undocumented code + data may prove slightly unfunny...
... though, when writing this paragraph, I got the idea to look for the MD5 init patterns... and there's indeed a match within the boot code. There's a MD5Init in the boot code, so the other MD5 functions are definitely there. Maybe the modular exponentiation is there, too.
Anyway, I'm going to bed now :)


I don't know what happens if the decryption of the 020(D 40) field, created by encrypting the MD5 of the 0326 0904 nnnnnnnn, doesn't match the MD5 of the timestamp. At best, the validation is happy with that, but at worst, if we want to generate seemingly properly signed OS, we'll have to factor that key as well.

[FloppusMaximus]

Hmm... so I guess the public key is stored in the boot code somewhere. For some reason I didn't think it was, but OK.

Here is a program that will search for the OS public keys in a ROM dump. (Assuming they're 64 bytes and stored in little-endian form, which has been the case in every example I've ever seen.) It shouldn't take more than a few minutes to run. GMP is required.

About date stamps: Every Flash app for the 73/83+ is required to have a date stamp (although OSes are not.) I'd guess the same is probably true on the 68k calcs. Third-party apps for the 83+ generally use one particular date stamp and signature that has been copied from the SDK example code. The funny thing is that that signature isn't actually valid! Even though the OS will reject the app if the signature is missing, it doesn't seem to care that the signature is incorrect. (Possibly because the date stamp itself is too old.)

[Lionel Debroux]

Possible key for os209.89u found at offset 0x1379: 0x8976D4B5045A8988FB2BBAF8BADAFAFA4C5F8ABD5A9453D46790B33A03F6C225AAF31500E8246E
63498D85A1C7C8240E0630331F1291F6F4F21611BD661FC2E7

Credits for finding this key go to you, good job :)

The offset of the 0x40 byte that precedes it was output by the trivial program for outputting the offsets of all 0x40 bytes I had made before going to bed, but I had not sifted through the output to weed out the false positives, because it was fairly large and I really needed some sleep :D

The first instruction of BN_power17Mod, 4E56FF7E (link a6,$FF7E), has a match in the boot code, and disassembling the code at this offset shows a function terribly similar to BN_power17Mod: over the first 40 bytes, the only difference between BN_power17Mod and the boot code routine is the offset of a PC-relative jump to subroutine. And disassembling the code reveals that the key mentioned above is used as third argument of BN_power17Mod.


I haven't yet found where the boot code references the key and where it calls its own BN_power17Mod, because there's no absolute reference to either.

[squalyl]

Wow nice job FloppusMaximus and Lionel :)

is the "0x8976D4B5045A8988FB2BBAF8BADAFAFA4C5F8ABD5A9453D46790B33A03F6C225AAF31500E
8246E
63498D85A1C7C8240E0630331F1291F6F4F21611BD661FC2E7" string already written in big or little endian?

I'll start sieving as soon as you confirm the key you found is used by bn_powermod to check the os signature :)

PS: the 0A2 certificate signing key is a nice to have, too. and it's a training to check how factMsieve is working !
the latest polynomial found for this key is:

-> Searching leading coefficients from 2175001 to 2176000.
M: 93418385993421535986396543342966293285842282888823876701071408837135134964709057
92386000570725407496386266958841287233639066420497516183523522764932374469
Murphy_E: 2.50e-12
Y0: -350791084175190064167292610984
Y1: 569286263571668489
alpha: -5.30
c0: -225357094835336050626085845875290221
c1: 1702973133645973635248126023481
c2: 2027121117005024269325626
c3: -5921514292702442389
c4: 5956565793327
c5: 2175720
norm: 1.31e+21
skewness: 894360.69

[Lionel Debroux]

In multiple 89 ROM dumps containing a boot code, Benjamin's program finds the same key:
Possible key for os209.89u found at offset 0x1379: 0x8976D4B5045A8988FB2BBAF8BADAFAFA4C5F8ABD5A9453D46790B33A03F6C225AAF31500E8246E
63498D85A1C7C8240E0630331F1291F6F4F21611BD661FC2E7
(the offset depends on the boot code version, but it's in the 0x1200-0x1500 range)

In one 89T AMS 3.00 ROM dump:
Possible key for os310.89u found at offset 0x12C8: 0xD65139FA0ADA452B80CD35C0F9ACA3604EFE1915F0D3A4232C2C3B1FFEDDF2D7B0A4572A12B0F8
6C92D7E69F9DB102B1C27A551AD128BB6AF9321784FD8EAFD1

In multiple 92+ ROM dumps:
Possible key for os209.9xu found at offset 0x1339: 0xAD49CA3CFEF1F2DE400B5D3790813BF3822CB0BD83E3F565CE81B3A6CEF36FB833D932596D0E97
9615BAB6811ABE68834CA7CEBF46145C1DD1920AA4E9558DF7

In two V200 ROM dumps:
Possible key for os310.v2u found at offset 0x1435: 0x8307B022CEC848E14CA5D57C0C148A4803FEB19F7EEEC4493C860DF89594250E8F0F80B7AB18CF
03C27A07C1BA41B5ED4368261F4427BBE200A3B017EE100511

[Lionel Debroux]

We've started polynomial selection on those four keys. Wouldn't it be good to double-check this phase, by running the polynomial selection concurrently on at least two different computers (which would severly decrease the odds of a faulty compilation / hardware) ?

[fullmetalcoder]

As I promised, here come all the polynoms I found thus far. In the archive I put both the .poly files (best candidates) and the polsel.cand.all (obviously all candidates). Besides I put a small text file (BOUNDS) where you may find the range of value on which I searched for polynoms (in case you feel like looking for better candidates) and succint instructions on how to get factMsieve to start polynomial selection from a value other than 0.

[squalyl]

Many thanks. This will be valuable to distribute the search across multiple hosts ^^

[FloppusMaximus]

Lionel: That shouldn't be necessary. If by some chance you did end up with an invalid pair of polynomials, the siever would complain about it. A better use of your time would be to spend more time and search a larger polynomial space, as a "better" polynomial will substantially reduce the amount of time you need to spend sieving.

As far as the rest of the factorization goes: if you have a glitch while sieving, I believe Msieve will notice that and discard any invalid relations. The only place where you're likely to have serious problems (e.g., if you're using faulty RAM, or an overclocked CPU) is in the linear algebra phase, and for that reason Msieve periodically verifies its own internal state and writes out "checkpoint" files as it goes.

fullmetalcoder: Thank you, that is very helpful.

[Lionel Debroux]

OK. squalyl and I have left our computers crunching away on polynomial selection for the 89, 89T and V200 keys last night (for us Europeans).
Though none has dethroned the best polynomials found about 15, 12 and 16 hours ago, a number of other "good" polynomials were found.
If you ran polynomial selection to completion, how long did that phase last on your dual-core Athlon 64 ?

[fullmetalcoder]

[Lionel Debroux]

OK, thanks for the explanation
My computer has been crunching for about 23 hours.
I have already posted my current .poly files for the 89 and 89T keys, I think I'll switch to sieving tomorrow.

[squalyl]

I've started sieving.

-> =====================================================
-> Best score so far: 2.640000e-12 (goodScore=2.470000e-12)
-> =====================================================

name: keyv200
n: 68625995847049740876626753887827955321505619080216523957462824970196387537571899
12517082637885407430147717938545038165980647741822312936842988033110181137
skew: 2168162.77
# norm 6.51e+21
c5: 1463760
c4: 15272492861412
c3: -31959549178645931636
c2: -58293683846649564044526733
c1: 36530556826953814708317801270724
c0: 37160559539671290602002622740718966025
# alpha -6.81
Y1: 39153676195103401
Y0: -342139844140534249972569210496
# Murphy_E 2.64e-12
# M 47303995649422071732486497177588531116225532802474600676258401402659068504960991
76901336536199080704216559999490259273827634368065008672058436360723157979
type: gnfs
rlim: 25700000
alim: 25700000
lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
rlambda: 2.6
alambda: 2.6
qintsize: 100000

Current state here: http://www.unsads.com/~squalyl/fact/osv200/
The current task output is sieve.log

[FloppusMaximus]

Sorry, I wasn't taking careful notes I had the polynomial search running for a bit over 3 days and searched leading coefficients up to 13,950,000. I haven't done enough of this to have a good idea of how much searching is optimal; in this case I suspect I probably should have kept going a bit longer. We will see.

By the way, I should perhaps mention that recent versions of Msieve contain a new polynomial selection algorithm which is supposed to give significantly better results than pol5. I've tried it with a few of these keys, but I haven't yet seen it produce any polynomials for numbers of this size. Maybe it's my PC, or maybe Msieve knows something I don't...

[Lionel Debroux]

OK.
So far, my Core 2 Duo T7200 (2 GHz) has searched more than 14.4M leading coefficients for the 154-digit 89 key, and more than 6.3M leading coefficients for the 155-digit 89T key. Though the last 24 hours didn't yield any new best result, I'll leave both running, each on its own core, until tomorrow afternoon at least (>= 48h total).

If the figures given by http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html and http://gilchrist.ca/jeff/factoring/nfs_msi...poly_guide.html were taken on the same machine, when the docs were made, msieve's polynomial selection was significantly slower than pol5: 5 hours instead of 2 for the 121-digit example. If the speed difference still holds, that might explain why your msieve polynomial selection runs haven't yet turned any results.
After I abort polynomial selection with ggnfs, I can give msieve a try on one of the cores, while the other one starts sieving the 89 key.

[FloppusMaximus]

I'm sure it's possible that my PC is just too slow, or I'm doing something else wrong, but when I tried Msieve on the 04 key, it ran for a week, produced no results, and gave up.

[Graphmastur]

All this rsa stuff needs to have it's own topic. Anyway, I have a question about the quadratic sieve. As in, they do all this mod of this weird little simble, and it's so confusing!!! Can it be explained in any better way? My mind basically turns off for the night reading some of those pages. Thanks in advance!!

[Lionel Debroux]

Another yAronet user, bobti89, has made a ready-to-use Windows package.
His post http://www.yaronet.com/posts.php?sl=&s...0&h=276#276 translates to:
"
* Install Perl : http://downloads.activestate.com/ActivePer...-x86-290470.msi

* Download : http://j.petitjean.club.fr/bobti89/tikey/tikey.zip

* Decompress the files wherever you want, modify the values of q in the <key*>.poly files according to what you want to crunch on, and open a command window in the folder that contains the .poly.

* execute 'perl factMsieveQ.pl <key*>.poly'
"

At present, bobti89's ZIP contains only the 89, 89T and V200 polynomials. However, we should definitely join forces, be it on adding other polynomials for the TI-Z80 keys to such a ZIP, or on the BOINC client effort started by squalyl.

[Skittle]

Hi! Ive been lurking this thread for a few days looking to see where i can help.
I am currently running the above script on keyti89t (i chose this solely because i own one) on a Q6600@3.0ghz.
Is there another key that I should work on instead?

happy hunting!

[Lionel Debroux]

You have a nice computer there.

bobti89 has added to his ZIP the six .poly posted above by fullmetalcoder, and the k0A.poly of the other thread. You can work on whatever key you wish to work on: TI-68k keys (keyti89, keyti89t, keyti92p, keyv200), TI-Z80 keys ("01", "02", "03", "08", "0A", "0101" and "0102")
It seems that the efforts are currently concentrated on the "0A" TI-Z80 key, see http://www.unitedti.org/index.php?showtopic=8899 .