There are several standard RSA key storage / exchange formats, such as RFC 3447 . Whatever the case, most (many in one way or another) use ASN.1 encoding, which in itself adds more complexity than most people like. Some use Base64 encoding, which is much easier to implement.
As for what the key is, you are right in its basic form; the public key includes a module (usually called n ) and an exponent (usually called e ).
To compute a key pair, you start with two large prime numbers, usually called p and q . You compute the module n as p * q . You also compute a number (often called r ), which is (p-1) * (q-1) .
Then e is a more or less randomly chosen number prime with respect to r . Warning: you do not want e be really small, although - log (e)> = log (n) / 4 at least.
Then you calculate d (private decryption key) as a number satisfying the relation:
d * e = 1 (mod r)
You usually calculate this using the Euclidean algorithm, although there are other options (see below). Again, you don't want d to be really small either, so if you get a really very small number, you probably want to try a different value for e and compute a new d to match.
There is another way to calculate your e and d . You can start by finding some number K that matches 1 mod r, and then expand it. Combine the main factors together to get two factors of approximately the same size, and use them as e and d .
As for the attacker calculating your d : you need r to calculate this, and knowing r depends on knowing p and q . This is exactly why / where / how factoring comes into the RSA gap. If you consider n , then you know p and q . From them you can find r , and from r you can calculate d corresponding to the known e .
So, let's work through the math to create a key pair. We are going to use prime numbers that are too small to be effective, but they should be enough to show the corresponding ideas.
So, let's start by choosing ap and q (of course, both must be primes):
p = 9999991 q = 11999989
Of those we compute n and r :
n = 119999782000099 r = 119999760000120
Then we need to either choose e or calculate K , and then calculate it to get e and d . At the moment, we will go with your proposal e = 65537 (since 65537 is prime, the only possibility for it and r not relative primes would be if r were an exact multiple of 65537, which, as we can check, is not is the case pretty easy).
Based on this, we need to calculate our d . We can do this quite easily (although not necessarily very quickly) using the "extended" version of the Euclidean algorithm, (as you mentioned) the Euler Totient, the Gauss method or any of a number of others.
For now, I will calculate this using the Gauss method:
template <class num> num gcd(num a, num b) { num r; while (b > 0) { r = a % b; a = b; b = r; } return a; } template <class num> num find_inverse(num a, num p) { num g, z; if (gcd(a, p) > 1) return 0; z = 1; while (a > 1) { z += p; if ((g=gcd(a, z))> 1) { a /= g; z /= g; } } return z; }
The result we get:
d = 38110914516113
Then we can connect them to the RSA implementation and use them to encrypt and decrypt the message.
So let it encrypt "Top Secret Message!". Using e and n above, it encrypts:
74603288122996 49544151279887 83011912841578 96347106356362 20256165166509 66272049143842 49544151279887 22863535059597 83011912841578 49544151279887 96446347654908 20256165166509 87232607087245 49544151279887 68304272579690 68304272579690 87665372487589 26633960965444 49544151279887 15733234551614
And, using the above d , it decrypts back to the original. The code for encryption / decryption (using hard-coded keys and a module) is as follows:
#include <iostream> #include <iterator> #include <algorithm> #include <vector> #include <functional> typedef unsigned long long num; const num e_key = 65537; const num d_key = 38110914516113; const num n = 119999782000099; template <class T> T mul_mod(T a, T b, T m) { if (m == 0) return a * b; T r = T(); while (a > 0) { if (a & 1) if ((r += b) > m) r %= m; a >>= 1; if ((b <<= 1) > m) b %= m; } return r; } template <class T> T pow_mod(T a, T n, T m) { T r = 1; while (n > 0) { if (n & 1) r = mul_mod(r, a, m); a = mul_mod(a, a, m); n >>= 1; } return r; } int main() { std::string msg = "Very Secret Message!"; std::vector<num> encrypted; std::cout << "Original message: " << msg << '\n'; std::transform(msg.begin(), msg.end(), std::back_inserter(encrypted), [&](num val) { return pow_mod(val, e_key, n); }); std::cout << "Encrypted message:\n"; std::copy(encrypted.begin(), encrypted.end(), std::ostream_iterator<num>(std::cout, "\n")); std::cout << "\n"; std::cout << "Decrypted message: "; std::transform(encrypted.begin(), encrypted.end(), std::ostream_iterator<char>(std::cout, ""), [](num val) { return pow_mod(val, d_key, n); }); std::cout << "\n"; }
To have any hope of security, you need to use a much larger module - at least hundreds of bits (and maybe a thousand or more for paranoid). You can do this with a regular integer library of arbitrary precision or routines written specifically for this task. RSA is inherently quite slow, so at one time most implementations used highly optimized code to do the job. Currently, the hardware is fast enough, so you can probably pretty easily handle a fairly medium large integer library (all the more so because in real use you want to use RSA only to encrypt / decrypt the key for a symmetric algorithm, and not to encrypt the raw data )
Even with a module of the right size (and code modified to support the necessary large numbers), this is still what is sometimes called the “RSA tutorial,” and it is not very suitable for the actual encryption method. For example, right now, it encrypts one byte of input at a time. This leaves noticeable patterns in the encrypted data. It is trivial to look at the encrypted data above and see that the second and seventh words are identical - because both are encrypted form e (which also occurs in a couple of other places in the message).
Currently, it can be attacked as a simple replacement code. The letter e is the most common in the English language, so we can (correctly) assume that the most common word in the encrypted data is e (and the relative frequencies of the letters in different languages are well known). Worse, we can also consider things like pairs and triples of letters to improve attack. For example, if we see the same word twice in encrypted data, we know that we see a double letter, which can be just a few letters in plain English text. Bottom line: although the RSA itself can be quite powerful, the way it is used above is definitely not.
To prevent this problem, with a (say) 512-bit key, we would also process input in 512-bit blocks. This means that we only have repetition if there are two places in the original input that go 512 bits at a time, which are all completely identical. Even if this happens, it’s pretty hard to guess what it will be, so although this is undesirable, it is not as vulnerable as in the case of the byte version shown above. In addition, you always want to complement the input with a multiple encrypted size.
Link
https://crypto.stackexchange.com/questions/1448/definition-of-textbook-rsa