Omnimaga

General Discussion => Technology and Development => Other => Topic started by: SirCmpwn on February 27, 2011, 06:39:33 pm

Title: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 06:39:33 pm
While a better program is worked on, I've put together a brute forcing program that will attempt to factor the key.  This is portable, and via Mono (http://www.mono-project.com/Main_Page), it can run on Mac and Linux.  It should run fine on most versions of Windows.  Here's what to do:
Whenever you are using your computer, try to have this program running.  It will save a file - persist.data - which should not be deleted, or you'll need to start over.  It automatically dumps its state into this file as it goes.  You shouldn't have any trouble with it.  When the key is found, it lets out one long beep to get your attention, displays the results, and saves them to factored_key.txt.
I seriously doubt we'll find the key with this, but it could get some of the work for the more advanced program out of the way, and who knows, even find the key.
Now, this can be very redundant unless we are careful.  When you download this, you'll need to claim a starting number.  Take the number from the bottom of the following list and increase it by a lot (or just request for someone else to assign you a number).  The number should be 512 bits.  Post it in the topic, and I'll add it to this list:
Currently Claimed Bounds (in hex):
Spoiler For Spoiler:
SirCmpwn:
1000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
squidgetx
2000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
apcalc
3000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
alberthrocks
4000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
Builderboy
5000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
z80man
6000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
shimbs
7000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
qazz42
8000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
Juju
9000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
DJ_O
A000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
cooliojazz
B000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
Title: Re: TI-Nspire Key Brute Forcer
Post by: squidgetx on February 27, 2011, 06:41:36 pm
I'll take
2000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000?
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 06:42:17 pm
Sounds good, go for it.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 06:43:01 pm
You used mscorlib, so cross compatibility is virtually nonexistent :(
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 06:43:42 pm
For goodness sakes, cross compatibility works fine!  Go get Mono and try it, I guarantee you it will run on whatever OS you put it on!
Title: Re: TI-Nspire Key Brute Forcer
Post by: apcalc on February 27, 2011, 06:45:05 pm
3000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

If this works, we should pay Sir 10 Million Dollars, as he could have probably won that in the lottery if he got that lucky there! :)
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 06:46:30 pm
I'm trying it......throws errors. I have mono.
Title: Re: TI-Nspire Key Brute Forcer
Post by: alberthrocks on February 27, 2011, 06:47:23 pm
broooom is working on a server atm. The server can give the starting point as well if needed. :)

I have errors too.... regarding "Access denied":
Code: [Select]
arthur@arthur-PC:~$ mono Nspire*.exe
1024 bit TI-Nspire boot2 RSA Key:
0xc3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d
0x3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b
0xbcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c
0xdf80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7


Unhandled Exception: System.ComponentModel.Win32Exception: Access denied
  at System.Diagnostics.Process.set_PriorityClass (ProcessPriorityClass value) [0x00000] in <filename unknown>:0
  at (wrapper remoting-invoke-with-check) System.Diagnostics.Process:set_PriorityClass (System.Diagnostics.ProcessPriorityClass)
  at NspireKeyFactorer.Program.Main (System.String[] args) [0x00000] in <filename unknown>:0
arthur@arthur-PC:~$
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 06:48:14 pm
Ah, I should fix that.  It automatically sets the priority to High, which is disallowed under non-Windows platforms.
EDIT: See the first post for a revised version.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 06:52:19 pm
I wonder if the cx uses the same keys?

Also, what key are we getting? boot2?
Title: Re: TI-Nspire Key Brute Forcer
Post by: alberthrocks on February 27, 2011, 06:53:07 pm
O_O
That's crazy.... :P
Did you implement that CPU usage watching idea?
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 06:54:32 pm
It doesn't watch your CPU, no.  It does take up quite a bit, I see...
It sticks to one core, though, and I haven't noticed the rest of my PC take a performance hit.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 06:55:26 pm
WARNING: The runtime version supported by this application is unavailable.
Using default runtime: v1.1.4322

** (Z:\home\william\Projects\factor.exe:25): WARNING **: The class System.ConsoleKeyInfo could not be loaded, used in mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089

Unhandled Exception: System.TypeLoadException: Could not load type 'System.ConsoleKeyInfo' from assembly 'mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089'.

Doesn't change whether I run with wine or just Mono, since I've got win's mono installed. Just gets rid of the Z:
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 06:56:58 pm
Thanks, I'll get rid of that particular element.
You may have to use a custom persist file, though, so which range do you want to claim?
Title: Re: TI-Nspire Key Brute Forcer
Post by: alberthrocks on February 27, 2011, 06:58:24 pm
My server will take
4000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

I can't really run this until that is implemented, since I won't be able to do my HW while that is running. :P
The above range will run on my server for now (withg.us.to under ircuser). :)
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 06:58:45 pm
hmmm.....how about
5000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
seems to be the trend :P

How long would that take?

EDIT, i'll take 5
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:02:48 pm
Any of our non-Windows friends should try making a file in the same directory as the program, and call it "persist.data"
In the file, in hex, put your number twice (on two lines).  Increase the second one by two.
That should do it.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 07:05:10 pm
as in

3000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

3000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000002

right?
Title: Re: TI-Nspire Key Brute Forcer
Post by: Ashbad on February 27, 2011, 07:05:21 pm
Also, I was just wondering, when it ends the process of trying to see if the key is correct, will it say if your guess was too low or high, so it can be tentatively be narrowed down in a WRNGOS fashion?
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 07:05:51 pm
actually, in most cases it will be both :P
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 27, 2011, 07:06:17 pm
I'll give 6000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000 a try. I hope this doesn't take half a year to run.
Title: Re: TI-Nspire Key Brute Forcer
Post by: apcalc on February 27, 2011, 07:07:07 pm
I'll give 6000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000 a try. I hope this doesn't take half a year to run.

