KEY ENCRYPTION

Introduction

The incredible growth of the Internet has excited businesses and consumers alike with its promise of changing the way we live and work. But a major concern has been just how secure the Internet is, especially when you're sending sensitive information through it.

There's a whole lot of information that we don't want other people to see, such as:

• Credit-card information
• Social Security numbers
• Private correspondence
• Personal details
• Sensitive company information
• Bank-account information

Information security is provided on computers and over the Internet by a variety of methods. A simple but straightforward security method is to only keep sensitive information on removable storage media like floppy disks. But the most popular forms of security all rely on encryption, the

process of encoding information in such a way that only the person (or computer) with the key can decode it.

Computer encryption is based on the science of cryptography, which has been used throughout history. Before the digital age, the biggest users of cryptography were governments, particularly for military purposes. The existence of coded messages has been verified as far back as the Roman Empire. But most forms of cryptography in use these days rely on computers, simply because a human-based code is too easy for a computer to crack.

Most computer encryption systems belong in one of two categories:

• Symmetric-key encryption
• Public-key encryption

Cryptographic techniques are typically divided into two generic types: symmetric-key and public-key . The encryption scheme is said to be symmetric-key if for each associated encryption/decryption key pair (e; d), it is computationally “easy” to determine d knowing only e, and to determine e from d.

The most striking development in the history of cryptography came in 1976, when Diffie and Hellman published New Directions in Cryptography. This paper introduced the revolutionary concept of public-key cryptography and also provided a new and ingenious method for key exchange, the security of which is based on the intractability of the discrete logarithm problem. Although the authors had no practical realization of a public-key encryption scheme at the time, the idea was clear and it generated extensive interest and activity in the cryptographic community. In 1978 Rivest, Shamir, and Adleman discovered the first practical public-key encryption and signature scheme, now referred to as RSA. The RSA scheme is based on another hard mathematical problem, the intractability of factoring large integers. This application of a hard mathematical problem to cryptography revitalized efforts to find more efficient methods to factor. The 1980s saw major advances in this area but none which rendered the RSA system insecure. In 1991 the first international standard for digital signatures was adopted. It is based on the RSA public-key scheme.

Symmetric key Encryption:

The encryption scheme is said to be symmetric-key if for each associated encryption/decryption key pair (e; d), it is computationally “easy” to determine d knowing only e, and to determine e from d. Generally e = d ; hence the name symmetric-key. Other terms used in the literature are single-key, one-key, privatekey,

and conventional encryption.

One of the major issues with symmetric-key systems is to find an efficient method to agree upon and exchange keys securely. This problem is referred to as the key distribution problem. It is assumed that all parties know the set of encryption/decryption transformations (i.e.,they all know the encryption scheme). The only information which should be required to be kept secret is the key d. However, in symmetric-key encryption, this means that the key e must also be kept secret, as d can be deduced from e.

Public-Key Encryption:

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

à Either of the two related keys can be used for encryption, with the other used for decription.

· Here each system has two keys, one is placed in the public register and is known as Public key whereas the other key is the Private key.

· When A wishes to send a message to B, it encrypts the message using B’s public key.

· When B receives the message, B decrypts it using B’s private key. No other recipient can decrypt the message because only B knows B’s private key.

This method covers the confidentiality aspect, but authentication is absent. ie. Anyone could have sent this message to B.

Another approach can be:

· A encrypts the message using A’s private key.

· B decrypts the message using A’s public key.

This method has the authentication aspect covered in it, but lacks confidentiality .ie. Anyone other than B can also receive the message and decrypt it using A’s public key.

To cover both confidentiality and authentication the scheme can be arranged like this:

· A encrypts the message using A’s private key. (authentication)

· The message is again encrypted using B’s public key.

· B decrypts the message first using B’s private key. (confidentiality)

· The message is again decrypted using A’s public key.

Disadvantages of symmetric-key cryptography

1. In a two-party communication, the key must remain secret at both ends.

2. In a large network, there are many key pairs to be managed. Consequently, effective key management requires the use of an unconditionally trusted third party.

3. In a two-party communication between entities A and B, sound cryptographic practice dictates that the key be changed frequently, and perhaps for each communication session.

4. Digital signature mechanisms arising from symmetric-key encryption typically require either large keys for the public verification function or the use of a trusted third party.

Advantages of public-key cryptography

1. Only the private key must be kept secret (authenticity of public keys must, however,

be guaranteed).

2. The administration of keys on a network requires the presence of only a functionally trusted third party (TTP) as opposed to an unconditionally TTP. Depending on the mode of usage, the TTP might only be required in an “off-line” manner, as opposed to in real time.

3. Depending on the mode of usage, a private key/public key pair may remain unchanged for considerable periods of time, e.g., many sessions (even several years).

4. Many public-key schemes yield relatively efficient digital signature mechanisms.

The key used to describe the public verification function is typically much smaller

