Knapsack Encryption

RSA is just one way of doing public key encryption. Knapsack is a good alternative where we can create a public key and a private one. The knapsack problem defines a problem where we have a number of weights and then must pack our knapsack with the minimum number of weights that will make it a given weight. In general the problem is:

• Given a set of numbers A and a number b.
• Find a subset of A which sums to b (or gets nearest to it).

So imagine you have a set of weights of 1, 4, 6, 8 and 15, and we want to get a weight of 28, we could thus use 1, 4, 8 and 15 (1+4+8+15=28).

So our code would become 11011 (represented by '1', '4', no '6', '8' and '15'.

Then if our plain text is 10011, with a knapsack of 1, 4, 6, 8, 15, we have a cipher text of 1+4+8+15 which gives us 28.

A plain text of 00001 will give us a cipher text of 15.

With public key cryptography we have two knapsack problems. One of which is easy to solve (private key), and the other difficult (public key).

Creating a public and a private key

We can now create a super-increasing sequence with our weights where the cur-rent value is greater than the sum of the preceding ones, such as {1, 2, 4, 9, 20, 38}. Super-increasing sequences make it easy to solve the knapsack problem, where we take the total weight, and compare it with the largest weight, if it is greater than the weight, it is in it, otherwise it is not.

For example with weights of {1,2,4,9,20,38} with a value of 54, we get:

        

Check 54 for 38? Yes (smaller than 54). [1] We now have a balance of 16.
Check 16 for 20? No. [0].

Check 5 for 4? Yes. [1]. We now have a balance of 1.
Check 16 for 9? Yes. [1]. We now have a balance of 5.
Check 1 for 2? No. [0].

Check 1 for 1? Yes [1].

Our result is 101101.

If we have a non-super-increasing knapsack such as {1,3,4,6,10,12,41}, and have to make 54, it is much more difficult. So a non-super-increasing knapsack can be the public key, and the super-increasing one is the private key.

Making the Public Key

We first start with our super-increasing sequence, such as {1,2,4,10,20,40} and take the values and multiply by a number n, and take a modulus (m) of a value which is greater than the total (m - such as 120). For n we make sure that there are no common factors with any of the numbers. Let's select an n value of 53, so we get:

1×53 mod(120) = 53

2×53 mod(120) = 106
4×53 mod(120) = 92

20×53 mod(120) = 100
10×53 mod(120) = 50

40×53 mod(120) = 80

So the public key is: {53,106,92,50,100,80} and the private key is {1, 2, 4, 10, 20,40}. The public key will be difficult to factor while the private key will be easy. Let's try to send a message that is in binary code:

111010 101101 111001

We have six weights so we split into three groups of six weights:

111010 = 53 + 106 + 92 + 100 = 351
101101 = 53+ 92 + 50 + 80 = 275

111001 = 53 + 106 + 92 + 80 = 331

Our cipher text is thus 351 275 331.

The two numbers known by the receiver is thus 120 (m - modulus) and 53 (n multiplier).

We need n-1, which is a multiplicative inverse of n mod m, i.e. n(n−1) = 1 mod m. For this we find the inverse of n:

n-1 = 53-1 mod 120

(53 x _n) mod 120 = 1 

So we try values of n-1 in (53 x n-1 mod 120) in order to get a result of 1:

n-1  Result
1     53

3    39
2    106
...

77  1
75   15

76  68

The inverse of 53 mod 120 is 77

Working out (we are searching for a value of 1)

Val (val * n) mod m

1 53

2 106

3 39

4 92

5 25

6 78

7 11

8 64

9 117

10 50

11 103

12 36

13 89

14 22

15 75

16 8

17 61

18 114

19 47

20 100

21 33

22 86

23 19

24 72

25 5

26 58

27 111

28 44

29 97

30 30

31 83

32 16

33 69

34 2

35 55

36 108

37 41

38 94

39 27

40 80

41 13

42 66

43 119

44 52

45 105

46 38

47 91

48 24

49 77

50 10

51 63

52 116

53 49

54 102

55 35

56 88

57 21

58 74

59 7

60 60

61 113

62 46

63 99

64 32

65 85

66 18

67 71

68 4

69 57

70 110

71 43

72 96

73 29

74 82

75 15

76 68

77 1

Found it at 77

RSA cryptosystem

RSA is an asymmetric system , which means that a key pair will be generated (we will see how soon) , a public key and a private key , obviously you keep your private key secure and pass around the public one.

The algorithm was published in the 70’s by Ron Rivest, Adi Shamir, and Leonard Adleman, hence RSA , and it sort of implement’s a trapdoor function such as Diffie’s one.

RSA is rather slow so it’s hardly used to encrypt data , more frequently it is used to encrypt and pass around symmetric keys which can actually deal with encryption at a faster speed.

We’ve got a message (“HELLO”) , and we’ve picked two tuples with two numbers each ( I will explain how these came about later). Obviously there’s no arithmetic operation we can perform with strings , so the message has to be convert it to something , so let’s say “HELLO” converts using some conversion algo to “2”

Normally , in production , a lot of different techniques are used to encode the message and padding is also used

The interesting bit is how we come about those numbers , and how (5,14) is related to (11,14), and this is the interesting part i believe , let’s start:

The details of the Decryption/Encryption pair:

1. Pick two prime numbers , I will pick 2 and 7 , lets call them p and q

P = 2 and Q = 7

2. Multiply P and Q , and that becomes the modulus

N = P * Q = 14

3. Make a list between 1 and 14 and remove the common factors:

Public Key Cryptography

Unlike symmetric key cryptography, we do not find historical use of public-key cryptography. It is a relatively new concept.

Symmetric cryptography was well suited for organizations such as governments, military, and big financial corporations were involved in the classified communication.

With the spread of more unsecure computer networks in last few decades, a genuine need was felt to use cryptography at larger scale. The symmetric key was found to be non-practical due to challenges it faced for key management. This gave rise to the public key cryptosystems.

The process of encryption and decryption is depicted in the following illustration −