Untitled

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 16 // Number of bits for the plaintext

// Function to calculate the greatest common divisor
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Key generation function
void key_generation(int* public_key, int* private_key, int* m, int* w) {
    int superincreasing_sequence[N];
    int sum = 0;

    // Generate superincreasing sequence
    for (int i = 0; i < N; i++) {
        int value = rand() % 20 + sum + 1;
        superincreasing_sequence[i] = value;
        sum += value;
    }

    *m = sum + (rand() % 100 + 1); // m > sum(superincreasing_sequence)

    do {
        *w = rand() % *m;
    } while (gcd(*w, *m) != 1); // w and m must be coprime

    // Generate public key
    for (int i = 0; i < N; i++) {
        public_key[i] = (superincreasing_sequence[i] * *w) % *m;
    }

    // Store private key
    for (int i = 0; i < N; i++) {
        private_key[i] = superincreasing_sequence[i];
    }
}

int encrypt(int* public_key, int plaintext) {
    int ciphertext = 0;
    for (int i = 0; i < N; i++) {
        int bit = (plaintext >> i) & 1;
        ciphertext += bit * public_key[i];
    }
    return ciphertext;
}

int mod_inverse(int w, int m) {
    for (int i = 1; i < m; i++) {
        if ((w * i) % m == 1) {
            return i;
        }
    }
    return -1;
}

int decrypt(int* private_key, int m, int w, int ciphertext) {
    int w_inverse = mod_inverse(w, m);
    int sum = (ciphertext * w_inverse) % m;
    int plaintext = 0;

    // Solve the subset sum problem
    for (int i = N - 1; i >= 0; i--) {
        if (sum >= private_key[i]) {
            sum -= private_key[i];
            plaintext |= (1 << i);
        }
    }
    return plaintext;
}

int main() {
    srand(time(NULL));
    
    int public_key[N], private_key[N], m, w;
    
    key_generation(public_key, private_key, &m, &w);
    
    int plaintext = 21845; // Example plaintext (binary: 0101010101010101)
    int ciphertext = encrypt(public_key, plaintext);
    
    printf("Plaintext: %d\n", plaintext);
    printf("Ciphertext: %d\n", ciphertext);
    
    int decrypted_plaintext = decrypt(private_key, m, w, ciphertext);
    printf("Decrypted Plaintext: %d\n", decrypted_plaintext);
    
    return 0;
}