Take a look at rsa.h, testing.h, testing.cpp, testRSA.cpp. Then Implement all the functions listed in it in rsa.cpp.

=====================

rsa.h

#ifndef RSA_H

#define RSA_H

#include

// calculate N

int computeN(int p, int q);

// calcluate

int computePhi(int p, int q);

// computes x mod m

int powmod(int x, int y, int m);

// computes the greatest common divisor of x and y

int gcd(int x, int y);

// find an integer e such that gcd(e, ) = 1

int computeE(int phi);

// returns a pair (a, b) such that ax + by = gcd(a, b)

std::pair extended_gcd(int x, int y);

// computes the multiplicative inverse of e mod

int multiplicativeInverse(int e, int phi);

// RSA encryption

int encrypt(int message, int e, int N);

// RSA decryption

int decrypt(int ciphertext, int d, int N);

#endif /* RSA_H */

======================================================

#ifndef TESTING_H

#define TESTING_H

#include

#include

void assertTrue(bool b, std::string description);

template

void assertEquals(const T& x, const U& y, std::string description) {

if (x == y) {

std::cout << "PASSED: " << description << std::endl;

} else {

std::cout << "FAILED: " << description << std::endl;

std::cout << " " << x << std::endl;

std::cout << " !=" << std::endl;

std::cout << " " << y << std::endl;

}

}

#endif

===================================================

testing.cpp

#include "testing.h"

using namespace std;

void assertTrue(bool b, string description) {

if (!b) {

cout << "FAILED: " << description << endl;

} else {

cout << "PASSED: " << description << endl;

}

}

=========================================

testRSA

#include

#include

#include

using namespace std;

#include "rsa.h"

#include "testing.h"

#include"rsa.cpp"

void testPowmod();

void testExtendedGCD();

void testMultiplicativeInverse();

void testRSA(int p, int q);

int main() {

srand(time(0));

testPowmod();

testExtendedGCD();

testMultiplicativeInverse();

testRSA(31, 59);

testRSA(17, 41);

testRSA(31, 47);

testRSA(43, 79);

return 0;

}

void testPowmod() {

assertTrue(powmod(43, 127, 53) == 38, "43^127 (mod 53) = 38");

}

void testExtendedGCD() {

auto res = extended_gcd(859, 1740);

assertTrue(res.first * 859 + res.second * 1740 == 1,

"extended_gcd(859, 1740)");

}

void testMultiplicativeInverse() {

int inv = multiplicativeInverse(527, 640);

assertTrue((527 * inv) % 640 == 1, "multiplicativeInverse(527, 640)");

}

void testRSA(int p, int q) {

int N = computeN(p, q);

int phi = computePhi(p, q);

int e = computeE(phi);

int d = multiplicativeInverse(e, phi);

int message = rand() % N;

int ciphertext = encrypt(message, e, N);

int decrypted = decrypt(ciphertext, d, N);

stringstream ss;

ss << "p = " << p << ", q = " << q << ", N = " << N << ", phi = " << phi

<< ", e = " << e << ", d = " << d << ", message = " << message

<< ", ciphertext = " << ciphertext << ", decrypted = " << decrypted;

assertTrue(message == decrypted, ss.str());

}

==================================================================

rsa.cpp

#include "rsa.h"

#include

#include

#include

#include

using namespace std;

// calculate RSA's N value from p and q

int computeN(int p, int q) {

// FIXME: implement this function

return -42;

}

// calculate RSA's value from p and q

int computePhi(int p, int q) {

// FIXME: implement this function

return -42;

}

// computes x mod m

int powmod(int x, int y, int m) {

// FIXME: implement this function

return -42;

}

// computes the greatest common divisor of x and y

int gcd(int x, int y) {

// FIXME: implement Euclid's algorithm

return -42;

}

// find an integer e such that gcd(e, ) = 1

// Hint: use rand() to find a number (in the correct range!) that works

int computeE(int phi) {

// FIXME: implement this function

return -42;

}

// returns a pair (a, b) such that ax + by = gcd(a, b)

std::pair extended_gcd(int x, int y) {

// FIXME: implement this function

// See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode

// for an implementation that you can copy

return make_pair(-42, -42);

}

// computes the multiplicative inverse of e mod

// That is: find inv such that (e * inv) % = 1

int multiplicativeInverse(int e, int phi) {

// FIXME: implement this function

// Use extended_gcd to do most of the work.

// The multiplicative inverse you get from extended_gcd might be negative--

// make sure to return a number between 0 and -1. (Hint: remember that

// adding multiples of do not change the result mod .)

return -42;

}

// RSA encryption--given a message, return the ciphertext

// (messages are ints in this implementation)

int encrypt(int message, int e, int N) {

// FIXME: implement this function

return -42;

}

// RSA decryption--given a ciphertext, return the decrypted message

// (messages are ints in this implementation)

int decrypt(int ciphertext, int d, int N) {

// FIXME: implement this function

return -42;

}

=======================================================

extra information

For extended_gcd, check out this Wikipedia pagehttps://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode-it has some good pseudocode

Use extended_gcd in multiplicativeInverse function, but there is one small issue with the values that extended_gcd returns: sometimes they are negative. For RSA we need a non-negative inverse between 0 and 1, so watch out for and fix any negative multiplicative inverses.

#include

pair is a type that holds two things

pair p = make_pair(x, y); creates a pair holding both x and y

p.first and p.second get the individual things out

Extended Euclidean Algorithm-

Finds x & y such that ax + by = gcd(a, b)