If this takes half a century to work, we will be extremely lucky!
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:08:10 pm
What willrandship said.  And it doesn't stop until it has the key, or you close it.
willrandship, like that, but remove the new lines.  So:
Code: [Select]
3000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
3000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 07:10:09 pm
I'm still getting the error about mscorlib, and the bit about the runtime version....sigh.
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:10:28 pm
Rage.  Let me look into it.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 07:12:13 pm
It might be that debian's mono version is old....
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:12:37 pm
Code: [Select]
sudo apt-get update mono;)
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 07:16:32 pm
one sec, I'm repairing my package manager after some naughty play :P
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:30:31 pm
Quick update, it gets rid of the flickering and changes the number of tests to reflect the total lifetime of the file.
(Download) (http://www.omnimaga.org/index.php?action=dlattach;topic=6810.0;attach=6364)
Title: Re: TI-Nspire Key Brute Forcer
Post by: AngelFish on February 27, 2011, 07:33:47 pm
I'll take
7000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:35:09 pm
Sounds good, Qwerty.55.  Once
9000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
is taken, the next one will be
1100000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
and so on.
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 27, 2011, 07:37:48 pm
I just transferred this to my more powerful computer, overclocked the cpu, turned all fans to high, disabled all background apps, and hoped my power bill won't be too high.  :P
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:38:34 pm
Sounds good :P if you really want to, this program only sets its priority to High, you can manually set it to realtime from the task manager ;)
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 27, 2011, 07:40:50 pm
Sounds good :P if you really want to, this program only sets its priority to High, you can manually set it to realtime from the task manager ;)
I will do that. And what if we made this a competition to see who can test the most keys in a month?

Edit: number of posts in a year, 365  ;D
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:44:23 pm
Awesome :) I have a head start, I guess, seeing as I'm currently at 1,227.  Higher starting numbers will be at a disadvantage, because it takes longer to find prime numbers when you get that high, and it only tests psuedoprime numbers.
Title: Re: TI-Nspire Key Brute Forcer
Post by: qazz42 on February 27, 2011, 07:47:05 pm
ok, running this now, don't know how far I will go without comp overheating

C#++ :P
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:47:35 pm
qazz42, are you going to pick a range?
Title: Re: TI-Nspire Key Brute Forcer
Post by: qazz42 on February 27, 2011, 07:51:24 pm
well I am unsure of what the range should be..
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:52:10 pm
Then you have this:
8000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

When the program prompts you for a starting number, enter it all on one line.
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 27, 2011, 07:52:39 pm
I just tried something new. For me I have a quad core proc. What I did was make four folders each containing the program and persist.data. For the first persist it was 60... the second 64... the third 68... and the fourth 6C...
Now I use the entire CPU potential instead of 25%
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 07:54:16 pm
Great idea!  If you have tons of power to go around, you can use it like this.  But it won't help to use more programs than you have cores, by the way.
Title: Re: TI-Nspire Key Brute Forcer
Post by: AngelFish on February 27, 2011, 08:04:01 pm
Can anyone pick up my range? I'll be unable to work with it due to other issues.
Title: Re: TI-Nspire Key Brute Forcer
Post by: shmibs on February 27, 2011, 08:22:52 pm
7000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
you mean?
i'll take it =D
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 08:23:29 pm
It's yours :) thanks.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 09:23:40 pm
still getting mscorelib and runtime problems after updating :(
Title: Re: TI-Nspire Key Brute Forcer
Post by: Juju on February 27, 2011, 09:34:27 pm
Sounds interesting.
I can have
9000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000?

BTW after 9 it's A right?
Title: Re: TI-Nspire Key Brute Forcer
Post by: apcalc on February 27, 2011, 09:38:21 pm
BTW after 9 it's A right?

Yep! :)
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 09:39:52 pm
Wait, sir said it was 11 earlier, so is it really in decimal?
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 09:41:15 pm
x.x you're right, it's in hex.
Title: Re: TI-Nspire Key Brute Forcer
Post by: jnesselr on February 27, 2011, 09:41:42 pm
hey, I keep getting these errors:

** (/Users/graphmastur/Desktop/NspireKeyFactorerv1-2.exe:238): WARNING **: The class System.ConsoleKeyInfo could not be loaded, used in mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089

Unhandled Exception: System.TypeLoadException: Could not load type 'System.ConsoleKeyInfo' from assembly 'mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089'.

Those don't look too good.  I'm on mac running mono, btw.
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 09:43:15 pm
Nonwindows has been having issues.  I'll fix them eventually.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 09:43:30 pm
I get the exact same on linux!!! :P

Edit: Ninjad :P
Title: Re: TI-Nspire Key Brute Forcer
Post by: jnesselr on February 27, 2011, 09:44:04 pm
I get the exact same on linux!!! :P
Sir just ninja'd you with the answer to life, the universe, and everything. :P
Title: Re: TI-Nspire Key Brute Forcer
Post by: Juju on February 27, 2011, 09:46:20 pm
Also, another question...

0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
should be valid? After all, it could be a string of 512 bits all on 0 and still be a 512-bit number.

Also, I keep getting an "Invalid 512-bit number." error.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 09:47:59 pm
But, it won't be a factor of anything :P
Title: Re: TI-Nspire Key Brute Forcer
Post by: Juju on February 27, 2011, 09:49:30 pm
Yes, but that was an example to say the number could begin with a 0 (so be less than 512-bit, padded to 512 bits.).
Title: Re: TI-Nspire Key Brute Forcer
Post by: Deep Toaster on February 27, 2011, 09:54:53 pm
I guess I'll take

B000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

? I'm guessing that's what you meant by what comes after 9000...?
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 09:55:04 pm
@juju true.

Someone should take mine, 5
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 09:57:42 pm
All zeroes is not valid.  The first digit must be nonzero, or it wouldn't be 512 bits.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 10:01:09 pm
But the factor doesn't have to be 512 bits.....
Title: Re: TI-Nspire Key Brute Forcer
Post by: Deep Toaster on February 27, 2011, 10:01:20 pm
Hmm, wouldn't that make it $8000... and above, then?

And anyway, the start value input only accepts 254 digits. Is that a problem?
Title: Re: TI-Nspire Key Brute Forcer
Post by: Juju on February 27, 2011, 10:02:18 pm
512 bits are 128 hex numbers, usually.