than for the symmetric-key counterpart.

5. In a large network, the number of keys necessary may be considerably smaller than

in the symmetric-key scenario.

The RSA Public key Encryption Algorithm:

In this scheme plaintext 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 log₂(n); in practice, the block size is 2^k bits, where 2^k <>k+1. Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C:

C=M^e mod n

M = C^d mod n = (M^e)^d mod n = M^ed mod n

Both sender and receiver must know he 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 KU = {e,n} and a private key of KR = {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 M^ed = M mod n for all M

2. It is relatively easy to calculate M^e and C^d for all values of M

3. It is infeasible to determine d given e and n.

In order to satisfy the first condition, we use the Euler’s theorem which states that given two prime numbers, p and q, and two integers, n and m, such that n = pq and 0

M^kf(n)+1 = m^{K(p-1)(q-1)+1} º m mod n

Where f(n) is the Euler totient function, which is the number of positive integer less than n and relatively prime to n.

It can be shown using Euler’s theorem that

f(pq) = (p-1)(q-1).

Thus we can achieve the desired relationship if

ed = kf(n) + 1

This is equivalent to saying:

ed º 1 mod f(n)

d º e^-1 mod f(n)

That is, e and d are multiplicative inverses mod f(n). According to the rules of modular arithmetic, this is true only if d (and therefore e) is relatively prime to f(n). Equivalently, gcd(f(n),d) = 1. [gcd º greatest common divisor].

Α

The ingredients of RSA scheme are the following:

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

n = pq (public, calculated)

e, with gcd(f(n),e) =1; 1<>f(n) (public, chosen)

d º e^-1 mod f(n) (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 = M^e (mod n) and transmits C. On receipt of this ciphertext, user A decrypts by calculating M = C^d(mod n).

We have chosen e and d such that

d º e^-1 mod f(n)

Therefore,

ed º 1 mod f(n)

Therefore, ed is of the form of kf(n) + 1. But by the corollary to Euler’s theorem, given two prime numbers, p and q, and integers n = pq and M, with 0

M^kf(n)+1 = M^{k(p-1)(q-1)+1} º M mod n

So, M^ed º M mod n. Now,

C = M^e mod n

M = C^d mod n º (M^e)^d mod n º M^ed mod n º M mod n

Fig (ii) summarizes the RSA algorithm.

Key Generation

Select p,q p and q both prime

Calculate n = p x q

Calculate f(n) = (p-1)(q-1)

Select integer e gcd( f(n), e ) = 1 ; 1 <>f(n)

Calculate d d = e^-1 mod f(n)

Public key KU = {e,n}

Private key KR = {d,n}

Encryption

Plaintext: M <>

Ciphertext: C = M^e (mod n)

Decryption

Plaintext: C

Ciphertext: M = C^d (mod n)

Fig(ii)

An example is shown in fig(iii). For this example, the keys were generated as follows:

1) Select two prime numbers, p = 7 and q = 17.

2) Calculate n = pq = 7 x 17 = 119.

3) Calculate f(n) = (p-1)(q-1) = 96.

4) Select e such that e is relatively prime to f(n) = 96 and less than f(n); in this case, e = 5.

5) Determine d such that de = 1 mod 96 and d < style=""> The correct value is d = 77, because 77 x 5 = 385 = 4 x 96 + 1.

The resulting keys are public key KU = {5,119} and private key KR = {77,119}. The example shows the use of these keys for a plaintext input of M = 19. For encryption, 19 is raised to the fifth power, yielding 2476099. Upon division by 119, the remainder is determined to be 66. Hence 19⁵ º 66 mod 119, and the ciphertext is 66. For decryption, it is determined that 66⁷⁷ º 19 mod 119.

Encryption Decryption

Ciphertext

Plaintext 19⁵ = 2476099 = 20807 with a 66 66⁷⁷ = 1.27…x10¹⁴⁰ = 1.06…x10¹³⁸ with

19 119 remainder of 119 a remainder of

66 19

KU = 5, 119 KR = 77, 119 Plaintext

19

Security of RSA

This subsection discusses various security issues related to RSA encryption. Various attacks are presented, as well as appropriate measures to counteract these threats.

(i) Relation to factoring

The task faced by a passive adversary is that of recovering plaintext from the corresponding ciphertext c, given the public information (n; e) of the intended receiver A. This is called the RSA problem (RSAP). There is no efficient algorithm known for this problem.

One possible approach which an adversary could employ to solving the RSA problem is to first factor n, and then compute f and d. Once d is obtained, the adversary can decrypt any ciphertext intended for A. On the other hand, if an adversary could somehow compute d, then it could subsequently factor n efficiently as follows. First note that since ed º 1 (mod f), there is an

