Very basic modular example - Cryptography Stack Exchange most recent 30 from crypto.stackexchange.com 2022-01-26T17:09:07Z https://crypto.stackexchange.com/feeds/question/48893 https://creativecommons.org/licenses/by-sa/4.0/rdf https://crypto.stackexchange.com/q/48893 0 Very basic modular example user1156544 https://crypto.stackexchange.com/users/49451 2017-07-06T09:40:43Z 2017-07-07T16:28:05Z <p>This is a very basic question, but I cannot get it right. I'm working on a basic asymmetric encryption example.</p> <p>So $(m^e)^d \equiv m \pmod n$ (at least with the premise of m &lt; n, I suppose)</p> <p>If I choose:</p> <ul> <li>m = 14 (my message)</li> <li>n = 19</li> <li>e = 3</li> <li>d = 13 -- because $3 \cdot 13 ≡ 1 \pmod{19}$</li> </ul> <p>Then I encrypt $14^3 ≡ 8 \pmod {19}$</p> <p>But I decrypt $8 ^ {13} ≡ 8 \pmod {19}$</p> <p>What am I doing wrong?</p> <hr> <p><strong>EDIT</strong> My logic behind this is:</p> <p>$m^e ≡ m' \pmod n$</p> <p>if $e \cdot d≡1 \pmod n$ then</p> <p>$m'^d ≡ m \pmod n$</p> <p>Because $(m^e)^d = m^{e \cdot d} ≡ m^1 \pmod n$</p> https://crypto.stackexchange.com/questions/48893/-/48916#48916 3 Answer by fgrieu for Very basic modular example fgrieu https://crypto.stackexchange.com/users/555 2017-07-07T05:16:26Z 2017-07-07T16:28:05Z <p>Trying to follow as reference Burt Kaliski's <a href="http://www.mathaware.org/mam/06/Kaliski.pdf" rel="nofollow noreferrer"><em>The Mathematics of the RSA Public-Key Cryptosystem</em></a>, the question has the following issues:</p> <ul> <li>The question selects $n=19$ as a prime, rather than as the factor of two distinct primes $p$ and $q$ ($p=5$, $q=11$, $n=55$ in the reference); this is however not disastrous, and we'll adapt the reference by taking $n=p$ and ignoring $q$.</li> <li>The question uses $d$ such that $e\,d\equiv1\pmod n$, when nothing suggests that in the reference; the reference uses $e\,d\equiv1\pmod L$ with $L=\operatorname{lcm(p-1,q-1)}$, and with our adaptation that becomes $L=n-1$, thus the relation between $e$ and $d$ should be $$e\,d\equiv1\pmod{(n-1)}$$</li> <li>The question ignores the stated requirement that $e$ is relatively prime to $p-1$ and $q-1$ (meaning: $e$ shares no prime factor with either $p-1$ or $q-1$); with our adaptation this becomes that $e$ is relatively prime to $n-1$. It follows that $e=3$ is an invalid choice for $n=19$, since $3$ divides both $e=3$ and $n-1=18$.</li> </ul> <p>If we keep $n=19$, we can use $e=5$, find $d$ such that $e\,d\equiv1\pmod{18}$, e.g. $d=11$. Then $c=m^e\bmod p=14^5\bmod19=10$, and $m'=c^d\bmod n=10^{11}\bmod19=14=m$, as expected.<br> Note: I use $c$ for the ciphertext as in the reference, and $m'$ for the the result of the decryption.</p> <p>This is an application of <a href="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem" rel="nofollow noreferrer">Fermat's little theorem</a>, which states that if $p$ is prime, then for all $m$ not divisible by $p$, it holds that $m^{p-1}\equiv1\bmod p$.</p> <p>Notice that since we chosed $d$ with $e\,d\equiv1\pmod{(n-1)}$, it holds that $e\,d=k(n-1)+1$ for some integer $k$.</p> <p>Now, the way we computed $m'$, it holds that \begin{align}m'&amp;\equiv c^d&amp;\pmod n&amp;&amp;\text{ using }m'=c^d\bmod n\\ &amp;\equiv{(m^e)}^d&amp;\pmod n&amp;&amp;\text{ using }c=m^e\bmod n\\ &amp;\equiv m^{e\,d}&amp;\pmod n\\ &amp;\equiv m^{k(n-1)+1}&amp;\pmod n&amp;&amp;\text{ using }e\,d=k(n-1)+1\\ &amp;\equiv {(m^{n-1})}^k\,m&amp;\pmod n\\ &amp;\equiv 1^k\,m&amp;\pmod n&amp;&amp;\text{ using FLT}\\ &amp;\equiv m&amp;\pmod n\\ \end{align} Note: when using the FLT, we rely on $n$ prime, and $m$ not divisible by $n$, which holds.</p> <p>Since $m'=c^d\bmod n$ it holds that $0\le m'&lt;n$. We have $0&lt;m&lt;n$ and $m'\equiv m\pmod n$, hence $m'=m$ <sub>Q.E.D.</sub></p> <hr> <p>An incorrect assumption made in the question's reasoning is that it would hold that $m^i\bmod n=m^{(i\bmod n)}\bmod n$; that's false in general, and a proof is given by the computations in the question.</p> <p>What really holds is that $m^i\bmod n=m^{(i\bmod\lambda(n))}\bmod n$ where $\lambda$ is the <a href="https://en.wikipedia.org/wiki/Carmichael_function" rel="nofollow noreferrer">Carmichael function</a>, and $m$ is coprime with $n$ or $n$ is <a href="https://en.wikipedia.org/wiki/Square-free_integer" rel="nofollow noreferrer">square-free</a>. The later holds in RSA. In the reference $n=p\,q$ with $p$ and $q$ distinct primes, and $\lambda(n)=L=\operatorname{lcm}(p-1,q-1)$.</p> <hr> <p>Standard notation, used in this answer (but not the reference, which omits parenthesis in the first notation): for $w&gt;0$</p> <ul> <li>$u\equiv v\pmod w$ means that $w$ divides $u-v$</li> <li>$u=v\bmod w$ means that $w$ divides $u-v$ and $0\le u&lt;w$.</li> </ul>