[Courses] [security] Crypto Scientists Crack Prime Problem

[Raven Alder]

Heya --

Quoth Sujita Purushothaman (Tue, Aug 13, 2002 at 04:42:12PM +0800):
> Life's too short for time-devouring jobs. :-)

	I wholeheartedly agree.
 
> 1. How is 'signing' different from 'encrypting' ? Is it one and the same?

	That's a really good question, and a common point of confusion.
They are not the same thing.  Signing a message digitally is indeed
different from encrypting it.  Signing is meant to prove that the
message was definitely sent by you, and was not changed in transit.
(Think of how much damage could be done if you wrote someone a letter,
and a malicious postal worker kept inserting the word "not" in key
places, or added a postscript describing your love for illegal bungee
jumping.) Encryption is meant to keep the folks in the middle from
reading the message, digital signatures keep them from undetectably
changing it.

	You can digitally sign a plaintext message if you want.  Some of
the most common implementations of digital signatures are bundled hand
in hand with encryption -- PGP allows you to sign, encrypt, or sign and
encrypt your documents.  We've already seen how public key encryption
works -- let's take a look at digital signatures.  Some of the same
technology is used, but in a different way.

	A common implementation is first to take a hash of the message.
A hash is a condensed value gotten by performing some mathematical
operations upon the content of the message.  You want to hash rather
than encrypt here because otherwise your signature runs the risk of
being as long as the message.  Hashes are generally lossy one-way
operations -- given the message, you can get the same hash every time,
but you can't derive the message just from the contents of the hash.
For example, you could hash a message by taking the ASCII value of every
character in it, adding them all together, and dividing by 17,000.   (I
completely made that up, but it would work.)  You'll end up with a
number.  Append that to your plaintext message.  When the other party
gets the message, they can perform the same hashing operation.  If they
get the same number that's been appended to the message, they can be
reasonably sure that it hasn't changed in transit.

	"But wait!", you cry.  "If they can change the data in transit,
surely they can also change the value of the hash to match!  Then you
wouldn't be able to tell it's been modified!"  Right you are.  So, once
the message has been hashed, that hash is encrypted with your private
key.  The recipient will be able to verify the hash using your public
key to decrypt the hash, and then use the same hashing algorithm to make
sure that the values match.  An attacker could change the hash, but
since they don't have your private key, they can't encrypt the hash
again.  So if you get a message with a hash that decrypts with the
sender's public key, and the hash values match, you know that it was
signed by the actual sender and that the contents didn't change in
transit.**

	** A picky note:  There are different documents that will
produce the same hash.  So it is theoretically possible to make a change
in such a way that the hashing function returns the same value for the
new document, though this is extremely mathematically unlikely.  This is
a possible avenue for attack on this sort of digital signature.

	In the real world, a common hashing algorithm is Ron Rivest's
Message Digest algorithm MD5.  He's the R in RSA.  [grin]  It produces a
hash with less chance of being able to change the message and get then
same hash than my theoretical "add up the ASCII and divide by 17,000"
does.  So the combination of MD5 hashing and public key infrastructure
(PKI) allows digital signatures.  There are other, more complex ways to
do the same thing with digital certificates.  But that's a whole other
mail.  [grin]

> 2. have you heard about the 'Expert Encryption System' ? Some info is
> here : http://www.chantilley.com/html/news3.htm Is it any good?

	I hadn't run across it before, I don't think.  I'd have to see
details on how it actually works before I could offer an opinion as to
whether it's likely to be any good.  The ITU citing is a good thing, but
so much of good crypto is in the implementation.  I'd have to see
details.

	Anyone else run across this?

Cheers,
Raven
 
"Do you know where the RSA t-shirt is?"
"No." 
"Well, I need the algorithm, so I'm doing laundry."
  -- me and RavenBlack