got P,Q,D, how to compute E?

[prejker]

Hey guys!
I found an app that uses rsa in this way:
if(serial^D mod N == name) { bIsRegged = true; }
My question is how can i compute E so i can generate a good serial?
I know that D = E^(-1) mod ((P-1)*(Q-1)) but dont know how to get E from that ;/
thx for replying

[dELTA]

Are you really sure you have P and Q? That does not make sense, where did you get them from? If you have those, it's very easy to get E and D, but the main idea of asymmetrical cryptos like RSA is that you only get N and one of D and E, from which is it "impossible" (if the bit length is big enough and so on) to calculate the one of D and E that you don't have, the whole security of the RSA crypto system relies on that.

[prejker]

let me correct myself
the app has N, D hardcoded in the serial routine and i've calculated P and Q in rsa-tool.

[dELTA]

Ok, I guess there weren't too many bits in that key after all then...

Well, like you say, simply solve the equation for E (E is the modular inverse of D (mod (p-1)*(q-1)))

Here's an example algo for you:

http://mathforum.org/library/drmath/view/51895.html

For more info, search for "modular inverse" etc...

Also, any decent bignum library will do it automatically for you.

[SheepShagger]

Quote:

[Originally Posted by prejker]I know that D = E^(-1) mod ((P-1)*(Q-1)) but dont know how to get E from that

E = D^(-1) mod ((p-1)(q-1))

