Various Questions About Rsa Encryption

Various questions about RSA encryption

There are some standard formats for storing/exchanging RSA keys such as RFC 3447. For better or worse, most (many, anyway) use ASN.1 encoding, which adds more complexity than most people like, all by itself. A few use Base64 encoding, which is a lot easier to implement.

As far as what constitutes a key goes: in its most basic form, you're correct; the public key includes the modulus (usually called n) and an exponent (usually called e).

To compute a key pair, you start from two large prime numbers, usually called p and q. You compute the modulus n as p * q. You also compute a number (often called r) that's (p-1) * (q-1).

e is then a more or less randomly chosen number that's prime relative to r. Warning: you don't want e to be really small though -- log(e) >= log(n)/4 as a bare minimum.

You then compute d (the private decryption key) as a number satisfying the relation:

d * e = 1 (mod r)

You typically compute this using Euclid's algorithm, though there are other options (see below). Again, you don't want d to be really small either, so if it works out to a really small number, you probably want to try another value for e, and compute a new d to match.

There is another way to compute your e and d. You can start by finding some number K that's congruent to 1 mod r, then factor it. Put the prime factors together to get two factors of roughly equal size, and use them as e and d.

As far as an attacker computing your d goes: you need r to compute this, and knowing r depends on knowing p and q. That's exactly why/where/how factoring comes into breaking RSA. If you factor n, then you know p and q. From them, you can find r, and from r you can compute the d that matches a known e.

So, let's work through the math to create a key pair. We're going to use primes that are much too small to be effective, but should be sufficient to demonstrate the ideas involved.

So let's start by picking a p and q (of course, both need to be primes):

p = 9999991
q = 11999989

From those we compute n and r:

n = 119999782000099
r = 119999760000120

Next we need to either pick e or else compute K, then factor it to get e and d. For the moment, we'll go with your suggestion of e=65537 (since 65537 is prime, the only possibility for it and r not being relative primes would be if r was an exact multiple of 65537, which we can verify is not the case quite easily).

From that, we need to compute our d. We can do that fairly easily (though not necessarily very quickly) using the "Extended" version of Euclid's algorithm, (as you mentioned) Euler's Totient, Gauss' method, or any of a number of others.

For the moment, I'll compute it using 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 is:

d = 38110914516113

Then we can plug these into an implementation of RSA, and use them to encrypt and decrypt a message.

So, let's encrypt "Very Secret Message!". Using the e and n given above, that encrypts to:

74603288122996
49544151279887
83011912841578
96347106356362
20256165166509
66272049143842
49544151279887
22863535059597
83011912841578
49544151279887
96446347654908
20256165166509
87232607087245
49544151279887
68304272579690
68304272579690
87665372487589
26633960965444
49544151279887
15733234551614

And, using the d given above, that decrypts back to the original. Code to do the encryption/decryption (using hard-coded keys and modulus) looks like this:

#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 even a hope of security, you need to use a much larger modulus though--hundreds of bits at the very least (and perhaps a thousand or more for the paranoid). You could do that with a normal arbitrary precision integer library, or routines written specifically for the task at hand. RSA is inherently fairly slow, so at one time most implementations used code with lots of hairy optimization to do the job. Nowadays, hardware is fast enough that you can probably get away with a fairly average large-integer library fairly easily (especially since in real use, you only want to use RSA to encrypt/decrypt a key for a symmetrical algorithm, not to encrypt the raw data).

Even with a modulus of suitable size (and the code modified to support the large numbers needed), this is still what's sometimes referred to as "textbook RSA", and it's not really suitable for much in the way of real encryption. For example, right now, it's encrypting one byte of the input at a time. This leaves noticeable patterns in the encrypted data. It's trivial to look at the encrypted data above and see than the second and seventh words are identical--because both are the encrypted form of e (which also occurs a couple of other places in the message).

As it stands right now, this can be attacked as a simple substitution code. e is the most common letter in English, so we can (correctly) guess that the most common word in the encrypted data represents e (and relative frequencies of letters in various languages are well known). Worse, we can also look at things like pairs and triplets of letters to improve the attack. For example, if we see the same word twice in succession in the encrypted data, we know we're seeing a double letter, which can only be a few letters in normal English text. Bottom line: even though RSA itself can be quite strong, the way of using it shown above definitely is not.

