# Assymetric Cryptography Question

## wswartzendruber

Is it possible to derive a public key from a private key?  This (odd) scenario of mine depends on the public key remaining secret, while everyone has access to the private key.

----------

## bunder

Moved from Off the Wall to Networking & Security.

----------

## TNorthover

 *wswartzendruber wrote:*   

> Is it possible to derive a public key from a private key?  This (odd) scenario of mine depends on the public key remaining secret, while everyone has access to the private key.

 

Technically it depends on the algorithm. I've just checked for RSA and it's precisely equivalent to finding the private from public key. If you're using a diferent algorithm, I can try to think about that too.

----------

## sts

 *wswartzendruber wrote:*   

> This (odd) scenario of mine depends on the public key remaining secret, while everyone has access to the private key.

 

You're doing it wrong.

----------

## Jake

 *TNorthover wrote:*   

> Technically it depends on the algorithm. I've just checked for RSA and it's precisely equivalent to finding the private from public key. If you're using a diferent algorithm, I can try to think about that too.

 

It's been a while since I looked at RSA in depth, but I think you're right, except for one critical problem. If you have the private key, you have the modulus and can probably assume whatever program generated the key pair chose a convenient public exponent like 65537.

So I'm going to concur with sts. You're doing it wrong, wswartzendruber. What are you actually trying to do?

----------

## TNorthover

 *Jake wrote:*   

> It's been a while since I looked at RSA in depth, but I think you're right, except for one critical problem. If you have the private key, you have the modulus and can probably assume whatever program generated the key pair chose a convenient public exponent like 65537.

 

Yuck, didn't know they did that. That's why muppets like me shouldn't comment on security issues, far too much subtlety.

----------

## wswartzendruber

I'm trying to make something privately encryptable that everyone can decrypt.  Now I read about RSA as well, and supposedly the public and private keys CAN be swapped.

EDIT:  It's for a product key system.  The software vendor has a public key.  They encrypt a hash of the user's e-mail address and that's the product key.  The setup program has a private key.  If the product key and e-mail address entered decrypt and hash out, then the user has a valid key.  You need the public key to make a keygen program (what I'm trying to prevent).

----------

## TNorthover

 *wswartzendruber wrote:*   

> I'm trying to make something privately encryptable that everyone can decrypt.

 

It looks like what you actually want is the ability to sign something. It's included in all the systems I know already.

 *Quote:*   

> Now I read about RSA as well, and supposedly the public and private keys CAN be swapped.

 

At least with gpg, Jake was perfectly correct: the public key is trivially crackable given the private. If anything he should have been rather more emphatic in telling me I was wrong. Don't do it.

----------

## shrndegruv

 *Quote:*   

> 
> 
> Is it possible to derive a public key from a private key?
> 
> 

 

doesn't this defeat the purpose of, um, the security of any scheme based on public/private key crypto?  because if you could do that, you could derive a private key from a public key.  there is no difference between the public and private keys, except one is kept secret and one is public.  when the two are generated, one is picked to be public and the other private, it doesn't matter which is which....

i might not understand the OP question.

----------

## wswartzendruber

 *shrndegruv wrote:*   

>  *Quote:*   
> 
> Is it possible to derive a public key from a private key?
> 
>  
> ...

 

Right, but I need to know that you CAN'T do this.

----------

## shrndegruv

can't do what?  get the private key from the public key?  No you can't, unless:

1: there is a weakness in the implementation you are using.  There are some known issues with some public key implementations.  

2: someone developed a way to factor large numbers.  It is unlikely this has occured.

If you could do that, then these systems would not be secure and noone would use them.

Note that you certainly can encrypt with your private key and then anyone can use your public key to decrypt.  

so you dont want a scheme where your private key is public and your public key is private--just use your private key to encrypt and your public to decrypt.  As previously stated, the only thing that makes the private key private is that that was the part of the pair that was deemed private.

----------

## TNorthover

 *shrndegruv wrote:*   

> 1: there is a weakness in the implementation you are using.
> 
> ...
> 
> As previously stated, the only thing that makes the private key private is that that was the part of the pair that was deemed private.

 

