{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Analysis of key generation data" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:00:25.518989Z", "start_time": "2019-03-17T23:00:24.501601Z" } }, "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-17T23:06:29.704432Z", "start_time": "2019-03-17T23:06:29.694540Z" } }, "outputs": [], "source": [ "# File name with output from ECTesterReader or ECTesterStandalone signatures.\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 = \"sturges\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Data processing" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:06:30.551732Z", "start_time": "2019-03-17T23:06:30.545202Z" } }, "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-17T23:00:38.023486Z", "start_time": "2019-03-17T23:00:27.178465Z" } }, "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) != 9:\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={3: unhexlify, 4: unhexlify,\n", " 5: hx, 6: unhexlify, 7: hx,\n", " 8: lambda b: bool(int(b))},\n", " dtype=np.dtype([(\"index\", \"u4\"), (\"sign_time\", \"u4\"), (\"verify_time\", \"u4\"),\n", " (\"data\", \"O\"), (\"pub\", \"O\"), (\"priv\", \"O\"), (\"signature\", \"O\"),\n", " (\"nonce\", \"O\"), (\"valid\", \"b\")]))\n", "\n", " \n", "sign_unit = \"ms\"\n", "verify_unit = \"ms\"\n", "# Setup the datatrimmed = False" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:00:38.465677Z", "start_time": "2019-03-17T23:00:38.025692Z" } }, "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 sign_unit == \"ms\":\n", " sign_unit = r\"$\\mu s$\"\n", " np.floor_divide(data[\"sign_time\"], 1000, out=data[\"sign_time\"])\n", "\n", "if header_names[2].endswith(\"[nano]\") and verify_unit == \"ms\":\n", " verify_unit = r\"$\\mu s$\"\n", " np.floor_divide(data[\"verify_time\"], 1000, out=data[\"verify_time\"])\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_sign = mquantiles(data[\"sign_time\"], prob=(quant_low_bound, 0.25, 0.5, 0.75, quant_high_bound))\n", "if trim:\n", " low_bound = quantiles_sign[0] if 0 <= trim_low <= 1 else trim_low\n", " high_bound = quantiles_sign[4] if 0 <= trim_high <= 1 else trim_high\n", " data_trimmed = data[np.logical_and(data[\"sign_time\"] >= low_bound,\n", " data[\"sign_time\"] <= high_bound)]\n", " quantiles_sign_trim = mquantiles(data_trimmed[\"sign_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_sign_trim = quantiles_sign\n", "\n", "description_sign = describe(data[\"sign_time\"])\n", "description_sign_trim = describe(data_trimmed[\"sign_time\"])\n", "\n", "max_sign_time = description_sign.minmax[1]\n", "min_sign_time = description_sign.minmax[0]\n", "bit_size = len(bin(max(data[\"priv\"]))) - 2\n", "byte_size = (bit_size + 7) // 8\n", "bit_size = byte_size * 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_sign_time = hist_size_func(description_sign.nobs, min_sign_time, max_sign_time, description_sign.variance, quantiles_sign[1], quantiles_sign[3])\n", "hist_size_sign_time_trim = hist_size_func(description_sign_trim.nobs, description_sign_trim.minmax[0], description_sign_trim.minmax[1], description_sign_trim.variance, quantiles_sign_trim[1], quantiles_sign_trim[3])\n", "\n", "if hist_size_sign_time < 30:\n", " hist_size_sign_time = max_sign_time - min_sign_time\n", "if hist_size_sign_time_trim < 30:\n", " hist_size_sign_time_trim = description_sign_trim.minmax[1] - description_sign_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-17T23:00:39.540701Z", "start_time": "2019-03-17T23:00:39.511019Z" } }, "outputs": [], "source": [ "display(\"Raw\")\n", "desc = [(\"N\", \"min, max\", \"mean\", \"variance\", \"skewness\", \"kurtosis\"),\n", " description_sign]\n", "display(HTML(tabulate.tabulate(desc, tablefmt=\"html\")))\n", "display(\"Trimmed\")\n", "desc = [(\"N\", \"min, max\", \"mean\", \"variance\", \"skewness\", \"kurtosis\"),\n", " description_sign_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-17T23:00:40.974497Z", "start_time": "2019-03-17T23:00:40.953755Z" } }, "outputs": [], "source": [ "tbl = [(quant_low_bound, \"0.25\", \"0.5\", \"0.75\", quant_high_bound),\n", " list(map(lambda x: \"{} {}\".format(x, sign_unit), quantiles_sign))]\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-17T23:00:41.961541Z", "start_time": "2019-03-17T23:00:41.949385Z" } }, "outputs": [], "source": [ "display(\"Bitsize:\", bit_size)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Plots" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Nonce MSB vs signature time heatmap" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:06:34.030472Z", "start_time": "2019-03-17T23:06:33.761991Z" } }, "outputs": [], "source": [ "fig_nonce = plt.figure(figsize=(10.5, 8), dpi=90)\n", "axe_nonce = fig_nonce.add_subplot(1, 1, 1)\n", "nonce_msb = np.array(list(map(lambda x: x >> (bit_size - 8), data_trimmed[\"nonce\"])), dtype=np.dtype(\"u1\"))\n", "max_msb = max(nonce_msb)\n", "min_msb = min(nonce_msb)\n", "heatmap, xedges, yedges = np.histogram2d(nonce_msb, data_trimmed[\"sign_time\"],\n", " bins=[max_msb - min_msb + 1, hist_size_sign_time_trim])\n", "extent = [min_msb, max_msb, yedges[0], yedges[-1]]\n", "im = axe_nonce.imshow(heatmap.T, extent=extent, aspect=\"auto\", cmap=cmap, origin=\"low\",\n", " interpolation=\"nearest\", norm=norm)\n", "axe_nonce.set_xlabel(\"nonce key MSB value\")\n", "axe_nonce.set_ylabel(\"signature time ({})\".format(sign_unit))\n", "fig_nonce.colorbar(im, ax=axe_nonce)\n", "\n", "del nonce_msb" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Nonce Hamming Weight vs signature time heatmap" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:05:26.804859Z", "start_time": "2019-03-17T23:05:18.214110Z" } }, "outputs": [], "source": [ "fig_nonce_hist = plt.figure(figsize=(10.5, 12), dpi=90)\n", "gs = gridspec.GridSpec(2, 1, height_ratios=[2.5, 1])\n", "axe_nonce_hist = fig_nonce_hist.add_subplot(gs[0])\n", "axe_nonce_hist_hw = fig_nonce_hist.add_subplot(gs[1], sharex = axe_nonce_hist)\n", "nonce_hw = np.array(list(map(hw, data_trimmed[\"nonce\"])), dtype=np.dtype(\"u2\"))\n", "h, xe, ye = np.histogram2d(nonce_hw, data_trimmed[\"sign_time\"], bins=[max(nonce_hw) - min(nonce_hw), hist_size_sign_time_trim])\n", "im = axe_nonce_hist.imshow(h.T, origin=\"low\", cmap=cmap, aspect=\"auto\", extent=[xe[0], xe[-1], ye[0], ye[-1]], norm=norm)\n", "axe_nonce_hist.axvline(x=bit_size//2, alpha=0.7, linestyle=\"dotted\", color=\"white\", label=str(bit_size//2) + \" bits\")\n", "axe_nonce_hist.set_xlabel(\"nonce Hamming weight\")\n", "axe_nonce_hist.set_ylabel(\"signature time ({})\".format(sign_unit))\n", "axe_nonce_hist.legend(loc=\"best\")\n", "\n", "plot_hist(axe_nonce_hist_hw, nonce_hw, \"nonce Hamming weight\", log_scale, True, True)\n", "\n", "param = norm_dist.fit(nonce_hw)\n", "pdf_range = np.arange(min(nonce_hw), max(nonce_hw))\n", "norm_pdf = norm_dist.pdf(pdf_range, *param[:-2], loc=param[-2], scale=param[-1]) * description_sign_trim.nobs\n", "axe_nonce_hist_hw.plot(pdf_range, norm_pdf, label=\"fitted normal distribution\")\n", "axe_nonce_hist_hw.legend(loc=\"best\")\n", "fig_nonce_hist.colorbar(im, ax=[axe_nonce_hist, axe_nonce_hist_hw])\n", "\n", "display(HTML(\"Nonce Hamming weight fitted with normal distribution:\"))\n", "display(HTML(tabulate.tabulate([(\"Mean\", \"Variance\"), param], tablefmt=\"html\")))\n", "\n", "del nonce_hw" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Signature time histogram" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:05:32.395983Z", "start_time": "2019-03-17T23:05:32.068823Z" } }, "outputs": [], "source": [ "fig_sig_hist = plt.figure(figsize=(10.5, 8), dpi=90)\n", "axe_hist_full = fig_sig_hist.add_subplot(2, 1, 1)\n", "axe_hist_trim = fig_sig_hist.add_subplot(2, 1, 2)\n", "plot_hist(axe_hist_full, data[\"sign_time\"], \"signature time ({})\".format(sign_unit), log_scale, hist_size_sign_time);\n", "plot_hist(axe_hist_trim, data_trimmed[\"sign_time\"], \"signature time ({})\".format(sign_unit), log_scale, hist_size_sign_time_trim);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Verification time histogram" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:05:33.358613Z", "start_time": "2019-03-17T23:05:32.963791Z" } }, "outputs": [], "source": [ "fig_vrfy_hist = plt.figure(figsize=(10.5, 5), dpi=90)\n", "axe_hist_full = fig_vrfy_hist.add_subplot(1, 1, 1)\n", "plot_hist(axe_hist_full, data[\"verify_time\"], \"verification time ({})\".format(verify_unit), log_scale, hist_size_sign_time);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Moving averages of signature and verification times" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:05:33.971385Z", "start_time": "2019-03-17T23:05:33.732857Z" } }, "outputs": [], "source": [ "fig_avg = plt.figure(figsize=(10.5, 8), dpi=90)\n", "axe_sign_avg = fig_avg.add_subplot(2, 1, 1)\n", "axe_vrfy_avg = fig_avg.add_subplot(2, 1, 2, sharex=axe_sign_avg)\n", "avg_sign_100 = moving_average(data[\"sign_time\"], 100)\n", "avg_sign_1000 = moving_average(data[\"sign_time\"], 1000)\n", "axe_sign_avg.plot(avg_sign_100, label=\"window = 100\")\n", "axe_sign_avg.plot(avg_sign_1000, label=\"window = 1000\")\n", "if low_bound is not None:\n", " axe_sign_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_sign_avg.axhline(y=high_bound, alpha=0.7, linestyle=\"dotted\", color=\"orange\", label=\"Hight trim bound = {}\".format(high_bound))\n", "axe_sign_avg.set_ylabel(\"signature time ({})\".format(sign_unit))\n", "axe_sign_avg.set_xlabel(\"index\")\n", "axe_sign_avg.legend(loc=\"best\")\n", "\n", "avg_vrfy_100 = moving_average(data[\"verify_time\"], 100)\n", "avg_vrfy_1000 = moving_average(data[\"verify_time\"], 1000)\n", "axe_vrfy_avg.plot(avg_vrfy_100, label=\"window = 100\")\n", "axe_vrfy_avg.plot(avg_vrfy_1000, label=\"window = 1000\")\n", "axe_vrfy_avg.set_ylabel(\"verification time ({})\".format(verify_unit))\n", "axe_vrfy_avg.set_xlabel(\"index\")\n", "axe_vrfy_avg.legend(loc=\"best\")\n", "\n", "del avg_sign_100, avg_sign_1000, avg_vrfy_100, avg_vrfy_1000" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Nonce MSB and LSB histograms" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:05:36.256032Z", "start_time": "2019-03-17T23:05:35.302194Z" } }, "outputs": [], "source": [ "fig_nonce_hists = plt.figure(figsize=(10.5, 8), dpi=90)\n", "nonce_msb = np.array(list(map(lambda x: x >> (bit_size - 8), data[\"nonce\"])), dtype=np.dtype(\"u1\"))\n", "nonce_lsb = np.array(list(map(lambda x: x & 0xff, data[\"nonce\"])), dtype=np.dtype(\"u1\"))\n", "axe_msb_n_hist = fig_nonce_hists.add_subplot(2, 1, 1)\n", "axe_lsb_n_hist = fig_nonce_hists.add_subplot(2, 1, 2)\n", "plot_hist(axe_msb_n_hist, nonce_msb, \"nonce MSB\", log_scale, False, False)\n", "plot_hist(axe_lsb_n_hist, nonce_lsb, \"nonce LSB\", log_scale, False, False)\n", "\n", "del nonce_msb, nonce_lsb" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Nonce bit length histogram" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2019-03-17T23:05:45.320760Z", "start_time": "2019-03-17T23:05:44.951189Z" } }, "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[\"nonce\"])), dtype=np.dtype(\"u2\"))\n", "\n", "h, xe, ye = np.histogram2d(bl_data, data_trimmed[\"sign_time\"], bins=[max(bl_data) - min(bl_data), hist_size_sign_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(\"nonce bit length\")\n", "axe_bl_heat.set_ylabel(\"signature time ({})\".format(sign_unit))\n", "\n", "plot_hist(axe_bl_hist, bl_data, \"nonce 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": "2218f80b2f784436bce6ffed5d971ea3", "lastKernelId": "1c06331a-17dd-4743-9e31-832000e597c8" }, "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 }