MODULE2

CHAPTER1 PUBLIC-KEY CRYPTOGRAPHY AND RSA

 The development of public-key cryptography is the greatest and perhaps the only truer evolution
in the entire history of cryptography.
 Earlier all cryptographic systems have been based on the elementary tools of substitution and
permutation.
 Public key algorithms are based on mathematical functions rather than on substitution and
permutation.
 More important, public-key cryptography is asymmetric, involving the use of two separate
keys, in contrast to symmetric encryption, which uses only one key.
 The use of two keys has profound consequences in the area so confidentiality , key distribution
,and authentication, as we shall see.

Common misconceptions concerning public-key encryption:

1. Public-key encryption is more secure from cryptanalysis than is symmetric encryption .In fact

,the security of any encryption scheme depends on the length of the key and the computational
work involved in breaking a cipher.
2. A second misconception is that public-key encryption is a general-purpose technique that has

made symmetric encryption obsolete.

3. Finally, there is a feeling that key distribution is important when using public-key encryption,

compared to the rather handshaking involved with key distribution centers for symmetric
encryption.

Terminology Related to Asymmetric Encryption

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.

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

Principles of Public-Key Cryptosystems

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.

As we have seen, key distribution under symmetric encryption requires either

1. Two communicants already share a key ,which some how has been distributed
2. The use of a key distribution center.

Whitfield Diffie, one of the discoverers of public-key encryption reasoned that this second
requirement negated the very essence of cryptography : the ability to maintain to secrecy over your
own communication.
The second problem is digital signatures. The electronic messages and documents would
need the equivalent of signatures used in paper documents. That is digital message had been sent by
a particular person? This is a somewhat broader requirement than that of authentication,
Diffie and Hellman achieved breakthrough by coming up with a method that addressed both
problems and was radically different from all previous approaches to cryptography.

Pag
Public-Key Cryptosystems

Pag
 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 in feasible to determine the decryption key given only

knowledge of the cryptographic algorithm and the encryption key.

 Either of the two related key scan be used for encryption ,with the other used for
decryption.

Any one knowing the public key can encrypt messages or verify signatures ,but cannot
decrypt messages or create signatures, thanks to some clever use of number theory.

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

Pag
The essential steps are the following:

1. Each user generates a pair of keys to be used for the encryption and decryption of messages.

Pag
 CNS
2. Each user places one of the two keys in a public register or other accessible file. This is the
public key.Thecompanionkeyiskeptprivate.Eachusermaintainsacollectionofpublickeysobtained
from others.

3. If Bob wishes to send a confidential message to Alice, Bob encrypts the messageusing Alice's
public key.

4. When Alice receives the message, she decrypts it using her private key. No otherrecipient can
decrypt the message because only Alice knows Alice's private key.

To discriminate between symmetric and public-key encryption, were to the key used in
symmetric encryption as a secret key. The two keys used for asymmetric encryption are referred
to as the public key and the private key .In variably, the private key is kept secret , but it is
referred to as a private key rather than a secret key to avoid confusion with symmetric
encryption.

ConventionalEncryption Public-Key Encryption

Neededto Work: Neededto Work:
1. The same algorithm with the same key 1. One algorithm is used for encryption
is used for encryption and decryption. and decryption with a pair of keys, one
2. The sender and receiver must share the for encryption and one for decryption.
algorithm 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 2. It must be impossible or atleast impractical to
impractical to decipher a message if decipher a message if no other information is
no other information is available. available.
3. Knowledge of the algorithm plus 3. Knowledge of the algorithm plus one of the
samples of cipher text must be keys plus samples of cipher text must be
insufficient to determine the insufficient to determine the other key.
key.

Page
 CNS

Public-Key Crypto systems : Secrecy and Authentication

 Public-key schemes can be used for either secrecy or authentication, or both (as shown here).
There is some source A that produces a message in plaintext X .The message is intended for
destination B.

 B generates a related pair of keys: a public key, PUb, and a private key, PRb. PRbis known
