The relationship between a private and public key?

Question

It's known that the relationship between public and private key allows data encrypted by the public key to be decrypted only by the corresponding private key.

As I understand it, this means that normally there is a relation between them (regarding obtain one from the other).

But I found this:

It is almost impossible to obtain the private key from the public key.

My question is how a private key can decrypt data encrypted with a public key, without it being possible to obtain the private key from the public key, since there has to be a relationship between them for decryption to work?

Answer 1

We'll assume RSA rather than elliptic curve, just because it's simpler.

A key consists of a modulus and an exponent. Both the public and private key use the same modulus, what differs is the exponent. To encrypt (or decrypt) you take your message, raise it to the power of the exponent, divide the modulus, and the remainder is your encrypted (or decrypted) answer.

How to generate your key

You start with two random prime numbers ("p" and "q"), if you have a 2048-bit key, then P and Q are both 1024 bits long. You multiply them together; that's your "modulus" -- the unique part of your public key. The other part of your public key (the "exponent") doesn't need to be unique, but it should be prime; most people just use 65537 because it's safe enough, and it makes your implementation fast.

Now let's figure out the corresponding private key. All you need to do is find the modulo multiplicative inverse of your public exponent with respect to (p-1) times (q-1). The math is simple, but not important here; it's just a simple calculation. That result you get, that's your private exponent; that's the "secret" part about your private key. You're done with P and Q now, throw 'em away.

So encrypt/decrypt a value: raise the value to either your public exponent or private exponent, divide by your modulus (same modulus for both keys) and the remainder is your answer.

Now let's try to attack it

I have the public key (which consists of the number 65537 as well as the modulus (P * Q) and what I'm trying to figure out is the number derived from (P-1) * (Q-1). If I knew what P and Q were, that would be dead-simple. But I don't. Instead, I know what P * Q is.

This is why people say that breaking RSA just boils down to factoring large numbers. Because if I could factor P * Q into P and Q, then I could re-derive the private key.

How are the keys related

The link between the two is this multiplicative inverse thing; it's like how 2 is linked to 1/2 and 13 is linked to 1/13. One can undo the other. Except that the relationship only exists in this finite field defined by the modulus. This is that wrap-around math world which is a lot like dealing with time on a clock -- where 10 plus 3 is 1 instead of 13 (because the clock only goes up to 12).

So to calculate that inverse relationship directly from the public key, you'd end up having to try to compute it over and over, with 1 trip around the clock, two trips, three, and so on until you got an answer that works. This turns out taking more time than the factoring challenge, so everybody just sticks to factoring.

---

This post contains mild technical inaccuracies mostly for brevity and simplicity. Feel free to leave a comment if you're the type of person who likes to argue on the Internet for fake points, but you will likely be summarily ignored.

Answer 2

Yes that is correct.

Your opinion turns out to be Fact.

Impossible eh!

Absolutely not, It is possible but the time and resource you'd require are ridiculous.That is why they say impossible.

In fact the entire foundation of PKC is based on the notion of Mathematical Difficulty of finding the one if you have other. So its difficult on mathematical level not impossible, yet impossible on practical application. For example RSA is a PKC standard, you take two prime factors of a ridiculously long number. One who understands prime number you'd also understand that it is difficult to find the other if you have one prime and result of those two but not impossible ...mathematically. In practice, you have relatively negligible amount of time than required and that's why its impossible.

N.B. You simply cannot derive Public/Private key with just Private/Public key. You at least need two ingredients out of three. (I presumed one as you didn't mention)

Answer 3

Your definitions are slightly backwards. Data is encrypted using a public key, and decrypted with that corresponding private key. IE if I had your pubkey, I could create a message that only you (not even myself, unless I included my pubkey as well) would be able to decrypt using your private key.

My understanding of the relationship between the two is that they are mathematically-linked, although not derivable from each other.

Conversely, data can be signed using your private key, and subsequently verified by anyone with your corresponding public key.

EDIT: https://en.wikipedia.org/wiki/Public-key_cryptography

Answer 4

There is a relationship - a highly (for me) mathematical one.

As for the reason as to why it is practically impossible to recover one without the other, you can think of them both as prime numbers A and B, each of them very large (think thousands of digits each). Their product, C, is then much larger and has A and B as its only factors.

If you give C to someone, I bet you they wouldn't be able to factor it and find A and B. So yeah, in Public-Key Cryptography, you could say that your message is multiplied (encrypt) in a way that it is almost impossible to factor (decrypt) it.

Crude explanation, but worked for me.

Answer 5

The relationship between them works the other way round.

Usually, you can calculate the public key from the private key. Sometimes, both parts are calculated from a common seed value (which is discarded after the key generation).