DiscMat assignment 9

exercise

9.3 Pitfalls of RSA

1) Small Moduli

a)

We first factorize $n=133$ into $p=7$ and $q=19$ $f=\varphi (n)=(p-1)(q-1)=108$ We know $d=e^{-1}(\mathrm{mod}f)$ and $e$ has a modular inverse if and only if $gcd(e,f)=1$ Using Corollary 4.5, there exist $u,v\in \mathbb{Z}$ such that $gcd(e,f)=1=u\cdot e+v\cdot f=25u+108v=1$ using the fact that $13\cdot 25-3\cdot 108=1$, we get $u=13,v=-3$ $d=u=13$

b)

$m=c^d(\mathrm{mod}n)=R_{133}(9^{13})$ We first calculate $R_7(9^{13})$ $9^{13}{\equiv }_7{2}^{13}{\equiv }_7(2^3{)}^4\cdot 2{\equiv }_7{8}^4\cdot 2{\equiv }_7{1}^4\cdot 2{\equiv }_{7}2$ We the calculate $R_{19}(9^{13})$ $9^{13}{\equiv }_{19}(9^2{)}^6\cdot 9{\equiv }_{19}81^6\cdot 9{\equiv }_{19}{5}^6\cdot 9{\equiv }_{19}25^3\cdot 9{\equiv }_{19}{6}^3\cdot 9{\equiv }_{19}216\cdot 9{\equiv }_{19}7\cdot 9{\equiv }_{19}6$ We now solve the equation system (using CRT) $\{\begin{array}{l}x\equiv 2(\mathrm{mod}7)\\ x\equiv 6(\mathrm{mod}19)\end{array}$ We get $x=44(\mathrm{mod}133)$ $m=R_{133}(9^{13})=44$

2) Modulus shared between multiple users

Case 1: $c_A$ and $c_B$ are coprime to $n$, $gcd(c_A,n)=gcd(c_B,n)=1$ We know $gcd(e_A,e_B)=1$ using corollary 4.5 we get $u{e}_A+v{e}_B=1$ where $u,v\in \mathbb{Z}$ Eve can efficiently compute such $u,v$ using the extended Euclidean algorithm. We know: $c_A{\equiv }_n{m}^{e_A}$ , $c_B{\equiv }_n{m}^{e_B}$ Therefore, $(c_A{)}^u(c_B{)}^v{\equiv }_n(m^{e_A}{)}^u(m^{e_B}{)}^v{\equiv }_n{m}^{u{e}_A+v{e}_B}{\equiv }_n{m}^1{\equiv }_{n}m$

There are two sub cases:

• If $u,v\ge 0$: just compute $m$ using $R_n((c_A{)}^u(c_B{)}^v)$
• If at least one of $u,v$ is negative:
  • Assume without loss of generosity that $u$ is negative, we write $u=-u^{\prime }$
  • $(c_A{)}^u=(c_A{)}^{-u^{\prime }}=(c_A^{-1}{)}^{u^{\prime }}$
  • Since $gcd(c_A,n)=1$, we can write it as $a{c}_A+bn=1$ using corollary 4.5, where $a,b\in \mathbb{Z}$
  • Again we can calculate $a,b$ using extended Euclidean algorithm
  • we get $c_A^{-1}$ by $c_A^{-1}=a$ and calculate $m$ using $R_n((c_A^{-1}{)}^{u^{\prime }}(c_B{)}^v)$

Case 2: At least one of $u,v$ is not co-prime to n Assume without loss of generosity that $gcd(c_A,n)\ne 1$ Let $g=gcd(c_A,n)$ where $g\ne 1$ $⟹g|n$

• $g=n$:
  • then $c_A{\equiv }_{n}0$
  • $⟹e_A^m{\equiv }_{n}0⟹m{\equiv }_{n}0⟹m=0$
• $1<g<n$:
  • we know $n=pq$ where $p,q$ are prime numbers and $p,q\ne n$
  • Let $p=g$, $q=\frac{n}{g}$, we can then easily compute $\varphi (n)=(p-1)(q-1)$
  • Once we have $f=\varphi (n)$, we can then compute $d_A{\equiv }_f{e}_A^{-1}$ using the extended Euclidean algorithm.
  • Now we have the decryption key, we can compute $m$ using $R_n((c_A{)}^{d_A})$