CRYPTOGRAPHY

A technique of securing information and communications

through use of codes so that only those persons for whom
the information is intended can understand it and process it.
Prevents unauthorized access to information.
Ensures confidentiality by encrypting sent messages using
an algorithm with a key only known to the sender and
recipient.
A common example is WhatsApp, which encrypts
conversations between people to ensure they cannot be
hacked or intercepted.
Used for authentication in many different situations, such
as when accessing a bank account, logging into a
computer, or using a secure network.
 CRYPTOGRAPHY
The prefix “crypt” means “hidden” and suffix “graphy” means
“writing”.
The techniques of securing information are obtained from
mathematical concepts and a set of rule based calculations
known as algorithms to convert messages in ways that make it
hard to decode it.
These algorithms are used for cryptographic key
generation, digital signing, verification to protect data
privacy, web browsing on internet and to protect
confidential transactions such as credit card and debit card
transactions.
 HISTORY OF
CRYPTOGRAPHY
The word ‘cryptography’ originated from two greek words
‘Krypto’ means hidden and ‘graphene’ means writing.

Classical Cryptography
• The roots are cryptography are found in Roman and Egyptian
civilizations.
• Some of the ancient types of cryptography are:
1. HIEROGLYPHS CRYPTOGRAPHY
The earliest known use of Cryptography can be dated back to
1900 BC during the time of the Old Kingdom of Egypt in form of
non-standard hieroglyphs.
Hieroglyphs were a secret form of communication that the
Egyptians used to communicate with one another.
This secret text was known only to the scribes of the kings who
used to transmit messages on their behalf.
2. CAESAR CIPHER
The ancient Greeks were well known for the use of Ciphers.
The Caesar Cipher or Shift Cipher is one of the earliest and
simplest well-known cryptographic techniques.
It is a form of Substitution Cipher where each character in a
word is replaced by a fixed number of positions.
For example with a shift of 3, A is replaced by D, B by E, and so
on.
3. VIGENERE CIPHER
During the 16th century, Vigenere designed a cipher in which
the encryption key is repeated multiple times spanning the
entire message, and then the cipher text is generated by
adding the message character with key character modulo 26.
This approach is also vulnerable to attacks, where the secrecy
of the message depends on the secrecy of the encryption key.
4. HEBERN ROTATING MACHINE
At the start of the 19th century, Hebern designed a Hebern
rotating machine.
In this machine, a single rotor is used where the secret key is
embedded in the rotating disc and the key has an embedded
substitution table.
Each key press from the keyboard resulted in the output of
cipher text.
This code is broken by using the letter frequencies.
5. ENIGMA MACHINE
Cryptography played a vital in the victory of Allied forces during
World War I and World War II.
World War II prominently saw the use of electromechanical
cipher machines.
The story of the Allied victory over the Germans by cracking
the world-famous Enigma machine is well known.
Enigma is a combination of electro-mechanical subsystems.
It consisted of three to five rotors.
Whenever a key was pressed, one or more rotors rotated on
the spindle, and accordingly, the key was scrambled to
something else.
The Enigma cipher was broken by Poland.
DATA ENCRYPTION STANDARD
(DES)
In the early 1970s, IBM realized that its customer base is requesting
some type of encryption method to protect the data.
They formed a crypto group headed by Horst-Feistel.
This group designed a cipher called Lucifer. In 1973, the Nation
Bureau of Standards (NBS) which is now known as the National
Institute of Standards and Technology (NIST) put out a proposal for
the block cipher.
Lucifer was eventually accepted and called Data Encryption
Standard (DES).
It is a symmetric-key algorithm based on the Feistel cipher and is used
for the encryption of electronic data.
It has a relatively small key size of 56-bits and is encrypted 64 bits or
8 characters at a time.
In 1997, DES was broken by an exhaustive search attack.
But, it was later discontinued as it was found to be insecure, especially
against brute force attacks cause of its relatively small key size.
ADVANCE ENCRYPTION
STANDARD
In 1997, NIST again put out a proposal for a new block cipher.
The Rijndael cipher is eventually accepted and renamed
as Advanced Encryption Standard (AES).
DES was replaced by Advance Encryption Standard or AES in
2001.
Unlike DES, AES is based on a substitution-permutation
network.
AES is a sub-set of Rijndael.
It is a family of ciphers with different key and block sizes.
In the case of AES, the block size is 128 bits or 16 characters
which means 16 characters can be encrypted at a time.
It comes with three different key size variants: 128 bits, 192
bits, and 256 bits.
TECHNIQUES USED FOR CRYPTOGRAPHY
In today’s age of computers cryptography is often associated
with the process where
An ordinary plain text is converted to cipher text which is the
text made such that intended receiver of the text can only
decode it. This process is known as encryption.
The process of conversion of cipher text to plain text this is
known as decryption.
TECHNIQUES USED FOR CRYPTOGRAPHY
• Consider two parties A and B. Now, A wants to send a message m to
B over a secure channel. The sender’s message or sometimes
called the Plaintext, is converted into an unreadable form using a
Key k.
• The resultant text obtained is called the Ciphertext. This process is
known as Encryption.
• At the time of received, the Ciphertext is converted back into the
plaintext using the same Key k, so that it can be read by the receiver.
This process is known as Decryption.
A (Sender) B (Receiver)
C = E (m, k) ----> m = D (C, k)
• Here, C refers to the Ciphertext while E and D are the Encryption
and Decryption algorithms respectively.
• Let’s consider the case of Caesar Cipher or Shift Cipher as an
example. As the name suggests, in Caesar’s Cipher each character
in a word is replaced by another character under some defined rules.
• Thus, if A is replaced by D, B by E and so on. Then, each character
in the word would be shifted by a position of 3.
FEATURES OF CRYPTOGRAPHY
1. Confidentiality:
• Information can only be accessed by the person for whom it is intended
and no other person except him can access it.
2. Integrity:
• Information cannot be modified in storage or transition between sender
and intended receiver without any addition to information being
detected.
3. Non-repudiation:
• The creator/sender of information cannot deny his intention to send
information at later stage.
4. Authentication:
• The identities of sender and receiver are confirmed. As well as
destination/origin of information is confirmed.
TYPES OF CRYPTOGRAPHY
In general there are three types of cryptography:

❖ Symmetric Key Cryptography

❖ Asymmetric Key Cryptography
❖ Hash Function
SYMMETRIC KEY CRYPTOGRAPHY
It is an encryption system where the sender and receiver of
message use a single common key to encrypt and decrypt
messages.
Symmetric Key Systems are faster and simpler but the
problem is that sender and receiver have to somehow
exchange key in a secure manner.
The most popular symmetric key cryptography system are
Data Encryption System(DES) and Advanced Encryption
System(AES).
ASYMMETRIC KEY
CRYPTOGRAPHY
Under this system a pair of keys is used to encrypt and decrypt
information.
A receiver’s public key is used for encryption and a receiver’s
private key is used for decryption.
Public key and Private Key are different. Even if the public key
is known by everyone the intended receiver can only decode it
because he alone know his private key.
The most popular asymmetric key cryptography algorithm is
RSA algorithm. (Rivest-Shamir-Adleman encryption).
HASH FUNCTION
There is no usage of any key in this algorithm.
A hash value with fixed length is calculated as per the plain
text which makes it impossible for contents of plain text to be
recovered.
Many operating systems use hash functions to encrypt
passwords.
CRYPTOGRAPHY VS ENCRYPTION
Cryptography is the science of concealing messages with a
secret code.
Encryption is the way to encrypt and decrypt data.
The first is about studying methods to keep a message
secret between two parties (like symmetric and asymmetric
keys), and the second is about the process itself.
SYMMETRIC ENCRYPTION
Symmetric encryption, also referred to as conventional
encryption or single-key encryption, was the only type of
encryption in use prior to the introduction of public-key
encryption in the late 1970s.
Countless individuals and groups, from Julius Caesar to the
German U-boat force to present-day diplomatic, military,
and commercial users, have used symmetric encryption for
secret communication.
It remains the more widely used of the two types of
encryption.
A SYMMETRIC ENCRYPTION SCHEME HAS FIVE
INGREDIENTS
Plaintext:
This is the original 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 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.
Decryption algorithm:
This is essentially the encryption algorithm run in reverse. It takes the
ciphertext and the secret key and produces the original plaintext
TWO REQUIREMENTS FOR SECURE USE OF
SYMMETRIC ENCRYPTION
Simplified Model of Symmetric Encryption
TWO REQUIREMENTS FOR SECURE USE OF
SYMMETRIC ENCRYPTION
1. We need a strong encryption algorithm. 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 to decipher the ciphertext or figure out the key.
This requirement is usually stated in a stronger form:
• The opponent should be unable to decrypt ciphertext or discover
the key even if he or she is in possession of a number of
ciphertexts together with the plaintext that produced each
ciphertext.
2. 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.
TWO GENERAL APPROACHES TO ATTACKING
A SYMMETRIC ENCRYPTION SCHEME
1. The first attack is known as cryptanalysis.
• Cryptanalytic attacks rely on the nature of the algorithm plus perhaps
some knowledge of the general characteristics of the plaintext or
even some sample plaintext-ciphertext pairs.
• This type of attack exploits the characteristics of the algorithm to
attempt to deduce a specific plaintext or to deduce the key being
used.
• If the attack succeeds in deducing the key, the effect is catastrophic:
All future and past messages encrypted with that key are compromised.
2. The second method, known as the brute-force attack
• is to try every possible key on a piece of ciphertext until an intelligible
translation into plaintext is obtained.
• On average, half of all possible keys must be tried to achieve
success.
TWO GENERAL APPROACHES TO ATTACKING A
SYMMETRIC ENCRYPTION SCHEME
Table shows how much time is involved for various key sizes.
The table shows results for each key size, assuming that it takes 1 μs to perform
a single decryption, a reasonable order of magnitude for today’s computers.
With the use of massively parallel organizations of microprocessors, it may be
possible to achieve processing rates many orders of magnitude greater.
The final column of the table considers the results for a system that can process 1
million keys per microsecond.
As we can see, at this performance level, a 56-bit key can no longer be
considered computationally secure.
SYMMETRIC BLOCK ENCRYPTION
ALGORITHMS
The most commonly used symmetric encryption algorithms are block
ciphers.
A block cipher processes the plaintext input in fixed-size blocks and
produces a block of ciphertext of equal size for each plaintext block.
The algorithm processes longer plaintext amounts as a series of fixed-size
blocks.
The most important symmetric algorithms, all of which are block ciphers, are
the Data Encryption Standard (DES), triple DES, and the Advanced
Encryption Standard (AES)
PRACTICAL SECURITY ISSUES
Typically, symmetric encryption is applied to a unit of data larger than a single
64-bit or 128-bit block.
E-mail messages, network packets, database records, and other plaintext sources
must be broken up into a series of fixed-length block for encryption by a
symmetric block cipher.
The simplest approach to multiple-block encryption is known as electronic
codebook (ECB) mode, in which plaintext is handled b bits at a time and each
block of plaintext is encrypted using the same key. Typically b 64 or b 128.
Figure 2.3a shows the ECB mode.
A plain text of length nb is divided into n b-bit blocks (P1, P2,c,Pn). Each block is
encrypted using the same algorithm and the same encryption key, to produce a
sequence of n b -bit blocks of ciphertext (C1, C 2,c,Cn). For lengthy messages,
the ECB mode may not be secure.
A cryptanalyst may be able to exploit regularities in the plaintext to ease the task
of decryption.
For example, if it is known that the message always starts out with certain
predefined fields, then the cryptanalyst may have a number of known
plaintext-ciphertext pairs to work with.
To increase the security of symmetric block encryption for large sequences of
data, a number of alternative techniques have been developed, called modes of
operation . These modes overcome the weaknesses of ECB; each mode has its
own particular advantages.
PRACTICAL SECURITY ISSUES
STREAM CIPHERS
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.
Although block ciphers are far more common, there are certain applications
in which a stream cipher is more appropriate.
A typical stream cipher encrypts plaintext one byte at a time, although a
stream cipher may be designed to operate on one bit at a time or on units
larger than a byte at a time.
Figure b is a representative diagram of stream cipher structure.
In this structure a key is input to a pseudorandom bit generator that
produces a stream of 8-bit numbers that are apparently random.
A pseudorandom stream is one that is unpredictable without knowledge of
the input key and which has an apparently random character. The output of
the generator, called a keystream , is combined one byte at a time with the
plaintext stream using the bitwise exclusive- OR (XOR) operation.
STREAM CIPHERS
With a properly designed pseudorandom number generator, a stream cipher
can be as secure as block cipher of comparable key length.
The primary advantage of a stream cipher is that stream ciphers are almost
always faster and use far less code than do block ciphers.
The advantage of a block cipher is that you can reuse keys. For applications
that require encryption/decryption of a stream of data, such as over a data
communications channel or a browser/Web link, a stream cipher might be
the better alternative. For applications that deal with blocks of data, such as
file transfer, e-mail, and database, block ciphers may be more appropriate.
However, either type of cipher can be used in virtually any application.
PUBLIC KEY CRYPTOGRAPHY (ASYMMETRIC
ENCRYPTION)
Public-key encryption, first publicly proposed by Diffie and Hellman in 1976 is the
first truly revolutionary advance in encryption in literally thousands of years.
Public-key algorithms are based on mathematical functions rather than on simple
operations on bit patterns, such as are used in symmetric encryption algorithms.
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 areas of confidentiality, key distribution, and
authentication.
Before proceeding, we should first mention several common misconceptions
concerning public-key encryption.
One is that public-key encryption is more secure from cryptanalysis than symmetric
encryption. In fact, the security of any encryption scheme depends on (1) the length
of the key and (2) the computational work involved in breaking a cipher. There is
nothing in principle about either symmetric or public-key encryption that makes one
superior to another from the point of view of resisting cryptanalysis.
A second misconception is that public-key encryption is a general- purpose
technique that has made symmetric encryption obsolete. On the contrary, because
of the computational overhead of current public-key encryption schemes, there
seems no foreseeable likelihood that symmetric encryption will be abandoned.
PUBLIC KEY CRYPTOGRAPHY (ASYMMETRIC
ENCRYPTION)
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 key:
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 encryption 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.
Note: (The key used in symmetric encryption is typically referred to as a secret key. The two keys used for
public-key encryption are referred to as the public key and the private key. Invariably, 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.)
PUBLIC KEY CRYPTOGRAPHY (ASYMMETRIC
ENCRYPTION)
PUBLIC KEY CRYPTOGRAPHY (ASYMMETRIC
ENCRYPTION)
As the names suggest, the public key of the pair is made public for others to use,
while the private key is known only to its owner.
A general-purpose public-key cryptographic algorithm relies on one key for
encryption and a different but related key for decryption.
The essential steps are the following:
1. Each user generates a pair of keys to be used for the encryption and decryption
of messages.
2. Each user places one of the two keys in a public register or other accessible
file. This is the public key. The companion key is kept private. As Figure a
suggests, each user maintains a collection of public keys obtained from others.
3. If B wishes to send a private message to A, B encrypts the message using A’s
public key.
4. When A receives the message, he decrypts it using his private key. No other
recipient can decrypt the message because only A knows A’s private key.
With this approach, all participants have access to public keys, and private keys are
generated locally by each participant and therefore need never be distributed.
As long as a user protects his or her private key, incoming communication is secure.
At any time, a user can change the private key and publish the companion public key
to replace the old public key.
PUBLIC KEY CRYPTOGRAPHY (ASYMMETRIC
ENCRYPTION)
• Figure b illustrates another mode of operation of public-key cryptography.
• In this scheme, a user encrypts data using his or her own private key.
Anyone who knows the corresponding public key will then be able to decrypt
the message.
• The scheme of Figure a is directed toward providing confidentiality:
• Only the intended recipient should be able to decrypt the ciphertext
because only the intended recipient is in possession of the required
private key. Whether in fact confidentiality is provided depends on a
number of factors, including the security of the algorithm, whether the
private key is kept secure, and the security of any protocol of which the
encryption function is a part.
• The scheme of Figure b is directed toward providing authentication and/or
data integrity.
• If a user is able to successfully recover the plaintext from B’s ciphertext
using B’s public key, this indicates that only B could have encrypted the
plaintext, thus providing authentication. Further, no one but B would be able
to modify the plaintext because only B could encrypt the plaintext with B’s
private key. Once again, the actual provision of authentication or data
integrity depends on a variety of factors.
APPLICATIONS FOR PUBLIC-KEY CRYPTOSYSTEMS
• Before proceeding, we need to clarify one aspect of public-key
cryptosystems that is otherwise likely to lead to confusion.
• Public-key systems are characterized by the use of a
cryptographic type of 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:
• digital signature, symmetric key distribution, and encryption
of secret keys.
APPLICATIONS FOR PUBLIC-KEY CRYPTOSYSTEMS

