cryptography and ntk security 2 019/20

CH 2 - PUBLIC KEY CRYPTOGRAPHY

2.1 Key Management
The concept of public-key cryptography evolved from an attempt to attack two of the most
difficult problems associated with symmetric encryption.

 The first problem is that of key distribution:- key distribution under symmetric
encryption requires either (1) that two communicants already share a key, which
somehow has been distributed to them; or (2) the use of a key distribution center.
Whitfield Diffie, one of the discoverers of public-key encryption (along with Martin
Hellman, both at Stanford University at the time), reasoned that this second requirement
negated the very essence of cryptography: the ability to maintain total secrecy over your
own communication. As Diffie put it [DIFF88], “what good would it do after all to
develop impenetrable cryptosystems, if their users were forced to share their keys with a
KDC that could be compromised by either burglary or subpoena?”
 The second problem that Diffie pondered, and one that was apparently unrelated to the
first, was that of digital signatures. If the use of cryptography was to become widespread,
not just in military situations but for commercial and private purposes, then electronic
messages and documents would need the equivalent of signatures used in paper
documents. That is, could a method be devised that would stipulate, to the satisfaction of
all parties, that a digital message had been sent by a particular person. This is a somewhat
broader requirement than that of authentication. Diffie and Hellman achieved an
astounding breakthrough in 1976 [DIFF76 a, b] by coming up with a method that
addressed both problems and was radically different from all previous approaches to
cryptography, going back over four millennia.

Key exchange can also be done using elliptic curves.

2.2 Public-Key Cryptosystems

Asymmetric algorithms rely on one key for encryption and a different but related key for
decryption. As the names suggest, the public key of the pair is made public for others to use,
while the private key is known only to its owner. These algorithms have the following important
characteristic:

 It is computationally infeasible to determine the decryption key given only knowledge of

the cryptographic algorithm and the encryption key.
In addition, some algorithms, such as RSA, also exhibit the following characteristic:

1
 cryptography and ntk security 2 019/20

 Either of the two related keys can be used for encryption, with the other used for
decryption.
A public-key encryption scheme has six ingredients (Figure 2.1):

 Plaintext: This is the readable message or data that is fed into the algorithm as input.
 Encryption algorithm: The encryption algorithm performs various transformations on
the plaintext.
 Public and private keys: This is a pair of keys that have been selected so that if one is
used for encryption, the other is used for decryption. The exact transformations
performed by the algorithm depend on the public or private key that is provided as input.
 Ciphertext: This is the scrambled message produced as output. It depends on the
plaintext and the key. For a given message, two different keys will produce two different
ciphertexts.
 Decryption algorithm: This algorithm accepts the ciphertext and the matching key and
produces the original plaintext.
The essential steps are the following:
1. Each user generates a pair of keys to be used for the encryption and decryption of
messages.
2. Each user places one of the two keys in a public register or other accessible file. This is
the public key. The companion key is kept private. As Figure 2.1.a suggests, each user
maintains a collection of public keys obtained from others.
3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message using
Alice's public key.
4. When Alice receives the message, she decrypts it using her private key. No other
recipient can decrypt the message because only Alice knows Alice's private key.
As long as a user's private key remains protected and secret, incoming communication is secure.
At any time, a system can change its private key and publish the companion public key to replace
its old public key.

2
 cryptography and ntk security 2 019/20

Figure 2.1. Public-Key Cryptography

 Applications for Public-Key Cryptosystems

Public-key systems are characterized by the use of a cryptographic algorithm with two keys, one
held private and one available publicly. Depending on the application, the sender uses either the
sender's private key or the receiver's public key, or both, to perform some type of cryptographic
function. In broad terms, we can classify the use of public-key cryptosystems into three
categories:

 Encryption/decryption: The sender encrypts a message with the recipient's public key.
 Digital signature: The sender "signs" a message with its private key. Signing is achieved