To prevent that problem, with a (say) 512-bit key, we'd also process the input in 512-bit chunks. That means we only have a repetition if there are two places in the original input that go for 512 bits at a time that are all entirely identical. Even if that happens, it's relatively difficult to guess that that would be, so although it's undesirable, it's not nearly as vulnerable as with the byte-by-byte version shown above. In addition, you always want to pad the input to a multiple of the size being encrypted.

Reference

https://crypto.stackexchange.com/questions/1448/definition-of-textbook-rsa

RSA Encryption and Decryption on Different Machines

It seems that you don't fully understand of how public key encryption works.

Both partners have to generate their own public/private key pair. Afterwards, you share the public keys (that is, M1 sends its public key to M2 and vice versa). In reality, there is the problem of key distribution and authentication, i.e. how do I know that a public key that says it belongs to John really belongs to John? But for your small example, you can ignore this at first.

Once both machines have the partner's public keys, you encrypt a message going from M1 to M2 using M2's public key. M2 then decrypts it using its private key. Apply the same idea for the reverse direction.

That way, you never have to share any of the prime factors or the private keys (as you correctly noticed, doing that would completely break the security of the process).

Haskell RSA encryption

Looking at the definition of rsadecrypt:

rsadecrypt (d, m) x = x^d `mod` m

It should be clear that all outputs will be between 0 and m-1 (inclusive). Since decryption definitely sits in that range, you cannot create an encryption for any message outside that range that will exactly round-trip.

...and, to connect the final two dots, 97 is outside the range of 0 to 91-1, so it cannot be correctly encrypted (for this definition of "correct").

What is the difference between encrypting and signing in asymmetric encryption?

When encrypting, you use their public key to write a message and they use their private key to read it.

When signing, you use your private key to write message's signature, and they use your public key to check if it's really yours.

I want to use my private key to generate messages so only I can possibly be the sender.

I want my public key to be used to read the messages and I do not care who reads them

This is signing, it is done with your private key.

I want to be able to encrypt certain information and use it as a product key for my software.

I only care that I am the only one who can generate these.

If you only need to know it to yourself, you don't need to mess with keys to do this. You may just generate random data and keep it in a database.

But if you want people to know that the keys are really yours, you need to generate random data, keep in it a database AND sign it with your key.

I would like to include my public key in my software to decrypt/read the signature of the key.

You'll probably need to purchase a certificate for your public key from a commercial provider like Verisign or Thawte, so that people may check that no one had forged your software and replaced your public key with theirs.

RSA Encryption in java and python gives different encryption result

Stopped working on this for a while. Got back to this and found that I was making a very stupid mistake.
The Encryption is right. When I was passing password as the query parameter, I need to replace the '=', '+', '/' with url encoding.
Reference from : w3schools.com/tags/ref_urlencode.ASP.

Here is the final code that I added :

String urlSafePassword = Base64.getEncoder().encodeToString(encryptedPassWord);
            urlSafePassword.replace("/", "%2F");
            urlSafePassword.replace("+", "%2B");
            urlSafePassword.replace("=", "%3D");
            return urlSafePassword;

I kept thinking that my encrytion type.

Thanks for all the help guys.
Have a great day.

Why does RSA encrypted text give me different results for the same text

A secure RSA encryption is implemented with an appropriate padding scheme, which includes some randomness. See PKCS#1 or OAEP for more details.

The RSA encryption encrypts message padded with '0's and a string of random bit. In the process, the random string is "hidden" in the ciphertext by cryptographic hashing and XORing. On decryption, the RSA decryption recovers the random string from the ciphertext and use it to recover message. This is why you get different result with openssl rsautl for the same text message.

RSA Encryption message Length

Not impossible at all - the exponentiation is performed modulo n, which means that the result will always be less than n. This not only limits the output size, but makes the calculation easier as intermediate stages can be reduced modulo n to keep the numbers involved "small". The Wikipedia page on modular exponentiation provides more detail on how the calculation can be performed.

---

Related Topics