And DT is right, if the first bit should be 1, so the number must be higher than 8000...?
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 10:04:16 pm
It is possible for it to be as low as 2 bits, and as high as 1022-1023 bits.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Juju on February 27, 2011, 10:06:39 pm
Yeah, IMHO, a 512-bit number is a number stocked on 512 bits, so it's between 0 and 2^512-1. The first bit is not necessarly 1. Unless the definition requires it, somehow...
Title: Re: TI-Nspire Key Brute Forcer
Post by: Deep Toaster on February 27, 2011, 10:06:50 pm
512 bits are 128 hex numbers, usually.

And DT is right, if the first bit should be 1, so the number must be higher than 8000...?

Why are all the numbers above 256 digits, then ???
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 27, 2011, 10:06:56 pm
I'm not entirely sure, we should check both of these things later.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Deep Toaster on February 27, 2011, 10:07:56 pm
We'd all be taking bad bounds, then...
Title: Re: TI-Nspire Key Brute Forcer
Post by: alberthrocks on February 27, 2011, 10:09:51 pm
Here's my build script for mono for non-Windows users to use.
The Ubuntu supplied Mono is too old to run this program.

Please, OPEN UP AND CHECK, AND IF NEEDED, MODIFY THE SCRIPT!
If you don't, I'll make you do it. ;)

It's a shell script, so when downloaded, make it executable, and then run it in a terminal.
(cd to the directory if needed, then run ./build_mono)

This is using latest mono version, so you don't need to modify the MONO variable.

To be fair, I haven't tested it thoroughly, since my server sucks at building things fast. :P
It should work though, considering that I've took an existing working script and modified it. ;)

Here it is! :D
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 27, 2011, 10:10:48 pm
no, as far as I can tell, the work happening now is valid, the prog will simply not cover all the possibilities. It will cover all the possibilities inside its range.

Edit: Yeah, afraid I won't be using that. I'm running debian. I also have the latest version of mono, as listed on their site.

Edit@ Scratch that, I'm using the old one :P

Found the problem btw, check out this bit of changelog from 2.10
Quote
(can now use any custom mscorlib)
Title: Re: TI-Nspire Key Brute Forcer
Post by: ruler501 on February 27, 2011, 11:37:35 pm
I'll take whatever you guys want to give me I would love to help with this
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 12:58:53 am
I might run this, although someone will have to send me a persist.data file because even after getting explained what to do on IRC I still don't understand, since everyone contradicts each other. 2 core max, though, because I would like Starcraft II to not take too much of a performance hit.
Title: Re: TI-Nspire Key Brute Forcer
Post by: AngelFish on February 28, 2011, 01:01:59 am
Juju has taken 9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

DJ will take
A000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Title: Re: TI-Nspire Key Brute Forcer
Post by: Juju on February 28, 2011, 01:02:05 am
Same, seems it always gives me an error, even if I have the right number of bits...

Code: [Select]
julien@amy:~/NspireKeyFactorer$ echo -n "9"; for i in `seq 1 127`; do echo -n "0"; done; echo;
90000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
julien@amy:~/NspireKeyFactorer$ mono NspireKeyFactorerv1-2.exe
1024 bit TI-Nspire boot2 RSA Key:
0xc3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d
0x3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b
0xbcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c
0xdf80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7

Ready to begin.  Press 1 to start at the minimum 512-bit value,
or anything else to specify a number.
Please specify which number to begin from (in hexadecimal):
90000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Invalid 512-bit number.

Also, the 5000... is free, if someone wants it.
Title: Re: TI-Nspire Key Brute Forcer
Post by: cooliojazz on February 28, 2011, 01:11:15 am
I call B00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000 !
Title: Re: TI-Nspire Key Brute Forcer
Post by: Builderboy on February 28, 2011, 01:13:01 am
I'll take 50000000...
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 28, 2011, 01:14:57 am
How is everyone doing so far? I know it is not much in the grand scheme of everything, but in 4 hours I will be reaching 100,000 tests. Accounting for the time I use that computer, it should total out to be 7 million tests each month. When the optimized asm version comes out I'm predicting significant speed gains of up to 4x. I know the chances are slim, but we might... just factor the rsa key.
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 02:00:01 am
2884 in almost an hour, so I guess 3000 an hour for me. Note I only use 1 core.
Title: Re: TI-Nspire Key Brute Forcer
Post by: bsl on February 28, 2011, 02:05:25 am
I haven't seen your algorithm for this, but this will improve your odds.
Include an ancient mathmetician's efficient algorithm for computers - Euclid !!!!
Use Euclid's gcd algorithm.

If your program looks like this:
Code: [Select]
do
 rannum = random()  // generate random 512 bit number or greater
 num = gcd(rannum,n) 
while(num  == 1 or num == n)   // break from loop if rannum a multiple of one of the primes ?
 print "Great !!!, factor found ", num
