Cryptography
BIT – 410
Perfect Secrecy
What does it mean that a crypto system is secure?
• In a scenario, if the adversary finds the entire plaintext or the entire
secret key, that would be a severe failure.
• But even if the adversary finds a small part of the plaintext or the key, or
even if the adversary determines that, say, the first letter of the plaintext
is more likely to be an A than the usual frequency of an A at the
beginning of a word in a typical English text, that would also be a
weakness.
What does it mean that a crypto system is secure?
• Idea: A cryptosystem is secure to an attack if the adversary does not
learn anything after the attack compared to what he knew before the
attack.
Types of Secercy:
• Perfect secrecy(Unconditional Security): the adversary does not learn
anything, no matter her computational power and how much time the
attack takes. This is the ideal, but cannot be realized by practical
cryptosystems.
• Computational secrecy: the adversary does not learn anything unless
she is performing more than N operations, where N is some huge
number (so that the attack takes thousands of years). This is good
enough and may be achieved by practical cryptosystems. Eg. DES, AES
etc.
• Provable Security: the adversary does not learn anything unless she can
factor large numbers easily. Factorization of large numbers is a NP-Hard
problem. Eg. RSA etc.
Analysing Perfect Secrecy:
• Assumptions
– Ciphertext only attack model
The attacker only has information about the ciphertext. The key and
plaintext are secret.
Based on the knowledge of various ciphertexts the attacker will try to
obtain the plaintexts.
Encryption
Plaintext Distribution
Key Distribution
Ciphertext Distribution
Ciphertext Set C={P,Q,R}
y K1 y K2
a R a Q
b Q b R
c P c P
Attacker’s Probabilities
• The attacker wants to determine the plaintext x
• Two scenarios
– Attacker does not have y(a corresponding Ciphertext) (a priori Probability)
• Probability of determining x is simply Pr[x]
• Depends on plaintext distribution (eg. Language charcteristics)
– Attacker has y (a posteriori probability)
• Probability of determining x is simply Pr[x|y]
Pr[y|x]=sum of probabilities of keys which map x to y
Computing Posteriori Probabilities
Perfect Secrecy
Perfect Secrecy
Shannon’s Theorem:
Perfect Secrecy(Example)
Pr[x|y]
Pr[a|P] = 1/2 Pr[b|P] = 1/3 Pr[c|P] = 1/6
Pr[a|Q] = 1/2 Pr[b|Q] = 1/3 Pr[c|Q] = 1/6
Pr[a|R] = 1/2 Pr[b|R] = 1/3 Pr[c|R] = 1/6
One Time Pad(Vernam Cipher):
• One-time pad encryption, also known as OTP encryption, uses a random
key that is only used once to encrypt plaintext.
• It is an unbreakable cipher. The key is exactly same as the length of
message which is encrypted.
• The key used for a one-time pad cipher is called pad, as it is printed on
pads of paper.
One Time Pad(Vernam Cipher):
• One-time pad encryption is a symmetric key encryption method,
meaning the same key is used for both encryption and decryption.
• It uses a random key that is the same length as the plaintext, making it
impossible for an attacker to determine the key without prior
knowledge.
• One-time pad encryption is theoretically unbreakable, as long as the key
remains secret and is only used once.
• It does not require complex mathematical algorithms or large amounts
of computing power, making it simple and efficient.
One Time Pad(Vernam Cipher):
• Advantages
1. One-time pad encryption provides the highest level of security
possible, as long as the key remains secret and is only used once.
2. It does not suffer from the same weaknesses as other encryption
methods, such as the vulnerability to brute-force attacks or known
plaintext attacks.
3. One-time pad encryption is flexible and can be used for both text and
binary data.
4. It is relatively simple to implement and can be done manually or with
the help of a computer.
One Time Pad(Vernam Cipher):
• Disadvantages
1. One-time pad encryption requires a truly random key that is the same
length as the plaintext, making it difficult to generate and manage for
large amounts of data.
2. The key must be kept completely secret and cannot be reused, as this
would compromise the security of the encryption.
3. One-time pad encryption is not suitable for real-time communication
or applications where speed is a critical factor, as generating and
transmitting the key can take time.
One Time Pad(Vernam Cipher):
One Time Pad(Vernam Cipher):
• Example
