Author Topic: New RSA Algorithm discussion  (Read 57811 times)

0 Members and 1 Guest are viewing this topic.

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: New RSA Algorithm discussion
« Reply #150 on: February 28, 2011, 01:09:48 am »
No, it doesn't need a server, and runs on almost every platform imaginable.  You'll be able to specify your range, and claim it here.
Ah I see what the range was for then. I was wondering how we would avoid duplicates while doing our own thing alone on each side x.x.

I wonder how many years this will take, though...
Dream of Omnimaga

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: New RSA Algorithm discussion
« Reply #151 on: February 28, 2011, 01:11:29 am »
Expect 500+ guests if they link to omni.

This should be fun.

I'm gonna say don't count your chickens before they hatch :P So the basic mentality here is that, we know its unlikely, but we are going for it against all odds?  I'm in :)

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: New RSA Algorithm discussion
« Reply #152 on: February 28, 2011, 01:11:31 am »
Best case: It'll be solved by tomorrow.

Worst case: The sun will have died by the time the solution is found using this method.
« Last Edit: February 28, 2011, 01:12:00 am by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: New RSA Algorithm discussion
« Reply #153 on: February 28, 2011, 02:40:04 am »
I think Slashdot and the like mostly post about stuff that has been done, not planned to be done, so it might not work. But otherwise I am not sure of a good way to convince other people to get into the project. It would take thousands and thousands of them, and then there would be a need for a server so we don't have to put like 1000 people in the first post.
Dream of Omnimaga

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: New RSA Algorithm discussion
« Reply #154 on: February 28, 2011, 08:08:58 am »
Quoting myself from reply #71 in this very topic:
Quote
We've already had lots of talk about factoring the key, in another topic (but it's understandable that you missed it: there's lots of activity on the forum, and that is a good thing): http://ourl.ca/6236 :)

I have summarized multiple times how impractical the factorization is (unless some ground-breaking algorithm comes to the rescue, which we should not hold our breath on): basically, three orders of magnitude harder than the state of the art.
A linear extrapolation of the figures given in the paper detailing the factorization of RSA-768, consistent with what we know of 512-bit RSA factoring, gives the need of sifting through 10000-100000 TB (yes, I really mean terabytes) of data, after those have been produced by several dozen thousands of computers running for years (or ten times as many computers, running for one tenth of the time).
This does not, however, mean that we can't spend up to several CPU-years trying to find a factor by Trial Factoring (beyond that would not be reasonable): it's extremely unlikely that we'll succeed by sifting through a search space which represents an vanishingly small part of a particle, compared to the whole universe - but such is the beauty of random.
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: New RSA Algorithm discussion
« Reply #155 on: February 28, 2011, 04:11:21 pm »
Best case: It'll be solved by tomorrow.

Worst case: The sun will have died by the time the solution is found using this method.
By the time the sun dies out, I'm pretty sure we'll have quantum computers.

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #156 on: February 28, 2011, 05:26:02 pm »
We all know complexity of it.  I know it very well in fact.  We're actually pretty much hoping to get lucky here. ;-)

SirCmpwn

  • Guest
Re: New RSA Algorithm discussion
« Reply #157 on: February 28, 2011, 05:38:53 pm »
I think we need to move away from the arguments about the infeasibility of this and move on to making it happen.

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: New RSA Algorithm discussion
« Reply #158 on: February 28, 2011, 06:14:15 pm »
Yeah to be fair I agree with Sir. Of course later it might be best to move on to more powerful computers and have this run on multiple computers from multiple people, because it's gonna take a friggin long while, but the thing is that in 2004-07, people said a Gameboy emulator for the 84+ was impossible, same for a Mode 7 engine, yet people managed to do it a few years later. Trying stuff is what makes the community progress. Not trying anything because we expect it to not work at all gives a 2008 POTY in long terms.
Dream of Omnimaga

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: New RSA Algorithm discussion
« Reply #159 on: February 28, 2011, 06:22:01 pm »
Yay for that.

