RSA use prime p as public exponent

Manc

12/23/22, 10:18 AM

I've got two 1024 bits prime $p$,$q$,and $n$ = $p$ * $q$. now I know the result of $ c^{p} \quad mod \quad n = x$,also the value of c is given, I wonder if it is possible to factorize $n$.

102

1 + 0

rsa

encryption

factoring

decryption

Score:2

Crypto

Samuel Neves

12/23/22, 11:25 AM

From Fermat's little theorem we know $$ a^p \equiv a \pmod{p}\,. $$ Applying this to the present problem, $c^p \equiv c \equiv x \pmod{p}$, and thus $p = \gcd(x - c, n)$.

0 + 0

fgrieu

9/6/23, 11:40 AM

The conclusion "thus $p=\gcd(x-c,n)$" is unwarranted. That's overwhelmingly likely for random $c$. Baring this, sure $p$ divides $x-c$, but it can happen that $x\equiv c\pmod n$, in which case $\gcd(x-c,n)$ is $n$ and does not reveal a factorization of $n$. In that case, it's worth trying if $\gcd(c,n)$ is a non-trivial factor of $n$, but that's not certain either. Small example: take $p=109$, $q=211$. Now $x\equiv c\pmod n$ occurs for $763$ values of $c\in[0,n)$, that is probability $7/q>3.3\%$ for random $c$. Within these only $114$, that is $<15\%$, are such that $\gcd(c,n)$ is $p$ or $q$.

Samuel Neves

9/6/23, 4:03 PM

Point well taken. This happens when $p \bmod \mathrm{ord}_q(x) \in {0,1}$. The other 114 aren't really valid elements of $\mathbb{Z}_n^\ast$, since they are multiples of $p$ or $q$ and amount to guessing one of the factors.

Elon Musk

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

EN: RSA use prime p as public exponent

TH: RSA ใช้ไพรม์ p เป็นเลขยกกำลังสาธารณะ

RO: RSA folosește prim p ca exponent public

RU: RSA использует простое число p в качестве общедоступного показателя

VI: RSA sử dụng số nguyên tố p làm số mũ công khai

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.