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


Baby-step giant-step: square-root discrete logs (Shanks 1971)
=============================================================

Diffie-Hellman and Schnorr are safe only if recovering x from g**x is hard.
Trying every exponent costs n steps in a group of order n. Shanks showed a
time-memory trade-off that costs about 2*sqrt(n): store m = sqrt(n) "baby
steps" g**j, then take "giant steps" target * g**(-m*i) until one matches.

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

The measured work follows 2*sqrt(n), far below n. The square root sets the
security level: a group of order 2**256 gives about 2**128 work, which is
why 256-bit curves are said to offer 128-bit security.

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

.. GENERATED FROM PYTHON SOURCE LINES 21-23

Recover a secret exponent
-------------------------

.. GENERATED FROM PYTHON SOURCE LINES 23-35

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    import blockchainkit as bk

    group = bk.crypto.DHGroup(1019, 509, 4)  # Order-509 subgroup of the integers mod 1019.
    secret = 377
    public = group.public(secret)
    result = bk.crypto.baby_step_giant_step(group.g, public, group.p, group.q)
    assert result.exponent == secret
    print(f"log_4({public}) = {result.exponent} after {result.group_operations} multiplications")





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

 .. code-block:: none

    log_4(767) = 377 after 40 multiplications




.. GENERATED FROM PYTHON SOURCE LINES 36-39

Work grows like the square root of the group order
--------------------------------------------------
Safe primes p = 2q + 1, with 4 generating the order-q subgroup.

.. GENERATED FROM PYTHON SOURCE LINES 39-59

.. code-block:: Python

    safe_primes = [
        p for p in range(1000, 200_000) if bk.crypto.is_prime(p) and bk.crypto.is_prime((p - 1) // 2)
    ]
    chosen = safe_primes[:: max(1, len(safe_primes) // 12)]
    orders, work = [], []
    for p in chosen:
        q = (p - 1) // 2
        target = pow(4, q - 1, p)  # The largest exponent: the worst case.
        orders.append(q)
        work.append(bk.crypto.baby_step_giant_step(4, target, p, q).group_operations)

    fig, ax = plt.subplots(figsize=(7, 4))
    ax.loglog(orders, work, "o", label="baby-step giant-step")
    grid = np.array(orders, dtype=float)
    ax.loglog(grid, 2 * np.sqrt(grid), "--", color="black", label="2 sqrt(n)")
    ax.loglog(grid, grid, ":", color="#b45309", label="brute force: n")
    ax.set(xlabel="group order n", ylabel="group operations", title="Square-root discrete logs")
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/discrete_log/images/sphx_glr_plot_01_baby_step_giant_step_001.png
   :alt: Square-root discrete logs
   :srcset: /api/gallery/crypto/discrete_log/images/sphx_glr_plot_01_baby_step_giant_step_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 60-65

Exercise
--------
The baby-step table needs sqrt(n) memory. Estimate its size in bytes for
n = 2**64 and for n = 2**256. Pollard's rho method (1978) needs almost no
memory for the same running time: why does that make memory no defense?


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

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


.. _sphx_glr_download_api_gallery_crypto_discrete_log_plot_01_baby_step_giant_step.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/discrete_log/plot_01_baby_step_giant_step.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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