# Tag Info

3

I'll use these common definitions and notations: $a\equiv b\pmod c$ means that $c>0$ and $c$ divides $b-a$ $a\equiv b^{-1}\pmod c$ means that $a\cdot b\equiv 1\bmod c$ $a=b\bmod c$ means that $a\equiv b\pmod c$ and $0\le a<c$ $a=b^{-1}\bmod c$ means that $a\equiv b^{-1}\pmod c$ and $0\le a<c$ $\varphi$ is the Euler totient function (also noted ...

3

The security of $\varphi$ and $\lambda$ should be equivalent since they are mathematically equivalent in the context in which they are used. (That is: the $d'$th power in $(\mathbb Z/pq\mathbb Z)^\times$ is exactly the same operation as the $d$th power.) However, the mathematically "right" modulus for computing $d$ is $\lambda(pq)$: it is precisely the ...

1

The general case is that of field extension. Given a field $\mathbb{F}_q$ of $q$ elements (in your case, the field is $\mathbb{Z}_p$, the integers modulo a prime $p$), you want to define and do computations in a field $\mathbb{F}_{q^k}$ of $q^k$ elements for some integer $k > 1$. To do so, one first considers $\mathbb{F}_q[X]$ which is the ring of ...

0

If you use a prime $p \equiv 3 \pmod 4$, then an element from $\mathbb{F}_{p^2}$ can be written as $a+ib$, where one has the following rules of calculus: $(a_1+ib_1)+(a_2+ib_2) = (a_1+a_2)+i(b_1+b_2)$ $(a_1+ib_1)\cdot(a_2+ib_2) = (a_1 a_2 - b_1 b_2)+ i (a_1 b_2+ a_2 b_1)$ $(a+ib)^{-1} = (a-i b) / (a^2+b^2)$ Sine $i^2 = -1$, those rules resemble ...

3

If $m^{ed} \equiv m \pmod{q}$, then $q\;|\;(m^{ed}-m)$; if $m^{ed} \equiv m \pmod{p}$, then $p\;|\;(m^{ed}-m)$; thus $m^{ed}-m$ is a multiple of both $p$ and $q$; thus $m^{ed}-m$ is a multiple of $\operatorname{lcm}(p,q)$. Because both $p$ and $q$ are distinct primes, $\operatorname{lcm}(p,q)=pq$ holds; Thus, $m^{ed}-m$ is a multiple of $pq$. So ...

0

Aside from being pedantic and telling you that you can choose arbitrarily large $d$ in some congruence class, you can always achieve $d\equiv -1 \bmod \phi(pq)$ by choosing $e$ to be the same. So in the interval $[1,\phi(pq)]$ the largest $d$ could be is $\phi(pq)-1$.

4

If $d$ is a valid RSA decryption exponent, then so is $d \pm k \lambda(pq)$ for any integer $k$. As a corollary, we may always choose the decryption exponent to lie in the range $0 < d < \lambda(pq)$. In fact, there's generally no reason to choose the decryption outside that range: a larger exponent would just make decryption slower, while using a ...

7

Mathematically speaking, there is no upper bound on the private exponent in RSA: assuming $d$ is a valid private exponent, then the valid exponents are the set of $d'=d+k\cdot\lambda(p\cdot q)$ with $k\in\mathbb Z$, where $\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$ since $p$ and $q$ are distinct primes; this set is unbounded. If you compute $d$ as an ...

Top 50 recent answers are included