The RSA cryptosystem is a public-key system based on modular exponentiation and the difficulty of factoring a product
of two large primes. To generate keys, choose distinct
primes and
, set
, choose a positive
integer encryption exponent
relatively prime to
, where
is the totient function,
and choose a positive integer
such that
. The pair
is public, while
and the factorization of
are private.
For an integer message representative , RSA encryption
computes
, and decryption recovers
. RSA signatures reverse the private and
public exponents: a signer computes a representative
, and verification checks
.
For integer message representatives and
, the textbook operation
satisfies
. It is thus multiplicative homomorphic
encryption. Practical RSA uses encoding and padding schemes rather than applying
these textbook operations directly to a message.