002
08.11.2007, 23:51 Uhr
0xdeadbeef
Gott
(Operator)
|
Hmm...ist ziemlich unüberschaubar in der Form. Warum spaltest dus nicht ein bisschen auf, in mehrere Funktionen? Dadurch wirds deutlich übersichtlicher. In diesem Fall würde es zum Beispiel Sinn machen, eigene Funktionen für das Generieren von Primzahlen, den erweiterten euklidischen Algorithmus, und Modulo-Potenzierung zu schreiben. Ich hatte grad nichts besseres zu tun, also hab ich meine Zeit mal damit totgeschlagen:
| C++: |
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
struct ext_euklid_info {
long d, s, t;
};
ext_euklid_info ext_euklid(unsigned long a, unsigned long b) {
ext_euklid_info ret = { a, 1, 0 };
if(b != 0) {
ext_euklid_info tmp = ext_euklid(b, a % b);
ret.d = tmp.d;
ret.s = tmp.t;
ret.t = tmp.s - a / b * tmp.t;
}
return ret;
}
unsigned long mult_inverse_mod(unsigned long x, unsigned long phi) {
ext_euklid_info info = ext_euklid(x, phi);
return (info.s + phi) % phi;
}
bool is_prime(unsigned long x, std::vector<unsigned long> primes) {
for(int i = 0; primes[i] * primes[i] <= x; ++i) {
if(x % primes[i] == 0)
return false;
}
return true;
}
std::vector<unsigned long> generate_primes(std::size_t num) {
std::vector<unsigned long> primes(2);
primes[0] = 2;
primes[1] = 3;
for(int i = 5, j = 2; primes.size() < num; i += j, j = 6 - j) {
if(is_prime(i, primes))
primes.push_back(i);
}
return primes;
}
unsigned long pow_mod(unsigned long base, unsigned long exp, unsigned long mod) {
unsigned long base_mod = base % mod;
if(exp == 0) return 1;
if(exp % 2 == 0) {
return pow_mod(base_mod * base_mod % mod, exp / 2, mod);
}
return base_mod * pow_mod(base_mod, exp - 1, mod) % mod;
}
int main() {
std::vector<unsigned long> primes;
unsigned long p, q, N, phi, d, e, C, K, K_c;
std::srand(std::time(0));
primes = generate_primes(1000);
p = primes[62];
q = primes[148];
N = p * q;
phi = (p - 1) * (q - 1);
// e muss nicht prim sein, sondern lediglich teilerfremd zu phi
do {
e = rand() % (phi / 10);
} while(ext_euklid(e, phi).d != 1);
d = mult_inverse_mod(e, phi);
std::cout << "p: " << p << std::endl
<< "q: " << q << std::endl
<< "phi: " << phi << std::endl;
std::cout << "pubkey : (" << e << ", " << N << ")" << std::endl
<< "privkey: (" << d << ", " << N << ")" << std::endl;
K = 12345;
C = pow_mod(K, e, N);
K_c = pow_mod(C, d, N);
std::cout << K << ", " << C << ", " << K_c << std::endl;
}
|
Wenn du das verwenden willst, wirst dus noch auf char-arrays tweaken müssen; das hier ist mehr so ne Art Referenzimplementierung. Davon aber mal ganz abgesehen, es wäre wahrscheinlich am sinnvollsten, du würdest dafür eine Krypto-Bibliothek verwenden, wie z.B. libgcrypt oder openssl, die haben da noch nämlich noch ne ganze Reihe an sicherheitstechnischen Tricks drauf, die ich hier nicht alle erschlagen kann - memory locking und so weiter.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra |
