1. ## 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. 2. 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. 3. 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. 4. > 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. 5. 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. 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. ## Thanks

Hi all!
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. 8. > 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. 9. 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] 10. [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] 11. 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. #### Posting Permissions

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