File RSA.h

↰ Parent directory (ADS/numeric)

The public key cryptosystem RSA of the reality check of section 17.3, on integers of 64 bits, a toy that shows the method and is not secure: the keys need some thousand bits.

Definition (ADS/numeric/RSA.h)

Detailed Description

Three random primes s, x and y, found by Miller-Rabin, give N = x y and the public exponent p with :math:` p s bmod ( x - 1 ) ( y - 1 ) = 1 ; the public key is ( N , p ), the private one ( N , s ), :math: C = M^p bmod N ` encrypts and :math:` M = C^s bmod N ` decrypts, since :math:` M^{p s} bmod N = M `. Signing is decrypting with the private key, checking is encrypting with the public one.

The contracts [see File Contract.h]: randomPrime() needs 2 <= bits <= 63 and gives an odd number of exactly that many bits; the keys of rsaKeys() undo each other, checked on the message 2; rsa() needs a message M < N. The functions are defined in RSA.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 17.3, https://algoritmicamente.it/materiali/libro/capitoli/cap17.pdf

    1. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21(2), 120-126, 1978, doi:10.1145/359340.359342

    1. Miller, Riemann’s hypothesis and tests for primality, Journal of Computer and System Sciences 13(3), 300-317, 1976, doi:10.1016/S0022-0000(76)80043-8

    1. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12(1), 128-138, 1980, doi:10.1016/0022-314X(80)90084-0

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions