Info Node: (nettle.info)RSA
nettle.info: RSA
Public-key algorithms 
DSA 
Public-key algorithms 
Back to Software Index
7.7.1 RSA
---------
The RSA algorithm was the first practical digital signature algorithm
that was constructed. It was described 1978 in a paper by Ronald
Rivest, Adi Shamir and L.M. Adleman, and the technique was also patented
in the USA in 1983. The patent expired on September 20, 2000, and since
that day, RSA can be used freely, even in the USA.
It’s remarkably simple to describe the trapdoor function behind RSA.
The “one-way”-function used is
F(x) = x^e mod n
I.e. raise x to the ‘e’’th power, while discarding all multiples of
‘n’. The pair of numbers ‘n’ and ‘e’ is the public key. ‘e’ can be
quite small, even ‘e = 3’ has been used, although slightly larger
numbers are recommended. ‘n’ should be about 2000 bits or larger.
If ‘n’ is large enough, and properly chosen, the inverse of F, the
computation of ‘e’’th roots modulo ‘n’, is very difficult. But, where’s
the trapdoor?
Let’s first look at how RSA key-pairs are generated. First ‘n’ is
chosen as the product of two large prime numbers ‘p’ and ‘q’ of roughly
the same size (so if ‘n’ is 2000 bits, ‘p’ and ‘q’ are about 1000 bits
each). One also computes the number ‘phi = (p-1)(q-1)’, in mathematical
speak, ‘phi’ is the order of the multiplicative group of integers modulo
n.
Next, ‘e’ is chosen. It must have no factors in common with ‘phi’
(in particular, it must be odd), but can otherwise be chosen more or
less randomly. ‘e = 65537’ is a popular choice, because it makes
raising to the ‘e’’th power particularly efficient, and being prime, it
usually has no factors common with ‘phi’.
Finally, a number ‘d’, ‘d < n’ is computed such that ‘e d mod phi =
1’. It can be shown that such a number exists (this is why ‘e’ and
‘phi’ must have no common factors), and that for all x,
(x^e)^d mod n = x^(ed) mod n = (x^d)^e mod n = x
Using Euclid’s algorithm, ‘d’ can be computed quite easily from ‘phi’
and ‘e’. But it is still hard to get ‘d’ without knowing ‘phi’, which
depends on the factorization of ‘n’.
So ‘d’ is the trapdoor, if we know ‘d’ and ‘y = F(x)’, we can recover
x as ‘y^d mod n’. ‘d’ is also the private half of the RSA key-pair.
The most common signature operation for RSA is defined in ‘PKCS#1’, a
specification by RSA Laboratories. The message to be signed is first
hashed using a cryptographic hash function, e.g. MD5 or SHA1. Next,
some padding, the ASN.1 “Algorithm Identifier” for the hash function,
and the message digest itself, are concatenated and converted to a
number ‘x’. The signature is computed from ‘x’ and the private key as
‘s = x^d mod n’(1) (Note: RSA-Footnote-1). The signature, ‘s’ is a
number of about the same size of ‘n’, and it usually encoded as a
sequence of octets, most significant octet first.
The verification operation is straight-forward, ‘x’ is computed from
the message in the same way as above. Then ‘s^e mod n’ is computed, the
operation returns true if and only if the result equals ‘x’.
The RSA algorithm can also be used for encryption. RSA encryption
uses the public key ‘(n,e)’ to compute the ciphertext ‘m^e mod n’. The
‘PKCS#1’ padding scheme will use at least 8 random and non-zero octets,
using M of the form ‘[00 02 padding 00 plaintext]’. It is required that
‘m < n’, and therefor the plaintext must be smaller than the octet size
of the modulo ‘n’, with some margin.
To decrypt the message, one needs the private key to compute ‘m = c^e
mod n’ followed by checking and removing the padding.
7.7.1.1 Nettle’s RSA support
............................
Nettle represents RSA keys using two structures that contain large
numbers (of type ‘mpz_t’).
-- Context struct: rsa_public_key size n e
‘size’ is the size, in octets, of the modulo, and is used
internally. ‘n’ and ‘e’ is the public key.
-- Context struct: rsa_private_key size d p q a b c
‘size’ is the size, in octets, of the modulo, and is used
internally. ‘d’ is the secret exponent, but it is not actually
used when signing. Instead, the factors ‘p’ and ‘q’, and the
parameters ‘a’, ‘b’ and ‘c’ are used. They are computed from ‘p’,
‘q’ and ‘e’ such that ‘a e mod (p - 1) = 1, b e mod (q - 1) = 1, c
q mod p = 1’.
Before use, these structs must be initialized by calling one of
-- Function: void rsa_public_key_init (struct rsa_public_key *PUB)
-- Function: void rsa_private_key_init (struct rsa_private_key *KEY)
Calls ‘mpz_init’ on all numbers in the key struct.
and when finished with them, the space for the numbers must be
deallocated by calling one of
-- Function: void rsa_public_key_clear (struct rsa_public_key *PUB)
-- Function: void rsa_private_key_clear (struct rsa_private_key *KEY)
Calls ‘mpz_clear’ on all numbers in the key struct.
In general, Nettle’s RSA functions deviates from Nettle’s “no memory
allocation”-policy. Space for all the numbers, both in the key structs
above, and temporaries, are allocated dynamically. For information on
how to customize allocation, see Note: GMP Allocation.
When you have assigned values to the attributes of a key, you must
call
-- Function: int rsa_public_key_prepare (struct rsa_public_key *PUB)
-- Function: int rsa_private_key_prepare (struct rsa_private_key *KEY)
Computes the octet size of the key (stored in the ‘size’ attribute,
and may also do other basic sanity checks. Returns one if
successful, or zero if the key can’t be used, for instance if the
modulo is smaller than the minimum size needed for RSA operations
specified by PKCS#1.
For each operation using the private key, there are two variants,
e.g., ‘rsa_sha256_sign’ and ‘rsa_sha256_sign_tr’. The former function
is older, and it should be avoided, because it provides no defenses
against side-channel attacks. The latter function use randomized RSA
blinding, which defends against timing attacks using chosen-ciphertext,
and it also checks the correctness of the private key computation using
the public key, which defends against software or hardware errors which
could leak the private key.
Before signing or verifying a message, you first hash it with the
appropriate hash function. You pass the hash function’s context struct
to the RSA signature function, and it will extract the message digest
and do the rest of the work. There are also alternative functions that
take the hash digest as argument.
There is currently no support for using SHA224 or SHA384 with RSA
signatures, since there’s no gain in either computation time nor message
size compared to using SHA256 and SHA512, respectively.
Creating an RSA signature is done with one of the following
functions:
-- Function: int rsa_md5_sign_tr(const struct rsa_public_key *PUB,
const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, struct md5_ctx *HASH, mpz_t
SIGNATURE)
-- Function: int rsa_sha1_sign_tr(const struct rsa_public_key *PUB,
const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, struct sha1_ctx *HASH, mpz_t
SIGNATURE)
-- Function: int rsa_sha256_sign_tr(const struct rsa_public_key *PUB,
const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, struct sha256_ctx *HASH, mpz_t
SIGNATURE)
-- Function: int rsa_sha512_sign_tr(const struct rsa_public_key *PUB,
const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, struct sha512_ctx *HASH, mpz_t
SIGNATURE)
The signature is stored in SIGNATURE (which must have been
‘mpz_init’’ed earlier). The hash context is reset so that it can
be used for new messages. The RANDOM_CTX and RANDOM pointers are
used to generate the RSA blinding. Returns one on success, or zero
on failure. Signing fails if an error in the computation was
detected, or if the key is too small for the given hash size, e.g.,
it’s not possible to create a signature using SHA512 and a 512-bit
RSA key.
-- Function: int rsa_md5_sign_digest_tr(const struct rsa_public_key
*PUB, const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, const uint8_t *DIGEST, mpz_t
SIGNATURE)
-- Function: int rsa_sha1_sign_digest_tr(const struct rsa_public_key
*PUB, const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, const uint8_t *DIGEST, mpz_t
SIGNATURE)
-- Function: int rsa_sha256_sign_digest_tr(const struct rsa_public_key
*PUB, const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, const uint8_t *DIGEST, mpz_t
SIGNATURE)
-- Function: int rsa_sha512_sign_digest_tr(const struct rsa_public_key
*PUB, const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, const uint8_t *DIGEST, mpz_t
SIGNATURE)
Creates a signature from the given hash digest. DIGEST should
point to a digest of size ‘MD5_DIGEST_SIZE’, ‘SHA1_DIGEST_SIZE’,
‘SHA256_DIGEST_SIZE’, or ‘SHA512_DIGEST_SIZE’respectively. The
signature is stored in SIGNATURE (which must have been
‘mpz_init’:ed earlier). Returns one on success, or zero on
failure.
-- Function: int rsa_pkcs1_sign_tr(const struct rsa_public_key *PUB,
const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, size_t LENGTH, const uint8_t
*DIGEST_INFO, mpz_t SIGNATURE)
Similar to the above ‘_sign_digest_tr’ functions, but the input is
not the plain hash digest, but a PKCS#1 “DigestInfo”, an ASN.1
DER-encoding of the digest together with an object identifier for
the used hash algorithm.
-- Function: int rsa_md5_sign (const struct rsa_private_key *KEY,
struct md5_ctx *HASH, mpz_t SIGNATURE)
-- Function: int rsa_sha1_sign (const struct rsa_private_key *KEY,
struct sha1_ctx *HASH, mpz_t SIGNATURE)
-- Function: int rsa_sha256_sign (const struct rsa_private_key *KEY,
struct sha256_ctx *HASH, mpz_t SIGNATURE)
-- Function: int rsa_sha512_sign (const struct rsa_private_key *KEY,
struct sha512_ctx *HASH, mpz_t SIGNATURE)
The signature is stored in SIGNATURE (which must have been
‘mpz_init’’ed earlier). The hash context is reset so that it can
be used for new messages. Returns one on success, or zero on
failure. Signing fails if the key is too small for the given hash
size, e.g., it’s not possible to create a signature using SHA512
and a 512-bit RSA key.
-- Function: int rsa_md5_sign_digest (const struct rsa_private_key
*KEY, const uint8_t *DIGEST, mpz_t SIGNATURE)
-- Function: int rsa_sha1_sign_digest (const struct rsa_private_key
*KEY, const uint8_t *DIGEST, mpz_t SIGNATURE);
-- Function: int rsa_sha256_sign_digest (const struct rsa_private_key
*KEY, const uint8_t *DIGEST, mpz_t SIGNATURE);
-- Function: int rsa_sha512_sign_digest (const struct rsa_private_key
*KEY, const uint8_t *DIGEST, mpz_t SIGNATURE);
Creates a signature from the given hash digest; otherwise
analoguous to the above signing functions. DIGEST should point to
a digest of size ‘MD5_DIGEST_SIZE’, ‘SHA1_DIGEST_SIZE’,
‘SHA256_DIGEST_SIZE’, or ‘SHA512_DIGEST_SIZE’, respectively. The
signature is stored in SIGNATURE (which must have been
‘mpz_init’:ed earlier). Returns one on success, or zero on
failure.
-- Function: int rsa_pkcs1_sign(const struct rsa_private_key *KEY,
size_t LENGTH, const uint8_t *DIGEST_INFO, mpz_t S)
Similar to the above _sign_digest functions, but the input is not
the plain hash digest, but a PKCS#1 “DigestInfo”, an ASN.1
DER-encoding of the digest together with an object identifier for
the used hash algorithm.
Verifying an RSA signature is done with one of the following
functions:
-- Function: int rsa_md5_verify (const struct rsa_public_key *KEY,
struct md5_ctx *HASH, const mpz_t SIGNATURE)
-- Function: int rsa_sha1_verify (const struct rsa_public_key *KEY,
struct sha1_ctx *HASH, const mpz_t SIGNATURE)
-- Function: int rsa_sha256_verify (const struct rsa_public_key *KEY,
struct sha256_ctx *HASH, const mpz_t SIGNATURE)
-- Function: int rsa_sha512_verify (const struct rsa_public_key *KEY,
struct sha512_ctx *HASH, const mpz_t SIGNATURE)
Returns 1 if the signature is valid, or 0 if it isn’t. In either
case, the hash context is reset so that it can be used for new
messages.
-- Function: int rsa_md5_verify_digest (const struct rsa_public_key
*KEY, const uint8_t *DIGEST, const mpz_t SIGNATURE)
-- Function: int rsa_sha1_verify_digest (const struct rsa_public_key
*KEY, const uint8_t *DIGEST, const mpz_t SIGNATURE)
-- Function: int rsa_sha256_verify_digest (const struct rsa_public_key
*KEY, const uint8_t *DIGEST, const mpz_t SIGNATURE)
-- Function: int rsa_sha512_verify_digest (const struct rsa_public_key
*KEY, const uint8_t *DIGEST, const mpz_t SIGNATURE)
Returns 1 if the signature is valid, or 0 if it isn’t. DIGEST
should point to a digest of size ‘MD5_DIGEST_SIZE’,
‘SHA1_DIGEST_SIZE’, ‘SHA256_DIGEST_SIZE’, or ‘SHA512_DIGEST_SIZE’
respectively.
-- Function: int rsa_pkcs1_verify(const struct rsa_public_key *KEY,
size_t LENGTH, const uint8_t *DIGEST_INFO, const mpz_t
SIGNATURE)
Similar to the above _verify_digest functions, but the input is not
the plain hash digest, but a PKCS#1 “DigestInfo”, and ASN.1
DER-encoding of the digest together with an object identifier for
the used hash algorithm.
While the above functions for the RSA signature operations use the
‘PKCS#1’ padding scheme, Nettle also provides the variants based on the
PSS padding scheme, specified in ‘RFC 3447’. These variants take
advantage of a randomly choosen salt value, which could enhance the
security by causing output to be different for equivalent inputs.
However, assuming the same security level as inverting the RSA
algorithm, a longer salt value does not always mean a better security
<http://www.iacr.org/archive/eurocrypt2002/23320268/coron.pdf>. The
typical choices of the length are between 0 and the digest size of the
underlying hash function.
Creating an RSA signature with the PSS padding scheme is done with
one of the following functions:
-- Function: int rsa_pss_sha256_sign_digest_tr(const struct
rsa_public_key *PUB, const struct rsa_private_key *KEY, void
*RANDOM_CTX, nettle_random_func *RANDOM, size_t SALT_LENGTH,
const uint8_t *SALT, const uint8_t *DIGEST, mpz_t SIGNATURE)
-- Function: int rsa_pss_sha384_sign_digest_tr(const struct
rsa_public_key *PUB, const struct rsa_private_key *KEY, void
*RANDOM_CTX, nettle_random_func *RANDOM, size_t SALT_LENGTH,
const uint8_t *SALT, const uint8_t *DIGEST, mpz_t SIGNATURE)
-- Function: int rsa_pss_sha512_sign_digest_tr(const struct
rsa_public_key *PUB, const struct rsa_private_key *KEY, void
*RANDOM_CTX, nettle_random_func *RANDOM, size_t SALT_LENGTH,
const uint8_t *SALT, const uint8_t *DIGEST, mpz_t SIGNATURE)
Creates a signature using the PSS padding scheme. SALT should
point to a salt string of size SALT_LENGTH. DIGEST should point to
a digest of size ‘SHA256_DIGEST_SIZE’, ‘SHA384_DIGEST_SIZE’, or
‘SHA512_DIGEST_SIZE’respectively. The signature is stored in
SIGNATURE (which must have been ‘mpz_init’:ed earlier). Returns
one on success, or zero on failure.
Verifying an RSA signature with the PSS padding scheme is done with
one of the following functions:
-- Function: int rsa_pss_sha256_verify_digest (const struct
rsa_public_key *KEY, size_t SALT_LENGTH, const uint8_t
*DIGEST, const mpz_t SIGNATURE)
-- Function: int rsa_pss_sha384_verify_digest (const struct
rsa_public_key *KEY, size_t SALT_LENGTH, const uint8_t
*DIGEST, const mpz_t SIGNATURE)
-- Function: int rsa_pss_sha512_verify_digest (const struct
rsa_public_key *KEY, size_t SALT_LENGTH, const uint8_t
*DIGEST, const mpz_t SIGNATURE)
Returns 1 if the signature is valid, or 0 if it isn’t. DIGEST
should point to a digest of size ‘SHA256_DIGEST_SIZE’,
‘SHA384_DIGEST_SIZE’, or ‘SHA512_DIGEST_SIZE’ respectively.
The following function is used to encrypt a clear text message using
RSA.
-- Function: int rsa_encrypt (const struct rsa_public_key *KEY, void
*RANDOM_CTX, nettle_random_func *RANDOM, size_t LENGTH, const
uint8_t *CLEARTEXT, mpz_t CIPHERTEXT)
Returns 1 on success, 0 on failure. If the message is too long
then this will lead to a failure.
The following function is used to decrypt a cipher text message using
RSA.
-- Function: int rsa_decrypt (const struct rsa_private_key *KEY, size_t
*LENGTH, uint8_t *CLEARTEXT, const mpz_t CIPHERTEXT)
Returns 1 on success, 0 on failure. Causes of failure include
decryption failing or the resulting message being to large. The
message buffer pointed to by CLEARTEXT must be of size *LENGTH.
After decryption, *LENGTH will be updated with the size of the
message.
There is also a timing resistant version of decryption that utilizes
randomized RSA blinding.
-- Function: int rsa_decrypt_tr (const struct rsa_public_key *PUB,
const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, size_t *LENGTH, uint8_t *MESSAGE,
const mpz_t CIPHERTEXT)
Returns 1 on success, 0 on failure.
If you need to use the RSA trapdoor, the private key, in a way that
isn’t supported by the above functions Nettle also includes a function
that computes ‘x^d mod n’ and nothing more, using the CRT optimization.
-- Function: int rsa_compute_root_tr(const struct rsa_public_key *PUB,
const struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func *RANDOM, mpz_t X, const mpz_t M)
Computes ‘x = m^d’. Returns one on success, or zero if a failure
in the computation was detected.
-- Function: void rsa_compute_root (struct rsa_private_key *KEY, mpz_t
X, const mpz_t M)
Computes ‘x = m^d’.
At last, how do you create new keys?
-- Function: int rsa_generate_keypair (struct rsa_public_key *PUB,
struct rsa_private_key *KEY, void *RANDOM_CTX,
nettle_random_func RANDOM, void *PROGRESS_CTX,
nettle_progress_func PROGRESS, unsigned N_SIZE, unsigned
E_SIZE);
There are lots of parameters. PUB and KEY is where the resulting
key pair is stored. The structs should be initialized, but you
don’t need to call ‘rsa_public_key_prepare’ or
‘rsa_private_key_prepare’ after key generation.
RANDOM_CTX and RANDOM is a randomness generator.
‘random(random_ctx, length, dst)’ should generate ‘length’ random
octets and store them at ‘dst’. For advice, see Note:
Randomness.
PROGRESS and PROGRESS_CTX can be used to get callbacks during the
key generation process, in order to uphold an illusion of progress.
PROGRESS can be NULL, in that case there are no callbacks.
SIZE_N is the desired size of the modulo, in bits. If SIZE_E is
non-zero, it is the desired size of the public exponent and a
random exponent of that size is selected. But if E_SIZE is zero,
it is assumed that the caller has already chosen a value for ‘e’,
and stored it in PUB. Returns one on success, and zero on failure.
The function can fail for example if if N_SIZE is too small, or if
E_SIZE is zero and ‘pub->e’ is an even number.
automatically generated by info2www version 1.2