Question

Q3. Privacy-Preserving Computation using Public-Key Cryptography (Marks: 3+5 = 8) Say, Alice wants to multiply two numbers (M1 and M2) and send the result to Bob. That is, Alice is the sender and Bob is the receiver. However, Alice does not have the computation power to multiply two numbers. Therefore, she decides to send both numbers to a cloud server. Though the cloud server has the computation power, it cannot be trusted. As a result, Alice relies on the Homomorphic properties of Public-Key Cryptography Schemes. Alice encrypts both numbers before sending them to the cloud. The cloud performs multiplication on encrypted numbers and sends the encrypted result to Bob. Assume that Alice considers the last digit of your student number as the first number (M1) and the second last digit as the second number (M2). For example, if your student number is “S123456”, the numbers are: M1 = 6 and M2 = 5. Bob generates public and private keys and sends the public key to Alice for the encryption and to cloud for the homomorphic multiplication. Answer the following questions:

a) Consider that Alice and Bob are using RSA Public-Key Cryptography Algorithm. With proper description, show detailed steps of key generation, encryption, homomorphic multiplication, and decryption process. Bob uses parameter p = 79 and q = 83. i. Choose a small public key parameter (e = 19) on behalf of Bob and show detailed steps to compute Bob’s public-key and private-key? ii. How would Alice encrypt numbers M1= and M2=? What would Alice send to the cloud? iii. How would the cloud perform homomorphic multiplication? What encrypted result would the cloud send to Bob? iv. How would Bob decrypt the encrypted result?

b) Consider that Alice and Bob are using ElGamal Public-Key Cryptography Algorithm. Show detailed steps of key generation, encryption, homomorphic multiplication, and decryption process. Bob uses parameter p = 5081, g = 93, and x = 106. i. Show detailed steps to compute Bob’s public-key? ii. Alice chooses two random numbers: r1 = 79 and r2 = 94. How would Alice encrypt numbers M1= and M2=? What would Alice send to the cloud? iii. How would the cloud perform homomorphic multiplication? What encrypted result would the cloud send to Bob? iv. How would Bob decrypt the encrypted result?

Answer 1

(a) 1st problem

Rivest-shamir-Adleman algoritm ( RSA ), is an asymmetric cryptographic algorithm.

RSA has two types of keys...

-> Private key : It's a secret key

-> Public key : can be known to all

If a user X is used public key for encryption we have to use the private key of same user X for decryption

To generate key...

-> Select 2 large prime numbers P and Q

-> Then calculate n=P*Q

-> Calculate Φ(n)=(p-1)*(q-1)

-> Choose value of e.Note that e must be greater that 1 and less than Φ(n) ie.., 1<e< Φ(n) and also gcd( Φ(n) ,e ) must be equal 1

-> Calculate d=1/e mod( Φ(n) ),ed=1mod Φ(n)

-> Public key={e,n}

-> Private key={d,n}

Solution...

P=79 and Q=83,e=19

Calculate n=p*q

n= 79*83

n=6557

Calucate Φ(n)=(p-1)*(q-1)

Φ(n)=78*82

Φ(n)=6396

Given e=19 ie.., 1<19<6396 gcd(6396,1)=1

Calculate d.... To calulate d*19 mod( Φ(n))=1,

d=1/e mod Φ(n), 1+k( Φ(n))/n=d ,take values of k=1,2,3

d*e= 1 mod Φ(n) we get k=11 ie.. -> 1+11*6396/19=3703

d*19=1 mod 6396

d*19 mod 6396=1

(3703*19)mod 6396=1

Therefore the value of d=3703

Public key={19,6557}

Private key={3703,6557}

______________________________________________________________

(b) 2nd problem

Encryption by alice

Give M1=6 and M2=5

Ie..,M1 is(last digit of student number) and M2 (second last digit of student number)

The equation to encrypt is C1 = M1^e mod n

we know that M1 is 6 and e=19

C1=6^19 mod 6557

by taking modulus we get the Value as C1=522(Calculate using scientific calculator )

C=M2^e mod

M2=5

C1=5^19 mod 6557

C2= 1900

Alice sends the encrypted messages C1=522 and C2=1900

M2=5