That's really not true. There's an inherent asymmetry in public key cryptography and no mathematical reason to expect encryption and decryption to be the same. As Jake said, in RSA it's common to pick the public key for quick encryption and derive the private key from that. It's not necessarily a weakness provided the system is used as intended.

----------

## shrndegruv

 *Quote:*   

> 
> 
> That's really not true. There's an inherent asymmetry in public key cryptography and no mathematical reason to expect encryption and decryption to be the same. 
> 
> 

 

consider two people communicating using public key crytpo.  UserA has generates two keys, one he keeps private and the other he makes public.  To send UserB a secure message UserA uses his PRIVATE key to encrypt his message.  UserB receives that message and uses UserA's PUBLIC key to decrypt it.  Now lets say UserB wants to send a response.  He uses UserA's PUBLIC key to encrypt the message, and UserA uses his PRIVATE key to decrypt.   So message one is encrypted using hte private key and decrypted using the public key.  message2 is encrypted using the public key and decrypted using the private.  

It doesn't matter which key is used to encrypt, as long as the other is used to decrypt.  

In fact there is every reason to expect encryption and decryption to be the same.  The same mathematical function is applied during encryption and decryption.  THE SAME.  the only thing that changes is the key.  I refer you to

http://en.wikipedia.org/wiki/Rsa#Encryption

 *Quote:*   

> 
> 
> As Jake said, in RSA it's common to pick the public key for quick encryption and derive the private key from that. It's not necessarily a weakness provided the system is used as intended.
> 
> 

 

If you could derive a private key from a public key, which is to say that you could get the other key from one part of the key, then this system would not be secure.  It doesn't make any sense.  whats the point of having a public/private key system if the private key can't be kept private?! I think from reading your sentence you are confusing a combination often used -- the public key encryption of a cipher key.  This is mixing and matching public and private key cryptography (note the namespace collision here: this is NOT the private key of a public/private key pair).  If you are encrypting using a cipher, that cipher depends on a key.  The same key is used to encrypt and decrypt.  the key must obviously be kept secret.  So if userA encrypts a message using a block cipher, and wants userB to read it, he needs to get the key to userB.  He can use a public key system like RSA to encrypt the cipher key.  When userB gets the encrypted cipher key he decrypts it with the public key crypto scheme, and now can use the cipher key to decode the message.

edit

 *Quote:*   

> 
> 
> Public-key cryptography, also known as asymmetric cryptography, is a form of cryptography in which the key used to encrypt a message differs from the key used to decrypt it. In public key cryptography, a user has a pair of cryptographic keys—a public key and a private key. The private key is kept secret, while the public key may be widely distributed. Incoming messages would have been encrypted with the recipient's public key and can only be decrypted with his corresponding private key. The keys are related mathematically, but the private key cannot be practically derived from the public key.
> 
> 

 

from wikipedias entry on public key cryptography.  Note the last sentence.

----------

## TNorthover

 *shrndegruv wrote:*   

> consider two people communicating using public key crytpo.  UserA has generates two keys, one he keeps private and the other he makes public.  To send UserB a secure message UserA uses his PRIVATE key to encrypt his message.

 

Not in public key cryptography, he doesn't. Otherwise anyone in possession of the public key could decrypt one direction of that conversation. What UserA does is use UserB's public key to encrypt his message.

 *Quote:*   

> In fact there is every reason to expect encryption and decryption to be the same.  The same mathematical function is applied during encryption and decryption.  THE SAME.  the only thing that changes is the key.  I refer you to
> 
> http://en.wikipedia.org/wiki/Rsa#Encryption

 

It happens to be the case for RSA, I've never denied that. But there are more public key cryptosystems out there, and there's absolutely no reason to expect the same mathematical function to be used in both cases.

 *Quote:*   

> If you could derive a private key from a public key, which is to say that you could get the other key from one part of the key, then this system would not be secure.

 

What you described isn't secure anyway. You could adapt RSA with your method to give a secure symmetric system (where they have to exchange keys securely). But there are better designed symmetric ciphers already (AES for example).

----------

## shrndegruv

