14-10-2010, 12:57 PM
[attachment=6022]
The RSA Cryptosystem
Orhan K AKYILDIZ
COMP5703 - Advanced Algorithms
oka[at]kayra.ca
Abstract
In this seminar report, we review public key cryptography, and RSA
public cyryptosystem in particular.
RSA public cryptosystem is a asymmetrical cryptosystem: it uses a
pair of keys, one of which is used to encrypt the data in such a way that
it can only be decrypted with the other key. The keys are generated
by a common process, but they can not be feasably generated from each
other. The relation between these keys relies on a NP-hard problem: in
virtually all cases, the function is a one-way function. There are a number
of such one-way functions that various cryptographic algorithms rely on,
including integer factorization, discrete logarithm, etc.
1 Introduction
A cryptosystem is a sytem that allows secure exchange of information over an
insecure channel [2],[3].
A crypto-system is typically modelled as a three-party system in which, a
sender (historically called `Alice' ) sends a message to a recipient (`Bob' ) over
an insecure channel, in the existance of an adversary (Eve), who tries to extract
information o, or potentially change, the message. Figure 1 on page 3 depicts
basic elements of a symmetric cryptosystem. Figure 2 on page 3 represents a
newer class of cryptosystems, called asymmetric cryptosystems.
A crypto-system is symmetrical when both encryption (the E(M; x) box in
gure 2) and decryption (the D(C; x) box) use the same key; in other words,
e and d are the same. Note that, it would not be wise to send the key on an
insecure channel in this case, as the adversary will then be able to capture the
key and will be able to gain control on the message.