diff options
Diffstat (limited to 'util/plot_dh.ipynb')
| -rw-r--r-- | util/plot_dh.ipynb | 214 |
1 files changed, 102 insertions, 112 deletions
diff --git a/util/plot_dh.ipynb b/util/plot_dh.ipynb index 4d4edbc..2e82292 100644 --- a/util/plot_dh.ipynb +++ b/util/plot_dh.ipynb @@ -4,7 +4,7 @@ "cell_type": "markdown", "metadata": {}, "source": [ - "# Analysis of key generation data" + "# Analysis of key agreement data" ] }, { @@ -12,13 +12,13 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:51:29.892989Z", - "start_time": "2019-03-17T19:51:29.557783Z" + "end_time": "2019-03-18T18:35:11.337869Z", + "start_time": "2019-03-18T18:35:11.331608Z" } }, "outputs": [], "source": [ - " %matplotlib notebook \n", + "%matplotlib notebook\n", "import numpy as np\n", "from scipy.stats import describe\n", "from scipy.stats import norm as norm_dist\n", @@ -27,7 +27,7 @@ "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 utils import plot_hist, moving_average, hw, time_scale\n", "from binascii import unhexlify\n", "from IPython.display import display, HTML\n", "from ipywidgets import interact, interactive, fixed, interact_manual\n", @@ -48,8 +48,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:57:52.012826Z", - "start_time": "2019-03-17T19:57:52.008374Z" + "end_time": "2019-03-18T18:35:28.957529Z", + "start_time": "2019-03-18T18:35:28.952399Z" } }, "outputs": [], @@ -57,6 +57,14 @@ "# File name with output from ECTesterReader or ECTesterStandalone ECDH.\n", "fname = \"filename.csv\"\n", "\n", + "# The time unit used in displaying the plots. One of \"milli\", \"micro\", \"nano\".\n", + "# WARNING: Using nano might lead to very large plots/histograms and to the\n", + "# notebook to freeze or run out of memory, as well as bad visualization\n", + "# quality, due to noise and low density.\n", + "time_unit = \"milli\"\n", + "# A number which will be used to divide the time into sub-units, e.g. for 5, time will be in fifths of units\n", + "scaling_factor = 1\n", + "\n", "# The amount of entries skipped from the beginning of the file, as they are usually outliers.\n", "skip_first = 10\n", "\n", @@ -94,8 +102,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:51:36.973070Z", - "start_time": "2019-03-17T19:51:36.967369Z" + "end_time": "2019-03-18T18:35:30.394517Z", + "start_time": "2019-03-18T18:35:29.499890Z" } }, "outputs": [], @@ -111,20 +119,8 @@ "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": [ + " norm = colors.Normalize()\n", + "\n", "# Read the header line.\n", "\n", "with open(fname, \"r\") as f:\n", @@ -140,31 +136,14 @@ "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", + "# Setup the data\n", "\n", + "orig_time_unit = header_names[1].split(\"[\")[1][:-1]\n", + "time_disp_unit = time_scale(data[\"time\"], orig_time_unit, time_unit, scaling_factor)\n", "\n", "# Trim times\n", "quant_low_bound = trim_low if 0 <= trim_low <= 1 else 0.01\n", @@ -189,6 +168,7 @@ "min_time = description.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", @@ -231,8 +211,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:57:59.534102Z", - "start_time": "2019-03-17T19:57:59.507172Z" + "end_time": "2019-03-18T18:35:31.158217Z", + "start_time": "2019-03-18T18:35:31.144280Z" } }, "outputs": [], @@ -259,14 +239,14 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:58:00.833677Z", - "start_time": "2019-03-17T19:58:00.827736Z" + "end_time": "2019-03-18T18:35:32.593550Z", + "start_time": "2019-03-18T18:35:32.588147Z" } }, "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", + " list(map(lambda x: \"{} {}\".format(x, time_disp_unit), quantiles))]\n", "display(HTML(tabulate.tabulate(tbl, tablefmt=\"html\")))" ] }, @@ -282,8 +262,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:58:01.954382Z", - "start_time": "2019-03-17T19:58:01.947339Z" + "end_time": "2019-03-18T18:35:33.252850Z", + "start_time": "2019-03-18T18:35:33.245928Z" } }, "outputs": [], @@ -304,7 +284,8 @@ "cell_type": "markdown", "metadata": {}, "source": [ - "### Private key MSB vs time heatmap" + "### Private key MSB vs time heatmap\n", + "The heatmap should show uncorrelated variables." ] }, { @@ -312,8 +293,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:58:03.641387Z", - "start_time": "2019-03-17T19:58:03.572612Z" + "end_time": "2019-03-18T18:35:34.581846Z", + "start_time": "2019-03-18T18:35:34.472065Z" } }, "outputs": [], @@ -329,7 +310,7 @@ "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", + "axe_private.set_ylabel(\"key agreement time ({})\".format(time_disp_unit))\n", "fig_private.colorbar(im, ax=axe_private)\n", "\n", "del priv_msb" @@ -339,7 +320,10 @@ "cell_type": "markdown", "metadata": {}, "source": [ - "### Private key Hamming Weight vs time heatmap" + "### Private key Hamming Weight vs time heatmap\n", + "The heatmap should show uncorrelated variables.\n", + "\n", + "Also contains a private key Hamming Weight histogram, which should be binomially distributed." ] }, { @@ -347,8 +331,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:58:07.768683Z", - "start_time": "2019-03-17T19:58:06.938237Z" + "end_time": "2019-03-18T18:35:39.673526Z", + "start_time": "2019-03-18T18:35:38.253945Z" } }, "outputs": [], @@ -362,7 +346,7 @@ "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.set_ylabel(\"key agreement time ({})\".format(time_disp_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", @@ -392,8 +376,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:58:17.986917Z", - "start_time": "2019-03-17T19:58:11.101449Z" + "end_time": "2019-03-18T18:35:51.604298Z", + "start_time": "2019-03-18T18:35:40.980632Z" } }, "outputs": [], @@ -401,8 +385,8 @@ "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);" + "plot_hist(axe_hist_full, data[\"time\"], \"key agreement time ({})\".format(time_disp_unit), log_scale, hist_size_time);\n", + "plot_hist(axe_hist_trim, data_trimmed[\"time\"], \"key agreement time ({})\".format(time_disp_unit), log_scale, hist_size_time_trim);" ] }, { @@ -417,8 +401,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:51:57.934476Z", - "start_time": "2019-03-17T19:51:57.877729Z" + "end_time": "2019-03-18T18:36:00.467782Z", + "start_time": "2019-03-18T18:36:00.418942Z" } }, "outputs": [], @@ -433,7 +417,7 @@ " 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_ylabel(\"key agreement time ({})\".format(time_disp_unit))\n", "axe_avg.set_xlabel(\"index\")\n", "axe_avg.legend(loc=\"best\")\n", "\n", @@ -444,7 +428,8 @@ "cell_type": "markdown", "metadata": {}, "source": [ - "### Private key MSB and LSB histograms" + "### Private key MSB and LSB histograms\n", + "Expected to be uniform over [0, 255]." ] }, { @@ -452,8 +437,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:51:58.466578Z", - "start_time": "2019-03-17T19:51:57.937797Z" + "end_time": "2019-03-18T18:36:02.558769Z", + "start_time": "2019-03-18T18:36:02.216115Z" }, "hide_input": false }, @@ -474,7 +459,8 @@ "cell_type": "markdown", "metadata": {}, "source": [ - "### Public key coordinate MSB and LSB histograms" + "### Private key bit length vs time heatmap\n", + "Also contains private key bit length histogram, which is expected to be axis flipped geometric distribution with $p = \\frac{1}{2}$ peaking at the bit size of the order of the curve." ] }, { @@ -482,42 +468,37 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:52:21.184705Z", - "start_time": "2019-03-17T19:52:20.589707Z" + "end_time": "2019-03-18T18:36:04.445752Z", + "start_time": "2019-03-18T18:36:04.317542Z" } }, "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", + "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", - "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", + "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_disp_unit))\n", "\n", - "_plot_coord(xs, \"X\", 1)\n", - "_plot_coord(ys, \"Y\", 3)\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 pub_coords, xs, ys" + "del bl_data" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ - "### Private key bit length histogram" + "## Validation\n", + "Perform some tests on the produced data and compare to expected results.\n", + "\n", + "This requires some information about the used curve, enter it below." ] }, { @@ -525,27 +506,14 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-17T19:52:07.657216Z", - "start_time": "2019-03-17T19:52:07.549731Z" + "end_time": "2019-03-18T18:36:15.492599Z", + "start_time": "2019-03-18T18:36:12.008827Z" } }, "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" + "p_str = input(\"The prime specifying the finite field:\")\n", + "p = int(p_str, 16) if p_str.startswith(\"0x\") else int(p_str)" ] }, { @@ -553,13 +521,35 @@ "execution_count": null, "metadata": {}, "outputs": [], - "source": [] + "source": [ + "r_str = input(\"The order of the curve:\")\n", + "r = int(r_str, 16) if r_str.startswith(\"0x\") else int(r_str)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "All of the following tests should pass (e.g. be true):" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": {}, + "outputs": [], + "source": [ + "max_priv = max(data[\"priv\"])\n", + "display(max_priv < r)\n", + "display(r <= p or max_priv > p)\n", + "display(max_priv.bit_length() == r.bit_length())" + ] } ], "metadata": { "@webio": { - "lastCommId": "954c1f99782e402895d668a42553e22f", - "lastKernelId": "0b8e59f0-d640-4f72-ae7f-1b327e75910b" + "lastCommId": "73e8d2ab400746298b234c8983722e8e", + "lastKernelId": "cedfe41c-66b9-4611-ad6f-ab448422bbd2" }, "hide_input": false, "kernelspec": { |