Sri Raghavendra Educational Institutions Society (R)

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

www.skit.org.in

Module-1: BASIC CONCEPTS OF CRYPTOGRAPHY AND SECURITY ASPECTS

Addressed: CO1

Course: Cryptography & Network Security

Presented by: SHWETA SINGH

Department: Computer Science & Engineering

CRYPTOGRAPHY

• Cryptography is a branch of mathematics that deals with the transformation of data.
• Cryptographic algorithms are used in many ways in information security and network security.
• Cryptography is an essential component in the secure storage and transmission of data, and in the secure interaction between parties.

2

NETWORK SECURITY

• To protect networks and their service from unauthorized modification, destruction, or disclosure, and assure that the network performs its critical functions correctly and there are no harmful side effects.

CYBERSECURITY

• Cybersecurity is all about protecting data and systems connected to the internet or any network from being stolen, changed, or damaged. It protects:

​

Stored Data – like your files, documents, passwords, etc.

Transmitted Data – like emails, messages, online banking info Processed Data – like when apps or websites handle your information

​

3

9/6/2024

Cryptography and Network Security Uses

For protecting Threats

• Eavesdropping (intercepting private messages)
• Masquerade (pretending to be someone else)
• Replay Attacks (re-sending valid data to trick the system)
• Message Modification

To provide Core Security Services

• Confidentiality: Prevent unauthorized disclosure of information
• Integrity: Ensure data is not altered without detection
• Authentication: Verify the identity of the user or system
• Access Control: Restrict access to authorized users only
• Availability: Ensure systems and data are usable when needed

To Enable Trusted Communication Over Insecure Networks

• Private messages to stay secret, no
• Data to travel safely through open channels
• Attackers to be blocked or detected

​

​

​

​

4

BASIC TERMS CRPTOGRAPHY

5

BASIC TERMS CRPTOGRAPHY

6

Block Cipher – Encrypts in fixed-size blocks.

​

Stream Cipher – Encrypts bit/byte by bit/byte.

​

Asymmetric Encryption – Public key encrypts, private key decrypts.

​

​

7

CLASSICAL ENCRYPTION TECHNIQUES

​

SYMMETRIC CIPHER MODEL

​

Symmetric encryption, also referred to as conventional encryption or single-key

encryption

8

​

A symmetric encryption scheme has five ingredients

​

■ Plaintext: This is the original intelligible message or data that is fed into the algorithm as input.

​

■Encryption algorithm: The encryption algorithm performs various substitutions and transformations on the plaintext.

​

■ Secret key: The secret key is also input to the encryption algorithm. The key is a value independent of the plaintext and of the algorithm. The algorithm will produce different output depending on the specific key being used at the time. The exact substitutions and transformations performed by the algorithm depend on the key.

​

■ Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the secret key. For a given message, two different keys will produce two different ciphertexts. The ciphertext is an apparently random stream of data and, as it stands, is unintelligible.

​

■ Decryption algorithm: This is essentially the encryption algorithm run in reverse.

It takes the ciphertext and the secret key and produces the original plaintext.

​

​

�

9

There are two requirements for secure use of conventional encryption:

​

• We need a strong encryption algorithm. At a minimum, we would like the algorithm to be such that an opponent who knows the algorithm and has access to one or more ciphertexts would be unable decipher the ciphertext or figure out the key.
• Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure. If someone can discover the key and knows the algorithm, all communication using this key is readable.

10

11

A source produces a message in plaintext, X = [X1, X2,….. XM]. The M elements of X are letters in some finite alphabet. Traditionally, the alphabet usually consisted of the 26 capital letters. Nowadays the binary alphabet {0, 1} is typically used. For encryption, a key of the form K = [K1, K2, ….., KJ] is generated. If the key is generated at the message source, then it must also be provided to the destination by means of some secure channel. Alternatively, a third party could generate the key and securely deliver it to both source and destination.With the message X and the encryption key K as input, the encryption algorithm forms the ciphertext Y = [Y1, Y2, ……, YN]. We can write this as

​

Y = E(K, X)

​

This notation indicates that Y is produced by using encryption algorithm E as a function of the plaintext X, with the specific function determined by the value of the key K.

​

The intended receiver, in possession of the key, is able to invert the transformation:

​

X = D(K, Y)

CRYPTOGPHY

12

Cryptographic systems are characterized along three independent dimensions:

​

1. The type of operations used for transforming plaintext to ciphertext.

​

