RSA algorithm
Summary
RSA is a foundational algorithm of public key cryptography. Any public key cryptography algorithm has the following form: an encryption function that is publicly accessible (including to eavesdroppers or malicious parties) and a decryption function
that is known to only the party doing decryption, such that
is the identity map.
The idea is that should not be easy to deduce from
.
The way it is used in practice is as follows: if wants to send a message to
but their only channel of communication is accessible to
. So,
looks up
's public encryption key (accessible to
as well), then sends
the message encrypted using that key, which
decrypts using the decryption key.
has access to the encrypted message and the encryption key, but cannot decrypt because of lack of access to the decryption key.
For a public key cryptography algorithm, the general format of both the encryption and decryption algorithms are known to everybody. The actual encryption algorithm depends additionally on knowledge of a specific number/string called the encryption key and the actual decryption algorithm depends on knowledge of a decryption key. Another way of putting this is thus that it should not be possible to quickly determine the decryption key from the encryption key. Actually, we want something stronger -- there should be no way to perform decryption based solely on knowledge of the encryption key.
General idea
RSA relies on the idea (or belief) that the root computation problem in a group does not have any simple reduction to the power computation problem if the order of the group is not known. The idea is as follows:
- First, come up with a general family of encodings of groups where the basic black-box group operations (multiplication, inverse, identity element, membership testing) are known and can be performed quickly, but the order of the group is known only to the party that constructs the group and is not known to other parties.
- Second, the party that has constructed a group selects two integers
such that
is congruent to 1 modulo the order of the group.
, the encryption key is published to all, and
is kept secret.
- The encryption algorithm (publicly accessible) works as follows on the elements of the group: an element
of the group is encrypted to
(i.e., the power computation problem) and an element
of the group is decrypted to
. (Note: This algorithm works on elements of the group, but combined with standard algorithms, it can be used to encrypt any string).
Here is a summary:
Party | Does this party know the order of the group? | Can this party access the group encoding and do the group operations? | Does this party know the encryption key? | Does this party know the decryption key? | Does this party know the encrypted message? | Does this party know the original message? |
---|---|---|---|---|---|---|
encrypting party ![]() |
No | Yes, these are necessary for the encryption algorithm | Yes, this is necessary for the encryption algorithm | No | Yes, after performing the encryption | Yes, it created the original message |
decrypting party ![]() |
Yes, ![]() |
Yes | Yes, ![]() |
Yes, ![]() |
Yes, after receiving it | Yes, after receiving and decrypting it |
third party ![]() |
No | Yes, because these are publicly available because ![]() |
Yes, publicly available because ![]() |
No | Yes, because the message is communicated on a channel that ![]() |
No, because ![]() |