Introduction to Network Security – Part 11

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used. You are welcome to point out any mistakes in my posting and/or leave a comment.

Key Distribution Using Public-Key Cryptography

In the previous post, introduction to network security – part 10, we saw three main methods of public-key:

  1. Public announcement,
  2. Public-key authority, and
  3. Public-key certificates

These methods can be used for encryption and decryption of messages (secrecy) and/or authentication.

These methods the disadvantage of being slow; therefore, its common to use symmetric-key encryption for secrecy and distribute using public-key encryption session keys. In this way we use the advantage of the speed of symmetric-key encryption and the security of public-key encryption.

Simple Key Distribution

In 1979,  Ralph C. Merkle created his thesis entitled “Secrecy, authentication and public key systems” which let him receive his Ph. D. in Electrical Engineering at Stanford University <http://en.wikipedia.org/wiki/Ralph_Merkle>.

For a key distribution, Merkle proposed:

  1. User A will generate a new temporaty public key pair, PUa
  2. User A send the public key, PUa, to user B together with its identity, IDa
    PUa, IDa
  3. User B generate the session key K.
  4. User B uses the public key, PUa, supplied by user A to encrypt the session key K. Then user B send the encrypted session to user A
  5. User A decrypt the message to obtain the session key K.
  6. User A discards the public key PUa
  7. User B discards user A’s public key, PUa.
  8. After the exchange of information is complete, user A and B discard the session key K.

The Man-In-The-Middle Attack

This type of key distribution have a disadvantage.  Lets assume that we have an attacker that gets in the middle of the communication in a way that this attacker can intercept the messages and then replay this message, modify this message, or send another different message.

Lets analyse this problem:

  1. User A send a message to user B which holds the public key PUa, and user A’s identifier IDa
  2. The attacker T intercept this message and create its own pair keys, public key PUt and private key PRt:
    {PUt, PRt}

  3. The attacker T send to user B, its own public key PUt together with the user A’s identification IDa :
    PUt||IDa
  4. User B generate a session key Ks. Then user B send this session key Ks encrypted using the public-key PUt that he received thinking that it came from user A.
    Ciphertext = E(PUt, Ks)
  5. The attacker T intercept the message obtaining the session key Ks by decrypting the message with his private key PRt.
    Ks = D(PRt, Ciphertext) = D(PRt, E(PUt, Ks))
  6. Then attacker T send the key session Ks to the user A using user A’s public key PUa
  7. Without user A and B knowing, the attacket T obtained the session Ks successfully.

Solution to The Man-In-The-Middle Attack

  1. The process begins with user A. User A encrypt the message containing the user A identification IDa plus a nonce N1 using the user B’s public key PUb
  2. User B generate a new nonce N2 and encrypts the message containing user A’s nonce N1 plus a new nonce N2 using the user A’s public key.
  3. Since user B is the only one that could decrypted the first message coming from user A plus the new message send from user B to user A will contain the nonce N1 (given by  user A in the first message), user A will know the new message is coming from user B and not an attacker.
  4. User A will encrypt nonce N2 using the public key PUb of user B. Then user A will send then encrypted nonce N2 to user B. In this way, since nonce N2 was generated by user B, when user B find nonce N2, user B will known the message came from user A.
  5. User A generate a secret key Ks. User A will encrypt first the secret key Ks using the private key PUa of user A which would provide authentication, and then it will encrypt the output of the encryption with the public key PUb of user B to produce a new ciphertext M which provide confidentiality.
  6. User B decrypt the ciphertext M by decrypting the ciphertext M using the private key PUb of userB, and the result will be decrypted again using the public key PUa of user A. In this way the secret key Ks is obtained.

Hybrid Key Distribution

Public key encryption is an algorithm that require a lot of processing. In a system that require to distribute session keys thought many users and require a frequently change of session keys, the public key encryption can slow the performance of the system as the load on the system keep increasing. One solution to this problem is to use an hybrid of different key distribution.

In an hybrid key distribution, the key distribution center (KDC) will be in charge of distributing a master key MK to each user of the system plus perform the distribution of session keys. Before these session keys are distributed, they will be encrypted by using the master key MK. Also, the master key is encrypted using a public key encryption. Since the master key only update in few occasions then the load of the system is reduced.

Share

Introduction to Network Security – Part 10

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used. You are welcome to point out any mistakes in my posting and/or leave a comment.

