UNIT IV

ASYMMETRIC KEY ALGORITHM, DIGITAL SIGNATURE AND RSA

Asymmetric encryption, also known as public-key cryptography, is a type of
encryption that uses a pair of keys to encrypt and decrypt data. The pair of
keys includes a public key, which can be shared with anyone, and a private
key, which is kept secret by the owner. In asymmetric encryption, the sender
uses the recipient’s public key to encrypt the data. The recipient then uses
their private key to decrypt the data. This approach allows for secure
communication between two parties without the need for both parties to
have the same secret key. Asymmetric encryption has several advantages
over symmetric encryption, which uses the same key for both encryption and
decryption. One of the main advantages is that it eliminates the need to
exchange secret keys, which can be a challenging process, especially when
communicating with multiple parties. Additionally, asymmetric encryption
allows for the creation of digital signatures, which can be used to verify the
authenticity of data. Asymmetric encryption is commonly used in various
applications, including secure online communication, digital signatures, and
secure data transfer. Examples of asymmetric encryption algorithms include
RSA, Diffie-Hellman, and Elliptic Curve Cryptography (ECC). Asymmetric
encryption, commonly known as public-key cryptography, employs two
distinct keys for encryption and decoding. The private key is a separate key
from the public key that is kept private by the owner of the public key while
the public key is made available to everyone. Anyone can encrypt a message
using the public key, but only the holder of the private key can unlock it.
With no chance of the communication being intercepted and read by a third
party, anyone can send a secure message to the public key’s owner.
Asymmetric encryption is frequently used for secure internet
communication, including email encryption, e-commerce, and online
banking. Digital signatures, which are used to confirm the legitimacy of
digital documents and messages, are another application for it.

Advantages of Asymmetric Encryption

Asymmetric encryption also known as public key cryptography is a method

of cryptography that uses two different keys to encrypt and decrypt data,
here are some advantages of asymmetric encryption: –
• Enhanced Security: Asymmetric encryption provides a higher level
of security compared to symmetric encryption where only one key is
used for both encryption and decryption with asymmetric
encryption a different key is used for each process and the private
 key used for decryption is kept secret by the receiver making, it
harder for an attacker to intercept and decrypt the data.
• Authentication: Asymmetric encryption can be used for
authentication purposes which means that the receiver can verify the
sender s identity. This is achieved by the sender encrypting a
message with their private key which can only be decrypted with
their public key if the receiver can successfully decrypt the message,
it proves that it was sent by the sender who has the corresponding
private key.
• Non-repudiation: Asymmetric encryption also provides non-
repudiation which means that the sender cannot deny sending a
message or altering its contents this is because the message is
encrypted with the sender s private key and only their public key can
decrypt it . Therefore, the receiver can be sure that the message was
sent by the sender and has not been tampered with.
• Key distribution: Asymmetric encryption eliminates the need for a
secure key distribution system that is required in symmetric
encryption with symmetric encryption, the same key is used for both
encryption and decryption and the key needs to be securely shared
between the sender and the receiver asymmetric encryption, on the
other hand, allows the public key to be shared openly and the private
key is kept secret by the receiver.
• Versatility: Asymmetric encryption can be used for a wide range of
applications including secure email communication online banking
transactions and e-commerce it is also used to secure SSL/TSL
connections which are commonly used to secure internet traffic.
Overall, the use of asymmetric encryption offers enhanced security
authentication non-repudiation key distribution, and versatility these
advantages make it a widely used and effective method for protecting
sensitive data in various applications.
RSA algorithm (Rivest-Shamir-Adleman)

What is the RSA algorithm (Rivest-Shamir-Adleman)?

The RSA algorithm (Rivest-Shamir-Adleman) is the basis of a cryptosystem
-- a suite of cryptographic algorithms that are used for specific security
services or purposes -- which enables public key encryption and is widely
used to secure sensitive data, particularly when it is being sent over an
insecure network such as the internet.
RSA was first publicly described in 1977 by Ron Rivest, Adi Shamir and
Leonard Adleman of the Massachusetts Institute of Technology, though the
1973 creation of a public key algorithm by British mathematician Clifford
Cocks was kept classified by the U.K.'s GCHQ until 1997.

Public key cryptography, also known as asymmetric cryptography, uses two

different but mathematically linked keys -- one public and one private.
The public key can be shared with everyone, whereas the private key must
be kept secret.

RSA is a type
of asymmetric encryption, which uses two different but linked keys.

