21 of 22
Polish
fgrieu
  • 111037
  • 9
  • 238
  • 475

what I am doing wrong?

Accepting as fact a recipe with an equation, rather than deriving it.

Illustration: « Then we obtain $m$ as ${c_1}^a + {c_2}^b \bmod n$ » is stated rather than derived. And wrong.

As an aside the question reverses $a$ and $b$ (or is it $c_1$ and $c_2$, or $e_1$ and $e_2$): they are correct per the official solution which asks $a\,e_1 + b\,e_2 = 1$, but the calculation then made assumes and states $a\,e_2 + b\,e_1 = 1$.

Hint to derive the correct equation:

  1. Prove that $m^1\bmod n=m$, by combining the definition¹ of raising to an integer exponent, the assumed range of $m$ in textbook RSA, and the definition² of the $\bmod$ operator.
  2. In this equation, substitute $1$ with $a\,e_1 + b\,e_2$ where $a$ and $b$ are the Bezout coefficients such that $a\,e_1 + b\,e_2=1$.
  3. Properly use properties³ of modular exponentiation. In cryptanalysis it's OK to assume plausible preconditions when that's necessary, but it remains good to verify them (or the result derived) in the end.

Suggestion: apply this technique with a slightly larger $n=14835196795348830319$, $(e_1,e_2)=(3,5)$, and $(c_1,c_2)=(14562201346830272020,1832973312396331965)$. As a bonus find the menu by expressing $m$ in hex. The point of these larger numbers is that guessing the Bezout coefficients and inverse is harder, and slightly more computer skills are needed.

More mathematically interesting, for a different method is needed, which would still work if $n$ was too large to factor directly from its value: with the same $(n,e_1,e_2)$ find $m$ for $(c_1,c_2)=(11810011337245959646,2207245693327700143)$.


Note: in actual use, RSA encryption

  • Does not reuse the same $n$ among several public keys, making this particular attack fail.
  • Does not directly encode the message as $m$, but rather adds randomness to the message in order to form $m$. That makes it extremely unlikely that $m$ is reused (it would be enough to allow some other attacks including with different $n$).
  • Uses $n$ with several hundred decimal digits in order to resist factorization. $n=143$ can be factored mentally, and the larger $n$ is factored in a small fraction of a second using a computer, which allows to find $m$ by using the normal RSA decryption equation, without needing $c_2$ or $e_2$.

Appreciation: taking at face value the statement that the extended Euclidean algorithm was used, the question shows fair skills to apply equations and algorithms, despite the inversion of $a$ and $b$. Be assured that the goal of such exercises is not learning the equations used. It's to learn to derive the necessary equations. That's easier when one gets the hang of it, and more fun. It's more reliable, and thus gets higher marks (which is a valid sub-goal) even when the reasoning is not considered in the notation. As a skill it's more useful, more adaptable, less likely to go obsolete, or unused and forgotten.


¹  By definition, $x^u$ for $u$ a strictly positive integer is $x$ when $u$ is $1$, and is $x\cdot\left(x^{\left(u-1\right)}\right)$ otherwise, where $\cdot$ is multiplication.

  • That can be written $$\forall x,\ \forall u\in\Bbb N^*,\ x^u\underset{\text{def}}=\begin{cases}x&\text{if}\ x=1\\x\cdot\left(x^{\left(u-1\right)}\right)&\text{otherwise}\end{cases}$$

  • Equivalently, $x^u$ is can be defined as $\underbrace{x\cdot x\cdot x}_{u\text{ times}}$. Both are valid whatever set $x$ belongs to, including the signed integers under multiplication $(\Bbb Z,\cdot)$ in the context of RSA.

  • There are extensions of that definition for $u\in\Bbb Z$, with some differences e.g. about if $0^0$ is defined, and then what that is defined to be. For the extension used in the context of RSA, see the last bullet in note² below.

  • In $x^u$ (pronounced « $x$ raised to exponent $u$ », or « $x$ to the $u$ » ), the exponent is written above, in smaller characters, and absent parenthesis is evaluated before $\cdot$ (thus before $+$ ).

  • The $\cdot$ operator can also be noted $\times$ or $*$ or replaced by a thin space. It can be omitted altogether except between digits: we write $2\cdot3=6$, or $2\cdot3=6$, perhaps $2\,3=6$, but never $23=6$ ; on the other hand we often write $2\,x=x+x$ or $2x=x+x$. Thus $x\cdot\left(x^{\left(u-1\right)}\right)$ can be written $x\,x^{u-1}$.