Offline Tribal

  • The Fallen
  • LV5 Advanced (Next: 300)
  • *
  • Posts: 218
  • Rating: +15/-1
    • View Profile
Re: New RSA Algorithm discussion
« Reply #160 on: March 07, 2011, 05:34:00 pm »
I've been trying to find some function that could be used to find the next number that *might* be a factor in a semiprime. I've been using this program to get my test data, I can't really explain what it's doing so if someone with more math skill than me and can understand this program, if you would I would appreciate it ;)

Code: [Select]
:PQ→N:1→F
:int(√(N→X
:{0→L1:L1→L2
:For(θ,1,2
:While (fPart(N/X)>fPart(N/(X+1)))+(θ=2
:If X=Q-1:Return
:X-1→X:F+1→F
:If θ=2:Then
:If X>0:Then
:If fPart(N/X)<fPart(N/(X+1:Then
:Disp {X,F
:If L1(1)=0
:Then
:{X→L1
:{F→L2
:Else
:X→L1(dim(L1)+1
:F→L2(dim(L2)+1
:End
:X-1→X:1→F
:End
:End
:End
:End
:X-1→X
:End

(not very effective because of the limited memory on the calculator, have to find almost a perfect semiprime to work with. Might try whipping up a C program that can be used to get/graph the data)

EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.
« Last Edit: March 07, 2011, 06:50:13 pm by Tribal »

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: New RSA Algorithm discussion
« Reply #161 on: March 07, 2011, 05:48:02 pm »
theoretically, we don't have to find a way to solve all semiprimes, just one :P
hmmmm

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: New RSA Algorithm discussion
« Reply #162 on: March 07, 2011, 11:46:15 pm »
I've been trying to find some function that could be used to find the next number that *might* be a factor in a semiprime. I've been using this program to get my test data, I can't really explain what it's doing so if someone with more math skill than me and can understand this program, if you would I would appreciate it ;)

Code: [Select]
:PQ→N:1→F
:int(√(N→X
:{0→L1:L1→L2
:For(θ,1,2
:While (fPart(N/X)>fPart(N/(X+1)))+(θ=2
:If X=Q-1:Return
:X-1→X:F+1→F
:If θ=2:Then
:If X>0:Then
:If fPart(N/X)<fPart(N/(X+1:Then
:Disp {X,F
:If L1(1)=0
:Then
:{X→L1
:{F→L2
:Else
:X→L1(dim(L1)+1
:F→L2(dim(L2)+1
:End
:X-1→X:1→F
:End
:End
:End
:End
:X-1→X
:End

(not very effective because of the limited memory on the calculator, have to find almost a perfect semiprime to work with. Might try whipping up a C program that can be used to get/graph the data)

EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.
Do you want to factor the TI-Nspire key from a TI calc using TI-BASIC? O.O

j/k interesting. :P
Dream of Omnimaga

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #163 on: March 08, 2011, 07:04:08 am »
EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.
usually P is used as the smaller.  And if you already know P or Q, why do we need to find it?

Offline Tribal

  • The Fallen
  • LV5 Advanced (Next: 300)
  • *
  • Posts: 218
  • Rating: +15/-1
    • View Profile
Re: New RSA Algorithm discussion
« Reply #164 on: March 08, 2011, 10:12:36 am »
EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.
usually P is used as the smaller.  And if you already know P or Q, why do we need to find it?

I was randomly throwing a prime in P and Q, so I didn't know which was smaller.
In these scenarios I am using a known P and Q only to generate a semiprime N. From that, I'm trying to find a formula that would give the amount of numbers away from what might be the factor of N(I'm not actually using P or Q for anything except to get N and to stop after I've reached the lower of the two). With this function, it may speed up any TF'ing because you are not checking every other number, you would be checking the number given by the function. I believe that the function is uniform to all semiprimes as well, because the graph given for a random semiprime is equivalent if not the same for all of them. I'm not exactly sure how to find this function though, that's where I'm stuck at. It is a exponential graph that has multiple asymptotes, but from that I don't know what todo :/
« Last Edit: March 08, 2011, 11:06:24 am by Tribal »