BITS F463

CRYPTOGRAPHY
2nd sem 2024-2025
Lecture 12
Principles Of Public-Key
Cryptosystems
❖ Public-Key Cryptosystems
❖ Applications for Public-Key Cryptosystems
❖ Requirements for Public-Key Cryptography
❖ Public-Key Cryptanalysis

❖ The RSA Algorithm

❖ Description of the Algorithm
❖ Computational Aspects
❖ The Security of RSA

BITS Pilani, Hyderabad Campus

 Public-Key Cryptography
• probably most significant advance in the 3000
year history of cryptography
• uses two keys – a public & a private key
• asymmetric since parties are not equal
• uses clever application of number theoretic
concepts to function
• complements rather than replaces private key
crypto

BITS Pilani, Hyderabad Campus

Public-Key Cryptography

BITS Pilani, Hyderabad Campus

Encryption with public key
(for message secrecy)

BITS Pilani, Hyderabad Campus

Encryption with private key
(for authentication)

BITS Pilani, Hyderabad Campus

(1)Public-Key Cryptosystems - secrecy
Attack scenario

BITS Pilani, Hyderabad Campus

(2) Public-Key Cryptosystems –
authentication
Attack scenario

BITS Pilani, Hyderabad Campus

(3) Public-Key Cryptosystems
– authentication and secrecy

BITS Pilani, Hyderabad Campus

Applications of Public-Key Systems
• We can classify the uses into 3 categories:
– encryption/decryption (provide secrecy)
– digital signatures (provide authentication)
– key exchange (of session keys)
• some algorithms are suitable for all uses,
others are specific to one

BITS Pilani, Hyderabad Campus

 Security of Public Key Schemes
• like private key schemes brute force exhaustive
search attack is always theoretically possible; but
keys used are too large (>512bits)
• security relies on a large enough difference in
difficulty between easy (en/decrypt) and hard
(cryptanalyse) problems
• requires the use of very large numbers; hence it is
slow compared to private key schemes
• We can't compare key sizes - a 64-bit private key scheme has
very roughly similar security to a 512-bit RSA - both could be
broken given sufficient resources

BITS Pilani, Hyderabad Campus

Introduction on RSA

❖ RSA is the best known, and by far the most widely used
general public key encryption algorithm, and was first
published by Rivest, Shamir & Adleman of MIT in 1978
[RIVE78]
❖ RSA has reigned supreme as the most widely accepted and
implemented general-purpose approach to public-key
encryption
❖ It is based on exponentiation in a finite (Galois) field over
integers modulo a prime, using large integers (eg. 1024
bits); Its security is due to the cost of factoring large
numbers

BITS Pilani, Hyderabad Campus

RSA description

❖ Plaintext is encrypted in blocks, with each block having a

