c2_flipping_bits.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# C2: flipping_bits"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "ct1:  13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654\n",
    "ct2:  79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065\n",
    "e1:  13\n",
    "e2:  15\n",
    "modulus:  103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627\n",
    "\n",
    "You have two captured ciphertexts. The public key is (e1, n). But,\n",
    "due to a transient bit flip, the second ciphertext was encrypted with a faulty\n",
    "public key: (e2, n). Recover the plaintexts.\n",
    "\n",
    "(The algorithm is RSA.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In RSA problems you can win many ways:\n",
    "\n",
    "* Factoring the modulus\n",
    "* The inverse of the public exponent modulo $ \\phi(N) == (p-1)*(q-1) $\n",
    "* Poorly Set Parameters (like p and q being very close to each other)\n",
    "* A small message so that $ m^e $ is smaller than the modulus\n",
    "\n",
    "In this case we have two cipher texts one is $m_1^{e_1}$ the other is $m_2^{e_2}$\n",
    "and $e_2 = 15$ and $e_1 = 13$.  But we have the additional knowledge that\n",
    "$e_2$ was supposed to be $e_1$.  So there might not be a modular inverse of $e_2$.\n",
    "\n",
    "At first I lost time looking for RSA exploits with small close exponents or\n",
    "what goes wrong when the wrong exponent is used in RSA and had no luck.\n",
    "\n",
    "In the process I went looking for algebraic relationships between $e_1 \\cdot e_2$ and $N$\n",
    "or $\\phi$.  Maybe $e_2 \\cdot d$ would have something interesting going on that could lead\n",
    "to an exploit.\n",
    "\n",
    "Then, after some frustration, I recognized that they didn't specify that $ m_1 $\n",
    "wasn't the same as $m_2$ and if it were then inverting the first cipher text will\n",
    "get me $ ct_1^{-1} == m_1^{-e_1}$.  Multiplying by $m_1^{e_1 + 2}$ would give $m_1^{e_1 + 2 - e_1}$\n",
    "which might be a small enough message/exponent combo that we can just take a square root.\n",
    "\n",
    "Sure enough `long_to_bytes(sqrt(inverse_mod(ct1, modulus)*ct2))` reveals the message.\n",
    "\n",
    "I switched to cloud.sagemath.com to get the large integer exact squareroot.\n",
    "\n",
    "Here is my solve.sagews code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import *\n",
    "N=103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627\n",
    "ct1=13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654\n",
    "ct2=79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065\n",
    "long_to_bytes(sqrt((inverse_mod(ct1, N)*ct2) % N))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}