How digital data encryption works: symmetric and asymmetric keys

 

An outline of modern encryption methods used to secure confidential information.

 

 

The characteristics of modular mathematics and the role of keys in encryption.

 

Encryption involves the use of an algorithm combined with a key to encrypt the information contained within a message. Data is translated from its original form into a meaningless state until the appropriate algorithm and key are used to decrypt the data. Both the algorithm and the keys exploit the characteristics of modular mathematics.

 

Most arithmetical operations can be reversed: in traditional mathematics division can be undone by multiplication. In modular mathematics however the quotient of the number is discarded and therefore cannot be recalculated by reversing the operation. This can be described as a one-way or trapdoor function: see Table 2.

 

The role of the keys in encrypting and decrypting the data lie in their relationship with each other to create a ‘key pair’ which have the ability to repeat the mathematical operation rather than reverse it to arrive at the original value.

 

For example the first row of Table 1 below contains the letters of the alphabet. The second row contains the alphabet that has been shifted 3 spaces to the right. The third row contains the letters from the second row shifted another 23 spaces to the right and have returned to their original value.

 

The keys 3 and 23 are therefore a key pair for a modulo value of 26 using the mathematical operation of addition. They form a key pair because one key encrypts and one key decrypts and where 3 + 23 = 26 mod 26 which is congruent to 0 mod 26 where 0 is known as the identity in addition because it leaves an initial value unchanged when applied mathematically.

 

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Table 1

 

Modern computing power and the development of established algorithms aid in these calculations.

 

Explanation of modular mathematics and one-way functions.

 

You may find this Prime number generator useful when reading this article.

 

Step 1	Take a natural number y (a message)	171
Step 2	Convert into a modular form by dividing y by the chosen modulus n, in this case 677 and record the remainder r where:   171/677 = 0 X 677 with remainder 171.   Note that the chosen modulus n must be a prime number and be large enough to incorporate the complete set of elements encoded for the encryption scheme and in this case is 677. The encryption key 143 need not be prime for encryption using multiplication. See Conditions for successful encryption below.	r mod n   171 mod 677
Step 3	Apply a further mathematical operation to the result in Step 2. In this case we use multiplication and multiply by the key: the number 143.   The result is given in a modular form where: (171 X 143)/677 = (24453)/677 = 36 X 677 with remainder 81.   Congruent means 'same remainder'.	171 X 143 mod 677   or   24453 mod 677   and this is congruent to   81 mod 677
In order to return to the value of 171 mod 677 in Step 2 which can be considered to be the unencrypted message or plaintext we require more information than is contained within the result in Step 3, 81 mod 677, which can be considered to be the encrypted message or ciphertext. Even if we know the encryption key, 143, we still cannot calculate the value of the original message.   The encryption key will have a mathematical partner and form a key pair that is capable of returning the encrypted message to the unencrypted state but it is this partner that can be computationally impractical for an unauthorised user to calculate. But it is possible to crack this one see Crack this example below. In practice however the numbers involved will be a considerably larger see Note on the level of encryption below.

Table 2

 

 

The keys used in data encryption can be described as symmetric or asymmetric.

 

 

 

Generation of a symmetric session key using the Diffie-Hellman process.

 

The Diffie-Hellman process allows independent and remote users to arrive at a common value without that value being exposed while in transit. The process involves the participants taking a pre-determined starting value and performing an agreed mathematical operation on that value with another secret value or number unique to each participant and capitalising on the one-way function properties of modular mathematics. The results, which to all intents and purposes are encrypted, would then be exchanged between the participants. By the nature of the commutative property of the agreed operation the application of each secret number on the encrypted result would reveal a value that is new and common to both participants, this valve could be used as a basis for a session key.

 

For example let us assume that Maggie and Tim wish to generate a common secret key.

 

In Table 3 below an agreed shared value is given for the modulus (n) and a starting value (v), these values do not need to be kept secret. Values are given for the participants secret numbers (m) and (t) respectively which are in this case to be used as powers, this is a clue to the agreed mathematical operation for the exchange: exponentiation.

 

Value for the modulus (n)	523
Value for Maggie’s secret number (m)	199
Value for Tim’s secret number (t)	462
Starting value (v)	23

Table 3

 

In Table 4 the two participants start with the same starting value (v) and when operated on by the respective secret numbers the encrypted results are exchanged and operated on again to produce a new value common to Maggie and Tim. This value could then be used as a basis for a session key.

 

Step 1	Maggie operates on v by exponentiation modulo n with m to give vm mod n and then sends the result to Tim.     Where 23199 / 523 has remainder 253.	vm mod n =   23199 mod 523   and this is congruent to   253 mod 523
Step 2	Tim operates on v by exponentiation modulo n with t to give vt mod n and then sends the result to Maggie.     Where 23462/ 523 has remainder 472.	vt mod n =   23462 mod 523   and this is congruent to   472 mod 523
Step 3	Maggie takes vt mod n received from Tim and operates on it by exponentiation modulo n with m to give vtm mod n.	vtm mod n = 472199 mod 523   and this is congruent to   488 mod 523
Step 4	Tim takes vm mod n received from Maggie and operates on it by exponentiation modulo n with t to give vmt mod n.     They have both arrived at the same value.	vmt mod n = 253462 mod 523   and this is congruent to   488 mod 523

Table 4

 

I will not be discussing symmetric keys in this article again but will concentrate on asymmetric key encryption.

 

 

 

 

Cracking the multiplicative cipher.

 

The example I gave of a simple multiplicative cipher in Table 2 above gave us:

 

plaintext of 171 mod 677

 

ciphertext of 81 mod 677

 

where the encryption key was 143 for modulo 677.

 

So is it possible to find the decryption key, crack the encryption and obtain the plaintext from the information we have: the ciphertext, the encryption key and the size of the modulus? Yes it is and I will show you how.

 

Let us go back a step to the additive cipher example at the beginning of this article, Table 1, where I said that :

 

"they form a key pair because one key encrypts and one key decrypts and where 3 + 23 = 26 mod 26 which is congruent to 0 mod 26 where 0 is known as the identity in addition because it leaves an initial value unchanged when applied mathematically".

 

Well the value of the identity for the mathematical operation of multiplication is 1 because multiplying by 1 leaves an initial value unchanged. Working directly from that result the decryption key is therefore a value x that when multiplied with the encryption key K will give the result 1 for the given modulus n that is: x X K = 1 mod n.

 

For this example then: x X 143 = 1 mod 677 where x is the decryption key.

 

That sounds straightforward and we could simply progress through every single possible value for the decryption key until we get the value we require. Unfortunately for modulo 677 because the number 677 is a prime number this results in the number of potential keys of 666.

 

However thanks to a couple of brilliant mathematicians called Euler and Fermat there is a shortcut.

They worked out that where K is the encryption key and n is the modulus:

 

K^n-1 = 1 mod n and therefore:

 

K^n-2 X K = 1 mod n

 

provided that the modulus is prime and so K and n are coprime.

 

Because our modulus is prime then all numbers less than the size of the modulus are coprime.

 

Substituting our x for K^n-2 into the Euler-Fermat equation we get:

 

143^677-2 X 143 = 1 mod 677.

 

So the decryption key is: 143^677-2 mod 677 which is congruent to 303 mod 677.

 

So the decryption key is 303.

 

Applying this decryption key to the ciphertext we have:

 

81 X 303 = 24543 mod 677 which is congruent to 171 mod 677 which is the original plaintext.

 

Clearly the multiplicative cipher is unsatisfactory for securing confidential information.

 

 

 

 

Cracking the exponential cipher.

 

To keep the explanation simple I will use a modulo size of 29 with an encryption key of 5. The plaintext we shall encrypt is the number 2.

 

Applying the encryption key to the element we have 2⁵ mod 29 = 3 mod 29 giving us:

 

plaintext of 2 mod 29

 

ciphertext of 3 mod 29.

 

Decryption.

 

We could now call on our old friends Euler and Fermat whom we used to help us crack the multiplicative cipher but it is not quite as simple as that. To crack the exponential cipher we need to find a value x that when multiplied with the encryption key K will give the result 1 for the modulus n-1 that is: x X K = 1 mod (n-1).

 

For this example then: x X 5 = 1 mod 28 where x is the decryption key.

 