binary value less than some number n (block size must be less
than or equal to log2(n) + 1; in practice, the block size is i bits,
where 2i < n ≤ 2i+1

Encryption and decryption

6 real life examples of use of RSA

BITS Pilani, Hyderabad Campus

 RSA Key Setup
• each user generates a public/private key pair by:
• selecting two large primes at random: p, q
• computing their system modulus n = p.q
– note ø(n)=(p-1)(q-1)
• selecting at random the encryption component e
• where 1<e<ø(n), gcd(e,ø(n))=1
• solve the following equation to find decryption
component d
– e.d=1 mod ø(n) and 0≤d≤n
• publish their public encryption key: PU={e,n}
• keep secret the private decryption key: PR={d,n}
BITS Pilani, Hyderabad Campus
 RSA Use
The actual RSA encryption and decryption computations are each simply a single
exponentiation mod (n). The message must be smaller than the modulus. The “magic”
is in the choice of the exponents which makes the system work.

• to encrypt a message M, the sender:

– obtains public key of recipient PU={e,n}
– computes: C = Me mod n, where 0≤M<n
• to decrypt the ciphertext C, the receipient:
– uses their private key PR={d,n}
– computes: M = Cd mod n
• note that the message M must be smaller
than the modulus n (block if needed)
BITS Pilani, Hyderabad Campus
 Why RSA Works
• because of Euler's Theorem:
❖aø(n)mod n = 1 where gcd(a,n)=1
• in RSA we have:
❖n=p.q
❖ø(n)=(p-1)(q-1)
❖carefully chose e & d to be inverses mod ø(n)
❖hence e.d=1+k.ø(n) for some k
• hence :
Cd = Me.d = M1+k.ø(n) = M1.(Mø(n))k
= M1.(1)k = M1 = M mod n

BITS Pilani, Hyderabad Campus

 RSA Example - Key Setup
1. Select primes: p=17 & q=11
2. Compute n = pq =17 x 11=187
3. Compute ø(n)=(p–1)(q-1)=16 x 10=160
4. Select e: gcd(e,160)=1; choose e=7
5. Determine d: de=1 mod 160 and d < 160
Value is d=23 since 23x7=161= 10x160+1
6. Publish public key PU={7,187}
7. Keep secret private key PR={23,187}

BITS Pilani, Hyderabad Campus

 RSA Example - En/Decryption
• sample RSA encryption/decryption is:
• given message M = 88 (nb. 88<187)
• encryption:
C = 887 mod 187 = 11
• decryption:
M = 1123 mod 187 = 88

BITS Pilani, Hyderabad Campus

Encrypt “hello” using RSA
To encrypt "hello" using RSA, convert the message to a numerical representation (e.g., ASCII), then apply the public key's
exponent and modulus to encrypt it, resulting in a ciphertext.
Here's a breakdown of the process:
1. Key Generation:
Choose two large prime numbers, p and q: For simplicity in this example, let's use p = 61 and q = 53.
Calculate the modulus n: n = p * q (In our example, n = 61 * 53 = 3233).
Calculate the totient phi(n): phi(n) = (p-1) * (q-1) (In our example, phi(n) = (61-1) * (53-1) = 60 * 52 = 3120).
Choose a public exponent e: e must be coprime with phi(n) (meaning their greatest common divisor is 1) and typically a small
prime number, like 17.
Calculate the private exponent d: d is the modular inverse of e modulo phi(n), meaning (e * d) mod phi(n) = 1. In our example, if
e=17, then d = 2753.
Public Key: The public key consists of (e, n) (in our example, (17, 3233)).
Private Key: The private key consists of (d, n) (in our example, (2753, 3233)).
2. Encryption:
Convert the message "hello" to its ASCII representation: 104 101 108 108 111.
Raise each ASCII value to the power of e (17) and take the modulus n (3233):
104^17 mod 3233 = 2790
101^17 mod 3233 = 3071
108^17 mod 3233 = 2276
108^17 mod 3233 = 2276
111^17 mod 3233 = 1217.
The ciphertext is: 2790 3071 2276 2276 1217.
3. Decryption:
Take each number in the ciphertext and raise it to the power of d (2753) and take the modulus n (3233):
2790^2753 mod 3233 = 104
3071^2753 mod 3233 = 101
2276^2753 mod 3233 = 108
2276^2753 mod 3233 = 108
1217^2753 mod 3233 = 111.
Convert the ASCII values back to characters: 104 101 108 108 111 becomes "hello".
BITS Pilani, Hyderabad Campus
 Exponentiation
“Square and Multiply Algorithm”

Function exp-by-squaring(x, n)
if n < 0 then return exp-by-squaring(1 / x, -n);
else if n = 0 then return 1;
else if n = 1 then return x ;
else if n is even then return exp-by-squaring(x * x, n / 2);
else if n is odd then return x * exp-by-squaring(x * x, (n - 1) / 2).

BITS Pilani, Hyderabad Campus

Speeding up RSA operation
❖ To speed up the operation of the RSA algorithm using the public key, we
can choose to use a small value of e (but not too small, since it is then
vulnerable to attack)
❖ We must then ensure any p or q chosen are relatively prime to the fixed e
(and reject and find another if not), for the system to work
❖ To speed up the operation of the RSA algorithm using the private key, we
can use the Chinese Remainder Theorem (CRT) to compute mod p
& q separately, and then combine results to get the desired answer.
This is approximately 4 times faster than calculating “C^d mod n”
directly
❖ Only the owner of the private key details (who knows the values of
p & q) can do this, but of course that is exactly where help is
needed, since if e is small then d will likely be large!

BITS Pilani, Hyderabad Campus

 Efficient Encryption
• encryption uses exponentiation to power e
• hence if e small, this will be faster
– often choose e=65537 (216-1)
– also see choices of e=3 or e=17
• but if e too small (eg e=3) the attacker can
carry out an attack
– using Chinese remainder theorem & 3 messages
with different modulii
• if e is fixed, we must ensure
gcd(e,ø(n))=1
– ie reject any p or q not relatively prime to e
BITS Pilani, Hyderabad Campus
 Efficient Decryption
• decryption uses exponentiation to power d
• We can use the Chinese Remainder Theorem
(CRT) to compute mod p & q separately. then
combine to get the desired answer
– approx 4 times faster than doing it directly
• only owner of private key who knows values
of p & q can use this technique

BITS Pilani, Hyderabad Campus

Attacks on RSA

❖ 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

BITS Pilani, Hyderabad Campus

Mathematical attacks on RSA

❖ We can identify three approaches to attacking RSA

mathematically, as shown. Mathematicians currently believe
that all are equivalent to factoring
❖ The best current algorithm is the “Lattice Sieve” (LS),
which replaced the “Generalized Number Field Sieve”
(GNFS), which replaced the “Quadratic Sieve”(QS).
❖ We have to assume computers will continue to get
faster, and that better factoring algorithms may yet be
found
❖ Numbers of size 1024-2048 bits look reasonable at
present, provided the factors meet other constraints

BITS Pilani, Hyderabad Campus

 Factoring Problem
➢ mathematical approach takes 3 forms:
➢ factor n=p.q, hence compute ø(n) and then d
➢ determine ø(n) directly and compute d
➢ find d directly
➢ currently all are treated equivalent to factoring
➢ We have seen slow improvements over the years
➢ as of May-05 best is 200 decimal digits (663) bit with LS
➢ biggest improvement comes from improved algorithm
➢ QS to GNFS to LS
➢ currently assume 1024-2048 bit RSA is secure
➢ ensure p, q of similar size and matching other constraints

BITS Pilani, Hyderabad Campus

New category of attacks on
RSA: timing attack

❖ A new category of attacks was developed by Paul Kocher in mid-

1990’s, 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 ciphertext only 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
❖ Although 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.

BITS Pilani, Hyderabad Campus

 Chosen Ciphertext Attacks
➢ The RSA algorithm is vulnerable to a chosen ciphertext attack
(CCA)
➢ CCA is defined as an attack in which the 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
➢ We can counter simple attacks with random pad of plaintext
➢ More sophisticated variants need to modify the plaintext using a
procedure known as optimal asymmetric encryption padding
(OAEP)

BITS Pilani, Hyderabad Campus