rsa.c

#include <math.h>
#include <stdio.h>

int primo(int a) {
  int i;
  int r = (int)sqrt(a);

  for (i = 2; i <= r; i++) {
    if (a % i == 0) {
      return 0; // Non primo
    }
  }
  return 1; // Primo
}

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

// Dati tre numeri, calcola (msg**exponent) % n.
// Teoria, in inglese: https://en.wikipedia.org/wiki/Modular_exponentiation
int powmod(long msg, int exponent, int n) {
  int res = 1;
  while (exponent > 0) {
    // Se exponent è dispari, moltiplico msg con res
    if (exponent % 2 != 0)
      res = (res * msg) % n;

    // exponent è pari ora
    exponent = exponent / 2;
    msg = (msg * msg) % n;
  }
  return res;
}

int main() {
  int p, q;    // I due numeri primi
  int n;       // n = p * q;
  int z;       // Funzione di Eulero
  int pub = 1; // Esponente pubblico

  long msg_chiaro, msg_criptato, msg_decriptato;

  do {
    printf("Inserisci numero primo 1: ");
    scanf("%d", &p);
  } while (!primo(p));

  do {
    printf("Inserisci numero primo 2: ");
    scanf("%d", &q);
  } while (!primo(q));

  n = p * q;
  z = (p - 1) * (q - 1);

  do {
    pub++;
  } while (!(mcd(z, pub) == 1));

  int priv = pub + 1;
  do {
    priv++;
  } while ((pub * priv % z) != 1);

  printf("La chiave pubblica è (%d, %d)\n", pub, n);
  printf("La chiave private è (%d, %d)\n", priv, n);

  do {
    printf("Inserisci un numero da crifrare: ");
    scanf("%ld", &msg_chiaro);
  } while (msg_chiaro > n);

  msg_criptato = powmod(msg_chiaro, pub, n);
  printf("Il messaggio cifrato è: %ld\n", msg_criptato);

  msg_decriptato = powmod(msg_criptato, priv, n);
  printf("Il numero decifrato è: %ld\n", msg_decriptato);
}