RSA Algorithm

RSA is an algorithm for public-key cryptography. The signals R.S.A. come from the last name of Ron Rivest, Adi Shamir, and Leonard Adleman who where the first to describe this algorithm. This algorithm is famous for being the first suitable algorithm for signing as well as encryption.

RSA algorithm allow to choose which key should be use for encryption and decryption.

  1. Public key for encryption, private key for decryption or,
  2. Private key for encryption, public key for decryption.

Generate the Pair Key (Public and Private Key)

  1. Choose two random prime numbers p and q.
    p = 17
    q = 11

    For better security, you can use the Primality Test to obtain to obtain these two random prime number. They should be of similar bit-length.
  2. Compute n = p*q in which n is the modulus used for both the private and public keys.
    n = p * q = 17 * 11 = 187
  3. Compute Euler Totient Function ø(n)
    ø(n) = ø(187) = (p – 1) * (q – 1) = 16 * 10 = 160
  4. Select a public key exponent e number where 1 < e < ø(n) and gcd(e, ø(n)) = 1
    If we choose e = 7 then gcd(e, ø(n)) = gcd(7, 160) = 1
  5. Determine the multiplicative inverse d:

    1. d must be less than ø(n): d < 160
    2. if d * e mod ø(n) = d * 7 mod ø(187) = d * 7 mod 160 = 1 then
    3. let d = 23 in this way d * e = 23 * 7 = 161 = (160 + 1)
      d * 7 mod 160 = 23 * 7 mod 160 = 1
  6. The public key will be:
    PU = {e, n} = {7, 187}
  7. The private key will be:
    PR = {d, n} = {23, 187}

Encryption

  1. Sender must obtain the public key PU = {e, n} to the recipient, where PU is the public key, n for modulus, and e for public exponent (also known as public encryption).
    PU = {e, n} = {7, 187}
  2. The message M (also known as the plaintext) must be turn into an integer m by using a padding scheme (an reversible protocol) in which 0 < m < n.
    Lets assume the message is m = 88 where 0 < m < n so 0 < 88 < 187.
  3. Then the sender must compute the ciphertext.

    Where c is the ciphertext, m is the integer message , e is the public exponent, and n i for modulus.

Decryption

  1. The recipient must use the private key to decrypt the ciphertext PR = {d, n} where PR is the private key, d is the private key exponent, n for modulus.
    PR = {d, n} = {23, 187}
  2. Compute the message.

    Where m is the integer message, c is the ciphertext, n for modulus.
  3. Then turn back the original message M by using  integer message m with the reverse padding scheme.

Encryption / Decryption Example

Algorithm Requirements

  1. There should be able to find values for e, d, and n so for all values of m where 0 < M < n
  2. and should be easy to calculate for all valus of m where 0 < m < n.
  3. It should be very hard for an attacker to determine d given e and n

Possible Attacks to RSA

  1. Brute Attack
  2. Mathematical attacks
    1. Determine d directly
    2. Determine the Euler Totient Function ø(n) without using the prime numbers p and q
    3. Factorising n into the correct prime factors p and q

Key Distribution

One of the important aspects is how to distribute the keys between the sender and the receiver. For example, one way is to use the public-key encryption to distribute the keys.

For doing that there are three different methods of distributions that can be used:

  1. Public announcement,
  2. Public-key authority, and
  3. Public-key certificates

Public Annoucement

One way to distribute the public keys is having the sender to distribute the public key to the recipient; however, this have the disadvantage that an attacker could create a key claiming to be the sender. This disadvantage is known as forgery.

A solution is to create a public-key autority.

Public Key Authority

A public key authority is a central authority that maintain a dynamic directory of public keys for all the users. Example: {name, public-key}

  1. In a secure way (in person), each user register a public key in this directory authority.
  2. It is required that the user known the public key for the directory.
  3. Only the authority known the corresponding private key
  4. Users interact with the directory in order to obtain the public key securely

