[SEC] Cryptography I

Cryptography I

Content

  • What is encryption?
  • Primitive types
  • Historic ciphers
  • The One Time Pad
  • Stream Ciphers
  • Cryptanalysis(密码分析学，密码翻译法)

Encryption

  • Encryption: We encode a message such that only authorised users may read it
  • Cipher: takes a string of plaintext, and converts it into a string of ciphertext
  • Encryption can provide:
    • Confidentiality
    • Integrity
    • Authenticity

Notation

  • A cipher converts a plaintext message M into a ciphertext C under the control of a key K
  • C is not a secret, but without knowledge of the key, it should be impossible to reconstruct M
  • Comes in two forms:
    • Symmetric- same key for encryption/decryption
    • Asymmetric- separate keys

The Caesar Cipher

  • An early substitution cipher, we replace each letter of plaintext with a shifted letter further down the alphabet
  • Vulnerable to frequency analysis

Frequency Analysis

  • The frequency of occurrences of each character are very consistent across the same language
  • The longer the ciphertext, the easier this becomes
  • enter image description here
  • A corresponding to H

Monoalphabetic Substitution

  • A slightly better approach, a key is used to alter the cipher alphabet
  • enter image description here
  • Still extremely vulnerable to frequency analysis

The Vigenere Cipher

  • An early stream cipher, the Vigenere cipher adds the plaintext to a key modulo 26: C = P + K mod 26
  • Unlike the Ceasar cipher, the key is repeated for as long as is required:
  • enter image description here
  • Equivalent to multiple interleaved Caesar ciphers
  • Spreads out the occurrences of characters making frequency analysis hard
  • This cipher is weak to Kasiski examination:
    • Repeated phrases in the ciphertext give away clues as to the length of the running key
    • Once the length of the key is known, simple frequency analysis can be performed
    • enter image description here

However, if we find(guess) the key length, the frequency analysis is pretty straightforward, just like the Ceasar Cipher:
enter image description here

Playfair

  • Playfair is an early block cipher
  • By using blocks of two characters(diagram) we increase the number of mappings to 650
  • This makes frequency analysis much harder
  • enter image description here
    (看看小block 对角线吧)

enter image description here

The One Time Pad

XOR

enter image description here

The One Time Pad(two kinds)

  • Key and M and C has the same length
  • The key is one time use only

enter image description here
enter image description here

BUT

  • The one time pad is not practical:
    • A 1GB file would need a 1GB key!
    • If you ever reuse a key, the entire cipher is broken

What the one-time pad gives us in secrecy, it lacks in:

  • Portability - the key is the same size as the message
  • Convenience - you must never reuse the key
  • Modern stream ciphers attempt to approximate the one time pad with a pseudorandom key stream

Modern Stream Ciphers

  • Modern stream ciphers use an initial seed key to generate an infinite pseudorandom keystream
  • The message and keystream are usually combined using XOR, which is reversible if applied twice
  • enter image description here

ChaCha20

enter image description here
enter image description here

Advantages of Stream Ciphers

  • Encrypting long continuous stream, possibly of unknown length, e.g. GSM mobile communications
  • Extremely fast with a low memory footprint, ideal for low-power devices
  • If designed well, can seek to any location in the steam

Cryptanalysis

Kerckhoff’s Principle

“A cryptographic system must be secure even if everything is known about the system with the exception of the secret key”

  • Algorithms can be published, but will work providing that the key remains secret - rather than security through obscurity.

Cryptographic Attack Models

enter image description here

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文