{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q1: [15 points] Checking if a number is a power of another number\n",
    "\n",
    "Write down a polynomial time algorithm if a given integer $N$ can be expressed as $a^b$ for positive integers $a,b$ with $b \\geq 2$. The running time of the algorithm should be $\\operatorname{poly}(\\log N)$.\n",
    "\n",
    "(Obviously, you are expected to write this function without using some built-in test within Sage to check if an integer is a perfect power). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_perfect_power(N):\n",
    "    '''\n",
    "    Should return either False, \n",
    "    or a pair of integers (a,b) such that N = a^b with b > 1.\n",
    "    '''\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q2: [20 points] Bad implementation of RSA\n",
    "\n",
    "The RSA cryptosystem is a very popular system that is used in many practical applications and relies on the hardness of \"factoring\". For a brief description, two large prime numbers are picked at random and let number $N = pq$. Furthermore, an \"exponent\" $e$ is chosen so that $\\gcd(e, (p-1)(q-1)) = 1$ (in most implementations, $e$ is either $3$ or $65537$, but in this problem we will set $e = 3$).\n",
    "\n",
    "A message $m$ is thought of as an element of $\\mathbb{Z}_N^\\ast$, and the encryption of $m$ is simply $\\operatorname{enc}(m) = m^e \\bmod{N}$.\n",
    "\n",
    "Thus anyone with the knowledge of just $N$ and $e$ can encrypt any message. However, without the factors of $N$ (assuming that factoring integers is a hard problem) turns out that computing $m$ from $\\operatorname{enc}(m)$ (in general) is hard. This ensures that only a person who knows the factorisation of $N$ can recover the intended message $m$ from $c$. However, one needs to be careful in implementing this in practical scenarios.\n",
    "\n",
    "If $m$ is too small (say $m \\ll N^{1/12}$), then $m^3 \\ll N$ and hence $c = m^3$ even without the mod. Computing cube-roots over integers is of course trivial and we can easily recover $m$ from $c$. So the standard approach is to ''pad'' $m$ into a larger string $m'$ so that $(m')^e$ definitely wraps around $N$ often. Some bad implementations of RSA might end up doing this padding in a predictable way such as $m \\rightarrow m' = 1111\\cdots 10m$ and compute $c = (m')^e \\bmod{N}$ as the encryption. You have to show why this is a TERRIBLE idea by using the techniques of Qn 4 from Part A of this problem set. \n",
    "\n",
    "Below is a bad implementation of RSA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_key(return_private_key = False):\n",
    "    e = 3 # This is the exponent we want\n",
    "    while(True):\n",
    "        p = Integer(randint(2**1000, 2**1024))\n",
    "        if p.is_prime() and gcd(e, p-1) == 1: break\n",
    "    while(True):\n",
    "        q = Integer(randint(2**1000, 2**1024))\n",
    "        if q.is_prime() and gcd(e, q-1) == 1: break\n",
    "    \n",
    "    N = p*q\n",
    "    if return_private_key: \n",
    "        return (e, N, p, q)\n",
    "    else:\n",
    "        return (e, N)\n",
    "\n",
    "def pow_mod(m, e, N):\n",
    "    if e == 0: return 1\n",
    "    if e == 1: return (m % N)\n",
    "    \n",
    "    s = pow_mod(m, e//2, N) \n",
    "    if e % 2 == 0: \n",
    "        return (s * s) % N\n",
    "    else:\n",
    "        return (s * s * m) % N\n",
    "        \n",
    "def vanilla_RSA_encrypt(m, e, N):\n",
    "    if m > N or gcd(m, N) != 1: raise ValueError(\"Constraint on m and N failed\")\n",
    "    return pow_mod(m, e, N)\n",
    "\n",
    "def pad_message(m):\n",
    "    '''\n",
    "    Expects a message m with no more than 29 digits.\n",
    "    \n",
    "    Returns a number m1 consisting of 546 digits:\n",
    "        pad_message(m) = 516 ones, followed by zeros, followed by m\n",
    "    \n",
    "    '''\n",
    "    if len(str(m)) >= 30: raise ValueError(f\"{m} is too long\")\n",
    "    \n",
    "    return int( (\"1\" * 516) + (\"0\" * 30) ) + m\n",
    "\n",
    "def padded_RSA(m, e, N):\n",
    "    '''\n",
    "    Pads the message m using the above padding function, and then applies the RSA encryption on it.\n",
    "    '''\n",
    "    \n",
    "    return vanilla_RSA_encrypt(pad_message(m), e, N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let us generate the keys etc. and a random message of about 80 bits. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "e, N = generate_key()\n",
    "while(True):\n",
    "    m = randint(1,2**80)\n",
    "    if gcd(m,N) == 1: break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are now going to encrypt $m$ using the padding function defined above, and here is a specific value instantiation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    N = 110475443751958845306143886778425046782064103827594367775863319218549890843522733269989775298217479906444000317035215078636093378717273996048245187798421883851380294073419729111369495264048695080185077090847662159692176535167781755002916746570980633467199208401881304433054573301204193892218625443357644182780864370482261764231452793082111167796158570848691855083795596935906526380372448058344499011116036053211663184196339908792442299765542660512666035653711488943865395007571216192543614770625472487157280530801016848604709366430428835362565508211618524261516798405718322699220933684453434088397251352568660906921\n",
    "    e = 3\n",
    "    \n",
    "    padded_RSA(m, e, N) = 82528186845679773516278133812223459542051590946443386965114675192394954205835087606281228746865004910659048095916434637976266114221141192950941209811973168285106508732328185461902088564565973617087820188377641821780879543116140550343702867436024697924795945579221959323209622222933100302467314679930070319447957559778248129385358222914966689829516153845234163669840541699936595377894676078741532488692531671413133002809296514323084674612073788677508848513573282103259966814399768644808177705327121133462036182337983085063936664878130322957687127864567627148909721446268828983809423633290059319047693746979758768413\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Question: Find $m$.\n",
    "\n",
    "(For this question, you can use the built in `LLL()` and `factor()` method. But you are NOT allowed to use the function `small_roots()`; you have to put in some effort to implement the method described in Part-A Qn4. :-) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sage has a built in function for factoring polynomials (over rationals, or over finite fields) and also for computing the LLL basis. Here are some examples. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(x - 1) * x * (x + 1) * (x^2 + 1) * (x^4 + 1)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R.<x> = PolynomialRing(QQ)\n",
    "(x^9 - x).factor()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, -1)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# LLL Example\n",
    "M = Matrix(QQ, [vector([71, 64]), vector([10, 9])])\n",
    "v = M.LLL()[0]  # The first element of the LLL basis is the short-ish vector found\n",
    "v"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.4",
   "language": "sage",
   "name": "sagemath-9.4"
  },
  "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}