Recovering multiple of $\phi(N)$ given two private public key pair

BBForage

3/1/24, 3:05 PM

Assume $\phi(N) = (p - 1) (q - 1)$ as in the original paper. Suppose that we are using the same modulus $N$ for public and private key pairs $(e_1, d_1)$ and $(e_2, d_2)$. How can we get a multiple of $\phi(N)$ from these two pairs?

0 + 7

poncho

3/1/24, 3:07 PM

Actually, you need only a single public/private key pair to get a multiple of $\phi(N)$ (actually, $\lambda(N)$, but both will allow you to factor...)

fgrieu

3/1/24, 3:27 PM

Having _two_ private/public key pairs will let you find a smaller multiple of $λ(N)$.

poncho

3/1/24, 3:30 PM

@fgrieu: actually, no it won't - with a multiple of $\lambda(N)$, you can factor, and that'll allow you to compute the smallest positive multiple of $\lambda(N)$ there is :-)

fgrieu

3/1/24, 3:38 PM

@poncho: right. Should have written: having _two_ private/public key pairs is likely to let you _easily_ compute a smaller multiple of $λ(N)$, putting you in a better position to factor $N$ or/and find $ϕ(N)$. I should also have noted that $(e_1, d_1)$ is not a valid public/private key pair, for it is lacking $N$.

BBForage

3/1/24, 3:43 PM

@fgrieu: I understand that we can get a multiple using $ed - 1 = -y * \lambda(N)$ or only 1 key pair, but how can we easily compute a smaller multiple of $\lambda(N)$ using two pairs?

fgrieu

3/1/24, 3:47 PM

Hint: If $u_1$ and $u_2$ both are non-zero multiples of $v$, then $v$ is a common divisor of $u_1$ and $u_2$. And from $u_1$ and $u_2$ we can often find a multiple of $v$ smaller than $u_1$ and $u_2$ in absolute value.

poncho

3/2/24, 1:45 PM

BBForage: if you have an answer to your own question, why don't you submit it as an answer (yes, this site allows you to answer your own questions)

Elon Musk

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

EN: Recovering multiple of $\phi(N)$ given two private public key pair

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.