[JoGu]

Cryptology

III.1 The RSA Cipher and its Algorithmic Foundations
a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

Contents

  1. Description of the RSA cipher [PDF]
  2. The binary power algorithm [PDF]
  3. The CARMICHAEL function [PDF]
  4. Suitable parameters for RSA [PDF]

The complete Chapter III.1 as an PDF file

Overview

The most important—that is, most applied and most analyzed—asymmetric cipher is RSA, named after its inventors Ron RIVEST, Adi SHAMIR, and Len ADLEMAN. It uses elementary number theoretic algorithms, and its supposed security relies on the hardness of factoring large numbers into primes, although breaking RSA might be easier then factoring, see Section 2.2.

The three fundamental arithmetic algorithms for implementing RSA are

the last two of them known from Part I of these lectures (in the context of linear ciphers as appendix of Chapter 9). These algorithms are basic not only for cryptography but more generally for algorithmic algebra and number theory (»computer algebra«). Moreover they are fundamental also for numerical mathematics—for problems that don't require approximate numerical solutions in floating-point numbers but exact solutions in integers, rationals, or symbolic expressions.

Author: Klaus Pommerening, 2000-May-21; last change: 2021-Feb-15