{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD\n",
    "from Crypto.Hash.SHA256 import SHA256Hash\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def key_creation():\n",
    "    p = getPrime(128)\n",
    "    q = getPrime(128)\n",
    "    N = p * q\n",
    "    while True:\n",
    "        e = random.randint(N//4,N-1)\n",
    "        if(GCD(e, (p-1)*(q-1)) == 1):\n",
    "            break\n",
    "    return (p, q), (N, e)\n",
    "\n",
    "def rsa_ds_sign(D, p, q, N):\n",
    "    D = bytes_to_long(D)\n",
    "    d = inverse(e, (p-1)*(q-1)) #compute private key\n",
    "    S = pow(D, d, N) #compute signature\n",
    "    return long_to_bytes(S)\n",
    "\n",
    "def rsa_ds_verif(D, S, e, N):\n",
    "    D = bytes_to_long(D)\n",
    "    S = bytes_to_long(S)\n",
    "    return pow(S, e, N) == D #verify using public key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Prerequisites\n",
    "- RSA signatures\n",
    "- Modular arithmetic\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $(G, E, D)$ be our signing algorithm based on RSA\n",
    "- $p, q$ primes\n",
    "- $N = pq;\\  \\varphi(N) = (p-1)(q-1)$\n",
    "- $d \\equiv e^{-1} \\bmod \\varphi(N)$ \n",
    "\n",
    "RSADSA \n",
    "- Sign: $\\sigma = m^d \\bmod N$\n",
    "- Verify: $m == \\sigma^e \\bmod N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task**\n",
    "> Given a signature $\\sigma$ an attacker can choose a new message $m'$ and a $k_{pub} =(N', e')$ such that $m' == \\sigma^{e'} \\bmod N'$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The attacker can choose can choose $e = 1$\n",
    "\n",
    "We know \n",
    "- $s \\equiv m' \\bmod (s - m') \\iff s - (s - m') \\equiv m' \\bmod (s - m') \\iff m' \\equiv m' \\bmod (s - m')$\n",
    "- Therefore the attacker sends $(N', e') = (s-m', 1)$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "(p, q), (N, e) = key_creation()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = b'secret_message'\n",
    "s = rsa_ds_sign(m, p, q, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#compute our public key\n",
    "N_ = bytes_to_long(s) - bytes_to_long(m)\n",
    "e_ = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#verif\n",
    "rsa_ds_verif(m, s, e_, N_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Resources"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- https://www.agwa.name/blog/post/duplicate_signature_key_selection_attack_in_lets_encrypt\n",
    "- https://crypto.stackexchange.com/questions/47445/rsa-duplicate-signature-attack\n",
    "- https://mailarchive.ietf.org/arch/msg/acme/F71iz6qq1o_QPVhJCV4dqWf-4Yc/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}