diff options
Diffstat (limited to 'util/plot_dh.ipynb')
| -rw-r--r-- | util/plot_dh.ipynb | 616 |
1 files changed, 616 insertions, 0 deletions
diff --git a/util/plot_dh.ipynb b/util/plot_dh.ipynb new file mode 100644 index 0000000..4d4edbc --- /dev/null +++ b/util/plot_dh.ipynb @@ -0,0 +1,616 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Analysis of key generation data" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:51:29.892989Z", + "start_time": "2019-03-17T19:51:29.557783Z" + } + }, + "outputs": [], + "source": [ + " %matplotlib notebook \n", + "import numpy as np\n", + "from scipy.stats import describe\n", + "from scipy.stats import norm as norm_dist\n", + "from scipy.stats.mstats import mquantiles\n", + "from math import log, sqrt\n", + "import matplotlib.pyplot as plt\n", + "from matplotlib import ticker, colors, gridspec\n", + "from copy import deepcopy\n", + "from utils import plot_hist, moving_average, hw\n", + "from binascii import unhexlify\n", + "from IPython.display import display, HTML\n", + "from ipywidgets import interact, interactive, fixed, interact_manual\n", + "import ipywidgets as widgets\n", + "import tabulate" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Settings\n", + "Enter your input below." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:57:52.012826Z", + "start_time": "2019-03-17T19:57:52.008374Z" + } + }, + "outputs": [], + "source": [ + "# File name with output from ECTesterReader or ECTesterStandalone ECDH.\n", + "fname = \"filename.csv\"\n", + "\n", + "# The amount of entries skipped from the beginning of the file, as they are usually outliers.\n", + "skip_first = 10\n", + "\n", + "# Whether to plot things in logarithmic scale or not.\n", + "log_scale = False\n", + "\n", + "# Whether to trim the time data outside the 1 - 99 percentile range (adjust below). Quite useful.\n", + "trim = True\n", + "\n", + "# How much to trim? Either a number in [0,1] signifying a quantile, or an absolute value signifying a threshold\n", + "trim_low = 0.01\n", + "trim_high = 0.99\n", + "\n", + "# Graphical (matplotlib) style name\n", + "style = \"ggplot\"\n", + "\n", + "# Color map to use, and what color to assign to \"bad\" values (necessary for log_scale)\n", + "color_map = plt.cm.plasma\n", + "color_map_bad = \"black\"\n", + "\n", + "# What function to use to calculate number of histogram bins of time\n", + "# one of \"sqrt\", \"sturges\", \"rice\", \"scott\" and \"fd\" or a number specifying the number of bins\n", + "hist_size = \"rice\"" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Data processing" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:51:36.973070Z", + "start_time": "2019-03-17T19:51:36.967369Z" + } + }, + "outputs": [], + "source": [ + "# Setup plot style\n", + "\n", + "plt.style.use(style)\n", + "\n", + "cmap = deepcopy(color_map)\n", + "cmap.set_bad(color_map_bad)\n", + "\n", + "# Normalization, linear or log.\n", + "if log_scale:\n", + " norm = colors.LogNorm()\n", + "else:\n", + " norm = colors.Normalize()" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:51:39.208449Z", + "start_time": "2019-03-17T19:51:37.430702Z" + } + }, + "outputs": [], + "source": [ + "# Read the header line.\n", + "\n", + "with open(fname, \"r\") as f:\n", + " header = f.readline()\n", + "header_names = header.split(\";\")\n", + "if len(header_names) != 5:\n", + " print(\"Bad data?\")\n", + " exit(1)\n", + "\n", + "# Load the data\n", + "\n", + "hx = lambda x: int(x, 16)\n", + "data = np.genfromtxt(fname, delimiter=\";\", skip_header=1, converters={2: unhexlify, 3: hx, 4: hx},\n", + " dtype=np.dtype([(\"index\", \"u4\"), (\"time\", \"u4\"), (\"pub\", \"O\"), (\"priv\", \"O\"), (\"secret\", \"O\")]))\n", + "\n", + "time_unit = \"ms\"" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:57:56.363502Z", + "start_time": "2019-03-17T19:57:56.331005Z" + } + }, + "outputs": [], + "source": [ + "# Setup the data\n", + "\n", + "# Skip first (outliers?)\n", + "\n", + "data = data[skip_first:]\n", + "\n", + "# If in nanoseconds, scale to microseconds\n", + "if header_names[1].endswith(\"[nano]\") and time_unit == \"ms\":\n", + " time_unit = r\"$\\mu s$\"\n", + " np.floor_divide(data[\"time\"], 1000, out=data[\"time\"])\n", + "\n", + "\n", + "# Trim times\n", + "quant_low_bound = trim_low if 0 <= trim_low <= 1 else 0.01\n", + "quant_high_bound = trim_high if 0 <= trim_high <= 1 else 0.95\n", + "quantiles = mquantiles(data[\"time\"], prob=(quant_low_bound, 0.25, 0.5, 0.75, quant_high_bound))\n", + "if trim:\n", + " low_bound = quantiles[0] if 0 <= trim_low <= 1 else trim_low\n", + " high_bound = quantiles[4] if 0 <= trim_high <= 1 else trim_high\n", + " data_trimmed = data[np.logical_and(data[\"time\"] >= low_bound,\n", + " data[\"time\"] <= high_bound)]\n", + " quantiles_trim = mquantiles(data_trimmed[\"time\"], prob=(quant_low_bound, 0.25, 0.5, 0.75, quant_high_bound))\n", + "else:\n", + " low_bound = None\n", + " high_bound = None\n", + " data_trimmed = data\n", + " quantiles_trim = quantiles_gen\n", + "\n", + "description = describe(data[\"time\"])\n", + "description_trim = describe(data_trimmed[\"time\"])\n", + "\n", + "max_time = description.minmax[1]\n", + "min_time = description.minmax[0]\n", + "bit_size = len(bin(max(data[\"priv\"]))) - 2\n", + "byte_size = (bit_size + 7) // 8\n", + "\n", + "if hist_size == \"sqrt\":\n", + " hist_size_func = lambda n, xmin, xmax, var, xlower, xupper: int(sqrt(n)) + 1\n", + "elif hist_size == \"sturges\":\n", + " hist_size_func = lambda n, xmin, xmax, var, xlower, xupper: int(log(n, 2)) + 1\n", + "elif hist_size == \"rice\":\n", + " hist_size_func = lambda n, xmin, xmax, var, xlower, xupper: int(2 * n**(1/3))\n", + "elif hist_size == \"scott\":\n", + " hist_size_func = lambda n, xmin, xmax, var, xlower, xupper: (xmax - xmin) // int((3.5 * sqrt(var)) / (n**(1/3)))\n", + "elif hist_size == \"fd\":\n", + " hist_size_func = lambda n, xmin, xmax, var, xlower, xupper: (xmax - xmin) // int(2 * (xupper - xlower) / (n**(1/3)))\n", + "else:\n", + " hist_size_func = lambda n, xmin, xmax, var, xlower, xupper: hist_size\n", + "\n", + "hist_size_time = hist_size_func(description.nobs, min_time, max_time, description.variance, quantiles[1], quantiles[3])\n", + "hist_size_time_trim = hist_size_func(description_trim.nobs, description_trim.minmax[0], description_trim.minmax[1], description_trim.variance, quantiles_trim[1], quantiles_trim[3])\n", + "\n", + "if hist_size_time < 30:\n", + " hist_size_time = max_time - min_time\n", + "if hist_size_time_trim < 30:\n", + " hist_size_time_trim = description_trim.minmax[1] - description_trim.minmax[0]" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Analysis" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Summary" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:57:59.534102Z", + "start_time": "2019-03-17T19:57:59.507172Z" + } + }, + "outputs": [], + "source": [ + "display(\"Raw\")\n", + "desc = [(\"N\", \"min, max\", \"mean\", \"variance\", \"skewness\", \"kurtosis\"),\n", + " description]\n", + "display(HTML(tabulate.tabulate(desc, tablefmt=\"html\")))\n", + "display(\"Trimmed\")\n", + "desc = [(\"N\", \"min, max\", \"mean\", \"variance\", \"skewness\", \"kurtosis\"),\n", + " description_trim]\n", + "display(HTML(tabulate.tabulate(desc, tablefmt=\"html\")))" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Selected quantiles" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:58:00.833677Z", + "start_time": "2019-03-17T19:58:00.827736Z" + } + }, + "outputs": [], + "source": [ + "tbl = [(quant_low_bound, \"0.25\", \"0.5\", \"0.75\", quant_high_bound),\n", + " list(map(lambda x: \"{} {}\".format(x, time_unit), quantiles))]\n", + "display(HTML(tabulate.tabulate(tbl, tablefmt=\"html\")))" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Info" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:58:01.954382Z", + "start_time": "2019-03-17T19:58:01.947339Z" + } + }, + "outputs": [], + "source": [ + "display(\"Bitsize: {}\".format(bit_size))\n", + "display(\"Histogram time bins: {}\".format(hist_size_time))\n", + "display(\"Histogram time bins(trimmed): {}\".format(hist_size_time_trim))" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Plots" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Private key MSB vs time heatmap" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:58:03.641387Z", + "start_time": "2019-03-17T19:58:03.572612Z" + } + }, + "outputs": [], + "source": [ + "fig_private = plt.figure(figsize=(10.5, 8), dpi=90)\n", + "axe_private = fig_private.add_subplot(1, 1, 1)\n", + "priv_msb = np.array(list(map(lambda x: x >> (bit_size - 8), data_trimmed[\"priv\"])), dtype=np.dtype(\"u1\"))\n", + "max_msb = max(priv_msb)\n", + "min_msb = min(priv_msb)\n", + "heatmap, xedges, yedges = np.histogram2d(priv_msb, data_trimmed[\"time\"],\n", + " bins=[max_msb - min_msb + 1, hist_size_time_trim])\n", + "extent = [min_msb, max_msb, yedges[0], yedges[-1]]\n", + "im = axe_private.imshow(heatmap.T, extent=extent, aspect=\"auto\", cmap=cmap, origin=\"low\",\n", + " interpolation=\"nearest\", norm=norm)\n", + "axe_private.set_xlabel(\"private key MSB value\")\n", + "axe_private.set_ylabel(\"key agreement time ({})\".format(time_unit))\n", + "fig_private.colorbar(im, ax=axe_private)\n", + "\n", + "del priv_msb" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Private key Hamming Weight vs time heatmap" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:58:07.768683Z", + "start_time": "2019-03-17T19:58:06.938237Z" + } + }, + "outputs": [], + "source": [ + "fig_priv_hist = plt.figure(figsize=(10.5, 12), dpi=90)\n", + "gs = gridspec.GridSpec(2, 1, height_ratios=[2.5, 1])\n", + "axe_priv_hist = fig_priv_hist.add_subplot(gs[0])\n", + "axe_priv_hist_hw = fig_priv_hist.add_subplot(gs[1], sharex = axe_priv_hist)\n", + "priv_hw = np.array(list(map(hw, data_trimmed[\"priv\"])), dtype=np.dtype(\"u2\"))\n", + "h, xe, ye = np.histogram2d(priv_hw, data_trimmed[\"time\"], bins=[max(priv_hw) - min(priv_hw), hist_size_time_trim])\n", + "im = axe_priv_hist.imshow(h.T, origin=\"low\", cmap=cmap, aspect=\"auto\", extent=[xe[0], xe[-1], ye[0], ye[-1]], norm=norm)\n", + "axe_priv_hist.axvline(x=bit_size//2, alpha=0.7, linestyle=\"dotted\", color=\"white\", label=str(bit_size//2) + \" bits\")\n", + "axe_priv_hist.set_xlabel(\"private key Hamming weight\")\n", + "axe_priv_hist.set_ylabel(\"key agreement time ({})\".format(time_unit))\n", + "axe_priv_hist.legend(loc=\"best\")\n", + "\n", + "plot_hist(axe_priv_hist_hw, priv_hw, \"private key Hamming weight\", log_scale, None)\n", + "\n", + "param = norm_dist.fit(priv_hw)\n", + "pdf_range = np.arange(min(priv_hw), max(priv_hw))\n", + "norm_pdf = norm_dist.pdf(pdf_range, *param[:-2], loc=param[-2], scale=param[-1]) * description_trim.nobs\n", + "axe_priv_hist_hw.plot(pdf_range, norm_pdf, label=\"fitted normal distribution\")\n", + "axe_priv_hist_hw.legend(loc=\"best\")\n", + "fig_priv_hist.colorbar(im, ax=[axe_priv_hist, axe_priv_hist_hw])\n", + "\n", + "display(HTML(\"<b>Private key Hamming weight fitted with normal distribution:</b>\"))\n", + "display(HTML(tabulate.tabulate([(\"Mean\", \"Variance\"), param], tablefmt=\"html\")))\n", + "\n", + "del priv_hw" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Key agreement time histogram" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:58:17.986917Z", + "start_time": "2019-03-17T19:58:11.101449Z" + } + }, + "outputs": [], + "source": [ + "fig_ka_hist = plt.figure(figsize=(10.5, 8), dpi=90)\n", + "axe_hist_full = fig_ka_hist.add_subplot(2, 1, 1)\n", + "axe_hist_trim = fig_ka_hist.add_subplot(2, 1, 2)\n", + "plot_hist(axe_hist_full, data[\"time\"], \"key agreement time ({})\".format(time_unit), log_scale, hist_size_time);\n", + "plot_hist(axe_hist_trim, data_trimmed[\"time\"], \"key agreement time ({})\".format(time_unit), log_scale, hist_size_time_trim);" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Moving averages of key agreement time" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:51:57.934476Z", + "start_time": "2019-03-17T19:51:57.877729Z" + } + }, + "outputs": [], + "source": [ + "fig_avg = plt.figure(figsize=(10.5, 7), dpi=90)\n", + "axe_avg = fig_avg.add_subplot(1, 1, 1)\n", + "avg_100 = moving_average(data[\"time\"], 100)\n", + "avg_1000 = moving_average(data[\"time\"], 1000)\n", + "axe_avg.plot(avg_100, label=\"window = 100\")\n", + "axe_avg.plot(avg_1000, label=\"window = 1000\")\n", + "if low_bound is not None:\n", + " axe_avg.axhline(y=low_bound, alpha=0.7, linestyle=\"dotted\", color=\"green\", label=\"Low trim bound = {}\".format(low_bound))\n", + "if high_bound is not None:\n", + " axe_avg.axhline(y=high_bound, alpha=0.7, linestyle=\"dotted\", color=\"orange\", label=\"Hight trim bound = {}\".format(high_bound))\n", + "axe_avg.set_ylabel(\"key agreement time ({})\".format(time_unit))\n", + "axe_avg.set_xlabel(\"index\")\n", + "axe_avg.legend(loc=\"best\")\n", + "\n", + "del avg_100, avg_1000" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Private key MSB and LSB histograms" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:51:58.466578Z", + "start_time": "2019-03-17T19:51:57.937797Z" + }, + "hide_input": false + }, + "outputs": [], + "source": [ + "fig_priv_hists = plt.figure(figsize=(10.5, 8), dpi=90)\n", + "priv_msb = np.array(list(map(lambda x: x >> (bit_size - 8), data[\"priv\"])), dtype=np.dtype(\"u1\"))\n", + "priv_lsb = np.array(list(map(lambda x: x & 0xff, data[\"priv\"])), dtype=np.dtype(\"u1\"))\n", + "axe_msb_s_hist = fig_priv_hists.add_subplot(2, 1, 1)\n", + "axe_lsb_s_hist = fig_priv_hists.add_subplot(2, 1, 2)\n", + "msb_h = plot_hist(axe_msb_s_hist, priv_msb, \"private key MSB\", log_scale, False, False)\n", + "lsb_h = plot_hist(axe_lsb_s_hist, priv_lsb, \"private key LSB\", log_scale, False, False)\n", + "\n", + "del priv_msb, priv_lsb" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Public key coordinate MSB and LSB histograms" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:52:21.184705Z", + "start_time": "2019-03-17T19:52:20.589707Z" + } + }, + "outputs": [], + "source": [ + "def _split(xy):\n", + " x = int.from_bytes(xy[1:byte_size + 1], byteorder=\"big\")\n", + " y = int.from_bytes(xy[1 + byte_size:], byteorder=\"big\")\n", + " return (x, y)\n", + "\n", + "pub_coords = np.array(list(map(_split, data[\"pub\"])), dtype=np.dtype(\"O\"))\n", + "xs = pub_coords[...,0]\n", + "ys = pub_coords[...,1]\n", + "fig_pub_hists = plt.figure(figsize=(10.5, 14), dpi=90)\n", + "\n", + "def _plot_coord(data, name, offset):\n", + " axe_msb_pub_hist = fig_pub_hists.add_subplot(4, 1, offset)\n", + " axe_lsb_pub_hist = fig_pub_hists.add_subplot(4, 1, offset + 1)\n", + " pub_msb = np.array(list(map(lambda x: x >> (bit_size - 8), data)))\n", + " pub_lsb = np.array(list(map(lambda x: x & 0xff, data)))\n", + " plot_hist(axe_msb_pub_hist, pub_msb, \"{} coordinate MSB\".format(name), log_scale)\n", + " plot_hist(axe_lsb_pub_hist, pub_lsb, \"{} coordinate LSB\".format(name), log_scale)\n", + " del pub_msb, pub_lsb\n", + "\n", + "_plot_coord(xs, \"X\", 1)\n", + "_plot_coord(ys, \"Y\", 3)\n", + "\n", + "del pub_coords, xs, ys" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Private key bit length histogram" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-17T19:52:07.657216Z", + "start_time": "2019-03-17T19:52:07.549731Z" + } + }, + "outputs": [], + "source": [ + "fig_bl = plt.figure(figsize=(10.5, 12), dpi=90)\n", + "gs = gridspec.GridSpec(2, 1, height_ratios=[2.5, 1])\n", + "axe_bl_heat = fig_bl.add_subplot(gs[0])\n", + "axe_bl_hist = fig_bl.add_subplot(gs[1], sharex=axe_bl_heat)\n", + "bl_data = np.array(list(map(lambda x: x.bit_length(), data_trimmed[\"priv\"])), dtype=np.dtype(\"u2\"))\n", + "\n", + "h, xe, ye = np.histogram2d(bl_data, data_trimmed[\"time\"], bins=[max(bl_data) - min(bl_data), hist_size_time_trim])\n", + "im = axe_bl_heat.imshow(h.T, origin=\"low\", cmap=cmap, aspect=\"auto\", extent=[xe[0], xe[-1], ye[0], ye[-1]], norm=norm)\n", + "axe_bl_heat.set_xlabel(\"private key bit length\")\n", + "axe_bl_heat.set_ylabel(\"key agreement time ({})\".format(time_unit))\n", + "\n", + "plot_hist(axe_bl_hist, bl_data, \"Private key bit length\", log_scale, align=\"right\")\n", + "fig_bl.colorbar(im, ax=[axe_bl_heat, axe_bl_hist])\n", + "\n", + "del bl_data" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [] + } + ], + "metadata": { + "@webio": { + "lastCommId": "954c1f99782e402895d668a42553e22f", + "lastKernelId": "0b8e59f0-d640-4f72-ae7f-1b327e75910b" + }, + "hide_input": false, + "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.2" + }, + "latex_envs": { + "LaTeX_envs_menu_present": true, + "autoclose": false, + "autocomplete": true, + "bibliofile": "biblio.bib", + "cite_by": "apalike", + "current_citInitial": 1, + "eqLabelWithNumbers": true, + "eqNumInitial": 1, + "hotkeys": { + "equation": "Ctrl-E", + "itemize": "Ctrl-I" + }, + "labels_anchors": false, + "latex_user_defs": false, + "report_style_numbering": false, + "user_envs_cfg": false + }, + "toc": { + "base_numbering": 1, + "nav_menu": {}, + "number_sections": true, + "sideBar": true, + "skip_h1_title": false, + "title_cell": "Table of Contents", + "title_sidebar": "Contents", + "toc_cell": false, + "toc_position": {}, + "toc_section_display": true, + "toc_window_display": false + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} |