1
$\begingroup$

Cant you look at the algorithm used to encrypt and find the private key from the public key that way? As an example, here's a simple python algorithm that encrypts an input:

rnd.seed(int(pasc))
return [(tran_ltn[content[i]] + rnd.randint(400, 1400)) for i in range(len(content))]

This is obviously symmetric. However, if I wanted to make it so that a different passcode decrypts this output, I could write:

rnd.seed(int(pasc))
pasc = rnd.randint(1, 100000)
rnd.seed(pasc)
return [(tran_ltn[content[i]] + rnd.randint(500, 1500)) for i in range(len(content))]

Suddenly, the same passcode that encrypted, cannot decrypt using the same algorithm it used to, but we can still find the private key from the public key with these lines:

rnd.seed(int(pasc))
pasc = rnd.randint(1, 100000)

What am I missing? Does asymmetric encryption only work if the encryptor does not have access to the encryption algorithm?

$\endgroup$
2
  • $\begingroup$ After seeing all these "clarify the confusion" questions, I'd totally support a policy where we invite askers to provide a link to the source articles, so that we can debunk and ridicule the ones that're horribly written. $\endgroup$
    – DannyNiu
    Mar 14, 2023 at 8:50
  • $\begingroup$ Quick observation: In the 2nd code block, the initial pasc is used to seed the RNG to derive another pasc. This kind of one-way hashing action is indeed incorporated in hash-based digital signature schemes, which is a kind of public-key algorithm (just not encryption). $\endgroup$
    – DannyNiu
    Mar 14, 2023 at 8:57

2 Answers 2

3
$\begingroup$

Cant you look at the algorithm used to encrypt and find the private key from the public key that way?

Welcome to the wonderful (and nonintuitive) world of public key cryptography.

In this world, we can generate a 'public key' and a 'private key'; with the 'public key', we can encrypt a message that can only be decrypted with the 'private key'. And, yes, you can examine the public key and the encryption program all you want; that doesn't tell you how to decrypt (!).

Here is a simple example ("IES") of such a scheme:

  • The public key will consist of a large prime $p$, a smaller value $g$, and the value $pub = g^x \bmod p$ [1], for some secret value $x$.

  • The private key will consist of everything in the public key, and the secret value $x$.

  • To encrypt, you pick a random value $y$ and compute both $g^y \bmod p$ and $pub^y \bmod p$. You then turn the value $pub^y \bmod p$ into a symmetric key (e.g. an AES key), and use it to encrypt your message. You then send the encrypted message and the value $g^y \bmod p$

  • To decrypt, you take the value $g^y \bmod p$ sent by the encryptor, and compute $(g^y \pmod p)^x \bmod p$; this value will happen to be the same as $pub^y \bmod p$; you turn this into a symmetric key (the same key as the encryptor used) and use it to decrypt the encrypted message.

To someone in the middle, he has the public key ($p, g, pub^x \bmod p$), and the ciphertext ($g^y \bmod p$, encrypted message). For a well chosen prime $p$ and value $g$, we don't know how to take that and turn it into the common value $pub^y \bmod p$; even though the decryptor can do it easily.

This is only a sample of public key cryptography; there's a lot more to it.


[1]: What $g^x \bmod p$ means is $g$ multiplied by itself $x$ times, all modulo the prime $p$. This can be practically done, even if $x$ is large, by noticing that we don't actually have to do $x-1$ multiplications by simplifying things, for example, $g^4 \bmod p$ can be performed by 2 multiplications, not 3, by $((g^2 \bmod p)^2 \bmod p)$ - it turns out these sorts of shortcuts allow us to compute everything with $O(\log x)$ multiplications with no internal value becoming larger than $p^2$

$\endgroup$
1
$\begingroup$

In asymmetric encryption, knowledge of the encryption key allows to encrypt, not to decrypt. That's even with full knowledge of the encryption and decryption algorithms†. Contrary to the question's code, the necessary decryption key is not merely hidden in the encryption algorithm; it's jut not there.

This answer to the question sketches how that's possible. That answer to another question uses a slightly different method‡, and comes with working python code and a link to try it online.


† More generally, algorithms are assumed public in modern cryptography unless otherwise stated.

‡ The main difference is that instead of using AES to encrypt the plaintext using $\mathrm{pub}^x\bmod p$ as key, the low-order bits of that value are XORed with the plaintext.

$\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.