Can an altered RSA private key still work as the original?

Question

I am interested in understanding public-key encryption using RSA. On the Khan Academy website, I noticed an anomaly when testing out the tutorial.

I created the following public/private keys:

-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCYIpH5BT9+1MPf+xqI7khDJZmhMLVltXPf0JJY0mk3gXMQtOar
IocOlKmtWDhz+24KZHa6LuK6edpehKoBjdlhGf1GK+IwSR2uc9TnduuaDB2ETByZ
ZA/4Cbdcw9uroeF2IQV9/MNBUJsV8WHDzMefEhf3cVgdIvhw4IUjbCcOlwIDAQAB
AoGAfzEn6ZJBq8AmozRE0wak076z2tfmUMqLviuarzf7T7Sihu03jQyo7b/MvGht
ikpDjdzAhph8ZntJ3ov7tqDpg8Cm/Un/JvTfk1TGvR5okD2qX0Ww0143+oPC7EWC
1HNq+fcls80mr9XtH0fsPSByBxSOyn7nkdCqDxgiNYVMogECQQDfvMhdTmnpSyT6
9b/4RUHF5ggh+WHagpUL7mUNmeMkBYVyegLtXy2Vy6idVeW6Noaa7Ga1H5sdFDcf
ZdDidexhAkEArhKZ6Q6rG22ULeHfvipU9LiaGpaFstbLCI/RItfrmPXuDjIr6wxU
CQTHMrnzBQCrl0ANg0jp0eGJGNd+Tzkd9wJAOoxuamxgrtopPTseF1wYUC9YJXvb
LZFKa6rg6uRAWmbPexuOtItZpH99Cl82FLq8EsKWRgOVVdC6dA7y0LBHQQJBAIMW
ywVx4HW1XeP3uBFzu6rX4mWneWQm0ZvPAoYk6O22NuJF8kD+dcKc8I5I7rSTvqUW
vZZisIM4P5CPqDVtJB0CQCuh0H2k4nb1MYbgpRmEELDhtNBE6canR/DM8G8M0V7J
BXH1XyyzVP/nxNYH7wyAZlBgCPbMYGLIWDT2EojBgZI=
-----END RSA PRIVATE KEY-----

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCYIpH5BT9+1MPf+xqI7khDJZmh
MLVltXPf0JJY0mk3gXMQtOarIocOlKmtWDhz+24KZHa6LuK6edpehKoBjdlhGf1G
K+IwSR2uc9TnduuaDB2ETByZZA/4Cbdcw9uroeF2IQV9/MNBUJsV8WHDzMefEhf3
cVgdIvhw4IUjbCcOlwIDAQAB
-----END PUBLIC KEY-----

My secret message was Hey What's up dafpunk.

So, I encrypted the above message using the public key, which looks like this:

KBevdNKidVNPFufMxVQ9o3Roq+NeieEEo7KjPyJaeQ01uRtosJ6SeXb72Hola/3DegYLgXiVBvbgIQupmcbNH2xw0GfwQ1NZpLPypuJnYgZQC2oH/OtKKmChA+EHnbFQeIo+zGIJpmD3+mTLwtE6v3ZCAcQrDdAb8CEZ/wd27pQ=

When I tried to decrypt the message using the private key, I got the expected Hey What's up dafpunk. This can be verified in the tutorial's web plugin.

But when I changed four values in the private key, the secret message still was decrypted. I didn't think the private key could be allowed to be changed and the secret message to be decoded. What gives?

Here is an example of the change (it's a bit hard to see so I spaced out the change to be more obvious). You can compare it with the actual private key to verify the length is the same as long as you remove the added spaces near the asdf change.

-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCYIpH5BT9+1MPf+xqI7khDJZmhMLVltXPf0JJY0mk3gXMQtOar
IocOlKmtWDhz+ asdf Ha6LuK6edpehKoBjdlhGf1GK+IwSR2uc9TnduuaDB2ETByZ
ZA/4Cbdcw9uroeF2IQV9/MNBUJsV8WHDzMefEhf3cVgdIvhw4IUjbCcOlwIDAQAB
AoGAfzEn6ZJBq8AmozRE0wak076z2tfmUMqLviuarzf7T7Sihu03jQyo7b/MvGht
ikpDjdzAhph8ZntJ3ov7tqDpg8Cm/Un/JvTfk1TGvR5okD2qX0Ww0143+oPC7EWC
1HNq+fcls80mr9XtH0fsPSByBxSOyn7nkdCqDxgiNYVMogECQQDfvMhdTmnpSyT6
9b/4RUHF5ggh+WHagpUL7mUNmeMkBYVyegLtXy2Vy6idVeW6Noaa7Ga1H5sdFDcf
ZdDidexhAkEArhKZ6Q6rG22ULeHfvipU9LiaGpaFstbLCI/RItfrmPXuDjIr6wxU
CQTHMrnzBQCrl0ANg0jp0eGJGNd+Tzkd9wJAOoxuamxgrtopPTseF1wYUC9YJXvb
LZFKa6rg6uRAWmbPexuOtItZpH99Cl82FLq8EsKWRgOVVdC6dA7y0LBHQQJBAIMW
ywVx4HW1XeP3uBFzu6rX4mWneWQm0ZvPAoYk6O22NuJF8kD+dcKc8I5I7rSTvqUW
vZZisIM4P5CPqDVtJB0CQCuh0H2k4nb1MYbgpRmEELDhtNBE6canR/DM8G8M0V7J
BXH1XyyzVP/nxNYH7wyAZlBgCPbMYGLIWDT2EojBgZI=
-----END RSA PRIVATE KEY-----

That change does nothing to the pub/private protocol, which is concerning. What am I missing?

Answer 1

I would be surprised that a proper system will work with this;

1. It fails in openssl check.

    openssl rsa -in sample_rsa_prv_mod.key -check RSA key 
    error: n does not equal p q

2. If you look at an ASN1 parser like ASN.1 JavaScript decoder you will see that your modifications change the modulus. Why the rest didn't corrupt, since the ASN.1 format uses delimiters.

The modulus is not correct. The Khan Academy provides no warning about this i.e. doesn't check as OpenSSL and this implies not a good library. Their implementation may use CRT and from the modulus with $n = p \cdot q$. This is the only plausible explanation since I've tested for some other plaintexts, too.

How the OpenSSL command line behaves with these two private keys;

$cat input.txt
1234567890

$ openssl rsautl -encrypt -pubin -inkey sample_rsa_pub.key -in input.txt

$ openssl rsautl -decrypt -inkey sample_rsa_prv.key -in encrypted.txt
1234567890

$ openssl rsautl -decrypt -inkey sample_rsa_prv_mod.key -in encrypted.txt
RSA operation error
140083785925952:error:0407109F:rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error:../crypto/rsa/rsa_pk1.c:251:
140083785925952:error:04065072:rsa routines:rsa_ossl_private_decrypt:padding check failed:../crypto/rsa/rsa_ossl.c:491:

As we can see, it fails to decrypt. So, the only plausible explanation is again they construct the $n$ from $p$ and $q$. They don't use $n$ in the file.

---

Note: They use various sources in their JS and probably one fails on their usage.

---

Textbook RSA little 101

1. Select target security $t$, today $t> 2048$
2. Select public exponent $e$, $e= \{3, 5, 17, 257,65537\}$ are possible candidates;
3. Generate two unifrom random prime $p$ and $q$ where each has 1024-bit
4. Form the modulus $n = p \cdot q$
5. Calculate Euler's totient function $\phi(n) = (p-1)\cdot(q-1)$ ( Actually use Carmichael Function $\lambda(n) = \text{LCM}(p-1,q-1)$ that can produce shorter private exponent $d$)
6. Check $\gcd(e,\phi(n))=1$, if not 1 return to step 3.
7. Find $d$ with Ext-GCD such that $e \cdot d = 1 \bmod \phi n$.
8. Publish the public key as the pair $(n,e)$, the RSA modulus, and the public exponent.
9. Keep secret the private key $(n,e,d,p,q)$ ( possible more: $n,e,d, p, q, d_p,d_q,d_{inv}$. The values $d_p,d_q,d_{inv}$ are used for CRT based calculation that can speed up modular exponentiation up to 4-time s)

Now encrypt a message $m$ as $c = m^e \bmod n$ and decrypt with $m = c^d \bmod n$.

TextBook RSA as the name suggests should never be used in practice. If you want to use RSA to encrypt some small messages use PKCS#1 v1.5 or OAEP padding to mitigate the attacks, see 20 years of RSA.

If you want to use RSA for signature, use it with PSS padding.

Today RSA mostly used in signatures. For encryption, we prefer hybrid-cryptosystem like key exchange with DHKE (better the ephemeral elliptic curve version ECHKE) and encrypt with authenticated encryption modes like AES-GCM(-SIV) and ChaCha20-Poly1305. It is possible to use RSA-KEM to send the key, too.

Answer 2

Let's start with a quick recap of how the RSA cryptosystem works.

Essentially, RSA encryption is based on encoding the message as number $m$ and raising that number to some odd power $e$ modulo the product $n$ of two large randomly chosen prime numbers $p$ and $q$. This operation is easy to carry out and in principle reversible, but as far as we know, there's no easy way to compute the reverse operation unless we know the prime factors of the modulus. (In fact, the easiest known general way to do that involves first factoring the modulus, for which there is also no known easy way.)

However, if we do know the factors $p$ and $q$ of the modulus $n$, then we can easily find a number $d$ such that $ed \equiv 1$ both modulo $p-1$ and modulo $q-1$. And this turns out to imply that $m^{ed} \equiv m$ modulo $n$, so reversing the encryption is as easy as raising the encrypted message $c = m^e \bmod n$ to the $d$-th power modulo $n$ (and then decoding the resulting number $m = c^d \bmod n$ back to the message).

It also turns out that if one does know the factors $p$ and $q$, there are various mathematical shortcuts (such as the Chinese remainder theorem) that one can use to make the decryption process even faster than simply raising the ciphertext $c$ to the $d$-th power modulo $n$. These shortcuts can't be used for RSA encryption (since they require knowing the factors, and knowing the factors would allow anyone to decrypt as well as encrypt messages), but fortunately RSA encryption is generally faster than decryption anyway, since we can safely choose the public exponent $e$ to be a small number with a simple form in binary (most commonly a small Fermat prime such as 3 or 65537 = 2¹⁶ + 1), which simplifies the math.

---

Now, the quick recap above skips over a lot of important details, like the fact that the way in which the message is encoded ("padded") into a number matters and the fact that, for practical reasons, the "message" is in fact usually an encryption key for some symmetric cryptosystem like AES that is used to encrypt the actual message. And it doesn't even touch on the fact that the same mathematical property can also be used to construct digital signatures, with a "message" $m$ (usually actually a padded cryptographic hash) yielding a signature $s = m^d \bmod n$ that can be verified by computing $m = s^e \bmod n$.

But the upshot of all this is that RSA public keys are pretty simple, containing the only two things that are needed for encryption (or for signature verification) and that can be safely published: the modulus $n$ and the public exponent $e$. If you change either of those, the encryption process will change, and the resulting encrypted messages will no longer decrypt correctly with the original key.

But RSA private keys typically contain a bunch of other redundant values too, since they can and since knowing those values can simplify the math and make decryption faster. In particular, RSA keys in the PKCS #1 format (which is what you have here) typically contain:

• the modulus $n = pq$ (same as in the public key),
• the public exponent $e$ (also same as in the public key),
• the private exponent $d$,
• the factors $p$ and $q$ of the modulus,
• the "reduced private exponents" $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$, and
• the "CRT coefficient" $q_{\rm inv}$, i.e. the modular multiplicative inverse of $q$ modulo $p$.

(Not all of those number will be the same length. When we speak of the size of an RSA key, what we usually mean is the size of the modulus $n$, so e.g. a 1024 bit RSA key will have a 1024 bit $n$. The private exponent $d$ will also normally be the same length or literally a bit shorter, while the rest of the numbers except for $e$ will typically be about half as long; i.e. around 512 bits each for a 1024 bit key. The $e$ value is typically short, up to 17 bits for $e = 65537$.)

Now, most of those values are actually redundant: in particular, just knowing $p$, $q$ and $e$ (or $d$) is enough to calculate all the others (and so is knowing $n$, $d$ and $e$, since knowing both $d$ and $e$ is enough to factor $n$). But having all the values precalculated in the private key file can save some time when using the key for decryption (or signing), since the extra values don't need to be recalculated each time.

But that also means that most RSA implementations won't actually use all the values in the private key file. In particular, most RSA implementations using the CRT (Chinese remainder theorem) won't actually use the $n$ or $d$ values in the key file for decryption, since they don't need them. And conversely, any implementations that use straight modular exponentiation will generally only use $n$ and $d$ and ignore the rest. And the $e$ value in the private key file is pretty much useless for anything except recalculating the public key if you need to, but since it's a small number that only takes a byte or two, including it doesn't really cost anything either.

---

So basically, if you chance a couple of consecutive random bytes in the encoded RSA private key file, you'll most likely end up changing only one of the numbers contained in the file. If it happens to be one of the numbers actually used by your RSA decryption (or signing) code, then that will mess up the results — but if it's not, then the program will most likely not even notice the change (unless it deliberately validates they keyfile, which costs extra time and effort).