Others view: satellites of saturn ♦ Quicksort algorithm ♦ Welcome ♦ 2D Fast Fourier Transform ♦ TicTacToe (game) ♦ XOR gate ♦ Forum and issue tracker ♦ JAMWiki ♦ Nussinov algorithm ♦ atomic orbitals ♦

RSA encryption algorithm

RSA is a widely used asymmetric encryption algorithm algorithm that, if properly implemented, so far cannot be cracked in acceptable time. RSA can be used for user authentication, data encryption and digital data signing. As any asymmetric algorithm RSA uses two separate keys[1]. One of these two keys is used to encode (encrypt) the message on the sender side, another is used to decode (decrypt) the message on the receiver side. One of these two keys is usually kept secret, restricting access to it (private key) and another is public and can be known to everyone.

Having two keys allows to initiate secure communication through public unprotected channels without the need to pass the private key to other side. As others asymmetric algorithms, RSA can be used in the following ways:

  1. Any sender uses widely known public key to encrypt the message. Only receiving person who also knows the private key can decrypt it. While all senders know the public key they cannot use it to decrypt each other's messages.
  2. A sender uses the private key can encrypt the hashcode of the message and attach it as a public electronic signature. The sender uses the pubic key to decrypt this hashcode and check it against the hashcode, computed directly from the text of the message. If they do not match, this proves that the message has been forged or altered on a way. Everybody can check the signature but only the owner of the private key can sign new messages.
  3. A guard says a challenge (arbitrary short string) that the passing person must return encoded with her private key. The guard then uses widely known public key to decrypt it and checks if the challenge phrase matches. As the challenge phrase is different every time, it is not possible to pass through the guard by replaying the spied phrase from the previous authentication session. Also, the guard cannot use his information to pass another guards, as he only knows the public key.

Security

RSA has been searched for security vulnerabilities for over 30 years (see 1998 year review[2]. The algorithm has a strong mathematical background and so far theoretically cannot be broken in acceptable time. However concrete implementations of RSA may be sensitive to side channel attacks, misinterpreting whom belongs the private key of the known public key and other potential security flaws that are not related to the algorithm itself.

The most sensitive targets are timing attacks[3] (if it is possible to measure very precisely how much it took for CPU to do authentication) and power attacks (if it is possible to record the precise power consumption profile that reflects the sequence of commands, actually executed by CPU). This is especially dangerous if timing and power profiles are available with high accuracy, as seen by oscilloscope, directly attached to the authenticating device. Also, it is a big advantage for the attacker to have possibility to experiment with the exact copy of the hardware and software stack the victim uses. The attack is much more difficult over network due induced network latency; however the attack over very fast and small local network may be possible.

These vulnerabilities are closed by using "cryptographic blinding" countermeasures that make both timing and power data also dependent on "on the fly" generated random number, preventing an easy attack.

There were some publications claiming that the RSA has been cracked "on a server" using timing channel attacks, but in this work the server cooperated with intruder providing precise times on how long it took to run the algorithm. In other study, the authors did recovered a key by varying CPU voltage outside approved boundaries (that caused multiple power faults)[4]. Again, Bernstein (2001) [5] did recovered a key but that key was much shorter that the keys practically used in the industry[6]. Some companies manufacture cryptographic extension cards that they think are more secure than software-based solutions[7] and still protects sensitive keys even after intruder gets physical access to the server box.


The algorithm is especially valuable because it is not relying on secrets how does the algorithm works; the source code can be public and the authentication is still secure. Ultrastudio.org server is also managed using RSA keys for authentication.

The algorithm

  1. Choose two distinct prime numbers, p and q.
  2. Let n = pq.
  3. Let φ(pq) = (p − 1)(q − 1). (φ is totient function).
  4. Pick an integer e such that 1 < e < φ(pq), and e and φ(pq) share no divisors other than 1 (e and φ(pq) are coprime).
  5. Find d which satisfies
.

d is a secret private key exponent.

  1. The public key consists of e (often called public exponent) and n(often called modulus). The private key consists of e and d (private exponent).

The message m is encrypted using formula

where c is the encrypted message. The encrypted message is decrypted using formula

Encryption and decryption formulas show how to encode and decode a single integer. Bigger (or different) pieces of information are encoded by converting them into (potentially large) integers first. As RSA is not particularly fast, it is usually only to encrypts the key of some faster algorithm. After RSA decrypts the key, this supplementary algorithm uses it to decrypt the rest of the message.

RSA algorithm is fundamentally based on the Euler theorem:

where a and n are positive integers and a is a co-prime to n.

To break the algorithm from the mathematical side, one needs to solve the factoring problem (find the two prime numbers that, when multiplied, produce the given result). When the picked numbers are large enough, the problem cannot be easily solved by brute force and at least currently it also does not have easier analytic solution.

References

  1. 1 Charles P.Pfleeger, Shari Lawrence Pfleeger. Security in Computing. Fourth edition. ISBN 0-13-239077-9
  2. 2 D. Boneh. Twenty years of attacks on the RSA cryptosystem
  3. 3 Onur Acıi, Cetin Kaya KoJean-Pierre Seifert On the Power of Simple Branch Prediction Analysis.
  4. 4 Andrea Pellegrini, Valeria Bertacco and Todd Austin. Fault-Based Attack of RSA Authentication
  5. 5 J. Bernstein. Circuits for Integer Factorization: A Proposal. Manuscript, November 2001.
  6. 6 R. Silverman Has the RSA algorithm been compromised as a result of Bernstein's Paper?
  7. 7 IBM PCIe Cryptographic Coprocessor