Python Programming Project II Encryption/Decryption

Lecture #11

The Proposed Algorithm

Python Programming Project II ? Encryption/Decryption

The algorithm contains two segments: encryption and decryption. The encryption algorithm is performed by a given quadratic equation. The decryption algorithm is the opposite of encryption, which is performed by the "inverse" of the quadratic equation. Their core concepts are expressed in Table 2. A later section will discuss their mathematic theories and the practicability for use as an encryption mechanism in details.

Table 2: Mechanism

Encryption Algorithm

Decryption Algorithm

Let E be ax2 + bx + c with a > 0

Convert P to get x C = E(f(x)) = E(ax2 + bx + c)

Let D be g(f(x))

Solve x = - ?2-4 with x 0

2

D(x) = D(- ?2-4)

2

Convert x to get P

Apparently, only when the result of calculation based on the selected mathematical equation can be "inversed" back to its original value, the selected mathematical equation and its inverse are qualified for use as encryption and decryption mechanism.

Quadratic

Aufmann, Barker, and Lockwood (2003) defines the term "quadratic equation" as an equation

Equation and Its of the standard form ax2 + bx + c = 0 with a 0. The following illustrates how to find the roots

Inverse

of x by completing the square.

x2

+

x

+

=

0

x2

+

x

=

-

(

+

2

)

2

=

-

+

2 42

=

2-4 42

?2 - 4

+ 2 =

2

Solving for x then yields the following formula.

x

=

-

?2-4 2

In mathematics, the inverse of a function f is defined as a function, typically donated by the letter g, such that g(f(x)) = x. Since a quadratic function can be expressed as f(x) = ax2 + bx + c,

its inverse function g of f can be expressed as:

g

=

-

?2-4 2

In other words, the inverse of the quadratic is the curve formed by the union of the following two functions:

Python Programming ? Penniel P. Wu, PhD.

334

Design Concepts

g = -+2-4 and g = --2-4

2

2

The following is an example that explains how the calculation and inversion work. It necessary to note that when ax2 + bx + c = d with d0, the calculation can be performed on ax2

+ bx + (c-d) = 0.

Let f(x) = x2-4x-8, while x = 3.

Therefore, f(3) = 32-4?3-8 = -11

The inversion can be performed by solving x2 - 4x -8 = -11, or in the standard form x2 -4x + 3 = 0.

-?2-4

Since x =

2 , x is either 3 or 1.

In order to test the proposed encryption and decryption mechanism, the instructor develops a set of Python applications. The "Encryption" application takes three integer entries, a, b, and c, to specify a quadratic function f(x) = ax2 + bx + c. It also takes a string input as the "plaintext".

When the "Encrypt" button is clicked, the string input will be broken to a character array. A for..in loop will convert each character to its ASCII code, such as 65 for "A", and then send the converted ASCII code to a function named "calculate()" similar to that in one of the above sample codes. The "calculate()" function will assign the ASCII value to an variable x and perform a calculation based on the quadratic function f(x) = ax2 + bx + c. The calculated result will be temporarily appended to a string variable. The for loop will then iterate through the entire character array until the last character is processed. In order to delimit every adjacent hash-like value, the instructor chooses comma (,) as delimiter. A comma is placed between every two-calculated hash-like values. The following figure demonstrates how the applications work.

Figure 1. Sample Applications and

During a data exchange scheme, as illustrated by the following figure, the sender must privately notify the recipient what the single-key is (the key consists of values of chosen a, b, and c) before the transmission of "plaintexts". The sender then encrypts the "plaintexts" and only transmits the "ciphertexts" to the recipient through the Internet. Upon receiving the "ciphertexts", the recipient uses the decryption mechanism to obtain the "plaintexts". During the transmission, eavesdroppers can capture packets with sniffer tools; however, they must crack the encryption mechanism to obtain the "plaintexts".

Figure 2: Data Exchange Scheme Privately exchange a, b, c

Sender

36951, I am 23134, Bob. 37582,

42321, Encrypt

Internet eavesdropper

Recipient

36951,2 3134,37 I am 582,423 Bob. 21,3312

Decrypt

Python Programming ? Penniel P. Wu, PhD.

335

36951,23134,3

7582,42321,33

124,.....

???

The "Decrypt" application simply inverse the ciphertext to the original plaintext using the following formulas with a condition that the negative x is eliminated.

-?2-4

x =

2

The Encryption / Decryption Mechanism

Seeing that the value of x of a given ax2 + bx + c = 0 can be obtained by the following formulas, the instructor heuristically evaluates the feasibility to use a quadratic formula for computing hash-like values.

-?2-4

x =

2

The "math" package of Python language provides a function, sqrt(n), to return the square root of a given number n. By importing the "math" package, programmers can use the sqrt() function to find the square root of 6.25, as shown below.

import math print(math.sqrt(6.25))

The above formulas can be expressed as the follows in Python code. It is necessary to note that programmers can use any programming language to write similar code as well as applications for encryption and decryption, although the instructor chooses to use Python as the language for demonstration.

