Exercise4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1309b3a6",
   "metadata": {},
   "source": [
    "## Alisa Todorova"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "85b71945",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sage.all import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "643af7a5",
   "metadata": {},
   "source": [
    "The following code generates an RSA key with a modulus N of n bits, generates a random polynomial: \n",
    "\n",
    "f(x)=x^2+ax+b mod N\n",
    "\n",
    "with a small root |x_0| < 2^(n/3), and recovers this root using Coppersmith’s technique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8caf09e9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p= 81148965068916712460696931040507301759 q= 42635304019031611976549643573856799573\n",
      "N= 3459810796543040601932605684167873238508415479328158216653323046757493348907\n",
      "Size of N: 251\n",
      "x0= 3390946262337443979873\n",
      "[(3390946262337443979873, 1), (-2310060546572452968656848621531895210562013071392/52074820704467544387439459, 1)]\n"
     ]
    }
   ],
   "source": [
    "def keyGen(n=256):\n",
    "  \"Generates an RSA key\"\n",
    "  while True:\n",
    "    p=random_prime(2^(n//2));q=random_prime(2^(n//2));e=3\n",
    "    if gcd(e,(p-1)*(q-1))==1: break\n",
    "  d=inverse_mod(e,(p-1)*(q-1))\n",
    "  Nn=p*q\n",
    "  print(\"p=\",p,\"q=\",q)\n",
    "  print(\"N=\",Nn)\n",
    "  print(\"Size of N:\",Nn.nbits())\n",
    "  return Nn,p,q,e,d\n",
    "\n",
    "\"Finds a small root of polynomial x^2+ax+b=0 mod N\"\n",
    "def CopPolyDeg2(a,b,Nn):\n",
    "  n=Nn.nbits()\n",
    "  X=2^(n//3-3)\n",
    "  M=matrix(ZZ,[[X^2,a*X,b],\\\n",
    "               [0  ,Nn*X,0],\\\n",
    "               [0  ,0  ,Nn]])\n",
    "  V=M.LLL()\n",
    "  v=V[0]\n",
    "  R.<x> = ZZ[]\n",
    "  f=sum(v[i]*x^(2-i)/X^(2-i) for i in range(3))\n",
    "  return f.roots()\n",
    "\n",
    "def test():\n",
    "  \"\"\"Generates a random polynomial with a small root x0 modulo Nn\n",
    "     and recovers his root.\"\"\"\n",
    "  Nn,p,q,e,d=keyGen()\n",
    "  n=Nn.nbits()\n",
    "  x0=ZZ.random_element(2^(n//3-10))\n",
    "  a=ZZ.random_element(Nn)\n",
    "  b=mod(-x0^2-a*x0,Nn)\n",
    "  print(\"x0=\",x0)\n",
    "  print(CopPolyDeg2(a,b,Nn))\n",
    "\n",
    "test()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4788976",
   "metadata": {},
   "source": [
    "### 1.3 Polynomials of degree 3\n",
    "Modify the previous code to find small roots of polynomials of degree 3. What is the new bound on x_0?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "cef050ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"Finds a small root of polynomial x^3+ax^2+bx+c=0 mod N\"\n",
    "def CopPolyDeg3(a,b,c,Nn):\n",
    "  n=Nn.nbits()\n",
    "  X=2^(n//6-3) # (n//6-3) ensures that X^3 is smaller than Nn\n",
    "  M=matrix(ZZ,[[X^3,a*X^2,b*X,c],\\\n",
    "               [0  ,Nn*X^2,0,0],\\\n",
    "               [0  ,0  ,Nn*X,0],\\\n",
    "               [0  ,0  ,0,Nn]])\n",
    "  V=M.LLL()\n",
    "  v=V[0]\n",
    "  R.<x> = ZZ[]\n",
    "  f=sum(v[i]*x^(3-i)/X^(3-i) for i in range(4))\n",
    "  return f, f.roots()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a466bb06",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p= 339689338561372054374259301840940987371 q= 198833485600304095938975144179941826501\n",
      "N= 67541615207419393238036369990185131302570648295314518369434899472092114118871\n",
      "Size of N: 256\n",
      "a= 49660948123930424666816797036933573882480867484011968552171338390244175019298\n",
      "b= 50831768301464795727379908330605632822656657824128866997855614468535412237016\n",
      "c= 10687140017733583282995761829639332364647973239570874920662960500552103027656\n",
      "x0= 1061616952\n",
      "polynomial= 1644759938011396594417577155442226664128*x^3 + 1140059011853963613441256809151418487994275290873198*x^2 - 395544242119092309198587024567839683127871658057441838312124215*x + 418629623447576707192840313580486682332572153871170437902835347584912264\n",
      "roots= [(1061616952, 1)]\n"
     ]
    }
   ],
   "source": [
    "def test():\n",
    "    \"\"\"Generates a random polynomial with a small root x0 modulo Nn\n",
    "    and recovers his root.\"\"\"\n",
    "    Nn, p, q, e, d = keyGen()\n",
    "    n = Nn.nbits()\n",
    "    x0 = ZZ.random_element(2 ^ (n // 6 - 10)) # (n//6-10) ensures that x0^3 is smaller than Nn\n",
    "    a = ZZ.random_element(Nn)\n",
    "    print(\"a=\", a)\n",
    "    b = ZZ.random_element(Nn)\n",
    "    print(\"b=\", b)\n",
    "    c = mod(-x0 ^ 3 - a * x0 ^ 2 - b * x0, Nn)\n",
    "    print(\"c=\", c)\n",
    "    print(\"x0=\", x0)\n",
    "    polynomial, roots = CopPolyDeg3(a, b, c, Nn)\n",
    "    print(\"polynomial=\", polynomial)\n",
    "    print(\"roots=\", roots)\n",
    "\n",
    "\n",
    "test()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6208e0b1",
   "metadata": {},
   "source": [
    "### 1.4 Application to breaking RSA encryption with small exponent e\n",
    "\n",
    "Let\n",
    "\n",
    "N = 709346188783707808067985067028456920198443445150943868007539748700843008346940940287222002891029537499396908056848095671838771377752278390679951948808475707450073714577930152529057057137554724537719912515486712408422541711159469388603174949214558211229232753033853223644282969544939436208933732047182752629\n",
    "\n",
    "be an RSA modulus of size 1017 bits. Let m be a message with m < 2^168. Let c = (2^1016 + m)^3 mod N\n",
    "with\n",
    "\n",
    "c = 106931790228306983984681105468768847489271870726744288161524001625441564428928138082764847546330455645721020672129383569332864980247631047991368975076235508102167034128121821366927744907882617928973322081585262275454789559141797135693781509609801881376951044409238368040773136628352506077437800520604807524\n",
    "\n",
    "Recover the message m using Coppersmith’s technique.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ac828d0d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Recovered message: 246444312520370940658372328078267298078392115432165\n"
     ]
    }
   ],
   "source": [
    "# The following code is based on slide 9 of lecture slides \"The RSA cryptosystem, Part 2: attacks against RSA\"\n",
    "\n",
    "# Coppersmith's technique to find roots of f(x) modulo N\n",
    "def coppersmith(N,c):\n",
    "    B = 2^1016\n",
    "    k = 0  # Chosen arbitrarily\n",
    "\n",
    "    # Polynomial f(x) = (B * 2^k + x)^3 - c (mod N)\n",
    "    R.<x> = PolynomialRing(Zmod(N))\n",
    "    f = (B * 2^k + x)^3 - c\n",
    "\n",
    "    roots = f.small_roots(X=2^168)\n",
    "\n",
    "    return roots\n",
    "\n",
    "# Given parameters\n",
    "N = 709346188783707808067985067028456920198443445150943868007539748700843008346940940287222002891029537499396908056848095671838771377752278390679951948808475707450073714577930152529057057137554724537719912515486712408422541711159469388603174949214558211229232753033853223644282969544939436208933732047182752629\n",
    "c = 106931790228306983984681105468768847489271870726744288161524001625441564428928138082764847546330455645721020672129383569332864980247631047991368975076235508102167034128121821366927744907882617928973322081585262275454789559141797135693781509609801881376951044409238368040773136628352506077437800520604807524\n",
    "\n",
    "message = coppersmith(N,c)\n",
    "\n",
    "print(\"Recovered message:\", message[0])\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.1",
   "language": "sage",
   "name": "SageMath-10.1"
  },
  "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.11.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}