[go: up one dir, main page]
Scribd
Upload
22 views3 pages

Elgama Code

Crypto code

Uploaded by

subir paul
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
22 views3 pages

Elgama Code

Crypto code

Uploaded by

subir paul
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 3

#include <stdio.

h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>

// GCD function to ensure key is valid


int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}

// Generate a key that is coprime with q


int gen_key(int q) {
int key = rand() % (q - 1) + 1; // key is between 1 and q-1
while (gcd(q, key) != 1) {
key = rand() % (q - 1) + 1;
}
return key;
}

// Efficient power function to compute (a^b) % c


long long power(long long a, long long b, long long c) {
long long result = 1;
a = a % c;
while (b > 0) {
if (b % 2 == 1) {
result = (result * a) % c;
}
b = b / 2;
a = (a * a) % c;
}
return result;
}

// Extended Euclidean Algorithm to find modular inverse


int mod_inverse(int a, int m) {
int m0 = m, t, q;
int x0 = 0, x1 = 1;
if (m == 1) return 0;
while (a > 1) {
q = a / m;
t = m;
m = a % m, a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0)
x1 += m0;
return x1;
}

// Encryption function (Alice)


void encrypt(char* msg, int q, int h, int g, long long* en_msg, int size, long
long* p_out) {
int k = gen_key(q);
long long s = power(h, k, q); // h^k % q (shared secret)
long long p = power(g, k, q); // g^k % q
*p_out = p; // Store p for decryption

for (int i = 0; i < size; i++) {


en_msg[i] = (s * msg[i]) % q; // Encryption formula
}
}

// Decryption function (Bob)


void decrypt(long long* en_msg, long long p, int key, int q, char* dr_msg, int
size) {
long long h = power(p, key, q); // h = p^x % q = g^(ak)
long long h_inv = mod_inverse(h, q); // Modular inverse of h

for (int i = 0; i < size; i++) {


dr_msg[i] = (en_msg[i] * h_inv) % q;
}
dr_msg[size] = '\0'; // Null-terminate the decrypted string
}

// Eavesdropping function (Eve)


void eavesdrop(long long* en_msg, long long p, int q, char* dr_msg, int size) {
// Eve brute-forces the private key
for (int key_guess = 1; key_guess < q; key_guess++) {
long long h = power(p, key_guess, q);
long long h_inv = mod_inverse(h, q);

for (int i = 0; i < size; i++) {


dr_msg[i] = (en_msg[i] * h_inv) % q;
}
dr_msg[size] = '\0';

// Display the guess


printf("Eve's guess with key %d: %s\n", key_guess, dr_msg);
}
}

int main() {
srand(time(0));
char msg[100];
printf("Enter the message: ");
fgets(msg, sizeof(msg), stdin);
msg[strcspn(msg, "\n")] = '\0'; // Remove newline character

printf("Original Message: %s\n", msg);

int q = 1024; // Smaller value of q for simplicity and breaking


int g = rand() % (q - 2) + 2;
int key = gen_key(q);
long long h = power(g, key, q);

printf("q used: %d\n", q);


printf("g used: %d\n", g);
printf("g^a used: %lld\n", h);

int size = strlen(msg);


long long en_msg[size]; // Use long long to avoid overflow
long long p; // To hold g^k from encryption
encrypt(msg, q, h, g, en_msg, size, &p);
printf("Encrypted Message: ");
for (int i = 0; i < size; i++) {
printf("%lld ", en_msg[i]);
}
printf("\n");

// Bob decrypts the message


char dr_msg[size + 1]; // Add 1 for null terminator
decrypt(en_msg, p, key, q, dr_msg, size);
printf("Bob's Decrypted Message: %s\n", dr_msg);

// Eve tries to eavesdrop and decrypt


printf("Eve tries to decrypt:\n");
eavesdrop(en_msg, p, q, dr_msg, size);

return 0;
}

You might also like