Scribd
Upload
6 views6 pages

Public Key Cryptography and RSA Overview

The document discusses the principles and applications of Public Key Cryptography, particularly focusing on the RSA algorithm. It outlines the characteristics of public key systems, the process of key generation, and the importance of secure communications without relying on a key distribution center. Additionally, it addresses potential vulnerabilities and attacks on RSA, including brute force, mathematical, timing, and chosen ciphertext attacks, along with countermeasures to enhance security.

Uploaded by

chodanker15
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views6 pages

Public Key Cryptography and RSA Overview

The document discusses the principles and applications of Public Key Cryptography, particularly focusing on the RSA algorithm. It outlines the characteristics of public key systems, the process of key generation, and the importance of secure communications without relying on a key distribution center. Additionally, it addresses potential vulnerabilities and attacks on RSA, including brute force, mathematical, timing, and chosen ciphertext attacks, along with countermeasures to enhance security.

Uploaded by

chodanker15
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

UNIT-2

Chapter 5
IT 810
Cryptography Public key
and Cryptography and
Network Security RSA

Principles of Public Key Cryptosystem Public Key Cryptosystem

Public Key Cryptosystem evolved from an attempt to solve two of the most • Asymmetric Key Cryptosystem OR Public key Cryptosystem
difficult problems associated with Symmetric Encryption • One key for Encryption and a different but related key for Decryption

1. Key Distribution under Symmetric Encryption requires • Public Key Cryptosystem/Algorithm – Following Characteristics
• That two communicants already share a key, which somehow has been • It is computationally infeasible to determine the decryption key given only
distributed to them knowledge of the cryptographic algorithm and the encryption key
- Non repudiation • Either of the two related keys can be used for encryption, with the other used for
decryption
• The use of a key distribution center – If KDC is compromised
• A Public-Key Encryption scheme has Six Ingredients
How to have secure communications in general without having to trust a KDC with your
key?? • Plaintext – readable message or data that is fed as input
• Encryption Algorithm – Performs various transformations on plaintext

2. Digital Signatures: • Public Key – is known to owner as well as others


• Private Key – is known to only Owner
• How to verify that a received message really comes from the claimed sender?
• Ciphertext – Scrambled message produced as output
• Decryption Algorithm - accepts the ciphertext and the matching key and produces
3 4
the original plaintext

Encryption with Receivers Public Key • Encryption with Senders Private Key
- Achieve Confidentiality • Achieve Authentication

5 6

1
• The essential steps are the following:

1. Each user generates a Pair of Keys to be used for the encryption and decryption
2. Each user places one of the two keys in a public register or other accessible file (This
is the public key). The companion key is kept private. Each user maintains a
collection of public keys obtained from others.
3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message
using Alice's public key.
4. When Alice receives the message, she decrypts it using her private key. No other
recipient can decrypt the message because only Alice knows Alice's private key

7 8

Public Key Cryptosystem : Secrecy Public Key Cryptosystem : Authentication

• Source - With the message X and the encryption Key Pub (public key of • Source - With the message X and the encryption Key PRa (Private key of source
Destination B ) as input A ) as input
• Source A forms the Ciphertext Y which is given by • Source A forms the Ciphertext Y which is given by
• Destination B in possession of the matching private key PRb is able to invert • Destination B in possession of the matching public key PUa is able to invert the
the transformation transformation

Entire encrypted message


Serves as a Digital Signature

Authenticated in terms of
Source & Data Integrity

9 10

Public Key Cryptosystem : Both Authentication and Secrecy Applications for Public Key Cryptosystem
• How to Provide both Authentication and Secrecy? • Encryption/ Decryption
• Double use of public key scheme • Sender encrypts the message with the recipients public key
• 1. Source - Encrypt the message X with its own Private Key PRa => Y • Digital Signature
• Provides Digital Signature • The sender “signs” a message with its private key
• 2. Source – Again encrypts Y by using public key PUb of destination => Z • Signing is achieved by a cryptographic algorithm applied to the message
• Provides Secrecy or Confidentiality • Key Exchange -
•The Final Ciphertext • Two sides cooperate to exchange a session key
can be decrypted only
by the intended recei- Some algorithms are suitable for all three applications, whereas others can be used only for
one or two of these applications
ver, who alone has the
Matching key

11 12

2
Requirement of Public Key Cryptography

1. It is computationally easy for a party B to generate a pair (PUb, PRb ) One Way Function:
is one that maps a domain into a range such that every function value has a unique
2. It is computationally easy for a sender A, knowing the public key and the message to be inverse, with the condition that the calculation of the function is easy, whereas the
encrypted M, to generate the corresponding Ciphertext: calculation of the inverse is infeasible