integer k such that ed - 1 = kf. Hence, a^ed-1 º 1 (mod n) for all a Î Z_n. Let ed - 1 = 2^st, where t is an odd integer. Then it can be shown that there exists an i Î [1, s] such that a^{2^(i-1)t} ≠±1 (mod n) and a^{2^(i)t} º 1(mod n) for at least half of all a Î Z_n; if a and i are such integers then gcd(a^{2^(i-1)t} – 1, n) is a non-trivial factor of n. Thus the adversary simply needs to repeatedly select random a Î Z_n and check if an i Î [1, s] satisfying the above property exists; the expected number of trials before a non-trivial factor of n is obtained is 2. This discussion establishes the following.

(ii) Small encryption exponent e

In order to improve the efficiency of encryption, it is desirable to select a small encryption exponent e such as e = 3. A group of entities may all have the same encryption exponent e, however, each entity in the group must have its own distinct modulus. If an entity A wishes to send the same message m to three entities whose public moduli are n1, n2, n3, and whose encryption exponents are e = 3, then A would send ci = m3 mod ni, for i = 1; 2; 3. Since these moduli are most likely pairwise relatively prime, an eavesdropper observing c1, c2, c3 can use Gauss’s algorithm to find a solution x, 0 ≤ x <>1n₂n₃, to the three congruences :

x º c1 (mod n₁)

x º c2 (mod n₂)

x º c3 (mod n₃).

Since m³ <>1n₂n₃, by the Chinese remainder theorem it must be the case that x = m3. Hence, by computing the integer cube root of x, the eavesdropper can recover the plaintext m. Thus a small encryption exponent such as e = 3 should not be used if the same message, or even the same message with known variations, is sent to many entities. Alternatively, to prevent against such an attack, a pseudo-randomly generated bitstring of appropriate length should be appended to the plaintext message prior to encryption; the pseudorandom bit string should be independently generated for each encryption. This process is sometimes referred to as salting the message.

Small encryption exponents are also a problem for small messages m, because if m<>1/e, then m can be recovered from the ciphertext c = m^e mod n simply by computing the integer eth root of c; salting plaintext messages also circumvents this problem.

(iii) Forward search attack

If the message space is small or predictable, an adversary can decrypt a ciphertext c by simply encrypting all possible plaintext messages until c is obtained. Salting the message as described above is one simple method of preventing such an attack.

(iv) Small decryption exponent d

As was the case with the encryption exponent e, it may seem desirable to select a small decryption exponent d in order to improve the efficiency of decryption. However, if gcd(p-1; q - 1) is small, as is typically the case, and if d has up to approximately one-quarter as many bits as the modulus n, then there is an efficient algorithm for computing d from the public information (n, e). This algorithm cannot be extended to the case where d is approximately the same size as n. Hence, to avoid this attack, the decryption exponent d should be roughly the same size as n.

(v) Multiplicative properties

Let m1 and m2 be two plaintext messages, and let c1 and c2 be their respective RSA encryptions. Observe that

(m1m2)^e º m1^em2^e º c1c2 (mod n)

In other words, the ciphertext corresponding to the plaintext m = m1m2 mod n is c = c1c2 mod n; this is sometimes referred to as the homomorphic property of RSA. This observation leads to the following adaptive chosen-ciphertext attack on RSA encryption.

Suppose that an active adversary wishes to decrypt a particular ciphertext c = m^e mod n intended for A. Suppose also that A will decrypt arbitrary ciphertext for the adversary, other than c itself. The adversary can conceal c by selecting a random integer x ÎZ_n and computing c’ = cx^e mod n. Upon presentation of c’, A will compute for the adversary m’ = (c’)^d mod n. Since

m’ º (c)^d º c^d(x^e)^d º mx (mod n),

the adversary can then compute m = m’x^-1 mod n. This adaptive chosen-ciphertext attack should be circumvented in practice by imposing some structural constraints on plaintext messages. If a ciphertext c is decrypted to a message not possessing this structure, then c is rejected by the decryptor as being fraudulent. Now, if a plaintext message m has this (carefully chosen) structure, then with high probability mx mod n will not for x Î Z_n. Thus the adaptive chosen-ciphertext attack described in the previous paragraph will fail because A will not decrypt c for the adversary.

(vi) Common modulus attack

The following discussion demonstrates why it is imperative for each entity to choose its own RSA modulus n.

It is sometimes suggested that a central trusted authority should select a single RSA modulus n, and then distribute a distinct encryption/decryption exponent pair (ei, di) to each entity in a network. However, as shown in (i) above, knowledge of any (ei, di) pair allows for the factorization of the modulus n, and hence any entity could subsequently determine the decryption exponents of all other entities in the network. Also, if a single message were encrypted and sent to two or more entities in the network, then there is a technique by which an eavesdropper (any entity not in the network) could recover the message with high probability using only publicly available information.

(vii) Cycling attacks

Let c = m^e mod n be a ciphertext. Let k be a positive integer such that c^{e^k} º c (mod n); since encryption is a permutation on the message space {0, 1, …… ,n – 1} such an integer k must exist. For the same reason it must be the case that c^{e^(k-1)} º m (mod n). This observation leads to the following cycling attack on RSA encryption. An adversary computes c^e mod n, c^{e^2} mod n, c^{e^3} mod n,….. until c is obtained for the first time. If c^{e^k} mod n = c, then the previous number in the cycle, namely c^{e^(k-1)} mod n, is equal to the plaintext m.

A generalized cycling attack is to find the smallest positive integer u such that f = gcd(c^{e^u}- c, n) > 1. If

c^{e^u} º c (mod p) and c^{e^u} ≠ c (mod q) …..(1)

then f = p. Similarly, if

c^{e^u} ≠c (mod p) and c^{e^u} º c (mod q) .….(2)

then f = q. In either case, n has been factored, and the adversary can recover d and then m. On the other hand, if both

c^{e^u} º c (mod p) and c^{e^u} º c (mod q) …..(3)

then f = n and c^{e^u}_º c (mod n). In fact, u must be the smallest positive integer k for which c^{e^k} º c (mod n). In this case, the basic cycling attack has succeeded and so m = c^{e^(u-1)} mod n can be computed efficiently. Since (3) is expected to occur much less frequently than (1) or (2), the generalized cycling attack usually terminates before the cycling attack does. For this reason, the generalized cycling attack can be viewed as being essentially an algorithm for factoring n.

Since factoring n is assumed to be intractable, these cycling attacks do not pose a threat to the security of RSA encryption.

(viii) Message concealing

A plaintext message m, 0 ≤ m ≤ n-1, in the RSA public-key encryption scheme is said to be unconcealed if it encrypts to itself; that is,m^e º m (mod n). There are always some messages which are unconcealed (for example m = 0, m = 1, and m = n - 1). In fact, the number of unconcealed messages is exactly

[1 + gcd(e – 1, p - 1)] * [1 + gcd(e – 1, q - 1)]:

Since e-1, p-1 and q -1 are all even, the number of unconcealed messages is always at

least 9. If p and q are random primes, and if e is chosen at random (or if e is chosen to be a small number such as e = 3 or e = 2¹⁶ + 1 = 65537), then the proportion of messages which are unconcealed by RSA encryption will, in general, be negligibly small, and hence unconcealed messages do not pose a threat to the security of RSA encryption in practice.

Conclusion:

So with the above descriptions of the strengths and weaknesses of RSA, we are able to conclude a number of things.

First of all – cryptography never finishes. Some breakthroughs are always made, either in encryption or in cryptanalysis. There is no such thing as a secure encryption method – and RSA algorithm might turn out to be a close-but-no-cigar solution… But conventional mathematics bound cryptography is always breakable. It is hard to create truly one-way functions, and if that succeeds, brute forcing is a definite option, as Moors law cashes out to those who wait.

Management Of Public key

Public key cryptograohy makes it possible for people who do not share a common key to communicate securely. It also makes signing message possible without the presence of trusted third party.

DATA ENRYPTON SYSTEM

Security is a prevalent concern in information and data systems of all types. Historically, military and national security issues drove the need for secure communications. Recently, security issues have pervaded the business and private sectors. E-commerce has driven the need for secure internet communications. Many businesses have firewalls to protect internal corporate information from competitors. In the private sector, personal privacy is a growing concern.

Products are available to scramble both e-mail and telephone communications.

One means of providing security in communications is through encryption. By encryption, data is transformed in a way that it is rendered unrecognizable. Only by decryption can this data be recovered. Ostensibly, the process of decryption can only be performed correctly by the intended recipient(s). The validity of this assertion determines the “strength” or “security” of the encryption scheme.

Many communications products incorporate encryption as a feature to provide security. This application report studies the implementation of one of the most historically famous and widely implemented encryption algorithms, the Data Encryption Standard (DES).

Implementation of DES is studied on the Texas Instruments TMS320C6000 family of processors.

Since the C6000 family is the DSP industry’s performance leader, it efficiently implements not only DES, but the mathematically intensive communications algorithms for which DES is often a complement. Many communications solutions are able to upgrade their products to incorporate an encryption feature while maintaining the same channel density of the original solution.

In some cases it is necessary to upgrade to one of the higher performing devices in the constantly growing C6000 family, but in lower data rate applications, it is possible to add encryption on the same processor which is already used. This allows the addition of encryption functionality with no extra manufacturing cost, and no increase in the board space required.

The Data Encryption Standard (DES)

Developed in 1974 by IBM in cooperation with the National Securities Agency (NSA), DES has

been the worldwide encryption standard for more than 20 years. For these 20 years it has held

up against cryptanalysis remarkably well and is still secure against all but possibly the most

powerful of adversaries [4]. Because of its prevalence throughout the encryption market, DES is

an excellent interoperability standard between different encryption equipment.

The predominant weakness of DES is its 56-bit key which, more than sufficient for the time