Steps:

  1. User A send  a timestamped message to the public key authority.
    This message contain a request for the public key of user B.
  2. The public-key authority responds to user A returning an encrypted message using it’s private key. This message contains:
    1. The original request so it can be use to match with the request
    2. The original timestamp so it can be determined if the message is not from the public-key authority.
    3. The public key of user B.
  3. User A store the public-key of user B and use this public-key to encrypt a message that will contain the identity of user A plus a “nonce N1”. This message will be deliver to user B.
  4. User B send  a timestamped message to the public key authority.
    This message contain a request for the public key of user A.
  5. The public-key authority responds to user B returning an encrypted message using it’s private key. This message contains:
    1. The original request so it can be use to match with the request
    2. The original timestamp so it can be determined if the message is not from the public-key authority.
    3. The public key of user A.
  6. User B encrypt a message using the public-key of user A and send this encrypted message to user A.
    This encrypted message have:

    1. User A’s nonce
    2. A nonce genereated by User B
  7. User A encrypt a message using the public-key of User B and send this encrypted message to user B.
    This encrypted message holds:

    1. the  nonce N2 of user A

    (This will ensure user B that the encrypted message is coming from user A).

Disavantages:

Since the users must appeal to the public-key authority in order to obtain the other users’ public key it can produce a bottleneck.

Public Key Certificates

Another way to exchange keys without the need of a public-key authority is the public-key certificates. The general idea would be:

  1. A certificate is a data block that contains a public key plus an identifier of the key’s owner. This data block would be signed by a trusted third party which would be the certificate authority.
  2. A user would generate a pair key and send the public key to this certify authority in a secure way and obtain a certificate issued by the certify authority (the trusted third party).
  3. This user then would publish this certificate so another user can verify that the certificate was created by the trusted third party.

Please notice that the certificate authority (the trusted third party) is the only one that can create and update certificates.

Steps:

  1. User A supply a public key PUa with a request for a certificate to the certificate authority. This request must be done in a secure ways such as in person for example.
  2. The certificate authority would provide user A with this from:
    where E is the encryption algorithm, PRauth is the authority’s private key and Time1 is a timestamp, and IDa is the user A identification.
  3. User A then can pass the certificate CA any user (in this case user B).
  4. User B get the certificate from user A and verify if the certificate correspond to the certify authority by decrypting the message using the authority’s public key:

    In this way it can verify that the certificate is not counterfeit.

Share

Introduction to Network Security – Part 8

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used. You are welcome to point out any mistakes in my posting and/or leave a comment.

In security, we use a system of key in order to work on encryption and decryption. The most common system used are the Symmetric Key Encryption and the Public Key Encryption

Symmetric Key Encryption

In a symmetric  system, one key is used for the encryption of a plaintext to a ciphertext and for the decryption of the ciphertext to a plaintext.

The key must be distributed in a secure way to the sender and the receiver making sure that the key is not disclose since then the communication could be compromised. The possible disclose of the key is one of the disadvantages of this system.

Another disadvantages of this system are:

  1. There is no way to prove the message was send by the original sender and not from an intruder.
  2. The recipient could change the message and say it came from the sender.

Public-key Encryption

In the public key system, normally two keys are generated (pair keys). One key is used to encrypt the message and another key is generated to decrypt the message.

The key that was used for the encryption of the message cannot be used for the decryption and the key used for the decryption of the message cannot be used for the encryption of the plaintext.

One key is the public key which is going to be used for the encryption of the plaintext to the ciphertext and for the verification of the signatures.

The other key is the private key which is going to be used for the decryption of the ciphertext to a plaintext and the generation of signatures.

This system can be used for:

  1. Authentication: Verify that the message came from the corresponding sender and the message is received to the corresponding receiver
  2. Confidentiality: Create a message that cannot be decrypt by an attacker
  3. Authentication and Confidentiality

However, this system still have some main issues such as:

  1. Key distribution: In the same way that the symmetric key encryption, there have to be a secure way to distribute keys.
  2. Digital Signatures: The way to verify that the message is coming for the sender and not an attacker.

The public-key encryption is considered to be an asymmetric system. This means that those who encrypt the plain-text and/or verify the signatures cannot decrypt the message or create signatures.

In order for a public key encryption to be feasible, it must:

  1. Make harder for an attacker to find the key used for the decryption of the ciphertext by just knowing the algorithm and the key used for the encryption of the plaintext.
  2. To provide an easy way to decrypt the ciphertext when the key for decryption is used.
  3. To provide a way in which either, the private key or public key, can be used for the encryption and the other key used for the decryption of the message. System that implement this policy is called RSA.

This is the way that normally pubic key works:

  1. Each user generate a pair of key that will be use for the encryption and decryption.
  2. Each user place one key (the public key) to a public register while holding the private key to themselves (the private key is never distributed).
  3. In case the private key is change, then the user must generate a new public key that will replace the older public key.

