Cryptography Reference
In-Depth Information
[Salo], and [Stin] as introductory sources, to the more comprehensive works
[MOV] and [Schn], and to the more mathematically oriented monographs [Kobl],
[Kran], and [HKW].
17.2 The RSA Algorithm
All that is merely probable is probably false.
—René Descartes
We shall now present a brief outline of the mathematical properties of the RSA
algorithm, and we shall see how the RSA procedure can be implemented both as
an asymmetric cryptosystem and an asymmetric signature scheme. Following the
mathematical principles of the RSA algorithm we shall develop C++ classes with
RSA functions for encryption and decryption as well as for the generation and
authentication of digital signatures. In this way we shall clarify the possibilities
offered for the implementation of the methods of our LINT class.
The most important aspect of the RSA algorithm is the pair of keys, which
have a particular mathematical form: An RSA key pair consists of three basic
components: the modulus n , the public key component e (encryption), and the
secret key component d (decryption). The pairs
e, n
d, n
and
then form a
public and private key.
We first generate the modulus n as the product n = pq of two prime numbers
p and q .If φ ( n )=( p
1) denotes the Euler phi function (cf. page 177),
then for a given n the public key component e can be chosen such that e<φ ( n )
and gcd ( e, φ ( n ))=1 . The secret component d corresponding to n and e is
obtained by calculating the inverse d = e 1 mod φ ( n ) (cf. Section 10.2).
We illustrate this principle with the help of a small example: We choose p =7
and q =11 . Then we have n =77 and φ ( n )=2 2
1) ( q
· 3 · 5=60 . Due to the
condition gcd ( e, φ ( n )) = 1 , the least possible value for the key component
e is 7 , from which we derive the value d =43 for the key component d , since
7 · 43 301 1mod60 . With these values we can apply the RSA algorithm
to a toy example, in which we calculate, say, that the “message” 5 is encrypted
to 5 7 mod77=47 and the decryption 47 43 mod77=5 restores the original
message.
Equipped now with such keys (we shall soon discuss what constitutes
a realistic size for the various key components) and appropriate software,
communication partners can securely exchange information with each other. To
demonstrate the procedure we consider the process by which a participant Ms. A
sends an RSA-encoded message to a communication partner Mr. B :
1. B generates his RSA key with components n B , d B ,and e B . He then gives the
public key
e B ,n B
to A .
 
Search WWH ::




Custom Search