is the private key which should be kept well... private (as in don't hardcode it in your program ) That's strike one and two. Strike three is to select small P and Q so that the factorization of N can be done trivially

This is a good example of why the general problem with cryptography is not the algorithm or the protocol but its implementation.

[prejker]

That really helped. thanks guys

[dELTA]

Quote:

is the private key which should be kept well... private (as in don't hardcode it in your program ) That's strike one and two.

Actually, only either D or E is to be kept secret out of , and since D and E are completely symmetrical, it doesn't matter which one of them you put on the "private key" and which one you put in the "public key", or rather, noone can even claim at all to know which one of them is E and which one is D (even though E is the common denomination of the one in the public key, sure, but in that case you can just as well say that it was just a slight deviation from naming conventions in prejker's original post and not a mistake on the application, and ALSO, in the case of a serial check using asymmetrical cryptography, the operation performed in the application is normally indeed a decryption, which is the normal situation to use the key containing D, so you can't even say it's a deviation from naming convention actually).

As for differences between D and E, their relative size is sometimes chosen in a way to optimize the speed of encryption vs decryption/signing, but that's another story...

[SheepShagger]

Sorry, but that's not entirely true. As I mentioned before, the weakest link in cryptography is not the algorithm, or the protocol but the implementation. The devil is always in the details

The RSA algorithm as designed by Rivest, Shamir and Adleman is:

1. Find two large random primes p and q of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits.

2. Compute n = pq and phi = (p-1)(q-1).

3. Select a random integer e, 1 < e < phi, such that gcd(e, phi) = 1

4. Use the extended Euclidean algorithm to compute the unique integer d, 1 < d < phi, such that ed is congruent 1 (mod phi).

5. becomes the public key and the private.

Encryption is achieved by c = m^e mod n and decryption by m = c^d mod n thus the relationship between e and d, in this context, is better defined as bijective rather than symmetrical: ((x^e)^d) is congruent x mod n

Choosing e is not something you approach lightly. Yes, you want a small enough number so computations are performed fast but above all things (this is about security after all) e must not divide neither (p-1) nor (q-1) otherwise your private key can be derived.

e and d shouldn't be used interchangeably because after you derive d you don't know if gcd(d,phi) = 1

As a general rule, always follow the designer's algorithm until the variation you want to implement has been reviewed and approved by the crypto community. Even a small, insignificant, deviation may have undesired interactions that can weaken the system.

I'm sure you (dELTA) are familiar with this paper but for the people following this thread that are not, D. Boneh wrote an interesting paper titled "Twenty years of attacks on the RSA cryptosystem" http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

[mike]

Quote:

[Originally Posted by SheepShagger]e and d shouldn't be used interchangeably because after you derive d you don't know if gcd(d,phi) = 1

Yes, you do! If gcd(e,phi(n))=1, then it's in the group of units mod phi(n). By the definition of a group, each element has an inverse in the group. So d is a unit, and is therefore also comprime to phi(n).

Signing messages is decrypting the hash of a message (i.e. raiseing to the d power mod n). Other people take your public key , encrypt the result, and check the hash to verify.

You choose e small if you want encryption to happen quickly, and d small if you want decryption to happen quickly. There are attacks on the system if e is too small (like 3). See the paper he cited.

[dELTA]

The crypto god has spoken, what can I tell you SheepShagger, I told you so? Also, even if you would have been correct in your statement about the asymmetry between D and E, the statement about which one was D and which one was E would only be according to the arbitrary labeling of prejker anyway, as I said above.

[SheepShagger]

Quote:

[Originally Posted by mike]Yes, you do! If gcd(e,phi(n))=1, then it's in the group of units mod phi(n)

You're correct. I guess the only thing I can use as an excuse for overlooking that fact is the time of the post.

At first, I was concerned that an "untested" d may lead to a solvable linear congruence of the form: de congruent b (mod n). The equation can only be solved if gcd(d,n) > 1 divides b (hence my post), but in my haste I overlooked that e and d are indeed coprimes (shame on me) plus since one is the modular inverse of the other, the linear congruence does not have a solution.

After thinking a bit about the question, I don't see any reason why couldn't be the public key providing that (I'm purposely ignoring any message padding like OEAP):

- Both exponents are of sufficient size to avoid small exponent attacks
- The keys are never interchanged (the public now becomes private)
- e isn't one of the usual values (3, 17, 2^16+1)

... but I've been wrong before and I still believe that a crypto algorithm should be followed as designed unless you fully (a.k.a. mathematically) comprehend the ramifications of the variation. Mike, could you point me to such analysis?

I mean, what's the impact of using RSA as designed except that the public key is ? What happen when n is multi-prime? And when the private key is in the form ?

dELTA, Now I understand your comment about how will he know if it's D or E and agree with your post

[mike]

Quote:

[Originally Posted by SheepShagger]After thinking a bit about the question, I don't see any reason why couldn't be the public key providing that (I'm purposely ignoring any message padding like OEAP): - Both exponents are of sufficient size to avoid small exponent attacks - The keys are never interchanged (the public now becomes private) - e isn't one of the usual values (3, 17, 2^16+1) ... but I've been wrong before and I still believe that a crypto algorithm should be followed as designed unless you fully (a.k.a. mathematically) comprehend the ramifications of the variation. Mike, could you point me to such analysis?

You're right: you should always follow the directions exactly unless you really know what you're doing.

Mathematically, there's no difference between d and e; if you choose one at random, the other is random too. As you noticed, there is a difference in the way they are used, though I don't know of any better analysis than the paper you cited.

[SheepShagger]

Quote:

[Originally Posted by mike]Mathematically, there's no difference between d and e

Well, I spent a couple of hours thinking about this and what I found so far is that e and d share the same mathematical properties so, I will cautiously agree with you and graciously concede it is possible that e and d are interchangeable.

However, I disagree with your statement about d being random. On the contrary, it is very much deterministic (calculated using the extended Euclidian algorithm to find the inverse of a number mod x) but I understand what you're trying to say.

dELTA, a lot of time and thought went into the design of RSA and you wouldn't believe how many crackpots (I'm not suggesting you're one of them ) claim they've discovered a way to factorize large numbers or have made changes to "strengthen" the algorithm so it's just natural that whenever someone suggests deviations from the design, a request for a proof will follow.

Anyway, enough math for today but thanks to you guys am a bit wiser so I'll drink on your honor.

P.S.: Speaking of crackpots, one of my favorites: http://www.timecube.com/

[mike]

Quote:

[Originally Posted by SheepShagger]However, I disagree with your statement about d being random. On the contrary, it is very much deterministic (calculated using the extended Euclidian algorithm to find the inverse of a number mod x) but I understand what you're trying to say.

Yes. Do what I mean