RSA Digital signatures vs "encryption with the private key"

Question

I found this statement

In RSA crypto, when you generate a key pair, it's completely arbitrary which one you choose to be the public key, and which is the private key. If you encrypt with one, you can decrypt with the other - it works in both directions.

in this question from StackOverflow. I would like to prove myself that this statement is true by actually trying it myself.

I have GnuPG 1.4.16 installed on my linux. I made two keys in pubring:

/home/alex/.gnupg/pubring.gpg
-----------------------------
pub   2048R/0FDEC709 2017-08-11
uid                  alice <alice@mail.com>
sub   2048R/8B76560E 2017-08-11  

pub   2048R/E500C1B1 2017-08-11
uid                  bob__ <bob@mail.com>
sub   2048R/B9D82FDE 2017-08-11

If I want Alice to send message to Bob I encrypt message like so:

gpg --output message.encrypted --encrypt --recipient bob@mail.com message.plaintext

If I want Bob to decrypt message received from Alice using his private key I type:

gpg --output message.decrypted --decrypt message.encrypted

after which Bob is prompted for passphrase and if it's correct message is decrepted.

Here, I assume gpg handles selecting Bob's public key when encrypting and using Bob's private key for decrypting, because I don't spesify that information myself. (If I am wrong with my assumptions/understanding of how gpg works - please let me know, I am new to it).

Now, I want Alice to send message to Bob again, but this time I want to use Alice's private key to encrypt, and then I want Bob to use Alice's public key to decrypt.

Question(s)

• What commands or what parameters should I pass to gpg to achieve that?
• Can GnuPG even allow me to do this? Should I use some other program?

Note: I am not trying to --sign that message. I am trying to prove to myself whether quote at the top of question is true or false, and that quote says nothing about signing.

A little bit of background of how I got here

I was trying to understand how RSA/public key/private key "stuff" works. I discovered that there is misunderstanding going on in this area in community. A lot of people say "signing is the same as encrypting with private key". I do not know how RSA internally implement things, and reading and understanding this will take me months, if not years, probably. Nevertheless, after reading this, this, this, this, this, this, this I find answers like this, this, this, this confusing. So far everywhere I looked I only saw people talking, but haven't seen somebody provide concrete example. If this is duplicate - let me know, I will remove this question. Also, I might be asking the wrong question, but I am here to find out.

Edit 1

Using this website you can generate public and private keys and try to encrypt/decrypt some message. If you do it the proper way (encrypt with public, decrypt with private) it works. But if you do it the other way around - it does not work. Which means a few things to me:

• it's a bug in javascript library

• quote at the beginning of this question is false

