Score:0

RSA rsa residue class ring

th flag

I've been working on the RSA method for several weeks and I don't understand what this residual class ring is all about.

I understand that if

$ x^e \bmod n$ there must be $x<n$ because of the clarity of the results

However, I don't understand what other advantages it brings.

When I look for manipulation attempts on the Internet, the modulo calculation is always very simple:

$(s^e y)^d \equiv s^{ed}x^{ed} \equiv (sx)^{ed} \bmod n$

But why does it even work so easy, isn't $y=x^d \bmod n$ ?

fgrieu avatar
ng flag
In this the last two equations are likely intended to be $(s^e\,y)^d\equiv s^{e\,d}*x^{e\,d} \equiv(s\,x)^{e\,d} \pmod n$ and one of $y=x^e\bmod n$ or $x=y^d\bmod n$.
Score:1
ng flag

For a fixed integer $n\ge2$, we can define an equivalence relation in the ring $(\mathbb Z,+,\cdot)$. That relation is known as "congruence modulo $n$", "equality modulo $n$", or "equivalence modulo $n$". It's noted $u\equiv v\pmod n$ when integers $u$ and $v$ are in said relation, meaning

  • $u$ and $v$ are such that $v-u$ is some multiple of $n$
  • that is, there exists an integer $k$ such that $v-u=k\,n$.

and said equivalence relation is used to build the residue class ring $\mathbb Z/nZ$, which (in crypto) is often noted $(\mathbb Z_n,+,\cdot)$ or just $\mathbb Z_n$.

$v\bmod n$, without parenthesis immediately on the left of$\bmod$ nor $\equiv$ sign at the same level of the expression, can be defined as the smallest non-negative member of the infinite set of integers $u$ with $u\equiv v\pmod n$. It holds $u=v\bmod n$, where$\bmod$ is an operator.

The notation $y=x^e\bmod n$ implies $0\le y<n$, but $y\equiv x^e\pmod n$ does not. Thus $y=x^e\bmod n$ defines a unique integer $y$ as a function of $x$, $e$ and $n$, when $y\equiv x^e\pmod n$ does not.

The output of the (textbook/raw) RSA encryption function $x\mapsto y=x^e\bmod n$ (with $x$ an integer and $0\le x<n$, which I assume in the all following) is a uniquely defined integer $y$, of size at most that of $n$. In particular (for $n>2$ and $e>1$) that function can't simply return $y=x^e$ for all $x$, which $y\equiv x^e\pmod n$ allows.

The difference matters because $x\mapsto y=x^e$ is a function that's easy to invert (by extracting an $n^\text{th}$ root in the integers); but with $n$ and $e$ properly chosen for RSA, the (mathematically invertible) function $x\mapsto y=x^e\bmod n$ is conjectured to be computationally hard to invert given $n$, $e$, and random $y$ or $y$ for random unknown $x$, unless one can obtain the factorization of $n$ or some equivalent information like $d$.


The modulo calculation is always very simple: $(s^e\,y)^d\equiv s^{e\,d}*x^{e\,d}\equiv(s\,x)^{e\,d}\pmod n$

Note: the modified equation clarifies that here$\bmod$ is not an operator, but a qualifier of the equivalence relation $\equiv$

This is a fact holding for $(n,e,d)$ as in RSA, and all integers $x$, $y$, $s$ with $y\equiv x^e\pmod n$. It does not allow to factor $n$, nor compute from $(n,e)$ a $d$ making $y\mapsto x=x^d\bmod n$ the inverse function of $x\mapsto y=x^e\bmod n$, or otherwise invert that function for random $y$ or $y$ for random unknown $x$.

Said fact would allow some manipulations if the textbook RSA function $x\mapsto y=x^e\bmod n$ was directly used to encrypt $x$, or if it's inverse function $y\mapsto x=y^d\bmod n$ was directly used to sign $y$. Common practice prevents such manipulation by choosing $x$ or $y$ close enough to random.

mangohost

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.