Question

Q2.1 [RSA Signature Scheme] (Marks: 2) Suppose Bob (the sender) wants to send a message m=123456 to Alice (the receiver). However, before sending the message he would like to sign the message. When Alice receives the signed message, she would like to verify that the message is indeed from Bob. To facilitate signing and verification Bob generates public and private keys using RSA encryption algorithm and sends the public key to Alice. Bob uses parameter p = 5563 and q = 3821, and chooses a suitable public key parameter e=9623. How would Bob sign message m=123456? How would Alice verify the signed message from Bob? [Hints: Refer to the lecture-6 and tutorial-6. You do not need to generate hash of the message m.]

Q2.2 [ElGamal Signature Scheme] (Marks: 2) Suppose Bob (the sender) wants to send a message m=4567 to Alice (the receiver). However, before sending the message he would like sign the message. When Alice receives the signed message, she would like to verify that the message is indeed from Bob. To facilitate signing and verification Bob generates public and private keys using ElGamal encryption algorithm and sends the public key to Alice. Bob chooses p= 7331, g=3411, x=41. How would Bob sign message m=4567? How would Alice verify the signed message from Bob? [Hints: Refer to the lecture-6 and tutorial-6. You do not need to generate hash of the message m.]

Answer 1

Question 1:

Prime factors

The security of RSA is based on the fact that it is easy to calculate the product n of two large primes p and q. However, it is very difficult to determine only from the product n the two primes that yield the product. This decomposition is also called the factorization of n.

As a starting point for RSA choose two primes p and q.

1st prime p 5563

2nd prime q 3821

For the algorithm to work, the two primes must be different.

For demonstration we start with small primes. To make the factorization difficult, the primes must be much larger. Currently, values of n with several thousand binary digits are used for secure communication.

n = p × q

21256223 (25 Bit)

Public key

The product n is also called module in the RSA method. The public key consists of the module n and an exponent e.

e 9623

This e may even be pre-selected and the same for all participants.

Secret key

RSA uses the Euler φ function of n to calculate the secret key. This is defined as

φ(n) = (p − 1) × (q − 1)

21246840

Here it is used that p and q are different. Otherwise, the φ function would calculate differently.

It is important for RSA that the value of the φ function is coprime to e (the largest common divisor must be 1).

gcd(e, φ(n))

1

To determine the value of φ(n), it is not enough to know n. Only with the knowledge of p and q we can efficiently determine φ(n).

The secret key also consists of n and a d with the property that e × d is a multiple of φ(n) plus one.

Expressed in formulas, the following must apply:

e × d = 1 (mod φ(n))

In this case, the mod expression means equality with regard to a residual class. It is x = y (mod z) if and only if there is an integer a with x − y = z × a.

For the chosen values of p, q, and e, we get d as:

d

16477727

This d can always be determined (if e was chosen with the restriction described above)—for example with the extended Euclidean algorithm.

Encryption and decryption

Internally, this method works only with numbers (no text), which are between 0 and n.

Encrypting a message m (number) with the public key (n, e) is calculated:

m' := m^e (mod n)

Decrypting with the private key (n, d) is done analogously with

m'' := m'^d (mod n).

This is

m'' = m^{e × d} (mod n).

RSA now exploits the property that

x^a = x^b (mod n)

if

a = b (mod φ(n))

As e and d were chosen appropriately, it is

m'' = m.

The order does not matter. You could also first raise a message with the private key, and then power up the result with the public key—this is what you use with RSA signatures.

Messages

In the following two text boxes, you can see how the encryption and decryption works for concrete input (numbers).

plaintext 123456

ciphertext 20144723

Question 2:

Alice's Public Key
p: 7331 g: 3411 h: 6162

h is calculated as h = g^x mod p

Private key for encryption (r): 155

Message: 4567

Bob's encrypted message
c1: 4347, c2: 2271

Bob's decrypted message: 4567