Symmetric Key Encryption Versus Public-Key Encryption

Before we go in deep comparing both encryption systems let clarify some points:

  1. The security of both system depend directly on the key/s length. The largest is the key, the harder is to break the cipher.
  2. While the public key may provide more security than symmetric key, it produce an overhead. This is the main reason that symmetric key is not considered obsolete with the apparition of the public key encryption.

Here are the differences between symmetric key (conventional) and public key:

  1. Symmetric key: Same algorithm using the same key is used for encryption and decrytion.
    Public-key: One algorithm is used for encryption and decryption but a pair of keys are generated. One key is used for the encryption, another is used for the decryption.
  2. Symmetric key: Sender and receiver must use the same algorithm and share the same key.
    Public-key: Sender and receiver must use the same algorithm, but each user must create a pair key. One of those keys (the public key) must be distributed from the receiver to the sender. The other key (private-key), the receiver must kept this key and make sure it doesn’t not get distributed.

Things that need to be resolve from the point of view of security:

  1. Symmetric key: The shared key must be kept in secret
    Public-key: One of the two keys (normally the private key) must be kept in secret.
  2. Symmetric and Public-key: It should be very hard for an attacker to decipher a message if there is no information available.
  3. Symmetric key: Even do the attacker may have knowledge of the algorithm and have possession of the ciphertext, it should be very hard to obtain the plaintext and/or the shared key.
    Public-key: Even do the attacker may have knowledge of the algorithm, samples of the ciphertext, and the public key, it should be very hard to obtain the plaintext and the other key.

How to Use Public Key Encryption

The public-key encryption can be used to provide:

  1. Confidentiality: Prevent attackers to know the content of the message
  2. Integrity: Prevent attackers for modifying the original message
  3. Authentication: To verify that the sender and/or receiver is not an attacker disguising as the sender and/or receiver
  4. Digital Signature:  To verify that the message is send by the sender and not the attacker

Confidentiality (secrecy):

  1. For a plaintext X where X = [X1, X2, …, Xn]
  2. User A will generate two keys: Public key (PUa) and Private key (PUb)
  3. User B will generate two keys: Public key (PUb) and Private key (PUa)
  4. For A to send a message to B, A will receive the public key (PUb) from B.
  5. User A will encrypt the plaintext (X) using the public key (PUb) from user B with the encryption algorithm (E) to generate the ciphertext (Y).
    Y = E(PUb, X)
  6. User B will receive the ciphertext (Y). Using private key (PRb) with the decryption algorithm (D), user B will obtain the plaintext (X).
    X = D(PRb, Y)

Authentication:

  1. User A generate a plaintext for user B. User A encrypt the plaintext (X) using the private key (PRa) and the encryption algorithm (E) then user A send the ciphertext (Y) to user B.
    Y = E(PRa, X)
  2. User B receive the ciphertext (Y) and using the public key (PUa) with the decryption algorithm (D), user B obtain the plaintext (X).
    X = D(PUa, Y)

Even do this provide authentication and provide safety against the alteration of the message, it does not provide confidentiality because:

  1. This Authentication do not prevent from eavesdropping.
  2. An attacker can decrypt the ciphertext (Y) using user A public key (PUa).

Since tthe message can be prepare only for user A because it was encrypted by using user A’s private key (PUa). this message can be used for the purpose of digital authentication (we can assure the message comes from user A since he provide the public key), and it provide data integrity ( prevention against alteration of the message) since it is impossible to alter the message without the private key (PRa).

Confidentiality and Authentication:

By using the the properties of Confidentiality and Authentication, we can create a scheme that provide more security.

  1. User A generates a pair of keys (PUa and PRa) while user B also generates a paid of keys (PUb and PRb)
  2. Sending the message: User A uses the private  key (PRa) with the encryption algorithm (E) to encrypt the plaintext (X) to a ciphertext (Y). Then user A uses the public key (PUb) from user B with the encryption algorithm (E) to encrypt the ciphertext again to a new ciphertext (Z).
    Z = E(PUb, E(PRa, X))
  3. Receiving the message: User B receive the ciphertext (Z) from user A. User B uses the decryption algorithm (D) with the private-key (PRb) with the ciphertext (Z) to produce ciphertext (Y). Then user B uses the public key (PUa) from user A with the decryption algorithm (D) to decrypt the ciphertext (Y) to the plaintext (X).
    X = D(PUa, D(PRb, Z))