All encryption algorithms are based on two general principles: substitution, in which each element in the plaintext (bit, letter, group of bits or letters) is mapped into another element, and transposition, in which elements in the plaintext are rearranged. The fundamental requirement is that no information be lost (i.e., that all operations are reversible). Most systems, referred to as product systems, involve multiple stages of substitutions and transpositions.

​

2. The number of keys used.

If both sender and receiver use the same key, the system is referred to as symmetric, single-key, secret-key, or conventional encryption. If the sender and receiver use different keys, the system is referred to as asymmetric, two-key, or public-key encryption.

​

3. The way in which the plaintext is processed.

A block cipher processes the input one block of elements at a time, producing an output block for each input block. A stream cipher processes the input elements continuously, producing output one element at a time as it goes along.

CAESAR CIPHER

13

The two basic building blocks of all encryption techniques are substitution and transposition.

​

Caesar cipher with a shift of 3, the alphabet is wrapped around, so that the letter following Z is A.

14

Three important characteristics of this problem enabled us to use a brute-force cryptanalysis:

​

1. The encryption and decryption algorithms are known.

2. There are only 25 keys to try.

3. The language of the plaintext is known and easily recognizable.

A brute-force cryptanalysis is easily performed: try all the 25 possible keys

​

Brute-force attack: The attacker tries every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained. On average, half

All possible keys must be tried to achieve success.

​

​

MONOALPHABETIC CIPHERS

15

If, instead, the “cipher” line can be any permutation of the 26 alphabetic characters, then there are 26! or greater than 4 * 1026 possible keys. This is 10 orders of magnitude greater than the key space for DES and would seem to eliminate brute-force techniques for cryptanalysis. Such an approach is referred to as a monoalphabetic substitution cipher, because a single cipher alphabet (mapping from plain alphabet to cipher alphabet) is used per message.

​

​

• Brute force seems impossible because 26! is enormous.
• But natural language (English) has patterns —
• single-letter frequencies (E, T, A, O, I, N…),
• common digrams (TH, IS, HE, IN, ON …), and
• common words (THE, SHE, AND etc.).
• Cryptanalysts exploit these regularities to break the cipher.
• They preserve frequency and pattern information: single-letter counts, digrams, repeated words, word lengths, grammar patterns

16

Encryption

• Write the plaintext message.
• For each letter, substitute it with its corresponding ciphertext letter using the key.
• The result is the ciphertext

Decryption

• Take the ciphertext.
• Replace each ciphertext letter with its plaintext equivalent.
• The result is the original plaintext.

​

​

​

​

General Monoalphabetic cipher = no formula.�Just a mapping table (substitution table) is created by hand or agreed as a key.

17

ONE TIME PAD

18

An Army Signal Corp officer, Joseph Mauborgne, suggested using a random key that is as long as the message, so that the key need not be repeated. In addition, the key is used to encrypt and decrypt a single message, and then is discarded. Each new message requires a new key of the same length as the new message. Such a scheme, known as a one-time pad, is unbreakable. It produces random output that bears no statistical relationship to the plaintext. Because the ciphertext contains no information whatsoever about the plaintext, there is simply no way to

break the code.

19

We need look no further for a cipher. The one-time pad offers complete Security but, in practice, has two fundamental difficulties:

​

• There is the practical problem of making large quantities of random keys. Any heavily used system might require millions of random characters regularly. Supplying truly random characters in this volume is a significant task.

​

• Even more daunting is the problem of key distribution and protection. For every message to be sent, a key of equal length is needed by both sender and receiver. Thus, a mammoth key distribution problem exists

​

​

.

Useful primarily for low-bandwidth channels requiring very high security.

20

h

STEGANOGRAPHY

21

A plaintext message may be hidden in one of two ways. The methods of steganography conceal the existence of the message, whereas the methods of cryptography render the message unintelligible to outsiders by various transformations of the text. It is not an encryption technique.

​

Various other techniques have been used historically; some examples are the following.

​

■ Character marking: Selected letters of printed or typewritten text are overwritten in pencil. The marks are ordinarily not visible unless the paper is held at an angle to bright light.

■ Invisible ink: A number of substances can be used for writing but leave no visible trace until heat or some chemical is applied to the paper.

■ Pin punctures: Small pin punctures on selected letters are ordinarily not visible unless the paper is held up in front of a light.

■ Typewriter correction ribbon: Used between lines typed with a black ribbon, the results of typing with the correction tape are visible only under a strong light.