by a cryptographic algorithm applied to the message or to a small block of data that is a
function of the message.
 Key exchange: Two sides cooperate to exchange a session key. Several different
approaches are possible, involving the private key(s) of one or both parties.
Some algorithms are suitable for all three applications, whereas others can be used only for one
or two of these applications. RSA is suitable for all three applications. Table 2.1 indicates the
applications supported by some of public-key encryption algorithms

3
 cryptography and ntk security 2 019/20

Table 2.1 Applications for Public-Key Cryptosystems

 Requirements for Public-Key Cryptography
1. It is computationally easy for a party B to generate a pair (public key PU b, private key
PRb).
2. It is computationally easy for a sender A, knowing the public key and the message to be
encrypted, M, to generate the corresponding ciphertext:
C = E(PUb, M)
3. It is computationally easy for the receiver B to decrypt the resulting ciphertext using the
private key to recover the original message:
M = D(PRb, C) = D[PRb, E(PUb, M)]
4. It is computationally infeasible for an adversary, knowing the public key, PU b, to
determine the private key, PRb.
5. It is computationally infeasible for an adversary, knowing the public key, PU b, and a
ciphertext, C, to recover the original message, M.
We can add a sixth requirement that, although useful, is not necessary for all public-key
applications:

6. The two keys can be applied in either order:

M = D[PUb, E(PRb, M)] = D[PRb, E(PUb, M)]
These are formidable requirements, as evidenced by the fact that only a few algorithms (RSA,
elliptic curve cryptography, Diffie-Hellman, DSS) have received widespread acceptance in the
several decades since the concept of public-key cryptography was proposed.

2.3 Confidentiality using Symmetric Encryption

Traditionally symmetric encryption is used to provide message confidentiality.

 Placement of Encryption Function

There are a large number of locations at which an attack can occur. Furthermore, for wide area
communications, many of these locations are not under the physical control of the end user. Even
in the case of local area networks, in which physical security measures are possible, there is
always the threat of the disgruntled employee.

4
 cryptography and ntk security 2 019/20

The most powerful and most common approach to securing the points of vulnerability is
encryption. If encryption is to be used to counter these attacks, then we need to decide what to
encrypt and where the encryption gear should be located. There are two fundamental
alternatives: link encryption and end-to-end encryption.

Figure 2.2: Encryption across a Packet-Switching Network

i) Link to Link Encryption

With link encryption, each vulnerable communications link is equipped on both ends with an
encryption device. Thus, all traffic over all communications links is secured. One of its
disadvantages is that the message must be decrypted each time it enters a switch because the
switch must read the address (logical connection number) in the packet header in order to route
the frame. Thus, the message is vulnerable at each switch. If working with a public network, the
user has no control over the security of the nodes.

Several implications of link encryption should be noted. For this strategy to be effective, all the
potential links in a path from source to destination must use link encryption (See Figure 2.2
above). Each pair of nodes that share a link should share a unique key, with a different key used
on each link. Thus, many keys must be provided.

ii) End-To-End Encryption

With end-to-end encryption, the encryption process is carried out at the two end systems. The
source host or terminal encrypts the data. The data in encrypted form are then transmitted
unaltered across the network to the destination terminal or host. The destination shares a key
with the source and so is able to decrypt the data. This plan seems to secure the transmission

5
 cryptography and ntk security 2 019/20

against attacks on the network links or switches. Thus, end-to-end encryption relieves the end
user of concerns about the degree of security of networks and links that support the
communication. There is, however, still a weak spot.

With end-to-end encryption, the user data are secure. However, the traffic pattern is not, because
packet headers are transmitted in the clear. On the other hand, end-to-end encryption does
provide a degree of authentication. If two end systems share an encryption key, then a recipient
is assured that any message that it receives comes from the alleged sender because only that
sender shares the relevant key. Such authentication is not inherent in a link encryption scheme.

