Can $s$ be any number in $s^x = x \bmod N$, where $N = p \cdot q$ for de Jonge / Chaum?

Satochi

3/5/24, 11:53 AM

I was reading about some way to imagine the signature of a message using the RSA problem :

Let $N$ be the product of two prime numbers $p$ and $q$. Let $s$ be the signature of a message $s$ (provided that such $s$ exists) defined as $s^x = x \bmod N$.

Later on the following requirement is made on $x$ : $x$ is prime with $\phi(N)$.

I do not understand this requirement. And why with $\phi(N)$ and not $N$ ?

In my understanding, $s$ must be prime with $N$, so that I will be able to use Euler's theorem at some point. But what is all about $x$ and $\phi(N)$ ?

0 + 2

swineone

3/5/24, 1:34 PM

RSA induces a group whose order is $k \phi(N) + 1$, thus not related to $N$ itself. Hence the requirement must be related to $\phi(N)$, not $N$.

poncho

3/6/24, 9:34 PM

Actually, there's no requirement that $s$ be relatively prime to $N$; for a toy example, $N=15, s=12$ is a valid signature of $x=3$.

Elon Musk

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

EN: Can $s$ be any number in $s^x = x \bmod N$, where $N = p \cdot q$ for de Jonge / Chaum?

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.