Berikut adalah contoh program C++ yang mengimplementasikan algoritma RSA pada kriptografi. Program ini menggunakan fungsi-fungsi berikut.
C++
#include <iostream>
#include <cmath>
using namespace std;
// Fungsi untuk mengecek apakah sebuah bilangan merupakan bilangan prima
bool isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// Fungsi untuk menghitung nilai phi dari dua bilangan prima p dan q
int calculatePhi(int p, int q) {
return (p - 1) * (q - 1);
}
// Fungsi untuk menghitung nilai gcd (greatest common divisor)
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
// Fungsi untuk menghitung nilai e (public key)
int calculateE(int phi) {
int e = 2;
while (e < phi) {
if (gcd(e, phi) == 1) {
return e;
}
e++;
}
return -1;
}
// Fungsi untuk menghitung nilai d (private key)
int calculateD(int e, int phi) {
int d = 1;
while ((d * e) % phi != 1) {
d++;
}
return d;
}
// Fungsi untuk melakukan enkripsi pesan
int encrypt(int message, int e, int n) {
return pow(message, e) % n;
}
// Fungsi untuk melakukan dekripsi pesan
int decrypt(int encryptedMessage, int d, int n) {
return pow(encryptedMessage, d) % n;
}
int main() {
int p, q, n, phi, e, d, message, encryptedMessage, decryptedMessage;
// Input bilangan prima p dan q
cout << "Masukkan bilangan prima p: ";
cin >> p;
cout << "Masukkan bilangan prima q: ";
cin >> q;
// Menghitung nilai n dan phi
n = p * q;
phi = calculatePhi(p, q);
// Menghitung nilai e dan d
e = calculateE(phi);
d = calculateD(e, phi);
// Input pesan yang akan dienkripsi
cout << "Masukkan pesan yang akan dienkripsi: ";
cin >> message;
// Melakukan enkripsi pesan
encryptedMessage = encrypt(message, e, n);
cout << "Pesan terenkripsi: " << encryptedMessage << endl;
// Melakukan dekripsi pesan
decryptedMessage = decrypt(encryptedMessage, d, n);
cout << "Pesan terdekripsi: " << decryptedMessage << endl;
return 0;
}
Silakan gunakan program di atas untuk mengimplementasikan algoritma RSA pada kriptografi.
Program di atas mengimplementasikan algoritma RSA pada kriptografi. Algoritma ini menggunakan dua bilangan prima, p dan q, untuk menghasilkan kunci publik (e) dan kunci privat (d). Kunci publik digunakan untuk mengenkripsi pesan, sedangkan kunci privat digunakan untuk mendekripsi pesan yang telah terenkripsi.
Program ini meminta input dari pengguna berupa dua bilangan prima (p dan q) dan pesan yang akan dienkripsi. Setelah itu, program akan menghitung nilai n dan phi menggunakan fungsi calculatePhi(). Kemudian, program akan menghitung nilai e menggunakan fungsi calculateE() dan nilai d menggunakan fungsi calculateD(). Setelah itu, program akan melakukan enkripsi pesan menggunakan fungsi encrypt() dan mendekripsi pesan menggunakan fungsi decrypt(). Hasil enkripsi dan dekripsi pesan akan ditampilkan pada layar.
Contoh Lain
C++
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<string.h>
using namespace std;
main()
{
char kata[100],kata2[100];
int x[100], y[100], panjang,key1,key2;
cout<<"Masukkan Kata : ";cin.getline(kata,sizeof(kata));
panjang=strlen(kata);
cout<<"masukan key 1 : ";cin>>key1;
cout<<endl;
cout<<"Hasil enkrip : ";
for(int i=0; i<panjang; i++)
{
if (int(kata[i])>96 && int(kata[i])<120 || int(kata[i])>64 && int(kata[i]<88))
{
x[i] = (int(kata[i]) + key1);
}
else if(int(kata[i])>119 && int(kata[i])<123 || int(kata[i])>87 && int(kata[i]<91))
{
x[i] = ((int(kata[i]) + key1)-26);
}
else if(int(kata[i]) == 32)
{
x[i] = int(kata[i]);
}
cout<<char(x[i]);
}
cout<<endl;
cout<<"Hasil dekrip : ";
for(int a=0; a<panjang; a++)
{
if (x[a]>99 && x[a]<123 || x[a]>67 && x[a]<91)
{
y[a] = (x[a] - key1);
}
if (x[a]>96 && x[a]<100 || x[a]>64 && x[a]<68)
{
y[a] = (x[a] - key1)+26;
}
else if(x[a] == 32)
{
y[a] = x[a];
}
cout<<char(y[a]);
}
cout<<endl<<endl;
system("pause");
}C++
#include <vector>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <complex>
#include <cstdio>
#include <utility>
using namespace std;
// base and base_digits must be consistent
const int base = 1000000000;
const int base_digits = 9;
struct bigint {
vector<int> a;
int sign;
bigint() :
sign(1) {
}
bigint(long long v) {
*this = v;
}
bigint(const string &s) {
read(s);
}
void operator=(const bigint &v) {
sign = v.sign;
a = v.a;
}
void operator=(long long v) {
sign = 1;
if (v < 0)
sign = -1, v = -v;
a.clear();
for (; v > 0; v = v / base)
a.push_back(v % base);
}
bigint operator+(const bigint &v) const {
if (sign == v.sign) {
bigint res = v;
for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
if (i == (int) res.a.size())
res.a.push_back(0);
res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
carry = res.a[i] >= base;
if (carry)
res.a[i] -= base;
}
return res;
}
return *this - (-v);
}
bigint operator-(const bigint &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
bigint res = *this;
for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
carry = res.a[i] < 0;
if (carry)
res.a[i] += base;
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
}
void operator*=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
if (i == (int) a.size())
a.push_back(0);
long long cur = a[i] * (long long) v + carry;
carry = (int) (cur / base);
a[i] = (int) (cur % base);
//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
/*
int val;
__asm {
lea esi, cur
mov eax, [esi]
mov edx, [esi+4]
mov ecx, base
div ecx
mov carry, eax
mov val, edx;
}
a[i] = val;
*/
}
trim();
}
bigint operator*(int v) const {
bigint res = *this;
res *= v;
return res;
}
friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
int norm = base / (b1.a.back() + 1);
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.a.resize(a.a.size());
for (int i = a.a.size() - 1; i >= 0; i--) {
r *= base;
r += a.a[i];
int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
int d = ((long long) base * s1 + s2) / b.a.back();
r -= b * d;
while (r < 0)
r += b, --d;
q.a[i] = d;
}
q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair(q, r / norm);
}
bigint operator/(const bigint &v) const {
return divmod(*this, v).first;
}
bigint operator%(const bigint &v) const {
return divmod(*this, v).second;
}
void operator/=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
long long cur = a[i] + rem * (long long) base;
a[i] = (int) (cur / v);
rem = (int) (cur % v);
}
trim();
}
bigint operator/(int v) const {
bigint res = *this;
res /= v;
return res;
}
int operator%(int v) const {
if (v < 0)
v = -v;
int m = 0;
for (int i = a.size() - 1; i >= 0; --i)
m = (a[i] + m * (long long) base) % v;
return m * sign;
}
void operator+=(const bigint &v) {
*this = *this + v;
}
void operator-=(const bigint &v) {
*this = *this - v;
}
void operator*=(const bigint &v) {
*this = *this * v;
}
void operator/=(const bigint &v) {
*this = *this / v;
}
bool operator<(const bigint &v) const {
if (sign != v.sign)
return sign < v.sign;
if (a.size() != v.a.size())
return a.size() * sign < v.a.size() * v.sign;
for (int i = a.size() - 1; i >= 0; i--)
if (a[i] != v.a[i])
return a[i] * sign < v.a[i] * sign;
return false;
}
bool operator>(const bigint &v) const {
return v < *this;
}
bool operator<=(const bigint &v) const {
return !(v < *this);
}
bool operator>=(const bigint &v) const {
return !(*this < v);
}
bool operator==(const bigint &v) const {
return !(*this < v) && !(v < *this);
}
bool operator!=(const bigint &v) const {
return *this < v || v < *this;
}
void trim() {
while (!a.empty() && a.back() == 0)
a.pop_back();
if (a.empty())
sign = 1;
}
bool isZero() const {
return a.empty() || (a.size() == 1 && !a[0]);
}
bigint operator-() const {
bigint res = *this;
res.sign = -sign;
return res;
}
bigint abs() const {
bigint res = *this;
res.sign *= res.sign;
return res;
}
long long longValue() const {
long long res = 0;
for (int i = a.size() - 1; i >= 0; i--)
res = res * base + a[i];
return res * sign;
}
friend bigint gcd(const bigint &a, const bigint &b) {
return b.isZero() ? a : gcd(b, a % b);
}
friend bigint lcm(const bigint &a, const bigint &b) {
return a / gcd(a, b) * b;
}
void read(const string &s) {
sign = 1;
a.clear();
int pos = 0;
while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = s.size() - 1; i >= pos; i -= base_digits) {
int x = 0;
for (int j = max(pos, i - base_digits + 1); j <= i; j++)
x = x * 10 + s[j] - '0';
a.push_back(x);
}
trim();
}
friend istream& operator>>(istream &stream, bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
}
friend ostream& operator<<(ostream &stream, const bigint &v) {
if (v.sign == -1)
stream << '-';
stream << (v.a.empty() ? 0 : v.a.back());
for (int i = (int) v.a.size() - 2; i >= 0; --i)
stream << setw(base_digits) << setfill('0') << v.a[i];
return stream;
}
static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + 1);
p[0] = 1;
for (int i = 1; i < (int) p.size(); i++)
p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (int i = 0; i < (int) a.size(); i++) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back(int(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int) cur);
while (!res.empty() && res.back() == 0)
res.pop_back();
return res;
}
void fft(vector<complex<double> > & a, bool invert) const {
int n = (int) a.size();
for (int i = 1, j = 0; i < n; ++i) {
int bit = n >> 1;
for (; j >= bit; bit >>= 1)
j -= bit;
j += bit;
if (i < j)
swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * 3.14159265358979323846 / len * (invert ? -1 : 1);
complex<double> wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
complex<double> w(1);
for (int j = 0; j < len / 2; ++j) {
complex<double> u = a[i + j];
complex<double> v = a[i + j + len / 2] * w;
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
w *= wlen;
}
}
}
if (invert)
for (int i = 0; i < n; ++i)
a[i] /= n;
}
void multiply_fft(const vector<int> &a, const vector<int> &b, vector<int> &res) const {
vector<complex<double> > fa(a.begin(), a.end());
vector<complex<double> > fb(b.begin(), b.end());
int n = 1;
while (n < (int) max(a.size(), b.size()))
n <<= 1;
n <<= 1;
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; ++i)
fa[i] *= fb[i];
fft(fa, true);
res.resize(n);
for (int i = 0, carry = 0; i < n; ++i) {
res[i] = int(fa[i].real() + 0.5) + carry;
carry = res[i] / 1000;
res[i] %= 1000;
}
}
bigint operator*(const bigint &v) const {
bigint res;
res.sign = sign * v.sign;
multiply_fft(convert_base(a, base_digits, 3), convert_base(v.a, base_digits, 3), res.a);
res.a = convert_base(res.a, 3, base_digits);
res.trim();
return res;
}
bigint mul_simple(const bigint &v) const {
bigint res;
res.sign = sign * v.sign;
res.a.resize(a.size() + v.a.size());
for (int i = 0; i < (int) a.size(); ++i)
if (a[i])
for (int j = 0, carry = 0; j < (int) v.a.size() || carry; ++j) {
long long cur = res.a[i + j] + (long long) a[i] * (j < (int) v.a.size() ? v.a[j] : 0) + carry;
carry = (int) (cur / base);
res.a[i + j] = (int) (cur % base);
}
res.trim();
return res;
}
typedef vector<long long> vll;
static vll karatsubaMultiply(const vll &a, const vll &b) {
int n = a.size();
vll res(n + n);
if (n <= 32) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
}
int k = n >> 1;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end());
vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2);
for (int i = 0; i < k; i++)
a2[i] += a1[i];
for (int i = 0; i < k; i++)
b2[i] += b1[i];
vll r = karatsubaMultiply(a2, b2);
for (int i = 0; i < (int) a1b1.size(); i++)
r[i] -= a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
r[i] -= a2b2[i];
for (int i = 0; i < (int) r.size(); i++)
res[i + k] += r[i];
for (int i = 0; i < (int) a1b1.size(); i++)
res[i] += a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
res[i + n] += a2b2[i];
return res;
}
bigint mul_karatsuba(const bigint &v) const {
vector<int> a6 = convert_base(this->a, base_digits, 6);
vector<int> b6 = convert_base(v.a, base_digits, 6);
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size())
a.push_back(0);
while (b.size() < a.size())
b.push_back(0);
while (a.size() & (a.size() - 1))
a.push_back(0), b.push_back(0);
vll c = karatsubaMultiply(a, b);
bigint res;
res.sign = sign * v.sign;
for (int i = 0, carry = 0; i < (int) c.size(); i++) {
long long cur = c[i] + carry;
res.a.push_back((int) (cur % 1000000));
carry = (int) (cur / 1000000);
}
res.a = convert_base(res.a, 6, base_digits);
res.trim();
return res;
}
};
bigint getRandomBigint(int len) {
string s;
for (int i = 0; i < len; i++)
s += rand() % 10 + '0';
return bigint(s);
}
pair<int, pair<int, int> > extendedEuclid(int a, int b)
{
int x = 1, y = 0;
int xLast = 0, yLast = 1;
int q, r, m, n;
while (a != 0)
{
q = b / a;
r = b % a;
m = xLast - q * x;
n = yLast - q * y;
xLast = x;
yLast = y;
x = m;
y = n;
b = a;
a = r;
}
return make_pair(b, make_pair(xLast, yLast));
}
int modInverse(int a, int m)
{
return (extendedEuclid(a, m).second.first + m) % m;
}
int main(){
int p,q,n,e,d,phi,cek;
bigint enkrip,dekrip,tempen,tempde,pangkaten=1,pangkatde=1;
char kata[100];
cout<<" Masukkan Nilai P = ";
cin>>p;
cout<<" Masukkan Nilai Q = ";
cin>>q;
n=p*q;
phi=(p-1)*(q-1);
cin.ignore();
cout<<"\n Masukkan Kata yang akan di Enkrip = ";
cin.getline(kata, sizeof(kata));
for(int x=2;x<=phi;x++){
cek=0;
for(int i=2;i<x;i++){
if (x%i==0){
cek=1;
}
}
if(cek==0){
if(phi%x){
e=x;
break;
}
}
}
cout<<"\n Nilai p = "<<p<<endl;
cout<<" Nilai q = "<<q<<endl;
cout<<" Nilai n = "<<n<<endl;
cout<<" Nilai phi = "<<phi<<endl;
cout<<" Nilai Enkripsi e = "<<e<<endl;
cout<<endl;
for(int x=0;kata[x];x++){
tempen=int(kata[x]);
tempen=tempen;
cout<<" Huruf "<<x+1<<" ("<<kata[x]<<") --> Plan Text ASCII = "<<tempen;
pangkaten=1;
for(int z=1;z<=e;z++){
pangkaten=tempen*pangkaten;
}
enkrip=pangkaten%n;
cout<<" -- > Enkripsi ASCII = "<<enkrip<<endl;
//cout<<char(cenkrip)<<endl;
}
cout<<"\n Kunci Dekripsi d = ";
cout<<modInverse(e, phi)<<endl;
d=modInverse(e, phi);
for(int x=0;kata[x];x++){
tempen=int(kata[x]);
tempen=tempen;
pangkaten=1;
for(int z=1;z<=e;z++){
pangkaten=tempen*pangkaten;
}
enkrip=pangkaten%n;
cout<<" Enkripsi Text ASCII = "<<enkrip;
pangkatde=1;
for(int y=1;y<=d;y++){
pangkatde=enkrip*pangkatde;
}
dekrip=pangkatde%n;
cout<<" --> Plan Text ASCII = "<<dekrip<<endl;
//cout<<char(dekrip+96);
}
}Silakan mencoba contoh program di atas untuk mengimplementasikan algoritma RSA pada kriptografi.
Leave a Reply