Then it would finish when it found a random number thats a multiple of one of its primes.
This is much better than finding one number by trial division.
Then your great grandchildren have a chance of factoring this.
Make sure you generate a 512 bit random number or greater if the number you are factoring is 1024.
Title: Re: TI-Nspire Key Brute Forcer
Post by: broooom on February 28, 2011, 02:59:23 am
I'm working on a server now... what do you guys suppose that would be a good range length to begin with? I think a whole 512-bit range is a bit too much.
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 28, 2011, 03:09:42 am
I'm working on a server now... what do you guys suppose that would be a good range length to begin with? I think a whole 512-bit range is a bit too much.
Is it feasible to complete Sir's current range. 100000000...
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 04:32:46 am
Is it a question or is it an answer? ???
Title: Re: TI-Nspire Key Brute Forcer
Post by: Lionel Debroux on February 28, 2011, 08:45:32 am
Um, people, remember ( http://ourl.ca/6418/129294 and other posts of mine): factoring a 1024-bit RSA key, using the best known algorithm, is a task more than three orders of magnitude harder than the state of the art (using unpublished algorithm implementations - the open source implementations aren't at that level yet, by a significant margin).
IOW, a problem that only very few persons in the entire world would have an idea how to tackle, let alone have the resources to run to completion - we're talking about dozens of thousands of cores for the sieving phase, and some pretty odd clusters and implementations for the post-processing phase...


As I wrote, some TF'ing can be done, although very extremely unlikely to succeed. It's even OK for you to make some software similar in spirit to the PRPNet/ECMNet server+client (that's where I'd start looking, if I wanted to make client+server software for RSA TF'ing).
So I'm not criticizing the idea itself. But if you're into TF'ing, then please, don't make an inferior independent reimplementation of a working wheel that was created months ago, on this very forum...
Namely, a C# TF'ing program with primality checking is a two-fold waste of CPU power - and a significant one at that, judging by the very low rate of progress indicated in various posts here (IIUC DJ's post, 3K divisions per hour... ouch !! Even 3M/hour would be bad):
* using C#, Java or any other language of the same class, for such kinds of very heavy number computation, is a cardinal sin. Even AOT compilation of those languages doesn't let one get down to the performance of C/C++ directly calling into highly optimized ASM-based libraries;
* the computational cost of primality-testing the numbers is extremely prohibitive, as shown by myself when optimizing the C program started by Tribal. Dividing mindlessly N, without any form of primality testing for P, makes the program much faster. And it can even be made slightly faster by adding several trial divisions to weed out the most obvious non-prime P. Check the post I linked to above in this post, and the topic that it links to.
And what's more, P or Q are very unlikely to be near enough from 0xxxxx00<many zeros>00 to be vulnerable to TF. Look at the hexadecimal representation of the factors for the TI-Z80 and TI-68k RSA keys. Choosing P and Q for making a good RSA key N=P*Q is a complicated process, which must (in the RFC sense) contain checks to ensure that P and Q are not too easy to find by indirect methods: strong primality testing/proving (APRT-CLE / ECPP / AKS), for P and Q; P-1, P+1, Q-1, Q+1 having at least one very large prime factor (i.e. P and Q are dubbed "strong primes"); and more.

I'm no cryptographer, and I don't know how any of the efficient integer factoring algorithms works. But after feeding the RSALS grid with more than 200 integers considered large for individuals or small groups of individuals, attending the serious sections of MersenneForum for one year and a half, and having some data about the harder factorizations done by the NFS@Home grid (which are still significantly easier than the factorization of a 768-bit RSA key), I think I have a better idea about the difficulty of factoring a 1024-bit RSA key, and the most efficient methods to achieve this aim, than all of you do ;)


TL;DR: facepalm. You guys fail at implementing a decent program for the task of factoring a RSA key, fail at using it, and as a result, you're wasting the vast majority of the CPU time you're devoting to it. Heaven forbid anyone notify MersenneForum, especially personalities such as Professor Robert Silverman, of this topic...
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 06:43:06 pm
Um, people, remember ( http://ourl.ca/6418/129294 and other posts of mine): factoring a 1024-bit RSA key, using the best known algorithm, is a task more than three orders of magnitude harder than the state of the art (using unpublished algorithm implementations - the open source implementations aren't at that level yet, by a significant margin).
IOW, a problem that only very few persons in the entire world would have an idea how to tackle, let alone have the resources to run to completion - we're talking about dozens of thousands of cores for the sieving phase, and some pretty odd clusters and implementations for the post-processing phase...


As I wrote, some TF'ing can be done, although very extremely unlikely to succeed. It's even OK for you to make some software similar in spirit to the PRPNet/ECMNet server+client (that's where I'd start looking, if I wanted to make client+server software for RSA TF'ing).
So I'm not criticizing the idea itself. But if you're into TF'ing, then please, don't make an inferior independent reimplementation of a working wheel that was created months ago, on this very forum...
Namely, a C# TF'ing program with primality checking is a two-fold waste of CPU power - and a significant one at that, judging by the very low rate of progress indicated in various posts here (IIUC DJ's post, 3K divisions per hour... ouch !! Even 3M/hour would be bad):
* using C#, Java or any other language of the same class, for such kinds of very heavy number computation, is a cardinal sin. Even AOT compilation of those languages doesn't let one get down to the performance of C/C++ directly calling into highly optimized ASM-based libraries;
* the computational cost of primality-testing the numbers is extremely prohibitive, as shown by myself when optimizing the C program started by Tribal. Dividing mindlessly N, without any form of primality testing for P, makes the program much faster. And it can even be made slightly faster by adding several trial divisions to weed out the most obvious non-prime P. Check the post I linked to above in this post, and the topic that it links to.
And what's more, P or Q are very unlikely to be near enough from 0xxxxx00<many zeros>00 to be vulnerable to TF. Look at the hexadecimal representation of the factors for the TI-Z80 and TI-68k RSA keys. Choosing P and Q for making a good RSA key N=P*Q is a complicated process, which must (in the RFC sense) contain checks to ensure that P and Q are not too easy to find by indirect methods: strong primality testing/proving (APRT-CLE / ECPP / AKS), for P and Q; P-1, P+1, Q-1, Q+1 having at least one very large prime factor (i.e. P and Q are dubbed "strong primes"); and more.

I'm no cryptographer, and I don't know how any of the efficient integer factoring algorithms works. But after feeding the RSALS grid with more than 200 integers considered large for individuals or small groups of individuals, attending the serious sections of MersenneForum for one year and a half, and having some data about the harder factorizations done by the NFS@Home grid (which are still significantly easier than the factorization of a 768-bit RSA key), I think I have a better idea about the difficulty of factoring a 1024-bit RSA key, and the most efficient methods to achieve this aim, than all of you do ;)


TL;DR: facepalm. You guys fail at implementing a decent program for the task of factoring a RSA key, fail at using it, and as a result, you're wasting the vast majority of the CPU time you're devoting to it. Heaven forbid anyone notify MersenneForum, especially personalities such as Professor Robert Silverman, of this topic...
Lionel Debroux, I think you need to tone down on the harshness. If you post a post like the above again, you'll be banned. You are not allowed to say anything negative against other people project unless you can contribute something better to it. Also saying facepalm to people is against the forum rules because it is rude and intended to make them feel like they have lower intelligence, which is not the case, and telling them they fail at something. There are nicer ways to say things. I decided to rate down your post.

Maybe you have a point, but so far you contributed no code for a better RSA key factorer program. People will be happy to use it to factor the key. Maybe coding it your way is beyond their programming skills, I don't know, but maybe before criticizing you should maybe contribute a better program.

Otherwise, Omnimaga goes with the following rule: "If you don't have anything nice to say, don't say anything at all."
Title: Re: TI-Nspire Key Brute Forcer
Post by: ruler501 on February 28, 2011, 06:58:46 pm
I agree with DJ if you can't be helpful it doesn't help for you to post.
I'm trying to work on this just my way is entirely theoretical.(Trying to predict primes) I probably won't be any help but I'm trying.
Should I count 2 when trying to predict primes since I know with the Gaussian integers it is not prime. I hope to find something but logically I don't think I will.
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 07:01:52 pm
Well, he is helpful in the way he suggested alternatives, but it's HOW he suggested them that is the problem. If people here had the experience to write a better factoring/whatever algorithm in the way Lionel suggested and in ASM, I am sure it would've been done long ago. Plus, for now, maybe we can start with what we got then once a better program is written, switch to that one?

My concern, how, however, is if we use a server, would it have enough space to store the entire info from people?
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 28, 2011, 07:11:07 pm
DJ, the serer doesn't store all the numbers. it would only need to store the end numbers from the ranges checked. ie 256, 512 is much oess than 256,257,258,259,260,...,270,...,280...512. Plus, as ranges get expanded, the space used is the same.
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 07:14:24 pm
I see, I guess it wouldn't be too bad, then.
Title: Re: TI-Nspire Key Brute Forcer
Post by: ruler501 on February 28, 2011, 07:17:37 pm
You could probably optimize this by only checking odd numbers. It should halve the number of numbers to be checked.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Builderboy on February 28, 2011, 07:18:12 pm
I agree with DJ as well, you have good points, but you can put them in a way that sounds less like you are insulting the intelligence of everybody working on the project, and more like you are offering your help.
Title: Re: TI-Nspire Key Brute Forcer
Post by: willrandship on February 28, 2011, 08:09:21 pm
@Ruler you can take that one step further, and eliminate roughly 69% of the numbers.
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 28, 2011, 08:47:17 pm
@Ruler you can take that one step further, and eliminate roughly 69% of the numbers.
We could go even farther by using the sieve of eratosthenes to calculate a large range of primes first, then test only those primes.
Title: Re: TI-Nspire Key Brute Forcer
Post by: jnesselr on February 28, 2011, 08:55:34 pm
@Ruler you can take that one step further, and eliminate roughly 69% of the numbers.
Can we just eliminate 70% of the numbers? Or how about 99%? Anything that lowers the numbers to check is a good algorithm to pursue.  Let's see, if we stored 2^512 bits in memory (2^509 bytes) for each number 0-2^512, we could then reset each bit when we disregarded that number by some algorithm.  Interesting thought memory wise, no?
Title: Re: TI-Nspire Key Brute Forcer
Post by: phenomist on February 28, 2011, 09:01:15 pm
Hmm, would somebody be interested in converting the key from hexdecimal to decimal? I can't get NET 4.0 Framework running on this computer...
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 28, 2011, 09:13:44 pm
Just want to let everyone know that we will get this project done. It may seem unfeasible at first, but every test we go through is a chance to factor the rsa key. Everyday our progress will increase exponentially. We will get more users, we will get faster computers, and we will get faster programs. Even if this takes one year, two years, even ten years it will still be worth it. The 83+ came out twelve years ago and it is still the most popular calculator here. Twelve years from now people will still use the nspire. It may take a while, but it will be worth it.

Update: My test count is now up to 270,000.  ;D
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 28, 2011, 09:14:33 pm
My test count is now up to 270,000
Daaaaamn

EDIT:
Also, I've recruited several people I know from school to help with this, and will be assigning them ranges soon.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Snake X on February 28, 2011, 09:20:12 pm
I has an idea: Lets write a program where all of us can do this together! Why go with this as individuals if we can make a program that will let us donate our cpu cycles to solve this one problem.. It would in theory be like a cluster of computers that would be working on this at the same time that way we could get it done faster :D

I know we are doing this together already, but I mean doing it together in real time and making our computers connected to do it at the same time.
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 28, 2011, 09:20:54 pm
Because that is extremely difficult.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Snake X on February 28, 2011, 09:23:40 pm
oh.. yeah I didnt think about that aspect of that.. well it is a neat concept nonetheless. Once I build my computer, I will run this thing at ~4.8 GHz at most with 4 cores. BTW you should make this utilize quad core cpu's that would be a nice feature :D
Or maybe we could write a bootable mini os that will only compute this task and run nothing else on it (no windows explorer, or task bar, or any windows services). Basically to utilize every single ounce of cpu power there is.
Title: Re: TI-Nspire Key Brute Forcer
Post by: jnesselr on February 28, 2011, 09:24:21 pm
Because that is extremely difficult.
That and the networking overhead, server that maintains it, etc. would all slow it down more than our individual efforts.
oh.. yeah I didnt think about that aspect of that.. well it is a neat concept nonetheless. Once I build my computer, I will run this thing at ~4.8 GHz at most with 4 cores. BTW you should make this utilize quad core cpu's that would be a nice feature :D
Or maybe we could write a bootable mini os that will only compute this task and run nothing else on it (no windows explorer, or task bar, or any windows services). Basically to utilize every single ounce of cpu power there is.
He could just create a linux live CD.  That could work pretty well.
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 28, 2011, 09:26:14 pm
There is a bit of a problem.
It seems that the BigInteger class I'm using only supports up to 512 bits.  And has been truncating everything.
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 09:29:04 pm
What does it means? Does it means we have to restart from scratch? O.O

And z80man what kind of computer do you have? O.O I got an Intel Core i7 (quad-core) 2.80 GHz with 8 GB of RAM and I'm not even at 60000 yet. O.O
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 28, 2011, 09:30:16 pm
It means we start from scratch.
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 09:31:46 pm
Darn X.x

Should we also wait until there's an ASM version or something now, since we have to restart anyway?
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 28, 2011, 09:32:31 pm
Probably.  I'll put together an implementation of calc84maniac's algorithm.
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 09:32:54 pm
Ah ok cool to hear.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Snake X on February 28, 2011, 09:33:20 pm
did the program have quad core support from the very beginning or is it just single core? Quad core would definitely help I think..
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 28, 2011, 09:33:43 pm
Yeah, I'll give the new one multi-core support.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Snake X on February 28, 2011, 09:34:40 pm
ah thanks for that. This should run nice 'n smooth on my computer... once I get it built x.x not to mention the time for the thermal compound to break in before touching the overclock button

edit: why wouldnt this work off a usb drive?
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 28, 2011, 09:35:27 pm
On anything other than Windows, I can provide no help.
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 09:37:34 pm
Will it be possible to set it to only use 1 core, though? My internet is already slower with the version you posted yesterday. O.O
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on February 28, 2011, 09:38:25 pm
I'll post a much better program when the time comes, that will allow you to customize exactly how much of your CPU(s) you want to devote to the task.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Snake X on February 28, 2011, 09:39:05 pm
See I was thinking of a dropdown menu to select how many cores you want to utilize... wait if this isnt a gui application, then a paremeter for 1-4 depending on how many cores you wanna use would work.. right?

edit: NINJI'D 8)
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 09:39:20 pm
Good to hear. :D
Title: Re: TI-Nspire Key Brute Forcer
Post by: phenomist on February 28, 2011, 10:02:35 pm
137426454337521899137502452525605466748829534697526357946510356073439963309278587906732336287048350193565270671049611558935534759741894429581138110991019864818898792610752419053602832785246554297841481080233597667469592742563152706207467933515159107380059434427511231769817853007350965081930222294271540538551

The key in decimal. If I converted what I think is the key.
Title: Re: TI-Nspire Key Brute Forcer
Post by: souvik1997 on February 28, 2011, 10:02:57 pm
I don't know if this has already been asked, but why not write it in x86 asm or C? They are faster than C#, and they are also more compatible with other operating systems. Other than that, very nice, although I don't think the key will be factored soon. :/
Title: Re: TI-Nspire Key Brute Forcer
Post by: alberthrocks on February 28, 2011, 10:09:28 pm
I don't know if this has already been asked, but why not write it in x86 asm or C? They are faster than C#, and they are also more compatible with other operating systems. Other than that, very nice, although I don't think the key will be factored soon. :/
It will be. calc84 is working on a C/inline ASM version as we speak. ;)
Add a GUI wrapper (wxWidgets!! :D), and it will be ready for mass use! ;)