In RSA cryptography, both the public and the private keys can encrypt a
message. The opposite key from the one used to encrypt a message is used to
decrypt it. This attribute is one reason why RSA has become the most widely
used asymmetric algorithm: It provides a method to assure the
confidentiality, integrity, authenticity, and non-repudiation of electronic
communications and data storage.
Many protocols, including Secure Shell (SSH), OpenPGP, S/MIME,
and SSL/TLS, rely on RSA for encryption and digital signature functions. It
is also used in software programs -- browsers are an obvious example, as
they need to establish a secure connection over an insecure network, like the
internet, or validate a digital signature. RSA signature verification is one of
the most commonly performed operations in network-connected systems.

Why is the RSA algorithm used?

RSA derives its security from the difficulty of factoring large integers that
are the product of two large prime numbers. Multiplying these two numbers
is easy, but determining the original prime numbers from the total --
or factoring -- is considered infeasible due to the time it would take using
even today's supercomputers.

The public and private key generation algorithm is the most complex part of
RSA cryptography. Two large prime numbers, p and q, are generated using
the Rabin-Miller primality test algorithm. A modulus, n, is calculated by
multiplying p and q. This number is used by both the public and private
keys and provides the link between them. Its length, usually expressed in
bits, is called the key length.

The public key consists of the modulus n and a public exponent, e, which is
normally set at 65537, as it's a prime number that is not too large. The e
figure doesn't have to be a secretly selected prime number, as the public key
is shared with everyone.

The private key consists of the modulus n and the private exponent d, which
is calculated using the Extended Euclidean algorithm to find the
multiplicative inverse with respect to the totient of n.

How does the RSA algorithm work?

Alice generates her RSA keys by selecting two primes: p=11 and q=13. The
modulus is n=p×q=143. The totient is n ϕ(n)=(p−1)x(q−1)=120. She chooses
7 for her RSA public key e and calculates her RSA private key using the
Extended Euclidean algorithm, which gives her 103.
Bob wants to send Alice an encrypted message, M, so he obtains her RSA
public key (n, e) which, in this example, is (143, 7). His plaintext message is
just the number 9 and is encrypted into ciphertext, C, as follows:

Me mod n = 97 mod 143 = 48 = C

When Alice receives Bob's message, she decrypts it by using her RSA
private key (d, n) as follows:

Cd mod n = 48103 mod 143 = 9 = M

Let us learn the mechanism behind the RSA algorithm: >> Generating
Public Key:
Select two prime no's. Suppose P = 53 and Q = 59.
Now First part of the Public key : n = P*Q = 3127.
We also need a small exponent say e :
But e Must be
An integer.
Not be a factor of Φ(n).
1 < e < Φ(n) [Φ(n) is discussed below],
Let us now consider it to be equal to 3.
Our Public Key is made of n and e
>> Generating Private Key:
We need to calculate Φ(n) :
Such that Φ(n) = (P-1)(Q-1)
so, Φ(n) = 3016
Now calculate Private Key, d :
d = (k*Φ(n) + 1) / e for some integer k
For k = 2, value of d is 2011.
Now we are ready with our – Public Key ( n = 3127 and e = 3) and Private
Key(d = 2011) Now we will encrypt “HI”:
Convert letters to numbers: H = 8 and I = 9
Thus Encrypted Data c = (89e)mod n
Thus our Encrypted Data comes out to be 1394
Now we will decrypt 1394:
Decrypted Data = (cd)mod n
Thus our Encrypted Data comes out to be 89
8 = H and I = 9 i.e. "HI".
To use RSA keys to digitally sign a message, Alice would need to create
a hash -- a message digest of her message to Bob -- encrypt the hash value
with her RSA private key, and add the key to the message. Bob can then
verify that the message has been sent by Alice and has not been altered by
decrypting the hash value with her public key. If this value matches the hash
of the original message, then only Alice could have sent it -- authentication
and non-repudiation -- and the message is exactly as she wrote it -- integrity.

Alice could, of course, encrypt her message with Bob's RSA public key --
confidentiality -- before sending it to Bob. A digital certificate contains
information that identifies the certificate's owner and also contains the
owner's public key. Certificates are signed by the certificate authority that
issues them, and they can simplify the process of obtaining public keys and
verifying the owner.

An RSA key
exchange involves multiple steps.
How is RSA secure?
RSA security relies on the computational difficulty of factoring large
integers. As computing power increases and more efficient factoring
algorithms are discovered, the ability to factor larger and larger numbers
also increases.

Encryption strength is directly tied to key size. Doubling key length can
deliver an exponential increase in strength, although it does impair
performance. RSA keys are typically 1024- or 2048-bits long, but experts
believe that 1024-bit keys are no longer fully secure against all attacks. This
is why the government and some industries are moving to a minimum key
length of 2048-bits.

Barring an unforeseen breakthrough in quantum computing, it will be many

years before longer keys are required, but elliptic curve
cryptography (ECC) is gaining favor with many security experts as an
alternative to RSA to implement public key cryptography. It can create
faster, smaller and more efficient cryptographic keys.

