« previous next »
Pages: 1 ... 6 7 [8] 9 10 ... 14   Go Down

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

0 Members and 2 Guests are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: New RSA Algorithm discussion
« Reply #105 on: February 27, 2011, 05:36:52 pm »
They could be adjacent odd numbers so that means the number could be N(N+2), right?
Logged

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 #106 on: February 27, 2011, 05:37:40 pm »
Yes. The lower bound on the gap is 2. However, there are numerous primes that are not part of the set of twin primes.
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #107 on: February 27, 2011, 05:38:05 pm »
Quote from: SirCmpwn on February 27, 2011, 05:36:47 pm
Could I have that number in hex? :)
somewhere between 0x2 and 0x164
Logged

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 #108 on: February 27, 2011, 05:42:07 pm »
Or somewhere between 0x2 and 0x200 ;)

ln_2(0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)=0x200
« Last Edit: February 27, 2011, 05:42:59 pm by Qwerty.55 »
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

SirCmpwn

  • Guest
Re: New RSA Algorithm discussion
« Reply #109 on: February 27, 2011, 05:49:57 pm »
This code should find the key, right?
I'm adding some other housekeeping things, but this is the actual key finding code:
Code: [Select]
static void Main(string[] args)
        {
            // Boot2 Key:
            // c3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d
            // 3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b
            // bcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c
            // df80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7

            // Other keys:
            // aba7f0b8c7feb6e33438af5c25c67389eaf4d73f80cd0a37922493431cde03b3
            // 4da448bdb05387cf7a8c59ee12d9613429a2b07ea385752f079892da1ae76c2b
            // 158f2d7169aae066432fe44f797df39dd6a0d7b2e2091281b30efac247c51576
            // ebc93ec456de2e27d36b713844336b65af67ee58e6107a6a1deb954a91095295

            // b15e01c47c421be62f4e769b3ac98f4f983a820b0c181e35715d84a4f1acf052
            // 7eeddfabf9f66e73bedb55376e22f860c34dc70ce239157297056d4ecf465357
            // 78c3917647b5a6bb9c5638cdeff3e309ff66878fd4f233cf157d7af4136f307d
            // f90ec6ae6eaff6bead6d52f423a37dac59ff38ae876008103728f2bd674e858f

            Console.WriteLine("Factoring 1024-bit TI-Nspire boot2 RSA Key:");
            Console.WriteLine("0xc3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d");
            Console.WriteLine("0x3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b");
            Console.WriteLine("0xbcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c");
            Console.WriteLine("0xdf80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7");

            BigInteger key = new BigInteger("c3b3a7015c04299ff3a25f104e2285c1ec2d55471e6208959d0f6981b2fa2c6d" +
                "3e316f9364d5eb5c7789e142b75bfaf402e7e02fac0cb09f6419db1f44679f8b" +
                "bcca142f1d312feb095708ef175a4ef80271321e7240f0d854c90a74fc59209c" +
                "df80aa8f85ae3b948a3ce55c69cd050098d5a79aebbc241cc642b106b1af2cb7", 16);

            BigInteger startValue = new BigInteger("1552518092300708935148979488462502555256886017116696611139052038026050952686376886330878408828646477950487730697131073206171580044114814391444287275041181139204454976020849905550265285631598444825262999193716468750892846853816057856", 10);
            string maxNumber = "";
            while (maxNumber.Length * 8 < 512)
                maxNumber += "F";
            BigInteger maxValue = new BigInteger(maxNumber, 8);

            Console.Write("\n");

            BigInteger numberOne = startValue, numberTwo = startValue + 2;
            BigInteger numberOfTests = 0;
            BigInteger temp = 0;
            BigInteger distance = 356;


            while (true)
            {
                Console.Clear();
                numberOfTests++;
                Console.WriteLine("Number of tests thus far: {0}\n", numberOfTests.ToString());
                Console.WriteLine("Current numbers:");
                Console.WriteLine(numberOne.ToHexString() + "\n");
                Console.WriteLine(numberTwo.ToHexString());
                if (numberOne * numberTwo == key)
                {
                    Console.WriteLine("----Key found----");
                    while (true)
                        Console.ReadLine(); // Stop here
                }
                Console.WriteLine("Current test done, searching for next prime pair...");
                while (true)
                {
                    numberOne++;
                    if ((numberOne - numberTwo).abs() > 356)
                    {
                        numberTwo++;
                        while (!numberTwo.isProbablePrime())
                            numberTwo++;
                        numberOne = numberTwo + 2;
                        while (!numberOne.isProbablePrime())
                            numberTwo++;
                        break;
                    }
                    if (numberOne.isProbablePrime())
                        break;
                }
            }
        }
Logged

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 #110 on: February 27, 2011, 05:50:10 pm »
another quick thing;

if you check division by all the primes up to a certain point, you know the factor is inside of this (k=key, p=highest prime checked) from k/P to sqrt(k)

This becomes less and less effective the higher you go, unfortunately, because of shrinking square roots. however, with a little twisting of the algorithm you can eliminate it in the other direction instead. Note: this looks for the higher factor, whereas the perl script looks for the lower factor (ie 3*11=33, this would find 11 and they would find 3, irrelevant in implementation, but good to know)
Logged

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #111 on: February 27, 2011, 05:52:06 pm »
Code: [Select]
BigInteger maxValue = new BigInteger(maxNumber, 8);
should be 16 instead of 8, correct?
Logged