Requirements for Public Key Encryption

  1. It should be easy for user A to generate a pair of keys: Public key (PUa) and private key (PRa).
  2. It should be easy for user B to generate a pair of keys: Public key (PUb) and private key (PRb).
  3. It should be easy for user A to encrypt the plaintext (M) to a ciphertext (C) using the public key (PUb) from user B.
    C = E(PUb, M)
  4. It should be easy for user B to decrypt the ciphertext (C) to the plaintext (M) using the private key (PRb).
    M = D(PRb, C)
    Since C  = E(PUb, M) then M = D(PRb, E(PUb, M))
  5. It should be very hard for an attacker while knowing the public key (PUb) from user B to guess correctly the private key (PRb) of user B.
  6. It should be very hard for the attacker while knowing the public key (PUb) from user B and the ciphertext (C) encrypted with the public key (PUb) to obtain the plaintext (M) send by user A to user B
  7. Both keys should be able to be used in either order for the encryption and decryption:
    M = D(PUb, E(PRb, M)) = D(PRb, E(PUb, M))

Algorithm such as RSA follow these requirements.

Share

Introduction to Network Security – Part 6

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used.

Poly-alphabetic Cipher

In the previous posting, we say that the mono-alphabetic cipher instead of shifting the alphabet a number of letters (Caesar cipher), its substitute each letter arbitrarily by mapping the plaintext letter map to a random arranged ciphertext. The only requirement for the ciphertext was that the letters must not be repeated. Now we are going to see a cipher that uses a set of related mono-alphabetic rules plus a key to determine which rule will be use to perform a transformation.

Vigenère Cipher

Encryption:

This cipher is similar to the Caesar cipher for the use of the 26 letters alphabet with the only different that we create a table in which:

  1. The columns represent the plain text
  2. The rows represent the key
  3. The alphabet inside the table is shifted to the right one letter one time for each letter of the alphabet key.

To be more clear, let take a quick look of the Caesar cipher table:
In this example, We started the alphabet on the letter ‘E’ because the key was 5.

Now, the Vigenère Cipher will apply this shifting 26 times, one time per row, for each letter of the alphabet that correspond to the key as follow:

Lets say that you have the following key “THIS  MESSAGE WAS FOR YOU”, and your key is “HELLO” then using the table:

We would obtain:

From a mathematical point of view we have:

  1. Lets assume that we take the letters of the alphabet from A to Z and be replace them with number starting from 0, for example: A = 0, B = 1, …, Z = 25.
  2. Since we have 26 letters in the alphabet, lets perform module of 26 on this equation.
  3. If ‘i’ is the letter position, P indicate the plaintext, K indicate the key, and C indicate the ciphertext then:
    C_i \equiv (P_i + K_i) \pmod {26}
    (For more information about the algebra involved in the Vigenère cipher: http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher)

Decryption

For decryption we only need to use a letter of the key to identify the row and the letter of the ciphertext in the row to identify the column, the letter designated to the column give us the plaintext letter.

From a mathematical point of view we have:

  1. Lets assume that we take the letters of the alphabet from A to Z and be replace them with number starting from 0, for example: A = 0, B = 1, …, Z = 25.
  2. Since we have 26 letters in the alphabet, lets perform module of 26 on this equation.
  3. If ‘i’ is the letter position, P indicate the plaintext, K indicate the key, and C indicate the ciphertext then:
    P_i \equiv (C_i - K_i) \pmod {26}
    (For more information about the algebra involved in the Vigenère cipher: http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher)

Security

This cipher is not secure. If two or more sequences are identical inside the plaintext, we run the risk that identical ciphertext sequence will be generated. The attacker can use these repetition in the ciphertext to make a deduction about what is the plaintext. The more plaintext is needed to encrypt, the more chances that the ciphertext can be broken or the key found.

As an example, lets assume we have the following:
Plaintext:   WE RUN WHEN WE WERE DISCOVER BY THEM
Key:             RUNNING NO RUNNING NO RUNNING NO

This would give us a ciphertext in which we can spot the repetitions:

The only way around this problem is by using the Autokey cipher.

Autokey Cipher

An auto-key cipher is the concept of generating a key that does not have a repetition cycle.