3. It is computationally easy for the receiver B to decrypt the resulting Ciphertext using the
private key to recover the original Message Trap Door One-way Function:
is easy to calculate in one direction and infeasible to calculate in the other direction
4. It is computationally infeasible for an adversary, knowing the public key PUb, to unless certain additional information is known. With the additional information the
determine the private key PRb inverse can be calculated in polynomial time

5. It is computationally infeasible for an adversary, knowing the public key PUb and a
ciphertext, C to recover the original message M

6. The two keys can be applied in either order Thus the development of a practical public-key scheme depends on discovery of a suitable
13 trap-door one-way function 14

Public-Key Cryptanalysis RSA Algorithm

• Ron Rivest, Adi Shamir and Len Adleman – in 1977


1. Public-key encryption scheme is vulnerable to a brute-force attack
1. Countermeasure – Use Larger Keys • Best Known & Widely used Public-Key Scheme or Asymmetric Algorithm
2. The key size must be large enough to make brute-force attack impractical but
small enough for practical encryption and decryption • Is a Block Cipher – Plaintext and Ciphertext are integers between 0 to n - 1 for some n

2. Another attack - To find some way to compute the private key given the public key. • Use Large Integers – 1024 bits or 309 decimal digits
- To date, it has not been mathematically proven that this form of attack
is infeasible for a particular public-key algorithm
• Based on Exponentiation in finite field over Integers modulo a prime

• RSA can be used for


• Encryption/Decryption
• Digital Signature
• Key Exchange
15 16

An integer p > 1 is a
prime number if and
RSA Algorithm RSA Algorithm- Example only if its only divisors
are ±1 and are ± p

1. Select two Prime numbers p = 17 and q = 11


Euler’s totient
function is defined as
2. Calculate n = p x q So n= 17 × 11 = 187 the number of
positive integers less
than n and
3. Calculate Ø (n) = ( p – 1 ) ( q – 1 ) = 16 × 10 = 160 relatively prime to n

For example Ø (37) = 36


Ø (35) = ??
List all of the positive integers less than 35 that are relatively prime to it
1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34
There are 24 positive integers less than 35 that are relatively prime to 35
Ø (35) = 24
By convention Ø (1) = 1
Ø (21) = ??
= Ø(3) x Ø (7) = (3 - 1) x (7 - 1) = 2 x 6 = 12
where the where the 12 integers are {1,2,4,5,8,10,11,13,16,17,19,20}
17 18

3
4. Select e such that e is relatively prime Ø (n) = 160 and less than Ø (n) 5. Determine d such that d x e  1 (mod 160) and d < 160
should satisfy Relative prime property =>> gcd ( Ø (n), e ) = 1
and 1 < e < Ø (n) The correct value is d = 23 because 23 × 7 = 161 = (1 × 160) + 1
How to select e and check whether they are relatively prime ?? d can be calculated using the extended Euclid’s algorithm
Let select e = 7 Extended Euclidian Algorithm => used to find Multiplicative Inverse of a given number
Euclidian Algorithm => used to find gcd of two positive integers -Only for First Time T1 =0 ; T2 = 1
We need to verify gcd ( 160, 7 ) = 1 T = T1 - (T2 x Q) Q A B R T1 T2 T
The algorithm assumes a > b > 0 T = 0 - (1 x 22) = -22 22 160 7 6 0 1 -22

Q A B R
T = 1 - (-22 x 1) = 1 + 22 = 23 1 7 6 1 1 -22 23
22 160 7 6
6 6 1 0 -22 23 -160
1 7 6 1 T = -22 - (23 x 6) = -22 -138 =-160
6 6 1 0 X 1 0 X 23 -160
X 1 0 X Multiplicative inverse of 7 is 23
19 20

n = 187 e= 7 d = 23

• The resulting keys are public key PU = {e , n} =>> {7, 187} and

Private key PR = { d, n} =>> {23, 187}

• Public keys are distributed to other parties

• Encryption

7
• Let Plaintext = 88 C = 88 mod 187
• Exploiting the properties of Modular arithmetic =>>
21 22

23 24

