MESSAGE AUTHENTICATION REQUIREMENTS

In the context of communications across a network, the following attacks can be identified.

1.                                       Disclosure: Release of message contents to any person or process not possess- ing the appropriate cryptographic key.

2.                                       Traffic analysis: Discovery of the pattern of traffic between parties. In a connection-oriented application, the frequency and duration of connections could be determined. In either a connection-oriented or connectionless environ- ment, the number and length of messages between parties could be determined.

3.                                       Masquerade: Insertion of messages into the network from a fraudulent source. This includes the creation of messages by an opponent that are purported to come from an authorized entity. Also included are fraudulent acknowledg- ments of message receipt or nonreceipt by someone other than the message recipient.

4.                                       Content modification: Changes to the contents of a message, including insertion, deletion, transposition, and modification.

5.                                       Sequence modification: Any modification to a sequence of messages between parties, including insertion, deletion, and reordering.

6.                                       Timing modification: Delay or replay of messages. In a connection-oriented application, an entire session or sequence of messages could be a replay of some previous valid session, or individual messages in the sequence could be delayed or replayed. In a connectionless application, an individual message (e.g., data- gram) could be delayed or replayed.

7.                                       Source repudiation: Denial of transmission of message by source.

8.                                       Destination repudiation: Denial of receipt of message by destination.

Measures to deal with the first two attacks are in the realm of message confi- dentiality and are dealt with in Part One. Measures to deal with items (3)  through

(2)                             in the foregoing list are generally regarded as message authentication. Mechanisms for dealing specifically with item (7) come under the heading of digital signatures. Generally, a digital signature technique will also counter some or all of the attacks listed under items (3) through (6). Dealing with item (8) may require a combination of the use of digital signatures and a protocol designed to counter this attack.

In summary, message authentication is a procedure to verify that received messages come from the alleged source and have not been altered. Message authentication may also verify sequencing and timeliness. A digital signature is an authentication technique that also includes measures to counter repudiation by the source.

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

The ElGamal Public Key Encryption Algorithm

The ElGamal Algorithm provides an alternative to the RSA for public key encryption. 

1) Security of the RSA depends on the (presumed) difficulty of factoring large integers. 

2) Security of the ElGamal algorithm depends on the (presumed) difficulty of computing discrete logs in a large prime modulus. 

ElGamal has the disadvantage that the ciphertext is twice as long as the plaintext. 

It has the advantage the same plaintext gives a different ciphertext (with near certainty) each time it is encrypted. 

Alice chooses 

i) A large prime pA (say 200 to 300 digits),

ii) A primitive element α A modulo pA, 

iii) A (possibly random) integer dA with 2 ≤ dA ≤ pA –2. 

Alice computes 

 iv) β A ≡ α A dA (mod pA). 

Alice’s public key is (pA, α A, β A). Her private key is dA.

Bob encrypts a short message M (M < pA) and sends it to Alice like this: 

i) Bob chooses a random integer k (which he keeps secret).

ii) Bob computes r ≡ α A k (mod pA) and t ≡ βA k M (mod pA), and then discards k.  

Bob sends his encrypted message (r, t) to Alice.

When Alice receives the encrypted message ( r, t), she decrypts (using her private key dA) by computing t r−dA. 

Note tr−dA ≡ βA k M ( α A k )−dA (mod pA) 

≡ ( α A dA ) k M ( α A k )−dA (mod pA) 

≡ M (mod pA)  

Even if Eve intercepts the ciphertext ( r, t), she cannot perform the calculation above because she doesn’t know dA. 

β A ≡ α A dA (mod pA), so dA ≡ L αA (β A) 

Eve can find dA if she can compute a discrete log in the large prime modulus pA, presumably a computation that is too difficult to be practical. 

Caution: Bob should choose a different random integer k for each message he sends to Alice. 

If M is a longer message, so it is divided into blocks, he should choose a different k for each block. 

