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.