period in which it was developed, has become insufficient to protect against brute-force attack

by modern computers [5] (see table 1). As a result of the need for a greater encryption strength,

DES evolved into triple-DES. Triple-DES encrypts using three 56-bit keys, for an encryption

strength equivalent to a 168-bit key. This implementation, however, requires three times as

many rounds for encryption and decryption and highlights a second weakness of DES – speed.

DES was developed for implementation on hardware, and DES implementations in software are

often less efficient than other standards which have been developed with software performance

in mind.

Data Encryption Standard (DES) Implementation on the TMS320C6000

As is highlighted in the Results section of this application report, however, the C6000 core is

able to achieve very impressive data rates for DES and triple-DES in software. Data rates on the

C6201 (200 MHz) are measured as high as 53 Mbits per second for DES and 22 Mbits per

second for triple-DES. Data rates on the C6211 (150 MHz) device are measured as high as 39

Mbits per second for DES and 18 Mbits per second for triple-DES. On a 300 MHz device such

as the C6203, we can extrapolate data rates of 80 Mbits per second for DES and 33 Mbits per

second for triple-DES.

This performance is typically more than sufficient for multichannel applications involving 8 Kbit

per second vocoders and/or 56 Kbytes per second modems. Even DES encryption at the full

G.lite ADSL rate of 1.5 Mbytes per second requires less than 50 MHz performance on the

C6000 core and could be added to an application with a simple upgrade from C6201 to the

C6202 or from the C6202 to the C6203. Due to the C6000 platform’s strong performance in

multi-channel communications applications, DES may be implemented as part of a one-chip

re-programmable multi-channel solution. This provides great savings in board space, cost,

power consumption and design time. Furthermore, because the solution is re-programmable, it

may be easily evolved to match the rapidly changing encryption market.

Modes of Operation for Encryption Algorithms

DES belongs to a category of ciphers called block ciphers. Block ciphers, as opposed to stream

ciphers, encrypt messages by separating them into blocks and encrypting each block separately.

Stream ciphers, on the other hand, operate on streams of data one bit at a time as a continuous

stream.

DES encrypts 64-bit blocks of plaintext into 64-bit blocks of ciphertext. Plaintext, used in the

context of cryptography, is the name commonly given to the body of a message before it is

encrypted, i.e. the unaltered text of the message which is to be sent. Likewise, ciphertext is the

name commonly given to the encrypted version of the message body which is meant to be

indecipherable to any person who does not have the decryption key.

The simplest implementation of a block cipher is to separate the plaintext into contiguous blocks,

encrypt each block into ciphertext blocks, and group these ciphertext blocks together as the

ciphertext output. This mode of operation is referred to as Electronic Code Book (ECB) mode

(see Figure 2A). The distinguishing property of this mode is that identical blocks of plaintext

always encrypt to the same ciphertext. This is undesirable in some applications.

It is possible to introduce feedback between blocks by feeding the results of the previous

encryption block into the input of the current block. The first block of feedback is a randomly

generated block called the initialization vector. When this is done, each ciphertext block is not

only dependent on the plaintext block that generated it but on each of the preceeding blocks as

well, including the initialization vector. Identical plaintext blocks will now only encrypt to the same

ciphertext block if each of the proceeding blocks are identical and the initialization vectors are

identical. This mode of operation is referred to as Cipher Block Chaining (CBC) mode (See

Figure 2B).

Implementation of DES

DES relies upon the encryption techniques of confusion and diffusion. Confusion is

accomplished through substitution. Specially chosen sections of data are substituted for

corresponding sections from the original data. The choice of the substituted data is based upon

the key and the original plaintext. Diffusion is accomplished through permutation. The data is

permuted by rearranging the order of the various sections. These permutations, like the

substitutions, are based upon the key and the original plaintext.

The substitutions and permutations are specified by the DES algorithm. Chosen sections of the

key and the data are manipulated mathematically and then used as the input to a look-up table.

In DES these tables are called the S-boxes and the P-boxes, for the substitution tables and the

permutation tables, respectively. In software these look-up tables are realized as arrays and

key/data input is used as the index to the array. Usually the S- and P-boxes are combined so

that the substitution and following permutation for each round can be done with a single look-up.

In order to calculate the inputs to the S- and P-box arrays, portions of the data are XORed with

portions of the key. One of the 32-bit halves of the 64-bit data and the 56-bit key are used.

Because the key is longer than the data half, the 32-bit data half is sent through an expansion

permutation which rearranges its bits, repeating certain bits, to form a 48-bit product. Similarly

the 56-bit key undergoes a compression permutation which rearranges its bits, discarding

certain bits, to form a 48-bit product. The S- and P-box look-ups and the calculations upon the

key and data which generate the inputs to these table look-ups constitute a single round of DES

(see Figure 3B).

This same process of S- and P-box substitution and permutation is repeated sixteen times,