4
Computational Aspects of RSA Computational Aspects of RSA
1. Exponentiation in Modular Arithmetic: 3. Efficient Operation Using Private Key:
Example1:
• We cannot similarly choose a small constant value of d for efficient operation
• A small value of d is vulnerable to a brute-force attack and to other forms of
• Fast efficient tech for exponentiation is required cryptanalysis
• Example - Requires 15 times multiplications • However, there is a way to speed up computation using the CRT (Chinese Remainder
How to proceed?? Theorem) --This is approx 4 times faster than calculating “Cd mod n” directly
we can achieve the same final result with only four multiplications if we repeatedly • Note that only the owner of the private key details (who knows the values of p & q)
take the square of each partial result, successively forming (x2, x4, x8, x16) can use this technique

Example 2 : x11 = x 1+2+8 = (x)(x2)(x8) 4. Key Generation:


In this case we compute x mod n, x2mod n, x4 mod n, and x8 mod n and then calculate Users of RSA must determine two primes at random - p, q
[(x mod n) x (x2 mod n) x (x8 mod n) mod n Select either e or d and compute the other
p, q must not be easily derived from modulus n = p.q
2. Efficient Operation Using Public Key:
• - means must be sufficiently large
-To speed up the operation of the RSA algorithm using the public key, a specific choice of e is • exponents e, d are inverses, so use Extended Euclids Inverse algorithm to compute the
usually made. other
25 26
-with a very small public key, RSA becomes vulnerable to a simple attack.

The Security of RSA The Mathematical Attack – Factoring Problem

Four Possible approaches to attack RSA


We can identify three approaches to attacking RSA mathematically
1. Brute Force Attack : This involves trying all possible private keys
1. Defense against this attack is to use Large Key Space 1. Factor n into its two prime factors n = p.q
2. Larger number of bits in d – slower the system => Hence This enables calculation of Ø (n) = (p - 1) × (q - 1)
=> Which in turn enables determination of d = e-1 (mod Ø (n))
2. Mathematical Attacks: There are several approaches, all equivalent in effort to factoring
the product of two primes 2. Determine Ø (n) directly, without first determining p and q
=> Again, this enables determination of d = e-1 (mod Ø (n))
3. Timing Attacks: These depend on the running time of the decryption algorithm
3. Determine d directly, without first determining Ø (n)
4. Chosen Ciphertext Attacks: This type of attack exploits properties of the RSA algorithm

With presently known algorithms, determining d given e and n appears to be at least as time-
consuming as the factoring problem. Hence, we can use factoring performance as a
benchmark against which to evaluate the security of RSA

27 28

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 (309 decimal digits), both p and q should be on the order of
magnitude 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

In addition, it has been demonstrated that if e < n and d < n1/4, then d can be easily
determined

29 30

5
Timing Attack

• A timing attack is somewhat analogous to a burglar guessing the combination of a


safe by observing how long it takes for someone to turn the dial from number to
number
• Snooper can determine a private key by keeping track of how long a computer
takes to decipher messages

• This attack is alarming for two reasons


• It comes from a completely unexpected direction
• It is a Ciphertext-only attack

-Therefore, if the observed time to execute the decryption algorithm is always slow
when this particular iteration is slow with a 1 bit, then this bit is assumed to be 1.

-If a number of observed execution times for the entire algorithm are fast, then this bit
is assumed to be 0

Countermeasures ??
31 32

Chosen Ciphertext Attack


• The RSA algorithm is vulnerable to a Chosen Ciphertext Attack (CCA)
Although the timing attack is a serious threat, there are simple countermeasures • CCA is defined as an attack in which adversary chooses a number of ciphertexts and
gets decrypted plaintext back with the target's private key (adversary could select a
1. Use Constant Exponentiation Time: plaintext => encrypt it with target's public key and then be able to get the plaintext
- Ensure that all exponentiations take the same amount of time back by having it decrypted with the private key)
- This is a simple fix but does degrade performance • Chooses ciphertext to exploit properties of RSA to provide info to help cryptanalysis

2. Add Random delays: For Example : Takes advantage of the following property of RSA
- Better performance could be achieved by adding a random delay to the E(PU,M1) × E(PU,M2) = E(PU, [M1 × M2])
exponentiation algorithm to confuse the timing attack
We can decrypt C = Me mod n using a CCA as follows
1. Compute X = (C × 2e) mod n
3. Blinding: Blind values used in calculations 2. Submit X as a chosen ciphertext and receive back Y = Xd mod n
- Multiply the ciphertext by a random number before performing exponentiation But now note that
- 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

33 34 From this we can deduce M

