Is private key generation without prior communication possible in naive RSA?

Alan Whitteaker

7/13/24, 10:28 PM

From what I have understood of naive RSA (without padding) so far, it seems that A and B must first decide on the prime factors in order for B to generate its private key to decrypt A's message. I do understand that the RSA system helps in the establishment of a secure "channel", rather than having to rely on creating a new secure channel everytime between A and B, but isn't this a circular argument?

If B is to generate its private key, A must first share a one time pad (or its equivalent) with B, and only then can it send the primes?

1 + 0

Score:0

Crypto

kodlu

7/13/24, 11:11 PM

TL;DR: The secure communication channels set up by RSA are one way and not duplex between two users. A sets up a channel for anyone to use to send secure messages to A. B sets up a channel (independently, with different primes B chooses) for anyone to use to securely communicate to B.

Not at all. The two parties independently choose their primes.

A chooses two random large primes $p,q$ computes the product $n=pq.$ A then chooses an encryption exponent $e$ and since it knows $p,q$ can efficiently determine the decryption exponent $d.$

(Note: It could also choose a decryption exponent $d$ and compute $e$, mathematically it's equivalent.

A publishes its public key $(n,e).$ This establishes a secure channel for anyone to send messages to A.

Independently, B chooses two random large primes $p',q'$ computes the product $n'=p'q'.$ B then chooses an encryption exponent $e'$ and since it knows $p',q'$ it can efficiently determine the decryption exponent $d'.$

B publishes its public key $(n',e').$ This establishes a secure channel for anyone to send messages to B.

+ 2

Alan Whitteaker

7/14/24, 5:07 AM

In that case, how could B possibly decrypt A's message, if all it has access to is pq and e?

Alan Whitteaker

7/14/24, 5:14 AM

Nevermind. (Leaving this up in case anyone else has this misconception as well.)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is private key generation without prior communication possible in naive RSA?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.