.. 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_03_rsa.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_03_rsa.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_03_rsa.py:


RSA: a public trapdoor (Rivest, Shamir and Adleman 1978)
========================================================

RSA publishes n = p*q and an exponent e; only the holder of p and q can
compute the inverse exponent d. Anyone can raise a message to e; only the
key holder can undo it. The same inverse pair gives digital signatures.

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

The message 65 encrypts to 2790 and decrypts back. Then textbook RSA's
algebra shows through: multiplying a ciphertext by 2**e doubles the hidden
message. Real RSA adds randomized padding (OAEP, PSS) to break this.

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 21-23

Encrypt and decrypt
-------------------

.. GENERATED FROM PYTHON SOURCE LINES 23-33

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    key = bk.crypto.rsa_keypair()  # p = 61, q = 53, e = 17: the classic textbook key.
    ciphertext = key.encrypt(65)
    assert (ciphertext, key.decrypt(ciphertext)) == (2790, 65)
    print("n =", key.n, "e =", key.e, "d =", key.d)
    print("RSA: 65 ->", ciphertext, "->", key.decrypt(ciphertext))





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

 .. code-block:: none

    n = 3233 e = 17 d = 2753
    RSA: 65 -> 2790 -> 65




.. GENERATED FROM PYTHON SOURCE LINES 34-36

Signatures are the same operation in reverse
--------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 36-39

.. code-block:: Python

    signature = key.decrypt(42)  # Apply the private exponent.
    assert key.encrypt(signature) == 42  # Anyone can check with the public one.








.. GENERATED FROM PYTHON SOURCE LINES 40-43

Textbook RSA is malleable
-------------------------
Multiplying a ciphertext by 2**e multiplies the decrypted message by 2.

.. GENERATED FROM PYTHON SOURCE LINES 43-47

.. code-block:: Python

    modified = ciphertext * pow(2, key.e, key.n) % key.n
    assert key.decrypt(modified) == 130
    print("Malleated ciphertext decrypts to", key.decrypt(modified))





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

 .. code-block:: none

    Malleated ciphertext decrypts to 130




.. GENERATED FROM PYTHON SOURCE LINES 48-50

A permutation of the residues
-----------------------------

.. GENERATED FROM PYTHON SOURCE LINES 50-56

.. code-block:: Python

    fig, ax = plt.subplots(figsize=(7, 3.8))
    messages = list(range(60))
    ax.scatter(messages, [key.encrypt(m) for m in messages], s=18, color="#7c3aed")
    ax.set(xlabel="message m", ylabel="ciphertext m**e mod n", title="Textbook RSA permutation")
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/public_keys/images/sphx_glr_plot_03_rsa_001.png
   :alt: Textbook RSA permutation
   :srcset: /api/gallery/crypto/public_keys/images/sphx_glr_plot_03_rsa_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 57-61

Exercise
--------
Factor n = 3233 by trial division and recompute d. Explain why a
scrambled-looking plot is not evidence of secure encryption.


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

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


.. _sphx_glr_download_api_gallery_crypto_public_keys_plot_03_rsa.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_03_rsa.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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