.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/crypto/sharing/plot_01_secret_sharing.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_crypto_sharing_plot_01_secret_sharing.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_crypto_sharing_plot_01_secret_sharing.py:


Shamir's secret sharing: reconstruct a secret without storing it whole (1979)
=============================================================================

The secret is the constant coefficient of a random polynomial. Any threshold
number of evaluations determines it; fewer evaluations leave it undetermined.
Arithmetic takes place in a prime field, not over floating-point reals.

What to look for
----------------

Watch every three-person subset recover the same secret. Two shares fit several possible
secrets; the curves illustrate why the missing share matters.

Read cells in order. An ``assert`` that produces no output has passed.
The final exercise asks you to change an input and explain the result.

The history behind this experiment: :doc:`/history/crypto_breakthroughs`.
See :doc:`/exercises/crypto` for a worked solution to the exercise.

.. GENERATED FROM PYTHON SOURCE LINES 23-37

.. code-block:: Python

    from itertools import combinations
    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    secret, prime = 42, 101
    shares = bk.crypto.split_secret(secret, 3, 5, prime, randbelow=Random(7).randrange)
    for subset in combinations(shares, 3):
        assert bk.crypto.recover_secret(subset, prime) == secret
    print("Five shares:", shares)
    print("Every one of the ten three-share subsets recovers", secret)





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Five shares: ((1, 1), (2, 99), (3, 33), (4, 5), (5, 15))
    Every one of the ten three-share subsets recovers 42




.. GENERATED FROM PYTHON SOURCE LINES 38-41

Two points admit every possible secret in a quadratic sharing scheme
--------------------------------------------------------------------
For each candidate constant, solve for the remaining two coefficients.

.. GENERATED FROM PYTHON SOURCE LINES 41-52

.. code-block:: Python

    (x1, y1), (x2, y2) = shares[:2]
    candidate_polynomials = []
    for candidate in (0, 20, 42, 80):
        # y_i - candidate = a*x_i + b*x_i**2
        determinant = (x1 * x2**2 - x2 * x1**2) % prime
        a = ((y1 - candidate) * x2**2 - (y2 - candidate) * x1**2) * pow(determinant, -1, prime) % prime
        b = (x1 * (y2 - candidate) - x2 * (y1 - candidate)) * pow(determinant, -1, prime) % prime
        candidate_polynomials.append((candidate, a, b))
        assert (candidate + a * x1 + b * x1**2) % prime == y1
        assert (candidate + a * x2 + b * x2**2) % prime == y2








.. GENERATED FROM PYTHON SOURCE LINES 53-68

.. code-block:: Python

    fig, ax = plt.subplots(figsize=(8, 4))
    xs = list(range(7))
    for candidate, a, b in candidate_polynomials:
        ax.scatter(
            xs, [(candidate + a * x + b * x**2) % prime for x in xs], label=f"secret={candidate}"
        )
    ax.scatter([x1, x2], [y1, y2], s=180, facecolors="none", edgecolors="black", label="known shares")
    ax.set(
        xlabel="Evaluation coordinate x",
        ylabel="Polynomial value modulo 101",
        title="Two shares, many possible secrets",
    )
    ax.legend(ncol=2)
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/sharing/images/sphx_glr_plot_01_secret_sharing_001.png
   :alt: Two shares, many possible secrets
   :srcset: /api/gallery/crypto/sharing/images/sphx_glr_plot_01_secret_sharing_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 69-74

Exercise
--------
Change a share before reconstruction. The result may be wrong without any
error: plain Shamir sharing does not authenticate shares. What additional
mechanism would participants need to detect dishonest contributions?


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.181 seconds)


.. _sphx_glr_download_api_gallery_crypto_sharing_plot_01_secret_sharing.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/crypto/sharing/plot_01_secret_sharing.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_secret_sharing.ipynb <plot_01_secret_sharing.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_secret_sharing.py <plot_01_secret_sharing.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_secret_sharing.zip <plot_01_secret_sharing.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_