22

The advantage of steganography is that it can be employed by parties who have something to lose should the fact of their secret communication (not necessarily the content) be discovered. Encryption flags traffic as important or secret or may identify the sender or receiver as someone with something to hide.

​

Steganography has a number of drawbacks when compared to encryption.

• It requires a lot of overhead to hide a relatively few bits of information, although using a scheme like that proposed in the preceding paragraph may make it more effective.
• once the system is discovered, it becomes virtually worthless.
• This problem, too, can be overcome if the insertion method depends on some sort of key

​

Alternatively, a message can be first encrypted and then hidden using steganography.

23

Stream Ciphers and Block Ciphers

A stream cipher encrypts a digital data stream one bit or one byte at a time.In which the keystream (ki) is as long as the plaintext bit stream (pi).

• If the cryptographic keystream is random, then this cipheris unbreakable by any means other than acquiring the keystream.
• However, the keystream must be provided to both users in advance via some independent and secure Channel.

​

This introduces insurmountable logistical problems if the intended data traffic is very large. for practical reasons, the bit-stream generator must be implemented as an algorithmic procedure, so that the cryptographic bit stream

can be produced by both users.

In this approach, the bit-stream generator is a key-controlled algorithm and must produce a bit stream that is cryptographically strong. That is, it must be computationally impractical to predict future portions of the bit stream based on previous portions of the bit stream. The two users need only share the generating key, and each can produce the keystream.one time pad is best example of stream cipher.

24

Block cipher

A block cipher is one in which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length.

A block size of 64 or 128 bits is used. As with a stream cipher, the two users share a symmetric encryption key. Using some of the modes of operation explained in a block cipher can be used to achieve the same effect as a stream cipher. they seem applicable to a broader range of applications than stream ciphers. The vast majority of network-based symmetric cryptographic applications make use of block ciphers.

DIFFERENCE BETWEEN BLOCK AND STREAM CIPHER

25

FEISTEL CIPHER

26

The left-hand side depicts the encryption structure proposed by Feistel.The inputs to the encryption algorithm are aplaintext block of length 2w bits and a key K.

• The plaintext block is divided into two halves,LE0 and RE0.
• The two halves of the data pass through n rounds of processing and then combine to produce the ciphertext block. Each round i has as inputs LEi-1 and REi-1 derived from the previous round, as well as a subkey Ki derived from the overall K.

In general, the subkeys Ki are different from K and from each other. In Figure 16 rounds are used, although any number of rounds could be implemented. A substitution is performed on the left half of the data. This is done by applying a round function F to the right half of the data and then taking the exclusive-OR of the output of that function and the left half of the data. The round function has the same general structure for each round but is parameterized by the round subkey Ki. Another way to express this is to say that F is a function of right-half block of w bits and a subkey of y bits, which produces an output value of length w bits: F(REi, Ki+1). Following this substitution, a

permutation is performed that consists of the interchange of the two halves of the data.

DATA ENCRYPTION STANDARD

27

DES, data are encrypted in 64-bit blocks using a 56-bit key. The algorithm transforms 64-bit input in a series of steps into a 64-bit output. The same steps, with the same key, are used to reverse the encryption.

• Encryption scheme, there are two inputs to the encryption function: the plaintext to be encrypted and the key.In this case, the plaintext must be 64 bits in length and the key is 56 bits in length.
• On the left-hand side of the figure, we can see that the processing of the plaintext proceeds in three phases. First, the 64-bit plaintext passes through an initial permutation (IP) that rearranges the bits to produce the permuted input.

This is followed by a phase consisting of sixteen rounds of the same function, which involves both permutation and substitution functions. The output of the last (sixteenth) round consists of 64 bits that are a function of the input plaintext and the key. The left and right halves of the output are swapped to produce the preoutput.

Finally, the preoutput is passed through a permutation [IP-1] that is the inverse of the initial permutation function, to produce the 64-bit ciphertext.

A DES EXAMPLE

28

A desirable property of any encryption algorithm is that a small change in either the plaintext or the key should produce a significant change in the ciphertext. In particular, a change in one bit of the plaintext or one bit of the key should produce a change in many bits of the ciphertext. This is referred to as the avalanche effect. If the change were small, this might provide a way to reduce the size of the plaintext or key space to be searched.

29