forming the sixteen rounds of the DES algorithm (see Figure 3A). There are also initial and final

permutations which occur before and after the sixteen rounds. These initial and final

permutations exist for historical reasons dealing with implementation on hardware and do not

improve the security of the algorithm. For this reason they are sometimes left out of

implementations of DES. They are, however, included in this analysis as they are part of the

technical definition of DES.

As is evident from the description above, DES is not a typical digital signal processing (DSP)

application. DSP applications tend to rely upon the sum of products as their core operation. DES

relies primarily on bit manipulation operations and actually uses no multiplication operations.

None the less, as will be evinced later in this application report, the C6000 platform is able to

perform the DES algorithm with high efficiency.

It is possible to go into much greater detail on the inner workings of the DES algorithm, as is

done in the following references: [1],[2],[3],[4]. The purpose of this application report is to

investigate the performance of DES on the C6000 platform using C code which is compiled by

Texas Instruments’ Optimizing C Compiler. Thus, we only go into the level of detail that is need

as background to the investigations presented later in this application report.

Information security and cryptography

The concept of information will be taken to be an understood quantity. To introduce cryptography,

an understanding of issues related to information security in general is necessary.

Information security manifests itself in many ways according to the situation and requirement.

Regardless of who is involved, to one degree or another, all parties to a transaction

must have confidence that certain objectives associated with information security have been

met. Some of these objectives are listed in Table 1.1.

Over the centuries, an elaborate set of protocols and mechanisms has been created to

deal with information security issues when the information is conveyed by physical documents.

Often the objectives of information security cannot solely be achieved through

mathematical algorithms and protocols alone, but require procedural techniques and abidance

of laws to achieve the desired result. For example, privacy of letters is provided by

sealed envelopes delivered by an accepted mail service. The physical security of the envelope

is, for practical necessity, limited and so laws are enacted which make it a criminal

offense to open mail for which one is not authorized. It is sometimes the case that security

is achieved not through the information itself but through the physical document recording

it. For example, paper currency requires special inks andmaterial to prevent counterfeiting.

Conceptually, the way information is recorded has not changed dramatically over time.

Whereas information was typically stored and transmitted on paper, much of it now resides

on magnetic media and is transmitted via telecommunications systems, some wireless.

What has changed dramatically is the ability to copy and alter information. One can

make thousands of identical copies of a piece of information stored electronically and each

is indistinguishable from the original. With information on paper, this is much more diffi-

cult. What is needed then for a society where information is mostly stored and transmitted

in electronic form is a means to ensure information security which is independent of the

physical medium recording or conveying it and such that the objectives of information security

rely solely on digital information itself.

One of the fundamental tools used in information security is the signature. It is a building

block formany other services such as non-repudiation, data origin authentication, identification,

and witnessing, to mention a few. Having learned the basics in writing, an individual

is taught how to produce a handwritten signature for the purpose of identification.

At contract age the signature evolves to take on a very integral part of the person’s identity.

This signature is intended to be unique to the individual and serve as a means to identify,

authorize, and validate. With electronic information the concept of a signature needs to be

redressed; it cannot simply be something unique to the signer and independent of the information

signed. Electronic replication of it is so simple that appending a signature to a

document not signed by the originator of the signature is almost a triviality.

Analogues of the “paper protocols” currently in use are required. Hopefully these new

electronic based protocols are at least as good as those they replace. There is a unique opportunity

for society to introduce new and more efficient ways of ensuring information security.

Much can be learned from the evolution of the paper based system, mimicking those

aspects which have served us well and removing the inefficiencies.

Achieving information security in an electronic society requires a vast array of technical

and legal skills. There is, however, no guarantee that all of the information security objectives

deemed necessary can be adequately met. The technical means is provided through

cryptography.

1.1 Definition Cryptography is the study of mathematical techniques related to aspects of information

security such as confidentiality, data integrity, entity authentication, and data origin

authentication.

Cryptography is not the only means of providing information security, but rather one set of

techniques.

Cryptographic goals

Of all the information security objectives listed in Table 1.1, the following four form a

framework upon which the others will be derived: (1) privacy or confidentiality (x1.5, x1.8);

(2) data integrity (x1.9); (3) authentication (x1.7); and (4) non-repudiation (x1.6).

1. Confidentiality is a service used to keep the content of information from all but those

authorized to have it. Secrecy is a term synonymous with confidentiality and privacy.

There are numerous approaches to providing confidentiality, ranging from physical

protection to mathematical algorithms which render data unintelligible.

2. Data integrity is a service which addresses the unauthorized alteration of data. To

assure data integrity, one must have the ability to detect data manipulation by unauthorized

parties. Data manipulation includes such things as insertion, deletion, and

substitution.

3. Authentication is a service related to identification. This function applies to both entities

and information itself. Two parties entering into a communication should identify

each other. Information delivered over a channel should be authenticated as to origin,