• there is some if statement in javascript library that says something like _{(it's a "jQuery pseudocode", hopefully you know what I mean)}

  if($('#privatekey').value.contains('public') { return false; }

  which is meant to restrict people like me from even trying to decrypt messages with public keys.

• it's non-intentional bug not in library itself, but in how it was used

Any other reasons?

But I am not worried too much about this website not doing it. I was looking into established program (or even just library) that can achieve what I was describing.

The javascript library used in that website appears to be kbpgp.

Notes

I did diff of encryption and decryption primitives vs signature and verification primitives from this text. Here is a link to diff. It appears that they are a "mirror image" of one another. What message in encryption is what signature in verification, and what ciphertext in decryption is what message in signing. As I understood that is what being called Raw RSA in this answer. But another thing this answer also states is that

It is often mentioned that signing is equivalent to RSA encrypting (the hash over) the message using the private key. This is only true if you disregard the required padding mechanism. The RSA padding mechanisms are different for encryption and signing.

By taking a quick look at padding (which is described in chapter 7 for encryption and chapter 9 for signing), description of padding indeed looks different for both encryption and signing (but I want to/have to look more into it). Which kind of narrows down my question to finding out whether padding implementation of encryption (aka. RSAES-OAEP or RSAES-PKCS1-v1_5) will allow me to encrypt with private key, and decrypt with public key safely, producing original message.

Answer 1

That statement regarding the key pairs is dangerously false. The public and private keys are mathematically related, and the public key is computed from the private key using the trap door function, meaning it's easy to compute the public key from the private key, but not the other way around. If you share the private key, an attacker could use it to calculate the public key, leaving your cryptosystem broken.

Answer 2

First, PGP is a bad place to look. Not only does it use different paddings for RSA encryption and signing as it should (and nearly everyone does) making the RSA operations themselves different, it handles variable size and possibly large messages using hybrid cryptography (as nearly everyone does). Thus encrypting a PGP message to an RSA key doesn't RSA-encrypt the message; it encrypts the message with a symmetric algorithm and a nonce key, and then RSA-encrypts only the nonce key. (This also covers an important use case for email, sending one message to multiple recipients; the large message is symmetric-encrypted only once, while the small nonce key is PK-encrypted separately for each recipient.) Signing a PGP message actually computes a hash of the message and RSA-signs that hash. And the format of an encrypted message is different from the format of a signed message, which are both different from the format of a clear message.

Second, I don't see how you can believe that RSA encryption and decryption works using m^ed mod n and signing and verifying works using r^de mod n but not believe ed = de (in Z, as mathematicians call the ring of integers) -- I learned that in about fifth grade IIRC.

But if you still need to see this, OpenSSL's commandline operation rsautl does support raw (and pure) RSA. You need the keypair (see more below) in one of the several PEM formats supported by OpenSSL, and a 'message' file which is exactly the bitsize of the modulus and numerically less -- since RSA moduli are usually chosen to be a 'nice' size like 512 1024 2048 bits (512 is probably fine for your example since you don't want security) it is enough if the top bit of the first byte of your message is zero, which is the case for all ASCII characters. Then:

$ xxd se167298.msg
0000000: 5945 5352 5341 4d41 5448 574f 524b 5342  YESRSAMATHWORKSB
0000010: 4f54 4857 4159 5331 3233 3435 3637 3839  OTHWAYS123456789
0000020: 3031 3233 3435 3637 3839 3031 3233 3435  0123456789012345
0000030: 3637 3839 3031 3233 3435 3637 3839 3031  6789012345678901

$ openssl rsautl -encrypt -raw -inkey se167298.key <se167298.msg >se167298.1
$ xxd se167298.1 # m^e
0000000: 3c10 98ee 4740 6791 b9e9 48b6 8474 0999  <...G@g...H..t..
0000010: f9bc 0b6d 83c6 3f6b d5c0 deab 1802 af8b  ...m..?k........
0000020: cd08 9541 45a2 57cc 8986 a434 28c8 f5b2  ...AE.W....4(...
0000030: fc28 ad74 2710 d8c8 724e 3c19 7d72 28af  .(.t'...rN<.}r(.
$ openssl rsautl -decrypt -raw -inkey se167298.key <se167298.1;echo # m^ed
YESRSAMATHWORKSBOTHWAYS12345678901234567890123456789012345678901
$ openssl rsautl -sign -raw -inkey se167298.key <se167298.1;echo # m^ed 
YESRSAMATHWORKSBOTHWAYS12345678901234567890123456789012345678901

$ openssl rsautl -sign -raw -inkey se167298.key <se167298.msg >se167298.2
$ xxd se167298.2 # m^d 
0000000: 85a1 8e07 f98a fbc6 2ce7 86b8 8d47 7a1a  ........,....Gz.
0000010: 1ad1 11e4 b8cf 969e 999c 4f33 b8ec f1a4  ..........O3....
0000020: a1c6 9e4f 482a 390d 138c 8994 47bb 6581  ...OH*9.....G.e.
0000030: 4042 c6d4 7437 249b 4d1e 9882 c1bb bbc4  @B..t7$.M.......
$ openssl rsautl -verify -raw -inkey se167298.key <se167298.2;echo # m^de 
YESRSAMATHWORKSBOTHWAYS12345678901234567890123456789012345678901
$ openssl rsautl -encrypt -raw -inkey se167298.key <se167298.2;echo # m^de
YESRSAMATHWORKSBOTHWAYS12345678901234567890123456789012345678901

One thing I glossed over: in addition to the more subtle flaws of raw RSA, swapping d and e is not secure at all if e is small, but small e is more efficient and practically all implementations for the last 30 years or so (including openssl) choose small e precisely because we never want to swap. Thus you'll need to do key generation more like the method of the original CACM paper: choose d randomly (and thus at least half the size of pq with overwhelming probability) but coprime to phi(pq)=(p-1)x(q-1) and compute e as its multiplicative inverse mod phi -- or equally good, though they only mention it, mod lambda(pq)=lcm(p-1,q-1) -- or at least choose random large coprime e and compute d as its inverse in the modern fashion. I leave that part to you.

Answer 3

In RSA crypto, when you generate a key pair, it's completely arbitrary which one you choose to be the public key, and which is the private key. If you encrypt with one, you can decrypt with the other - it works in both directions.

I would like to prove myself that this statement is true

The statement is true only in a very narrow sense: an RSA key pair includes a public exponent e and its modular inverse (mod phi(N)), the private exponent d. Of course e is also the modular inverse (mod phi(N)) of d. So given particular values of e and d, the purely mathematical operations of RSA will work whether you call one of those values or the other e.

You can easily verify this, but not by using the method you suggested. Instead, generate an RSA key pair using OpenSSL or any similar package, and extract the values of e, d and the modulus N. Then perform RSA mathematical calculations to convince yourself of the interchangability of d and e, using some number m < N such as: (m^d)^e (mod N) = (m^e)^d (mod N) = m

However in any practical setting you cannot, and must not, swap the Private and Public keys. Most obviously, in practical RSA implementations the value of the public exponent e is fixed at a small constant, typically 65537. By swapping e and d you expose what is actually meant to be secret (d), and leave the attacker to guess something trivial (e).

Beyond that, the same mathematical operations involving Public and Private Keys are used for completely different purposes. In practical schemes they have different padding and other usage differences. "Textbook RSA" ignores such considerations, and as a result is known to be insecure.

For example, raising "plaintext" to the power of the key (mod N) is used in both Encryption (when the key is the Public Key) and Signing (when the key is the Private Key). However, the padding is different in practice.

Furthermore, in practice a Signature is calculated over the hash of the input, and Encryption is usually of a symmetric encryption key rather than of the input. So you will not be able to test the veracity of the above statement using a Signing/Encryption package directly.

I hope that explains why the above statement is in fact highly misleading.