Using the example from Table 4.2, Table 4.3 shows the result when the fourth bit of the plaintext is changed, so that the plaintext is 12468aceeca86420. The second column of the table shows the intermediate 64-bit values at the end of each round for the two plaintexts. The third column shows the number of bits that differ between the two intermediate values. The table shows that, after just three rounds, 18 bits differ between the two blocks. On completion, the two ciphertexts differ in 32 bit positions.

​

Table 4.4 shows a similar test using the original plaintext of with two keys that differ in only the fourth bit position: the original key, 0f1571c947d9e859, and the altered key, 1f1571c947d9e859. Again, the results show that about half of the bits in the ciphertext differ and that the avalanche effect is pronounced after just a few rounds.

THE STRENGTH OF DES

30

Small Key Size (56-bit) – DES uses only 56 effective key bits. In the 1970s it seemed secure, but now with fast processors and supercomputers, brute-force attacks (trying all keys) can break DES within hours.

​

S-Box Design Doubts – DES relies heavily on substitution boxes (S-boxes). The rules for creating these were secret, so people feared that they might contain weaknesses known only to the designers. However, no serious flaws have ever been proven.

​

Timing Attacks – By carefully measuring the time taken for encryption/decryption, attackers may gain hints about the key (like number of 1s in it). DES resists this fairly well, but timing attacks are still a concern in cryptography

​

Better Alternatives – Because of these weaknesses, DES is no longer considered secure. It has been replaced by Triple DES (3DES) and later by AES (Advanced Encryption Standard), which use larger key sizes (128, 192, 256 bits) and are much stronger.

31

BLOCK CIPHER DESIGN PRINCIPLES

32

The cryptographic strength of a Feistel cipher derives from three aspects of the design:

​

• The number of rounds
• The function F
• The key schedule algorithm

​

The number of rounds

​

The criterion should be that the number of rounds is chosen so that known cryptanalytic efforts require greater effort than a simple brute-force key search attack. This criterion was certainly used in the design of DES. Schneier [SCHN96] observes that for 16-round DES, a differential cryptanalysis attack is slightly less efficient than brute force: The differential cryptanalysis attack requires 255.1 operations,9 whereas brute force requires 255. If DES had 15 or fewer rounds, differential cryptanalysis would require less effort than a brute-force key search. This criterion is attractive, because it makes it easy to judge the strength of an

algorithm and to compare different algorithms. In the absence of a cryptanalytic breakthrough, the strength of any algorithm that satisfies the criterion can be judged solely on key length.

Design of Function F

33

The heart of a Feistel block cipher is the function F, which provides the element of confusion in a Feistel cipher. Thus, it must be difficult to “unscramble” the substitution performed by F. One obvious criterion is that F be nonlinear, as we discussed previously. The more nonlinear F, the more difficult any type of cryptanalysis will be.

​

In general, this means that a change in one bit of the input should produce a change in many bits of the output. A more stringent version of this is the strict avalanche criterion (SAC) [WEBS86], which states that any output bit jof an S-box (see Appendix C for a discussion of S-boxes) should change with probability 1/2 when any single input bit i is inverted for all i, j. Although SAC is expressed in terms of S-boxes, a similar criterion could be applied to F as a whole. This is important when considering designs that do not include S-boxes. Another criterion proposed in [WEBS86] is the bit independence criterion (BIC), which states that output bits j and k should change independently when any single input bit i is inverted for all i, j, and k. The SAC and BIC criteria appear to strengthen the effectiveness of the confusion function.

Key Schedule Algorithm�

34

With any Feistel block cipher, the key is used to generate one subkey for each round.

​

In general, we would like to select subkeys to maximize the difficulty of deducing individual subkeys and the difficulty of working back to the main key. No general principles for this have yet been promulgated. Adams suggests [ADAM94] that, at minimum, the key schedule should guarantee key/ciphertext Strict Avalanche Criterion and Bit Independence Criterion.

35

Module-2

Addressed: CO2

Course: Cryptography & Network Security

Presented by: SHWETA SINGH

Department: Computer Science & Engineering

SECOND UNIT

36

USE OF RANDOM NUMBERS

​

RANDOMNESS

Traditionally, the concern in the generation of a sequence of allegedly random numbers has been that the sequence of numbers be random in some well-defined statistical sense. The following two criteria are used to validate that a

sequence of numbers is random:

■ Uniform distribution: The distribution of bits in the sequence should be uniform; that is, the frequency of occurrence of ones and zeros should be approximately equal.

■ Independence: No one subsequence in the sequence can be inferred from the others.