Now the Euler-Fermat equation in the form given for cracking the multiplicative cipher above only works when the modulus is prime and so therefore K and n are coprime. It is still the case that K and n are coprime because although the modulus is no longer prime the encryption key is. However the Euler-Fermat equation in its original form is no longer valid.

 

We may have to resort to a brute force attack and try all the possible keys and find the one that gives us the result of 1 mod 28.

 

For modulo 28 there is not too many. Using the Prime number generator we find here are only 9 prime numbers and therefore numbers that are coprime with 28 to choose from. They are: 2,3,5,7,11,13,17,19,23. Let us go for 17 as I am feeling lucky.

 

17 X 5 = 85 mod 28 with is congruent to 1 mod 28. Success!

 

So the decryption key is 17.

 

Applying this decryption key to the ciphertext we have:

 

3¹⁷ = 129140163 mod 29 which is congruent to 2 mod 29 the original plaintext.

 

Clearly the exponential cipher is more secure than the multiplicative cipher but still flawed for securing confidential information.

 

 

RSA algorithm: the unbreakable cipher?

 

The RSA encryption method named after Ron Rivest, Adi Shamir and Leonard Adleman the trio that invented it utilizes the mathematical operation of exponentiation but with an extra twist. The RSA algorithm derives its keys not from the modulus used in the actual encryption but from a new modulus that is related mathematically to the original modulus.

 

The modulus used for the encryption is formed from the product of two large prime numbers. The modulus used to calculate the keys is also formed from the product of two numbers. Those two numbers are derived from the original two primes. These prime numbers however once combined by multiplication remain secret due to the one-way or trapdoor function properties of multiplication and the difficulties to factorize extremely large numbers. Without those prime numbers it is not possible to calculate the modulus from which the keys are calculated.

 

The effect of this is that the encryption key can be widely distributed together with the modulus used in the encryption. These pieces of information are known as the 'public key'. Both pieces of information will be of little help to a cracker. The RSA cipher is an example of a public private key encryption cipher.

 

Table 5: a demonstration of the RSA cipher using small primes.

 

To encrypt   Step 1	Take two prime numbers a and b.	a = 5   b= 11
Step 2	Calculate the product of a and b and use this value as the modulus n.   n will not be prime.	a X b = n   5 X 11 = 55
Step 3	Calculate the product of (a-1)(b-1) and use this value for the modulus m.	(a-1)(b-1) = m   4 X 10 = 40
Step 4	Choose an suitable encryption key K so that it is less than and coprime with m.   K must be prime.	K = 7
Step 5	Encrypt the plaintext message p, 9 for example, with the encryption key K using exponentiation with the modulus n to create the ciphertext c.	pk = c mod n   97 = 4 mod 55
To decrypt   Step 1	Calculate the decryption key x so that: x X K = 1 mod m.   23 is the decryption key.	x X K = 1 mod m   23 X 7 = 1 mod m
Step 2	Decrypt the ciphertext c with the decryption key x.   The plaintext p is 9 as required.	cx = p mod n   423 = 9 mod 55
To encrypt you need K and the modulus n To decrypt you need x and the modulus n Given K, a and b you can calculate x Knowing K and n will not allow you to calculate a or b and therefore x   The product of a x b would in practice result in a number in excess of 200 digits. As of date 2009 it is not practically feasible to find the prime factors of numbers larger than 200 digits.   The RSA-1024 bit encryption cipher uses a 309 digit number for the modulus. For example: RSA-1024 = 13506641086599522334960321627880596993888147560566702752448514 3851526510604859533833940287150571909441798207282164471551373680419703964 1917430464965892742562393410208643832021103729587257623585096431105640735 0150818751067659462920556368552947521350085287941637732853390610975054433 4999811150056977236890927563

Table 5

 

There is currently work being undertaken to discover algorithms that are able either to factorize these large numbers or decrypt the cipher without the need for factorization. Alongside this we have the exciting new encryption methods being investigated and developed including quantum encryption.

 

 

 

 

Article by: David Beet.

Date: 1st July 2009.

 

 

Back to top.

 

 

Copyright © 2006-2012 justfigures.co.uk