1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ The question boils down to: I altered a private key slightly, why does it still works? This has nothing to do with the title. $\endgroup$ – fgrieu Feb 20 at 16:11
  • $\begingroup$ I can update the title per your suggestion. Are you suggesting that as the title? I'm new to encryption and in part the question is reflecting my level of familiarity with the subject. $\endgroup$ – LeanMan Feb 21 at 3:23
  • $\begingroup$ Indeed, a better title would be: can an altered RSA private key still work as the original? $\endgroup$ – fgrieu Feb 21 at 8:51
5
$\begingroup$

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
  1. 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 Charmichael 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.

$\endgroup$
5
  • $\begingroup$ Why a library that decrypts even with a corrupted key is not good? :) More to the point, I think openssl indeed uses CRT decryption. $\endgroup$ – Fractalice Feb 20 at 7:37
  • $\begingroup$ @Fractalic yes whenever the necessary parameters are existing OpenSSL uses CRT, however that doesn't mean that it will not provide the error. I will test that. $\endgroup$ – kelalaka Feb 20 at 7:39
  • 1
    $\begingroup$ @Fractalic FYI I've check OpenSSL command line and that fails with the modified private key. $\endgroup$ – kelalaka Feb 20 at 7:59
  • $\begingroup$ I'm sorry I'm new to cryptography. What is a modulus? Could you tell me in laymen terms what you mean? I think you said their implementation is plausibly different than openssl but it may also be a bug. $\endgroup$ – LeanMan Feb 20 at 14:03
  • 1
    $\begingroup$ I wrote a little 101 TextBook RSA, see the update. Yes, they don't check that $ n = p \cdot q$ or not. I don't think that that can cause insecurity, however, it annoys. Well, bug or a feature. Who knows? $\endgroup$ – kelalaka Feb 20 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.