Caeser's cipher and Diffie-Hallman key exchange

文章目录
  1. 1. Caeser’s cipher
  2. 2. Diffie-Hallman key exchange
  3. 3. reference
CipherDisk2000 from Wikipedia

In my IoT class, one of my coursework is to implement a Diffie-Hallman key exchange algorithm which is used to exchange data without leaking safty information in the network communications. In my experiment, some communications take place between a client and a server, the transmitted data have been encrypted and decrypt with Caeser’s cipher when sent to the server from client after the connection is built. So my task is just to add Diffie-Hallman key exchange to secure a message delivery. In this article, I’ll introduce two algorithms, Caeser’s cipher or shift cipher[1] and Diffie-Hallman key exchange.

Caeser’s cipher

Caeser’s cipher is one of the simplest and widely known techniques to do encrypt and decrypt. The task of this algorithm is to replace each alphabet to another alphabet. But how to get the new alphabet? Let me see an example:(公众号:正义的程序猿)

job done

The original data is “job done”, after the decryption, it is “qvi kvul”, the data is changed and we can not understand the meaning except the whitespace. Even though these alphabete have been disrupted, you can also find some regulations or patterns if you’re a sensetive person. That’s the secret of the Caeser’s cipher. The ASCII code of each alphabete is added 7 or each alphabete has been right shifted of 7.

shadow-character set from Wikipedia

In my data, the character ‘j’ has a ASCII code of 6A in Hex format(106 Dec format), while it is replaced by ‘q’ (71 in Hex format, 113 in Dec format). In this demo, we have a right shift of 7. (公众号:正义的程序猿)Also the shift key can be any number including positive and negtive number. If shift key is negtive, it means left shift. The data then can be transmitted with the encrypt format:

data transmit

Here is my code which can be used for the lower case letters:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void encrypt(unsigned char *input, unsigned char *output, int shiftKey)
{
int i;
int shift = shiftKey%26;
for (i=0; i<strlen(input); i++)
{
if (input[i]>='a' && input[i]<='z')
{
output[i] = input[i] + shift;
if (output[i]>'z') output[i]-=26;
}
else output[i] = input[i];
}
output[i] = 0;
}

In terms of the decryption, it is a reverse process. If right shift in the encrypt,(公众号:正义的程序猿) left shift should in the decrypt. So the code is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void decrypt(unsigned char *input, unsigned char *output, int shiftKey)
{
int i;
int shift = shiftKey%26;
for (i=0; i<strlen(input); i++)
{
if (input[i]>='a' && input[i]<='z')
{
output[i] = input[i] - shift;
if (output[i]<'a') output[i]+=26;
}
else output[i] = input[i];
}
output[i] = 0;
}

In my code, we use modular arithmetic, it can avoid the overflow of the scheme. Such as A → 0, B → 1, …, Z → 25.

Inclusion, Encryption of a letter x by a shift n can be described mathematically as:

En(x)=(x+n)mod26E_{n}(x)=(x+n) \mod {}26

Decryption is performed similarly: (公众号:正义的程序猿)

En(x)=(xn)mod26E_{n}(x)=(x-n) \mod {26}

Diffie-Hallman key exchange

Diffie-hallman key exchange is a mthod of changine keys over a public network securely, W. Diffie and M. E. Hellman published an article “New directions in cryptography” in 1976 [2], here is a color illustration of Diffie-Hallman key exchange:

Diffie-Hellman_Key_Exchange from wikipedia

The process begins by having the two parties, Alice and Bob, publicly agree on an arbitrary starting color that does not need to be kept secret (but should be different every time). In this example, the color is yellow. Each person also selects a secret color that they keep to themselves – in this case, red and blue-green. The crucial part of the process is that Alice and Bob each mix their own secret color together with their mutually shared color, resulting in orange-tan and light-blue mixtures respectively, and then publicly exchange the two mixed colors. Finally, each of them mixes the color they received from the partner with their own private color. The result is a final color mixture (yellow-brown in this case) that is identical to their partner’s final color mixture.

— from Wikipedia

The steps of Diffie-Hallman: (公众号:正义的程序猿)

  • Bot parties share some common information in public:
    • Modulus p, should be prime
    • Base g, should be a primitive root modulo of p
  • Each party select a secret number s and calculate another number by: r=gsmod(p)r=g^{s} \mod (p)
  • Bother parties change their calculated number, r
  • Each party uses the received number r to calculate a common key by: K=rsmod(p)K=r^{s} \mod (p)
  • Magically, both parties arrive to the same K value!!!

During the process, whoever knowing p, g and both r values,(公众号:正义的程序猿) but without any s, can not compute K. See a cryptographic explanation of Diffie-Hallman from wikipedia:

Cryptographic explanation of Diffie-Hallman

An demo of Diffie-Hallman:

illustration table of Diffie-Hallman

reference


  1. https://en.wikipedia.org/wiki/Caesar_cipher ↩︎

  2. W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. 22, no. 6, Nov 1976, pp. 644-654. ↩︎