0
$\begingroup$

I've recently asked a question about RSA encryption. One of the things that I don't understand is the usage of two public keys.

In the example on Wikipedia, a message is encrypted like:

c(m) = m ^ e % n

This means that I need e and n to do an encryption. Also, in the article m is defined as plaintext but represented as an integer.

My two questions are:

  1. How do I combine e and n to be one public key?
  2. How should plaintext be formatted to be used in the Wikipedia example?

PS: RSA public key generation is based on this Wikipedia article.

PPS: Here is an example of an online RSA generation tool, I don't understand how those hashes are created based on the Wikipedia example.

$\endgroup$
2
$\begingroup$

An RSA public key is made of 2 parts, the modulus n and the exponent e. They are both required, and neither alone can be considered "the key". Often e will be one of just a few different values, but this is mostly convention and shouldn't be assumed.

RSA does work on integers; if your data is of another form, you have to specify how to convert it. For instance, if you have text you might encode it to a byte array with UTF-8, then take blocks of bytes such that the number if bits is less than the length of n, and then treat that byte array as one big integer (either little-endian or big-endian).

But you probably don't want to be doing this math yourself, and there are a lot of pitfalls (padding, etc) to trap the unwary. You should be using a library that someone has already implemented.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks @bmm6o, I'm writing this script to help me understand cryptography better. So I'm trying to write it myself :-) But the goal is not to use it in production, it's to help myself and others understand the principles better. $\endgroup$ – Bob van Luijt Nov 2 '15 at 11:28
1
$\begingroup$

How do I combine $e$ and $n$ to be one public key?

The two components of the public key are indeed the modulus and the public exponent. It doesn't really matter how they are stored together, as long as the two components can be reconstructed afterwards.

The most common way is probably using the ASN.1 specification and DER encryption of RSAPublicKey as specified in the PKCS#1 standards. That in turn may be wrapped by a SubjectPublicKeyInfo structure in X.509 certificates and certificate requests. PGP and SSH - for instance - may however use different formats.

How should plaintext be formatted to be used in the Wikipedia example?

The Wikipedia article specifies textbook RSA or raw RSA. In that case the message is usually directly converted into a number. The size of the resulting number should be less than $n$ though. Again, how this conversion is performed is inconsequential to RSA. A common method would be to encode the text using ASCII or UTF-8 and then treat the result as unsigned big endian value.

Secure padding schemes, as specified by the aforementioned PKCS#1 specifications, however expect the message to be represented by bytes. The result after padding is then converted into a number to be used in modular exponentiation.

| improve this answer | |
$\endgroup$
1
$\begingroup$

@bmm6o already answered your main question.

To answer your PPS: the data shown on that webpage is not a hash of any kind. It is an encoding of a structure, using a method called PEM, originally developed for a complete Privacy Enhanced Mail scheme which fell by the wayside, but the PEM encoding is still used a good deal in cryptography. In general that consists of "BEGIN" and "END" lines surrounding base64-encoded data, which is usually an ASN.1 DER structure. For a public key, the DER structure is the SubjectPublicKeyInfo field defined by X.509, the most widely used standard for digital certificates. For example the initial (apparently default) value I see on the webpage

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCrSwmLyDboN9ElaE2gv42VqkKq
en2NWg4nyBd+1by70lwAPMuEuUiIvSb+5f52wH93zPEdt0W/2ugMQB24eprS+2Gy
PEllSB8o7sPOMgNV3KYAWjCTllpoCCjPcbNNPaFr7Lq/31yC9fBcgcgStz77xmUB
etNPd6J0OKj3vDLBSwIDAQAB
-----END PUBLIC KEY-----

decodes as a structure containing the following RSA public key (displayed by OpenSSL in hex)

Modulus:
    00:ab:4b:09:8b:c8:36:e8:37:d1:25:68:4d:a0:bf:
    8d:95:aa:42:aa:7a:7d:8d:5a:0e:27:c8:17:7e:d5:
    bc:bb:d2:5c:00:3c:cb:84:b9:48:88:bd:26:fe:e5:
    fe:76:c0:7f:77:cc:f1:1d:b7:45:bf:da:e8:0c:40:
    1d:b8:7a:9a:d2:fb:61:b2:3c:49:65:48:1f:28:ee:
    c3:ce:32:03:55:dc:a6:00:5a:30:93:96:5a:68:08:
    28:cf:71:b3:4d:3d:a1:6b:ec:ba:bf:df:5c:82:f5:
    f0:5c:81:c8:12:b7:3e:fb:c6:65:01:7a:d3:4f:77:
    a2:74:38:a8:f7:bc:32:c1:4b
Exponent: 65537 (0x10001)

which as you see does contain a (large) modulus and a (small, conventional) public exponent.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks @dave_thompson_085, I'm not sure that I understand how PEM is used in this context. Are you maybe able to give a small example? $\endgroup$ – Bob van Luijt Nov 2 '15 at 11:31
  • $\begingroup$ I just gave you an example, using the data on that webpage: it displays both a private key and a public key for RSA in PEM formats, but since your question was about public key I used the public key. That PEM (SPKI) encoding of an RSA public key includes the values you asked about, namely the modulus (n) and the public exponent (e). I'm afraid I don't see how to make it clearer. $\endgroup$ – dave_thompson_085 Nov 4 '15 at 1:39

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.