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