Scribd
Upload
4 views4 pages

Unit-3.3 RSA Examples

The document provides examples of RSA encryption and decryption, detailing the key generation, encryption, and decryption processes for messages M = 9 and M = 10. It also explains modular exponentiation using the square-and-multiply method and discusses timing attacks that exploit variations in computation time during RSA operations. Countermeasures against these attacks are suggested, including constant time algorithms and adding random delays.

Uploaded by

Karishma Mehta
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
4 views4 pages

Unit-3.3 RSA Examples

The document provides examples of RSA encryption and decryption, detailing the key generation, encryption, and decryption processes for messages M = 9 and M = 10. It also explains modular exponentiation using the square-and-multiply method and discusses timing attacks that exploit variations in computation time during RSA operations. Countermeasures against these attacks are suggested, including constant time algorithms and adding random delays.

Uploaded by

Karishma Mehta
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

Example 1: Encrypt and Decrypt a Message

Use RSA to encrypt and decrypt the message (M = 9) using: (p = 5),


(q = 13), Choose (e = 7)

Solution:

Step 1: Key Generation

 n= p×q =5×13=65
 ϕ(n)= (p−1)(q−1) = 4×12= 48
 e=7, check that gcd(7,48) = 1
Find (d) such that d X e = 1 mod 48

Try values:

 d = 7 : ( 7 X 7 = 49 ≡ 1 mod 48 )

So:
 Public key: (e = 7, n = 65)
 Private key: (d = 7, n = 65)

Step 2: Encryption

 C = Me mod n = 97 mod 65
 97 = 4782969
 4782969 mod 65 = 9

Encrypted message: C = 9

Step 3: Decryption

 M = Cd mod n = 97 mod 65 = 9

Decrypted message: M = 9
Example 2: Encrypt and Decrypt a Different Message

Question: Encrypt and decrypt ( M = 10 ) using: ( p = 7 ), ( q = 17 )


Choose ( e = 5 )

Solution:

Step 1: Key Generation

 n = 7 X 17 = 119
 ϕ(n) = (p−1)(q−1) = (7 - 1)(17 - 1) = 6 X 16 = 96
 e = 5, check gcd(5, 96) = 1
Find d such that d X 5 ≡ 1 mod 96

Try:
 d = 77 : ( 77 X 5 = 385 ≡ 1 mod 96 )

So:
 Public key: (e = 5, n = 119)
 Private key: (d = 77, n = 119)

Step 2: Encryption

 C = 105 mod 119 = 100000 mod 119


 100000 / 119 = 840 and remainder 40

 Encrypted message: C = 40

Step 3: Decryption

 M = 4077 mod 119

This is a large exponent, so we use modular exponentiation:


 Using fast exponentiation or a calculator: 4077 mod 119 = 10

 Decrypted message: M = 10
Step-by-Step: Modular Exponentiation (Square-and-Multiply)

We want to compute 4077mod 119

Step 1: Convert exponent to binary

 77 in binary is: 1001101


which means: 77=26+23+22+20

Step 2: Initialize

 Result = 1
 Base = 40

Step 3: Process each bit from left to right

We loop through each bit of the exponent and do:

 Square the current result


 If the bit is 1, multiply by base
 Always take modulo n=119

Let’s go through it:

Final result: 4077 mod 119 = 10


RSA: timing attacks—a type of side-channel attack that exploits the time
taken during exponentiation to infer secret information.

What’s Happening in RSA Exponentiation?

RSA encryption and decryption rely on modular exponentiation, which involves


computing something like:

C=Me mod n or M=Cd mod n

Depending on the value of the exponent (especially the secret key d), the time
taken to perform this operation can vary—particularly if the implementation
uses algorithms like square-and-multiply, where the number of multiplications
depends on the number of 1s in the binary representation of the exponent.

How Attackers Exploit This:


 By measuring how long the RSA operation takes for different inputs,
attackers can statistically analyse the timing data.
 Over many observations, they can reconstruct bits of the private key d,
especially if the system leaks consistent timing differences.
 This is known as a timing attack, and it doesn’t break RSA mathematically—
it exploits implementation flaws.

Counter measures:
 use constant exponentiation time
 add random delays
 blind values used in calculations

You might also like