Instead of having a plaintext and a key such as this example:
Plaintext:   WE RUN WHEN WE WERE DISCOVER BY THEM
Key:             RUNNING NO RUNNING NO RUNNING NO

We could have the following key:
Plaintext:   WE RUN WHEN WE WERE DISCOVER BY THEM
Key:             RUNNING IS NOT THE SOLUTION THIS

This would give us a ciphertext with no repetitions:

One-Time Pad Cipher

The One-Time Pad cipher use a similar concept as the Auto-Key Cipher; however, the difference is the generation of a random key which is as long as the message. Also, it is required that at the end of the transmission, the random key generated must be destroyed.

The only problem is to find a secure way to distribute the random generated key between the principals.

Share

Introduction to Network Security – Part 5

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used.

Symmetric Encryption

In the symmetric encryption, the same key (normally a single-key) is used to perform the encryption and decryption of the ciphertext.

Symmetric Cipher Model: This model is performed by performing transformations and substitutions on the plaintext. A secret key, independent from the plaintext and the algorithm, is used to cipher the plaintext. After, the ciphertext plus the secret key is used with the decryption algorithm to obtain the original plaintext.

Symmetric Encryption is the opposite to the concept of public key distribution which will be explained in future postings.

Requirements:

  1. The cipher model must be mathematical expression:
    (E: Encryption, D: Decryption, X: plaintext, Y: ciphertext, K: secret key)

    Y = E(K, X)
    X = D(K, Y)
    
  2. Assumption that the encryption algorithm is known to the attacker.
  3. A strong encryption algorithm which in case the attacker would obtain or know some examples of the ciphertext and the plaintext produced from the ciphertext, the attacker would still be not able to obtain the key. This means that if the attacker would obtain the ciphertext, the attacker would not be able to obtain the secret key or the plain text.
  4. Secret key should be known only by the sender and the receiver of the ciphertext.
  5. The distribution of the secret key must be done in a secure fashion. For example, the use of a third party that would generate and provide in a secure way the key to the sender and the receiver.

Substitution Ciphers

In classical substitution ciphers, all the letters in the plaintext will be replaced by another letter, number, and/or symbol.

Caesar Cipher

History explains that Julius Caesar <http://www.roman-empire.net/republic/caesar-index.html> came up with a substitution cipher that he used in his campaigns for military affairs.

The cipher works in the following way:

  1. We use the alphabet of 26 letters:
    
    
  2. Under this alphabet, we will rewrite the alphabet by picking a letter as a starting point.
    Lets say our key indicate the starting point such as K = 4 so we begin with the letter ‘E’ then:
  3. This means that if we wish to send a plaintext (P) that says HELLO, the ciphertext (C) would be LIPPS, and the key (K) would be 4
  4. The mathematical way to represent this cipher will be the follows:
    1. Give each letter of the alphabet a number:
      A = 1, B = 2, C = 3, D = 4, E = 5,F = 6, G = 7, H = 8, J = 9, K = 10, L = 11, M = 12, N = 13, O = 14,P = 15, Q = 16, R = 17, S = 18, T = 19, U = 20, V = 21, W = 22, X = 23, Y = 24, Z = 25.
    2. Encryption Algorithm:
      E: Encryption, Ct: Ciphertext, Pt: Plaintext, K: secret key

      Ct = E(Pt)
         = (Pt + K) mod 26
    3. Decryption Algorithm:
      D: Decryptor, Ct: Ciphertext, Pt: Plaintext, K: secret key

      Pt = D(Ct)
         = (26 + (Ct - K)) mod 26
  5. The weakness of this cipher is that it can be broken by brute force. We just need to test the 25 combinations of different keys  until we find the key that reveals the message.

Monoalphabetic Cipher

The mono-alphabetic cipher instead of shifting the alphabet a number of letters, its substitute each letter arbitrarily by mapping the plaintext letter map to a random arranged ciphertext. The only requirement for the ciphertext is that the letters must not be repeated.

Since we are using 26 letters of the alphabet the arrangement of the cipher can permute a total of 26! permutations.

If we wish to encode the word “HELLO”, we would obtain “NERRS”

Lets assume we wish to cipher a plaintext:

Plaintext = “THIS IS A SECRET MESSAGE ENCODED IN MONOALPHABETIC”

Ciphertext = “XNMW MW E WIGBIX OIWWEJI IPGSCIC MP OSPSERUEDIXMG”