x = (-b + math.sqrt(b*b - 4*a*c)) / 2*a

and

x = (-b ? math.sqrt(b*b - 4*a*c)) / 2*a

The following is a simple function named "calculate()" that takes four parameters, x, a, b, and c, to perform the arithmetic calculation based on the formula f(x) =x2 - 4x ? 8 and then return the result of calculation. The "calculate()" function is a simplified version created to illustrate the proposed algorithm. Values of a, b, and c are set to be 1, -4, and -8 for the sake of demonstration. The value of x is set to 65; therefore, the "calculate()" function will convert the integer 65 (which is the ASCII code of the capital letter `A' and is said to be the "plaintext" in this case) with the designated quadratic function (f(x) =x2 - 4x ? 8) to produce another integer 3957 which is said to be the "ciphertext".

def calculate(x, a, b, c): return a*x*x+b*x+c

x = 65 a = 1 b = -4 c = -8 d = calculate(x, a, b, c)

print("f(x) =", d)

or, simply

Python Programming ? Penniel P. Wu, PhD.

336

def calculate(x, a, b, c): return a*x*x+b*x+c

x = 65 a = 1 b = -4 c = -8

print("f(x) =", calculate(x, a, b, c))

The following inverse() function can solve a quadratic function by letting x2 - 4x - 8 = 3957, and it will produce two x values, 65 and -61, with only one of them being the "plaintext". The reason why the instructor wrote the statement, c=c-d, is because the equation needs to be converted to x2 - 4x - 8 - 3957 = 0. The value of c was -8 before the conversion, and will be -8 ? 3957 after the conversion.

import math

def inverse(a, b, c, d): # convert ax2+bx+c=d to ax2+bx+c-d=0 c=c-d;

n1 = (-b+math.sqrt(b*b-4*a*c))/2*a; n2 = (-b-math.sqrt(b*b-4*a*c))/2*a;

print("n1 =", n1, "n2 =", n2)

a = 1 b = -4 c = -8 d = 3957 inverse(a, b, c, d)

The above code has a problem of calculation bias. When the value of a is larger than 1 or less than -1, the returned n1 and n2 are multiples of the given ASCII value. For example, the equation, 2x2-8x-16, is technically 2 ? (x2-4x-8); therefore, f(65) = 2x2-8x-16=7914 (or 2 ? 3957).

During the inverse calculation, the equation 2x2-8x-16 is simplified to x2-4x-8 for the sake of lowered complexity in calculation, as illustrated below.

f(x) = 2x2-8x-16 = 2 ? (x2-4x-8)

thus,

f(65) = 2x2-8x-16 = 2 ? (x2-4x-8) = 7914 = 2 ? 3957

so, x2-4x-8 = 3957

The above sample code does not take into consideration how the simplification of equation during calculation could affect the results. The following version of code illustrates how the bias of calculation is a problem. It uses f(x) = 2x2-8x-16 as formula, so a is set to be 2, b is -8, and c is -16, while x is still 65.

import math

def inverse(a, b, c, d):

Python Programming ? Penniel P. Wu, PhD.

337

c=c-d; n1 = (-b+math.sqrt(b*b-4*a*c))/2*a; n2 = (-b-math.sqrt(b*b-4*a*c))/2*a;

print("n1 =", n1, "n2 =", n2)

a = 2 b = -8 c = -16 d = 7914 inverse(a, b, c, d)

The following is the result of the above code. However, n1 and n2 are expected to be 65 and 61.

('n1 =', 260.0, 'n2 =', -244.0)

Interestingly, 260 = 65 ? 4 and -244 = -61 ? 4. In other words, 260 = 65 ? 22 and -244 = -61 ? 22. Since a = 2, 260 = 65 ? a2 and -244 = -61 ? a2. The following is the code that can avoid such calculation bias.

n1 = n1 / (a*a); n2 = n2 / (a*a);

Additionally, since ASCII code can only be a positive integer between 0 and 255; therefore, the negative value (such as -61) is eliminated and 65 is the "plaintext". The following is a revised version that will just return the positive value of x and ignore the negative one. It also eliminates the possible calculation bias.

import math

def inverse(a, b, c, d): c=c-d; n1 = (-b+math.sqrt(b*b-4*a*c))/2*a; n2 = (-b-math.sqrt(b*b-4*a*c))/2*a;

n1 = n1 / (a*a); n2 = n2 / (a*a);

if (n1 < 0): return n2 else: return n1

a = 1 b = -4 c = -8 d = 3957

print("x =", inverse(a, b, c, d))

Both n1 and n2 must be integers because values of ASCII codes are integers. The following could provide some sort of insurance because the "int()" function can convert a floating-point value to an integer.

if (n1 < 0): return int(n2) else: return int(n1)

The following is functionally equivalent to the above code, although their logics could seem to be reversed. By the way, ASCII code 0 is defined as NULL, which is typically not used. Therefore, the cases of (n1 == 0) or (n2 == 0) can be omitted in this program.

Python Programming ? Penniel P. Wu, PhD.

338

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download