Contents:

1) Small Introduction
2) Algorithm
3) Easy Example
4) How to break harder implementations
5) Homework {for those who are in my list}

This algorithm is still used to protect the information, so it will be very useful to know it for us and to understand the basics of Cryptoanalisys. To understand material that is provide you have to have some background in Mathematics, and if you are willing to be more involved in this activity, experienced crackers need it. If you are not, we will make everything to introduce this kind of protection, but you need more practice, that's why I am going to prepare some programs based on those crypto-systems and will find Software that uses those.

Conditions:

Algorithm:

Let's assume that you want to encrypt this set of binary digits;

X={1,1,0,1,1,0,0,0,1,0}. And you want to choose any set of integers; this set of integers has to be properly choosen. Firstly, I will show you what happens when user of this crypto-system chooses a bad set.

For example, you choose a integer set that satisfies the folowing condition:

1) Sum of (a_1+a_2+a_3+...+a_[n-1]) < a_n

It is very easy to recover the message you encrypt using this set.

Bad Chosen_Set: A={23,47,91,203,450,977,1792,2256,4052,7309}

Note that number of elements in X and A sets must be equal.

So, Y=a_1*x_1+a_2*x_2+a_3*x_3+...+a_n*x_n ; substituting our values we will get that Y equals:

Y=1*23+1*47+0*91+1*203+1*450+0*977+0*1792+0*2256+1*4052+0*7309=4775

As I said before, set of integers A and sum of elements after multiplication are released to the public, so if the user chosed this set we can easily get the initial text. Here is the way:

You go backwards;

4775<a_10=7309, so x_10=0

4775>a_9 =4052, so x_9 =1 {here we substruct 4775-4052=723}

723<a_8 =2256, so x_8 =0

723>a_7 =1792, so x_7 =0 {590-301=289}

723<a_6 = 977, so x_6 =0

723>a_5 = 450, so x_5 =1 {723-450=273}

273>a_4 = 203, so x_4 =1 {273-203= 70}

70<a_3 = 91, so x_3 =0

70>a_2 = 47, so x_2 =1 { 70 - 47= 23}

23=a_1 = 23, so x_1 =1

-----As, you can see, the recovery is a very trivial calculation once the user of this crypto-system chose similar sequence of integers I have shown you. In most cases there are a very big number of bits that should be encrypted, but it would be very simple to code a program in any language to backward the calculations and in the end get the desired message.

In discribed public key algorithm, A represents the public key. Anyone can produce cyphertext Yfrom plaintext X by equation Y=A*X. But for this approach to be cryptographically strong, it must not be computationally feasible to obtain X from information assumed to be known to cryptoanalyst, thus preventing the process from being inverted by discovery of function g.

----Now, I will show what procedure you should you in order to decrypt the message if your initial condition when we do not have this convenient integer set.

For example, you have:

A = {2302, 5914, 892,1205,7329,7301,1023,4029,9823,278} ;information for public use

As you can see we can not implement the procedure I mentioned before. Now, we will will do some transformations. In this trapdoor knapsack the choice of vector A was carefully chosen, so it allows user to find the X (initial message) from Y (secret message) using the secret key that is known only to the user, and it makes it difficult for anyone else to find the initial message. We have to use the secret quantity to make proper transformations to make this problem easier to solve. The conversion function will become X=g'(A,Y, secret quantity), where function g' is easily calculated. This principle includes transformation of Y to Y', under following conditions:

1) We have to choose secret integers r & t, that are relatively prime.

2) Then, another secret prime integer, s, which has to be derived. It has to be a multiplicative inverse of t modulo r. In other words, following condition has to be satisfied:

s*t = 1 (mod r)

So, our transformation will look like this:

Y' = Y*s (mod r)

Y' = A'*X

This relations will allow us easy recovery of X, since A' is the same that we met earlier. It means that A' is used for knapsack algorithms that are very easily decyphered. In other words, we introduce trapdoor A' with secret quntities, r & t, that transformed hard knapsack problem (Vector A) into very easy one (Vector A') .

To construct this trapdoor, we have to choose set of integers , A', which elements satisfies a condition:

{bold} Sum of (a'_1+a'_2+a'_3+...+a'_[n-1]) < a'_n

A'={23,47,91,203,450,977,1792,2256,4052,7309} ; this set taken from previous example totally satisfies this condition. So, let me use this one to show how to handle hard knapsack algorithms.

Now, we have to choose the secret quantities as it was said before. But, they have to hold these conditions:

a) r> Sum of (a'_1+a'_2+a'_3+...+a'_[n-1] + a'_n)

b) r> t

c) r & t have to be relatively prime. It means that GCD (Greatest Common Divisor) has to be 1.

Calculation_a) So, lets pick up some primes. Before we do that, check what is the sum of all the elements. It should be: Sum = 17200. It would be easier to make a program to calculate what should be the r that is bigger than this Sum. I found that r can be 19211, which is prime number.

Calculation_b) We can pick up any prime that is less then r. I decided to choose 521.

Calculation_c) Now, we have to pick the number which is relatively prime to r. I found that t can be 521. To test that they are relatively prime we can use Euclid's algorithm. The principle of this algorithm is this:

19211=36*521+455

521= 1*455+66

455= 6* 66+59

66= 1* 59+ 7

59= 8* 7+ 3

7= 2* 3+ 1

3= 2* 1+ 1

1= 1* 1

The last 1 represents the GCD of 19211 & 521. It says that they are relatively prime.

Easily solvable knapsack vector A' is transformed into A via this relation:

A = A' * t (mod r)

Since, Y = A*X we can write:

Y = A' * t * X (mod r); where Y is: Y = Sum of [a'_i * x_i * t (mod r)] ;where i = 1,2,3...n

Multiplying both sides by s we get:

Y' = A' * X

It is now very easy to recover the message X. The idea here to use the secret quantities t & r is to transform Y to Y' that is the easiest form. It transforms hard knapsack problem to trivial one. To get to this point this equation has to be hold:

s*t=1 (mod r)

Since, s is a multiplicative inverse of t modulo r there is a unique solution for s. It was proved in the Euclid's algorithm that supported that s has only one solution. To assure that there is a unique solution, r must be greater than sum of all elements from the A set.

The value of s is computed again using Euclid's algorithm from previous example by rewriting it in reverse manner.

1 = 7 - 2*3

1 = 7 - 2*(59-8*7) = 17*7-2*59

1 = 17*(66-1*59)-2*59=17*66-19*59

1 = 17*66-19*(455-6*66)=131*66 -19*455

1 = 131* (521-1*455)-19*455= 131*521-150*455

1 = 131*521-150*(19211-36*521)

1 = 5531*521-150*19211

which is equivalent to :

1 = factor_1*SK+factor_2*r

It means that SK, in our case it is our s = 5531

If we go further Y' = Y * s (mod r) , which is desired result which required transformation from Y to Y'.

Let's find the message.

First find the values of A = A' * t (mod r)

A'={23,47,91,203,450,977,1792,2256,4052,7309}

t = 521

r = 19211

A becomes: a_1 = a'_1*t (mod r) which is equal to; a_1 = 11983

a_2 = a'_2*t (mod r) = 5276

.

.

.

A= {11983,5276,8989,9708,3918,9531,11504,3505,17093,15274}

Before decyphering, here is the overall quantities derived,secret & public:

1) A'={23,47,91,203,450,977,1792,2256,4052,7309} ----secret, derived

2) t =521 ----secret, chosen

3) r =19211 ----secret, chosen

4) s =5531 ----secret, derived

5) A= {11983,5276,8989,9708,3918,9531,11504,3505,17093,15274} ----non-secret, derived

A message X = {1,1,0,1,1,0,0,0,1,0},

is encrypted using A, as follows:

Y = A * X = (11983+5276+9708+3918+17093) = 47978

Multiplying Y by secret quantity of s results: Y' = 47978 * s (mod r)= 4775.

The first part of this essay described how to decypher from this point.

You have Y' & A', where A' elements satisfy this condition:

Sum of (a'_1+a'_2+a'_3+...+a'_[n-1]) < a'_n

So, all you have to do it to reverse this procedure as it was explained and you will get the message X.

You will have the same result. As you can see it is very convenient to use this method,

but once you have more elements in the X and respectively in A, you probably will wish to code a program that would do calculations for you. Although, here exist a problem when you will have to find big prime numbers, the same problem as in RSA algorithm, but it is possibly to create a 80 digit numbers using MIRACL library in C/C++, so the creation of these kind of numbers wll be explained in one of the next essays, prepared by HellForge.

N/A