Cryptography using key

Problem:

(a) Suppose that there are n people who want to communicate with each other securely. How many keys are needed when a symmetric key cryptosystem is used? How about public key cryptosystem? Explain.

(b) Digital signatures cannot be done using symmetric key cryptography. Explain why.

(c) Suppose we produce a “digest” of a message by simply adding up the words (e.g., treating each character as a 8-bit number). What is the problem of this approach?


Follow-up:

(a) Using symmetric keys, the number of keys required for pair-wise communication is nC2 = n (n –1)/2. Using public key cryptosystem, the number 2 of keys require is just 2n (one public key and one private for each user).

(b) One of the most important requirements in digital signatures is non-repudiation—the signer cannot deny that a signature is produced by him/her. Thus, we need a “secret” that is bound to and only to each user. Using symmetric key cryptosystem, a secret key is known to at least two users and, therefore, a digital signature produced with a secret key cannot be bound to a unique user.


(c) The problem is that a message can be easily transformed into an entirely different message with the same digest, by just re-arranging the characters or words. For example, “car” and “arc” have the same digest.

Cracking using quantum computing

Comment:

What if quantum computing cracks the theory of public key approach?

Follow-up:

Theoretically, based on Peter Shor’s factorization algorithm, a quantum computer can break a public key cryptosystem in very short time. Thus, public key cryptosystem as we are using it now will become completely useless.

The critical problem of the current public key cryptosystem (the “RSA” algorithm) is that it relies on computational intractability. In other words, its security is not mathematically proven.

Security scientists are actively researching on “provable” public key approaches.

Certificate authority

Comment:

What if the certificate authority discloses private information of users? Safe?

Follow-up:

Yes it is definitely possible that a CA could inadvertently discloses some private information. For example, a CA’s database could be compromised by some hackers, just like the credit-card numbers are disclosed in some hacking of e-business Web sites.

So in a sense, one could argue that our Internet security is quite fragile.

Comment:

Who will certify the public key of the certificate authority?

Follow-up:

A CA’s public key is not “certified” but just published in a widely accessible site so that everyone can verify it.

Internet Key: Key generation

Comment:

(I am) Still confused about public key cryptography.

Follow-up:

Simply put, in a public key cryptosystem, each user owns a pair of keys, one made public and the other kept secret. To send a message securely, the public key of the intended recipient is used for the encryption so that only the recipient can decrypt it. On the other hand, for digital signature, the signer uses his/her own private key to encrypt the message (or actually the digest of the message) so that everyone can decrypt it using the signer’s public key to verify it.

For those of you who are interested in the mathematical details, please study the attached lecture notes on public key cryptography (file: module3-PublicKeyCrypto.pdf).

Comment:

How does KDC work?

Follow-up:

The KDC shares secret key (or symmetric key) with every register user. Thus, by using this key, the KDC can send a newly generated key (denoted as R1 in Presentation #5) to a user requesting for a new key to be shared with another register user of the KDC. Once getting this R1, the two users can then transform it further using some agreed-upon protocol to generate the actual shared key which is unknown to the KDC.

Comment:

I want to know if it is possible to combine the use of public and private keys as follows.

Follow-up:

Yes of course your suggestion would work. In fact, it provides not only “confidentiality” but “non-repudiation” as well.