only to B, whereas PUb is publicly available and therefore accessible byA.

 With the message X and the encryption key Pub as input,A forms the ciphertext

Y = E(PUb, X)

 The intended receiver, in possession of the matching private key, is able to invert the
transformation: X = D(PRb, Y).

 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. This provides confidentiality.

 Public-key encryption can also provide authentication:

Y=E(PRa, X);X=D(PUa, Y)

 To provide both the authentication function and confidentiality have a double use of the
public- key scheme (as shown here):

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

X=D(PUa,D(PRb,Z))
Page
 CNS
Applications for Public-Key Cryptosystems

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

Requirements for Public-Key Cryptography

1. It is computationally easy for a party B to generate a 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)]

Page
 CNS

A one-way function is one that maps a domain into arrange such that every function value has a
unique inverse, with the condition that the calculation of the function is easy whereas the calculation of
the inverse is infeasible:

Y=f(X) easy

X=f–1(Y)infeasible

Trap-door one-way function

It is easy to calculate in one direction and infeasible to calculate in the other direction unless certain
additional information is known.

Y = fk(X) easy, if k and X are known

X=f–1(Y)easy ,if k and Y are known

X=f–1(Y)infeasible , if Y known but k not known

Public-Key Cryptanalysis
 As with symmetric encryption, a public-key encryption scheme is vulnerable to a brute-force
attack. The countermeasure is the same: Use large keys.
 The key size must be large enough to make brute-force attack impractical but result in
encryption/decryption speeds that are too slow for general-purpose use.
 Another form of attack is to find someway to compute the private key given the public key
.To date, it has not been mathematically proven that this form of attack is infeasible for a
particular public-key algorithm.
 Finally, there is a form of attack that is peculiar to public-key systems. This is, in essence ,a
probable-message attack.
 Suppose, for example, that a message were to be sent that consisted solely of a 56-bitDES key.
An adversary could encrypt all possible 56-bit DES keys using the public key and could
discover the encrypted key by matching the transmitted ciphertext.
 Thus, no matter how large the key size of the public-key scheme, the attack is reduced to a
brute-force attack on a 56-bit key. This attack can be thwarted by appending some randombits
to such simple messages.

Page
 CNS
The RSA Algorithm

RSA Algorithm was developed in1977byRon Rivest ,Adi Shamir ,and Len Adlemanat MIT.

The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supreme as the
most widely accepted and implemented general-purpose approach to public-key encryption.

The RSA scheme is a block cipher in which the plaintext and ciphertext 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 21024 .

Description of the Algorithm:

RSA makes use of an expression with exponentials. 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 2(n) + 1. Encryption and decryption are of the following form, for some
plaintext block M and ciphertext block C.

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

Forth is 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 modn =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 determined 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

Page
 CNS
The preceding relationship holds if e and d are multiplicative in verse s modulo
φ(n),where φ(n) is the Euler totient function. The relationship between e and d can be expressed
as e d mod ɸ(𝑛) = 1 e-1
This is equivalent to saying

That is, e and 𝑑are multiplicative inverses mo𝑑 (ɸ𝑛 ) . Note that, according to the rules of modular
arithmetic, this is true only if 𝑑(and therefore e)is relatively prime to ɸ(𝑛).Equivalently ,gcd (ɸ(𝑛),
𝑑)=1.

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

𝑝,𝑞 two prime numbers (private, chosen)

n=pq (public,calculated)

e, with gcd (ɸ(𝑛),e) =1; 1<e<(n) (public,chosen)

