{ "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. = 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 }