To achieve greater security, both link and end-to-end encryptions are needed, as is shown in
Figure 2.2. When both forms of encryption are employed, the host encrypts the user data portion
of a packet using an end-to-end encryption key. The entire packet is then encrypted using a link
encryption key. As the packet traverses the network, each switch decrypts the packet, using a
link encryption key to read the header, and then encrypts the entire packet again for sending it
out on the next link. Now the entire packet is secure except for the time that the packet is actually
in the memory of a packet switch, at which time the packet header is in the clear.

Link Encryption End-to-End Encryption

Link encryption encrypts all the data along a End-to-end encryption, the headers, addresses,
specific communication path. Not only is the routing, and trailer information are not
user information encrypted, but the header, encrypted, enabling attackers to learn more
trailers, addresses, and routing data that are part about a captured packet and where it is headed.
of the packets are also encrypted.

All data are encrypted, including headers, Headers, addresses, and routing information
addresses, and routing information. are not encrypted, and therefore not protected.

It works at a lower layer in the OSI model. It works at Network layer.

All of the information is encrypted, and the The packets do not need to be decrypted and
packets must be decrypted at each hop so the then encrypted again at each hop, because the
router, or other intermediate device, knows headers and trailers are not encrypted.
where to send the packet next.

Table 2.2: Summary of link and end-to-end encryptions

 Traffic Confidentiality
The following types of information that can be derived from a traffic analysis attack:
 Identities of partners

6
 cryptography and ntk security 2 019/20

 How frequently the partners are communicating

 Message pattern, message length, or quantity of messages that suggest important
information is being exchanged
 The events that correlate with special conversations between particular partners
Another concern related to traffic is the use of traffic patterns to create a covert channel.
Typically, the channel is used to transfer information in a way that violates a security policy. For
example, an employee may wish to communicate information to an outsider in a way that is not
detected by management and that requires simple eavesdropping on the part of the outsider.

With the use of link encryption, network-layer headers (e.g., frame or cell header) are
encrypted, reducing the opportunity for traffic analysis. However, it is still possible in those
circumstances for an attacker to assess the amount of traffic on a network and to observe the
amount of traffic entering and leaving each end system. An effective countermeasure to this
attack is traffic padding.

Traffic padding produces ciphertext output continuously, even in the absence of plainext. A
continuous random data stream is generated. When plaintext is available, it is encrypted and
transmitted. When input plaintext is not present, random data are encrypted and transmitted. This
makes it impossible for an attacker to distinguish between true data flow and padding and
therefore impossible to deduce the amount of traffic.

Traffic padding is essentially a link encryption function. If only end-to-end encryption is

employed, then the measures available to the defender are more limited. For example, if
encryption is implemented at the application layer, then an opponent can determine which
transport entities are engaged in dialogue.

One technique that might prove useful is to pad out data units to a uniform length at either the
transport or application level. In addition, null messages can be inserted randomly into the
stream. These tactics deny opponent knowledge about the amount of data exchanged between
end users and obscure the underlying traffic pattern.
 Key Distribution

For symmetric encryption to work, the two parties to an exchange must share the same key, and
that key must be protected from access by others. Furthermore, frequent key changes are usually
desirable to limit the amount of data compromised if an attacker learns the key. Therefore, the
term that refers to the means of delivering a key to two parties who wish to exchange data,

7
 cryptography and ntk security 2 019/20

without allowing others to see the key. For two parties A and B, key distribution can be achieved
in a number of ways, as follows:

1. A can select a key and physically deliver it to B.

2. A third party can select the key and physically deliver it to A and B.
3. If A and B have previously and recently used a key, one party can transmit the new key
to the other, encrypted using the old key.
4. If A and B each has an encrypted connection to a third party C, C can deliver a key on the
encrypted links to A and B.
Physical delivery (1 & 2) is simplest - but only applicable when there is personal contact
between recipient and key issuer. This is fine for link encryption where devices & keys occur in
pairs, but does not scale as number of parties who wish to communicate grows. 3 is mostly based
on 1 or 2 occurring first.

