.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/crypto/public_keys/plot_01_merkle_puzzles.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_public_keys_plot_01_merkle_puzzles.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_public_keys_plot_01_merkle_puzzles.py:


Merkle's puzzles: the first public-key exchange (1974-1978)
===========================================================

As a student, Ralph Merkle asked whether two strangers could agree on a key
over a public channel. His answer used only a symmetric cipher. Alice
publishes many puzzles, each a session key locked by a deliberately weak
key. Bob solves one at random and announces only its label. An eavesdropper
does not know which puzzle Bob picked, and must open about half of them.

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

Bob's work stays flat while the eavesdropper's grows with the number of
puzzles. With N puzzles of N-trial difficulty, honest parties do O(N) work
and the attacker O(N**2): a real but only *quadratic* advantage. Diffie and
Hellman's exponential gap came next.

The history behind this experiment: :doc:`/history/crypto_breakthroughs`.

.. GENERATED FROM PYTHON SOURCE LINES 23-25

One exchange
------------

.. GENERATED FROM PYTHON SOURCE LINES 25-37

.. code-block:: Python

    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    bits = 8
    puzzles, alice_table = bk.crypto.merkle_puzzles(64, bits, randbits=Random(78).getrandbits)
    bob = bk.crypto.solve_puzzle(puzzles[Random(1).randrange(64)], bits)
    print("Bob announces", bob.puzzle_id.hex(), "after", bob.trials, "trials")
    assert alice_table[bob.puzzle_id] == bob.key  # Alice looks the key up: shared secret.





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

 .. code-block:: none

    Bob announces 05c37466005cee6c after 105 trials




.. GENERATED FROM PYTHON SOURCE LINES 38-40

What the eavesdropper must do
-----------------------------

.. GENERATED FROM PYTHON SOURCE LINES 40-49

.. code-block:: Python

    eve_trials = 0
    for puzzle in puzzles:
        opened = bk.crypto.solve_puzzle(puzzle, bits)
        eve_trials += opened.trials
        if opened.puzzle_id == bob.puzzle_id:
            assert opened.key == bob.key
            break
    print("Eve needed", eve_trials, "trials")





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

 .. code-block:: none

    Eve needed 2050 trials




.. GENERATED FROM PYTHON SOURCE LINES 50-52

Honest work versus attack work
------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 52-66

.. code-block:: Python

    counts = [2**k for k in range(2, 9)]
    bob_work, eve_work = [], []
    for count in counts:
        puzzles, _ = bk.crypto.merkle_puzzles(count, bits, randbits=Random(count).getrandbits)
        trials = [bk.crypto.solve_puzzle(p, bits).trials for p in puzzles]
        bob_work.append(sum(trials) / count)  # One puzzle, on average.
        eve_work.append(sum(trials) / 2)  # Half the puzzles, on average.
    fig, ax = plt.subplots(figsize=(7, 4))
    ax.loglog(counts, bob_work, "o-", label="Bob: one puzzle")
    ax.loglog(counts, eve_work, "s-", label="Eve: half of the puzzles")
    ax.set(xlabel="number of puzzles", ylabel="trials", title="A quadratic gap from symmetric crypto")
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/public_keys/images/sphx_glr_plot_01_merkle_puzzles_001.png
   :alt: A quadratic gap from symmetric crypto
   :srcset: /api/gallery/crypto/public_keys/images/sphx_glr_plot_01_merkle_puzzles_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 67-72

Exercise
--------
Set the number of puzzles to 2**bits. Express Alice's, Bob's and Eve's work
in terms of N = 2**bits. If honest parties can afford 2**30 operations, how
much work does the attacker face? Compare with Diffie-Hellman.


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

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


.. _sphx_glr_download_api_gallery_crypto_public_keys_plot_01_merkle_puzzles.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/public_keys/plot_01_merkle_puzzles.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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