3
$\begingroup$

For what I know from the RSA algorithm, the receiver of an encrpyted message needs the Euler totient to generate its private decryption key. If the sender has chosen two primes p and q, then the Euler totient could be $(p-1)*(q-1)$ which is a value needed for the receiver. In this case, how the Euler totient is shared, because it do not see how the receiver would get that value.

The algorithm is fairly understandable, but I have not found information about if this value is shared or how is this shared?

Thanks

$\endgroup$
0

2 Answers 2

14
$\begingroup$

It's simple: the sender does not choose any primes. The key pair is generated by the receiver, and the sender uses the public key to encrypt the message. As such, the Euler totient is simply calculated at the receiver and the primes never need to be communicated.

When asymmetric cryptography is used, the private key or private components of the key never need to be transported, except if the key is used on multiple related systems or possibly for backup purposes.

The public key must be trusted to come from the receiver to keep the message confidential. Here the various aspects of key management and public key infrastructures (PKI) come into play.

To sign a message the sender does use their own generated key pair, and now it is the receiver that must use and trust the public key of the sender to verify the signature.

$\endgroup$
3
$\begingroup$

No,suppose that Alice will receive messages from Bob, the steps of generating the key are:

Key setup for Alice

  1. Choose $p, q$ random primes of 3072 bits.
  2. Compute $n = pq$.
  3. Compute $φ(n) = (p − 1)(q − 1)$
  4. Choose $e = 65537$, and compute d such that (Euler's totient is used only here) $$ed ≡ 1 \pmod {φ(n)}$$
  5. public key: $(n, e)$; private key $(d)$

No need to setup a key for Bob. Bob will get the public key and do the following computation: $c = m^e \pmod{n} $

$c$ is the ciphered message to be sent to Alice.

Alice will use: $m = c^d \pmod{n}$ and recover the plain text message.

Some concerns about security of RSA (Understanding Cryptography, Paar):

Theorem The following three computational problems are equivalent:

  1. Factoring RSA modulus: Given n, find p and q such than $n = pq$.
  2. Finding φ: Given n, find φ(n).
  3. Finding d: Given n and e, find d.
$\endgroup$
4
  • 2
    $\begingroup$ Actually, in practicem first the $e$ is chosen then the random primes are tested. In your case, one may still need to choose another $e$, too. $\endgroup$
    – kelalaka
    Jul 10, 2022 at 19:48
  • $\begingroup$ "Bob will grab the public key" ... no, Bob should not just grab the public key as the public key needs to be trusted. I understand your reasoning and probably "grab" is just there to indicate that the public key needs to be transported somehow, but the "trust" part is fundamental to security. $\endgroup$
    – Maarten Bodewes
    Jul 11, 2022 at 7:50
  • $\begingroup$ @MaartenBodewes, sorry, I have no much practice with English language, I saw that "grab" is aggressive in this context, "get" is a better word. But I have said only the fundamentals of the protocol (Textbook RSA). It need some layers of security by adding padding to prevent message modification and the alleged owner of the pub key need to sign some message to add trust to this system. $\endgroup$
    – charles
    Jul 12, 2022 at 1:38
  • 1
    $\begingroup$ Not entirely what I meant. It is required for a receiver of a public key to be able to trust that the public key has originated from the right party. You cannot do this by signing with the private key. In PKIX this the trust is established by having a third party CA sign the certificate, but that is after the CA has performed some checks to validate the identity of the party that generated the key pair. If you skip all these steps then an adversary can perform a man in the middle attack by replacing the original public key with public key belonging to their own key pair. $\endgroup$
    – Maarten Bodewes
    Jul 12, 2022 at 10:52

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.