𝑑 ≡e−1𝑚o𝑑 (ɸ𝑛 ) (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 𝐶
=𝑀e 𝑚o𝑑 𝑛 and transmits C.On receipt of this cipher text ,user A decrypts by calculating 𝑀 =𝐶𝑑
𝑚o𝑑 𝑛.

Example:

Alice generates a public/private key pair; Bob encryptsusing Alice’s public key; andAlice
decrypts using her private key. For this example, the keys were generated as follows.
1. Select two prime numbers ,p =17andq=11.
2. Calculate n =pq =17* 11 =187.
3. Calculate f (n) =(p-1)(q-1) =16 * 10=160.
4. Selecte such that e is relatively prime to f(n)=160 and less than f(n);we choose e=7.
5. Determined such that de K 1(mod160) and d 6160.The correct value is d=23,because 23
Page
 CNS
*7=161=(1*160)+1; d can be calculated using the extended Euclid’s 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 plaintext input of M= 88. For encryption, we need to
calculate C = 887mod 187. Exploiting the properties of modular arithmetic, we can do this as follows.

887mod 187 = [(884mod187) ×(882mod 187) ×(881mod 187)]mod 187

881mod 187 =88

882mod 187 =7744 mod187 =77

884mod 187 = 59,969,536 mod 187 =132

887mod 187 = (88×77 ×132) mod 187 =894,432 mod 187 =11

For decryption, we calculate M =1123mod 187:

Page
 CNS
1123mod187 =[(111mod187)×(112mod187)×(114mod 187)×(118mod187) ×(118mod187)]
mod187
111mod187= 11

112mod187=121

114mod187=14,641mod187=55

118mod187=214,358,881 mod187=33

1123mod187=(11×121×55×33×33)mod187=79,720,245mod187=88

Computational Aspects

We now turn to the issue of the complexity of the computation required to use RSA.Thereare
actually two issues to consider: encryption/decryption and key generation.

To perform the modular exponentiations, you can use the “Square and Multiply
Algorithm”, a fast, efficient algorithm for doing exponentiation.

The idea is to repeatedly square the base, and multiply in the ones that are needed to compute
the result, as found by examining the binary representation of the exponent.

 Eg.7=7.7=3.7=10mod11

 eg.3129=3128.31=5.3 =4 mod 11

The RSA algorithm requires that during key generation, the user selects a value of e that is
relatively prime to ø (n).Thus, if a value if e is selected first, and the primes p and q are generated ,it
may turn out that gcd (ø(n),e) ≠ 1.In that case, the user must reject the p,q values and generate an e
w p, q pair.

RSA Key Generation

 Before the application of the public-key cryptosystem, each participant must generate a pair of
keys, which requires finding primes and computing inverses.
 Both the prime generation and the derivation of a suitable pair of inverse exponents may
involve trying a number of alternatives.

Page
 CNS

 Typically make random guesses for a possible p or q, and check using a probabilistic
primality test whether the guessed number is indeed prime. If not, try again.
 Note that the prime number theorem shows that the average number of guesses needed is not
too large.
 Then computed ecryption exponent d using Euclid’s Inverse Algorithm ,which is quite
efficient.

The Security of RSA

Four possible approaches to attacking the RSA algorithm areas 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.

Brute force:

The defense against the brute-force approach is the same for RSA as for other
cryptosystems, namely, use a large key space. Thus, the larger the number of bits in d, the better.
However ,because the calculations involved, both in key generation and in encryption/decryption,
are complex, the larger the size of the key, the slower the system will run.

The Factoring Problem:

We can identify three approaches to attacking RSA mathematically:

 Factor n into its two prime factors. This enables calculation of ɸ(𝑛)=(p -1)*( q-1),which,
in turn ,enables determination o f𝑑=e−1𝑚o𝑑(ɸ𝑛 ) .
 Determine ɸ(𝑛) directly, with out first determining p and q .Again ,this enables
determination of 𝑑=e−1𝑚o𝑑 (ɸ𝑛 ) .
 Determined directly, with out first determining ɸ(𝑛).

Determining ɸ(𝑛) given n is equivalent to factoring n.With presently known

Page
 CNS
algorithms,determiningdgiveneandnappearstobeatleastastime-consumingasthe

Page
 CNS

Factoring problem. Hence, we can use factoring performance as a benchmark against which
to evaluate the security of RSA.

To avoid values of n that may be factored more easily ,the algorithm's inventors
suggest the following constraints on p and q:

1. p and q should differ in length by only a few digits. Thus, for a 1024-bit key (309decimal
digits), both p and q should be on order of 1075 to 10100.
2. Both(p– 1)and(q –1)should contain a large prime factor
3. gcd(p–1,q–1)should be small.

Timing Attacks:

 Timing Attacks demonstrated that can determine a private key by keeping track of how
long a computer takes to decipher messages.
 Timing Attacks are based on observing how long it takes to compute the cryptographic
operations. Timing attacks are applicable not just to RSA, but to other public-key
cryptography systems.
 This attack is alarming for two reasons: It comes from a completely unexpected direction
and it is a cipher text-only attack.

The timing attack is a serious threat; there are simple countermeasures that can be used,
including using constant exponentiation time algorithms, adding random delays, or using blind
values in calculations.

 Constant exponentiation time: Ensure that all exponentiations take the same amount of time
before returning a result. This is a simple fix but does degrade performance.
 Random delay: Better performance could be achieved by adding a random delay to the
exponentiation algorithm to confuse the timing attack. Kocher points out that if defenders
don't add enough noise, attackers could still succeed by collecting additional measurements to
compensate for the random delays.
 Blinding: Multiply the ciphertext by a random number before performing exponentiation.
This process prevents the attacker from knowing what ciphertext bits are being processed
inside the computer and therefore prevents the bit-by-bit analysis essential to the timing
attack.

Page
 CNS
Chosen Ciphertext Attacks:

Page
 CNS

 The RSA algorithm is vulnerable to a chosen ciphertext attack (CCA).

 CCA is defined as an attack in which adversary chooses a number of ciphertexts and is then
given the corresponding plaintexts, decrypted with the target’s private key.
 The adversary exploits properties of RSA and selects blocks of data that, when processed
using the target’s private key, yield information needed for cryptanalysis.
 More sophisticated variants need to modify the plaintext using a procedure known as optimal
asymmetric encryption padding (OAEP).

To counter such attacks RSA Security, a leading RSA vendor and former holder of the
RSA patent, recommends modifying the plaintext using a procedure known as optimal
asymmetric encryption padding (OAEP).

 As a first step the message M to be encrypted is padded. A set of optional parameters P is

passed through a hash function H.

Page
 CNS

 The output is then padded with zeros to get the desired length in the overall data block(DB).
Next, a random seed is generated and passed through another hash function, called the mask
generating function (MGF).
 The resulting hash value is bit-by-bit XORed with DB to produce a masked DB.
 The masked DB is in turn passed through the MGF to form a hash that is XORed with the
seed to produce the masked seed.
 The concatenation of the masked seed and the masked DB forms the encoded message EM.
 Note that the EM includes the padded message, masked by the seed, and the seed, masked by
the masked DB. The EM is then encrypted using RSA.

Page
 CNS

CHAPTER2.OTHERPUBLICKEYCRYPTOSYSTEMS

Diffie-Hellman Key Exchange

The purpose of the algorithm is to enable two users to securely exchange a key that can then
be used for subsequent encryption of messages.

If a is “a” primitive root of the prime number p, then the numbers

amodp, a2mod p,...,ap1mod p

are distinct and consist of the integers from1through p-1in some permutation.

Example:

3 is primitive root of 7.

The number 3 is a primitive root modulo7, because

31=3=30×3≡3≡3(𝑚o𝑑)7

32=9=32×3≡9≡2(𝑚o𝑑7)

33=27=33×3≡6≡6 (𝑚o𝑑7)

34=81=34×3≡18≡4 (𝑚od7)

35=243=35×3≡12≡5 (𝑚o𝑑7)

36=729=36×3≡15≡1 (𝑚od7)

Here we see that the period of 3k modulo7 is 6.The remainders in the period, which are 3,2,
6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a
primitive root modulo 7.
The Algorithm:
There are two publicly known numbers: a prime number q and an integer that is aprimitive
root of q.
Suppose the users A and B wish to exchange a key. User A selects a random integer XA<q
and computes YA= XA mod q. Similarly, user B independently selects a random integer XA<q and
computes YB= XB mod q.

Page
 CNS

Each side keeps the X value private and makes the Y value available publicly to the other side.

User A computes the key as K=(YB)XA mod q and user B computes the key as K =(YA)XB mod q.
These two calculations produce identical results:

K=(YB)XAmodq
=(XBmodq)XAmodq
=(XB)XAmodq by the rules of modular arithmetic
=(XBXAmodq
=(XA)XBmodq
=(XAmod q)
=(XAmodq)XBmodq
=(YA)XBmodq

Example:

Prime number q=353and a primitive root of 353,in this case α=3.

A and B select secret keys XA=97 and XB=233, respectively. Each computes its public key:

A computes YA=397 mod353=40.

B computes YB=3233 mod353= 248.

After they exchange public keys ,each can compute the common secret key:

A computes K XA =24897mod 353 =160.

= (YB)
B computes K=(YA)XBmod 353 =40233mod 353.

Key Exchange Protocols:

Page
 CNS
Suppose that user A wishes to set up a connection with user B and use a secret key to encrypt
messages on that connection. User A can generate a one-time private key XA,calculate YA, and send
that to user B.
UserB responds by generating aprivate value XBcalculatingYB, and sending YB touserA.Both
users can now calculate the key.
The necessary public values q and  would need to be known ahead of time.
Alternatively ,userA could pick values for q and and include those in the first message.

Man-in-the-MiddleAttack:

Suppose Alice and Bob wish to exchange keys ,and Darth is the adversary .The attack
proceeds as follows.

At this point, Bob and Alice think that they share a secret key ,but instead Bob and Darth share
secret key K1 and Alice and Darth share secret key K2 .All future communication between Bob and
Alice is compromised in the following way.

Page
 CNS

The key exchange protocol is vulnerable to such an attack because it does not authenticate
the participants. This vulnerability can be overcome with the use of digital signatures and public-
key certificates;

ELGAMAL CRYPTOGRAPHIC SYSTEM

As with Diffie-Hellman, the global elements of ElGamal are a prime number and, which is a
primitive root of .User A generates a private/public key pair as follows:
1. Generate a random integer XA,such that1<XA<Q-1

2. Compute𝑌A=𝛼𝑋𝐴𝑚o𝑑𝑞
3. A’s private key isXA; A’s pubic key is{𝑞,𝛼,𝑌A}
Any user B that has access toA’s public key can encrypt a message as follows:

Page
 CNS

User A recovers the plaintext as follows:

User A generates a public/private key pair;user Bencrypts using A’s public key;and user
A decrypts using her private key.

First, how 𝐾 is recovered by the decryption process:

Next, using 𝐾,we recover the plaintext as

Page
 CNS

Example:
Thus, 𝐾 functions as a one-time key, used to encrypt and decrypt the message. For example, let us
start with the prime field GF (19); that is, q 19. It has primitive roots {2, 3, 10, 13, 14, and 15}, as
shown in Table 8.3.We choose 𝛼= 10.

Vidya H A Assistant Professor Dept of ISE SVIT Page

 CNS
Encryption:
Alice generates a key pair as follows:

Suppose Bob wants to send the message with the value M=17.Then,

Decryption:

If a message must be broken up into blocks and sent as a sequence of encrypted blocks, a
unique value of “k” should be used for each block .If is used for more than one block ,knowledge of
one block m1of the message enables the user to compute other blocks as follows. Let

The security of Elgamal is based on the difficulty of computing discrete logarithms. To recover
A’sprivate key, an adversary would have to compute XA= dlog α,q(YA).

Page23