The two books I have "Applied Cryptography" by Bruce Schneier and "Mastering Algorithms with C" by Kyle Loudon both say that e must be coprime with (p - 1)(q - 1), not (p - 1) and (q - 1).
They are equivalent. e is coprime to (p - 1)(q - 1) if and only if it is coprime to both (p - 1) and (q - 1). :)
“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”
Well isn't that convenient. :)
Thanks everyone for pointing these things out.
Attached is my RSA C++ source code. It is based on Matt McCutchen's C++ Big Integer Library -- https://mattmccutchen.net/bigint/
Notes:
- p and q are both 200 digit primes. These primes are well-known, so they're not really good at keeping the ciphertext secure. This source code is for learning RSA. You'll have to find your own prime numbers.
- I add a 512-bit salt to the message before converting it into plaintext (a single integer). This is not as good as using Optimal Asymmetric Encryption Padding, but it's better than nothing.
- The salt is generated using the standard C library srand/rand. This is not a cryptographically secure pseudorandom number generator (PRNG). You'll have to find your own PRNG. See: https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
It has to be coprime to both p - 1 and q - 1, otherwise the security is considerably weakened and/or the encryption is not reversible.
In the end I used e = 65537. I tried 65536 for fun, and the program died with a segfault LOL (I'm using someone else's bigint library).
From what I read, m must be less than p*q = n, and e must be less than (p - 1)*(q - 1) = totient.
From what I read, m must be less than p*q = n, and e must be less than (p - 1)*(q - 1) = totient.
From what I read, m must be less than p*q = n, and e must be less than (p - 1)*(q - 1) = totient.
It doesn't hurt if e is larger than (p - 1)*(q - 1). By the Euler-Fermat theorem, changing e by adding or subtracting (p - 1)*(q - 1) results in the same encoding.
So, it's periodic like a sine wave?
So, it's periodic like a sine wave?
It's periodic in the same way that the sequence of integers modulo 3 looks like 0 1 2 0 1 2 0 1 2 0 1 2 ... if you take any integer and add 3, the result modulo 3 won't change :)
Technically the exponent is periodic modulo lcm(p - 1, q - 1) which is smaller than (p - 1)(q - 1) but there is not much difference, the lcm is usually within a small factor of the product depending on how many factors p - 1 and q - 1 share.
“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”
Technically the exponent is periodic modulo lcm(p - 1, q - 1) which is smaller than (p - 1)(q - 1) but there is not much difference, the lcm is usually within a small factor of the product depending on how many factors p - 1 and q - 1 share.