​

UNPREDICTABILITY In applications such as reciprocal authentication, session key generation, and stream ciphers, the requirement is not just that the sequence of numbers be statistically random but that the successive members of the sequence are unpredictable. With “true” random sequences, each number is statistically independent of other numbers in the sequence and therefore unpredictable.

​

TRNGs, PRNGs, and PRFs

37

• A true random number generator (TRNG) with two forms of pseudorandom number generators.
• A TRNG takes as input a source that is effectively random; the source is often referred to as an entropy source. In essence, the entropy source is drawn from the physical environment of the computer and could include things such as keystroke timing patterns, disk electrical activity, mouse movements, and instantaneous values of the system clock. The source, or combination of sources, serve as input to a algorithm that produces random binary output. The TRNG may simply involve conversion of an analog source to a binary output. The TRNG may involve additional processing to overcome any bias in the source.
• A PRNG takes as input a fixed value, called the seed, and produces a sequence of output bits using a deterministic algorithm. Quite often, the seed is generated by a TRNG. there is some feedback path by which some of the results of the algorithm are fed back as input as additional output bits are produced. The important thing to note is that the output bit stream is determined solely by the input value or values, so that an adversary who knows the algorithm and the seed can reproduce the entire bit stream.

38

Pseudorandom function (PRF): A PRF is used to produce a pseudorandom string of bits of some fixed length. Examples are symmetric encryption keys and nonces. Typically, the PRF takes as input a seed plus some context specific values, such as a user ID or an application ID.

​

LINEAR CONGRUENTIAL GENERATORS

A widely used technique for pseudorandom number generation is an algorithm first proposed by Lehmer, which is known as the linear congruential method.

The algorithm is parameterized with four numbers, as follows:

​

​

​

​

​

​

The selection of values for a, c, and m is critical in developing a good random number generator. For example, consider a = c = 1. The sequence produced is obviously not satisfactory. Now consider the values a = 7, c = 0, m = 32, and X0 = 1. This generates the sequence {7, 17, 23, 1, 7, etc.}, which is also clearly unsatisfactory. Of the 32 possible values, only four are used; thus, the sequence is said to have a period of 4. If, instead, we change the value of a to 5, then the sequence is {5, 25, 29, 17, 21, 9, 13, 1, 5, etc. }, which increases the period to 8. We would like m to be very large, so that there is the potential for producing a long series of distinct random numbers. A common criterion is that m be nearly

39

BLUM BLUM SHUB GENERATOR

A popular approach to generating secure pseudorandom numbers is known as

the Blum Blum Shub (BBS) generator named for its developers . It has perhaps the strongest public proof of its cryptographic strength of any purpose-built algorithm. The procedure is as follows.

• First, choose two large prime numbers, p and q, that both have a remainder of 3 when divided by 4. That is, simply means that (p mod 4) = (q mod 4) = 3.

​

​

​

Thus, the least significant bit is taken at each iteration. Table 8.1 shows an example of BBS operation. Here, n = 192649 = 383 * 503, and the seed s = 101355.

40

The BBS is referred to as a cryptographically secure pseudorandom bit generator (CSPRBG). A CSPRBG is defined as one that passes the next-bit test, which, in turn, is defined as follows. A pseudorandom bit generator is said to pass the next-bit test if there is not a polynomial-time algorithm1 that, on input of the first k bits of an output sequence, can predict the (k + 1)st bit with probability significantly greater than 1/2. In other words, given the first k bits of the sequence, there is not a practical algorithm that can even allow you to state that the next bit will be 1 (or 0) with probability greater than 1/2. For all practical purposes,

the sequence is unpredictable. The security of BBS is based on the difficulty of factoring n. That is, given n, we need to determine its two prime factors p and q.

Terminology Related to Asymmetric Encryption

41

Asymmetric Keys

Two related keys, a public key and a private key, that are used to perform complementary operations, such as encryption and decryption or signature generation and signature verification.

​

Public Key Certificate

A digital document issued and digitally signed by the private key of a Certification Authority that binds the name of a subscriber to a public key. The certificate indicates that the subscriber identified in the certificate has sole control and access to the corresponding private key.

​

Public Key (Asymmetric) Cryptographic Algorithm

A cryptographic algorithm that uses two related keys, a public key and a private key. The two keys have the property that deriving the private key from the public key is computationally infeasible.

​

Public Key Infrastructure (PKI)

