You instead create a SHA-1 (or better) cryptographic hash of your data and then you push the hash through the RSA encryption algorithm with your private key. This is called signing. Verification is done by using the public key to restore the cryptographic hash from encrypted form and then checking if the data hash and restored hash match. The properties of hashes add resistance to the RSA algorithm in that it prevents various kinds of attack such as known data. It also means that a single signature is sufficient for a payload of practically any size. The payload could even be left in plain text form (unless you purposely want to obfuscate it) since there is no reasonable way to make changes that will bypass signature verification.
@ImperialGood: Go
Please read a bit about subject before posting on forum to not mistake people ;) I will just point out some bull*hits in your post, so next time please think about it twice.
1. Rsa encryption and rsa signing are 2 different things handled by separate cryptosystems. They just use common public key algorithm.
2. Properties of hashes (in the way you describe it) do nothing to improve resistance of RSA, they even decrease it (instead of breaking rsa you may as well break hash, and sign any message with it).
3. You don't "apply rsa" to hash (as you wrote in previous message), first you pad message with appropriate padding and then apply rsa (just google "why textbook rsa is bad").
1.1. Rsa encryption and rsa signing are 2 different things handled by separate cryptosystems. They just use common public key algorithm.
Quote:
3.3. You don't "apply rsa" to hash (as you wrote in previous message), first you pad message with appropriate padding and then apply rsa (just google "why textbook rsa is bad").
Suppose Alice wishes to send a signed message to Bob. She can use her own private key to do so. She produces a hash value of the message, raises it to the power of d (modulo n) (as she does when decrypting a message), and attaches it as a "signature" to the message.
Which means that another algorithm is required to generate the hash and that you first generate a hash and encrypt the hash using RSA.
Quote:
2.2. Properties of hashes (in the way you describe it) do nothing to improve resistance of RSA, they even decrease it (instead of breaking rsa you may as well break hash, and sign any message with it).
Firstly the hash function is public and not an issue. In fact you want people to be able to generate the hash as that is what you use to verify the integrity of the message. The security comes by the asymmetric encryption of the hash. To sign the data you need the private key to encrypt the hash. The clients verify by having the public key to descramble the signature into the hash. If the data has been modified the hash from the descrambled signature will mismatch so the data can be discarded. If the signature has been modified randomly it will descramble into something different which will then mismatch with the hash computed from the data and so the data can be discarded. In order to generate a valid signature for the data the private key is needed hence it is as secure as RSA and the private key.
Wikipedia supports this to some degree.
Quote:
To prevent attacks, one can first apply a cryptographic hash function to the message m and then apply the RSA algorithm described above to the result. This approach can be proven secure in the so-called random oracle model[clarification needed].
Since cryptographic hash functions have this property...
Quote:
Stated differently, a random oracle is a random mathematical function, that is, a function mapping each possible query to a (fixed) random response from its output domain.
This adds resistance by disallowing control over the data being encrypted (as the hash function controls what is encrypted). The chance of a hacker being able to generate a meaningful payload with a hash of a specific value is practically impossible.
I am aware there are more steps involved with signing.
Generate cryptographic hash of data to sign.
Pad cryptographic hash with secure padding.
Encrypt hash with padding using private key.
And for the inverse direction...
Decrypt hash with padding using public key.
Verify and strip padding from hash.
Generate cryptographic hash of data to verify and compare with the stripped hash.
@ImperialGood: Go
I suggest using better sources of information than wikipeida, because we're talking about implementation of RSA, not wondering what is it. Therefore lectures such as PKCS #1 or RFC 3447 would be more appropriate. Let me quote part of RFC 3447:
Quote:
A scheme combines cryptographic primitives and other techniques to achieve a particular security goal. Two types of scheme are specified in this document: encryption schemes and signature schemes with appendix.
There are several reasons to sign such a hash (or message digest) instead of the whole document.
For efficiency: The signature will be much shorter and thus save time since hashing is generally much faster than signing in practice.
For compatibility: Messages are typically bit strings, but some signature schemes operate on other domains (such as, in the case of RSA, numbers modulo a composite number N). A hash function can be used to convert an arbitrary input into the proper format.
For integrity: Without the hash function, the text "to be signed" may have to be split (separated) in blocks small enough for the signature scheme to act on them directly. However, the receiver of the signed blocks is not able to recognize if all the blocks are present and in the appropriate order.
Ooops, nothing about security ;) Reading whole sources is advised, not only parts that suit your current thesis ;) In case you don't understand it i explained topic further:
Firstly the hash function is public and not an issue. In fact you want people to be able to generate the hash as that is what you use to verify the integrity of the message.
You're forgetting about fact, that hash functions are surjections, therefore exists infinite amount of messages generating this particular hash (assuming infinite memory). Because of this if you crack hash function you can sign basically anything, because hash of your message (eventually with some random bits) will be equal to hash encrypted with public key. MD4 can be cracked in realtime, cracking md5 and sha1 takes a bit longer. Cracking sha2 is question of time (there are theoretical attacks reducing complexity of computing collision), also they made sha3 for some reason, uh? Because of this RSA signing is less secure (long term) than RSA encryption, however because verifying long RSA signatures is expensive we just go with hashes that are >>currently<< good enough.
This adds resistance by disallowing control over the data being encrypted (as the hash function controls what is encrypted). The chance of a hacker being able to generate a meaningful payload with a hash of a specific value is practically impossible.
Thats purpose of padding in RSA cryptosystem(it uses random oracle model and cryptographic hashes 1) internally). Also this is not really true for hashes in long term ( as I mentioned before ), you just add weak point that will be broken faster than RSA cryptosystem.
RSA encryption is secure - you could as well encrypt message with RSA cryptosystem. It's not like signing is more secure than encryption - it's just much faster for larger input (few orders of magnitude), and it's "good enough" - that's why we sign stuff.
1) Note that hashes here are used to produce random sequence of bits that will be xored with message, and collision resistance doesn't matter.
Ooops, nothing about security ;) Reading whole sources is advised, not only parts that suit your current thesis ;) In case you don't understand it i explained topic further:
Why you apologizing? You are not making sense anymore.
Quote:
You're forgetting about fact, that hash functions are surjections, therefore exists infinite amount of messages generating this particular hash (assuming infinite memory). Because of this if you crack hash function you can sign basically anything, because hash of your message (eventually with some random bits) will be equal to hash encrypted with public key. MD4 can be cracked in realtime, cracking md5 and sha1 takes a bit longer. Cracking sha2 is question of time (there are theoretical attacks reducing complexity of computing collision), also they made sha3 for some reason, uh?
You seem to not understand the purpose of a hash. There is nothing to "crack" with a hashing algorithm? Heck the algorithms are standard and well know there is not even anything secret to them. They are purely used to generate a finite field from a possibly near infinite data source which shows low output relationship with the values input.
I think you were referring to hash collisions by these "cracks". This is when a different message has the same hash so breaks a hashtable (security risk) or can be passed off as another message (substitution). None of these apply in this case. Sure they might be able to find a collision however the collision might not be meaningful (wrong format or size). Further more if 256 bit hashes are used the chances of people finding a collision are practically near 0 and certainly not possible by the average user. In fact no one has reported collisions in 256 bit hash systems. The largest reported collisions were with SHA-1 which still wound need a large super computer to even attempt.
Since a hacker would want to make a meaningful change it is more likely they want to reverse engineer the RSA private key so they can sign off any message hash than it is for them to try generating some garbage message that fits the hash they have. As such the signature is secure.
Quote:
Thats purpose of padding in RSA cryptosystem(it uses random oracle model and cryptographic hashes 1) internally). Also this is not really true for hashes in long term ( as I mentioned before ), you just add weak point that will be broken faster than RSA cryptosystem. RSA encryption is secure - you could as well encrypt message with RSA cryptosystem. It's not like signing is more secure than encryption - it's just much faster for larger input (few orders of magnitude), and it's "good enough" - that's why we sign stuff.
It is better for the following reasons.
Hashes do not suffer from collision issues as much as you make out. Even when they do the result might be invalid. As such they are not a weakness.
It is not viable to decrypt huge messages with asymmetric encryption due to resource constraints, there is no arguing with that.
The data can still be read even if it fails verification. Encrypted data cannot be read unless decrypted and only if encrypted correctly. Possibly useful for certain features such as sandbox modes where people could bypass the checks for that session.
Simply hashing is not enough.
Which is why I never told you to simply hash.
You instead create a SHA-1 (or better) cryptographic hash of your data and then you push the hash through the RSA encryption algorithm with your private key. This is called signing. Verification is done by using the public key to restore the cryptographic hash from encrypted form and then checking if the data hash and restored hash match. The properties of hashes add resistance to the RSA algorithm in that it prevents various kinds of attack such as known data. It also means that a single signature is sufficient for a payload of practically any size. The payload could even be left in plain text form (unless you purposely want to obfuscate it) since there is no reasonable way to make changes that will bypass signature verification.
@ImperialGood: Go Please read a bit about subject before posting on forum to not mistake people ;) I will just point out some bull*hits in your post, so next time please think about it twice.
Acording to Wikipedia ( http://en.wikipedia.org/wiki/RSA_(cryptosystem) )...
Which means that another algorithm is required to generate the hash and that you first generate a hash and encrypt the hash using RSA.
Firstly the hash function is public and not an issue. In fact you want people to be able to generate the hash as that is what you use to verify the integrity of the message. The security comes by the asymmetric encryption of the hash. To sign the data you need the private key to encrypt the hash. The clients verify by having the public key to descramble the signature into the hash. If the data has been modified the hash from the descrambled signature will mismatch so the data can be discarded. If the signature has been modified randomly it will descramble into something different which will then mismatch with the hash computed from the data and so the data can be discarded. In order to generate a valid signature for the data the private key is needed hence it is as secure as RSA and the private key.
Wikipedia supports this to some degree.
Since cryptographic hash functions have this property...
This adds resistance by disallowing control over the data being encrypted (as the hash function controls what is encrypted). The chance of a hacker being able to generate a meaningful payload with a hash of a specific value is practically impossible.
I am aware there are more steps involved with signing.
And for the inverse direction...
@ImperialGood: Go I suggest using better sources of information than wikipeida, because we're talking about implementation of RSA, not wondering what is it. Therefore lectures such as PKCS #1 or RFC 3447 would be more appropriate. Let me quote part of RFC 3447:
Let me quote next part of wikipeida page that you quoted (https://en.wikipedia.org/wiki/Digital_signature):
Ooops, nothing about security ;) Reading whole sources is advised, not only parts that suit your current thesis ;) In case you don't understand it i explained topic further:
You're forgetting about fact, that hash functions are surjections, therefore exists infinite amount of messages generating this particular hash (assuming infinite memory). Because of this if you crack hash function you can sign basically anything, because hash of your message (eventually with some random bits) will be equal to hash encrypted with public key. MD4 can be cracked in realtime, cracking md5 and sha1 takes a bit longer. Cracking sha2 is question of time (there are theoretical attacks reducing complexity of computing collision), also they made sha3 for some reason, uh? Because of this RSA signing is less secure (long term) than RSA encryption, however because verifying long RSA signatures is expensive we just go with hashes that are >>currently<< good enough.
Thats purpose of padding in RSA cryptosystem(it uses random oracle model and cryptographic hashes 1) internally). Also this is not really true for hashes in long term ( as I mentioned before ), you just add weak point that will be broken faster than RSA cryptosystem. RSA encryption is secure - you could as well encrypt message with RSA cryptosystem. It's not like signing is more secure than encryption - it's just much faster for larger input (few orders of magnitude), and it's "good enough" - that's why we sign stuff.
1) Note that hashes here are used to produce random sequence of bits that will be xored with message, and collision resistance doesn't matter.
Why you apologizing? You are not making sense anymore.
You seem to not understand the purpose of a hash. There is nothing to "crack" with a hashing algorithm? Heck the algorithms are standard and well know there is not even anything secret to them. They are purely used to generate a finite field from a possibly near infinite data source which shows low output relationship with the values input.
I think you were referring to hash collisions by these "cracks". This is when a different message has the same hash so breaks a hashtable (security risk) or can be passed off as another message (substitution). None of these apply in this case. Sure they might be able to find a collision however the collision might not be meaningful (wrong format or size). Further more if 256 bit hashes are used the chances of people finding a collision are practically near 0 and certainly not possible by the average user. In fact no one has reported collisions in 256 bit hash systems. The largest reported collisions were with SHA-1 which still wound need a large super computer to even attempt.
Since a hacker would want to make a meaningful change it is more likely they want to reverse engineer the RSA private key so they can sign off any message hash than it is for them to try generating some garbage message that fits the hash they have. As such the signature is secure.
It is better for the following reasons.
I'm happy that you agree with me :) Still not 100% right, but dragging this discussion is pointless. Have a nice day.