Question

4. Supppose Alice and Bob are using the prime p = 1451 and the base g = 2 for an ElGamal cryptosystem. (a) Alice chooses a = 753 as her private key. What is the value of her public key A? (b) Now suppose Bob chooses b = 500 as his private key, and thus his public key is 464 mod 1451. Alice encrypts the message m = 284 using the ephemeral key k=512. What is the ciphertext Alice sends to Bob? (c) Alice chooses a new private key a = 451 with associated public key A = 609 mod 1373. Bob encrypts a message and sends the ciphertext (C1, C2) = (332,869). What is the message?

all infor given

Answer 1

The given below program will help you to find the calculations :

(a^b) % MOD = ((a % MOD)^b) % MOD

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int power(int a,int b)
{
    if(b==1)
        return a;
    long int subAns = power(a,b/2)%1451;
    if(b&1)
        return (((subAns*subAns)%1451)*a)%1451;
    return (subAns*subAns)%1451;
}
int main()
{
        int ans = (284*power(500,512))%1451;
        cout<<ans;
        return 0;
}

Step1: Key Creation:

Chooses private key 1 ≤ a ≤ p − 1.

Computes A = g^a(mod p).

Publishes the public key A.

So we have p = 1451.

g = 2 and a = 753.

On calculating this using the above program , we got A = 995 . So private Key for Alice will be 995.

Part B.

i) Chooses plaintext m.

ii) Chooses random ephemeral key k.

iii) Uses BOB’s public key b to compute c1 = g^k(mod p) and c2 = m*b^k (mod p).

iv) Sends ciphertext (c1, c2) to BOB.

For C1 = g^k mod p

2⁵¹² mod 1451 .

we got C1 = 1185

and C2 = 284*500⁵¹² mod 1451 = 1411 .

So , the Cipher Text that will be sent to bob ( 1185 , 1411) .

Step 3.

i ) Calcuate (C₁^a)^-1 x C₂ (mod p )

ii) C1 = 332 , C2 = 869 , a = 451 , p = 1451

iii) 869*(332⁴⁵¹)^-1 mod 1451 . is the required expression.

iv) First Calculate ,  (332⁴⁵¹)^-1 mod 1451 , ............ eq (i)

it can be written as A * 332⁴⁵¹ mod 1451 = 1

v) So, the value of A for which the LHS = RHS will satisfy is the required mod for eqn i.

So for A = 1088 it is satisfied .

vii) Now , calculate 869*1088 mod 1451 which 871.

So the Message will be 871 .

below the is code for finding A.

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int power(int a,int b)
{
    if(b==1)
        return a;
    long int subAns = power(a,b/2)%1451;
    if(b&1)
        return (((subAns*subAns)%1451)*a)%1451;
    return (subAns*subAns)%1451;
}
int main()
{
        for(int i = 1 ; i<=2000 ; i++){

        int ans = (i*power(332,451))%1451;

        if(ans==1)
        {

                cout<<i ;
                break ; 
        }

}
        
        return 0;
}