1
$\begingroup$

I know that usually with RSA, you encrypt data using the public key, and decrypt using the private key. Or alternatively, you sign using the private key, and verify the signature using the public key.

Now some years back, I came across an unusual scheme: Data is encrypted using a private key (on a server), and decrypted using a public key (obfuscated and embedded in a client).

Are there any specific cryptographic weaknesses to this approach? For example, if I have some pairs of (plaintext, encrypted data), is it possible to derive the public key (without de-obfuscating the source)? Or if I do have the public key in addition to some pairs of data, is it possible to derive the private key?

In this case, the public key exponent is around $2^{124}$, and modulus around $2^{1024}$, for encrypting 128-byte blocks of data.

Edit: It seems like another way to view this is the clients having the private key ($d$ and $n$, without $p$ or $q$), and the server has the public key. Then encryption is done in it's "standard" way using the public key.

In that case, is there any way to derive the "public key" on the server? If one of the standard small values of $e$ were used it should be easy to guess, but I'm not sure if there are any weaknesses if there is a large $e$ here.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Do you have a source for this (e.g. URL, book name, etc.). I think it's some form of signature with message recovery (when signature with appendix is more common nowadays). $\endgroup$
    – DannyNiu
    Commented Jun 7 at 14:25
  • $\begingroup$ @DannyNiu I don't have good info on this, but here is some code that I presume is based on reverse engineering the original client: https://github.com/yushulx/South-Africa-driving-license/blob/main/sadl/__init__.py. The original description of the scheme is here, but doesn't have much info: https://pastebin.com/gb049dfx. $\endgroup$
    – Ralf
    Commented Jun 7 at 15:06
  • 2
    $\begingroup$ No, you cannot switch the public and private key around like you are suggesting at the end of your question. The key pair is generated using a specific way and although both the public exponent and private exponents are used as - well - exponents that doesn't make them identical. I always understood that this is secure if the public exponent is as large as the private exponent, but 1. that might be wrong altogether and 2. your public exponent is much smaller than the private exponent which should also be in the order of 1024 bits. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jun 9 at 2:49
  • $\begingroup$ @MaartenBodewes After reading up more about this, I understand, public and private keys are "symmetrical" - you can switch the two around. $(m^e)^d \equiv m \ (\text{mod} \ n)$, and $(m^d)^e \equiv m \ (\text{mod} \ n)$ - there is no mathematical difference between those two. One big difference comes in if you additionally store the private factors $p$ and $q$ together with the private key, since those could be used to derive both keys. Another practical difference could be the relative size of $e$ vs $d$, which affects performance and level of security. $\endgroup$
    – Ralf
    Commented Jun 10 at 7:42
  • 2
    $\begingroup$ @Ralf: The above misses at least one consideration. If we "switch the public and private keys", then the originally-named-public exponent must be large enough (beside secret). If it's below about $N^{ 0.292}$, and the originally-private key is made public, then the now-secret exponent can be found by this method. $\endgroup$
    – fgrieu ♦
    Commented Jun 10 at 14:15

1 Answer 1

Reset to default
4
+50
$\begingroup$

By Wiener's attack$^1$, RSA becomes completely insecure as soon as $d < n^{1/4}/3$, which is the case in your context (as you use a secret exponent of size $2^{124}$). Some improvements over this attack expand the "danger zone" to larger keys. In general, using small values of $d$ seems ill-advised.

In contrast, as pointed out in the comments, when using a uniformly random large $e$ and $d = e^{-1} \bmod \phi(n)$, exchanging their roles has no impact on the system.

$^1$ See also the Wikipedia page

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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