Answers2_7013.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Κρυπτογραφία\n",
    "## Ομάδα Ασκήσεων 2\n",
    "###  Ανακοίνωση Παρασκευή 30/12/2016 - Προθεσμία Δευτέρα 30/01/2017 \n",
    "### Γεώργιος Στεφανίδης, Σοφία Πετρίδου"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 1\n",
    "### Κρυπτοσύστημα RSA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Υλοποιείστε τη συνάρτηση **keygen(bits)** για τη δημιουργία των κλειδιών RSA η οποία θα δέχεται ως είσοδο το πλήθος των bit των κλειδιών (με τιμές στο διάστημα [512,1024]) και θα επιστρέφει τα κλειδιά: δημόσιο και ιδιωτικό.\n",
    "2. Υλοποιείστε τη συνάρτηση **rsa_enc(m,e,n)** για τη λειτουργία κρυπτογράφησης RSA η οποία θα δέχεται ως είσοδο το μήνυμα $m$ και το δημόσιο κλειδί $(e, n)$ και θα επιστρέφει το κρυπτοκείμενο.\n",
    "3. Υλοποιείστε τη συνάρτηση **rsa_dec(c,d,n)** για τη λειτουργία αποκρυπτογράφησης RSA η οποία θα δέχεται ως είσοδο το κρυπτοκείμενο $c$, το ιδιωτικό κλειδί $d$ και το modulus $n$ και θα επιστρέφει το απλό κείμενο.\n",
    "4. Υλοποιείστε τη συνάρτηση **str2num(s):** για τη λειτουργία κωδικοποίησης βάσει του εκτεταμένου ASCII η οποία θα δέχεται ως είσοδο μια συμβολοσειρά $s$ και θα επιστρέφει έναν μεγάλο ακέραιο.\n",
    "5. Υλοποιείστε τη συνάρτηση **num2str(n):** για τη λειτουργία αποκωδικοποίησης βάσει του εκτεταμένου ASCII η οποία θα δέχεται ως είσοδο έναν μεγάλο ακέραιο $n$ και θα επιστρέφει τη συμβολοσειρά στην οποία αντιστοιχεί. \n",
    "6. Μέσα από κατάλληλες κλήσεις και έχοντας ορίσει ένα απλό κείμενο της επιλογής σας δείξτε τις λειτουργίες κρυπτογράφησης και αποκρυπτογράφησης."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Υλοποιείστε τη συνάρτηση keygen(bits) για τη δημιουργία \n",
    "# των κλειδιών RSA η οποία θα δέχεται ως είσοδο το πλήθος \n",
    "# των bits των κλειδιών  (με τιμές στο διάστημα [512,1024])\n",
    "# και θα επιστρέφει τα κλειδιά: δημόσιο και ιδιωτικό.\n",
    "\n",
    "def keygen(bits):\n",
    "    if (bits in range(512, 1025)):  # [512, 1024]\n",
    "        p = next_prime(ZZ.random_element(2^(bits//2 +1)))\n",
    "        q = next_prime(ZZ.random_element(2^(bits//2 +1)))\n",
    "        n = p*q\n",
    "    \n",
    "        phi_n = (p-1) * (q-1)\n",
    "        while True:\n",
    "            #random_element: if two integers are given, return an integer between x and y−1 inclusive\n",
    "            e = ZZ.random_element(1,phi_n)\n",
    "            if gcd(e,phi_n) == 1: \n",
    "                break\n",
    "    \n",
    "        # private key\n",
    "        d = inverse_mod(e,phi_n)\n",
    "    \n",
    "        # confirm the relationship between public and private key\n",
    "        if (e*d)%phi_n == 1:\n",
    "            return n, e, d, p, q\n",
    "        else:\n",
    "            return \"Error on public and private key confirmation\"\n",
    "    else:\n",
    "        return \"Select bits in range [512, 1024]\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Υλοποιείστε τη συνάρτηση rsa_enc(m,e,n) για τη λειτουργία \n",
    "# κρυπτογράφησης RSA η οποία θα δέχεται ως είσοδο το μήνυμα  \n",
    "# m  και το δημόσιο κλειδί e,n και θα επιστρέφει το κρυπτοκείμενο.\n",
    "\n",
    "def rsa_enc(m, e, n):\n",
    "    # encryption\n",
    "    cipher = power_mod(m, e, n)\n",
    "    #print \"The ciphertext is:\", cipher\n",
    "\n",
    "    return cipher\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Υλοποιείστε τη συνάρτηση rsa_dec(c,d,n) για τη λειτουργία \n",
    "# αποκρυπτογράφησης RSA η οποία θα δέχεται ως είσοδο το \n",
    "# κρυπτοκείμενο c, το ιδιωτικό κλειδί d και το modulus\n",
    "# n και θα επιστρέφει το απλό κείμενο.\n",
    "\n",
    "def rsa_dec(c, d, n):\n",
    "    # decryption\n",
    "    plain = power_mod(c, d, n)\n",
    "    #print \"The plaintext is:\", plain\n",
    "    \n",
    "    return plain\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Υλοποιείστε τη συνάρτηση str2num(s): για τη λειτουργία\n",
    "# κωδικοποίησης βάσει του εκτεταμένου ASCII η οποία θα\n",
    "# δέχεται ως είσοδο ένα κείμενο s και θα επιστρέφει \n",
    "# έναν μεγάλο ακέραιο.\n",
    "\n",
    "def str2num(s):\n",
    "    # Convert a text string into a large integer\n",
    "    \n",
    "    # returns the ascii code of each character\n",
    "    pl = map(ord, s)\n",
    "\n",
    "    # compute a large integer of base 256\n",
    "    plint = ZZ(pl, 256) \n",
    "    \n",
    "    return plint\n",
    "         "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'>\\x03\\x84\\x9b!\\xf7\\x1bc'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Υλοποιείστε τη συνάρτηση num2str(n): για τη λειτουργία \n",
    "# αποκωδικοποίησης βάσει του εκτεταμένου ASCII η οποία θα \n",
    "# δέχεται ως είσοδο έναν μεγάλο ακέραιο n και θα επιστρέφει\n",
    "# το κείμενο στο οποίο αντιστοιχεί.\n",
    "\n",
    "def num2str(n):\n",
    "    # Convert a large integer into a text string\n",
    "\n",
    "    # retrieve the digits of the large integer of base 256\n",
    "    d256 = n.digits(256)\n",
    "\n",
    "    # convert the ascii codes to characters\n",
    "    ms = map(chr, d256)\n",
    "    msready = ''.join(ms)\n",
    "   \n",
    "    return msready\n",
    "num2str(7141573357841154878)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Αρχικό μήνυμα:\n",
      "Jingle Bells, Jingle Bells, Jingle all the way! \n",
      "Oh, What fun it is to ride In a one horse open sleigh.\n",
      "\n",
      "\n",
      "Κωδικοποιημένο μήνυμα(ASCII):\n",
      "1138987172800590827767025767326657538290012739689310337163360131191803995732089474814209043684625585430473794485964074075134524503194260062112334041019084679897581119456930173357425650199241035443976045000632248060541720116728572219340999846773287242\n",
      "\n",
      "Κρυπτοκείμενο:\n",
      "7814747436780998495053920855748339550582620086074816942367414305477701772113584060452643979834986625189026848152190217217103575539133104204109196855384660942169632236463947793050167784939856741287640361922233125798925110403238472005563847384068035645174903918399285638966320956631603671544410307242225451462\n",
      "\n",
      "plaintext (ASCII):\n",
      "1138987172800590827767025767326657538290012739689310337163360131191803995732089474814209043684625585430473794485964074075134524503194260062112334041019084679897581119456930173357425650199241035443976045000632248060541720116728572219340999846773287242\n",
      "\n",
      "Ανάκτηση κειμένου:\n",
      "Jingle Bells, Jingle Bells, Jingle all the way! \n",
      "Oh, What fun it is to ride In a one horse open sleigh.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Μέσα από κατάλληλες κλήσεις και έχοντας ορίσει ένα απλό \n",
    "#κείμενο της επιλογής σας δείξτε τις λειτουργίες \n",
    "# κρυπτογράφησης και αποκρυπτογράφησης.\n",
    "\n",
    "m = \"Jingle Bells, Jingle Bells, Jingle all the way! \\nOh, What fun it is to ride In a one horse open sleigh.\\n\" #16<128, 32<256, 64<512\n",
    "print \"Αρχικό μήνυμα:\\n\", m\n",
    "\n",
    "# επιλογή bits για δημιουργία κλειδιού ώστε να μην υπάρχει σφάλμα στην κωδικοποίηση.\n",
    "if len(m)<64:\n",
    "    bits = 512\n",
    "else:\n",
    "    bits = 1024\n",
    "    \n",
    "n, e, d, p, q = keygen(bits)\n",
    "\n",
    "encoded = str2num(m)\n",
    "print \"\\nΚωδικοποιημένο μήνυμα(ASCII):\\n\", encoded\n",
    "\n",
    "cipher = rsa_enc(encoded, e, n)\n",
    "print \"\\nΚρυπτοκείμενο:\\n\", cipher\n",
    "\n",
    "plain = rsa_dec(cipher, d, n)\n",
    "print \"\\nplaintext (ASCII):\\n\", plain\n",
    "\n",
    "text = num2str(plain)\n",
    "print \"\\nΑνάκτηση κειμένου:\\n\", text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 2\n",
    "### Το Κινέζικο Θεώρημα Υπολοίπων"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Επιταχύνετε τη διαδικασία αποκρυπτογράφησης του RSA με χρήση του Κινέζικου Θεωρήματος υπολοίπων (CRT). Υλοποιείστε τη συνάρτηση **rsa_decrt(c,d,p,q)** για τη λειτουργία αποκρυπτογράφησης RSA η οποία θα δέχεται ως είσοδο το κρυπτοκείμενο $c$, το ιδιωτικό κλειδί $d$ και τους πρώτους $p, q$ και θα επιστρέφει το απλό κείμενο.\n",
    "2. Μέσα από κατάλληλες κλήσεις των συναρτήσεων της Άσκησης 1 (με εξαίρεση την **rsa_dec**) και της συνάρτησης **rsa_decrt** και έχοντας ορίσει ένα απλό κείμενο της επιλογής σας δείξτε τις λειτουργίες κρυπτογράφησης και αποκρυπτογράφησης."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ερώτημα 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Επιταχύνετε τη διαδικασία αποκρυπτογράφησης του RSA με χρήση του \n",
    "# Κινέζικου Θεωρήματος υπολοίπων (CRT). Υλοποιείστε τη συνάρτηση \n",
    "# rsa_decrt(c,d,p,q) για τη λειτουργία αποκρυπτογράφησης RSA η οποία \n",
    "# θα δέχεται ως είσοδο το κρυπτοκείμενο c, το ιδιωτικό κλειδί d και \n",
    "# τους πρώτους p,q και θα επιστρέφει το απλό κείμενο.\n",
    "\n",
    "\n",
    "def rsa_decrt(c, d, p, q):\n",
    "    n = p*q\n",
    "    \n",
    "    # 1. Αναγωγή\n",
    "    cp = c%p # cp = c mod p \n",
    "    cq = c%q # cq = c mod q\n",
    "    \n",
    "    # 2. Υπολογισμοί στα Ζp, Zq\n",
    "    dp = d%(p-1) # dp = d mod ϕ(p) = d mod (p−1)\n",
    "    dq = d%(q-1) # dq = d mod ϕ(q) = d mod (q−1)\n",
    "    mp = power_mod(cp,dp,p) #(cp^dp)%p # mp = cp^dp mod p \n",
    "    mq = power_mod(cq,dq,q) #(cq^dq)%q # mq = cq^dq mod q\n",
    "    \n",
    "    # 3. Σύνθεση βάση του CRT\n",
    "    tp = inverse_mod(q, p) # tp = q^(−1) mod p\n",
    "    tq = inverse_mod(p, q) # tq = p^(−1) mod q\n",
    "    plain = (q*tp*mp + p*tq*mq)%n # m = q tp mp + p tq mq mod n\n",
    "    \n",
    "    #print \"1.\\ncp =\", cp, \"\\ncq =\", cq\n",
    "    #print \"\\n\\n2.\\ndp =\", dp, \"\\ndq =\", dq, \"\\nmp =\", mp, \"\\nmq =\",mq\n",
    "    #print \"\\n\\n3.\\ntp =\", tp, \"\\ntq =\", tq\n",
    "    #print \"\\n*************************************************\\n\"\n",
    "    #print \"Result: \\n\", plain\n",
    "    return plain\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ερώτημα 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Αρχικό μήνυμα:\n",
      "We wish you a Merry Christmas\n",
      "We wish you a Merry Christmas\n",
      "We wish you a Merry Christmas and a Happy New Year!\n",
      "\n",
      "Κωδικοποιημένο μήνυμα(ASCII):\n",
      "269619152943156212056292919344345900472320515461865345723041367497646027239701117707520573154398742638615854002975863734179730465876526606289821181787371586584730773609339876770916632654600776996482007918986210010789712014286137333777135951744428809128114879190820183\n",
      "\n",
      "Κρυπτοκείμενο:\n",
      "27839118114798857294528879508860898492994716075088213458872517232443079244778153075293464556989460395460580433354929038257179788761802831141794276522420928345300612904984667733466239332396618684630464746540770324549486582342186058394668353057085613326035476295421089411460429143758756653947912554863898543629\n",
      "\n",
      "plaintext (ASCII):\n",
      "269619152943156212056292919344345900472320515461865345723041367497646027239701117707520573154398742638615854002975863734179730465876526606289821181787371586584730773609339876770916632654600776996482007918986210010789712014286137333777135951744428809128114879190820183\n",
      "\n",
      "Ανάκτηση κειμένου:\n",
      "We wish you a Merry Christmas\n",
      "We wish you a Merry Christmas\n",
      "We wish you a Merry Christmas and a Happy New Year!\n"
     ]
    }
   ],
   "source": [
    "# Κρυπτογράφηση και αποκρυπτογράφηση\n",
    "\n",
    "m = \"We wish you a Merry Christmas\\nWe wish you a Merry Christmas\\nWe wish you a Merry Christmas and a Happy New Year!\"\n",
    "print \"Αρχικό μήνυμα:\\n\", m\n",
    "\n",
    "# επιλογή bits για δημιουργία κλειδιού ώστε να μην υπάρχει σφάλμα στην κωδικοποίηση.\n",
    "if len(m)<64:\n",
    "    bits = 512\n",
    "else:\n",
    "    bits = 1024\n",
    "    \n",
    "n, e, d, p, q = keygen(bits)\n",
    "\n",
    "encoded = str2num(m)\n",
    "print \"\\nΚωδικοποιημένο μήνυμα(ASCII):\\n\", encoded\n",
    "\n",
    "cipher = rsa_enc(encoded, e, n)\n",
    "print \"\\nΚρυπτοκείμενο:\\n\", cipher\n",
    "\n",
    "plain = rsa_decrt(cipher, d, p, q) # Αποκρυπτογράφηση με CRT\n",
    "print \"\\nplaintext (ASCII):\\n\", plain\n",
    "\n",
    "\n",
    "text = num2str(plain)\n",
    "print \"\\nΑνάκτηση κειμένου:\\n\", text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 3\n",
    "### Επίθεση κοινού modulus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Υλοποιείστε τη συνάρτηση **crack_rsa_comoda(p,q,e1,e2,c1,c2)** για την επίδειξη μιας επίθεσης κοινού modulus. Δημιουργείστε ένα δικό σας ρεαλιστικό σενάριο στο οποίο η συνάρτηση θα δέχεται ως είσοδο τους πρώτους $p,q$, τους δημόσιους εκθέτες $e_1,e_2$ και τα κρυπτοκείμενα $c_1,c_2$ και θα επιστρέφει το απλό κείμενο $m$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "500"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# επίθεση κοινού modulus\n",
    "\n",
    "def crack_rsa_comoda(p,q,e1,e2,c1,c2):\n",
    "    g, s, t = xgcd(e1, e2)\n",
    "    n = p*q\n",
    "    m = (c1^s * c2^t)%(n)\n",
    "    return m \n",
    "\n",
    "# Παράδειγμα εργαστηρίου 7.\n",
    "crack_rsa_comoda(37,43,17,5,849,22)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 4\n",
    "### Ανταλλαγή κλειδιών Diffie-Hellman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Υλοποιείστε τη συνάρτηση **generate_parameters(bits)** η οποία δέχεται ως είσοδο το πλήθος των bits ενός μεγάλου πρώτου $p$ και επιστρέφει 4 τιμές: $p, q, g$ και $F$. Θα πρέπει τα $p$ και $q$ να είναι πρώτοι αριθμοί τέτοιοι ώστε $p = 2*q + 1$, $g$ θα είναι ένας ακέραιος γεννήτορας του $\\mathbb{Z_p}^{*}$ και $F$ ένα πεπερασμένο σώμα με $p$ στοιχεία.\n",
    "2. Υλοποιείστε τη συνάρτηση **public_private_pair(p,q,g,F)** η οποία παίρνει ως είσοδο την έξοδο της **generate_parameters** και επιστρέφει το ζευγάρι τιμών $(X, x)$, όπου $X = g^x \\bmod p$ και $x \\in \\{2, \\ldots, p-2\\}$.\n",
    "3. Υλοποιείστε τη συνάρτηση **generate_secret(X,y)** η οποία παίρνει ως είσοδο τη δημόσια πληροφορία του άλλου μέλους της επικοινωνίας κατά την ανταλλαγή DH και τον ιδιωτικό εκθέτη και επιστρέφει το κοινό μυστικό κλειδί.\n",
    "4. Χρησιμοποιώντας τις παραπάνω συναρτήσεις δείξτε την ανταλλαγή κλειδιών DH."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Υλοποιείστε τη συνάρτηση generate_parameters(bits) η οποία \n",
    "# δέχεται ως είσοδο το πλήθος των bits ενός μεγάλου πρώτου p\n",
    "# και επιστρέφει 4 τιμές: p, q, g και F. Θα πρέπει τα p και q \n",
    "# να είναι πρώτοι αριθμοί τέτοιοι ώστε p=2∗q+1, g θα είναι \n",
    "# ένας ακέραιος γεννήτορας του ℤp∗ και F ένα πεπερασμένο σώμα\n",
    "# με p στοιχεία.\n",
    "def generate_parameters(bits):\n",
    "    p = 1\n",
    "    while not is_prime(p):\n",
    "        q = next_prime(ZZ.random_element(2^(bits//2 +1)))\n",
    "        p = 2*q + 1  # αν είναι πρώτος δηλαδή όταν πετύχω πρώτο αριθμό τότε φεύγω και δουλεύω με αυτά.\n",
    "\n",
    "    F = GF(p)\n",
    "    Zp = IntegerModRing(p)\n",
    "\n",
    "    # find a generator g\n",
    "    g = F(2)\n",
    "    if multiplicative_order(Zp(g)) != (p-1): # ή q δηλαδη (p-1)\\2 ή p-1\n",
    "        g = F(Mod(-2, p))\n",
    "\n",
    "    return p, q, g, F\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Υλοποιείστε τη συνάρτηση public_private_pair(p,q,g,F) η οποία\n",
    "# παίρνει ως είσοδο την έξοδο της generate_parameters και \n",
    "# επιστρέφει το ζευγάρι τιμών (X,x), όπου  X = g^x mod p \n",
    "# και x∈{2,…,p−2}.\n",
    "\n",
    "def public_private_pair(p, q, g, F):\n",
    "    x = F(randint(2,p-1))\n",
    "    X = g^x\n",
    "    \n",
    "    return X, x\n",
    "#p, q, g, F = generate_parameters(100)\n",
    "#print public_private_pair(p, q, g, F)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Υλοποιείστε τη συνάρτηση generate_secret(X,y) η οποία παίρνει \n",
    "# ως είσοδο τη δημόσια πληροφορία του άλλου μέλους της \n",
    "# επικοινωνίας κατά την ανταλλαγή DH και την ιδιωτικό εκθέτη και\n",
    "# επιστρέφει το κοινό μυστικό κλειδί.\n",
    "def generate_secret(X,y):\n",
    "    return X^y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice computes her secret value 46741 and public value: 17996\n",
      "\n",
      "Bob computes his secret value 110750 and public value: 70741\n",
      "\n",
      "Alice shared secret key: 64358\n",
      "\n",
      "Bob's shared secret key: 64358\n"
     ]
    }
   ],
   "source": [
    "# Χρησιμοποιώντας τις παραπάνω συναρτήσεις δείξτε την ανταλλαγή κλειδιών DH.\n",
    "\n",
    "p, q, g, F = generate_parameters(32)\n",
    "\n",
    "# Alice computes secret and public value\n",
    "A, x = public_private_pair(p, q, g, F)\n",
    "print \"Alice computes her secret value\", x, \"and public value:\", A\n",
    "\n",
    "# Bob computes secret and public value\n",
    "B, y = public_private_pair(p, q, g, F)\n",
    "print \"\\nBob computes his secret value\", y, \"and public value:\", B \n",
    "    \n",
    "# Alice generates shared secret\n",
    "print \"\\nAlice shared secret key:\", generate_secret(B, x)\n",
    "\n",
    "# Bob generates shared secret\n",
    "print \"\\nBob's shared secret key:\", generate_secret(A, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 5\n",
    "### Πρωτόκολλο κρυπτογράφησης El Gamal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Κωδικοποιείστε κατάλληλα το μήνυμα \"Next Monday\" και εν συνεχεία κρυπτογραφήστε το με το κρυπτοσύστημα El Gamal. Εν συνεχεία προβείτε σε αποκρυπτογράφηση και αποδωδικοποίηση προκειμένου να ανακτήσετε το αρχικό μήνυμα. Επιλέξτε έναν τυχαίο πρώτο $p$ τάξης $128$ bits, ενώ για την επιλογή μιας μεγάλης υποομάδας του $\\mathbb{Z}_p$ χρησιμοποιείστε την εντολή \"g=mod(primitive_root(p),p)\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p -> 1151726803702102851091632403478259831647 \n",
      "g -> 5\n",
      "Κρυπτοκείμενο c -> 406016748137904633912821552207916773604\n",
      "Message is: Next Monday\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# Κωδικοποιείστε κατάλληλα το μήνυμα \"Next Monday\" και εν συνεχεία κρυπτογραφήστε \n",
    "# το με το κρυπτοσύστημα El Gamal. Εν συνεχεία προβείτε σε αποκρυπτογράφηση και \n",
    "# αποδωδικοποίηση προκειμένου να ανακτήσετε το αρχικό μήνυμα. Επιλέξτε έναν τυχαίο \n",
    "# πρώτο p τάξης 128 bits, ενώ για την επιλογή μιας μεγάλης υποομάδας του  \n",
    "# ℤp χρησιμοποιείστε την εντολή \"g=mod(primitive_root(p),p)\".\n",
    "\n",
    "m = \"Next Monday\"\n",
    "\n",
    "# Κωδικοποίηση\n",
    "ms = str2num(m)\n",
    "\n",
    "# Υπολογίζω τους πρώτους\n",
    "p = generate_parameters(256)[0] # παίρνω μόνο την πρώτη επιστρεφόμενη τιμή δηλαδή το p.\n",
    "g = int(mod(primitive_root(p),p))\n",
    "    \n",
    "\n",
    "print \"p ->\", p, \"\\ng ->\", g\n",
    "\n",
    "# O Bob υπολογίζει\n",
    "d = Kprb = randint(2, p-2)  # random int {2, p-2}\n",
    "b = power_mod(g, d, p) # στέλνει p, g, b\n",
    "\n",
    "# Η Alice υπολογίζει\n",
    "i = randint(2, p-2)  # random int {2, p-2}\n",
    "Ke = power_mod(g, i, p)\n",
    "KmA = power_mod(b, i, p)\n",
    "\n",
    "c = power_mod((ms*KmA), 1, p) # στέλνει Ke, c\n",
    "print \"Κρυπτοκείμενο c ->\", c\n",
    "\n",
    "# Bob \n",
    "KmB = power_mod(Ke, d, p)\n",
    "\n",
    "# Αποκρυπτογραφεί\n",
    "inv = inverse_mod(KmB, p) # αντίστροφος\n",
    "pln = power_mod(c*inv, 1, p) # (c*(inverse_mod(KmB, p)))%p\n",
    "\n",
    "# Αποκωδικοποίηση\n",
    "msg = num2str(pln)\n",
    "\n",
    "print \"Message is:\", msg\n",
    "print m == msg   # έλεγχος\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 6\n",
    "### Το Πρόβλημα του Διακριτού Λογαρίθμου (DLP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Έστω $p = 499$, $g = 7$ και $X = 297$. Να βρεθεί $x$ τέτοιο ώστε $X = g^x$.\n",
    "2. Έστω $p = 863$, $g = 5$, $X=543$ και $Y=239$. Να βρεθούν $x$ και $y$ τέτοια ώστε $X = g^x$ και $Y = g^y$.\n",
    "3. Έστω $p = 7589$, $g = 2$, $X = 6075$ και $Y = 1318$. Να βρεθεί το κοινό μυστικό κλειδί σε μια ανταλλαγή κλειδιού DH με αυτές τις παραμέτρους."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ερώτημα 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "362\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# Έστω p = 499, g = 7 και X = 297. Να βρεθεί x τέτοιο ώστε X = g^x.\n",
    "\n",
    "p = 499\n",
    "F = GF(p)\n",
    "g = F(7)\n",
    "\n",
    "X = F(297)\n",
    "x = X.log(g)\n",
    "print x\n",
    "\n",
    "print g^x == X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ερώτημα 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "641\n",
      "762\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# Έστω p = 863, g = 5, X = 543 και Y = 239. Να βρεθούν x και y τέτοια ώστε X = g^x και Y = g^y.\n",
    "\n",
    "p = 863\n",
    "F = GF(p)\n",
    "g = F(5)\n",
    "\n",
    "X = F(297)\n",
    "Y = F(239)\n",
    "\n",
    "x = X.log(g)\n",
    "print x\n",
    "\n",
    "y = Y.log(g)\n",
    "print y\n",
    "\n",
    "print g^x == X\n",
    "print g^y == Y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ερώτημα 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Common secret key computed by X: 6803\n",
      "Common secret key computed by Y: 6803\n"
     ]
    }
   ],
   "source": [
    "# Έστω p = 7589, g = 2, X = 6075 και Y = 1318. Να βρεθεί το κοινό μυστικό \n",
    "# κλειδί σε μια ανταλλαγή κλειδιού DH με αυτές τις παραμέτρους.\n",
    "\n",
    "p = 7589\n",
    "F = GF(p)\n",
    "g = F(2)\n",
    "\n",
    "X = F(6075)\n",
    "Y = F(1318)\n",
    "\n",
    "x = X.log(g)\n",
    "y = Y.log(g)\n",
    "\n",
    "print \"Common secret key computed by X:\", Y^x\n",
    "print \"Common secret key computed by Y:\", X^y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 7\n",
    "### Ανταλλαγή κλειδιών – ECDH"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Δίνονται: \n",
    "* μια ελλειπτική καμπύλη $E(\\mathbb{F}_p)$, όπου $p=63709$, με εξίσωση $Y^2 = X^3 + 26484*X + 15456$\n",
    "* μια μεγάλη υποομάδα της με τάξη $q = 63839 \\le order(E)$\n",
    "* ένα σημείο βάσης $G=(53819, 6786)$ (= γεννήτορας της υποομάδας)\n",
    "\n",
    "Αναπτύξτε:\n",
    "1. μια συνάρτηση που θα δέχεται μια καμπύλη Ε, ένα σημείο βάσης P επί της Ε και θα επιστρέφει (παράγει) τον ιδιωτικό βαθμωτό πολλαπλασιαστή (ιδιωτικό κλειδί) x και τo δημόσιο κλειδί (σημείο) X.\n",
    "2. μια συνάρτηση που θα δέχεται το δημόσιο και ιδιωτικό κλειδί και θα υπολογίζει το (κοινό) μυστικό κλειδί-σημείο\n",
    "3. εφαρμόστε τις συναρτήσεις αυτές προκειμένου να προσομοιώσετε μια ανταλλαγή κλειδιών (ECDH) για τις παραπάνω παραμέτρους."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# μια συνάρτηση που θα δέχεται μια καμπύλη Ε, ένα σημείο βάσης P επί της Ε και θα επιστρέφει \n",
    "#(παράγει) τον ιδιωτικό βαθμωτό πολλαπλασιαστή (ιδιωτικό κλειδί) x και τo δημόσιο κλειδί (σημείο) X.\n",
    "\n",
    "def computeXx(E, P):\n",
    "    # Υπολογίζει τον ιδιωτικό πολλαπλασιαστή και το δημόσιο κλειδί.\n",
    "    x = randint(2, P.order()) # τυχαίος στο διάστημα (2 έως G.order()), ιδιωτικός πολλαπλασιαστής\n",
    "    X = x*P # δημόσιο κλειδί\n",
    "    return X, x\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# μια συνάρτηση που θα δέχεται το δημόσιο και ιδιωτικό κλειδί και θα υπολογίζει \n",
    "# το (κοινό) μυστικό κλειδί-σημείο\n",
    "\n",
    "def computeCommonSecretKey(Y, x):\n",
    "    # Υπολογίζει το κοινό μυστικό κλειδί.\n",
    "    return x*Y\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Ερώτημα 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "\n",
      "Μυστικός πολλαπλασιαστής του Bob: 45722\n",
      "Μυστικός πολλαπλασιαστής της Alice: 60133\n",
      "\n",
      "Δημόσιο κλειδί του Bob: (42696 : 16005 : 1)\n",
      "Δημόσιο κλειδί της Alice: (61227 : 41530 : 1)\n",
      "\n",
      "Κοινή μυστική πληροφορία του Bob: (27785 : 62887 : 1)\n",
      "Κοινή μυστική πληροφορία της Alice: (27785 : 62887 : 1) \n",
      "\n",
      "((61227 : 41530 : 1), 60133, (42696 : 16005 : 1), 45722, (27785 : 62887 : 1), (27785 : 62887 : 1))\n"
     ]
    }
   ],
   "source": [
    "# Εφαρμόστε τις συναρτήσεις αυτές προκειμένου να προσομοιώσετε μια ανταλλαγή\n",
    "# κλειδιών (ECDH) για τις παραπάνω παραμέτρους.\n",
    "\n",
    "\n",
    "def ECDHKeyExchange(E, G):\n",
    "    # Η συνάρτηση προσομοιώνει την ανταλλαγή κλειδιών ECDH\n",
    "    A, a = computeXx(E, G)\n",
    "    B, b = computeXx(E, G)\n",
    "    \n",
    "    Qa = computeCommonSecretKey(A, b)\n",
    "    Qb = computeCommonSecretKey(B, a)\n",
    "    \n",
    "    if Qa == Qb:\n",
    "        print \"\\nΜυστικός πολλαπλασιαστής του Bob:\", b\n",
    "        print \"Μυστικός πολλαπλασιαστής της Alice:\", a\n",
    "        print \"\\nΔημόσιο κλειδί του Bob:\", B\n",
    "        print \"Δημόσιο κλειδί της Alice:\", A\n",
    "        print \"\\nΚοινή μυστική πληροφορία του Bob:\", Qb\n",
    "        print \"Κοινή μυστική πληροφορία της Alice:\", Qa, \"\\n\"\n",
    "    else:\n",
    "        return \"Something is wrong...\"\n",
    "    \n",
    "    return A, a, B, b, Qa, Qb\n",
    "\n",
    "##\n",
    "## Καμπύλη με εξίσωση Y^2 = X^3 + 26484 ∗ X + 15456\n",
    "## \n",
    "\n",
    "p = 63709\n",
    "K = GF(p)\n",
    "E = EllipticCurve(K, [26484,15456]) # y^2 = x^3 + 26484x + 15456 στο GF(63709)\n",
    "\n",
    "G = E(53819, 6786) # γεννήτορας\n",
    "q = 63839 # Η τάξη αυτής της υποομάδας είναι πρώτος και ίση με την τάξη της καμπύλης και του γεννήτορα.\n",
    "\n",
    "print G.order() == E.order() == q\n",
    "print is_prime(q)\n",
    "\n",
    "\n",
    "print ECDHKeyExchange(E, G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 8\n",
    "### Κρυπτοσύστημα ελλειπτικού El Gamal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Έστω η ελλειπτική καμπύλη $Ε: Y^2 = X^3 + X + 6$ πάνω στο $\\mathbb{F}_{11}$.\n",
    "1. Προσδιορίστε τα σημεία της.\n",
    "2. Επειδή κάθε ομάδα με τάξη πρώτο αριθμό είναι κυκλική και από το ερώτημα (1) έχετε διαπιστώσει ότι η τάξη της $Ε$ είναι $13$, έπεται ότι κάθε σημείο της εκτός από το $\\mathcal{O}$ είναι ένας γεννήτορας. Υποθέστε ότι επιλέγουμε ως γεννήτορα το $G= (2, 7)$ και υπολογίστε όλα τα πολλαπλάσια (δυνάμεις) του G αντιστοιχίζοντάς τα με τα σημεία της $Ε(\\mathbb{F}_{11})$.\n",
    "3. Υποθέστε τώρα ότι η Alice και ο Bob συμφωνούν να χρησιμοποιήσουν το κρυπτοσύστημα ελλειπτικού ElGamal με ελλειπτική καμπύλη την $Ε$ και το σημείο $G \\in Ε(\\mathbb{F}_{11})$. Περιγράψτε τις διαδικασίες κρυπτογράφησης και αποκρυπτογράφησης σε περίπτωση που ο Bob θελήσει να στείλει το μήνυμα $m=(10, 9)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ερώτημα 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Σημεία της καμπύλης:\n",
      "[(0 : 1 : 0), (2 : 4 : 1), (2 : 7 : 1), (3 : 5 : 1), (3 : 6 : 1), (5 : 2 : 1), (5 : 9 : 1), (7 : 2 : 1), (7 : 9 : 1), (8 : 3 : 1), (8 : 8 : 1), (10 : 2 : 1), (10 : 9 : 1)]\n",
      "\n",
      "Τάξη της καμπύλης: 13\n"
     ]
    }
   ],
   "source": [
    "# Προσδιορίστε τα σημεία της καμπύλης με εξίσωση Y^2 = X^3 + X + 6 στο F11\n",
    "\n",
    "p = 11\n",
    "K = GF(p)\n",
    "E = EllipticCurve(K, [1, 6]) # y^2 = x^3 + x + 6 στο GF(11)\n",
    "\n",
    "#G = E(53819, 6786) # γεννήτορας\n",
    "#q = 63839 # Η τάξη αυτής της υποομάδας είναι πρώτος και ίση με την τάξη της καμπύλης και του γεννήτορα.\n",
    "\n",
    "#print G.order() == E.order() == q\n",
    "#print is_prime(q)\n",
    "\n",
    "print \"Σημεία της καμπύλης:\\n\", E.points()\n",
    "print \"\\nΤάξη της καμπύλης:\", E.order()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ερώτημα 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Τάξη της καμπύλης: 13\n",
      "True\n",
      "True\n",
      "\n",
      "\n",
      "Τα πολλαπλάσια του G θα είναι όλα το ουδέτερο στοιχείο γιατί η τάξη της ομάδας είναι ίση με την τάξη του γεννήτορα G και είναι πρώτος αριθμός.\n",
      "\n",
      "[(0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0), (0 : 1 : 0)]\n"
     ]
    }
   ],
   "source": [
    "# Επειδή κάθε ομάδα με τάξη πρώτο αριθμό είναι κυκλική και από το ερώτημα (1) έχετε διαπιστώσει ότι \n",
    "# η τάξη της Ε είναι 13, έπεται ότι κάθε σημείο της εκτός από το O είναι ένας γεννήτορας. \n",
    "# Υποθέστε ότι επιλέγουμε ως γεννήτορα το G = (2,7) και υπολογίστε όλα τα πολλαπλάσια (δυνάμεις) \n",
    "# του G αντιστοιχίζοντάς τα με τα σημεία της Ε(𝔽11).\n",
    "\n",
    "print \"Τάξη της καμπύλης:\", E.order()\n",
    "print is_prime(E.order())\n",
    "\n",
    "G = E(2,7)\n",
    "x = G.order()\n",
    "\n",
    "print x == E.order()\n",
    "print \"\\n\\nΤα πολλαπλάσια του G θα είναι όλα το ουδέτερο στοιχείο γιατί η τάξη της ομάδας είναι ίση με την τάξη του γεννήτορα G και είναι πρώτος αριθμός.\\n\"\n",
    "print [x*P for P in E] # ένα ένα τα στοιχεία της καμπύλης επί το order της ομάδας βγάζει το ουδέτερο γιατί όλα έχουν order ίσο με 13(πρώτος)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ερώτημα 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "(10 : 9 : 1) 2 (2 : 4 : 1)\n",
      "The ciphertext is:  (5 : 2 : 1) (7 : 2 : 1)\n",
      "The plaintext is:  (10 : 9 : 1)\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# Υποθέστε τώρα ότι η Alice και ο Bob συμφωνούν να χρησιμοποιήσουν το κρυπτοσύστημα ελλειπτικού ElGamal\n",
    "# με ελλειπτική καμπύλη την Ε και το σημείο G∈Ε(F11). Περιγράψτε τις διαδικασίες κρυπτογράφησης και \n",
    "# αποκρυπτογράφησης σε περίπτωση που ο Bob θελήσει να στείλει το μήνυμα m = (10,9).\n",
    "\n",
    "m = E(10,9)\n",
    "print E.is_on_curve(10, 9)\n",
    "\n",
    "# Bob chooses his private key\n",
    "r = randint(2, G.order()-1)\n",
    "\n",
    "# Bob computes and sends his public info to ALice\n",
    "Q_b = r*G\n",
    "\n",
    "# Alice chooses her private key\n",
    "k = randint(2, G.order()-1)\n",
    "\n",
    "# Alice computes her public info, encrypts and sends the message\n",
    "C_1 = k*G\n",
    "print m,k,Q_b\n",
    "C_2 = m+k*Q_b\n",
    "print \"The ciphertext is: \", C_1, C_2\n",
    "\n",
    "# Bob decrypts the message\n",
    "plaintext = C_2-r*C_1\n",
    "print \"The plaintext is: \", plaintext\n",
    "\n",
    "print m == plaintext\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 9\n",
    "### Κωδικοποίηση Koblitz και κρυπτοσύστημα ελλειπτικού El Gamal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Δίνεται μια ελλειπτική καμπύλη $E(\\mathbb{F}_p)$, όπου $p=593899$, με εξίσωση $Y^2 = X^3 + 7*X + 11$ και το μήνυμα $m=12345$. Κωδικοποιείστε κατάλληλα το μήνυμα $m$ (δηλαδή αναπαραστήστε το ως σημείο της καμπύλης) και εν συνεχεία κρυπτογραφήστε το με το κρυπτοσύστημα του ελλειπτικού El Gamal. Εν συνεχεία προβείτε σε αποκρυπτογράφηση και αποδωδικοποίηση προκειμένου να ανακτήσετε το αρχικό μήνυμα $m$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The ciphertext is:  (490038 : 203121 : 1) (487912 : 79325 : 1)\n",
      "The plaintext is:  12345\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "p = 593899\n",
    "K = GF(p)\n",
    "E = EllipticCurve(K, [7, 11]) # y^2 = x^3 + 7x + 11 στο GF(593899)\n",
    "\n",
    "m = 12345 # πρέπει να το κωδικοποιήσω ως σημείο της καμπύλης.\n",
    "\n",
    "# Κωδικοποίηση\n",
    "k = 654\n",
    "f(x) = x^3 + 7*x + 11 \n",
    "\n",
    "count = 0\n",
    "while(legendre_symbol(f(m*k+count),p)  < 1):\n",
    "    count = count +1\n",
    "\n",
    "x = m*k+count\n",
    "z = x^3 + 7*x + 11\n",
    "y = Mod(z,p).sqrt();\n",
    "\n",
    "# Ατασηναπαράση κειμένου σε ως σημείο της καμπύλης\n",
    "M = E(x, y)\n",
    "G = E.random_point()\n",
    "\n",
    "# Bob chooses his private key\n",
    "r = randint(2, G.order()-1)\n",
    "\n",
    "# Bob computes and sends his public info to Alice\n",
    "Q_b = r*G\n",
    "\n",
    "# Alice chooses her private key\n",
    "a = randint(2, G.order()-1)\n",
    "\n",
    "# Alice computes her public info, encrypts and sends the message\n",
    "C_1 = a*G\n",
    "C_2 = M+a*Q_b\n",
    "print \"The ciphertext is: \", C_1, C_2\n",
    "\n",
    "# Bob decrypts the message\n",
    "pln = C_2-r*C_1\n",
    "\n",
    "# Bob decodes the message\n",
    "plaintext =  floor(x/k) \n",
    "print \"The plaintext is: \", plaintext\n",
    "\n",
    "print m == plaintext\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Άσκηση 10\n",
    "### Ψηφιακές υπογραφές"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Δοθέντος ενός σχήματος ψηφιακών υπογραφών RSA με δημόσιο κλειδί $n = 9797, e = 131$\n",
    "* Ποιες από τις παρακάτω υπογραφές είναι έγκυρες;\n",
    "    1. $(x = 123, sig(x) = 6292)$\n",
    "    2. $(x = 4333, sig(x) = 4768)$\n",
    "    3. $(x = 4333, sig(x) = 1424)$\n",
    "* Δείξτε πώς μπορεί ο αντίπαλος να φέρει εις πέρας μια επίθεση υπαρξιακής πλαστογράφησης, δίνοντας ένα παράδειγμα με τις παραμέτρους αυτού του συστήματος."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Απάντηση"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Verified signature: 6292 gives 123\n",
      "Signature is not verified for combination ( 4768 , 4333 )\n",
      "Verified signature: 1424 gives 4333\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 9797\n",
    "e = 131\n",
    "\n",
    "def checkDigSig(n, e, x, s):\n",
    "    ms = power_mod(s,e,n)\n",
    "    if ms == x:\n",
    "        print \"Verified signature:\", s,\"gives\", x\n",
    "        return True\n",
    "    else:\n",
    "        print \"Signature is not verified for combination (\", s, \",\", x, \")\"\n",
    "        return False\n",
    "       \n",
    "# 1.(x=123,sig(x)=6292)\n",
    "checkDigSig(n, e, 123, 6292 )\n",
    "\n",
    "# 2.(x=4333,sig(x)=4768)\n",
    "checkDigSig(n, e, 4333, 4768)\n",
    "\n",
    "# 3.(x=4333,sig(x)=1424)\n",
    "checkDigSig(n, e, 4333, 1424)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Verified signature: 16994 gives 263\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Δείξτε πώς μπορεί ο αντίπαλος να φέρει εις πέρας μια επίθεση υπαρξιακής\n",
    "# πλαστογράφησης, δίνοντας ένα παράδειγμα με τις παραμέτρους αυτού του συστήματος.\n",
    "\n",
    "s = randint(1,99999) # Ότι τιμή και να έχει η υπογραφή θα βγεί έγκυρη.\n",
    "x = power_mod(s, e, n)\n",
    "\n",
    "checkDigSig(n, e, x, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.4",
   "language": "",
   "name": "sage-7.4"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}