{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime\n",
    "from random import randint, choice\n",
    "import string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "template_message = \"Your secret 10 letter password is {secret}! Don't share it with anyone!\"\n",
    "password_length = 10\n",
    "\n",
    "def generate_example():\n",
    "    p, q = getPrime(512), getPrime(512)\n",
    "    N = p*q\n",
    "    e = 3\n",
    "\n",
    "    secret = ''.join(choice(string.ascii_uppercase + string.digits + string.ascii_lowercase) for _ in range(password_length))\n",
    "    message = template_message.format(secret=secret)\n",
    "    print(\"Generating the plaintext...\")\n",
    "    print(\"This is the secret plaintext:\", message)\n",
    "    ciphertext = pow(bytes_to_long(message.encode()), e, N)\n",
    "    \n",
    "    return ciphertext, secret, N, e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def coppersmith(ciphertext, N, e):\n",
    "\n",
    "    blank_secret = \"\\x00\" * password_length\n",
    "    stereotyped = bytes_to_long(template_message.format(secret=blank_secret).encode())\n",
    "\n",
    "    suffix = \"! Don't share it with anyone!\"\n",
    "    \n",
    "    modN = Zmod(N)\n",
    "    polyfield.<x> = PolynomialRing(modN)\n",
    "    mypolynomial = (stereotyped + (x * 2^(8*len(suffix))))^e - ciphertext\n",
    "    roots = mypolynomial.monic().small_roots()\n",
    "    return long_to_bytes(int(roots[0])).decode()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generating the plaintext...\n",
      "This is the secret plaintext: Your secret 10 letter password is hWlqwYsnxm! Don't share it with anyone!\n",
      "\n",
      "Hacking time... \n",
      "Coppersmith found the following solution: hWlqwYsnxm\n",
      "\n",
      "Checking solution...\n",
      "The solutions match! hehe :)\n"
     ]
    }
   ],
   "source": [
    "ciphertext, secret, N, e = generate_example()\n",
    "solution = coppersmith(ciphertext, N, e)\n",
    "\n",
    "print(\"\\nHacking time... \\nCoppersmith found the following solution:\", solution)\n",
    "\n",
    "print(\"\\nChecking solution...\")\n",
    "if secret == solution:\n",
    "    print(\"The solutions match! hehe :)\")\n",
    "else:\n",
    "    print(\"WHAAAAAAA?!!! They don't match :(\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.4",
   "language": "sage",
   "name": "sagemath"
  },
  "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}