Results 1 to 3 of 3

Thread: elliptic distribution

  1. #1
    : Code Injector : nikolatesla20's Avatar
    Join Date
    Apr 2002
    Location
    :ether:
    Posts
    815

    elliptic distribution

    Maybe if Mike is around he could answer this, or some of you other Crypto experts:

    Say you have a algo like RSA public key. Now, I know if the key size is large bruteforcing would take forever and a day no matter what you do, but my question is - even if you wrote a bruteforcer, why would you actually start at the beginning and scan. I would tend to think the chances of the required value would very rarely be on the ends of the spectrum. Also very rare would be in the exact middle. I would think the best places to scan would be the lower and upper 2/3 of the number distribution.

    Am I on any kind of right track of thinking here? This is how I've always thought about any type of algorithm that ppl use to lock away code, in the case of writing a bruteforcer. Wouldn't the distro be similar to the normal "chaotic" bell curve?

    -niko

  2. #2
    Naides is Nobody
    Join Date
    Jan 2002
    Location
    Planet Earth
    Posts
    1,647

    Re: elliptic distribution

    Originally posted by nikolatesla20
    Maybe if Mike is around he could answer this, or some of you other Crypto experts:

    Say you have a algo like RSA public key. Now, I know if the key size is large bruteforcing would take forever and a day no matter what you do, but my question is - even if you wrote a bruteforcer, why would you actually start at the beginning and scan. I would tend to think the chances of the required value would very rarely be on the ends of the spectrum. Also very rare would be in the exact middle. I would think the best places to scan would be the lower and upper 2/3 of the number distribution.

    Am I on any kind of right track of thinking here? This is how I've always thought about any type of algorithm that ppl use to lock away code, in the case of writing a bruteforcer. Wouldn't the distro be similar to the normal "chaotic" bell curve?

    -niko
    I am hardly an expert in the field, but I here is my answer:

    The overhead of writing a key generator with chaotic functions, and keeping track of the already tested keys for not repeating too many of them would quickly neutralize any time saving advantage you might get by generating "random looking" keys.

  3. #3
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    The best way to factor large numbers (above a few hundred bits) is the Number Field Sieve. It works by finding a lot of relationships between numbers mod n and algebraic complex numbers. Algebraic numbers are those that you can get by using + - * / ^.

    For example, when n=2501 then you can say 50 = i since

    50^2 = 2500 = -1 mod n and i^2 = -1 in complex numbers.

    You'd try to factor every number a+bi in a certain "small" range, then factor a+b*50. You put a 1 in the matrix if the exponent on a prime factor is odd, and a zero if even.

    Finally, you try to find a set of rows that add to zero mod 2. With good probability, this will give you one factor.

    So the brute-force part is trying every a,b in a range, but it's not testing them as potential factors of n.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •