Your peers in the course Introduction to Modern Cryptography at the LMU München create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

Introduction to Modern Cryptography

First Attempt: Shift Cipher/Cesar Cipher

Encryption method of Shift Cipher: Shift every letter in alphabet by a constant number k of letters.

The key of the scheme then is this number k.

Plaintext: MEET ME AT MIDNIGHT

Ciphertext: JBBQ JB XQ JFAKFDEQ

Introduction to Modern Cryptography

Security of Shift Cipher/Cesar Cipher

Simplest possible attack: If attacker knows shift cipher has been used, he can simply try and test all possible keys k.

There are only 26 of them!

Introduction to Modern Cryptography

Second Attempt: Substitution Cipher

Encryption method: Every letter is replaced (=„substituted“) by a letter from some substitution alphabet.

The key is this substitution alphabet.

Our earlier shift cipher hence is a special case of substitution cipher…

• Substitution ciphers are generally more complex and have more possible keys – Number of possible keys: 26! = 4.03 * 1026 – A single key has length of log2 26! ~89 bits.

(Compare to key length of5 bits of shift ciphers!)

Introduction to Modern Cryptography

Security of Substitution Cipher

- Despite longer keys, a lot of the structure of the plaintext still is preserved…
- Attack: Frequency analysis by Al Kindi (801-873 a.c.) (1) Every letter appears with characteristic frequency in any

given natural language…

Introduction to Modern Cryptography

Third Attempt: Vigenere Cipher

Substituting every plaintext letter with a fixed other letter does not work well… (→frequency analysis)

• Idea: Why not substitute every plaintext letter by a ciphertext letter whose choice depends on the original plaintext letter‘s position in the plaintext?

• This is the basic idea of

the Vigenere cipher…

Introduction to Modern Cryptography

Security of the Vigenere Cipher

Structure of plaintext is hidden/scrambled much better than in previous ciphers…

• Still, there is an applicable variant of the frequency attack described first by Friedrich W. Kasiski (1805-1881) (1)

• Idea: If the key is repeated over a (long) plaintext, occasionally the same word or phrase will be encrypted

with the same letters of key, leading to repetitions in ciphertext

Introduction to Modern Cryptography

The One-Time Pad

Basic idea of one-time pad: – Procede (almost) as in the Vigenere cipher... – But: Choose code word/key uniformly and independently at random

– But: Choose code word/key as long as the complete text that shall be encrypted with it… Any key letter will encrypt only one plaintext letter,

will not be reused for other plaintext letters afterwards…

Introduction to Modern Cryptography

Security of the One-Time Pad

- Without knowing the key: – Given a certain ciphertext, all plaintexts are possible – and even equally likely!
- REASON I: Given any (plaintext, ciphertext)-pair, there is exactly one key that maps this plaintext to this ciphertext…
- REASON II: Key is chosen uniformly at random from all possible keys!

– Ciphertext hence intuitively does not reveal any information

about plaintext (e.g., about its structure) - This feature is called „perfect secrecy“ or „information-theoretic security“. It is not met by the other ciphers we have seen…

Introduction to Modern Cryptography

Formalization of One-Time Pad Security

How can one comprehensively formalize and prove the security of the one-time pad?

• Work and merit of Claude Shannon (1916-2001), founder of information theory (1)

• We will follow his traces in the sequel, and will formally define and prove the „perfect secrecy“ or „information-theoretic security“

of the one-time pad

Introduction to Modern Cryptography

Practical Impact perfect secrecy

- Since ciphertext and plaintext are information-theoretically and statistically independent:

Even unbounded computational power does not help the attacker… - The only assumptions required for „perfect“ and everlasting secrecy:

Uniform randomness and

secrecy of the key itself! - All key material in one-time pad must be chosen truly (=physically) at random – I.e., if messages are n bits long, then n independent, truly random key bits must be physically generated
- This can be very cumbersome for large n in practice… – E.g., typists in WWII – but did not generate truly random and independent bits!
- Quantum (1) or other (2)modern physical random number generators today
- Keys also must remain

secret forever! - One-time pad‘s key bits / key material cannot be re-used securely in practice…

Introduction to Modern Cryptography

Summary

- First lecture of the course („Overview and Symmetric Encryption, Part I“)
- Clarified some technicalities – Moodle, discussion forum, always ask questions!
- First half: Scientific warm-ups – Shift cipher (with special case Cesar cipher, where shift parameter k=-3)
- Substitution cipher – Vigenere cipher – None of them secure. Discussed attacks on all of them:

Small key space. Frequency analysis. Kasiski‘s attack. - Second half: One-time pad (OTP) as provably secure encryption scheme
- Information-theoretic security and its practical impact – Cannot attack, even with unlimited computational power…
- However, there is a price we pay... Keys in OTP must inevitably be: – Very long (as long as message) – Truly and physically random (→how to generate them?) – Kept secret at any time (→how to store them safely?)
- OTP key bits must never be re-used in practice!
- Take away messages:
- – Be careful in implementation of cryptographic primitives!
- – Be careful in practical application of mathematical theorems
- –make sure all necessary conditions are really fulfilled!

Introduction to Modern Cryptography

Computationally Secure Encryption

- Perfect secrecy is a worthwhile goal, but its costs may be unnecessarily high as unbounded computational power does not exist
- For practicability, a scheme may still be considered secure if it leaks only a tiny amount of information to eavesdroppers with bounded computational power.
- We relax the notion of perfect secrecy by the following:
- - Security is only preserved against efficient adversaries
- - Adversaries can potentially succeed with some very small probability, which is small enough so that we are not concerned

that it will ever really happen

For your degree program Introduction to Modern Cryptography at the LMU München there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to LMU München overview pageCheck out courses similar to Introduction to Modern Cryptography at other universities

Back to LMU München overview pageStudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for Introduction to Modern Cryptography at the LMU München or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Best EdTech Startup in Europe

X

X
## Good grades at university? No problem with StudySmarter!

### 89% of StudySmarter users achieve better grades at university.

50 Mio Flashcards & Summaries

Create your own content with Smart Tools

Individual Learning-Plan