A third party (so called key distribution center-KDC), whom all parties trust, can be used as a
trusted intermediary to mediate the establishment of secure communications between them (4).
They must trust intermediary not to abuse the knowledge of all session keys. As number of
parties grows, some variant of 4 is only practical solution to the huge growth in number of keys
potentially needed.

The use of a key distribution center is based on the use of a hierarchy of keys. At a minimum,
two levels of keys are used.

 Communication between end systems is encrypted using a temporary key, often referred
to as a session key. Typically, the session key is used for the duration of a logical
connection and then discarded.

 Master key is shared by the key distribution center and an end system or user and used to
encrypt the session key.

2.4 Public Key Cryptography and RSA

The RSA scheme is a block cipher in which the plain text and cipher text are integers between 0
and n-1 for some n. A typical size for n is 1024 bits, or 309 decimal digits. That is, n is less than
2 1024

 Description of the RSA Algorithm

The scheme developed by Rivest, Shamir, and Adleman makes use of an expression with
exponentials. Plain text is encrypted in blocks, with each block having a binary value less than
some number n. That is, the block size must be less than or equal to log2(n); in practice, the

8
 cryptography and ntk security 2 019/20

block size is i bits, where 2i< n ≤ 2i+1. Encryption and decryption are of the following form, for
some plain text block M and cipher text block C:

C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
Both sender and receiver must know the value of n. The sender knows the value of e, and only
the receiver knows the value of d. Thus, this is a public-key encryption algorithm with a public
key of PU = {e, n} and a private key of PR = {d, n}. For this algorithm to be satisfactory for
public-key encryption, the following requirements must be met:

1. It is possible to find values of e, d, n such that Med mod n = M for all M < n.
2. It is relatively easy to calculate Me mod n and Cd mod n for all values of M < n.
3. It is infeasible to determine d given e and n.
For now, we focus on the first requirement and consider the other questions later. We need to
find a relationship of the form

Med mod n = M
The preceding relationship holds if e and d are multiplicative inverses modulo φ ( n ), where φ ( n )
is the Euler totient function. For p, q prime, φ ( pq ) = (p - 1)(q - 1). The relationship between e
and d can be expressed as

ed mod φ ( n )=1
This is equivalent to saying

ed  1 mod φ ( n )
d  e-1 mod φ ( n )
That is, e and d are multiplicative inverses mod φ ( n ). Note that, according to the rules of modular
arithmetic, this is true only if d (and therefore e) is relatively prime to φ ( n ). Equivalently, gcd(
φ ( n ),d) = 1.

We are now ready to state the RSA scheme. The ingredients are the following:

p,q, two prime numbers (private, chosen)

n = pq (public, calculated)
e, with gcd(φ ( n ), e) = 1;1 < e < φ ( n ) (public, chosen)
d  e (mod φ ( n ))
-1
(private, calculated)
The private key consists of {d, n} and the public key consists of {e, n}. Suppose that user A has
published its public key and that user B wishes to send the message M to A. Then B calculates C
= Me mod n and transmits C. On receipt of this cipher text, user A decrypts by calculating M =
Cd mod n. Table 2.3 summarizes the RSA algorithm.

Key Generation
9
 cryptography and ntk security 2 019/20

Select p , q p ∧q both prime , p ≠ q

Calculate n= p ×q
Calculate ∅ ( n ) =( p − 1 ) × ( q −1 )
Select integer e gcd ( ∅ ( n ) , e )=1 ; 1<e < ∅ ( n )
Calculate d d ≡e ( mod ∅ ( n ) )
−1

Public key PU = { e , n }
Private key PR= { d , n }
Encryption
Plaintext : M <n
Cipher text : C=M mod n
e

Decryption
Cipher text : C
Plaintext : M =C mod n
d

Table 2.3: The RSA Algorithm

