Cryptography Reference
In-Depth Information
1. Unconditional Security or Perfect Secrecy: A cryptosystem is called un-
conditionally secure if it cannot be broken, even with infinite computa-
tional resources.
2. Computational Security: A cryptosystem is called computationally se-
cure if the best known algorithm for breaking it requires at least N
operations, where N is some specified, very large number.
3. Provable Security: A cryptosystem is called provably secure if it is as dif-
ficult to break as solving some well-known and supposedly di
cult (such
as NP-hard [30]) problem. It is important to note that a cryptosystem
based on a hard problem does not guarantee security. For example, the
worst case complexity for solving a problem may be exponential, but the
average case complexity or the complexity for some specific instances of
the problem may be polynomial.
1.6 Private and Public Key Cryptosystems
There are two types of cryptosystems: (1) private or symmetric and (2)
public or asymmetric.
1. Private Key Cryptosystem or Symmetric Key Cryptosystem. Here we
have a single secret key k = k
e
= k
d
, shared between the sender (Alice)
and the receiver (Bob). Alice and Bob agree upon the key prior to
communication (either through face-to-face discussion when they were
together, or through some secure channel).
Private or symmetric key cryptosystems are further divided into two
classes:
(a) Block Cipher. It is a memory-less (or state-less) permutation algo-
rithm that breaks a plaintext m into successive blocks m
1
,m
2
,...,
and encrypts each block with the same key k. Thus,
E
k
(m) = E
k
(m
1
)E
k
(m
2
)....
The decryption function is the inverse permutation algorithm.
(b) Stream Cipher. It is a finite state machine with internal mem-
ory that breaks a plaintext m into successive characters or bits
m
1
,m
2
,..., and encrypts each m
r
with a different key k
r
from a
keystream k = k
1
,k
2
,.... Thus,
E
k
(m) = E
k
1
(m
1
)E
k
2
(m
2
)....