Algorithm Digital Signature Symmetric Key Encryption of

Distribution Secret Keys

RSA Yes Yes Yes

Diffie-Hellman No Yes No

DSS Yes No No

Elliptic Curve Yes Yes Yes

REQUIREMENTS FOR PUBLIC-KEY CRYPTOGRAPHY
The cryptosystem depends on a cryptographic algorithm based on two related keys.
Diffie and Hellman postulated this system 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 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 opponent, knowing the public key, PUb, to
determine the private key, PRb.
5. It is computationally infeasible for an opponent, 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. Either of the two related keys can be used for encryption, with the other used
for decryption.
M = D[PUb, E(PRb, M)] = D[PRb, E(PUb, M)]
ASYMMETRIC ENCRYPTION ALGORITHMS
Here are the most widely used asymmetric encryption algorithms.
RSA:
One of the first public-key schemes was developed in 1977 by Ron Rivest, Adi
Shamir, and Len Adleman at MIT and first published in 1978 [RIVE78].
The RSA scheme has since reigned supreme as the most widely accepted and
implemented approach to public-key encryption.
RSA is a block cipher in which the plaintext and ciphertext are integers between 0
and n – 1 for some n.
In 1977, the three inventors of RSA dared Scientific American readers to decode a
cipher they printed in Martin Gardner’s “Mathematical Games” column. They offered a
$100 reward for the return of a plaintext sentence, an event they predicted might not
occur for some 40 quadrillion years.
In April of 1994, a group working over the Internet and using over 1600 computers
claimed the prize after only eight months of work [LEUT94].
This challenge used a public-key size (length of n) of 129 decimal digits, or around
428 bits. This result does not invalidate the use of RSA; it simply means that larger
key sizes must be used.
Currently, a 1024-bit key size (about 300 decimal digits) is considered strong enough
for virtually all applications.
DIFFIE-HELLMAN KEY AGREEMENT
The first published public-key algorithm appeared in the
seminal paper by Diffie and Hellman that defined
public-key cryptography [DIFF76] and is generally
referred to as Diffie-Hellman key exchange, or key
agreement.
A number of commercial products employ this key
exchange technique.
The purpose of the algorithm is to enable two users to
securely reach agreement about a shared secret that can
be used as a secret key for subsequent symmetric
encryption of messages.
The algorithm itself is limited to the exchange of the keys.
DIGITAL SIGNATURE STANDARD
The National Institute of Standards and Technology (NIST)
has published Federal Information Processing Standard
FIPS PUB 186, known as the Digital Signature Standard
(DSS).
The DSS makes use of SHA-1 and presents a new digital
signature technique, the Digital Signature Algorithm (DSA).
The DSS was originally proposed in 1991 and revised in
1993 in response to public feedback concerning the
security of the scheme. There was a further minor revision
in 1996.
The DSS uses an algorithm that is designed to provide
only the digital signature function. Unlike RSA, it cannot be
used for encryption or key exchange.
ELLIPTIC CURVE CRYPTOGRAPHY
The vast majority of the products and standards that use public-key
cryptography for encryption and digital signatures use RSA.
The bit length for secure RSA use has increased over recent years, and this
has put a heavier processing load on applications using RSA.
This burden has ramifications, especially for electronic commerce sites that
conduct large numbers of secure transactions.
Recently, a competing system has begun to challenge RSA: elliptic curve
cryptography (ECC).
Already, ECC is showing up in standardization efforts, including the IEEE
(Institute of Electrical and Electronics Engineers) P1363 Standard for
Public-Key Cryptography.
The principal attraction of ECC compared to RSA is that it appears to offer
equal security for a far smaller bit size, thereby reducing processing
overhead.
On the other hand, although the theory of ECC has been around for some
time, it is only recently that products have begun to appear and that there
has been sustained cryptanalytic interest in probing for weaknesses.
Thus, the confidence level in ECC is not yet as high as that in RSA.
PUBLIC-KEY CERTIFICATES
The point of public-key encryption is that the public key is public.
Thus, if there is some broadly accepted public-key algorithm, such as RSA, any
participant can send his or her public key to any other participant or broadcast the key
to the community at large.
Although this approach is convenient, it has a major weakness. Anyone can forge
such a public announcement.
That is, some user could pretend to be A and send a public key to another participant
or broadcast such a public key. Until such time as A discovers the forgery and alerts
other participants, the forger is able to read all encrypted messages intended for A
and can use the forged keys for authentication.
The solution to this problem is the public-key certificate.
A certificate consists of a public key plus a user ID of the key owner, with the whole
block signed by a trusted third party.
The certificate also includes some information about the third party plus an indication
of the period of validity of the certificate. The third party is a certificate authority (CA)
that is trusted by the user community, such as a government agency or a financial
institution. A user can present his public key to the authority in a secure manner and
obtain a signed certificate. The user can then publish the certificate. Anyone needing
this user’s public key can obtain the certificate and verify that it is valid by means of
the attached trusted signature.
PUBLIC-KEY CERTIFICATES
One scheme has become universally accepted for formatting public-key certificates:
the X.509 standard.
X.509 certificates are used in most network security applications, including IP
Security (IPsec), Transport Layer Security (TLS), Secure Shell (SSH), and
Secure/Multipurpose Internet Mail Extension (S/MIME).
Figure: Public-Key Certificate Use
SYMMETRIC KEY EXCHANGE USING PUBLIC-KEY
ENCRYPTION
With symmetric encryption, a fundamental requirement for two parties to communicate securely
is that they share a secret key.
Suppose A wants to create a messaging application that will enable him to exchange e-mail
securely with anyone who has access to the Internet or to some other network that the two of
them share.
Suppose A wants to do this using symmetric encryption.
With symmetric encryption, A and his correspondent B, must come up with a way to share a
unique secret key that no one else knows. How are they going to do that?
If B is in the next room from A, A could generate a key and write it down on a piece of paper or
store it on a disc or thumb drive and hand it to B.
But if B is on the other side of the country, what can A do? He could encrypt this key using
symmetric encryption and e-mail it to B, but this means that A and B must share a secret key to
encrypt this new secret key.
Furthermore, A and everyone else who uses this new e-mail package faces the same problem
with every potential correspondent: Each pair of correspondents must share a unique secret key.
One approach is the use of Diffie-Hellman key exchange. This approach is indeed widely used.
However, it suffers the drawback that, in its simplest form, Diffie-Hellman provides no
authentication of the two communicating partners.
There are variations to Diffie-Hellman that overcome this problem. Also, there are protocols
using other public-key algorithms that achieve the same objective.
DIFFIE-HELLMAN KEY EXCHANGE
The first published public-key algorithm appeared in the seminal paper by
Diffie and Hellman that defined public-key cryptography [DIFF76] and is
generally referred to as Diffie-Hellman key exchange. A number of
commercial products employ this key exchange technique.
The purpose of the algorithm is to enable two users to exchange a secret key
securely that can then be used for subsequent encryption of messages. The
algorithm itself is limited to the exchange of the keys.
The Diffie-Hellman algorithm depends for its effectiveness on the difficulty of
computing discrete logarithms.
Briefly, we can define the discrete logarithm in the following way.
First, we define a primitive root of a prime number p as one whose powers
generate all the integers from 1 to p - 1.
DIFFIE-HELLMAN KEY EXCHANGE
That is, if a is a primitive root of the prime number p , then the numbers
a modp, a2modp,……., ap-1 modp
are distinct and consist of the integers from 1 through p - 1 in some
permutation.

For any integer b less than p and a primitive root a of prime number p , one
can find a unique exponent i such that
b = ai mod p where 0 < i < (p - 1)
The exponent i is referred to as the discrete logarithm, or index, of b for the
base a , mod p .
We denote this value as dlog a,p ( b )2
THE ALGORITHM
With this background we can define the Diffie-Hellman key exchange.
For this scheme, there are two publicly known numbers:
a prime number q and
an integer α that is a primitive 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 modq .
Similarly, user B independently selects a random integer XB < q and
computes YB = α XB modq . 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)XA mod q
= (aXB mod q)XA mod q
= (aXB)XB mod q
= aXB XA mod q
= (aXA)XB mod q
= (aXA mod q)XB mod q
= (YA)XB mod q