Perfect Secrecy and One-Time Pad

Loading...

來自 University of Colorado System 的課程

Cryptography and Information Theory

41 個評分

University of Colorado System

Cryptography and Information Theory

41 個評分

課程 1（共 4 門，Specialization Applied Cryptography）

Welcome to Cryptography and Information Theory! This course combines cryptography (the techniques for protecting information from unauthorized access) and information theory (the study of information coding and transfer). More specifically, the course studies cryptography from the information-theoretical perspectives and discuss the concepts such as entropy and the attacker knowledge capabilities, e.g., Kerckhoff's Principle. It also contrasts information-theoretic security and computational security to highlight the different train of thoughts that drive the cryptographic algorithmic construction and the security analyses. This course is a part of the Applied Cryptography specialization.

從本節課中

Brute-Force Attack and Cryptanalysis

This module studies the attacker view whose objective is to learn the key and break the cryptographic protection using the key. First, we will define brute force attack and describe how to quantify the attacker effort for brute force attack. Next, we will contrast cryptanalysis and brute force attack. Lastly, we will discuss about perfect secrecy, which is immune to cryptanalysis and is a strong notion of security derived from information theory.

Perfect Secrecy and One-Time Pad3:23

與講師見面

Sang-Yoon Chang
Assistant Professor
Computer Science

When the ciphertext provides no information about the plaintext without the key,

and an attacker cannot learn the plain text

regardless of how many time or effort it puts in,

then the cryptosystem is set to achieve

perfect secrecy and is cryptanalytically unbreakable.

In the 1940s, Claude Shannon, who, by the way,

also introduced information entropy,

showed that perfect secrecy can be

achievable by using a key that is as long as the message.

In other words, the key entropy is as great as the message entropy.

In addition, to achieve perfect secrecy,

the key should never be reused in the encryption,

meaning that there is no dependency or relationship across the parts of the key.

Such key is called a one-time pad due to

the key being fresh and random every time it is used for encryption.

Perfect secrecy is derived from

information theory and it's the strongest notion for encryption.

It holds even against the computationally unbounded attacker.

With less than perfect secrecy with bounded entropy for the key,

an attacker will eventually break the cipher and learn the plaintext and the key,

as the message length and the ciphertext length increase.

However, with perfect secrecy,

the encryption remains secure even when the message length grows infinitely.

You may wonder how the brute-force search fits into

the information theoretical notion of perfect secrecy.

Let's set aside the discussion of how difficult the brute-force search would be

for the attacker and practice and assume that it is possible.

We'll revisit one-time pad after studying some encryption algorithms.

Even against the brute-force attacker,

who exhaust the keyspace and finds all possible plaintext,

there are many plaintexts that makes sense.

And, the attacker cannot distinguish between the correct and the incorrect plaintext,

which was a requirement for a successful brute-force attack.

While one-time pad is proven to achieve perfect secrecy,

the strongest security notion for encryption,

it has limited practical use because the key is too long and grows as the message grows.

This provides challenges in key and randomness generation as

well as in key distribution and agreement between the sender and the destination.

And these overheads become too much in practical security context.

However, in addition to being used for

low bandwidth applications where the messages are short,

perfect secrecy does provide

a useful guidance and a reference when designing the cryptosystem,

such as deciding on the key refresh rate,

especially for protecting a high risk data against the powerful adversary,

such as a nation state and the crowd.

And, an example for crowd can be when a standardized crypto design,

such as those by the United States' NIST,

National Institute of Standards and Technology,

is under the watchful eyes of the public.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取