diff options
Diffstat (limited to 'util/plot_dsa.ipynb')
| -rw-r--r-- | util/plot_dsa.ipynb | 220 |
1 files changed, 144 insertions, 76 deletions
diff --git a/util/plot_dsa.ipynb b/util/plot_dsa.ipynb index 503bde8..6fa5663 100644 --- a/util/plot_dsa.ipynb +++ b/util/plot_dsa.ipynb @@ -12,8 +12,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:08:10.526799Z", - "start_time": "2019-03-18T18:08:10.073972Z" + "end_time": "2019-03-21T16:47:51.573214Z", + "start_time": "2019-03-21T16:47:50.777035Z" } }, "outputs": [], @@ -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, time_scale\n", + "from utils import plot_hist, moving_average, hw, time_scale, hist_size_func\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-18T18:15:54.067732Z", - "start_time": "2019-03-18T18:15:54.063679Z" + "end_time": "2019-03-21T16:47:51.578911Z", + "start_time": "2019-03-21T16:47:51.575142Z" } }, "outputs": [], @@ -67,7 +67,7 @@ "scaling_factor = 1\n", "\n", "# The amount of entries skipped from the beginning of the file, as they are usually outliers.\n", - "skip_first = 100\n", + "skip_first = 10\n", "\n", "# Whether to plot things in logarithmic scale or not.\n", "log_scale = False\n", @@ -103,8 +103,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:15:55.985799Z", - "start_time": "2019-03-18T18:15:55.495414Z" + "end_time": "2019-03-21T16:47:55.190977Z", + "start_time": "2019-03-21T16:47:52.428880Z" } }, "outputs": [], @@ -177,21 +177,8 @@ "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", + "hist_size_sign_time = hist_size_func(hist_size)(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(hist_size)(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", @@ -218,8 +205,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:15:57.175564Z", - "start_time": "2019-03-18T18:15:57.161611Z" + "end_time": "2019-03-21T16:18:19.188665Z", + "start_time": "2019-03-21T16:18:19.164737Z" } }, "outputs": [], @@ -246,8 +233,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:15:58.257820Z", - "start_time": "2019-03-18T18:15:58.254036Z" + "end_time": "2019-03-21T16:18:20.110503Z", + "start_time": "2019-03-21T16:18:20.099333Z" } }, "outputs": [], @@ -269,13 +256,15 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:15:58.917927Z", - "start_time": "2019-03-18T18:15:58.909693Z" + "end_time": "2019-03-21T16:18:20.768858Z", + "start_time": "2019-03-21T16:18:20.758881Z" } }, "outputs": [], "source": [ - "display(\"Bitsize:\", bit_size)" + "display(\"Bitsize:\", bit_size)\n", + "display(\"Histogram time bins: {}\".format(hist_size_sign_time))\n", + "display(\"Histogram time bins(trimmed): {}\".format(hist_size_sign_time_trim))" ] }, { @@ -298,14 +287,14 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:15:59.977656Z", - "start_time": "2019-03-18T18:15:59.926337Z" + "end_time": "2019-03-21T16:18:22.549846Z", + "start_time": "2019-03-21T16:18:22.332677Z" } }, "outputs": [], "source": [ "fig_nonce = plt.figure(figsize=(10.5, 8), dpi=90)\n", - "axe_nonce = fig_nonce.add_subplot(1, 1, 1)\n", + "axe_nonce = fig_nonce.add_subplot(1, 1, 1, title=\"Nonce MSB vs signature time\")\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", @@ -314,10 +303,11 @@ "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_xlabel(\"nonce MSB value\")\n", "axe_nonce.set_ylabel(\"signature time ({})\".format(sign_disp_unit))\n", "fig_nonce.colorbar(im, ax=axe_nonce)\n", "\n", + "fig_nonce.tight_layout()\n", "del nonce_msb" ] }, @@ -336,16 +326,16 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:01.977710Z", - "start_time": "2019-03-18T18:16:01.717704Z" + "end_time": "2019-03-21T16:18:26.230002Z", + "start_time": "2019-03-21T16:18:24.323208Z" } }, "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", + "axe_nonce_hist = fig_nonce_hist.add_subplot(gs[0], title=\"Nonce Hamming weight vs signature time\")\n", + "axe_nonce_hist_hw = fig_nonce_hist.add_subplot(gs[1], sharex=axe_nonce_hist, title=\"Nonce Hamming weight\")\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", @@ -361,11 +351,13 @@ "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", "\n", "display(HTML(\"<b>Nonce Hamming weight fitted with normal distribution:</b>\"))\n", "display(HTML(tabulate.tabulate([(\"Mean\", \"Variance\"), param], tablefmt=\"html\")))\n", "\n", + "fig_nonce_hist.tight_layout()\n", + "fig_nonce_hist.colorbar(im, ax=[axe_nonce_hist, axe_nonce_hist_hw])\n", "del nonce_hw" ] }, @@ -381,17 +373,18 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:03.232728Z", - "start_time": "2019-03-18T18:16:03.134237Z" + "end_time": "2019-03-21T16:18:48.188494Z", + "start_time": "2019-03-21T16:18:39.850301Z" } }, "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", + "axe_hist_full = fig_sig_hist.add_subplot(2, 1, 1, title=\"Signature time\")\n", + "axe_hist_trim = fig_sig_hist.add_subplot(2, 1, 2, title=\"Signature time (trimmed)\")\n", "plot_hist(axe_hist_full, data[\"sign_time\"], \"signature time ({})\".format(sign_disp_unit), log_scale, hist_size_sign_time);\n", - "plot_hist(axe_hist_trim, data_trimmed[\"sign_time\"], \"signature time ({})\".format(sign_disp_unit), log_scale, hist_size_sign_time_trim);" + "plot_hist(axe_hist_trim, data_trimmed[\"sign_time\"], \"signature time ({})\".format(sign_disp_unit), log_scale, hist_size_sign_time_trim);\n", + "fig_sig_hist.tight_layout()" ] }, { @@ -406,15 +399,16 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:04.380116Z", - "start_time": "2019-03-18T18:16:04.227481Z" + "end_time": "2019-03-21T16:19:05.618320Z", + "start_time": "2019-03-21T16:18:53.161932Z" } }, "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_disp_unit), log_scale, hist_size_sign_time);" + "axe_hist_full = fig_vrfy_hist.add_subplot(1, 1, 1, title=\"Verification time\")\n", + "plot_hist(axe_hist_full, data[\"verify_time\"], \"verification time ({})\".format(verify_disp_unit), log_scale, hist_size_sign_time);\n", + "fig_vrfy_hist.tight_layout()" ] }, { @@ -429,15 +423,15 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:05.236199Z", - "start_time": "2019-03-18T18:16:05.123540Z" + "end_time": "2019-03-21T16:19:56.783127Z", + "start_time": "2019-03-21T16:19:56.375647Z" } }, "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", + "axe_sign_avg = fig_avg.add_subplot(2, 1, 1, title=\"Moving average of signature time\")\n", + "axe_vrfy_avg = fig_avg.add_subplot(2, 1, 2, sharex=axe_sign_avg, title=\"Moving average of verification time\")\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", @@ -458,6 +452,8 @@ "axe_vrfy_avg.set_xlabel(\"index\")\n", "axe_vrfy_avg.legend(loc=\"best\")\n", "\n", + "fig_avg.tight_layout()\n", + "\n", "del avg_sign_100, avg_sign_1000, avg_vrfy_100, avg_vrfy_1000" ] }, @@ -474,8 +470,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:06.352067Z", - "start_time": "2019-03-18T18:16:06.059476Z" + "end_time": "2019-03-21T16:20:00.354254Z", + "start_time": "2019-03-21T16:19:59.289152Z" } }, "outputs": [], @@ -483,11 +479,12 @@ "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", + "axe_msb_n_hist = fig_nonce_hists.add_subplot(2, 1, 1, title=\"Nonce MSB\")\n", + "axe_lsb_n_hist = fig_nonce_hists.add_subplot(2, 1, 2, title=\"Nonce LSB\")\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", + "fig_nonce_hists.tight_layout()\n", "del nonce_msb, nonce_lsb" ] }, @@ -504,16 +501,16 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:07.625289Z", - "start_time": "2019-03-18T18:16:07.544334Z" + "end_time": "2019-03-21T16:20:02.737798Z", + "start_time": "2019-03-21T16:20:02.481429Z" } }, "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", + "axe_bl_heat = fig_bl.add_subplot(gs[0], title=\"Nonce bit length vs signature time\")\n", + "axe_bl_hist = fig_bl.add_subplot(gs[1], sharex=axe_bl_heat, title=\"Nonce bit length\")\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", @@ -522,6 +519,8 @@ "axe_bl_heat.set_ylabel(\"signature time ({})\".format(sign_disp_unit))\n", "\n", "plot_hist(axe_bl_hist, bl_data, \"nonce bit length\", log_scale, align=\"right\")\n", + "\n", + "fig_bl.tight_layout()\n", "fig_bl.colorbar(im, ax=[axe_bl_heat, axe_bl_hist])\n", "\n", "del bl_data" @@ -531,9 +530,58 @@ "cell_type": "markdown", "metadata": {}, "source": [ + "### Nonce bit length histogram given time\n", + "Interactively shows the histogram of nonce bit length given a selected time range centered around `center` of width `width`. Ideally, the means of these conditional distributions are equal, while the variances can vary." + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-21T16:20:10.306709Z", + "start_time": "2019-03-21T16:20:10.102626Z" + }, + "scrolled": false + }, + "outputs": [], + "source": [ + "fig_bl_time = plt.figure(figsize=(10.5, 5), dpi=90)\n", + "axe_bl_time = fig_bl_time.add_subplot(111)\n", + "axe_bl_time.set_autoscalex_on(False)\n", + "def f(center, width):\n", + " lower_bnd = center - width/2\n", + " upper_bnd = center + width/2\n", + " values = data_trimmed[np.logical_and(data_trimmed[\"sign_time\"] <= upper_bnd,\n", + " data_trimmed[\"sign_time\"] >= lower_bnd)]\n", + " axe_bl_time.clear()\n", + " axe_bl_time.set_title(\"Nonce bit length, given signature time $\\in ({}, {})$ {}\".format(int(lower_bnd), int(upper_bnd), sign_disp_unit))\n", + " bl_data = np.array(list(map(lambda x: x.bit_length(), values[\"nonce\"])), dtype=np.dtype(\"u2\"))\n", + " plot_hist(axe_bl_time, bl_data, \"nonce bit length\", bins=11, range=(bit_size-10, bit_size+1), align=\"left\")\n", + " axe_bl_time.set_xlim((bit_size-10, bit_size))\n", + " fig_bl_time.tight_layout()\n", + "\n", + "center_w = widgets.IntSlider(min=min(data_trimmed[\"sign_time\"]),\n", + " max=max(data_trimmed[\"sign_time\"]),\n", + " step=1,\n", + " value=description_sign_trim.mean,\n", + " continuous_update=False,\n", + " description=\"center {}\".format(sign_disp_unit))\n", + "width_w = widgets.IntSlider(min=1, max=100, continuous_update=False,\n", + " description=\"width {}\".format(sign_disp_unit))\n", + "w = interactive(f, center=center_w,\n", + " width=width_w)\n", + "display(w)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ "## Validation\n", "Perform some tests on the produced data and compare to expected results.\n", "\n", + "\n", "This requires some information about the used curve, enter it below." ] }, @@ -542,8 +590,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:48.791656Z", - "start_time": "2019-03-18T18:16:45.435426Z" + "end_time": "2019-03-21T15:24:57.397880Z", + "start_time": "2019-03-21T15:24:37.395614Z" } }, "outputs": [], @@ -557,8 +605,8 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:55.343989Z", - "start_time": "2019-03-18T18:16:49.543154Z" + "end_time": "2019-03-21T15:25:05.137250Z", + "start_time": "2019-03-21T15:24:59.218945Z" } }, "outputs": [], @@ -571,7 +619,7 @@ "cell_type": "markdown", "metadata": {}, "source": [ - "All of the following tests should pass (e.g. be true):" + "All of the following tests should pass (e.g. be true), given a large enough sample and run without the `--fixed` or `-priv/-npriv` flags:" ] }, { @@ -579,20 +627,40 @@ "execution_count": null, "metadata": { "ExecuteTime": { - "end_time": "2019-03-18T18:16:56.289305Z", - "start_time": "2019-03-18T18:16:56.278296Z" - } + "end_time": "2019-03-21T16:23:08.618543Z", + "start_time": "2019-03-21T16:23:08.451827Z" + }, + "scrolled": true }, "outputs": [], "source": [ "max_priv = max(data[\"priv\"])\n", "max_nonce = max(data[\"nonce\"])\n", - "display(max_priv < r)\n", - "display(r <= p or max_priv > p)\n", - "display(max_nonce < r)\n", - "display(r <= p or max_nonce > p)\n", - "display(max_priv.bit_length() == r.bit_length())\n", - "display(max_nonce.bit_length() == r.bit_length())" + "un = len(np.unique(data[\"priv\"])) != 1\n", + "if un:\n", + " print(\"Private keys are smaller than order:\\t\\t\\t\" + str(max_priv < r))\n", + " print(\"Private keys are larger than prime(if order > prime):\\t\" + str(r <= p or max_priv > p))\n", + "print(\"Nonces are smaller than order:\\t\\t\\t\\t\" + str(max_nonce < r))\n", + "print(\"Nonces are larger than prime(if order > prime):\\t\\t\" + str(r <= p or max_nonce > p))\n", + "if un:\n", + " print(\"Private keys reach full bit length of order:\\t\\t\" + str(max_priv.bit_length() == r.bit_length()))\n", + "print(\"Nonces reach full bit length of order:\\t\\t\\t\" + str(max_nonce.bit_length() == r.bit_length()))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "metadata": { + "ExecuteTime": { + "end_time": "2019-03-21T16:23:09.355514Z", + "start_time": "2019-03-21T16:23:09.315702Z" + } + }, + "outputs": [], + "source": [ + "if un:\n", + " print(\"Private key bit length (min, max):\" + str(min(data[\"priv\"]).bit_length()) + \", \" + str(max(data[\"priv\"]).bit_length()))\n", + "print(\"Nonce bit length (min, max):\" + str(min(data[\"nonce\"]).bit_length()) + \", \" + str(max(data[\"nonce\"]).bit_length()))" ] }, { @@ -605,8 +673,8 @@ ], "metadata": { "@webio": { - "lastCommId": "7c4c5d836a8d43e5846df95890bbafa3", - "lastKernelId": "b01f6c07-c08b-4348-a503-dc2c9cf1db89" + "lastCommId": "9597ec08f0744c0c9aff275fad95d237", + "lastKernelId": "e6055c6c-6313-439b-909b-d90592f67d26" }, "hide_input": false, "kernelspec": { |