Author Topic: Virus to crack RSA for nspire? :P  (Read 71068 times)

0 Members and 1 Guest are viewing this topic.

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #75 on: July 07, 2010, 06:40:07 pm »
I agree too. We should be realistic. That team that factored the 768 bit number took two years to do it. If they factored a 1024 bit number with the same resources, it would take about as long as factoring 2^256 of those 768 bit numbers.

Offline bwang

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 634
  • Rating: +30/-11
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #76 on: July 07, 2010, 06:56:04 pm »
It would not take 2^256 times longer, but it would still take too long.

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: Virus to crack RSA for nspire? :P
« Reply #77 on: July 08, 2010, 01:45:59 am »
My cores are usually working on stuff more useful than TF'ing 1024-bit numbers ;)
That I know fully well that TF'ing 1024-bit numbers is impractical (I was the second person to write it in the topic, an hour after bwang :) ) does not mean that I cannot help speeding up the program (as a ways to learn a bit about the GMP API, which I had never used before) and make my computers spend a reasonable amount of time trying. I might end up unfathomably lucky, after all - and if not, no biggie, I knew it was impractical :)

Quote
What is the "only practical method"? I thought the GNFS was currently the fastest algorithm for factoring large integers with no special form.
Yes, it is GNFS. But we don't have access to the special implementation of GNFS + post-processing steps that enabled factoring RSA-768, made by the top researchers in the field :)
And anyway, even if we had it, I don't think it would be that useful to us, as some pieces of it would probably need some improvements so that they can scale up three orders of magnitude in difficulty, for factoring RSA-1024. Only the top researchers of the field can make the (probably) needed improvements.
« Last Edit: July 08, 2010, 02:26:36 am 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 Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #78 on: July 08, 2010, 03:17:16 am »
out of morbit curiosity, do we know what the probability that we actually manage to factor this is?

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: Virus to crack RSA for nspire? :P
« Reply #79 on: July 08, 2010, 03:19:02 am »
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: Virus to crack RSA for nspire? :P
« Reply #80 on: July 09, 2010, 02:46:28 pm »
Stopping work on 0xaba7... after ~3.1e12 trial divisions, switching to 0xc3b3...
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline quasi_Phthalo

  • LV3 Member (Next: 100)
  • ***
  • Posts: 90
  • Rating: +1/-1
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #81 on: July 10, 2010, 02:40:24 pm »
hey, on a side note, think of how famous the ti-community would be if we factored ANY 2048 bit key, not specifically the nspire's. so, ponder this: if you multiply two 2048 bit keys together, and try to factor that, you now have to locate one of 4 possible prime numbers in a field that is no larger than if you were factoring a single key alone. you've just doubled your chances, which halves the amount of time it takes to do it! with 4 keys together, you could factor one of them in 1/4 the time!!!! actually, its a little longer than that because you're working with a bigger number, but still!!!! ok, so we won't be able to factor the specific key we want, necessarily, but we'll still be famous for being the first people to factor a 2048 bit RSA key!!!

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: Virus to crack RSA for nspire? :P
« Reply #82 on: July 10, 2010, 02:45:13 pm »
We should maybe at least manage to do 1024 first, though :P

Offline quasi_Phthalo

  • LV3 Member (Next: 100)
  • ***
  • Posts: 90
  • Rating: +1/-1
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #83 on: July 10, 2010, 02:56:50 pm »
oops, sorry! I meant to say 1024 bit. I was just testing you all....slash, I was 50 years ahead in computer technology. good job DJ!

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #84 on: July 10, 2010, 04:01:50 pm »
2^1024 * 2^1024 = 2^2048.

Isn't that a lot bigger than one key by itself?

I think you were thinking add, or multiply by two.
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline apcalc

  • The Game
  • CoT Emeritus
  • LV10 31337 u53r (Next: 2000)
  • *
  • Posts: 1393
  • Rating: +120/-2
  • VGhlIEdhbWUh (Base 64 :))
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #85 on: July 10, 2010, 04:42:40 pm »
hey, on a side note, think of how famous the ti-community would be if we factored ANY 2048 bit key, not specifically the nspire's. so, ponder this: if you multiply two 2048 bit keys together, and try to factor that, you now have to locate one of 4 possible prime numbers in a field that is no larger than if you were factoring a single key alone. you've just doubled your chances, which halves the amount of time it takes to do it! with 4 keys together, you could factor one of them in 1/4 the time!!!! actually, its a little longer than that because you're working with a bigger number, but still!!!! ok, so we won't be able to factor the specific key we want, necessarily, but we'll still be famous for being the first people to factor a 2048 bit RSA key!!!

I think the community would become famous if we did just crack the 1024 bit key.  Has this ever been done before?  The community even got some publicity with the 512 bit keys!


Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #86 on: July 10, 2010, 05:12:09 pm »
As far as I know, it hasn't been done, considering the best one I heard about was 2 years for 768 bits.

Offline quasi_Phthalo

  • LV3 Member (Next: 100)
  • ***
  • Posts: 90
  • Rating: +1/-1
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #87 on: July 10, 2010, 05:13:14 pm »
Quote
I think you were thinking add, or multiply by two.
no, i actually meant multiply the 'n' values for two different keys together. the resulting number has 4 primes, each having about half as many digits as ONE of the n's. the probability of selecting a correct factor is doubled.

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: Virus to crack RSA for nspire? :P
« Reply #88 on: July 10, 2010, 05:54:57 pm »
Actually, that is incorrect. They are still 512 bits in length, so it makes no difference.

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: Virus to crack RSA for nspire? :P
« Reply #89 on: July 10, 2010, 05:56:32 pm »
One team actually did crack a 1024-bit key, but it wasn't through a factoring method. It was by starving the cpu of electricity, giving out tiny parts of the factor along with a bunch of other stuff. It took 11 months, and isn't applicable to the nspire, because of how it's factored.

Check out the article here
http://www.engadget.com/2010/03/09/1024-bit-rsa-encryption-cracked-by-carefully-starving-cpu-of-ele/