Modern hardware and software are ECC-ready, and its popularity is likely
to grow. It can deliver equivalent security with lower computing power and
battery resource usage, making it more suitable for mobile apps than RSA.

A team of researchers, which included Adi Shamir, a co-inventor of RSA,

successfully created a 4096-bit RSA key using acoustic cryptanalysis.
However, note that any encryption algorithm is vulnerable to attack.

NP HARD:
A problem is in the class NPC if it is in NP and is as hard as any problem in
NP. A problem is NP-hard if all problems in NP are polynomial time
reducible to it, even though it may not be in NP itself.

If a polynomial time algorithm exists for any of these problems, all problems
in NP would be polynomial time solvable. These problems are called NP-
complete. The phenomenon of NP-completeness is important for both
theoretical and practical reasons.
Definition of NP-Completeness
A language B is NP-complete if it satisfies two conditions
• B is in NP
• Every A in NP is polynomial time reducible to B.
If a language satisfies the second property, but not necessarily the first one,
the language B is known as NP-Hard. Informally, a search problem B is NP-
Hard if there exists some NP-Complete problem A that Turing reduces to B.
The problem in NP-Hard cannot be solved in polynomial time, until P = NP.
If a problem is proved to be NPC, there is no need to waste time on trying to
find an efficient algorithm for it. Instead, we can focus on design
approximation algorithm.
NP-Complete Problems
Following are some NP-Complete problems, for which no polynomial time
algorithm is known.
•Determining whether a graph has a Hamiltonian cycle
• Determining whether a Boolean formula is satisfiable, etc.
NP-Hard Problems
The following problems are NP-Hard
• The circuit-satisfiability problem
• Set Cover
• Vertex Cover
• Travelling Salesman Problem
In this context, now we will discuss TSP is NP-Complete
TSP is NP-Complete
The traveling salesman problem consists of a salesman and a set of cities. The
salesman has to visit each one of the cities starting from a certain one and
returning to the same city. The challenge of the problem is that the traveling
salesman wants to minimize the total length of the trip

SYMMETRIC AND ASYMMETRIC KEY CRYPTOGRAPHY

TOGETHER:
When symmetric and asymmetric encryption are combined, the following
takes place: Symmetric encryption is used to convert the plaintext to
ciphertext. This takes advantage of the symmetric encryption speed.
Asymmetric encryption is used to exchange the symmetric key used for
encryption.

Symmetric Key Encryption: Encryption is a process to change the form of

any message in order to protect it from reading by anyone. In Symmetric-
key encryption the message is encrypted by using a key and the same key is
used to decrypt the message which makes it easy to use but less secure. It also
requires a safe method to transfer the key from one party to another.
Asymmetric Key Encryption: Asymmetric Key Encryption is based on
public and private key encryption techniques. It uses two different key to
encrypt and decrypt the message. It is more secure than the symmetric key
encryption technique but is much slower.
Symmetric Key Encryption Asymmetric Key Encryption

It requires two keys, a public key

It only requires a single key for both
and a private key, one to encrypt
encryption and decryption.
and the other one to decrypt.

The size of cipher text is the same

The size of cipher text is the same or
or larger than the original plain
smaller than the original plain text.
text.

The encryption process is very fast. The encryption process is slow.

It is used when a large amount of It is used to transfer small amounts

data is required to transfer. of data.

It provides confidentiality,
It only provides confidentiality.
authenticity, and non-repudiation.

The length of key used is 128 or 256 The length of key used is 2048 or
bits higher

In symmetric key encryption, In asymmetric key encryption,

resource utilization is low as resource utilization is high.
 Symmetric Key Encryption Asymmetric Key Encryption

compared to asymmetric key

encryption.

It is comparatively less efficient as

It is efficient as it is used for
it can handle a small amount of
handling large amount of data.
data.

Security is less as only one key is It is more secure as two keys are
used for both encryption and used here- one for encryption and
decryption purpose. the other for decryption.

The Mathematical Representation is The Mathematical Representation

as follows- is as follows-
P = D (K, E(K, P)) P = D(Kd, E (Ke,P))
where K –> encryption and where Ke –> encryption key
decryption key Kd –> decryption key
P –> plain text D –> Decryption
D –> Decryption E(Ke, P) –> Encryption of plain
E(K, P) –> Encryption of plain text text using encryption key Ke. P –>
using K plain text

Examples: 3DES, AES, DES and Examples: Diffie-Hellman, ECC, El

RC4 Gamal, DSA and RSA