A set of policies, processes, server platforms, software and workstations used for the purpose of administering certificates and public-private key pairs, including the ability to issue, maintain, and revoke public key certificates.

PUBLIC-KEY CRYPTOSYSTEMS�

42

Asymmetric algorithms rely on one key for encryption and a different but related key for decryption. 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.

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

​

■ 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 encrypted message produced as output. It depends on the plaintext and the key. For a given message, two different keys will produce two different ciphertexts

​

PUBLIC KEY CRYPTOGRAPHY

43

44

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. 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.

45

46

Let us take a closer look at the essential elements of a public-key encryption scheme. There is some source A that produces a message in plaintext

X = [X1, X2,….., XM]

The M elements of X are letters in some finite alphabet. The message is intended for destination B

B generates a related pair of keys:

• Public key PUb
• Private key PRb

PRb is known only to B, whereas PUb is publicly available and therefore accessible by A. With the message X and the encryption key PUb as input, A forms the ciphertext

Y = [Y1, Y2, ….. YN]:

Y = E(PUb, X)

The intended receiver, in possession of the matching private key, is able to invert the transformation:

X = D(PRb,Y)

47

An adversary,

observing Y and having access to PUb, but not having access to PRb or X, must attempt to recover X and/or PRb.

It is assumed that the adversary does have knowledge of the encryption (E) and decryption (D) algorithms.

If the adversary is interested only in this particular message, then the focus of effort is to recover X by generating a plaintext estimate Xn .

Often, however, the adversary is interested in being able to read future messages as well, in which case an attempt is made to recover PRb by generating an estimate PRnb.b.

48

We mentioned earlier that either of the two related keys can be used for encryption, with the other being used for decryption. This enables a rather different cryptographic scheme to be implemented. the use of public-key encryption to provide authentication:

Y = E(PRa,X)

X = D(PUa,Y)

49

A prepares a message to B and encrypts it using A’s private key before transmitting it. B can decrypt the message using A’s public key. Because the message was encrypted using A’s private key, only A could have prepared the message.

Therefore, the entire encrypted message serves as a digital signature.

In addition, it is impossible to alter the message without access to A’s private key, so the message is authenticated both in terms of source and in terms of data integrity.

​

In the preceding scheme, the entire message is encrypted, which, although validating both author and contents, requires a great deal of storage. Each document must be kept in plaintext to be used for practical purposes.

A copy also must be stored in ciphertext so that the origin and contents can be verified in case of a dispute.

A more efficient way of achieving the same results is to encrypt a small block of bits that is a function of the document. Such a block, called an authenticator, must have the property that it is infeasible to change the document without changing the authenticator.

If the authenticator is encrypted with the sender’s private key, it serves as a signature that verifies origin, content, and sequencing

50

It is important to emphasize that the encryption process depicted in Figures 9.1b and 9.3 does not provide confidentiality. That is, the message being sent is safe from alteration but not from eavesdropping. This is obvious in the case of a signature based on a portion of the message, because the rest of the message is transmitted in

the clear. Even in the case of complete encryption, as shown in Figure 9.3, there is no protection of confidentiality because any observer can decrypt the message by using the sender’s public key.

It is, however, possible to provide both the authentication function and confidentiality by a double use of the public-key scheme (Figure 9.4)

Z = E(PUb, E(PRa,X))

X = D(PUa, D(PRb,Z))

In this case, we begin as before by encrypting a message, using the sender’s private key. This provides the digital signature. Next, we encrypt again, using the receiver’s public key. The final ciphertext can be decrypted only by the intended receiver, who alone has the matching private key. Thus, confidentiality is provided

.

The disadvantage of this approach is that the public-key algorithm, which is complex, must be exercised four times rather than two in each communication.

51

52

Applications for Public-Key Cryptosystems

53

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 function.

■ Encryption/decryption: The sender encrypts a message with the recipient’s public key, and the recipient decrypts the message with the recipient’s private 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, which is a secret

key for symmetric encryption generated for use for a particular transaction (or session) and valid for a short period of time. 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

54

Requirements for Public-Key Cryptography

The cryptosystem depends on a cryptographic algorithm based on two related keys without demonstrating that such algorithms exist. However, they did lay out the conditions that such algorithms must fulfill

1. It is computationally easy for a party B to generate a key pair (public key PUb, 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, PUb, to determine the private key, PRb.

5. It is computationally infeasible for an adversary, knowing the public key, PUb, 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. Before elaborating