An example is shown in Figure 2.3. For this example, the keys were generated as follows:
1. Select two prime numbers, p = 17 and q = 11.
2. Calculate n = pq = 17 x 11 = 187.
3. Calculate φ ( n ) = (p - 1)(q - 1) = 16 x 10 = 160.
4. Select e such that e is relatively prime to φ ( n ) = 160 and less than φ ( n )we choose
e = 7.
5. Determine d such that de  1 (mod 160) and d < 160. The correct value is d = 23,
because 23 x 7 = 161 = 10 x 16 + 1; d can be calculated using the extended
Euclid's algorithm.

Figure 2.3: Example of RSA Algorithm

The resulting keys are public key PU = {7,187} and private key PR = {23,187}. The example
shows the use of these keys for a plain text input of M = 88. For encryption, we need to calculate
C = 887 mod 187. Exploiting the properties of modular arithmetic, we can do this as follows:
887 mod 187 = [(884 mod 187) x (882 mod 187) x (881 mod 187)] mod 187
881 mod 187 = 88
882 mod 187 = 7744 mod 187 = 77
884 mod 187 = 59,969,536 mod 187 = 132
887 mod 187 = (88 x 77 x 132) mod 187 = 894,432 mod 187 = 11
For decryption, we calculate M = 1123 mod 187:
1123 mod 187 = [(111 mod 187) x (112 mod 187) x (114 mod 187) x (118 mod 187) x (118
mod 187)] mod 187
111 mod 187 = 11

10
 cryptography and ntk security 2 019/20

112 mod 187 = 121

114 mod 187 = 14,641 mod 187 = 55
118 mod 187 = 214,358,881 mod 187 = 33
1123 mod 187 = (11 x 121 x 55 x 33 x 33) mod 187 = 79,720,245 mod 187 = 88
 Key Generation
Before the application of the public-key cryptosystem, each participant must generate a pair of
keys. This involves the following tasks:
 Determining two prime numbers, p and q
 Selecting either e or d and calculating the other
First, consider the selection of p and q. Because the value of n = pq will be known to any
potential adversary, to prevent the discovery of p and q by exhaustive methods, these primes
must be chosen from a sufficiently large set (i.e. p and q must be large numbers). On the other
hand, the method used for finding large primes must be reasonably efficient. The procedure for
picking a prime number is as follows.
1. Pick an odd integer n at random (e.g., using a pseudorandom number generator).
2. Pick an integer a < n at random.
3. Perform the probabilistic primality test, such as Miller-Rabin, with a as a parameter. If n
fails the test, reject the value n and go to step 1.
4. If n has passed a sufficient number of tests, accept n; otherwise, go to step 2.
This is a somewhat tedious procedure. However, remember that this process is performed
relatively infrequently: only when a new pair (PU, PR) is needed.
 The Security of RSA
Four possible approaches to attacking the RSA algorithm are as follows:
 Brute force: This involves trying all possible private keys.
 Mathematical attacks: There are several approaches, all equivalent in effort to factoring
the product of two primes.
 Timing attacks: These depend on the running time of the decryption algorithm.
 Chosen cipher text attacks: This type of attack exploits properties of the RSA
algorithm.
Conventional Encryption Public-Key Encryption
Needed to Work: Needed to Work:
1. The same algorithm with the same key is used for 1. One algorithm is used for encryption and
encryption and decryption. decryption with a pair of keys, one for
2. The sender and receiver must share the algorithm encryption and one for decryption.
and the key. 2. The sender and receiver must each have one of
the matched pair of keys (not the same one).
Needed for Security: Needed for Security:
1. The key must be kept secret. 1. One of the two keys must be kept secret.
2. It must be impossible or at least impractical to 2. It must be impossible or at least impractical to
decipher a message if no other information is decipher a message if no other information is
available. available.
3. Knowledge of the algorithm plus samples of cipher 3. Knowledge of the algorithm plus one of the
text must be insufficient to determine the key. keys plus samples of cipher text
Table 2.4: Conventional and Public-Key Encryption

11
cryptography and ntk security 2 019/20

12