Say he encrypts two messages (or blocks) M1 and M2, using the same k, producing ciphertexts

(r1, t1) = ( α A k , β A k M1), ( r2, t2) = ( α A k , β A k M2 ). 

Then t2 t1 −1 ≡ M2M1 −1 (mod p), M2 ≡ t2 t1 −1 M1 (mod p). If Eve intercepts both ciphertext messages and discovers one plaintext message M1, she can compute the other plaintext message M2.

Diffie Hellman key exchange algorithm

1. In Public key encryption schemes are secure only if authenticity of the public key is assured.
2. Diffie-Hellman key exchange is a simple public key algorithm.
3. The protocol enables 2 users to establish a secret key using a public key scheme based on discrete algorithms.
4. The protocol is secure only if the authenticity of the 2 participants can be established.
5. or this scheme, there are 2 publicly known numbers :
   • A prime number q
   • An integer α that is a primitive root of q.
   (Note: Premitive root of a prime number P is one, whose powers module P generate all the images from 1 to P-1)
6. Suppose users A and B wish to exchange the key.
   User A selects a random integer XA<q$X_A<q$ and computes
   YA=αXAmod q$Y_A={\alpha }^{XA}modq$
7. User B independently selects a random integer XB<q$X_B<q$ and compute
   YB=αXBmod q$Y_B={\alpha }^{XB}modq$
8. Each side keeps X value private and makes Y value available publicly to the other side user A computes the key as:
   k=(YB)XAmod q$k=(Y_B{)}^{XA}modq$
   User B computes the key as :
   k=(YA)XBmod q$k=(Y_A{)}^{XB}modq$
   The calculations produce identical results :
   k=(YB)XAmod q−>calculated by user A=(αXBmod q)XAmod q=(αXB)XA(mod q)−>By rules of modular arithmetic=αXB XAmod q=(αXA)XBmod q$$\begin{gathered} k=(Y_B{)}^{XA}modq->\text{calculated by user A} \\ =({\alpha }^{XB}modq{)}^{XA}modq \\ =({\alpha }^{XB}{)}^{XA}(modq)->\text{By rules of modular arithmetic} \\ ={\alpha }^{XBXA}modq \\ =({\alpha }^{XA}{)}^{XB}modq \end{gathered}$$
   k=(αXAmod q)XBmod q$k=({\alpha }^{XA}modq{)}^{XB}modq$
9. Diffie Hellman key Exchange Algorithm
   1. k=(YA)XBmodq$k=(Y_A{)}^{XB}modq$ -> same as calculated by B
   2. Global Public Elements
      q ; prime number
      α ; α < q and it is primitive root of q
   3. USER A KEY GENERATION
      Select Private key XAXA<q$X_A{X}_A<q$
      Calculation of Public key YAYA=αXAmod q$Y_A{Y}_A={\alpha }^{XA}modq$
   4. USER B KEY GENERATION
      Select Private key XBXB<q$X_B{X}_B<q$
      Calculation of Public key YBYB=αXBmod q$Y_B{Y}_B={\alpha }^{XB}modq$
   5. Calculation of Secret Key by A
      k=(YB)XAmod q$k=(Y_B{)}^{XA}modq$
   6. Calculation of Secret Key by B
      k=(YA)XBmod q$k=(Y_A{)}^{XB}modq$
10. The result is that two sides have exchanged a secret value.
11. Since XA$X_A$ and XB$X_B$ are private the other party can work only following ingredients:
    q,α,XA,XB$q,\alpha ,X_A,X_B$
    Note: YB=αXB$Y_B={\alpha }_{XB}$ mod a
    XB=dlogα,q(YB)$XB=d\log \alpha ,q(YB)$

↑$\uparrow$

$$ Discrete Logarithm

12. The algorithm security lies on the fact that it is easy to calculate exponential modulo a prime, last difficult to calculate to calculate discrete logarithm.

Figure 5.6 Diffie-Hellman Exchange Algorithm$$$$