Department of Computer Science
COMP40451 Cyber Security
Lecture 6
Cryptography (2)
Dr Xiaoqi Ma
Outline
1 One-time pad encryption
2 Integrity check methods
3 Symmetric encryption
4 Summary
One-Time Pad
The one-time pad (OTP) is a type of encryption, which has been proven to be impossible
to crack if used correctly
Each bit or character from the plaintext is encrypted by a modular addition with a bit or
character from a secret random key (or pad) of the same length as the plaintext, resulting
in a ciphertext
If the key is truly random, as large as or greater than the plaintext, never reused in whole
or part, and kept secret, the ciphertext will be impossible to decrypt or break without
knowing the key
One-Time Pad Encryption
One-Time Pad Decryption
Cryptoanalysing One-Time Pad
An Exercise of One-Time Pad
Plaintext SYMMETRICAL
Key JEVSRITJPGF
Ciphertext
An Exercise of One-Time Pad
Plaintext SYMMETRICAL
Key JEVSRITJPGF
Ciphertext BCHEVBKRRGQ
Security of One-Time Pad
One-time pads are information-theoretically secure in that the encrypted message
(ciphertext) provides no information about the original message to a cryptanalyst (except
the length of the message)
The security property has been mathematically proved by Claude Shannon (perfect
secrecy)
Properly used one-time pads are secure in this sense even against adversaries with infinite
computational power
Limitations of One-Time Pad
Despite the perfect secrecy property, one-time pad has serious drawbacks in practice:
It requires perfectly random one-time pads
Secure generation and exchange of the one-time pad material are difficult
Careful treatment to make sure that it continues to remain secret from any adversary, and is disposed
of correctly preventing any reuse in whole or part are also not easy
The theoretical perfect security of the one-time pad applies only in a theoretically perfect
setting
One-time pad is, in practice, little-used
Data Integrity
Data integrity ensures that data is “whole” or complete, the condition in which data is
identically maintained during any operation (such as transfer, storage or retrieval), and
the preservation of data for their intended use
Put simply, data integrity is the assurance that data is consistent and correct
Integrity can be compromised through:
Malicious altering
Accidental altering
One-Way Function
A one-way function is a function that is easy to compute on every input, but hard to
invert given the image of a random input
Suppose we have a key which is a 128-bit number. There are
340, 282, 366, 920, 938, 463, 463, 374, 607, 431, 768, 211, 456
128-bit numbers. If we use 1,000,000,000 machines each of which could try
1,000,000,000 keys/sec, it would take all these machines longer than the universe as we
know it has existed to find the key
Hash Function
A cryptographic hash function is also a one-way function
A one-way hash function takes a variable-length input sequence of bytes and converts it
into a fixed-length sequence
The data to be encoded is often called the message, and the hash value is sometimes
called the message digest or simply digest, or checksum
Source of image: https://aboutssl.org/
Examples of Hash Functions
MD5 (Message-Digest Algorithm 5)
Input length: arbitrary
Output length: 128 bits
SHA-1 (Secure Hash Algorithm)
Input length: arbitrary
Output length: 160 bits
Collisions and Birthday Paradox
We have a collision if there are two inputs 𝑥1 and 𝑥2, 𝑥1
≠𝑥2, with ℎ(𝑥1)=ℎ(𝑥2), where ℎ is a hash function
In this case, an attacker might modify the message in a
way that leaves the hash value unchanged and the
changes to the message would not be detected
Birthday paradox: In a class of 𝑛 students, how is it
likely that there are two students having the same
birthday?
Birthday Paradox
Number of Probability of birthday
students sharing
23 50.7%
50 97%
57 99%
100 99.99997%
Birthday paradox is not actually a paradox, but it is probably counter-intuitive
Encryption
Encryption: the process of transforming information using an algorithm to make it
unreadable to anyone except those possessing special knowledge, usually referred to as a
key
Decryption is the reverse process of encryption
Flavours of Encryption
Two flavours of encryption:
Symmetric encryption: The same key is used for encryption and decryption
Asymmetric encryption: Different keys are used for encryption and decryption. It is also called public
key encryption
Symmetric Encryption (1)
Symmetric encryption algorithms: a class of algorithms for cryptography that use
trivially related, often identical, cryptographic keys for both decryption and encryption
Source of image: https://aboutssl.org/
Symmetric Encryption (2)
Two types of symmetric encryption algorithms:
Stream ciphers: encrypt the bytes of the message one at a time
Block ciphers: take a number of bytes and encrypt them as a single unit
Most widely used symmetric encryption algorithms:
DES: Data Encryption Standard
AES: Advanced Encryption Standard
Summary
1 One-time pad
2 Data integrity
3 One-way function
4 One-way hash function
5 Symmetric encryption