date of origin, data content, time sent, etc. For these reasons this aspect of cryptography

is usually subdivided into two major classes: entity authentication and data

origin authentication. Data origin authentication implicitly provides data integrity

(for if a message is modified, the source has changed).

4. Non-repudiation is a service which prevents an entity fromdenying previous commitments

or actions. When disputes arise due to an entity denying that certain actions

were taken, a means to resolve the situation is necessary. For example, one entity

may authorize the purchase of property by another entity and later deny such authorization

was granted. A procedure involving a trusted third party is needed to resolve

the dispute.

A fundamental goal of cryptography is to adequately address these four areas in both

theory and practice. Cryptography is about the prevention and detection of cheating and

other malicious activities.

This book describes a number of basic cryptographic tools (primitives) used to provide

information security. Examples of primitives include encryption schemes (x1.5 and x1.8),

be evaluated with respect to various criteria such as:

1. level of security. This is usually difficult to quantify. Often it is given in terms of the

number of operations required (using the best methods currently known) to defeat the

intended objective. Typically the level of security is defined by an upper bound on

the amount of work necessary to defeat the objective. This is sometimes called the

work factor (see x1.13.4).

2. functionality. Primitives will need to be combined to meet various information security

objectives. Which primitives are most effective for a given objective will be

determined by the basic properties of the primitives.

3. methods of operation. Primitives, when applied in various ways and with various inputs,

will typically exhibit different characteristics; thus, one primitive could provide

very different functionality depending on its mode of operation or usage.

4. performance. This refers to the efficiency of a primitive in a particular mode of operation.

(For example, an encryption algorithm may be rated by the number of bits

per second which it can encrypt.)

5. ease of implementation. This refers to the difficulty of realizing the primitive in a

practical instantiation. This might include the complexity of implementing the primitive

in either a software or hardware environment.

The relative importance of various criteria is very much dependent on the application

and resources available. For example, in an environmentwhere computing power is limited

one may have to trade off a very high level of security for better performance of the system

as a whole.

Cryptography, over the ages, has been an art practised by many who have devised ad

hoc techniques to meet some of the information security requirements. The last twenty

years have been a period of transition as the disciplinemoved froman art to a science. There

are now several international scientific conferences devoted exclusively to cryptography

and also an international scientific organization, the International Association for Cryptologic

Research (IACR), aimed at fostering research in the area.

This book is about cryptography: the theory, the practice, and the standards.

Digital signatures

A cryptographic primitive which is fundamental in authentication, authorization, and nonrepudiation

is the digital signature. The purpose of a digital signature is to provide a means

for an entity to bind its identity to a piece of information. The process of signing entails

transforming the message and some secret information held by the entity into a tag called

a signature. A generic description follows.

Nomenclature and set-up

_ Mis the set of messages which can be signed.

_ S is a set of elements called signatures, possibly binary strings of a fixed length.

_ SA is a transformation from the message setMto the signature set S, and is called

a signing transformation for entity A.3 The transformation SA is kept secret by A,

and will be used to create signatures for messages fromM.

_ VA is a transformation from the set M _ S to the set ftrue; falseg.4 VA is called

a verification transformation for A’s signatures, is publicly known, and is used by

other entities to verify signatures created by A.

Definition The transformations SA and VA provide a digital signature scheme for A. Occasionally

the term digital signature mechanism is used.

Example (digital signature scheme)M= fm1;m2;m3g and S = fs1; s2; s3g. The left

side of Figure 1.10 displays a signing function SA from the setMand, the right side, the

corresponding verification function VA.

Signing procedure

Entity A (the signer) creates a signature for a message m2Mby doing the following:

1. Compute s = SA(m).

2. Transmit the pair (m; s). s is called the signature for message m.

Verification procedure

To verify that a signature s on a message m was created by A, an entity B (the verifier)

performs the following steps:

1. Obtain the verification function VA of A.

2. Compute u = VA(m; s).

3. Accept the signature as having been created byAif u = true, and reject the signature

if u = false.

1.43 Remark (concise representation) The transformations SA and VA are typically characterized

more compactly by a key; that is, there is a class of signing and verification algorithms

publicly known, and each algorithm is identified by a key. Thus the signing algorithm SA

of A is determined by a key kA and A is only required to keep kA secret. Similarly, the

verification algorithm VA of A is determined by a key lA which is made public.

1.44 Remark (handwritten signatures) Handwritten signatures could be interpreted as a special

class of digital signatures. To see this, take the set of signatures S to contain only one

element which is the handwritten signature of A, denoted by sA. The verification function

simply checks if the signature on a message purportedly signed by A is sA.

An undesirable feature in Remark 1.44 is that the signature is not message-dependent.

Hence, further constraints are imposed on digital signature mechanisms as next discussed.

Properties required for signing and verification functions

There are several propertieswhich the signing and verification transformationsmust satisfy.

