{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7870e6da",
   "metadata": {},
   "source": [
    "## RSA kriptosistem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "201873d5",
   "metadata": {},
   "source": [
    "RSA kriptosistem bomo predstavili v Pythonovskem zvezku. Seveda potrebujemo nekaj dodatnih orodij."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "edcc71c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from sympy import prime\n",
    "from sympy.ntheory import ecm\n",
    "from sympy.ntheory import totient\n",
    "from random import randint"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb499fff",
   "metadata": {},
   "source": [
    "_prime_? praštevilo\n",
    "\n",
    "_ecm_? praštevilski razcep \n",
    "\n",
    "_totient_? Eulerjeva funkcija, alternativno ime\n",
    "\n",
    "_randint_? slučajno število"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d4ff21e",
   "metadata": {},
   "source": [
    "### Dve veliki praštevili"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aeca405b",
   "metadata": {},
   "source": [
    "Radi bi poiskati dve primerljivo veliki praštevili.\n",
    "Primerljivo veliki? Skoraj isto število binarnih/decimalnih mest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ac6b78cb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22801763489\n",
      "18054236957\n"
     ]
    }
   ],
   "source": [
    "p = prime(1000000000)\n",
    "q = prime(800000000)\n",
    "print(p)\n",
    "print(q)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbfadfae",
   "metadata": {},
   "source": [
    "Produkt praštevil *p* in *q* označimo z *n*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "010fdab5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "411668441067877062973\n"
     ]
    }
   ],
   "source": [
    "n = p*q\n",
    "print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d613f26f",
   "metadata": {},
   "source": [
    "### Eulerjeva funkcija"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df4c0906",
   "metadata": {},
   "source": [
    "S *phi* označimo Eulerjevo funkcijo števila *n = p q*.\n",
    "Ker poznamo praštevilski razcep števila *n* je naloga otročje lahka."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "45be81fe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "411668441027021062528\n"
     ]
    }
   ],
   "source": [
    "phi = (p-1)*(q-1)\n",
    "print(phi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c909a79f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{18054236957, 22801763489}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ecm(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "a598df95",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle 411668441027021062528$"
      ],
      "text/plain": [
       "411668441027021062528"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "totient(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2a0bb48",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">Naše število je dovolj majhno, da zna njegov razcep oziroma Eulerjevo funkcijo izračunati tudi Python. To pomeni, da naši ključi v tem zgledu nikakor niso varni!</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea5df9bd",
   "metadata": {},
   "source": [
    "### Konstrukcija javnega in privatnega ključa"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb6ec424",
   "metadata": {},
   "source": [
    " Izberimo si poljubno število *d*, manjše od *phi*, ki je **tuje** *phi*. Poskusimo s slučajnim številom."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "7458e708",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "88859890694783175795\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "d = randint(1,n)\n",
    "print(d)\n",
    "print(math.gcd(d, phi))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9102d0cb",
   "metadata": {},
   "source": [
    "\n",
    "Par *(n,d)* je Borutov privatni ključ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "a04fcb3d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(411668441067877062973, 88859890694783175795)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(n,d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b4968b5",
   "metadata": {},
   "source": [
    "Določimo naravno število *e*, ki reši diofansko enačbo: *e d = 1 + k phi*. Ker sta _d_ in _phi_ tuji števili, je ta LDE rešljiva.\n",
    "\n",
    "Z drugimi besedami, produkt *e d* je po modulu *phi* kongruenten *1*. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "babcf65a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "275253687879854124347\n"
     ]
    }
   ],
   "source": [
    "e = pow(d, -1, phi)\n",
    "print(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fff66c1",
   "metadata": {},
   "source": [
    "Tole zgoraj je trik. Iskali smo _inverz_ k _d_ za množenje po modulu _phi_.  \n",
    "\n",
    "Preverimo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "5aa7be22",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "e * d % phi"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "322ffdcc",
   "metadata": {},
   "source": [
    "Par (n,e) je Borutov javni ključ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "8b152963",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(411668441067877062973, 275253687879854124347)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(n,e)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4746a426",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">Zelo pomembno se je znebiti števila *phi*.\n",
    "Ravno tako moramo paziti, da nihče ne more do privatnega ključa.</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d1f05f2",
   "metadata": {},
   "source": [
    "### Prenos kriptiranih podatkov"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d16bc77",
   "metadata": {},
   "source": [
    "\n",
    "Ančka bi rada Borutu poslala sporočilo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d52aa250",
   "metadata": {},
   "source": [
    "Sporočilo, ki ga Ančka počilja Borutu mora biti kratko. Manjše od *n*. To ne predstavlja nobenega problema. Če je sporočilo daljše, ga Ančka lahko razseka na ustrezno kratke dele."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "8586a54c",
   "metadata": {},
   "outputs": [],
   "source": [
    "sporocilo = 12345678987654321"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0377d625",
   "metadata": {},
   "source": [
    " <span style=\"color:blue\">Sporočilo Ančka zaklene z Borutovim javnim ključem.\n",
    " Potencira ga na potenco *e* in določi ostanek pri deljenju z *n*.</span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "054a4091",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "362266224501015323438\n"
     ]
    }
   ],
   "source": [
    "zaklenjenosporocilo = pow(sporocilo,e,n)\n",
    "print(zaklenjenosporocilo)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c01b100",
   "metadata": {},
   "source": [
    " Zaklenjeno sporočilo lahko pošlje Borutu po nezavarovanem kanalu. Odklene ga lahko samo Borut."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d4c1df4",
   "metadata": {},
   "source": [
    " <span style=\"color:blue\">Borut sporočilo odklene s svojim privatnim ključem. Potencira ga na potenco *d* in določi ostanek pri deljenju z *n*.</span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "d603e600",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12345678987654321\n"
     ]
    }
   ],
   "source": [
    "odklenjenosporocilo = pow(zaklenjenosporocilo,d,n)\n",
    "print(odklenjenosporocilo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "9f752937",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sporocilo == odklenjenosporocilo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f3e2610",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}