Countermeasure - Plaintext is modified using a procedure known as Optimal Asymmetric - The concatenation of the maskedseed and the maskedDB forms the Encoded Message EM
Encryption Padding (OAEP) -Note that the EM includes the padded message, masked by the seed, and the seed, masked
As a first step the message M to be encrypted by the maskedDB
is padded - The EM is then encrypted using RSA
-A set of optional parameters P is passed through
a hash function H
- The output is then padded with zeros to get the
desired length in the overall data block (DB)
- 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 maskedDB
- The maskedDB is in turn passed through the
MGF to form a hash that is XORed with the seed
35 36
to produce the masked seed

Common questions

Powered by AI

Modular arithmetic is foundational to RSA, allowing operations within a limited numerical range, effectively serving as the backbone for the encryption and decryption processes. Messages are encrypted using exponentiation in a modular space, which keeps numbers within manageable bounds and allows the inversion process (decryption) to retrieve the original plaintext efficiently. This use of modular arithmetic also prevents overflow and maintains security by relying on the difficulty of reversing such operations without knowledge of the private key .

Choosing appropriate RSA keys is crucial because improper key sizes or values can compromise security. A small e might expedite encryption but can make the system vulnerable to specific attacks; similarly, a small d could simplify brute-force attacks or cryptanalysis. Furthermore, insufficiently large primes p and q increase the risk of factorization, making it easier for an adversary to compute φ(n) and thereby discover the private key d. Ensuring these elements are robustly chosen maintains the security and efficiency of the algorithm .

Euler’s totient function, φ(n), is integral to RSA as it is used in calculating the public and private keys. Specifically, φ(n) = (p-1)*(q-1) for primes p and q, which impacts the selection of e and computation of d as d is the multiplicative inverse of e modulo φ(n). It ensures that e and d are compatible such that applying the RSA algorithm recovers the original message, while the difficulty of determining φ(n) without knowing p and q helps secure the system against attacks based on factoring n .

Trap-door one-way functions are critical to public-key schemes because they allow secure encryption: they are functions that are easy to compute in one direction but infeasible to invert without special knowledge (the 'trap-door'). In the case of RSA, the factorization of a product of two large primes serves as the trap-door. This ensures that while it is computationally straightforward to encrypt data or verify a signature, only someone with the private key (knowledge of the prime factors) can decrypt the data or create a legitimate signature efficiently .

To achieve both authenticity and confidentiality, a message is first encrypted with the sender's private key to generate a digital signature, thus providing authenticity. This output is then encrypted again using the recipient's public key, ensuring confidentiality because only the recipient can decrypt it with their private key. This two-step encryption process ensures that only the intended recipient can access the message, and they can verify the sender's identity through the digital signature .

Chosen ciphertext attacks involve an attacker using knowledge about ciphertexts, possibly created by encrypting known plaintexts, and observing their decrypted values to reveal information about the encryption algorithm and its keys. RSA defends against such attacks by employing Optimal Asymmetric Encryption Padding (OAEP), which introduces randomness to the ciphertexts to prevent meaningful analysis based on the attacker’s chosen ciphertext .

Timing attacks can threaten RSA security by exploiting the time variations in the decryption process to infer sensitive information about the private key. An adversary may observe the decryption duration to deduce bit patterns of the key. A common countermeasure is using constant exponentiation time, which ensures that all decryption operations take the same amount of time, thereby removing time-based clues from which an adversary might deduce information .

To expedite RSA cryptographic operations, the Chinese Remainder Theorem (CRT) is utilized. It allows computations like decryption to be performed separately in smaller modular fields defined by the RSA primes, which are subsequently combined. This reduces the computational load significantly, making the operation approximately four times faster than conventional exponentiation directly with modulus n. This optimization takes advantage of the properties of moduli in computational efficiency .

Public key cryptosystems address the challenges of key distribution and digital signatures in symmetric encryption. Key distribution under symmetric encryption requires communicants to already share a secret key, potentially leading to issues of trust in a Key Distribution Center. Public key cryptosystems eliminate the need for such a trusted intermediary by using asymmetric key pairs. Additionally, digital signatures provide a mechanism to verify message authenticity, ensuring that a message truly originates from the claimed sender without requiring a shared secret .

For secure key generation in RSA, users must generate two large random prime numbers, ensuring they are not easily deduced from the modulus n=p*q. The numbers should differ by a few digits to prevent easy factorization. Additionally, both (p-1) and (q-1) should have large prime factors to resist attacks. The public exponent e should be chosen such that it is relatively prime to φ(n) and appropriately sized to prevent simple attacks, whereas d must be kept large enough to avoid vulnerabilities to brute-force attacks or other cryptanalysis .

You might also like