The following website let you play a little with monoalphabetic cipher by randomizing for you the ciphertext:
<http://www.simonsingh.net/The_Black_Chamber/generalsubstitutionWithMenu.html>

The only problem is that this cipher can be exploited by doing regularities analysis over the frequency of the letters. Base on the language rules some letters are used more than others. For example, in English, the letter ‘E’ is the most common used in words, followed by A, I, O, N, R, S, T. Others letters such as K, J, Q, X, Z are less used than the rest.

The largest is the message, the most chances that the attacker can decrypt the message.
Just in this message “XNMW MW E WIGBIX OIWWEJI IPGSCIC MP OSPSERUEDIXMG” we have:

  • W = 6 letters
  • E = 4 letters
  • M = 4 letters
  • S = 3 letters
  • P = 2 letters
  • ….

And continue counting.

As you may notice the letter ‘W’ of the encrypted message have the most counts, so we could  assume that this is the letter E of the plaintext.

If you are interested to know the frequency of letters in English you can go to the following website:
<http://www.cryptograms.org/letter-frequencies.php>

For more information about attacking mono-alphabetic cipher, there is a good example on this website:
<http://unsecure.co.uk/attackingmonoalphabeticciphers.asp>

Playfair Cipher

Playfair is one way to improve the security of mono-alphabetic cipher by encrypting multiple letters.

Playfair Encryption

  1. Create a playfair key matrix:
    1. Create a matrix of letters based on a keyword. For this example, the matrix should be 5 by 5
    2. Fill in the letters of the keyword from left to right and from top to bottom. Make sure that there are not duplicate letters
    3. Fill the rest of the matrix with the other letters that are not in the keyboard, making sure to not duplicate letters.
    4. As a rule, the letter I and J count as one letter.
      • I am not sure the reason for this rule, except the following:
        • First, it make it harder to decrypt the message since one letter is missing.
        • Second, in some languages, the J and I would have the same pronunciation.
          For example, my last name Carlstein was originally written as Karlštejn.
      • In case you know the real reason, please let me know and give me a reference to verify (thanks).
    5. Example of playfair key matrix:
      1. Let use the keyword: “EDUCATOR”
      2. The table should looks like this:
      3. Notice that I and J are counted as one letter
  2. The next step is to encrypt the plaintext taking two letters at the time.
    1. In case a two letters are the same (repeated), we must insert a filler letter (use the letter X as the filler). For example:
      HELLO → HE LX LO
    2. In case two letters are in the same row, replace each letter with the letter to the right. In case the letter is at the last column, pick the letter of the first row (the table is considerate to be circular). For example, lets say we have the letters D and A:

      1. D → U and A → E
      2. Therefore DA became UE
    3. In case two letters are in the same column, replace each letter with the letter below. In case the letter is at the last row, pick the letter of the first row (the table is considerate to be circular). For example, lets say we have the letters T and V:

      1. T → G and V → E
      2. Therefore TV became GE
    4. In case two letter are in different row and column, the first letter will be replaced with another letter of the same row on the column of the second letter. The second letter will be replaced with another letter of the same row on the column of the first letter. For example lets say we have the letters O and Q:

      1. To replace the letter O:
        1. This means that O → B
      2. To replace the letter Q:
        1. This means that Q → N
      3. Therefore OQ became BN

Playfair Decryption:

  1. Decrypt two letters at a time:
    1. In case two letters are in the same row, replace each letter with the letter to the left. In case the letter is at the last column, pick the letter of the first row (the table is considerate to be circular). For example, lets say we have the letters U and E:

      1. U → D and E → A
      2. Therefore UE became DA
    2. In case two letters are in the same column, replace each letter with the letter above. In case the letter is at the last row, pick the letter of the first row (the table is considerate to be circular). For example, lets say we have the letters G and E:

      1. G → T and E → V
      2. Therefore GE became TV
    3. In case two letter are in different row and column, the first letter will be replaced with another letter of the same row on the column of the second letter. The second letter will be replaced with another letter of the same row on the column of the first letter. For example lets say we have the letters B and N:

      1. To replace the letter B:
        1. This means that O → B
      2. To replace the letter Q:
        1. This means that Q → N
      3. Therefore OQ became BN
  2. After you will finish with the final message. You must remove any extra X that do not make sense in the message:
    HE LX LO → HELLO
Share