The key functions/methods are:
bigint bigint::random_prime(int digits, double pfail);
Returns a random prime number with the requested number of (decimal) digits.
There is no certainty, but the probability of the returned number not really
being prime will be less than pfail.
void bigint::get_random_prime_and_generator(int digits, bigint & pr, bigint & ge, double pfail);
The reference parameters deliver two results, digits and pfail are given to random_prime
as above, the reulting random prime is stored in pr. A generator for pr is stored in ge.
A generator for pr is a number such that every value between 1 and pr - 1 inclusive is
the result of (ge ^ i) % pr for some value of i also between 1 and pr - 1.
Example: 3 is a generator for 7:
3^1 = 3, 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243, 3^6 = 729
3%7 = 3, 9%7 = 2, 27%7 = 6, 81%7=4, 243%7=5, 729%7 = 1
All the numbers 1, 2, 3, 4, 5, 6 come up at some point.
Another example, 3 is not a generator for 11:
The powers of 3 are 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049
modulo 11 they are 3, 9, 5, 4, 1, 3, 9, 5, 4, 1.
2, 6, 7, 8, 10 are never produced.
The constructor rsakeypair::rsakeypair(int digits, double pfail);
Creates an object that contains two keys k1 and k2, one for encryption and one for decryprion.
Anything encrypted with k1 can only be decrypted with k2, and also
anything encrypted with k2 can only be decrypted with k1.
k1 is your secret key, nobody else may know it. k2 is your public key, everyone must know it.
The keys are pairs of numbers (d, n) and (e, n), n is the same for both of them.
bigint rsakey::encrypt(bigint msg);
k.encrypt(m) is the result of encrypting msg with key k.
All messages can be represented as bigints. Just think of the letters of the alphabet as
the digits of a base-26 number. Messages are split into blocks of characters that are
encrypted and decrypted separately one by one because msg must never be as big as n.
The objects are
struct rsakey
{ bigint d, n;
rsakey(const bigint & d, const bigint & n);
rsakey();
bigint encrypt(bigint msg); };
struct rsakeypair
{ rsakey pub, prv;
rsakeypair(const rsakey & u, const rsakey & v);
rsakeypair(int digits, double pfail); };
Diffie-hellman is used to allow two people to agree on a password or encryption key securely
even when an enemy is able to see all of their communications in real time. It takes just a few
steps:
1. One of the people (A) has to initiate the process. A uses the constructor like this:
diffie_hellman dhA(int digits, double pfail)
to start things off. Diffie-hellman is also based on very large prime numbers, the two
parameters are exactly as for bigint::random_prime. The dhA object created by the constructor
contains two bigints: dhA.p and dhA.g they are sent unsecurely to the other party, B.
2. B receives the p and g sent by A in the first two steps. B then uses another constructor
to start their side of the procedure like this:
diffie_hellman dhB(p, g);
3. The initiator, A, then uses dhA.step_2(bigint & kA), which sets its reference parameter kA
to another special value. A sends kA to B unsecurely and awaits B's reply.
4. B does the same thing, using dhAB.step_2(bigint & kAB), which sets its reference parameter kB
to another special value. B sends kB to A unsecurely and awaits A's reply.
5. When A receives kB, they use dhA.step_3(kB). That creates another value dhA.password.
6. When B receives kA, they use dhB.step_3(kA). That creates another value dhB.password.
7. It is guaranteed that dhA.password and dhB.password will be exactly the same. The enemy
who saw everything can not work out what that password is. dhA and dhB retained some extra
random numbers that were never transmitted, and are needed to generate the password.
The only important parts of this object are
struct diffie_hellman
{ bigint p, g, secret, password;
...
static const int primes[] =
{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139,
149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439,
443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557,
563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117,
1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249,
1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381,
1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613,
1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879,
1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017,
2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141,
2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399,
2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689,
2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953,
2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089,
3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253,
3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373,
3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529,
3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793,
3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923,
3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073,
4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219,
4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357,
4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513,
4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651,
4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957,
4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237,
5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413,
5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527,
5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683,
5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827,
5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981,
5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131,
6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389,
6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571,
6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719,
6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869,
6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001,
7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187,
7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333,
7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517,
7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639,
7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789,
7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937,
7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111,
8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269,
8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429,
8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599,
8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731,
8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863,
8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029,
9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187,
9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341,
9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467,
9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631,
9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787,
9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929,
9931, 9941, 9949, 9967, 9973 };
const int numprimes = sizeof(primes) / sizeof(primes[0]);
const int prime_pos_tens[] = { 0, 4, 25, 168, numprimes };
bigint bigint::gcd(bigint a, bigint b)
{ bigint x, t;
a.make_positive();
b.make_positive();
while (b.size != 0)
{ t = a;
a = b;
t.divmod(b, x);
b = x; }
a.make_positive();
return a; }
void bigint::gcdswapf(bigint & var1, bigint & var2, const bigint & quo)
{ bigint newvar(quo);
newvar.mul(var2);
newvar.sub(var1);
newvar.neg = ! newvar.neg;
var1.digit = var2.digit;
var1.neg = var2.neg;
var1.cap = var2.cap;
var1.size = var2.size;
var2.digit = newvar.digit;
var2.neg = newvar.neg;
var2.cap = newvar.cap;
var2.size = newvar.size;
newvar.digit = NULL;
newvar.cap = 0; }
bigint bigint::extgcd(bigint a, bigint b, bigint & m, bigint & n)
{ bool awasneg = a.is_negative(), bwasneg = b.is_negative(), swap = false;
a.make_positive();
b.make_positive();
m = 1;
n.clear();
bigint nm = 0, nn = 1, q;
if (b > a)
{ bigint::swap(a, b);
swap = true; }
while (! b.is_zero())
{ q = a / b;
bigint::gcdswapf(m, nm, q);
bigint::gcdswapf(n, nn, q);
bigint::gcdswapf(a, b, q); }
if (swap)
bigint::swap(m, n);
if (awasneg)
{ m.negate();
if (bwasneg)
n.negate(); }
else if (bwasneg)
n.negate();
a.make_positive();
return a; }
static void gcdswapf(long long int & var1, long long int & var2, long long int quo)
{ long long int val = var1 - quo * var2;
var1 = var2;
var2 = val; }
long long int extgcd(long long int a, long long int b, long long int & m, long long int & n)
{ bool awasneg = false, bwasneg = false, swap = false;
if (a < 0)
{ awasneg = true;
a = - a; }
if (b < 0)
{ bwasneg = true;
b = - b; }
m = 1;
n = 0;
long long int nm = 0, nn = 1, q;
if (b > a)
{ long long int t = a;
a = b;
b = t;
swap = true; }
while (b != 0)
{ q = a / b;
gcdswapf(m, nm, q);
gcdswapf(n, nn, q);
gcdswapf(a, b, q); }
if (swap)
{ long long int t = m;
m = n;
n = t; }
if (awasneg)
{ m = - m;
if (bwasneg)
n = - n; }
else if (bwasneg)
n = - n;
if (a < 0)
return - a;
return a; }
long long int modinv(long long int a, long long int mod)
{ long long int m, n;
int g = extgcd(a, mod, m, n);
if (g != 1)
return 0;
if (m < 0 || m >= mod)
{ m %= mod;
if (m < 0)
m += mod; }
return m; }
bigint bigint::modinv(const bigint & mod)
{ bigint m, n;
bigint g = bigint::extgcd(* this, mod, m, n);
if (g != 1)
return 0;
if (m.is_negative() || m >= mod)
{ m %= mod;
if (m.is_negative())
m += mod; }
return m; }
double bigint::approximate_logarithm(int base)
{ if (neg || is_zero())
throw biginterror("logarithm of zero or negative");
if (base <= 1.0)
throw biginterror("base for logarithms must be > 1");
int digs = size;
if (digs > 15)
digs = 15;
double mant = 0.0, pow = 0.1;
for (int i = size - 1; i >= size - digs; i -= 1)
{ mant += digit[i] * pow;
pow /= 10.0; }
return (log10(mant) + size) / log10(base); }
bool bigint::tiny_is_prime() const
{ if (neg || size == 0)
return false;
if (size > 4)
throw biginterror("number too big for tiny_is_prime");
int v = intval();
for (int i = 0; i < numprimes; i += 1)
if (primes[i] == v)
return true;
return false; }
bool bigint::rabin_miller(long long int ntimes) // p is to be tested for primality, should not be changed.
{ if (neg || size == 0)
randomise();
if (size <= 4)
return tiny_is_prime();
bigint p = * this; // do not use if p.size < 4
for (int i = 0; i < ntimes; i += 1)
{ bigint m = p; // find m so that p = 1 + (2 ^ b) * m
m.sub(1);
int b = 0; // b = how many times can p - 1 be divided by 2
while (true)
{ if (! m.is_odd())
break;
m.halve();
b += 1; }
bigint a = bigint::random(p.size - 2, p.size); // pick random a less than p
if (a.size == p.size)
{ int last = a.size - 1;
if (a.digit[last] >= p.digit[last])
a.digit[last] = p.digit[last] - 1;
while (last >= 0 && a.digit[last] == 0)
last -= 1;
if (last >= 2)
a.size = last + 1;
else
a = bigint::random(p.size - 1); }
int j = 0; // j = 0 and z = (a ^ m) mod p
bigint z = a;
z.powmod(m, p);
if (z == 1) // z = 1 or p - 1 means p passes the test
continue;
if (z.is_one_less_than(p))
continue;;
while (true)
{ if (j > 0 && z == 1)
return false;
j += 1;
if (z.is_one_less_than(p))
break;
if (j >= b)
return false;
z.powmod(2, p); } }
return true; }
bool bigint::test_primality_nt(long long int ntimes)
{ if (ntimes == 0)
return true;
if (neg || size == 0)
return false;
if (size < 4)
return tiny_is_prime();
return rabin_miller(ntimes); }
static long long int r_m_pfail_to_times(double pfail)
{ if (pfail == 0.0)
throw biginterror("pfail of zero is not possible");
double t = log(1.0 / pfail) / log(4.0);
if (t > maxposlonglongint - 1)
throw biginterror("pfail too low to be acheivable");
return (long long int)(t + 1); }
bool bigint::test_primality(double pfail)
{ if (pfail < 0.0 || pfail > 1.0)
throw biginterror("pfail not between 0 and 1");
if (pfail == 1.0)
return true;
if (neg || size == 0)
return false;
if (size < 4)
return tiny_is_prime();
return rabin_miller(r_m_pfail_to_times(pfail)); }
static int prime_ends[] = { 1, 3, 7, 9 };
bigint bigint::random_prime_nt(int digits, int ntimes)
{ if (digits < 1)
digits = 1;
if (digits < 5)
{ int start = prime_pos_tens[digits - 1], end = prime_pos_tens[digits] - 1;
int pos = ::random() % (end - start) + start;
return primes[pos]; }
while (true)
{ bigint r = bigint::random(digits);
int pos = ::random() & 3;
r.digit[0] = prime_ends[pos];
if (r.test_primality_nt(ntimes))
return r; } }
bigint bigint::random_prime(int digits, double pfail)
{ return random_prime_nt(digits, r_m_pfail_to_times(pfail)); }
void bigint::get_random_prime_and_generator_nt(int digits, bigint & pr, bigint & gen, int ntimes)
{ while (true)
{ bigint g1 = bigint::random_prime_nt(digits >> 1, ntimes);
bigint g2 = bigint::random_prime_nt(digits - (digits >> 1), ntimes);
pr = g1 * g2;
bigint x = pr;
pr *= 2;
pr += 1;
if (! pr.test_primality_nt(ntimes))
continue;
for (int igen = 3; igen > 0; igen += 2)
{ bigint t = igen;
t.powmod(x, pr);
if (t == 1)
continue;
x = g1 * 2;
t = igen;
t.powmod(x, pr);
if (t == 1)
continue;
x = g2 * 2;
t = igen;
t.powmod(x, pr);
if (t != 1)
{ gen = igen;
return; } }
throw biginterror("failed to find generator in 2147483647 tries"); } }
void bigint::get_random_prime_and_generator(int digits, bigint & pr, bigint & ge, double pfail)
{ return get_random_prime_and_generator_nt(digits, pr, ge, r_m_pfail_to_times(pfail)); }
int bigint::bits_to_digits(int n)
{ return (int)(n * log10overlog2 - 0.99999999); }
int bigint::digits_to_bits(int n)
{ return (int)(n / log10overlog2); }
void bigint::increase_until_prime_nt(int ntries)
{ if (! is_odd())
add(1);
while (true)
{ if (test_primality_nt(ntries))
return;
add(2); } }
void bigint::increase_until_prime(double pfail)
{ increase_until_prime_nt(r_m_pfail_to_times(pfail)); }
rsakey::rsakey(const bigint & id, const bigint & in)
{ d = id;
n = in; }
rsakey::rsakey()
{ }
ostream & operator<<(ostream & out, const rsakey & k)
{ out << k.n << ":" << k.d;
return out; }
istream & operator>>(istream & in, rsakey & k)
{ string s;
in >> s;
size_t p = s.find(':');
if (p == string::npos)
throw biginterror("incorrect format, rsakey should be n:d");
bigint n = s.substr(0, p);
bigint d = s.substr(p + 1);
k.n = n;
k.d = d;
return in; }
rsakeypair::rsakeypair(const rsakey & u, const rsakey & v): pub(u), prv(v)
{ }
rsakeypair::rsakeypair(int digits, double pfail)
{ bigint::randomise();
if (digits < 2)
throw biginterror("too few digits for rsakeypair");
int ntimes = r_m_pfail_to_times(pfail);
bigint p = bigint::random_prime_nt(digits / 2, ntimes);
bigint q = bigint::random_prime_nt(digits / 2, ntimes);
bigint n = p;
n.mul(q);
p.sub(1);
q.sub(1); // n is p * q, p is p - 1, q is q - 1
bigint pm1qm1 = p;
pm1qm1.mul(q);
bigint d, e;
while (true)
{ e = bigint::random(digits);
while (e > pm1qm1)
e.halve();
while (bigint::gcd(e, pm1qm1) != 1)
e.add(1);
if (e <= 0)
continue;
d = e.modinv(pm1qm1);
if (d > 0)
break; }
pub = rsakey(e, n);
prv = rsakey(d, n); }
bigint rsakey::encrypt(bigint msg)
{ if (msg >= n)
throw biginterror("rsa ecryption attempt with message >= n");
msg.powmod(d, n);
return msg; }
diffie_hellman::diffie_hellman()
{ stage = 0; }
void diffie_hellman::set(int digits, double pfail)
{ bigint::randomise();
if (digits < 2)
throw biginterror("too few digits for diffie_hellman");
bigint q = bigint::random_prime(digits / 2, pfail);
while (true)
{ bigint r = bigint::random(digits / 2);
p = q * r + 1;
if (p.test_primality(pfail / 10.0))
break; }
while (true)
{ g = bigint::random(digits) % p;
g.powmod((p - 1) / q, p);
if (g != 1)
break; }
stage = 1; }
diffie_hellman::diffie_hellman(int digits, double pfail)
{ set(digits, pfail); }
void diffie_hellman::set(const bigint & p0, const bigint & g0)
{ bigint::randomise();
p = p0;
g = g0;
stage = 1; }
diffie_hellman::diffie_hellman(const bigint & p0, const bigint & g0)
{ set(p0, g0); }
void diffie_hellman::step_2(bigint & publishable)
{ if (stage == 0)
throw biginterror("diffie_hellman used without initialisation");
secret = bigint::random(p.num_digits() - 1);
publishable = g;
publishable.powmod(secret, p);
stage = 2; }
void diffie_hellman::step_3(const bigint & received)
{ if (stage < 2)
throw biginterror("diffie_hellman step_3 used without earlier step_2");
password = received;
password.powmod(secret, p);
stage = 3; }