Algorithms and Encryption Algorithms
You could view an algorithm as just another word for formula. Algorithms were in daily
use long before computers were ever heard of and they are merely routines for
performing mathematical tasks. As an example, the algorithm (or formula as it used to
be called) for calculating the area of the four walls of a room is “Add the length and
breadth, multiply by the height and then multiply by 2”.
An encryption algorithm is a set of procedures which makes intelligible information
completely unintelligible. However, it is of no use whatsoever if it does not provide
means for restoring the information to an intelligible state at a subsequent stage.
Plaintext
Plaintext is information in the form in which it was originally written, i.e. intelligible
information. It is more often than not in the form of sentences and paragraphs, but it
may also be a set of engineering drawings or a list of names.
Ciphertext
Cipher means “put into secret writing” – in other words scramble intelligible text.
Ciphertext is information that has been rendered unintelligible by being encrypted. For
example, Plaintext of HELLO when converted to Ciphertext might become PMSVQ.
Caesar Cipher
The simplest and oldest encryption algorithm is the Caesar Cipher once used by the
Roman army, but now considered too basic for even the most undemanding of users.
The basic form of the Caesar Cipher algorithm is "Shift the letter to the next one along,
bearing in mind that A follows Z". Examples are: Plaintext: HELLO Ciphertext: IFMMP or
Plaintext: ZEBRA Ciphertext: AFCSB. Alternatively you can shift the letter 2 or more along.
In the case where you “shift 3 along” HELLO becomes KHOOR.
Session Key
The session key is the secret piece of information which both sender and receiver share
and which, as its name suggests, changes with every new message or session. In the
case of the Caesar Cipher the key would be in the range 1 to 25. Where you only shift
the letter to the next one along, this means that the session key = 1.
Different numbering systems
The decimal number system which we use in everyday arithmetic is not very suitable for
use in computers. The alternatives are to use binary numbers or Hexadecimal (Hex)
numbers.
Binary Numbers are based on 2 and Hex numbers are based on 16. To illustrate this, 0
– 15 (decimal) would be represented as:
Decimal: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Binary: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101
1110 1111
Hex: 0 1 2 3 4 5 6 7 8 9 A B C D E F
Comparing numbering systems
The decimal number 1,000,000,000,000 = one trillion = 10^12 is equivalent to 2^39.8 =
40 bits. The rule of thumb for converting multi-figure decimal number to bits is to divide
by 0.301. To reverse the process, multiply by 0.301. To convert bits to hex, divide by 4. A
comparison table:
Decimal digits 12 39 77 154 14796 139
Bits 40 128 256 512 49152 448
Hex digits 10 32 64 128 12288 112
Key Strength
The longer the session key the stronger the encryption algorithm and hence the harder it
becomes to penetrate the key to calculate the algorithm and get access to the actual
Plaintext. The international Data Encryption Standard (DES) is not measured in decimal
numbers, because the key is binary. The DES key is 56 bits, so a typical DES session
key could be:
10001111101010101111000010101100001101010101111100000001 (56 bits)
Since there are 72, 057, 594, 037, 927, 936 different ways of creating a selection of 56
bits, this number becomes the measure of the algorithm's key strength in decimal
notation.
The strongest Diplomatic Standard Algorithm key strength is Hawthorne Davies’
TOUAREG Encryption Algorithm used in CRYPTETO. It uses a session key equivalent
to 49,152 bits.
Symmetric Cipher (Encryption Algorithm) / Asymmetric Cipher
Having established how algorithms, ciphers, session keys and key strengths inter-
relate, it is important to know the difference between symmetric and asymmetric
ciphers. An example of a symmetric cipher is DES (the Data Encryption standard). The
56-bit key that encrypts the Plaintext is identical to the 56-bit key that decrypts the
Ciphertext. In the case of an asymmetric cipher the key that decrypts the Ciphertext is
quite different from the key used for encrypting the Plaintext. Further, it is mathematically
impossible to calculate one given the other. This can be a major advantage in making it
easier to transfer keys between sender and receiver.
Block Cipher / Stream Cipher / Pseudo-Random Stream
The two main types of cipher used commercially are Block ciphers and Stream ciphers.
A Block cipher takes Plaintext, a block of 64-bits at a time, and mixes the session key
into each block using bit handling techniques such as shifting and XORing.
1 xor 1 = 0 0 xor 1 = 1
1 xor 0 = 1 0 xor 0 = 0
To achieve this, the process is repeated by taking the output of the first mixing process
and re-mixing it with the key. Each re-mixing process is called a “round”. Standard
DES uses 16 rounds. Other block ciphers use 32 and even 64 rounds.
Stream Ciphers use an encryption principle first proposed by Vigenere in the sixteenth
century. You won’t find his blog anywhere! In a Stream Cipher the session key is
broken down into a set of starter numbers called Primitives. The primitives generate a
Pseudo-Random stream. If the stream is truly random, the unfortunate receiver at the
other end cannot recreate it. Since, however, a Stream Cipher is symmetric, the
receiver can use the same primitives to recreate the stream. The stream is added to the
Plaintext and has the effect of disguising it completely. The Plaintext is restored by
subtracting the same Pseudo-Random Stream from the Ciphertext.
Multiple Fermat Sequence
A Fermat Sequence is a sequence formed by successive multiplications of a base
number modulated by a prime number. You can generate your own by selecting the
prime 227 and generating the power sequence 1, 3, 9, 27, 81, 243 etc. A Multiple
Fermat Sequence is formed by combining several sequences. The Multiple Fermat
Sequence MFS-3 used in the HFX40 Cipher used three primes and has a cyclic length
of more than one million, million. The Cyclic length of MFS-2048, used in the TOUAREG
ENCRYPTION ALGORITHM has a cyclic length of 10^9891 – that’s one followed by 9891
zeros!
Non-recursive randomness
All methods for generating pseudo-randomness are recursive, that is to say, they start
from a set of primitive numbers and proceed by repeating the same process on each
element of the sequence. The sequence is defined by its primitives. Such a sequence
can never be purely random. Hawthorne Davies has perfected a way of generating non-
recursive randomness which adheres to the prime condition of pure randomness,
namely, that the next term in the sequence can never be determined by knowledge of all
preceding terms however numerous. We have developed a pocket-sized machine
which, combined with a laptop, produces non-recursive randomness at a fantastic
speed.
Salting
Salting is a method for “refreshing” a secret key, so that it can operate as a new secret
key. The TOUAREG ENCRYPTION ALGORITHM gets its name for the salting process
used in the key management of the algorithm. The name is in recognition of the
Touareg people’s salt caravans which traverse the Sahara desert.
Fusion
The FUSION SUBROUTINE is unique to Hawthorne Davies Ltd. It is a method of
combining a short open key with a long secret key to produce a new secret key. An
authentic example taken from the TOUAREG ENCRYPTION ALGORITHM is:
Secret Key:
BBA77EAB4835D91CAC59AF75836A0B98D64976F272B3B487933F4BB17A129861A5
59EA4176CEC11EEE5458982207A768578B090D0E6F3D3E7FAB3F5051397DFD367
EA37ECEC2F152C2F583D71BCC3A50AB64F3F0740D3D1F804297A339BF220
Open key representing the date 15th January 2010:
150110
New fused key:
20FA50920C34534B1B6BB9B8D78DA8D9486F5D68FB740C18D0CD47FC38B01F7B4
3488FACFC57C64E0801EDD830CB8613D4E3CBC487E5EEECC4E45FACF0A98B47A
F878A4B48F79C8F64D058F1E13A230293EE18DA20B3EC4BCD381B4C812A440
Entropy / Enigma Machine of WW2 / Key crashing
The important consideration in the design of a cipher is Entropy. Entropy, defined
simply, is the amount of “unravelling” you have to do to recover the Plaintext. If a cipher
has a very strong key, it does not necessarily mean that this is the measure of its
Entropy. It may be that a skilful cryptanalyst can see a way of getting round the
laborious task of trying all possible keys. Once this weakness is discovered, the
Entropy of the cipher is greatly reduced. The most famous example of loss of Entropy is
the Enigma machine of WW2. Its inventor thought he was adding to its Entropy by
introducing a back-plate which further scrambled the message and sent it back along a
different path. He did not realise that it simplified the cryptanalyst's task very
considerably.
If a cipher is well designed, then the common approach of trying to recover the Plaintext
is by “key crashing”, which means trying all possible keys. Its Entropy is measured by
this task. Every other method must be orders of magnitude more time consuming. The
security authorities largely rely on the key crashing approach because they have at their
disposal multiple super computers.
Attacks / Known Plaintext Attack
All methods of trying to break ciphers, other than crashing the key, are called Attacks,
and are largely the work of academics. There are two methods of Attack that are
commonly used. It must be remembered that session keys always change with each
new message, so a successful Attack on a message does not necessarily mean that
further messages will be vulnerable.
The most common form of attack is “Known Plaintext Attack”. In this form of Attack the
cryptanalyst knows, or guesses, some of the content of the message. It was the main
method by which the Enigma was broken on a routine basis. It was a particularly easy
method if it came from an over-courteous officer who might always start with "I have the
honour to report---".
It might be thought that KPA is a thing of the past. One of the problems of encrypting e-
commerce is that all messages are roughly the same in structure. More than 80% of a
1000-word document written in "Word" is also known, making a Stream Cipher very
vulnerable.
Key Dissemination / Public/Private Key / Public Key Infrastructure
The greatest problem in cryptography is Key Dissemination, i.e. the safe distribution of
the key. So the problem is how to convey the session key to the receiver. Obviously it
cannot be added as a header, unless of course, it is separately encrypted by a means
that is recoverable by both sender and receiver.
Public/Private Key (PPK)
Public Private Key is, in reality, an Asymmetric Cipher used to encrypt session keys. The
mathematics of Public/Private Key (PPK) depends on the fact that it is very difficult to
factorise a large number where there are only two factors. For example, there is not
much difficulty breaking 35 into 5 x 7. Breaking down 5,893 into 83 x 71 is just a little bit
more time consuming. 83 and 71 are prime numbers and can not be broken down
further. 853,996,753 = 29,989 x 28,477 is at the upper limit of pencil and paper
Arithmetic. 3,729,216,835,514,207 = 46,999,987 x 79,345,061 is at the upper limit of the
precision Arithmetic of an average PC. Beyond that, it soon becomes mathematically
infeasible.
With reference to work undertaken in December 2009, we now know that PPK requires
the equivalent of 300 decimal digits to beat today's computers. Complicated as it may
be, PPK delivers a session key very effectively. The sender uses the receiver's Public
Key to encrypt the Session Key. The Session Key then encrypts the message. The crypt
image of the session key is added as a header and the receiver gets the lot. Because
the cipher is asymmetric, the receiver can use his Private Key to decrypt the session key
and hence recover the message.
Public Key Infrastructure (PKI)
Public Key Infrastructure (PKI) is the name given to the management of Public / Private
Key technology. It involves issuing and maintaining Certification of all Public Keys,
otherwise it would be easy for an eavesdropper to deceive a sender into using his
public key instead of the intended receiver's. Certificating Authorities who offer PKI
services have to be monitored. Since encrypted traffic is international, who monitors the
monitors? Public Key Infrastructure, as a means of managing everyday e-commerce, is
a hammer to crack a nut.
Repudiation / Authentication / Integrity
Cryptography is not solely about sending secret messages. The world of industry and
commerce is, of course, concerned about secrecy, but it is also concerned about fraud
and deception. Cryptography can solve problems of Repudiation, where one of two
parties refuses to meet his obligations under an electronically created document,
claiming, rightly or wrongly, that it has been altered to his disadvantage. This raises
issues of Authentication (is the author who he claims to be?) and Integrity (has the
document been tampered with en route?)
Cryptographic Hash
A cryptographic hash is bit string of information which has the capability of preserving
any file of information from fraudulent alteration. The fundamental property of a hash
algorithm is that it is mathematically infeasible to make the slightest alteration in the file
without altering the hash. It must also be infeasible to construct a document to “fit” a
given hash. The internationally recognised HFX40-I hash algorithm, published in
Geneva on 26th November 1996, is the work of Dr William McMullen Hawthorne. In a
recent test a 20-page government document sent to HAWTHORNE DAVIES Ltd was
processed by HFX40-I to create the hash value: 233AC0793F61. The document was
then altered by removing a single colon from the text. This had the effect of altering the
hash value to: 54BCAC25DD46.
And that’s just the beginning……
Hawthorne Davies hopes that this has given you a basic understanding of how the
various elements of Encryption pull together. The subject can be, and is, far more
complex. If you are keen to learn more there is plenty more Encryption technology and
jargon around.
Hawthorne Davies’ research programmes are very innovative, and as a result, we have
to confess to adding lots of new jargon. Some of our favourite terms and expressions,
that we hope one day to explain to you, are:
SUN WHEEL, PLANET WHEEL
PRE-TABULATED CIPHER, MULTI-MODE CIPHER, INFINITELY SCALABLE CIPHER
CELLAR KEY, MUTUAL KEY
ACCUMULATED MAXIMUM RUNS TEST, YELLOW JERSEY TEST
ELECTRONIC WATERMARKING, ELECTRONIC WITNESSING . . . . . .
|
|