DIGITAL SIGNATURE:
Digital signatures are created and verified by using public key cryptography,
also known as asymmetric cryptography. By the use of a public key
algorithm, such as RSA, one can generate two keys that are mathematically
linked- one is a private key, and another is a public key.
Digital signatures are the public-key primitives of message authentication. In
the physical world, it is common to use handwritten signatures on
handwritten or typed messages. They are used to bind signatory to the
message.
Similarly, a digital signature is a technique that binds a person/entity to the
digital data. This binding can be independently verified by receiver as well as
any third party.
Digital signature is a cryptographic value that is calculated from the data and
a secret key known only by the signer.
In real world, the receiver of message needs assurance that the message
belongs to the sender and he should not be able to repudiate the origination
of that message. This requirement is very crucial in business applications,
since likelihood of a dispute over exchanged data is very high.
Model of Digital Signature
As mentioned earlier, the digital signature scheme is based on public key
cryptography. The model of digital signature scheme is depicted in the
following illustration −

The following points explain the entire process in detail −

• Each person adopting this scheme has a public-private key pair.
• Generally, the key pairs used for encryption/decryption and
signing/verifying are different. The private key used for signing is
referred to as the signature key and the public key as the
verification key.
• Signer feeds data to the hash function and generates hash of data.
• Hash value and signature key are then fed to the signature
algorithm which produces the digital signature on given hash.
Signature is appended to the data and then both are sent to the
verifier.
• Verifier feeds the digital signature and the verification key into the
verification algorithm. The verification algorithm gives some value
as output.
 • Verifier also runs same hash function on received data to generate
hash value.
• For verification, this hash value and output of verification
algorithm are compared. Based on the comparison result, verifier
decides whether the digital signature is valid.
• Since digital signature is created by ‘private’ key of signer and no
one else can have this key; the signer cannot repudiate signing the
data in future.
It should be noticed that instead of signing data directly by signing algorithm,
usually a hash of data is created. Since the hash of data is a unique
representation of data, it is sufficient to sign the hash in place of data. The
most important reason of using hash instead of data directly for signing is
efficiency of the scheme.
Let us assume RSA is used as the signing algorithm. As discussed in public
key encryption chapter, the encryption/signing process using RSA involves
modular exponentiation.
Signing large data through modular exponentiation is computationally
expensive and time consuming. The hash of the data is a relatively small digest
of the data, hence signing a hash is more efficient than signing the entire data.
Importance of Digital Signature
Out of all cryptographic primitives, the digital signature using public key
cryptography is considered as very important and useful tool to achieve
information security.
Apart from ability to provide non-repudiation of message, the digital
signature also provides message authentication and data integrity. Let us
briefly see how this is achieved by the digital signature −
• Message authentication − When the verifier validates the digital
signature using public key of a sender, he is assured that signature
has been created only by sender who possess the corresponding
secret private key and no one else.
• Data Integrity − In case an attacker has access to the data and
modifies it, the digital signature verification at receiver end fails.
The hash of modified data and the output provided by the
verification algorithm will not match. Hence, receiver can safely
deny the message assuming that data integrity has been breached.
• Non-repudiation − Since it is assumed that only the signer has the
knowledge of the signature key, he can only create unique signature
on a given data. Thus the receiver can present data and the digital
 signature to a third party as evidence if any dispute arises in the
future.
By adding public-key encryption to digital signature scheme, we can create a
cryptosystem that can provide the four essential elements of security namely
− Privacy, Authentication, Integrity, and Non-repudiation.
Encryption with Digital Signature
In many digital communications, it is desirable to exchange an encrypted
messages than plaintext to achieve confidentiality. In public key encryption
scheme, a public (encryption) key of sender is available in open domain, and
hence anyone can spoof his identity and send any encrypted message to the
receiver.
This makes it essential for users employing PKC for encryption to seek digital
signatures along with encrypted data to be assured of message authentication
and non-repudiation.
This can archived by combining digital signatures with encryption scheme.
Let us briefly discuss how to achieve this requirement. There are two
possibilities, sign-then-encrypt and encrypt-then-sign.
However, the crypto system based on sign-then-encrypt can be exploited by
receiver to spoof identity of sender and sent that data to third party. Hence,
this method is not preferred. The process of encrypt-then-sign is more reliable
and widely adopted. This is depicted in the following illustration −

The receiver after receiving the encrypted data and signature on it, first
verifies the signature using sender’s public key. After ensuring the validity of
the signature, he then retrieves the data through decryption using his private
key.

MESSAGE DIGEST AND HASH FUNCTION:

What Does Message Digest Mean? A message digest is a cryptographic hash
function containing a string of digits created by a one-way hashing formula.
Message digests are designed to protect the integrity of a piece of data or
media to detect changes and alterations to any part of a message.

What is the difference between hash function and message digest?

A message digest is a fixed size numeric representation of the contents of a
message. A message digest is computed by a hash function, which is a
transformation that meets two criteria: The hash function must be one way.