(a) s is a valid signature of A on message m if and only if VA(m; s) = true.

(b) It is computationally infeasible for any entity other than A to find, for any m2M,

an s 2 S such that VA(m; s) = true.

Figure 1.10 graphically displays property (a). There is an arrowed line in the diagram

for VA from (mi; sj) to true provided there is an arrowed line frommi to sj in the diagram

for SA. Property (b) provides the security for the method – the signature uniquely binds A

to the message which is signed.

No one has yet formally proved that digital signature schemes satisfying (b) exist (although

existence is widely believed to be true); however, there are some very good candidates.

x1.8.3 introduces a particular class of digital signatures which arise from publickey

encryption techniques. Chapter 11 describes a number of digital signature mechanisms

which are believed to satisfy the two properties cited above. Although the description of a

digital signature given in this section is quite general, it can be broadened further, as presented

in x11.2.

Authentication and identification

Authentication is a term which is used (and often abused) in a very broad sense. By itself

it has little meaning other than to convey the idea that some means has been provided to

guarantee that entities are who they claim to be, or that information has not been manipulated

by unauthorized parties. Authentication is specific to the security objective which

one is trying to achieve. Examples of specific objectives include access control, entity authentication,

message authentication, data integrity, non-repudiation, and key authentication.

These instances of authentication are dealt with at length in Chapters 9 through 13.

For the purposes of this chapter, it suffices to give a brief introduction to authentication by

describing several of the most obvious applications.

Authentication is one of the most important of all information security objectives. Until

themid 1970s itwas generally believed that secrecy and authenticationwere intrinsically

connected. With the discovery of hash functions (x1.9) and digital signatures (x1.6), it was

realized that secrecy and authentication were truly separate and independent information

security objectives. It may at first not seem important to separate the two but there are situations

where it is not only useful but essential. For example, if a two-party communication

between Alice and Bob is to take place where Alice is in one country and Bob in another,

the host countries might not permit secrecy on the channel; one or both countries might

want the ability to monitor all communications. Alice and Bob, however, would like to be

assured of the identity of each other, and of the integrity and origin of the information they

send and receive.

The preceding scenario illustrates several independent aspects of authentication. If Alice

and Bob desire assurance of each other’s identity, there are two possibilities to consider.

1. Alice and Bob could be communicating with no appreciable time delay. That is, they

are both active in the communication in “real time”.

2. Alice or Bob could be exchanging messages with some delay. That is, messages

might be routed through various networks, stored, and forwarded at some later time.

In the first instance Alice and Bob would want to verify identities in real time. This

might be accomplished by Alice sending Bob some challenge, to which Bob is the only

entity which can respond correctly. Bob could perform a similar action to identify Alice.

This type of authentication is commonly referred to as entity authentication or more simply

identification.

For the second possibility, it is not convenient to challenge and await response, and

moreover the communication path may be only in one direction. Different techniques are

now required to authenticate the originator of the message. This form of authentication is

called data origin authentication.

1.7.1 Identification

1.45 Definition An identification or entity authentication technique assures one party (through

acquisition of corroborative evidence) of both the identity of a second party involved, and

that the second was active at the time the evidence was created or acquired.

Typically the only data transmitted is that necessary to identify the communicating parties.

The entities are both active in the communication, giving a timeliness guarantee.

c

1997 by CRC Press, Inc.—See accompanying notice at front of chapter.

x 1.8 Public-key cryptography 25

1.46 Example (identification) A calls B on the telephone. If A and B know each other then

entity authentication is provided through voice recognition. Although not foolproof, this

works effectively in practice. _

1.47 Example (identification) Person A provides to a banking machine a personal identification

number (PIN) along with a magnetic stripe card containing information about A. The

banking machine uses the information on the card and the PIN to verify the identity of the

card holder. If verification succeeds, A is given access to various services offered by the

machine. _

Example 1.46 is an instance of mutual authentication whereas Example 1.47 only provides

unilateral authentication. Numerous mechanisms and protocols devised to provide

mutual or unilateral authentication are discussed in Chapter 10.

1.7.2 Data origin authentication

1.48 Definition Data origin authentication or message authentication techniques provide to

one partywhich receives a message assurance (through corroborative evidence) of the identity

of the party which originated the message.

Often a message is provided to B along with additional information so that B can determine

the identity of the entity who originated the message. This form of authentication

typically provides no guarantee of timeliness, but is useful in situations where one of the

parties is not active in the communication.

1.49 Example (need for data origin authentication) A sends to B an electronic mail message

(e-mail). The message may travel through various network communications systems and be

stored forB to retrieve at some later time. AandB are usually not in direct communication.

B would like some means to verify that the message received and purportedly created by

A did indeed originate from A. _

Data origin authentication implicitly provides data integrity since, if the message was

modified during transmission, A would no longer be the originator.

TO DOWN LOAD REPORT AND PPT

DOWNLOAD