////////////////////////////////////////////////////////////////// //////**************RSA Cryptosystem //////**************Author: Petros Simidyan ////***************** #include #include #include typedef unsigned int uint; constexpr uint gCD(uint a, uint b) { if (b == 0) return a; else return gCD(b, a%b); } const uint extEuclid(uint x, uint y, int * d, int * k) { uint sa = 1, ta = 0, sb = 0, tb = 1, q, tempA, tempB; int a = x, b = y; while (b > 0) { q = a / b; tempA = a; a = b; b = tempA - q * b; tempA = sa; tempB = ta; sa = sb; ta = tb; sb = tempA - q * sb; tb = tempB - q * tb; } *d = sa; *k = ta; return a; } //function counts (base^exp)%rem in O(ld(n)) time uint fastExp(int base, int exp, uint rem) { while (base < 0) base += rem; //if the exponent is negative we should set the //modular multiplicative inverse of base to base and exp = -exp //e.g. we have to count 2^(-123)%3=(2^-1%3)^123%3=-1^123%3 //because -1 is modular multiplicative inverse of 2 with 2*(-1)%3=1 if (exp < 0) { int temp = 0; extEuclid(base, rem, &base, &temp); return fastExp(base, -1 * exp, rem); } uint res = 1; base = base % rem; while (exp > 0) { if (exp&1) res = (res*base) % rem; exp = exp >> 1; base = (base*base) % rem; } return res; } const uint prepareKey(int& e, int&d) { using namespace std; //First we have to choose two different prime numbers p and q uint p = 67, q = 193; //now we count N = p*q uint rem = p * q; //now we count euler = (p-1)(q-1) uint euler = (p - 1)*(q - 1); //after that we count the public key e, //with 1