Cryptanalysis

Cryptanalysis
introduction
Affine Ciphers
The affine cipher uses a pair of keys in which the first key is from Z26* and the second is from Z26. The size of the key domain is 25 × 11 = 275.
Example 1
Use an affine cipher to encrypt the message “hello” with the key pair (7, 2).

Example 2
Use the affine cipher to decrypt the message “ZEBBW” with the key pair (7, 2) in modulus 26.
The additive cipher is a special case of an affine cipher in which k1 = 1. The multiplicative cipher is a special case of affine cipher in which k2 = 0.

Monoalphabetic Substitution Cipher
Because additive, multiplicative, and affine ciphers have small key domains, they are very vulnerable to brute-force attack.
A better solution is to create a mapping between each plaintext character and the corresponding ciphertext character. Alice and Bob can agree on a table showing the mapping for each character.
Polyalphabetic Ciphers
In polyalphabetic substitution, each occurrence of a character may have a different substitute. The relationship between a character in the plaintext to a character in the ciphertext is one-to-many.
Cryptanalysis
As cryptography is the science and art of creating secret codes, cryptanalysis is the science and art of breaking those codes.
Ciphertext-Only Attack
Known-Plaintext Attack
Chosen-Plaintext Attack
Chosen-Cipher text Attack
Example 5 brute-force attack
Eve has intercepted the ciphertext “UVACLYFZLJBYL”. Show how she can use a brute-force attack to break the cipher
Solution:
Eve tries keys from 1 to 7. With a key of 7, the plaintext is “not very secure”, which makes sense.
Example 6
Eve has intercepted the following ciphertext. Using a statistical
attack, find the plaintext.
Solution
When Eve tabulates the frequency of letters in this ciphertext, she
gets: I =14, V =13, S =12, and so on. The most common character
is I with 14 occurrences. This means key = 4.

•As cryptanalysts develop techniques for breaking ciphers, cryptographers must develop new ciphers which are more difficult to break
•This has been an ongoing process for over 2000 years
•Current cryptographic techniques are highly mathematical in nature
•Government Communications Headquarters (GCHQ) and the National Security Agency (NSA) currently undertake such work in the UK and USA respectively
Caesar Substitution Cipher
•One of the earliest recorded uses of a cipher is by Julius Caesar
•This (now simple) type of cipher is commonly known as the Caesar Substitution Cipher
•Each letter of the alphabet is substituted by another letter, according to the cipher algorithm

Ciphertext
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD
KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL,
QBOP KBO BXV OPVOV LBO LXRO CI SX’XJMI, KBO JCKO XPV
EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: ‘DJOXL EYPD, ICJ X
LBCMKXPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM
LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK.
SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?’
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK

Breaking the Cipher
•Simple substitution cipher
•Plain text in English
•We can use a technique known as frequency analysis to begin with
–In any given language, on average, each letter makes up a specific percentage of that written language
–Dependant on type of text
–Not effective for short messages
•Ciphertext is normally shown in capitals, whilst plaintext uses lower case
Frequency analysis of letters
•Frequency analysis for passages taken from English newspapers and novels (approx. 100,000 characters)
LetterPercentLetterPercentLetterPercentLetterPercenta8.2h6.1o7.5v1.0b1.5i7.0p1.9w2.4c2.8j0.2q0.1x0.2d4.3k0.8r6.0y2.0e12.7l4.0s6.3z0.1f2.2m2.4t9.1g2.0n6.7u2.8

Analysis of the Encrypted Message
•The three most common letters in the ciphertext are O, P and X
•Therefore it seems likely that these represent e, t or a in plaintext
•Next, lets see which letters O, P and X are adjacent to in the ciphertext

Analysis of the Encrypted Message
• Number of occurrences of letters adjacent to O, X and P in the ciphertext
ABCDEFGHIJKLMO1903111014601X0701111024630P1056000001122NOPQRSTUVWXYZO2280410030112X3190240332001P08000000110990

Analysis of the Encrypted Message
•Both O and X are neighbors with the majority of letters
–probably vowels a and e ?
•P avoids being neighbors with 15 letters
–possibly a consonant t ?
•In the ciphertext OO appears twice
–suggests O = e and therefore X = a
Analysis of the Encrypted Message
•X appears on its own in a single letter word
–confirms X = a
•Y also appears on its own
–suggests Y = i
•Also in the English language, h often appears before e, but rarely after e
–suggests B = h
Add the lowercase ‘guessed’ letters
PCQ VMJiPD LhiK LiSe KhahJaWaV haV ZCJPe EiPD
KhahJiUaJ LhJee KCPK. CP Lhe LhCMKaPV aPV IiJKL PiDhL,
QheP Khe haV ePVeV Lhe LaRe CI Sa’aJMI, Khe JCKe aPV
EiKKeV Lhe DJCMPV ZeICJe hiS, KaUiPD: ‘DJeaL EiPD, ICJ a
LhCMKaPV CPe PiDhLK i haNe ZeeP JeACMPLiPD LC UCM
Lhe IaZReK CI FaKL aDeK aPV Lhe ReDePVK CI aPAiePL EiPDK.
SaU i SaEe KC ZCRV aK LC AJaNe a IaNCMJ CI UCMJ SaGeKLU?’
eFiRCDMe, LaReK IJCS Lhe LhCMKaPV aPV CPe PiDhLK

Look for common words
•The most common three letter words in the English language are the and and
•Lhe appears six times
–suggests L = t
•aPV appears five times
–suggests P = n and V = d
Write in the common words
nCQ dMJinD thiK tiSe KhahJaWad had ZCJne EinD
KhahJiUaJ thJee KCnK. Cn the thCMKand and IiJKt niDht,
Qhen Khe had ended the taRe CI Sa’aJMI, Khe JCKe and
EiKKed the DJCMnd ZeICJe hiS, KaUinD: ‘DJeat EinD, ICJ a
thCMKand Cne niDhtK i haNe Zeen JeACMntinD tC UCM
the IaZReK CI FaKt aDeK and the ReDendK CI anAient EinDK.
SaU i SaEe KC ZCRd aK tC AJaNe a IaNCMJ CI UCMJ SaGeKtU?’
eFiRCDMe, taReK IJCS the thCMKand and Cne niDhtK

Keep Going
•We can continue the process and in this way end up with the original text
The Resultant Plaintext
Now during this time Shahrazad had borne King
Shahriyar three sons. On the thousand and first night,
when she had ended the tale of Ma’aruf, she rose and
kissed the ground before him, saying: ‘Great King, for a
thousand and one nights I have been recounting to you
the fables of past ages and the legends of ancient kings.
May I make so bold as to crave a favour of your majesty?’
Epilogue, Tales from the Thousand and One Nights

One for you to try
•PSIIZWFPCMFSW UWTFWUUAG CAU MQU JUSJDU OQS JASVFYU MQU FWXACGMAZPMZAU XSA PSIIZWFPCMFSW KUMOUUW FWYFVFYZCDG CWY SATCWFGCMFSWG. MAN MS FICTFWU C OSADY FW OQFPQ CDD XSAIG SX PSIIZWFPCMFSW QCVU KUUW AUISVUY; WS MUDUVFGFSW, WS ACYFS, WS MUDUJQSWUG, WS FWMUAWUM, WS GCM-WCV.
sol:
communication engineers are the people who provide the infrastructure for communication between individuals and organisations. try to imagine a world in which all forms of communication have been removed; no television, no radio, no telephones, no internet, no sat-nav.