calc84: if you're reading this, I suggest (if you don't know already) to use libpthread to get multiple cores working.
IF I'm right, multiple threads = multiple CPUs (at least in Linux, anyway). libpthread is recommended for cross-platform dev, and is probably much easier than Windows threads.
Title: Re: TI-Nspire Key Brute Forcer
Post by: phenomist on February 28, 2011, 10:15:59 pm
This seems like a better algorithm than the every number and divide algorithm :P

http://www.alpertron.com.ar/ECM.HTM.

I call Curves 0 - 1000.
Title: Re: TI-Nspire Key Brute Forcer
Post by: XVicarious on February 28, 2011, 10:35:58 pm
Sir, I'll take D and F! I have two computers!
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 10:39:35 pm
Welcome back Jkag! However I am not too sure if we'll choose anymore on the next version. Maybe it will be done through a server or something and automatically assign you a range, I'm not sure anymore.
Title: Re: TI-Nspire Key Brute Forcer
Post by: XVicarious on February 28, 2011, 10:40:45 pm
Ohh.... Okay. I should have read more, but I didn't wanna read 8 pages lol
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on February 28, 2011, 10:43:24 pm
Yeah I understand, not to mention there is another topic too. XD But yeah as suggestion, checking the topic's first post is generally a good idea in some cases. Other times it isn't because it is not updated, but some authors update the main info there.
Title: Re: TI-Nspire Key Brute Forcer
Post by: XVicarious on February 28, 2011, 10:44:35 pm
It doesn't look to me like he updated it, oh well. I know now
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on February 28, 2011, 11:57:54 pm
I think it should also be a small range that a server assigns you at a time. Running nonstop on my computer http://ourl.ca/9218/175045 with four instances it would take me four days to get through a 32 bit range on the C# version. For the asm version I am expecting about twelve hours on my system.
Title: Re: TI-Nspire Key Brute Forcer
Post by: phenomist on March 01, 2011, 12:03:48 am
What algorithm are you using? ECM has breezed through a 64 bit range in less than 2 hours.
Spoiler For ECM curve progress:
* = Paused Progress
Spoiler For Curves 0 - 10000:
0-1000 - phenomist
x0yy: finished, x1yy: finished, x2yy: finished, x3yy: 33% done*, x4yy: done, x5yy: done, x6yy: 37% done, x7yy: ns, x8yy: ns, x9yy: ns

