U RSA kriptosistemu, svaki učesnik \(A\) ima javni ključ \(P_A = (e, n)\), i privatni ključ \(S_A = (d, n)\), gde je \(n = p q\) (za neke proste brojeve \(p\) i \(q\)) i \(d \equiv e^{-1} \ (\,\mathrm{mod}\,\phi(n))\). Šifrovanjem poruke \(M\) dobijamo šifrat \(C\), i to kao \(C \equiv M^e \ (\,\mathrm{mod}\,n)\). Dešifrovanjem šifrata \(C\) dobijamo originalnu poruku \(M\), i to kao \(M \equiv C^d \ (\,\mathrm{mod}\,n)\).
Neka je dat javni ključ \(P_A = (e, n)\) i šifrat \(C\). Pored toga, dat je i zbir prostih brojeva \(x = p + q\). Odrediti poruku \(M\) dešifrovanjem šifrata \(C\) privatnim ključem \(S_A = (d, n)\).
Sa standardnog ulaza se učitava zbir prostih brojeva \(x\), proizvod prostih brojeva \(n\), javni eksponent \(e\), i šifrat \(M\),
Na standardni izlaz ispisati poruku \(M\).
143 111 65537 24
89
Iz uslova zadatka imamo:
\[\begin{align*} n &= p q \\ x &= p + q \\ \end{align*}\]
Iz druge jednačine izrazimo \(p = x - q\), te zamenimo \(p\) u prvoj jednačini
\[\begin{align*} n &= (x - q)q \\ n &= xq - q^2 \\ 0 &= q^2 - xq + n \\ \end{align*}\]
Rešimo kvadratnu jednačinu
\[\begin{align*} D &= x^2 - 4n \\ p &= \frac{x - \sqrt{D}}{2} \\ q &= \frac{x + \sqrt{D}}{2} \\ \end{align*}\]
Računamo \(\phi(n) = (p - 1)(q - 1)\), a zatim i \(d = e^{-1} \ (\,\mathrm{mod}\,\phi(n))\). Na kraju imamo
\[M = C^d \ (\,\mathrm{mod}\,n).\]
#include <iostream>
#include <cmath>
using namespace std;
// Dato
long long bezu(long long a, long long b, long long& s, long long& t) {
long long r0 = a, r1 = b;
long long s0 = 1, s1 = 0;
long long t0 = 0, t1 = 1;
while (r1 > 0) {
long long q = r0 / r1;
long long tmp;
tmp = r0;
r0 = r1;
r1 = tmp - q*r1;
tmp = s0;
s0 = s1;
s1 = tmp - q*s1;
tmp = t0;
t0 = t1;
t1 = tmp - q*t1;
}
s = s0; t = t0;
return r0;
}
// Dato
bool inverz(long long a, long long n, long long& t) {
long long s;
long long r = bezu(n, a, s, t);
if (t < 0) t += n;
return r == 1;
}
// Dato
long long stepen_po_modulu(long long x, long long k, long long n) {
k %= n;
long long stepen = 1;
while (k > 0) {
if (k % 2 == 1)
stepen = (stepen * x) % n;
x = (x * x) % n;
k /= 2;
}
return stepen;
}
int main() {
long long n, C, e, x;
cin >> n >> C >> e >> x;
long long D = x * x - 4 * n;
long long D_sqrt = sqrt(D);
long long p = (x - D_sqrt) / 2;
long long q = (x + D_sqrt) / 2;
long long phi_n = (p - 1) * (q - 1);
long long d; inverz(e, phi_n, d);
long long M = stepen_po_modulu(C, d, n);
cout << M << endl;
return 0;
}