2
$\begingroup$

Let's say I want to use RSA to encrypt a message 'Rocket will be launched at 2am' that has 30 letters.

I use the keys from this example: https://etherhack.co.uk/asymmetric/docs/rsa_key_breakdown.html, so the modulus is 129 bytes long (1032 bits long number). So my message is shorter than the modulus and I can encrypt it.

(Let's assume I don't use padding scheme.)

What I have to do now with my message to encrypt it?

I have to convert it to a number $m$, so I use some encoding to convert each letter to byte and I concatenate the bytes? (how do I choose that, is there a convention, will encoding and endianness be written into ASN.1 keys)

According to RSA I now have to compute: $$c(m)=m^{65537} \pmod{\text{...1032_bits_long_number...}}$$

and message is 240 bits long number. Is this the procedure?

$\endgroup$
  • 1
    $\begingroup$ Your RSA modulus is really 1024 bits. RSA math works for any size, but it is conventional to use sizes that are powers of 2 or small multiples like 1024 1536=512x3 2048 3072=1024x3. Your link shows a key as stored in ASN.1 DER and ASN.1DER/BER represents integers in two's-complement, so a positive number of exactly 8n bits (like an RSA modulus) requires an extra '00' octet to contain the sign, thus storing 1032 bits for a 1024-bit value. Your actual raw-and-horribly-weak RSA values must be < N which is not even the full range of 1024 bits. $\endgroup$ – dave_thompson_085 Nov 17 '17 at 23:33
  • 1
    $\begingroup$ Also RSA 1024 has not been considered to provide an adequate margin of safety since 2011, almost 7 years ago. The standard now is 2048, although in principle 1536 could be safe. $\endgroup$ – dave_thompson_085 Nov 17 '17 at 23:34
6
$\begingroup$

The straight-forward way to do this is:

  • Convert the ASCII string into an array of bytes.
  • Convert that byte array into a large integer. For that you need a library with support for arbitrary large integers (e.g. BigInteger)
  • Endianness does not matter for this.
  • For encryption, the library should already offer some modular exponentiation method, because otherwise you will have to write square-and-multiply yourself, where you apply the modulus after every step.
  • Decryption is the same as encryption, it's just modular exponentiation again.

Of course this is just for this basic exercise. In an actuall application, you definately need:

  • A proper padding scheme, e.g. RSA-OAEP
  • You usually don't encrypt the message directly. Instead, hybrid encryption is used in all cases, so that it doesn't matter how long the message is.
  • Follow the standards, e.g. PKC#1, section 4 for the data conversion from integers to byte strings (thanks to @MaartenBodewes for pointing that out)
  • And to be honest: You should just use an implementation of RSA (and other encryption schemes) provided by a cryptographic library.
$\endgroup$
  • 1
    $\begingroup$ You may want to mention the OS2IP and I2OSP algorithms in PKCS#1 to convert (or interpret) integers to bytes and back. I've made an implementation in Java here (of course without the stupidity of implementing them using the math that describe how the numbers are represented by the bytes). $\endgroup$ – Maarten Bodewes Nov 17 '17 at 15:58
  • $\begingroup$ Is OS2IP talking about converting array of message bytes to integer (bullet 2 from this answer)? So that according to 4.2 from the PKCS: x=R*256^29 + o*256^28 + c*256^27 + ... $\endgroup$ – croraf Nov 17 '17 at 16:38
  • $\begingroup$ How do I know I have to use ASCII encoding, is this part of PKCS or another standard (or maybe encoded in ASN.1), or we have to communicate encoding separately? $\endgroup$ – croraf Nov 17 '17 at 16:46
  • $\begingroup$ @croraf: PKCS>1< doesn't specify (anything about) encoding or other semantics of the bytes. Standards for encrypting messages (like PKCS 7 and S/MIME) generally RSA-encrypt only a key (which is bytes to start with), and for the symmetrically-encrypted data they don't specify encoding but sometimes enable users to do so. In practice most things this century either use ASCII or Unicode -- and they usually encode Unicode in UTF-8 which by design is compatible with ASCII. $\endgroup$ – dave_thompson_085 Nov 17 '17 at 23:48
  • 1
    $\begingroup$ @croraf You don't have to use ASCII encoding. It is just one possible way to do this, and it is quite convenient as there are usually built-in functions for conversion. You could also use arithmetic encoding, but you probably have to write that yourself. But usually, encodings and format are outside of scope of cryptosystems - they work for anything that can be expressed as message with a bounded number of bits - but how you interpret those bits is completely up to you. $\endgroup$ – tylo Nov 20 '17 at 12:28