yeah on the UserA and UserB example I wrote I messed up.  But the point I was trying to make was valid -- that is that mathematically speaking there is nothing special about the private key, and furthermore, that you cannot get the private key from the public key.

----------

## TNorthover

 *shrndegruv wrote:*   

> yeah on the UserA and UserB example I wrote I messed up.  But the point I was trying to make was valid -- that is that mathematically speaking there is nothing special about the private key, and furthermore, that you cannot get the private key from the public key.

 

That statement is true for RSA, under certain implementations. It is false for gpg (I checked the code earlier today), probably false for other implementations of RSA, and a ridiculous claim for a general public key cryptosystem.

Specifically, gpg uses either 41 or 65537 by default for the exponent of the public key.

Edit: As a concrete example look at http://en.wikipedia.org/wiki/ElGamal_encryption. Decryption algorithm is completely different to encryption.

----------

## wswartzendruber

So here's what I'm currently planning for:

1. The software vendor encrypts the hash of the customer's name with the product's private key; this becomes that customer's serial number for that software.

2. If the software's installer package can decrypt that serial number and it matches the hash for the customer's name, then that customer is authorized to use said software.

NOTE:  I am absolutely NOT making money from this.

----------

## Hu

What happens if the verification fails?  Does the installer simply refuse to install the program?

I think you are concerned about the wrong aspect of the system.  If this is intended as access control for the installer, it would be far more practical for an attacker to simply disable all the access checking code than for him to try to generate fake keys.

----------

## sts

 *Hu wrote:*   

> If this is intended as access control for the installer, it would be far more practical for an attacker to simply disable all the access checking code than for him to try to generate fake keys.

 

Or they'll just register one copy with a fake name and then distribute the key for everyone else to use.

This seems like an exceptionally bad way to go about this. Why not use one a pre-existing license activation method? They are all ineffective but at least you won't risk a huge security blunder.

----------

## Jake

How is this different from a typical signature verification scenario where the signer keeps the private key private and anyone with the public key can check the signature?

As for Hu's comment about disabling all the checks, I agree, but there are ways to make that more difficult like obfuscating symbol names, jumping around blocks of junk to throw off disassemblers, trying to prevent debuggers from attaching, and utilizing run-time encryption.

And as for sts's way to bypass the registration scheme, you'd either need to factor information about the hardware you're running on into the license check or else use a license client/server model. And/or if you want to be nasty, install bits to unexpected places that serve no purpose other than to be difficult to locate and copy.

----------

## wswartzendruber

 *Jake wrote:*   

> How is this different from a typical signature verification scenario where the signer keeps the private key private and anyone with the public key can check the signature?
> 
> As for Hu's comment about disabling all the checks, I agree, but there are ways to make that more difficult like obfuscating symbol names, jumping around blocks of junk to throw off disassemblers, trying to prevent debuggers from attaching, and utilizing run-time encryption.
> 
> And as for sts's way to bypass the registration scheme, you'd either need to factor information about the hardware you're running on into the license check or else use a license client/server model. And/or if you want to be nasty, install bits to unexpected places that serve no purpose other than to be difficult to locate and copy.

 

No accomplishment worth a damn was ever easy.  People told Thomas Edison over and over again that he'd never invent a usable light bulb.

I intend to find a way to control software installations using completely open methods, to include, completely open code.  Furthermore, I also intend to encrypt the installer's packaged files.  The first goal is coming together.  The second is going to be far more difficult.

EDIT:  Should this not be moved back to OTW, seeing as how this is a .NET project?

----------

## sts

Have you done any research to see if this has already been done? Cryptography is notorious in that new protocols tend to almost always get something wrong. Not to mention you could save a lot of work.

And this probably isn't the best place to ask crypto questions.   :Sad: 

----------

## wswartzendruber

 *sts wrote:*   

> Have you done any research to see if this has already been done?

 

Sounds like this is what I'm looking for:

 *Quote:*   

> The RSA signature schema as described in RFC 2437 [4] and FIPS-186-2 [5] can be used to authenticate the content of a message. As opposed to the scheme described above, this scheme employs an RSA key pair instead of a single secret key. The data is signed using a private key and the signature is verified using a matching public key.

 

----------

