{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The reblocking problem\n",
    "\n",
    "Suppose that Alice wants to send Bob a signed and encrypted message $m$. She will use RSA for both signing and encrypting. She first uses her private key $(n_A, d_A)$ to obtain the signature $s = m^{d_A} \\bmod{n_A}$, and then uses Bob's public key $(n_B, e_B)$ to obtain the ciphertext $c = s^{e_B} \\bmod{n_B}$. She sends $c$ to Bob, who then decrypts it with his private key $(n_B, d_B)$ to obtain $s' = c^{d_B} \\bmod{n_B}$, and finally recovers the message $m' = s'^{e_A} \\bmod{n_A}$ using Alice’s public key $(n_A, e_A)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "nA = 62894113\n",
    "eA = 3\n",
    "dA = 41918819\n",
    "\n",
    "nB = 55465219\n",
    "eB = 17\n",
    "dB = 26094257\n",
    "\n",
    "m = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us first sign the message $m$ with Alice's private key, and then encrypt the signature using Bob's public key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19714331"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = Integer(pow(m, dA, nA))\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20507849"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = Integer(pow(s, eB, nB))\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now decrypt the ciphertext using Bob's private key, and then extract the message with Alice's public key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19714331"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ss = Integer(pow(c, dB, nB))\n",
    "ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mm = Integer(pow(ss, eA, nA))\n",
    "mm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us try with another message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, 62006589, 51623723, 6541370, 42173672)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = 5\n",
    "s = Integer(pow(m, dA, nA))\n",
    "c = Integer(pow(s, eB, nB))\n",
    "ss = Integer(pow(c, dB, nB))\n",
    "mm = Integer(pow(ss, eA, nA))\n",
    "(m, s, c, ss, mm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We se that since the original signature $s$ was larger than Bob's modulus $n_B$, decrypting $c$ only gives $s' = s \\bmod{n_B}$, leading to $m' \\ne m$.\n",
    "\n",
    "The probability of this happening can be expressed as $(n_A - n_B)/n_A$, where $n_A > n_B$. Let us compute it for our case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.118117477863151"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N((nA - nB)/nA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Several measures can be taken to prevent this from happening.\n",
    "\n",
    "* Set a threshold $t$, and use different keys for encryption and signing: the signing keys should have moduli $n < t$, while the encryption keys should have moduli $n > t$.\n",
    "* Use hash functions and hybrid encryption schemes: to sign the message, compute the RSA signature of its digest, and append it to the message. Then, randomly choose a key $k$ for a symmetric encryption scheme (say, AES), and encrypt the signed message with $k$ (say, using the CBC mode of operation). Then, encrypt $k$ with RSA ($k$ will be much smaller than the modulus), and prepend its encryption to the symmetric encryption of the message."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.3",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}