Linear and Differential Cryptanalysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Cryptanalysis and Differential Cryptanalysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is based on the paper found in: https://eprint.iacr.org/2017/1008.pdf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import string\n",
    "import math\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## S-Boxes , P-Boxes and SPN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "Sbox_dict = {'0000': '1110', \n",
    "        '0001': '0100', \n",
    "        '0010': '1101', \n",
    "        '0011': '0001', \n",
    "        '0100': '0010', \n",
    "        '0101': '1111', \n",
    "        '0110': '1011', \n",
    "        '0111': '1000',\n",
    "        '1000': '0011', \n",
    "        '1001': '1010',\n",
    "        '1010': '0110',\n",
    "        '1011': '1100',\n",
    "        '1100': '0101',\n",
    "        '1101': '1001',\n",
    "        '1110': '0000',\n",
    "        '1111': '0111'}\n",
    "\n",
    "inverse_Sbox_dict = {'1110': '0000', \n",
    "        '0100': '0001', \n",
    "        '1101': '0010', \n",
    "        '0001': '0011', \n",
    "        '0010': '0100', \n",
    "        '1111': '0101', \n",
    "        '1011': '0110', \n",
    "        '1000': '0111',\n",
    "        '0011': '1000', \n",
    "        '1010': '1001',\n",
    "        '0110': '1010',\n",
    "        '1100': '1011',\n",
    "        '0101': '1100',\n",
    "        '1001': '1101',\n",
    "        '0000': '1110',\n",
    "        '0111': '1111'}\n",
    "\n",
    "Pbox_dict = (1,5,9,13,2,6,10,14,3,7,11,15,4,8,12,16) #index:original position, element:permutated position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Sbox(text): \n",
    "    assert len(text) == 4 \n",
    "    if text in Sbox_dict: \n",
    "        return Sbox_dict[text]\n",
    "\n",
    "def inverse_Sbox(text): \n",
    "    assert len(text) == 4 \n",
    "    if text in inverse_Sbox_dict: \n",
    "        return inverse_Sbox_dict[text]\n",
    "\n",
    "def Pbox(text): \n",
    "    assert len(text) == 16\n",
    "    new_list = ['']*16\n",
    "    for i in range(len(text)):\n",
    "        perm_index = Pbox_dict[i]\n",
    "        new_list[perm_index-1] = text[i]\n",
    "    text= ''\n",
    "    for j in new_list: \n",
    "        text+= j\n",
    "    return text\n",
    "\n",
    "def AddKey(text,key): ### Xor of length 16\n",
    "    assert len(text) == 16 & len(key)==16\n",
    "    x = int(text,2)\n",
    "    x =  \"{0:016b}\".format(x^int(key,2))\n",
    "    return x\n",
    "\n",
    "def Xor4(text1,text2):  ### Xor of length 4\n",
    "    assert len(text1) == 4 & len(text2) == 4\n",
    "    x = int(text1,2)\n",
    "    x =  \"{0:04b}\".format(x^int(text2,2))\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "def SPN(plaintext):\n",
    "    assert len(plaintext) == 16\n",
    "    text = plaintext\n",
    "    rounds = 1\n",
    "    k1='0100'*4\n",
    "    k2='00100100'*2\n",
    "    k3='00000100'*2\n",
    "    while (rounds !=4):\n",
    "        a = Sbox(text[0:4])\n",
    "        b = Sbox(text[4:8])\n",
    "        c = Sbox(text[8:12])\n",
    "        d = Sbox(text[12:])\n",
    "        text = a+b+c+d\n",
    "        text = Pbox(text)\n",
    "       \n",
    "        ##add round key \n",
    "        if rounds ==1:\n",
    "            text = AddKey(text, k1)\n",
    "        if rounds ==2:\n",
    "            text = AddKey(text, k2)\n",
    "        if rounds ==3:\n",
    "            text = AddKey(text, k3)   \n",
    "\n",
    "        rounds+=1\n",
    "        \n",
    "    a4 = Sbox(text[0:4])\n",
    "    b4 = Sbox(text[4:8])\n",
    "    c4 = Sbox(text[8:12])\n",
    "    d4 = Sbox(text[12:16])\n",
    "    text = a4+b4+c4+d4\n",
    "    ##add round key\n",
    "    text = AddKey(text,'0100001100000111') #### This is the key we trying to break [15 6]\n",
    "    return text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Cryptanalysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will only jump the analysis part of making the tables and tracing based on the tutorial analysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rand_text(length):  \n",
    "    key1 = \"\" \n",
    "    for i in range(length): \n",
    "        temp = str(random.randint(0, 1)) # randint function to generate 0, 1 randomly and converting  \n",
    "        key1 += temp \n",
    "    return key1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bias_linear(key): \n",
    "    total = 0\n",
    "    count = 0 \n",
    "    partial_key1 = key[0:4]\n",
    "    partial_key2 = key[4:8]\n",
    "    partial_key3 = key[8:12]\n",
    "    partial_key4 = key[12:16]\n",
    "    while(total <10000):\n",
    "        plaintext = rand_text(16) ### Linear differential is a known-plaintext attack, randomly find 10000 plaintext\n",
    "        ciphertext = SPN(plaintext) \n",
    "        ##this part is based on the manual calculation\n",
    "        partial_ctext2 = ciphertext[4:8]\n",
    "        partial_ctext4 = ciphertext[12:16]\n",
    "        partial_U2 = inverse_Sbox(Xor4(partial_ctext2, partial_key2))\n",
    "        partial_U4 = inverse_Sbox(Xor4(partial_ctext4, partial_key4))\n",
    "        p5,p7,p8 = plaintext[4],plaintext[6], plaintext[7]\n",
    "        u6,u8,u14,u16 = partial_U2[1],partial_U2[3], partial_U4[1], partial_U4[3]  \n",
    "        if int(u6)^int(u8)^int(u14)^int(u16)^int(p5)^int(p7)^int(p8) == 0:\n",
    "            count+=1\n",
    "        total+=1\n",
    "    return abs(count - 5000)/10000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done 0 0\n",
      "done 0 1\n",
      "done 0 2\n",
      "done 0 3\n",
      "done 0 4\n",
      "done 0 5\n",
      "done 0 6\n",
      "done 0 7\n",
      "done 0 8\n",
      "done 0 9\n",
      "done 0 10\n",
      "done 0 11\n",
      "done 0 12\n",
      "done 0 13\n",
      "done 0 14\n",
      "done 0 15\n",
      "done 1 0\n",
      "done 1 1\n",
      "done 1 2\n",
      "done 1 3\n",
      "done 1 4\n",
      "done 1 5\n",
      "done 1 6\n",
      "done 1 7\n",
      "done 1 8\n",
      "done 1 9\n",
      "done 1 10\n",
      "done 1 11\n",
      "done 1 12\n",
      "done 1 13\n",
      "done 1 14\n",
      "done 1 15\n",
      "done 2 0\n",
      "done 2 1\n",
      "done 2 2\n",
      "done 2 3\n",
      "done 2 4\n",
      "done 2 5\n",
      "done 2 6\n",
      "done 2 7\n",
      "done 2 8\n",
      "done 2 9\n",
      "done 2 10\n",
      "done 2 11\n",
      "done 2 12\n",
      "done 2 13\n",
      "done 2 14\n",
      "done 2 15\n",
      "done 3 0\n",
      "done 3 1\n",
      "done 3 2\n",
      "done 3 3\n",
      "done 3 4\n",
      "done 3 5\n",
      "done 3 6\n",
      "done 3 7\n",
      "done 3 8\n",
      "done 3 9\n",
      "done 3 10\n",
      "done 3 11\n",
      "done 3 12\n",
      "done 3 13\n",
      "done 3 14\n",
      "done 3 15\n",
      "done 4 0\n",
      "done 4 1\n",
      "done 4 2\n",
      "done 4 3\n",
      "done 4 4\n",
      "done 4 5\n",
      "done 4 6\n",
      "done 4 7\n",
      "done 4 8\n",
      "done 4 9\n",
      "done 4 10\n",
      "done 4 11\n",
      "done 4 12\n",
      "done 4 13\n",
      "done 4 14\n",
      "done 4 15\n",
      "done 5 0\n",
      "done 5 1\n",
      "done 5 2\n",
      "done 5 3\n",
      "done 5 4\n",
      "done 5 5\n",
      "done 5 6\n",
      "done 5 7\n",
      "done 5 8\n",
      "done 5 9\n",
      "done 5 10\n",
      "done 5 11\n",
      "done 5 12\n",
      "done 5 13\n",
      "done 5 14\n",
      "done 5 15\n",
      "done 6 0\n",
      "done 6 1\n",
      "done 6 2\n",
      "done 6 3\n",
      "done 6 4\n",
      "done 6 5\n",
      "done 6 6\n",
      "done 6 7\n",
      "done 6 8\n",
      "done 6 9\n",
      "done 6 10\n",
      "done 6 11\n",
      "done 6 12\n",
      "done 6 13\n",
      "done 6 14\n",
      "done 6 15\n",
      "done 7 0\n",
      "done 7 1\n",
      "done 7 2\n",
      "done 7 3\n",
      "done 7 4\n",
      "done 7 5\n",
      "done 7 6\n",
      "done 7 7\n",
      "done 7 8\n",
      "done 7 9\n",
      "done 7 10\n",
      "done 7 11\n",
      "done 7 12\n",
      "done 7 13\n",
      "done 7 14\n",
      "done 7 15\n",
      "done 8 0\n",
      "done 8 1\n",
      "done 8 2\n",
      "done 8 3\n",
      "done 8 4\n",
      "done 8 5\n",
      "done 8 6\n",
      "done 8 7\n",
      "done 8 8\n",
      "done 8 9\n",
      "done 8 10\n",
      "done 8 11\n",
      "done 8 12\n",
      "done 8 13\n",
      "done 8 14\n",
      "done 8 15\n",
      "done 9 0\n",
      "done 9 1\n",
      "done 9 2\n",
      "done 9 3\n",
      "done 9 4\n",
      "done 9 5\n",
      "done 9 6\n",
      "done 9 7\n",
      "done 9 8\n",
      "done 9 9\n",
      "done 9 10\n",
      "done 9 11\n",
      "done 9 12\n",
      "done 9 13\n",
      "done 9 14\n",
      "done 9 15\n",
      "done 10 0\n",
      "done 10 1\n",
      "done 10 2\n",
      "done 10 3\n",
      "done 10 4\n",
      "done 10 5\n",
      "done 10 6\n",
      "done 10 7\n",
      "done 10 8\n",
      "done 10 9\n",
      "done 10 10\n",
      "done 10 11\n",
      "done 10 12\n",
      "done 10 13\n",
      "done 10 14\n",
      "done 10 15\n",
      "done 11 0\n",
      "done 11 1\n",
      "done 11 2\n",
      "done 11 3\n",
      "done 11 4\n",
      "done 11 5\n",
      "done 11 6\n",
      "done 11 7\n",
      "done 11 8\n",
      "done 11 9\n",
      "done 11 10\n",
      "done 11 11\n",
      "done 11 12\n",
      "done 11 13\n",
      "done 11 14\n",
      "done 11 15\n",
      "done 12 0\n",
      "done 12 1\n",
      "done 12 2\n",
      "done 12 3\n",
      "done 12 4\n",
      "done 12 5\n",
      "done 12 6\n",
      "done 12 7\n",
      "done 12 8\n",
      "done 12 9\n",
      "done 12 10\n",
      "done 12 11\n",
      "done 12 12\n",
      "done 12 13\n",
      "done 12 14\n",
      "done 12 15\n",
      "done 13 0\n",
      "done 13 1\n",
      "done 13 2\n",
      "done 13 3\n",
      "done 13 4\n",
      "done 13 5\n",
      "done 13 6\n",
      "done 13 7\n",
      "done 13 8\n",
      "done 13 9\n",
      "done 13 10\n",
      "done 13 11\n",
      "done 13 12\n",
      "done 13 13\n",
      "done 13 14\n",
      "done 13 15\n",
      "done 14 0\n",
      "done 14 1\n",
      "done 14 2\n",
      "done 14 3\n",
      "done 14 4\n",
      "done 14 5\n",
      "done 14 6\n",
      "done 14 7\n",
      "done 14 8\n",
      "done 14 9\n",
      "done 14 10\n",
      "done 14 11\n",
      "done 14 12\n",
      "done 14 13\n",
      "done 14 14\n",
      "done 14 15\n",
      "done 15 0\n",
      "done 15 1\n",
      "done 15 2\n",
      "done 15 3\n",
      "done 15 4\n",
      "done 15 5\n",
      "done 15 6\n",
      "done 15 7\n",
      "done 15 8\n",
      "done 15 9\n",
      "done 15 10\n",
      "done 15 11\n",
      "done 15 12\n",
      "done 15 13\n",
      "done 15 14\n",
      "done 15 15\n",
      "[[0.008, 0.0071, 0.0068, 0.0009, 0.0017, 0.0068, 0.0004, 0.0211, 0.0095, 0.0019, 0.0058, 0.015, 0.0029, 0.0005, 0.0037, 0.0063], [0.0012, 0.0072, 0.0089, 0.0021, 0.0035, 0.0055, 0.0145, 0.0162, 0.0014, 0.0238, 0.019, 0.0104, 0.0006, 0.0016, 0.0052, 0.0071], [0.008, 0.0022, 0.0005, 0.0018, 0.0092, 0.002, 0.0046, 0.0169, 0.0102, 0.0058, 0.0066, 0.0036, 0.0037, 0.0037, 0.0043, 0.0007], [0.0132, 0.0063, 0.0025, 0.0062, 0.0041, 0.0119, 0.0121, 0.0325, 0.0103, 0.0163, 0.0248, 0.017, 0.0104, 0.0098, 0.009, 0.0031], [0.023, 0.0101, 0.0059, 0.0029, 0.0107, 0.0062, 0.0134, 0.0047, 0.0102, 0.0052, 0.014, 0.0053, 0.0012, 0.013, 0.0107, 0.0], [0.0064, 0.0063, 0.0092, 0.0022, 0.0078, 0.0089, 0.0036, 0.0, 0.0035, 0.0049, 0.0026, 0.0098, 0.0072, 0.0016, 0.006, 0.0055], [0.0053, 0.0056, 0.0156, 0.0042, 0.0072, 0.002, 0.0075, 0.0042, 0.0123, 0.004, 0.0037, 0.0094, 0.0062, 0.001, 0.0027, 0.0021], [0.0019, 0.0129, 0.0013, 0.0047, 0.0104, 0.0037, 0.0013, 0.0015, 0.0061, 0.0094, 0.0001, 0.0082, 0.0044, 0.0028, 0.0049, 0.0058], [0.0126, 0.0044, 0.0035, 0.0001, 0.0002, 0.0019, 0.0004, 0.0064, 0.0018, 0.0027, 0.0049, 0.0088, 0.0118, 0.0064, 0.0048, 0.0026], [0.019, 0.0073, 0.0022, 0.0046, 0.0099, 0.0059, 0.004, 0.0011, 0.0078, 0.007, 0.0024, 0.0051, 0.0076, 0.0045, 0.0103, 0.0006], [0.0033, 0.0026, 0.0041, 0.0014, 0.0129, 0.0006, 0.0056, 0.0097, 0.0034, 0.0027, 0.0105, 0.0026, 0.0006, 0.0013, 0.0035, 0.0023], [0.0074, 0.0057, 0.0042, 0.0032, 0.0008, 0.0054, 0.0094, 0.0001, 0.0019, 0.006, 0.0044, 0.0046, 0.0096, 0.0059, 0.0056, 0.0043], [0.0007, 0.0032, 0.0033, 0.0055, 0.0044, 0.0009, 0.0093, 0.002, 0.0094, 0.0033, 0.006, 0.0054, 0.0066, 0.0068, 0.0156, 0.0148], [0.0121, 0.0035, 0.0102, 0.0019, 0.0022, 0.0001, 0.0007, 0.0083, 0.0108, 0.0015, 0.0037, 0.0134, 0.0012, 0.0063, 0.0059, 0.002], [0.0007, 0.0057, 0.0002, 0.0047, 0.0027, 0.0089, 0.0083, 0.0166, 0.0018, 0.0003, 0.0111, 0.005, 0.0031, 0.0036, 0.0205, 0.0086], [0.0048, 0.0086, 0.0001, 0.0038, 0.0027, 0.0125, 0.0072, 0.0157, 0.0021, 0.003, 0.0037, 0.0023, 0.0036, 0.0051, 0.0077, 0.0009]]\n"
     ]
    }
   ],
   "source": [
    "table = []\n",
    "for i in range(16): \n",
    "    string1 = \"{0:04b}\".format(i)\n",
    "    row = []\n",
    "    for j in range(16):\n",
    "        string2 = \"{0:04b}\".format(j)\n",
    "        plaintext = '0000'+string1 + '0000' + string2\n",
    "        row.append(bias_linear(plaintext))\n",
    "        print('done ' +str(i) +\" \"+ str(j))\n",
    "    table.append(row)\n",
    "print(table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.008 0 0\n",
      "0.0211 0 7\n",
      "0.0238 1 9\n",
      "0.0325 3 7\n"
     ]
    }
   ],
   "source": [
    "max_biaslin = 0\n",
    "max_i = -1\n",
    "max_j = -1\n",
    "for i in range(16):\n",
    "     for j in range(16):\n",
    "        if table[i][j] >= max_biaslin: \n",
    "            max_biaslin = table[i][j]\n",
    "            max_i = i\n",
    "            max_j = j\n",
    "            print(str(max_biaslin) +\" \"+ str(max_i)+ \" \" + str(max_j))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the nearest to the bias 1/32 in magnitude based on the "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.008 0 0\n",
      "0.0211 0 7\n",
      "0.0238 1 9\n",
      "0.0325 3 7\n"
     ]
    }
   ],
   "source": [
    "nearest_biaslin = 0\n",
    "nearest_i = -1\n",
    "nearest_j = -1\n",
    "for i in range(16):\n",
    "     for j in range(16):\n",
    "        if abs(1/32 - table[i][j])<= abs(1/32 - nearest_biaslin): \n",
    "            nearest_biaslin = table[i][j]\n",
    "            nearest_i = i\n",
    "            nearest_j = j\n",
    "            print(str(nearest_biaslin) +\" \"+ str(nearest_i)+ \" \" + str(nearest_j))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This confirm that the highest partial key is the largest bias as the paper has written. Tried partial keys for [2,4] and [1,2]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Differential Cryptanalysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prob_differential(target_key):\n",
    "    assert len(target_key) ==16\n",
    "    total = 0\n",
    "    count = 0 \n",
    "    partial_key1 = target_key[0:4]\n",
    "    partial_key2 = target_key[4:8]\n",
    "    partial_key3 = target_key[8:12]\n",
    "    partial_key4 = target_key[12:16]\n",
    "    while(total <5000) :\n",
    "        differential = '0000101100000000' ## this is the differential we want. since differential cryptanalysis is a chosen plaintext attack\n",
    "        plaintext1 = rand_text(16) ## we randomly find a plaintext.\n",
    "        plaintext2 = \"{0:016b}\".format(int(plaintext1,2)^int(differential,2)) ## and get the differential pair of plaintext1.\n",
    "        ciphertext1 = SPN(plaintext1)\n",
    "        ciphertext2 = SPN(plaintext2)\n",
    "        ##this part is based on the manual calculation in the paper\n",
    "        differential_ciphertext = \"{0:016b}\".format(int(ciphertext1,2)^int(ciphertext2,2))\n",
    "        if (differential_ciphertext[0:4] != '0000' or differential_ciphertext[8:12] != '0000'):\n",
    "            total+=1\n",
    "            continue\n",
    "        diff_u2 = Xor4(inverse_Sbox(Xor4(ciphertext1[4:8],target_key[4:8])),inverse_Sbox(Xor4(ciphertext2[4:8],target_key[4:8])))\n",
    "        diff_u4 = Xor4(inverse_Sbox(Xor4(ciphertext1[12:16],target_key[12:16])),inverse_Sbox(Xor4(ciphertext2[12:16],target_key[12:16])))\n",
    "        if (diff_u2 == '0110' and diff_u4 == '0110'):\n",
    "            count+=1\n",
    "        total+=1\n",
    "    return count/5000\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0\n"
     ]
    }
   ],
   "source": [
    "print(prob_differential('0000001000000100'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done 0 0\n",
      "done 0 1\n",
      "done 0 2\n",
      "done 0 3\n",
      "done 0 4\n",
      "done 0 5\n",
      "done 0 6\n",
      "done 0 7\n",
      "done 0 8\n",
      "done 0 9\n",
      "done 0 10\n",
      "done 0 11\n",
      "done 0 12\n",
      "done 0 13\n",
      "done 0 14\n",
      "done 0 15\n",
      "done 1 0\n",
      "done 1 1\n",
      "done 1 2\n",
      "done 1 3\n",
      "done 1 4\n",
      "done 1 5\n",
      "done 1 6\n",
      "done 1 7\n",
      "done 1 8\n",
      "done 1 9\n",
      "done 1 10\n",
      "done 1 11\n",
      "done 1 12\n",
      "done 1 13\n",
      "done 1 14\n",
      "done 1 15\n",
      "done 2 0\n",
      "done 2 1\n",
      "done 2 2\n",
      "done 2 3\n",
      "done 2 4\n",
      "done 2 5\n",
      "done 2 6\n",
      "done 2 7\n",
      "done 2 8\n",
      "done 2 9\n",
      "done 2 10\n",
      "done 2 11\n",
      "done 2 12\n",
      "done 2 13\n",
      "done 2 14\n",
      "done 2 15\n",
      "done 3 0\n",
      "done 3 1\n",
      "done 3 2\n",
      "done 3 3\n",
      "done 3 4\n",
      "done 3 5\n",
      "done 3 6\n",
      "done 3 7\n",
      "done 3 8\n",
      "done 3 9\n",
      "done 3 10\n",
      "done 3 11\n",
      "done 3 12\n",
      "done 3 13\n",
      "done 3 14\n",
      "done 3 15\n",
      "done 4 0\n",
      "done 4 1\n",
      "done 4 2\n",
      "done 4 3\n",
      "done 4 4\n",
      "done 4 5\n",
      "done 4 6\n",
      "done 4 7\n",
      "done 4 8\n",
      "done 4 9\n",
      "done 4 10\n",
      "done 4 11\n",
      "done 4 12\n",
      "done 4 13\n",
      "done 4 14\n",
      "done 4 15\n",
      "done 5 0\n",
      "done 5 1\n",
      "done 5 2\n",
      "done 5 3\n",
      "done 5 4\n",
      "done 5 5\n",
      "done 5 6\n",
      "done 5 7\n",
      "done 5 8\n",
      "done 5 9\n",
      "done 5 10\n",
      "done 5 11\n",
      "done 5 12\n",
      "done 5 13\n",
      "done 5 14\n",
      "done 5 15\n",
      "done 6 0\n",
      "done 6 1\n",
      "done 6 2\n",
      "done 6 3\n",
      "done 6 4\n",
      "done 6 5\n",
      "done 6 6\n",
      "done 6 7\n",
      "done 6 8\n",
      "done 6 9\n",
      "done 6 10\n",
      "done 6 11\n",
      "done 6 12\n",
      "done 6 13\n",
      "done 6 14\n",
      "done 6 15\n",
      "done 7 0\n",
      "done 7 1\n",
      "done 7 2\n",
      "done 7 3\n",
      "done 7 4\n",
      "done 7 5\n",
      "done 7 6\n",
      "done 7 7\n",
      "done 7 8\n",
      "done 7 9\n",
      "done 7 10\n",
      "done 7 11\n",
      "done 7 12\n",
      "done 7 13\n",
      "done 7 14\n",
      "done 7 15\n",
      "done 8 0\n",
      "done 8 1\n",
      "done 8 2\n",
      "done 8 3\n",
      "done 8 4\n",
      "done 8 5\n",
      "done 8 6\n",
      "done 8 7\n",
      "done 8 8\n",
      "done 8 9\n",
      "done 8 10\n",
      "done 8 11\n",
      "done 8 12\n",
      "done 8 13\n",
      "done 8 14\n",
      "done 8 15\n",
      "done 9 0\n",
      "done 9 1\n",
      "done 9 2\n",
      "done 9 3\n",
      "done 9 4\n",
      "done 9 5\n",
      "done 9 6\n",
      "done 9 7\n",
      "done 9 8\n",
      "done 9 9\n",
      "done 9 10\n",
      "done 9 11\n",
      "done 9 12\n",
      "done 9 13\n",
      "done 9 14\n",
      "done 9 15\n",
      "done 10 0\n",
      "done 10 1\n",
      "done 10 2\n",
      "done 10 3\n",
      "done 10 4\n",
      "done 10 5\n",
      "done 10 6\n",
      "done 10 7\n",
      "done 10 8\n",
      "done 10 9\n",
      "done 10 10\n",
      "done 10 11\n",
      "done 10 12\n",
      "done 10 13\n",
      "done 10 14\n",
      "done 10 15\n",
      "done 11 0\n",
      "done 11 1\n",
      "done 11 2\n",
      "done 11 3\n",
      "done 11 4\n",
      "done 11 5\n",
      "done 11 6\n",
      "done 11 7\n",
      "done 11 8\n",
      "done 11 9\n",
      "done 11 10\n",
      "done 11 11\n",
      "done 11 12\n",
      "done 11 13\n",
      "done 11 14\n",
      "done 11 15\n",
      "done 12 0\n",
      "done 12 1\n",
      "done 12 2\n",
      "done 12 3\n",
      "done 12 4\n",
      "done 12 5\n",
      "done 12 6\n",
      "done 12 7\n",
      "done 12 8\n",
      "done 12 9\n",
      "done 12 10\n",
      "done 12 11\n",
      "done 12 12\n",
      "done 12 13\n",
      "done 12 14\n",
      "done 12 15\n",
      "done 13 0\n",
      "done 13 1\n",
      "done 13 2\n",
      "done 13 3\n",
      "done 13 4\n",
      "done 13 5\n",
      "done 13 6\n",
      "done 13 7\n",
      "done 13 8\n",
      "done 13 9\n",
      "done 13 10\n",
      "done 13 11\n",
      "done 13 12\n",
      "done 13 13\n",
      "done 13 14\n",
      "done 13 15\n",
      "done 14 0\n",
      "done 14 1\n",
      "done 14 2\n",
      "done 14 3\n",
      "done 14 4\n",
      "done 14 5\n",
      "done 14 6\n",
      "done 14 7\n",
      "done 14 8\n",
      "done 14 9\n",
      "done 14 10\n",
      "done 14 11\n",
      "done 14 12\n",
      "done 14 13\n",
      "done 14 14\n",
      "done 14 15\n",
      "done 15 0\n",
      "done 15 1\n",
      "done 15 2\n",
      "done 15 3\n",
      "done 15 4\n",
      "done 15 5\n",
      "done 15 6\n",
      "done 15 7\n",
      "done 15 8\n",
      "done 15 9\n",
      "done 15 10\n",
      "done 15 11\n",
      "done 15 12\n",
      "done 15 13\n",
      "done 15 14\n",
      "done 15 15\n",
      "[[0.0039, 0.0044, 0.0017, 0.0123, 0.0111, 0.0022, 0.0007, 0.0062, 0.0038, 0.0053, 0.0002, 0.0038, 0.0094, 0.001, 0.0023, 0.0052], [0.0057, 0.0093, 0.0117, 0.0083, 0.003, 0.0089, 0.0157, 0.0034, 0.0017, 0.0109, 0.0, 0.0026, 0.007, 0.0012, 0.0073, 0.0052], [0.0113, 0.0001, 0.0032, 0.0038, 0.0022, 0.0143, 0.0003, 0.0032, 0.0019, 0.0132, 0.0019, 0.0004, 0.0017, 0.0082, 0.0023, 0.0062], [0.0037, 0.0062, 0.0003, 0.0145, 0.0003, 0.0042, 0.0057, 0.0153, 0.0079, 0.0094, 0.0106, 0.0037, 0.0025, 0.0045, 0.0134, 0.0073], [0.0275, 0.0128, 0.012, 0.0143, 0.0073, 0.0001, 0.008, 0.0091, 0.0108, 0.0068, 0.0007, 0.0024, 0.0198, 0.0175, 0.0104, 0.0014], [0.0174, 0.0055, 0.0074, 0.0154, 0.0037, 0.0006, 0.0019, 0.0079, 0.0053, 0.012, 0.0117, 0.002, 0.0008, 0.008, 0.0093, 0.0061], [0.0177, 0.019, 0.0064, 0.0144, 0.0033, 0.0121, 0.0059, 0.0119, 0.0017, 0.0135, 0.0017, 0.0065, 0.014, 0.0192, 0.0196, 0.0025], [0.0163, 0.0042, 0.0032, 0.0064, 0.0096, 0.0045, 0.0041, 0.0062, 0.0091, 0.0, 0.0093, 0.0068, 0.0186, 0.0065, 0.0089, 0.013], [0.0192, 0.0037, 0.0, 0.0154, 0.0022, 0.0037, 0.0091, 0.0034, 0.0062, 0.0125, 0.0121, 0.011, 0.0014, 0.0028, 0.0168, 0.001], [0.0157, 0.0085, 0.0054, 0.008, 0.0015, 0.0002, 0.0023, 0.0101, 0.0046, 0.0095, 0.0068, 0.0029, 0.0059, 0.0046, 0.0128, 0.0171], [0.0259, 0.0005, 0.0066, 0.0026, 0.0113, 0.0003, 0.0011, 0.006, 0.0053, 0.0067, 0.003, 0.0018, 0.0145, 0.0109, 0.0087, 0.0101], [0.0036, 0.0092, 0.0075, 0.0052, 0.0061, 0.0039, 0.0106, 0.003, 0.008, 0.0067, 0.0089, 0.011, 0.0004, 0.007, 0.0129, 0.003], [0.007, 0.0117, 0.0029, 0.0035, 0.004, 0.0075, 0.0017, 0.0046, 0.0036, 0.0045, 0.0019, 0.0028, 0.0083, 0.0057, 0.0025, 0.0026], [0.0069, 0.0124, 0.0014, 0.0091, 0.0065, 0.0037, 0.0025, 0.0073, 0.0003, 0.0012, 0.0066, 0.0103, 0.0111, 0.0038, 0.0064, 0.0048], [0.0001, 0.0034, 0.0058, 0.0077, 0.0029, 0.0043, 0.0053, 0.0091, 0.0058, 0.0034, 0.0046, 0.0001, 0.0058, 0.005, 0.009, 0.0043], [0.0012, 0.001, 0.0077, 0.0039, 0.0012, 0.0099, 0.0072, 0.0019, 0.0029, 0.0126, 0.0026, 0.0069, 0.0059, 0.0035, 0.0004, 0.0034]]\n"
     ]
    }
   ],
   "source": [
    "table_diff = []\n",
    "for i in range(16):\n",
    "    string_diff1 = \"{0:04b}\".format(i)\n",
    "    row_diff = []\n",
    "    for j in range(16):\n",
    "        string_diff2 = \"{0:04b}\".format(j)\n",
    "        plaintext_diff = '0000'+string_diff1 + '0000' + string_diff2\n",
    "        row_diff.append(prob_differential(plaintext_diff))\n",
    "        print('done ' +str(i) +\" \"+ str(j))\n",
    "    table_diff.append(row_diff)\n",
    "print(table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0 0 0\n",
      "0.0 0 1\n",
      "0.0 0 2\n",
      "0.0002 0 3\n",
      "0.0002 0 4\n",
      "0.0002 0 6\n",
      "0.0124 1 0\n",
      "0.0292 4 0\n"
     ]
    }
   ],
   "source": [
    "max_probdiff = 0\n",
    "max_i_diff = -1\n",
    "max_j_diff = -1\n",
    "for i in range(16):\n",
    "     for j in range(16):\n",
    "        if table_diff[i][j] >= max_probdiff: \n",
    "            max_probdiff = table_diff[i][j]\n",
    "            max_i_diff = i\n",
    "            max_j_diff = j\n",
    "            print(str(max_probdiff) +\" \"+ str(max_i_diff)+ \" \" + str(max_j_diff))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This confirm the paper that the largest prob is the key. Tried partial keys for [2,4] and [1,2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Results\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. '0000001000000100': expected output: [2 4]  Linear:0.0371 [2 4]                 Differential: 0.0276 [2 4]<br>\n",
    "2. '0000000100000010': expected output: [1 2]  Linear:0.0324 [1 2]                 Differential:0.024 [1 2] <br>\n",
    "3. '0100001100000111': expected output: [3 7]  Linear: 0.0261 [3 7] 0.0274 [3 10]  Differential: 0.0272 [3 7] <br>\n",
    "4. '0100010101001111': expected output: [5 15] Linear: 0.0313 [5 15]               Differential: 0.0238 [5 15] <br>\n",
    "5. '0100001100001010': expected output: [3 10] Linear: 0.0317 [3 10]               Differential: 0.0258 [3 10]  <br>\n",
    "6. '0101111100000110': expected output: [15 6] Linear: 0.0352 [15 6]               Differential:  0.0274 [15 6]<br>\n",
    "7. '1001101100001000': expected output: [11 8] Linear: 0.028 [11 8]                Differential: 0.0274 [11 8]<br>\n",
    "8. '1011100111111001': expected output: [9 9]  Linear: 0.0277 [9 9] 0.032 [11 9]   Differential: 0.0236 [9 9] <br>\n",
    "9. '1011101110001101': expected output: [11 13]Linear: 0.0321 [11 13]              Differential: 0.0282 [11 13] <br>\n",
    "10. '1011010010000000': expected output: [4 0] Linear: 0.0275 [4 0]                Differential: 0.0292 [4 0]"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}