1000-2000
2000-3000
3000-4000
4000-5000
5000-6000
6000-7000
7000-8000
8000-9000
9000-10000
10000+ (once assigned, categories will be written out)
Spoiler For curve = 10000+:

Starting at 421337: phenomist (up to 421345)
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on March 01, 2011, 01:49:25 am
How many did SirCmpwn's program went through in the same amount of time compared to yours?

Also, from what I gather, Calc84maniac rewrote his program in assembly, but I could be wrong.
Title: Re: TI-Nspire Key Brute Forcer
Post by: phenomist on March 01, 2011, 02:16:23 am
Well, to be precise, I only found the program; I obviously did not write the (really good) factorizer in the link.
(Rehash: link is here -> http://www.alpertron.com.ar/ECM.HTM )
Spoiler For key in decimal:
137426454337521899137502452525605466748829534697526357946510356073439963309278587906732336287048350193565270671049611558935534759741894429581138110991019864818898792610752419053602832785246554297841481080233597667469592742563152706207467933515159107380059434427511231769817853007350965081930222294271540538551

I accidentally truncated the key in an early test run to 42 digits (about 120-ish bits); it factored (or rather didn't factor) the prime in under a second.

Also, there's no way I can directly compare speed otherwise, but I'd say that it'll run somewhere on the magnitude of millions of times faster, if the current algorithm is a straight up divide this, add by two algorithm.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Lionel Debroux on March 01, 2011, 02:52:52 am
Quote
I don't know if this has already been asked, but why not write it in x86 asm or C?
Yes, it has been suggested by myself on page 6, and such a TF program was even written and published on Omnimaga, by Tribal and myself, months ago ;)

phenomist, ECM is only good for finding small factors. It's roughly as extremely unlikely to find a 512-bit factor as TF is... IOW, you too are wasting your CPU time.


I stand corrected, I failed to communicate in my previous post, on page 6. That people make a bad independent reinvention of the wheel, without having consulted the background contained in other previous topics (or understood it, as DJ is arguing - I disagree, see below), and make everyone waste time (CPU time or explanation time) was no valid reason for the TL;DR part. Again, this is no excuse, but if some big names in the integer factoring had commented on the topic, now that would have been bashing, I can tell you... Although they'd probably have chosen to completely ignore 1) anyone trying to TF a RSA key and 2) the misguided waste of CPU time due to the sub-par implementation we're talking about here.
It's sad to see people focusing on several words at the end of a post containing > 90% of useful content (I could just have posted the TL;DR part, Kofler's style - you know that he's less patient than I am). It's sad to see that they seem to keep working in the wrong direction (the C# program) or reimplementing the wheel yet another time (for the fifth time in two days: on the Omnimaga forum, there's already a C program started by Tribal and optimized by myself, with manual resume support, I explicitly mentioned it in my previous post - so there was nothing to understand, just use the program) - i.e. I totally failed, because my post has had the opposite of the intended effect.

Anyhow, it's probably the last time I'm trying to help on Omnimaga wrt. factorization of the Nspire keys. I've already spent too much time trying to explain things. I'm aware that not everybody reads everything on Omnimaga - for one, I don't - but I really feel I've wasted my time.


BTW, could someone explain me how I attempted to start a language war by pointing the well-known, common sense fact that C#, and other languages of the same class, are not the best fit for heavy number computation tasks ? That might help me for the next time I'm participating in a discussion here.
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on March 01, 2011, 03:11:41 am
@Lionel Debroux you are trying to start a language war.
Quote
by pointing the well-known, common sense fact that C#, and other languages
If you see here by calling this a common sense fact you are being offensive to people who code in C# and are involved in this project. You are not providing any reasons and are just discouraging people from taking part in this project. You also blame others for not reading your post fully when it seems that you did not fully read the topic. If you had you would see that the C# program is only temporary until Calcdude84SE codes the optimized asm version. C# was chosen as that is the language Sir best programs in. Brooom is also in the process of creating a server to streamline the factoring process. So far all you have contributed is a negative atomsphere and this will not be tolerated any longer.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Lionel Debroux on March 01, 2011, 03:20:17 am
Nope, I did not miss the "While a better program is worked on" part. But the thing is, a better program than this one did already exist, although nobody seemed to remember, and, as I reminded, I have worked on it.
And z80man, I did provide reasons for why there were better fits than C# or languages or the same class ;)
Also, note that I haven't written that there wasn't any way to do a better TF program than the existing program that Tribal and I worked on ;)

EDIT: at z80man's request, adding link to the topic containing the GMP-based C implementation made by Tribal and I: http://ourl.ca/6236 / http://www.omnimaga.org/index.php?action=topicattach;topic=3639 .


As I already wrote on IRC and above, I don't think that my warning is undeserved. It was, however, unfair, insulting (even slanderous ?) that a number of you vilified me for not having worked on better TF'ing programs (despite my explicit mention, in that very post, that I did !)... This is why my first reaction on IRC, this morning, was "Um, are you nuts ?".
We're in a situation where both "you" (the participants to the topic) and me feel doubly insulted. And as AOC posted after the initial version of my post, let's calm down. On my side, I've already posted my apologies.
Title: Re: TI-Nspire Key Brute Forcer
Post by: TIfanx1999 on March 01, 2011, 03:57:48 am
@All:Please calm down a bit guys. I don't see any evidence of anyone trying to start a language war. If a tool has already been written in a more efficient language, I don't see pointing that fact out as trying to incite a language war.

@Lionel: I understand your frustration seeing as you have contributed in a previous topic about the same thing and helped the C implementation of a factoring program. Just, be sure not to be rude.
Title: Re: TI-Nspire Key Brute Forcer
Post by: KermMartian on March 01, 2011, 11:33:50 am
As a computer scientist and electrical engineer with two degrees and two more in progress, I completely back Lionel on this.  The state-of-the-art involves research labs with millions of dollars of funding and massive superclusters working on this problem; your approach is naive and lacks their experience (no offense, that's the fact; naive in its computer science definition: "taking the most apparent route, which is often the least optimized").  To put it harshly and bluntly, if teams with dozens or hundreds of years of research experience between them have shown this problem to be prohibitive with large clusters and extremely well-written C code, I'm afraid that an amateur implementation in C# is not going to cut it.  I think it was pretty clear that Lionel was looking out for your best interests and trying to save you frustration, electricity, and computer load.  His post was well-written, knowledgeable, and I think those who read it in its entirety should have taken no offense from it.  Regarding the language issue, the speed of C# due to overhead compared with well-written C is a well-documented academic fact.

Cheers.
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on March 01, 2011, 02:43:30 pm
Yeah, the issue was simply the final part of the post, which was against Omni rules (especially the "facepalm" comment). When a post contains one harsh part, for many people it will pretty much blind them from the rest of the post content, and I feel that a large useful post is not an excuse to append a small rude comment at the end. As for the language comment I guess I misinterpreted it as a language war starter, but we had several of them recently by various people so I guess it can be hard to make the difference after a while. I also had to deal with several language wars before on another game-related calculator forum and yAronet is historically known to have them too (eg: Goplat's port of Java to the TI-Nspire was heavily bashed by various people, even if the project was by the very one who wrote a TI-Nspire NES emulator and a computer TI-Nspire one).

That said, calc84maniac came to the rescue with his ASM alternative, but otherwise we would be stuck with a C# version, since no one else knew how to write one in ASM or C. I am hoping that Lionel's method of factoring the key will be implemented in the ASM version or that his own program will be used, if people can actually find it in the 3 threads. Basically, for now, it was either an innefficient C# method, or nothing.

I apologise for misinterpreting the C# comment as language war and accusing you of not having contributed any program for this, but remember to be careful about the tone of your posts on Omnimaga. Just remember also that there are people who are more sensitive than others and when visiting this forum they might be like:

PotentialHardcoreTiProgrammer: "Wow look at that thread, look what kind of remark this guy say to others. Let's find another forum."
RandInt(1,2
If Ans=1:Then
*signs up elsewhere*
*suggests friends to avoid Omnimaga*
Else
*quits the community after failing to find another board*
End

We won't single out/treat as inferior being this group of people, like I saw happen on many other TI sites in the past.  Anyway you apologised for the that so that's good.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Lionel Debroux on March 01, 2011, 03:05:29 pm
Quote
I am hoping that Lionel's method of factoring the key will be implemented in the ASM version or that his own program will be used, if people can actually find it in the 3 threads.
Well, DJ, I provided a direct link to the source code in my previous post ;)
The topic is http://ourl.ca/6236 , and the attachments are http://www.omnimaga.org/index.php?action=topicattach;topic=3639 . And maybe admins have a quick way to find the post corresponding to a given attachment ?
Quoting myself:
Quote
note that I haven't written that there wasn't any way to do a better TF program than the existing program that Tribal and I worked on ;)


I know of the algorithm you've posted - but it goes for both myself and yourselves ;)
On the one side, there are two improper words in the "TL;DR" summary of my post, for which I apologized.
On the other side, there's a groundless personal attack, sent by some of you - among which some moderators - against me. I have actually spent some of my free time working on something to help with TF'ing the Nspire key - unlike most of those who posted that attack and down-rated my post.
So, please apologize on your side, and let's go forward together. Thanks in advance :)
Title: Re: TI-Nspire Key Brute Forcer
Post by: DJ Omnimaga on March 01, 2011, 03:22:04 pm
Yeah I simply went to the attachment list personally, as I couldn't find it through posts. And yeah admins can find a specific attachment post, but it's one single list for the entire forum, so your post would be buried in the list behind about 1000-2000 posts, most likely.

Anyway I'm sorry for the personal attacks if I made any. I guess I was kinda frustrated at the last part of the post then later how this matter was brought up on another IRC channel (I do not know the intention behind this) that had nothing to do with Omni, and when I am angry I tend to say things I would not say normally. You are free to rate down my posts if they contain any.
Title: Re: TI-Nspire Key Brute Forcer
Post by: Lionel Debroux on March 01, 2011, 03:24:51 pm
Quote
Anyway I'm sorry for the personal attacks if I made any. I guess I was kinda frustrated at the last part of the post then later how this matter was brought up on another IRC channel (I do not know the intention behind this) that had nothing to do with Omni, and when I am angry I tend to say things I would not say normally. You are free to rate down my posts if they contain any.
ACK. Let's move forward together then ;)

I'm not sure I'm in a position where down-rating your posts wouldn't be considered rude ;)
But yeah, for example, "but so far you contributed no code for a better RSA key factorer program" and "If people here had the experience to write a better factoring/whatever algorithm in the way Lionel suggested and in ASM, I am sure it would've been done long ago", and "and more like you are offering your help", as replies to a message that contains an explicit mention (even though no direct link) of such code of mine (though as I also mentioned, I did not fully write it myself), was very rude ;)
Title: Re: TI-Nspire Key Brute Forcer
Post by: Horrowind on March 01, 2011, 03:34:22 pm
a better aproach for a longtime project would be using an existing infrastructure such as BOINC (http://boinc.berkeley.edu/) but one would need to work into the API. On the other hand it would be easier on the client side, since there is already an existing client software, which could attract more people. But well, as the chances are very small  :-\
Title: Re: TI-Nspire Key Brute Forcer
Post by: Lionel Debroux on March 01, 2011, 03:43:25 pm
Correct, and even if BOINC is (rather) easy to set up and maintain, maybe (more evaluation is required) we don't even need to bother with this kind of generic infrastructure.
Using programs such as PRPNet/ECMNet as a starting point might do the job, given that those are already dealing with integers, they have a networking protocol between sockets on the two sides, and they launch external worker programs on the client side :)
Adaptations will be necessary, of course, because we're not dealing with ECM curves or primality tests. And the latest version of ECMNet might be a better starting point than the latest version of PRPNet, because there's not yet any dependency on a SQL server (just edit text files with a simple syntax on the client and the server - I've done this earlier today for local ECMNet testing on an integer).
Title: Re: TI-Nspire Key Brute Forcer
Post by: SirCmpwn on March 01, 2011, 05:37:43 pm
Just how many times do I have to say that I don't expect the brute force method to work?  I know it won't work.  But it is possible to happen, and it's better than doing nothing.
Title: Re: TI-Nspire Key Brute Forcer
Post by: qazz42 on March 01, 2011, 05:50:04 pm
Just how many times do I have to say that I don't expect the brute force method to work?  I know it won't work.  But it is possible to happen, and it's better than doing nothing.
^ this

what sets us apart from TI is that we at least try :D
Title: Re: TI-Nspire Key Brute Forcer
Post by: z80man on March 01, 2011, 08:39:29 pm
I would personally like to apologize to Lionel Debroux for some misunderstanding between posts. I understand that you were frustrated that people were not noticing the earlier work developed by you and Tribal. Unfortunately what I have noticed before that online, the intentions of others can be hard to interpret. I fully agree with you that a C/asm version is required, but I only wanted to defend the work of other members.  I apologize that some of my posts were rude, but now I hope that we can continue to work together on this project.