²  By definition, $y\bmod n$ is the $x$ in range $[0,n)$ such that $n>0$ divides $y-x$. Computer languages often feature a % operator similar to $\bmod$ but:

  • The two might differ on the result when $y$ is negative: e.g. $(-1)\bmod 2$ is $1$ but (-1)%2 is -1 in Java, C++, and most dialects of C. There's no such issue in Python.

  • % usually has the same priority as multiplication * but the rule differs for $\bmod$ : absent parenthesis, the $\bmod$ operator is evaluated after $+$ ( thus after $\cdot$ thus after exponentiation) at least on the left of $\bmod$ (it's best to use explicit parenthesis for the right operand up to the next operator of clearly lower precedence, such as $=$ ). Thus $x+y\,z^{u+v}\bmod n=t$ is to be understood as $\Biggl(\biggl(x+\Bigl(y\cdot\left(z^{\left(u+v\right)}\right)\Bigr)\biggr)\bmod n\Biggr)=t$ and can be implemented as (x+y*z)%n=t in computer languages including Python.

  • The expression $x=y\bmod n$ is read « $x$ equals $y$ modulo $n$ » and means $x\,=\,(y\bmod n)$.

  • When there is an opening parenthesis immediately before $\bmod$, and/or an $\equiv$ somewhere on the left of $\bmod$, that $\bmod$ is not an operator, but rather an indication that all that's on its left is computed modulo $n$. That is, the expression $x\equiv y\pmod n$ can be read « $x$ is congruent to $y$ (pause) modulo $n$ ». It means that $y-x$ is a multiple of $n$, but does not set bounds for $x$. Notational shortcuts for $x\equiv y\pmod n$ include $x=y\pmod n$ and $x\equiv y\mod n$, but are best avoided in an RSA context, where the bound of plaintext and ciphertext matter.

  • In the context of RSA, the quantity $x^u\bmod n$ is defined as an extension of the above such that $(x^u\bmod n)\,(x^{-u}\bmod n)-1$ is a multiple of $n$ whenever both $x^u\bmod n$ and $x^{-u}\bmod n$ can be defined, that is when $\gcd(x,n)=1$ or when $u=0$.
    More precisely, for $x\in\Bbb Z$, $u\in\Bbb Z$, $n\in\Bbb N^*$, the quantity $x^u\bmod n$ is defined if and only if $u\ge0$ or $\gcd(x,n)=1$, and then is the integer $y\in[0,n)$ such that
    ⋅  $x^u-y$ is a multiple of $n$, when $u>0$
    ⋅  $y=1$, when $u=0$
    ⋅  $x^{-u}\,y-1$ a multiple of $n$, when $u<0$ and $\gcd(x,n)=1$
    In Python 3.8 and later, pow(x,u,n) computes $x^u\bmod n$ per that convention.


³  $\forall n\in\Bbb N^*$, $\forall x\in\Bbb Z$, $\forall u\in\Bbb Z$, $\forall v\in\Bbb Z$, if $\gcd(x,n)=1$ or ($u\ge0$ and $v\ge0$), and with the convention that $x^0\bmod n=1$, it holds: $$\begin{align} x^{u+v}\bmod n&\,=\,\left(x^u\bmod n\right)\,\left(x^v\bmod n\right)\bmod n\\ x^{u\,v}\bmod n&\,=\,\left(x^u\bmod n\right)^v\bmod n \end{align}$$ or equivalently, with multiplication operator $\cdot$ explicit and more parenthesis: $$\begin{align} \bigl(x^{(u+v)}\bigr)\bmod n&\,=\,\bigl(\left(x^u\bmod n\right)\cdot\left(x^v\bmod n\right)\bigr)\bmod n\\ \bigl(x^{(u\cdot v)}\bigr)\bmod n&\,=\,\bigl(\left(x^u\bmod n\right)^v\bigr)\bmod n \end{align}$$ or using modular equivalence instead of the $\bmod$ operator: $$\begin{array}{ccc} x^{(u+v)}&\equiv&(x^u)\,(x^v)&\pmod n\\ x^{(u\,v)}&\equiv&\left(x^u\right)^v&\pmod n \end{array}$$

fgrieu
  • 111037
  • 9
  • 238
  • 475