RSA

Может запоздало, но зато то, что нужно:

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

struct rsa_public_key {
    int e, m;
};

struct rsa_private_key {
    int d, m;
};

// Calculates greatest common divisor of two positive integers
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// Solves Diophant's equation a*x + b*y = 1
void SolveDiophant(int a, int b, int &x, int &y)
{
    int a11=1, a12=0, a21=0, a22=1;
    while (1) {
        int r = a % b;
        if (r == 0) {
            x = a12;
            y = a22;
            return;
            }
        else {
            int q = a/b;
            int save12 = a12;
            int save22 = a22;
            a12 = a11-save12*q;
            a22 = a21-save22*q;
            a11 = save12;
            a21 = save22;
            a = b;
            b = r;
            }
        }
}

// Find number y such that (x*y)%m == 1
int FindInvert(int x, int m)
{
    int y, sux;
    SolveDiophant(x, m, y, sux);
    while (y < 0)
        y += m;
    return y;
}

// Calculate (a in power b)%m
int Power(int a, int b, int m)
{
    a %= m;
    int res = a;
    for (int i = 1; i < b; i++)
        res = (res * a) % m;
    return res;
}

// Generate RSA key pair. p and q must be prime numbers and conditions
// GCD(e, p-1) = GCD(e, q-1) = 1
// must be satisfied
void GenKeyPair(int p, int q, int e, rsa_public_key &pub,
  rsa_private_key &pri)
{
    if ((gcd(e, p-1) != 1) || (gcd(e, q-1) != 1)) {
        printf("GenerateKeyPair: Invalid parameters\n");
        exit(1);
        }
    pub.m = p*q;
    pub.e = e;
    pri.m = p*q;
    // Eulers function phi(m)
    int phi_m = (p-1)*(q-1);
    pri.d = FindInvert(e, phi_m);
}

// Important! Must be source < key.m
int Encode(int source, rsa_public_key &key)
{
    return Power(source, key.e, key.m);
}

int Decode(int source, rsa_private_key &key)
{
    return Power(source, key.d, key.m);
}

int main ()
{
    // Achtung: (p*q)^2 must fit into int
    int p = 71;
    int q = 73;
    int e = 59;
    rsa_public_key pub_key;
    rsa_private_key pri_key;
    GenKeyPair(p, q, e, pub_key, pri_key);
    srand(time(NULL));
    int source = rand() % pub_key.m;
    int enc = Encode(source, pub_key);
    int dec = Decode(enc, pri_key);
    if (dec != source)
        printf("There was a bug\n");
    else
        printf("Source: %d, encoded: %d, decoded: %d\n",
          source, enc, dec);
}

Сам сейчас писал, но вроде работает.