SirCmpwn

  • Guest
Re: New RSA Algorithm discussion
« Reply #112 on: February 27, 2011, 05:52:43 pm »
Already fixed.
I also think that the code that finds the next pair to test isn't working, any ideas?
Logged

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 #113 on: February 27, 2011, 05:56:06 pm »
right, but you count up with this method. Really, this would serve best as a range finder, for where to start something else.

@sir, remember to start on an odd number. ;)
« Last Edit: February 27, 2011, 05:56:38 pm by willrandship »
Logged

Offline alberthrocks

  • Moderator
  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 876
  • Rating: +103/-10
    • View Profile
Re: New RSA Algorithm discussion
« Reply #114 on: February 27, 2011, 05:58:49 pm »
I'm loving this! :D (Especially the Folding@Home kind of idea! ;))
Just before we go too crazy, some things I'd like to suggest:

1) Server submission - should be written in PHP or some web language. It must withstand many submissions (a mini DDoS, practically :P), and it has to be stable. The client prgm, after submitting, should pull the latest batch of numbers for backup. The server also reports any mirrors (mirrors are a MUST - you don't want numbers lost!), and the server reports if it's the main server or not. It can also report a main/mirror change if needed. If a factor is found, the main server should email everyone the key immediately, and proceed to pastebin the key as well. My server can act as the mirror, but it may need donations to get it at a good state. It won't be a main server tho – 512 MB of RAM is pretty shabby... :P

2) Client – I'd like to keep it up and running 24/7, but I don't want to have to stop it every time. An idea is to have it probe CPU usage. If it sees high CPU usage, it'll stop. Once the CPU usage goes down, it'll wait for a buffer 2-3 minutes before resuming work. Work, as usual, should be saved as much as possible. That way, it can act like a service/daemon/background program. :)

Indication of the client's activity can be achieved with wxWidgets via tray icon. (And if possible, a notification)

Also, as said above, it should submit their number, and pull an update list and such.

That's all! :) Continue discussing numbers! :P

EDIT: for CPU usage probing, probe every 10 seconds. Don't probe continuously or every second - then you'll be taking 100% CPU... :P
« Last Edit: February 27, 2011, 06:00:19 pm by alberthrocks »
Logged
Withgusto Networks Founder and Administrator
Main Server Status: http://withg.org/status/
Backup Server Status: Not available
Backup 2/MC Server Status: http://mc.withg.org/status/


Proud member of ClrHome!

Miss my old signature? Here it is!
Spoiler For Signature:
Alternate "New" IRC post notification bot (Newy) down? Go here to reset it! http://withg.org/albert/cpuhero/

Withgusto Networks Founder and Administrator
Main Server Status: http://withg.org/status/
Backup Server Status: Not available
Backup 2/MC Server Status: http://mc.withg.org/status/

Activity remains limited due to busyness from school et al. Sorry! :( Feel free to PM, email, or if you know me well enough, FB me if you have a question/concern. :)

Don't expect me to be online 24/7 until summer. Contact me via FB if you feel it's urgent.


Proud member of ClrHome!

Spoiler For "My Projects! :D":
Projects:

Computer/Web/IRC Projects:
C______c: 0% done (Doing planning and trying to not forget it :P)
A_____m: 40% done (Need to develop a sophisticated process queue, and a pretty web GUI)
AtomBot v3.0: 0% done (Planning stage, may do a litmus test of developer wants in the future)
IdeaFrenzy: 0% done (Planning and trying to not forget it :P)
wxWabbitemu: 40% done (NEED MOAR FEATURES :P)

Calculator Projects:
M__ C_____ (an A____ _____ clone): 0% done (Need to figure out physics and Axe)
C2I: 0% done (planning, checking the demand for it, and dreaming :P)

SirCmpwn

  • Guest
Re: New RSA Algorithm discussion
« Reply #115 on: February 27, 2011, 06:01:34 pm »
So it looks like my program works, I need to add some more stuff and it shall be glorious.  It's pretty slow though, averaging about 30 tests a minute.  This is because it only tests numbers that are likely to be prime, and it takes time to find the next psuedoprime number.  I'll add some stuff to reduce redundancy when others use it simultaneously, and persistance between runs, as well as crash protection (you shouldn't have to start over just because something went wrong.
Logged

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 #116 on: February 27, 2011, 06:02:11 pm »
One major issue is duplication. We only need to check each num once, so I think a server that held the ranges alreay checked would be nice. It would only take ~1024 bits per range, and big ranges would be the same size stored as small ranges :)
Logged

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #117 on: February 27, 2011, 06:03:48 pm »
@alberthro yeah, you pretty much described boinc there. :D
Logged

Offline broooom

  • LV2 Member (Next: 40)
  • **
  • Posts: 28
  • Rating: +2/-0
    • View Profile
Re: New RSA Algorithm discussion
« Reply #118 on: February 27, 2011, 06:04:21 pm »
I can do the server-side software. :)
Logged

SirCmpwn

  • Guest
Re: New RSA Algorithm discussion
« Reply #119 on: February 27, 2011, 06:04:45 pm »
Quote from: willrandship on February 27, 2011, 06:02:11 pm
One major issue is duplication.

Quote from: SirCmpwn on February 27, 2011, 06:01:34 pm
...I'll add some stuff to reduce redundancy when others use it simultaneously...
Logged
Pages: 1 ... 6 7 [8] 9 10 ... 14   Go Up
« previous next »