Question

In: Computer Science

Explain the mathematical proof that One time pad (OTP) is perfectly secure under Ciphertext Only attack...

Explain the mathematical proof that One time pad (OTP) is perfectly secure under Ciphertext Only attack (COH).

Solutions

Expert Solution

The OTP is an encryption technique that cannot be cracked, but it requires the use of a one-time pre-shared key the same size as, or longer than, the message being sent. In this technique, a plain text is paired with a random secret key. Then, each bit or character of the plain text is encrypted by combining it with the corresponding bit from the pad using modular addition.
The resulting ciphertext are going to be impossible to decrypt or break if the subsequent given below four conditions are met:

  1. The Key must be truly random.
  2. The Key must be a minimum of as long because the plaintext.
  3. The Key must not be ever reused in whole or partially
  4. The key must be kept completely secret.

It has also proven that any cipher with the property of perfect secrecy must use keys with effectively the same requirements as OTP keys. Digital version of one-time pad cipher are employed by nation for critical diplomatic and military communication, but the issues of secure key distribution have made them impractical for many applications.

Example:

Suppose Joy wishes to send the message "HELLO" to Roy. Assume two pad of paper containing identical random sequences of the letters were previously produced and securely issued to both of them. Joy chooses the appropriate unused page from the pads. The way to do this, normally arranged for in advance, as for instance "use the next available sheet for the next message".

The material that is on the selected sheet is the key for the message. Each letter from the pad will be combined in a predetermined way. (It is commonly used way, but not required, to assign each letter a numerical value, "A" is 0, "B" is 1, "C" is 3 and so on.)

The technique to combine the key and the message using modular addition. The numerical values of corresponding message and key letters are added together, modulo 26. So, if key material begins with "XMCKL" and the message is "HELLO", then the coding be done as follows:

   H       E       L       L       O → (message)
   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) → (message)
+ 23 (X)  12 (M)   2 (C)  10 (K)  11 (L) → (key)
= 30      16      13      21      25   →  (message + key)
=  4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) → (message + key) mod 26
      E       Q       N       V       Z  → (ciphertext)

If number is larger than 25, then the remainder after subtraction of 26 is taken in modular arithmetic fashion. This means that if the computations "go past" of Z, the sequence starts again from A.

The ciphertext to be sent to Roy is thus "EQNVZ". Roy use the matching key page and the same process, but in reverse, to obtain plain text(message sent by joy will be decrypted). Here the key is subtracted from the ciphertext, again using modular arithmetic fashion:

       E       Q       N       V       Z → (ciphertext)
    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) → (ciphertext)
-  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) → (key)
= -19       4      11      11      14   → (ciphertext – key)
=   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) → (ciphertext – key) mod 26
       H       E       L       L       O  → (message)

from the above, if a number is negative, then 26 is added to make the number zero or higher.

Thus Roy recovers Joy's plain text, the message "HELLO". Both Joy and Roy destroy the key sheet immediately after use, thus preventing reuse and attack against the cipher.

Mathematical Proof:

Claude Shannon proved, that the one-time pad has a property he termed perfect secrecy; that is, the ciphertext C gives absolutely no additional information about the plain text. This is because, given a truly random key that is used only once for the message and than destroyed, a ciphertext can be translated into any plain text of the same length, and all are equal. Thus, the priori probability of a plaintext message M is the same as the a posteriori probability of a plaintext message M given the ciphertext.

Mathematically, this is expressed as H(M)=H(M|C) , where H(M) is the information entropy of the plaintext and H(M|C) is the conditional entropy of the plaintext for the given ciphertext C.  Η is the capital Greek letter eta. This implies that for every message M and its corresponding ciphertext C, there must be at least one key K that will bind them as a one-time pad. Mathematically, this means , where K,C,M are the distinct quantity of key, cipher and message

Another way of saying that perfect secrecy is based on the idea that for all messages m1,m2 in message space M, and for all ciphers c in cipher space C, we have

where Pr represents the probabilities, taken over a choice k in key space K over the coin tosses of a probabilistic algorithm, E. Perfect secrecy is a strong notion of the cryptanalytic difficulty.


Related Solutions

Which of the 5 AES modes satisfies COA (Ciphertext only attack)
Which of the 5 AES modes satisfies COA (Ciphertext only attack)
1. (a) Explain the “one-time pad” method for sending secret messages. In particular, explain the nature...
1. (a) Explain the “one-time pad” method for sending secret messages. In particular, explain the nature and the role of the secret key. (b) Why is it impossible for anyone without the secret key to read the encrypted message?
When there is only one buyer in the market a. then the market will be perfectly...
When there is only one buyer in the market a. then the market will be perfectly competitive b. a monopsony exists c. a closed shop exists. d. the supply curve for the good will be perfectly elastic. Any practice that forces employers to use more labor than they would otherwise use is a. monopolistic exploitation b. a craft union c. closed shop d. featherbedding. IN MICROECONOMICS
what is MAC address flooding attack ? briefly explain any one meathod to prevent this attack?
what is MAC address flooding attack ? briefly explain any one meathod to prevent this attack?
Consider the one-time pad with messages and key-streams both being binary sequences. Suppose that the system...
Consider the one-time pad with messages and key-streams both being binary sequences. Suppose that the system is used erroneously, so that two messages have been encrypted using the same key. What information can an adversary that hears the two ciphertexts deduce about the plaintexts? Show this mathematically using EXOR logic
1. Draw equilibrium of a perfectly competitive firm under the following conditions (one diagram for each):...
1. Draw equilibrium of a perfectly competitive firm under the following conditions (one diagram for each): a) Short run profits b) Short run losses c) Long run equilibrium with zero economic profits 2. State the condition (in terms of costs and revenues) that describes allocative efficiency that occurs in LR equilibrium and explain what happens to Producer Surplus in this case. 3. A firm accepts a price of $22 in a market consisting of many producers all making essentially the...
1. Adjusting entries are needed Select one: a.  only under the cash basis of accounting. b. only...
1. Adjusting entries are needed Select one: a.  only under the cash basis of accounting. b. only under a perpetual inventory system c. only under IFRS d.  to produce relevant financial information for users. e. to update accounts at the beginning of the accounting period. 2. Walmarts sells $6,250 of goods on account in the current year and collects $3,250 of this. It incurs $4,200 in expenses on account during the current year and pays $2,600 of them. Walmart would report what...
Write the Faraday’s Law. mathematical expressions (integral form only). Explain each symbol, each detail in each...
Write the Faraday’s Law. mathematical expressions (integral form only). Explain each symbol, each detail in each of these equations – by words. Draw sketches when they are necessary for your explanation.
Give an example of a perfectly competitive market (or one that closely approximates one). Explain why...
Give an example of a perfectly competitive market (or one that closely approximates one). Explain why you believe this market is competitive. If you can’t think of such a market, explain why it is difficult to find a perfectly competitive market. Be specific.
Give one example of a perfectly competitive team and one example of a monopoly team. Explain.
Give one example of a perfectly competitive team and one example of a monopoly team. Explain.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT