Results 1 to 11 of 11

Thread: RSA keygenning

  1. #1
    DinDon
    Guest

    RSA keygenning

    Hi!

    Just to avoid to reinvent the wheel...
    Has anyone already managed to solve this problem?

    Find a key k from this expression:

    k^65537 mod M = N, where:
    M and N are known huge integers (64 bytes long)
    ^ denotes the exponentiation operation
    mod denotes the modulus operation (in C denoted as %, integer remainder between two integers)

    In other words: the problem is to find the integer n-th root of an huge integer; the further modulus operation may make the things more difficult.
    I digged through the net, but I could not find nothing interesting.
    I suspect that some faster approach must exist, different from the classical RSA-breaking problem (which consist in finding two primes whose multiplication yields the modulus operand M).

    My best regards to all.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  2. #2
    Dizzy
    Guest
    DinDon (12-12-2000 19:02):

    Find a key k from this expression:

    k^65537 mod M = N, where:
    M and N are known huge integers (64 bytes long)

    I suspect that some faster approach must exist, different from the classical RSA-breaking problem.
    Good luck finding a method which is faster
    than factorization... It's a really
    hard
    mathematical problem.

    FYI, 512 bit moduli have been factorized
    using the GNFS (general number field sieve),
    but no easy-to-use public implementation
    is available. Also it would probably take
    more resources than it's worth.

    Take a look at http://www.codebook.org for
    an interesting break of a 512 bit modulus
    (stage 10).


    Diz.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  3. #3
    IcyDee
    Guest
    If this were a 'normal' function such as

    k^65537 = N

    and you knew N then you could easily calculate k.

    k = 65537th root of N

    however the modulus M makes it significantly more difficult since effectively you are 'throwing away' information needed to reverse the calculation. The equation is inherently none-reversable (if that is the correct term). This only leaves a brute force approach which is what makes it infeasible for sufficiently large values on M and N.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  4. #4
    Spath.
    Guest
    > The equation is inherently none-reversable
    > (if that is the correct term). This only leaves
    > a brute force approach which is what makes
    > it infeasible for sufficiently large values on M
    > and N.

    Uh ? There are efficient methods to solve such
    equations, you should never use brute force for
    that ; also efficiency of these methods does
    not depend on how large N is, but how easily
    you can factor it.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  5. #5
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    Are you designing the system or attacking it?

    If you're attacking it, 64-bit numbers are the product of two 32-bit numbers, easily brute-forced over a weekend with a naive algorithm (loop through all odd numbers and check for divisibility).

    If you're designing it, check out the protectionist's corner. From whom are you trying to protect the software? What functionality do you want to protect?

  6. #6
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    mike (12-13-2000 06:19):
    64-bit numbers are the product of two 32-bit numbers, easily brute-forced over a weekend with a naive algorithm (loop through all odd numbers and check for divisibility).
    Sorry, 64-byte numbers can't be brute-forced!

    Why not replace M and N in the file you're attacking so that you can pick an arbitrary k?

  7. #7
    DinDon
    Guest

    Thanks

    Hi all!
    Thanks to everybody for your answers...
    Another project to be thrown to the trashcan...

    dizzy:
    Good luck finding a method which is faster
    than factorization... It's a really
    hard mathematical problem.
    You are right. Thanks for the link (even if its content is not so technical). After reading that, I realized that even GNFS is not a feasible solution...

    IcyDee:
    the modulus M makes it significantly more difficult since effectively you are
    'throwing away' information needed to reverse the calculation.
    Correct! Furthermore, k^65537 mod M is different from k^65537 % M, as I thought before. It is not the same to apply the modulus operator just at the end of the exponentiation, but it must be applied after every multiplication performed to obtain the exponentiatiation!

    Spath:
    efficiency of these methods does
    not depend on how large N is, but how easily
    you can factor it.
    Sorry, I do not understandand what are the methods you are talking of. Probably you are referring to factorization of the modulus operand M. But this is a practically impossible job, at least with just one PC...

    mike:
    Are you designing the system or attacking it?
    Why not replace M and N in the file you're attacking so that you can pick an arbitrary k?
    Nope, I am not a protectionist and I am not interested to protect my software...
    Your solution (replacing M and N) is a good one, as would be to modify the code which compare the wrong encrypted key with the right encrypted one. But my initial target was just to build a keymaker in order to generate a valid usercode and an username without altering the executable (which is furthermore AsPacked or AsProtected) - ImageEye in my case.
    As I have seen, thanks to your all help, this target is not possible.

    My best regards.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  8. #8
    Spath
    Guest
    > It is not the same to apply the modulus operator
    > just at the end of the exponentiation, but it must be applied after
    > every multiplication performed to obtain the exponentiatiation!

    No, they are the same (basic multiplication in Z/nZ), but
    implementations with multiple intermediate modulos are much faster.

    > Sorry, I do not understandand what are the methods you are talking of.
    > Probably you are referring to factorization of the modulus operand M.
    > But this is a practically impossible job, at least with just one PC...

    Clearly solving equations in Z/nZ is generally speaking more complicated
    than solving them in Z. My point was that one never use brute-force
    to solve equations in Z/nZ, one can for instance use Euler totient
    function for this, which depends on modulo factorization. Now this
    does not help for your particular problem, i'm afraid.

    Regards,

    Spath.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  9. #9
    The Owl
    Guest
    this was written a while ago, hopefully everyone will find something useful in it.

    [pre]
    1.1 RSA basics


    RSA is a public key encryption system based on the arithmetics of
    (large) integers. in this system a message is represented as a series of
    large (but finite) integers, and the encrpytion/decryption process will
    eventually transmit these numbers. since each of these integers goes
    through the same process (think of it as a block cipher with larger than
    usual blocks), let's discuss what happens with one such message block.


    the basic insight of RSA is that Euler's theorem can be put to use in a
    public key system. the theorem states the following:


    (1.1) m^phi(n) = 1 mod n


    where 'm' and 'n' are integers, 0 <= m < n, gcd(m,n) = 1 and phi(n) is
    Euler's function (giving the number of integers relative prime to 'n',
    i.e. for a prime 'p': phi(p) = p-1).


    Fermat's little theorem is the special case of Euler's for n = p where
    'p' is a prime:


    (1.2) m^(p-1) = 1 mod p


    from Euler's theorem we can derive the following:


    (1.3) m^(phi(n)+1) = m mod n


    as we can see, modulo exponentiation will be a no-op when a very
    specific exponent is used (in other words, the exponent in mod n
    arithmetics can be reduced mod phi(n)) and this is exactly what a full
    cycle of RSA encryption and decryption does. namely, both of these
    operations perform a modulo exponentiation (with encryption exponent 'e'
    and decryption exponent 'd') as is shown below:


    (1.4) m^e = c mod n


    ('c' is the ciphertext and is eventually transmitted to the receiver)


    (1.5) c^d = m^(e*d) = m mod n


    the condition to make this whole scheme to work is that


    (1.6) e*d = 1 mod phi(n)


    the rest of the RSA scheme is about the choice for 'n' so that 'e' and
    'd' can be chosen/computed in an efficient way (by the sender of course)
    and to allow all possible messages to be encrypted (remember, Euler's
    theorem required gcd(m,n) = 1). as it turns out, if we choose 'n' to be
    a product of two primes 'p' and 'q', and 'e' such that gcd(e,phi(n)) = 1
    then all the above equations will work as expected. in this case:


    (1.7) phi(n) = phi(p*q) = (p-1)*(q-1).


    and either of 'd' or 'e' can be randomly chosen and the other computed
    from (1.6). in practice, we place certain restrictions on them in order
    to deter some attacks and make computations fast.
    [/pre]
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  10. #10
    The Owl
    Guest
    [pre]
    1.2 some observations regarding RSA and mod n arithmetics


    the security of RSA is not known (no mathematical proof exists either
    pro or contra), all we know is that our current knowledge is not
    sufficient to determine


    'm' from (1.4) (modulo n e'th root problem)
    'm' from (1.5) without knowing 'd'
    'd' from (1.6) without knowing phi(n)
    phi(n) from (1.7) without knowing 'p' and 'q'
    'p' and 'q' without factorizing 'n'


    for a sufficiently large 'n' (recommended minimum is 1024 bits, 2048 and
    up are desired). in summary, the security of RSA seems to be based on
    the intracktability of the modulo n root and the integer factorization
    problems.


    it is interesting to see from a more practical point of view where RSA
    (and mod n arithmetics in general) gets its security from. consider


    (1.8) x^y = z mod n


    which is equivalent to


    (1.9) x^y = k*n + z


    for some integer 'k'. in plain english it means that we LOSE information
    (the value of 'k') when we perform the mod n reduction. the more this
    information is (the higher the possible range for 'k' is) the harder it
    will be to reconstruct 'k' (which is what we will eventually perform if
    we manage to solve (1.8) for one of its variables).


    for the mathematically challenged reader here is a more visual approach:
    imagine the function f(x) = x^y in the x-y plane (for some fixed 'y').
    the curve looks like a parabola. if we consider integer values for 'x'
    only, we will get a series of dots along the curve, like a necklace. we
    notice that the larger 'x' is the further the dots are from each other.
    now, imagine what happens if reduce f(x) mod n: our necklace breaks down
    into smaller parts and these parts will slip down to the 'x' axis along
    the 'y' one. the 'length' of these parts decreases as 'x' increases, but
    for 'small' values one can actually recognize the arcs of the original
    curve (the larger 'n' is compared to 'y' the better the effect is).
    however, as soon as f(x+1) - f(x) becomes larger than 'n' itself we
    arrive at what best can be described as chaos and that is what makes
    mod n arithmetics based algorithms intracktable (at least these days).
    [/pre]
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  11. #11
    DinDon
    Guest
    Thanks, TheOwl (and Spath), for your lucid explanations in a rather obscure matter.

    I have spent some hours until now playing with BC.EXE, giant integer libraries and 64-digits numbers (and I forgot to poll the forum in the last days :-))

    Aaargh! How can I disable that stupid yellow face??? The backslash in front of the ASCII characters of the emotion does not work!

    Cheers.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

Similar Threads

  1. FlexLM keygenning question
    By john in forum Advanced Reversing and Programming
    Replies: 3
    Last Post: April 26th, 2014, 09:51
  2. Help doing inline keygenning....
    By EJ12N in forum The Newbie Forum
    Replies: 9
    Last Post: May 7th, 2004, 14:20
  3. Struck in keygenning
    By hell in forum The Newbie Forum
    Replies: 2
    Last Post: March 19th, 2004, 01:51
  4. Finding RSA Constants for keygenning...
    By foxthree in forum RCE Cryptographics
    Replies: 3
    Last Post: April 12th, 2002, 09:45
  5. Advanced RSA, ECC and crypto keygenning...
    By x30n- in forum Advanced Reversing and Programming
    Replies: 6
    Last Post: January 19th, 2001, 12:49

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
  •