Return to Answer

deleted 140 characters in body

Source Link

edited Apr 4, 2014 at 9:53

Here are two alternatives to ECDSA which was already mentioned:

RSA-PSS with message recovery -- RSA signatures are at least as long as the modulus. But RSA-PSS with message recovery allows to pack part (or all) of the data you want to sign into the signature itself. Verification of RSA signatures is also pretty fast. If the message you want to sign is not much shorter than the RSA modulus the size overhead will be very small. (See example below)
EdDSA -- also a method based on an elliptic curve, but supposedly faster and easier to implement in a safe way than ECDSA. These kinds of signatures take up 4s bits for a security of s bits.

Example for RSA-PSS with message recovery:

RSA modulus: 3072 bits
hash: SHA-256
salt: 64 random bits

Then, the signature of 3072 bits (384 bytes) stores a 256 bit hash (32 bytes), a 64 bit salt (8 bytes), and two fixed bytes (I think). That leaves room for up to 342 message bytes. So, for a 342-byte message you sign and encode this wayof at least 342 bytes you'll have an overhead of only 42 bytes (336 bits) at a security level of "128" (not "80"). You might want to add a "key ID" to this so that the program that tries to decode and verify this knows which public key to use.

Here are two alternatives to ECDSA which was already mentioned:

RSA-PSS with message recovery -- RSA signatures are at least as long as the modulus. But RSA-PSS with message recovery allows to pack part (or all) of the data you want to sign into the signature itself. Verification of RSA signatures is also pretty fast. If the message you want to sign is not much shorter than the RSA modulus the size overhead will be very small. (See example below)
EdDSA -- also a method based on an elliptic curve, but supposedly faster and easier to implement in a safe way than ECDSA. These kinds of signatures take up 4s bits for a security of s bits.

Example for RSA-PSS with message recovery:

RSA modulus: 3072 bits
hash: SHA-256
salt: 64 random bits

Then, the signature of 3072 bits (384 bytes) stores a 256 bit hash (32 bytes), a 64 bit salt (8 bytes), and two fixed bytes (I think). That leaves room for up to 342 message bytes. So, for a 342-byte message you sign and encode this way you'll have an overhead of 42 bytes (336 bits) at a security level of "128" (not "80"). You might want to add a "key ID" to this so that the program that tries to decode and verify this knows which public key to use.

Here are two alternatives to ECDSA which was already mentioned:

RSA-PSS with message recovery -- RSA signatures are at least as long as the modulus. But RSA-PSS with message recovery allows to pack part (or all) of the data you want to sign into the signature itself. Verification of RSA signatures is also pretty fast. If the message you want to sign is not much shorter than the RSA modulus the size overhead will be very small. (See example below)
EdDSA -- also a method based on an elliptic curve, but supposedly faster and easier to implement in a safe way than ECDSA. These kinds of signatures take up 4s bits for a security of s bits.

Example for RSA-PSS with message recovery:

RSA modulus: 3072 bits
hash: SHA-256
salt: 64 random bits

Source Link

created Apr 4, 2014 at 9:45

sellibitze

Here are two alternatives to ECDSA which was already mentioned:

RSA-PSS with message recovery -- RSA signatures are at least as long as the modulus. But RSA-PSS with message recovery allows to pack part (or all) of the data you want to sign into the signature itself. Verification of RSA signatures is also pretty fast. If the message you want to sign is not much shorter than the RSA modulus the size overhead will be very small. (See example below)
EdDSA -- also a method based on an elliptic curve, but supposedly faster and easier to implement in a safe way than ECDSA. These kinds of signatures take up 4s bits for a security of s bits.

Example for RSA-PSS with message recovery:

RSA modulus: 3072 bits
hash: SHA-256
salt: 64 random bits

Then, the signature of 3072 bits (384 bytes) stores a 256 bit hash (32 bytes), a 64 bit salt (8 bytes), and two fixed bytes (I think). That leaves room for up to 342 message bytes. So, for a 342-byte message you sign and encode this way you'll have an overhead of 42 bytes (336 bits) at a security level of "128" (not "80"). You might want to add a "key ID" to this so that the program that tries to decode and verify this knows which public key to use.