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


Lamport one-time signatures: signing with only a hash (1979)
============================================================

Lamport built a signature from nothing but a one-way function. The private
key is 256 pairs of random strings; the public key is their hashes. To sign,
reveal one string from each pair, chosen by the bits of the message digest.

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

A signature verifies, and changing the message breaks it. But every
signature reveals half the private key: after a few signatures an attacker
can sign new messages. The key must sign exactly once. Because security
needs only a one-way hash, the idea survives quantum computers; it is the
ancestor of today's standardized SPHINCS+ (SLH-DSA).

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-25

Sign once, verify
-----------------

.. GENERATED FROM PYTHON SOURCE LINES 25-36

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    key = bk.crypto.lamport_keypair(b"teaching seed, never reuse")
    signature = bk.crypto.lamport_sign(b"pay Bob 10", key)
    assert bk.crypto.lamport_verify(b"pay Bob 10", signature, key.public)
    assert not bk.crypto.lamport_verify(b"pay Bob 99", signature, key.public)
    print(len(signature), "revealed preimages,", sum(map(len, signature)), "bytes")






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

 .. code-block:: none

    256 revealed preimages, 8192 bytes




.. GENERATED FROM PYTHON SOURCE LINES 37-41

Reusing the key leaks it
------------------------
Collect the preimages revealed by k signatures, then count how many random
messages an attacker could now sign (every digest bit must be covered).

.. GENERATED FROM PYTHON SOURCE LINES 41-74

.. code-block:: Python

    def forgeable_fraction(signed_count: int, trials: int = 300) -> float:
        known = set()
        for i in range(signed_count):
            message = f"message {i}".encode()
            for position, revealed in enumerate(bk.crypto.lamport_sign(message, key)):
                bit = key.private[position].index(revealed)
                known.add((position, bit))
        hits = 0
        for t in range(trials):
            digest = int.from_bytes(bk.crypto.sha256(f"forgery {t}".encode()), "big")
            bits = [(digest >> (255 - i)) & 1 for i in range(256)]
            hits += all((i, b) in known for i, b in enumerate(bits))
        return hits / trials


    counts = list(range(1, 13))
    observed = [forgeable_fraction(k) for k in counts]
    expected = [(1 - 0.5**k) ** 256 for k in counts]
    assert observed[0] == 0 and observed[-1] > 0.8

    fig, ax = plt.subplots(figsize=(7, 4))
    ax.plot(counts, observed, "o", label="measured")
    ax.plot(
        counts, expected, "-", color="black", label="expected over random messages: (1 - 2**-k)**256"
    )
    ax.set(
        xlabel="signatures made with one key",
        ylabel="fraction of messages forgeable",
        title="A one-time key used many times",
    )
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/hash_signatures/images/sphx_glr_plot_01_lamport_signatures_001.png
   :alt: A one-time key used many times
   :srcset: /api/gallery/crypto/hash_signatures/images/sphx_glr_plot_01_lamport_signatures_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 75-80

Exercise
--------
A Lamport public key is 16 KiB. Merkle (1979) signed many messages by
putting many one-time public keys in a hash tree and publishing only its
root. How big is a proof that one key belongs to a tree of 2**20 keys?


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

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


.. _sphx_glr_download_api_gallery_crypto_hash_signatures_plot_01_lamport_signatures.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/hash_signatures/plot_01_lamport_signatures.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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