3
$\begingroup$

It's too late—you've already revealed your message to the world!

‘But no,’ you say. ‘That was just an example message. The real messages aren't that.’ In that case, what is the distribution on real messages? Your job, in fitting it into RSA, is to map the distribution on real messages into a uniform distribution on elements of $\mathbb Z/n\mathbb Z$.

Why? The RSA trapdoor permutation is good at concealing a uniform distribution on $\mathbb Z/n\mathbb Z$, but terrible at concealing other distributions. For example, if all your messages were under 256 bits long, and the exponent were $e = 3$ (which is a completely sensible choice for sensible RSA-based encryption schemes), then anyone could take a ciphertext $c$ as an integer and compute the real number cube root to recover the plaintext.

So do you have $n$ different messages, where $2^{1031} < n < 2^{1032}$, or something very near it? If not, then because of the modulo bias, you may find it difficult to shoehorn your message distribution into a near-uniform distribution on $\mathbb Z/n\mathbb Z$. That is why sensible RSA-based encryption schemes do not attempt to shoehorn messages themselves into elements of $\mathbb Z/n\mathbb Z$ for the RSA trapdoor permutation.

For example, RSA-KEM simply picks an element $x \in \mathbb Z/n\mathbb Z$ uniformly at random, independent of your message; conceals it as $y \equiv x^3 \pmod n$; and uses the hash $H(x)$ as a secret key for a standard AEAD scheme such as AES-GCM to hide your message. Unlike the RSA trapdoor permutation, AES-GCM is really good at concealing messages of arbitrary lengths with arbitrary distributions.

Other kludgier RSA-based encryption schemes such as RSAES-OAEP try hard to shoehorn certain classes of messages, like up to 256-bit keys, into $\mathbb Z/n\mathbb Z$, which are the ‘padding schemes’ you sometimes hear of. These are much more complicated to work with and understand, so I don't bother with the details, but they are perhaps more widely used because of the historical mistake of focusing on using the RSA trapdoor permutation as a public-key encryption scheme rather than a public-key key encapsulation method.

$\endgroup$
  • $\begingroup$ Whaaaat? :D. This is way too advanced for me to understand. $\endgroup$ – croraf Nov 17 '17 at 17:09
  • $\begingroup$ Is there a part of this message you find particularly confusing on which you would like elaboration? $\endgroup$ – Squeamish Ossifrage Nov 17 '17 at 17:12
  • $\begingroup$ chat.stackexchange.com/rooms/68896/… $\endgroup$ – croraf Nov 17 '17 at 17:15
  • $\begingroup$ The RSA trapdoor permutation is good at concealing a uniform distribution on Z/nZZ/nZ, but terrible at concealing other distributions do you have some more resources about that please? $\endgroup$ – gusto2 Nov 26 '17 at 22:51
2
$\begingroup$

(Let's assume I don't use padding scheme.)

Padding is very important part, never do RSA without padding in reality. Now lets assume you are doing schoolbook - learning excercise.

What I have to do now with my message to encrypt it?

the most practical way until now is hybrid encryption but I believe you want to do pen-and-pencil RSA (is it so?)

I have to convert it to a number m, so I use some encoding to convert each letter to byte and I concatenate the bytes?

Indeed, all operations are over array of bytes at the end. It's up to you to how you make the byte array (or rather - bit array for RSA) from your message. For schoolbook text you can just concatenate the ascii of the message characters

is there a convention, will encoding and endianness be written into ASN.1 keys

you see, I always use out-of-box libraries to read and parse the keys, so I don't really recall how the ASN.1 format stores the numbers. I strongly believe the first bit is the most significant (big-endian), however I really may be wrong (if someone knows, please correct).

However with RSA itself - it doesn't matter in this case

According to RSA I now have to compute: c(m)=m^65537 (mod ...1032_bits_long_number...)

yes, you need to do $c = M^e\ mod\ n$
you could use exponentiation by squaring which is just shitfing $e$ and summing. Though for 1024 but key you will do it... many times if you are doing it by hand.

$\endgroup$
  • $\begingroup$ Thanks! I'm doing a study not real life encryption. What I want to know if I use a module for encryption and you use another for decryption, and we agree to use RSA and I provide you ASN.1 (or PEM) public key, will you have the info of how to convert plain text into array of bytes and how to convert this array of bytes into big integer so you can do the RSA encoding? $\endgroup$ – croraf Nov 17 '17 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.