Author Topic: TI-Nspire Key Brute Forcer  (Read 34149 times)

0 Members and 2 Guests are viewing this topic.

Offline z80man

  • Casio Traitor
  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 977
  • Rating: +85/-3
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #75 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.

List of stuff I need to do before September:
1. Finish the Emulator of the Casio Prizm (in active development)
2. Finish the the SH3 asm IDE/assembler/linker program (in active development)
3. Create a partial Java virtual machine  for the Prizm (not started)
4. Create Axe for the Prizm with an Axe legacy mode (in planning phase)
5. Develop a large set of C and asm libraries for the Prizm (some progress)
6. Create an emulator of the 83+ for the Prizm (not started)
7. Create a well polished game that showcases the ability of the Casio Prizm (not started)

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: TI-Nspire Key Brute Forcer
« Reply #76 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.
« Last Edit: February 28, 2011, 02:00:20 am by DJ_O »

Offline bsl

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 157
  • Rating: +14/-0
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #77 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.

Offline broooom

  • LV2 Member (Next: 40)
  • **
  • Posts: 28
  • Rating: +2/-0
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #78 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.

Offline z80man

  • Casio Traitor
  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 977
  • Rating: +85/-3
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #79 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...

List of stuff I need to do before September:
1. Finish the Emulator of the Casio Prizm (in active development)
2. Finish the the SH3 asm IDE/assembler/linker program (in active development)
3. Create a partial Java virtual machine  for the Prizm (not started)
4. Create Axe for the Prizm with an Axe legacy mode (in planning phase)
5. Develop a large set of C and asm libraries for the Prizm (some progress)
6. Create an emulator of the 83+ for the Prizm (not started)
7. Create a well polished game that showcases the ability of the Casio Prizm (not started)

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: TI-Nspire Key Brute Forcer
« Reply #80 on: February 28, 2011, 04:32:46 am »
Is it a question or is it an answer? ???

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: TI-Nspire Key Brute Forcer
« Reply #81 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...
« Last Edit: February 28, 2011, 03:33:55 pm by Lionel Debroux »
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: TI-Nspire Key Brute Forcer
« Reply #82 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."
« Last Edit: February 28, 2011, 06:44:05 pm by DJ_O »

Offline ruler501

  • Meep
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2475
  • Rating: +66/-9
  • Crazy Programmer
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #83 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.
I currently don't do much, but I am a developer for a game you should totally try out called AssaultCube Reloaded download here https://assaultcuber.codeplex.com/
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCM/CS/M/S d- s++: a---- C++ UL++ P+ L++ E---- W++ N o? K- w-- o? !M V?
PS+ PE+ Y+ PGP++ t 5? X R tv-- b+++ DI+ D+ G++ e- h! !r y

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: TI-Nspire Key Brute Forcer
« Reply #84 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?

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #85 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.

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: TI-Nspire Key Brute Forcer
« Reply #86 on: February 28, 2011, 07:14:24 pm »
I see, I guess it wouldn't be too bad, then.

Offline ruler501

  • Meep
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2475
  • Rating: +66/-9
  • Crazy Programmer
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #87 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.
I currently don't do much, but I am a developer for a game you should totally try out called AssaultCube Reloaded download here https://assaultcuber.codeplex.com/
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCM/CS/M/S d- s++: a---- C++ UL++ P+ L++ E---- W++ N o? K- w-- o? !M V?
PS+ PE+ Y+ PGP++ t 5? X R tv-- b+++ DI+ D+ G++ e- h! !r y

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #88 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.

Offline willrandship

  • Omnimagus of the Multi-Base.
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2953
  • Rating: +98/-13
  • Insert sugar to begin programming subroutine.
    • View Profile
Re: TI-Nspire Key Brute Forcer
« Reply #89 on: February 28, 2011, 08:09:21 pm »
@Ruler you can take that one step further, and eliminate roughly 69% of the numbers.