Secure browsing and Escaping firewall by using SSH

Secure browsing and escaping firewall by using SSH

This article about how to build a secure browsing environment and how to escape firewall rules or even escaping ISPs rules over browsing (HTTP and HTTPS).

The idea here is to forward all your traffic down in a tunnel(SSH tunnel) into another server and that server forwards your traffic to its destination point.
The SOCKS protocol binds your browser to the tunnel via a local port.
First we going to try it on Linux OS and then on Android.

Linux OS

1- SSH installed on your local machine
2- Remote SSH server, you can get one for free http://shells.red-pill.eu
3- Internet browser

How To Do :

1- Establish a SSH tunnel between your local machine and the remote SSH server
ssh -D 4321 -f -C -q -N user@remote -p 22
-D : Launch a SOCKS server (SOCKS4 and SOCKS5 only) and bind it to a local port 4321
-f : Send ssh to go to background
-C : Enable compression mode for all data
-q : Enable quiet mode to suppress all warnings and messages
-N : Not to execute any remote commands
-p : SSH remote port

Note: Only root can forward privileged ports

So let's suppose i got a SSH server on www.xshellz.com with username "HamzaMegahed"
When i execute this command
ssh -D 4321 -f -C -q -N HamzaMegahed@shell.xShellz.com -p 22
Nothing happens because the program now is working in the background

Note: You can choose your own (4321 is just an example)
Note: You can make sure that the process in working in the background using ps aux | grep ssh
The output should be something like "ssh -D 4321 -f -C -q -N HamzaMegahed@shell.xShellz.com"

2- Bind your browser to SOCKS port
In Firefox
From Edit menu ---> Preferences --> Advanced --> Network --> Settings
Choose "Manual proxy configuration"
Delete all data from all data for (HTTP, SSL, FTP) and set ports to 0 except SOCKS Host
Set SOCKS Host to or localhost and set SOCKS port to 4321


Now we gonna try to block all HTTP requests and then try to go escape that block
- We gonna use iptables to drop all HTTP (port 80)
iptables -A OUTPUT -p tcp --destination-port 80 -j DROP
Now all outgoing communications to port 80 will be dropped and you can confirm it by using any internet browser

Note : The previous rule only if you want POC , and after you finish You have to delete that rule or you firewall is going to block all your HTTP requests
you can flush all iptables rules with iptables -F

- Then build our SSH tunnel
ssh -D 4321 -f -C -q -N HamzaMegahed@shell.xShellz.com -p 22
- Then bind the browser to SOCKS port (4321)
You will see that now port 80 is now working fine!

Configure SOCKS proxy in whole mode:
You can configure your local system to run all communications through SOCKS proxy without configuring each program (you don't have to configure your Internet browser also)
1- Open gnome-control-center
2- Choose Network
3- Choose Network proxy
4- Set method to "Manual"
5- Clear all then set SOCKS host to and Port 4321

Disable tunneling mode:

If you want to stop the tunneling first ps aux | grep ssh
and kill the process with a name like this "ssh -D 4321 -f -C -q -N HamzaMegahed@shell.xShellz.com" by its PID number . Don't forget to set your browser back to "Use system proxy settings" when you done tunneling.
In case you run whole mode just set the method to "None" and kill the SSH process.

Note: You can use this exact method on Windows OSs using PuTTY.
Note: You can choose any other Internet browser and do the same proxy configuration.

On Android
1- SSH installed on your android (i'm going to use ConnectBot)
2- Remote SSH server, you can get one for free http://shells.red-pill.eu
3- Internet browser

How TO DO:
1- Establish SSH connection between your mobile and the remote server by creating a new connection to ssh by entering UserName@RemoteHost:Port So in my case HamzaMegahed@shell.xShellz.com

after starting the connection then enter my password when prompted

2- Configure port forwards by click on the menu then select port forwards then hit the menu again and select add port forward.
Choose a name for the port forward then change type to Dynamic(SOCKS) then set source port to 4321 then hit create port forward.

In Firefox:

Open Firefox and in the URL bar enter about:config
click on search icon and search for "socks" and do this configuration exactly
set network.proxy.socks -->
set network.proxy.socks_port --> 4321
set network.proxy.socks_remote_dns --> true

click on search icon again and search for "proxy.type"
set network.proxy.type --> 1

Done !!
You can make sure by checking your ip address

Note : You can setup a public key authentication to skip entering your password each time.
1- click on menu and select Manage pubkeys then click again on the menu and select generate.
2- Choose a name for your key and select Load key on start then generate.

3- Long press on your key and then select copy public key.
4- Access your ssh and then execute echo "paste your key here" >> .ssh/authorized_keys  .Make sure the key is loaded before you access the server or public key authentication fails.

Disable tunneling mode:

1- Click on menu and select disconnect. 
2- From Firefox hit about:config.
3- Search for "socks" and reset all Values.
4- search for "proxy.type" and reset it to 5.



Cryptography 18

Digital Signature

Digital Signature is an authentication mechanism tha enable the creator of a message to attach a code that act as a signature.
Digital Signature is formed by taking the hash of the message and encrypting the message with the creator's private key.
Digital Signature grantees the source and integrity of the message.
Digital Signature is a public key technique but it cannot be used for encryption or key exchange.

-Digital Signature Properties:

1- It must verify the author and the time and the date of the signature.
2- It must authenticate the contents at the time of the signature.
3- It must be verifiable by third-parties to solve disputes.

Digital Signature Requirements:

1- The signature must be a bit pattern that depends on the message being singed.
2- The signature must use some information unique to the sender to prevent both forgery and denial.
3- It must be relatively easy to produce the digital signature.
4- It must be relatively easy to recognize and verify the digital signature.
5- It must be computationally infeasible to forge a digital signature.
6- It must be practical to retain a copy of the digital signature in storage.

ELgamal Digital Signature Scheme:

Elgamal Digital Signature uses the private key for encryption and public key for decryption.
The global elements of ELgamal Digital Signature are prime number q and primitive root of q is alpha , User A generates a private key as follows:
1- Generate a random integer \({X}_{a}\) such that 1<\({X}_{a}\) <q-1.
2- Compute \({Y}_{a} = {a}^{{X}_{a}}\) mod(q).
A's private key is \({X}_{a}\) and public key is {q,a,\({Y}_{a}\)}.

To sign a message M, User A first compute the hash value m of the message m = H(M) such that m is an integer 0<= m <=q-1.
Then user A forms the digital signature as follows:
1- Choose a random integer k such that 1<= k <=q-1 and gcd (k,q-1)=1.
2- Compute \({S}_{1} = {a}^{k} mod(q)\)
3- Compute \({k}^{-1} mod(q-1)\)
4- Compute \({S}_{2} = {K}^{-1} * (m-{X}_{a}-{S}_{1}) mod(q-1)\)
5- The signature consists of (\({S}_{1},{S}_{2})\)

User B can verify the signature as follows:
1- Compute \({V}_{1} = {a}^{m} mod(q)\)
2- Compute \({V}_{2} = {Y}_{a}^{{S}_{1}} * {S}_{1}^{S2} mod(q)\)
If \({V}_{1}={V}_{2}\) then the signature is valid.

For Example:

In GF(19) q = 19 has primitive roots {2,3,10,13,14,15} and we choose a = 10
User A generates public/private key as follows:
1- \({X}_{a}\) = 16
2- \({Y}_{a} = {a}^{{X}_{a}} mod(q) = 4\)
Then User A private key = 16 and public key={19,10,4}
Suppose User A wants to sign a message with a hash value =14

1- choose k =5
2- \({S}_{1} = {a}^{k} mod(q) {10}^{5} mod(19) = 3\)
3- \({k}^{-1} mod(q-1) = {5}^{-1} mod(18) = 11\)
4- \({S}_{2} = {K}^{-1} * (m-{X}_{a}-{S}_{1}) mod(q-1) = 11(14-16-3)mod(18) = 4\)

User B can verify the signature as follows:
1- \({V}_{1} = {a}^{m} mod(q) = {10}^{14} mod(19) = 16\)
2- \({V}_{2} = {Y}_{a}^{{S}_{1}} * {S}_{1}^{{S}_{2}} mod(q) = {4}^{3} * {3}^{4} mod 19 = 16\)

\({V}_{1} = {V}_{2}\) Then the signature is valid.

Schnorr Digital Signature Scheme:

Schnorr scheme is also based on discrete logarithms and this scheme is based on using a prime number p with p-1 having a prime factor q.
To generate public/private key

1- Choose p and q such that q is a prime factor of p-1.
2- Choose integer b such that \({a}^{b}\) = 1 mod(q)
The values b,p,q comprise a global public key that can be common to a group of users
3- Choose random integer S 0< S <q , this is user's private key
4- Calculate \(V={b}^{-S} mod(p)\) , this is user's public key
User's public key is V and User's private key is S can generates a signature as follows:
1- Choose a random integer r 0< r <q and compute \(X = {b}^{r} mod(p)\)
2- Concatenate the message with X and hash the result to compute value e  e=H(M||X)
3- Compute \(Y= (r+{S}_{e}) mod(q)\) the signature consists of (e,Y)
Other users can verify the signature as follows:
1- Compute \(X` = {b}^{Y} * {V}^{e} mod(p)\)
2- Verify e = H(M||X`)
If H(M||X)= H(M||X`) Then the signature is valid.

The Digital Signature Algorithm (DSA):

DSA is also based on discrete logarithms and based on ELgamal and Schnorr schemes.
DSA consists of
Three public parameters that can be common to a group of users
1- 160 bit prime number q is chosen
2- prime number p with length from 512 to 1024 bits such that q divides (p-1)
3- g is chosen to be in the form of \({h}^{(p-1)/1}\) mod(p) where h is an integer between 1 and (p-1) and g > 1.

-With these three parameters each user can generate his public/private key.
-The private key X must be random number from 1 to (q-1)
-The public key can be calculated \(y = {g}^{X}\)

To create a signature, users calculate two parameters r and s that are function of the public key components (p,q,g) and user's private key (x) and the hash code of the message H(M) and a random integer k and unique for each signature

\(r= ({g}^{k} mod(p))mod(q)\)
\(s= [ {K}^{-1} * H(M) + X] mod(q)\)
The signature is (r,s)

At the receiving end verification can be done as follows
1- \(W= {s`}^{-1} mod(q)\)
2- \({U}_{1}= (H(M`)*W) mod(q)\)
3- \({U}_{3}= (r`*w) mod(q)\)
4- \(V= [({g}^{U1} * {Y}^{{U}_{2}} mod(p))] mod(q)\)

If V = r` then the signature is valid.

Note: It is computationally infeasible to recover k from r or recover X from S.



Cryptography 17

Secure Hashing Algorithm (SHA)

Secure Hashing Algorithm (SHA) is based on the hash function MD4 ,SHA was developed by National Institute of Standards and Technology (NIST) and published in 1993 known as SHA-0, and then published SHA-1 in 1995 that produces a hash value of 160 bits, Then SHA-2 with a hash value length of 256,384 and 512 bits known as SHA-256 SHA-384 and SHA-512 respectively.


SHA-512 takes as input a message with a maximum length less than \(2^{128}\) and produces 512 bits.
The block length is 1024 bits.
The processes consists of:

1- Append Padding Bits:

Padding is always added even if the message is already of the desire length, the padding consists of a single 1 bit followed by the necessary number of 0 bits, the message padded so that its length 896 mod 1024.
L + 1 + K = 896 (mod 1024)
L = Length of the original message
K = Number of zeros

2- Append Length:

A block of 128 bits is appended to the message and contains the length of the original message.


Suppose the original message = "01100001 01100010 01100011 01100100 01100101"
Then after padding it with a single 1 bit = "01100001 01100010 01100011 01100100 01100101 1"
Length of the original message L=40 , The number of zeros K= 855
Then the message after append padding step in Hex =

61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

Since L=40, Then we add 128 bits in the end of message "00000000 00000000 00000000 00000028"
The final padded message in Hex

61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000028

3- Initialize Hash Buffer:

A 512 bit buffer can be represented as eight 64 bit register (a,b,c,d,e,f,g,h)
These values were obtained by taking the first sixty bit of the fractional parts of the square roots of the first eight prime numbers, and these values are stored in big-Indian format.

a = 6a09e667f3bcc908
b = bb67ae8584caa73b
c = 3c6ef372fe94f82b
d = a54ff53a5f1d36f1
e = 510e527fade682d1
f = 9b05688c2b3e6c1f
g = 1f83d9abfb41bd6b
h = 5be0cd19137e2179

4- Process The Message In 1024 Bits:

SHA-512 consists of 80 rounds takes as input 512 bit value (a,b,c,d,e,f,g,h) and then update the contents of the buffer, and then take \({K}_{t}\) Where 0 <= t <= 79 and these words represent the first 64 bits of the fractional parts of the cube root of the first 80 prime numbers

   428a2f98d728ae22 7137449123ef65cd b5c0fbcfec4d3b2f e9b5dba58189dbbc
   3956c25bf348b538 59f111f1b605d019 923f82a4af194f9b ab1c5ed5da6d8118
   d807aa98a3030242 12835b0145706fbe 243185be4ee4b28c 550c7dc3d5ffb4e2
   72be5d74f27b896f 80deb1fe3b1696b1 9bdc06a725c71235 c19bf174cf692694
   e49b69c19ef14ad2 efbe4786384f25e3 0fc19dc68b8cd5b5 240ca1cc77ac9c65
   2de92c6f592b0275 4a7484aa6ea6e483 5cb0a9dcbd41fbd4 76f988da831153b5
   983e5152ee66dfab a831c66d2db43210 b00327c898fb213f bf597fc7beef0ee4
   c6e00bf33da88fc2 d5a79147930aa725 06ca6351e003826f 142929670a0e6e70
   27b70a8546d22ffc 2e1b21385c26c926 4d2c6dfc5ac42aed 53380d139d95b3df
   650a73548baf63de 766a0abb3c77b2a8 81c2c92e47edaee6 92722c851482353b
   a2bfe8a14cf10364 a81a664bbc423001 c24b8b70d0f89791 c76c51a30654be30
   d192e819d6ef5218 d69906245565a910 f40e35855771202a 106aa07032bbd1b8
   19a4c116b8d2d0c8 1e376c085141ab53 2748774cdf8eeb99 34b0bcb5e19b48a8
   391c0cb3c5c95a63 4ed8aa4ae3418acb 5b9cca4f7763e373 682e6ff3d6b2b8a3
   748f82ee5defb2fc 78a5636f43172f60 84c87814a1f0ab72 8cc702081a6439ec
   90befffa23631e28 a4506cebde82bde9 bef9a3f7b2c67915 c67178f2e372532b
   ca273eceea26619c d186b8c721c0c207 eada7dd6cde0eb1e f57d4f7fee6ed178
   06f067aa72176fba 0a637dc5a2c898a6 113f9804bef90dae 1b710b35131c471b
   28db77f523047d84 32caab7b40c72493 3c9ebe0a15c9bebc 431d67c49c100d4c
   4cc5d4becb3e42b6 597f299cfc657e2a 5fcb6fab3ad6faec 6c44198c4a475817

also each round makes use of 64 bit value derived from the current 1024 bit block being processing.

Each round defined by the following equations:

h = g
g = f
f = e
e = d+T1
d = c
c = b
b = a
a = T1+T2
Where t = step number 0<= t <= 79
 If e then f else g

\(ROTR^{n}\) (x): Circular right shift of the 64 bit argument x by n bits.
\({W}_{t}\)  a 64 bit word derived from the current 512 bit input block.
\({K}_{t}\): a 64 bit additive constant.

\({W}_{t}\) values are derived from 1024 bit message, the first 16 values of \({W}_{t}\) are taken directly from 16 words of the current block and the remaining derived from :

 \(ROTR^{n}\) (x) = Circular right shift of 64 bit argument x by n bits.
\(SHR^{n}\)  (x)  = Left shift of 64 bit argument  by n bits with padding by zeros on the right.
+ = Addition modulo  \(2^{64}\).
Finally, the output of 80th round is added to the input of the first round (a,b,c,d,e,f,g,h) and the addition is done independently for each of the eight words in buffer with each of the corresponding word(a,b,c,d,e,f,g,h) by using addition modulo \(2^{64}\).
Then the output is 512 bit message digest.



Cryptography 16

Hash Functions

What is hash function ?!
Hash function maps a variable length message into a fixed length hash value.

Cryptographic hash function is an algorithm for which no attack is more efficient than brute force to find

1- Get the message from the hash value.
2- Find two messages with the same hash value.

Building a simple hash function:

The simplest form of hash function is bit-by-bit XOR but it is not secure at all

h = B1  B2  B3 .....

But this form has a low effectiveness, we can improve this algorithm by perform one-bit circular shift
by the following steps:
1- Set the hash value to zero.
2- Rotate the hash value one bit to the left.
3- XOR the hash value with the data block.
This algorithm added more randomizing to hash value than bit-by-bit XOR.

Requirements for building a hash function:

For a hash function h= H(x)

h is the hash value , H is a hash function or many-to-one mapping algorithm
x is a data block (preimage)

A collision occurs if x != y and H(x) = H(y) , and it is not good when using a hash function in data integrity or in message authentication.

For any given hash value h, there will in general be multiple preimages and this is a measure of the number of potential collision for a given hash value.

Suppose the length of the hash code in n ,and the hash function takes a data block as input of length b such that b>n.
Then the total number of possible messages is \(2^{b}\) and the total number of possible hash values is \(2^{n}\) then the hash value will have close to \(2^{\frac{b}{n}}\) preimages and this is a security risk.

So the requirement for building a hash function

1- H can be applied to a block of data of any size.
2- H produces a fixed length of output h.
3- H(x) is relatively easy to compute for any given x.
4- Preimage Resistance (one-way property): For any given hash value h, it is computationally infeasible to find y such that H(y) = h .
5- Second Preimage Resistance (weak collision resistance) : For any given block x , it is computationally infeasible to find H(y) = H(x) x != y.
6- Collision Resistance (strong collision resistance): It is computationally infeasible to find any pair (x,y) such that H(x)=H(y) .
7- Pseudorandomness : The output of H function meets standard tests for pseudorandomness.

To build a strong hash function, the hash function must satisfies the first 6 requirements, and if the hash function satisfies the first 5 requirements , so this hash function is weak hash function.



Cryptography 15

Elliptic Curve

Elliptic curve is an equation with two variables and coefficients and it is a cubic equation like the following form:

Let's plot \(y^{2}=x^{3}+ax+b\) with set of points E(a,b) = E(1,1)

Addition Over Elliptic curve :

First we have element called O (zero point or point of infinity) and we have a rule in geometric tearm "If 3 points on an elliptic curve lie on a straight line, their sum is O."
We can drive some rules from this rule :
1- For any point P on elliptic curve P+O=P.
2- The negative of point P with the same X coordinate, so if P=(x,y) then -P=(x,-y).
3- To add two points P and Q,draw a straight line between them and the third intersection point with curve is -R, then these three points P+Q=-R and the positive value of P+Q is the mirror image of the third point.
If the line between P and Q is tangent to the curve then R=P or R=Q.
4- To double point P,draw the tangent line and find the intersection point S then 2P=-S.

Algebraic addition over Elliptic curve :

1- To add two points \(P({X}_{p},{Y}_{p}) \ Q({X}_{q},{Y}_{q})\), then the slope of the line that join them \(\Delta = \frac{{Y}_{q}-{Y}_{p}} {{X}_{q}-{Y}_{p}}\)
Then we can express R (which R= P+Q)

\({X}_{r} = \Delta ^{2} - {X}_{p}-{X}_{q}\)
\({Y}_{r} = -{Y}_{p}+\Delta({X}_{p}-{X}_{r})\)

2- To double point P P+P=2P = R
\({X}_{r} =(\frac{3{X}_{p}^{2}+a}{2{Y}_{p}})^{2}-2{X}_{p}\)
\({Y}_{p} =(\frac{3{x}_{p}^{2}+a} {2{Y}_{p}})({X}_{p}-{X}{r})-{Y}_{p}\)

Elliptic Curve over finite field :

Elliptic Curve over finite field is using elliptic curve in which variables and coefficients are all restricted to elements of finite field.

Prime Curve over Zp :

Prime Curve is using a cubic equation in which the variables and coefficients take value from 0 to P-1.
Equation of elliptic curve over Zp :
\(y^{2} mod(p)=(x^{3}+ax+b) mod(p)\)

The rules for addition over \({E}_{p}(a,b)\):

1- If \(P({X}_{p},{Y}_{p}) \ then \ -P({X}_{p},{-Y}_{p})\).
2- To add two points \(P({X}_{p},{Y}_{p}) \ and \ Q ({X}_{q},{Y}_{q}) \ R= P+Q\)
Then R =

\(\lambda = \begin{cases}(\frac{{}{Y}_{q}-{Y}_{p}}{{X}_{q}-{X}_{p}})mod(p)) & if\ p\neq q \\ \\
(\frac{3{X}_{p}^{2}+a}{2{Y}_{p}})mod(p) & \text if \ p=q (double\ point\ p) \end{cases}\)

For example :

Let P=(3,10) Q=(9,7) in \({E}_{23}(1,1)\)
\(\lambda=\frac{7-10}{9-3}mod(23)\ =\frac{-1}{2}mod(23)=11\)
Then P+Q = (17,20)

To double point P 2P

For example :

Let P =(3,10)
Then 2P = (7,12)

Elliptic curve over \(GF(2^{m})\) : 

\(GF(2^{m})\) consists of \(2^{m}\) elements with addition and multiplication can be defined over polynomials, which variables and coefficients are elements of \(GF(2^{m})\).
The cubic equation for cryptographic applications for elliptic curve can take the following form :

\(y^{2}+xy= x^{3}+ax^{2}+b\)
For Example :

For g = 0010
\(y^{2}+xy=x^{3}+g^{4}x^{2}+1 \ \ \ where \ a=g^{4} ,b=g^{0}\)
\(a= g^{4}, b = 1\)  and points that satisfies this equation \((g^{5},g^{3})\)
1100+0101 = 0001+1001+0001
1001 = 1001

The rules of addition over \(GF(2^{m})\) :

1- If \(P({X}_{p},{Y}_{p}) and Q({X}_{q},{Y}_{q}) R = P+Q\)

2- If \(P({X}_{p},{Y}_{p}) R = 2P\)

Key exchange using elliptic curve:

First choose a large integer q OR a prime number P or integer of form \(2^{m}\)
Then choose base point \(G =({x}_{1},{x}_{2})\) in Ep(a,b) whose order is a very large value n, The order n of point G is the smallest positive integer n such that nG=0.
The Key exchange can be done by the following:
1- User A select an integer \({n}_{A}\) less than n , This is A's private key, then compute public key \({P}_{a}={n}_{A} * G\)
2- User B select \({n}_{B}\) and compute the public key \({P}_{b}\)
3- User A compute the secret key \(K={n}_{A} * {P}_{b}\)
4- User B compute the secret key \(K={n}_{B} * {P}_{a}\)
Note : The secret key is a pair of numbers.

For Example:
P=211 in Ep(0,-4)
The equation \(y^{2} = x^{3} - 4\)
G = (2,2)
A's private key \({n}_{A}=121\)
B's private key \({n}_{B}=203\)
A's public key \({P}_{a}={n}_{A} * G = 121(2,2) = (115,48)\)
B's public key \({P}_{b}={n}_{B} * G = 203(2,2) = (130,203)\)
A's secret key \(K={n}_{A} * {P}_{b} = 121(130,203) = (161,69)\)
B's secret key \(K={n}_{B} * {P}_{a} = 203(115,48)  = (161,69)\)
Then the shared key k = (161,69)

Elliptic Curve encryption algorithm :

First we have to encode the message to be sent as x and y coordinates, and it is not easy because not all points are in \({E}_{p}(a,b)\).
As with the key exchange
- Choose a point G
- User A select a private key \({n}_{A}\)
- User A calculate the public key \({P}_{a}={n}_{A} * G\)
To send a message Pm to User B, User A choose a random integer K and then produce the ciphertext Cm by the following:
\({C}_{m} = (KG.{P}_{m} + K{P}_{b})\)
Note : User A masked the message Pm by adding (K.Pb) and nobody but user A knows k value.

For Example :
P=751 in \({E}_{p}(-1,188)\)
The equation \(y^{2} = x^{3} -x + 188\)
G=(0,376) Pm = (562,201)
User A choose k=386
\({P}_{b} = (201,5)\)
Then K.G = 386(0,376) = (676,558)
\({P}_{m} + K,{P}_{b}\)
(562,201) + 386(201,5) = (385,328)
Then the ciphertext Cm
Cm = {(676,558),(385,328)}



Cryptography 14

Elgamal Cryptographic System

Elgamal cryptographic system is a public-key algorithm based on discrete logarithm.
Elgamal cryptographic system is used in digital signature standard (DSS).

Elgamal Cryptographic algorithm:

There are prime number q and primitive root of q = a.
User A want to generate private and public keys as the following:

1- Generate a random integer \({X}_{a}\) such that 1 < \({X}_{a}\) < q-1.
2- Compute \({Y}_{a}=a^{{X}_{a}} mod(q)\).
\({X}_{a}\) is A's private key and (q,a,\({Y}_{a}\)) is A's public key.

If user B Has A's public key then he can send him encrypted message as the following:
1- Represent the message as an integer M such that 0 <= M <= q-1, and longer messages are send as a sequence of blocks, each block has integer value less than q.
2- Choose a random number k such that 1 <= k <= q-1.
3- Calculate one-time key \(K = ({Y}_{a})^{k} mod(q)\).
4- Encrypt the message M as a pair of integer(C1,C2)
   \({C}_{1} = a^{k} mod(q) \\\  {C}_{2} = KM mod(q)\).

User A can decrypt the message :

1- Recover the key by calculating \(K ={C}_{1}^{{X}_{a}} mod(q)\).
2- Calculate \(M = {C}_{2}*k^{-1} mod(q)\).

How user A can recover the K value to decrypt the message M?

K value is defined during the encryption process
\(K = {Y}_{a}^{k} mod(q)\)  ----> we can substitute \({Y}_{a}=a^{{X}_{a}} mod(q)\)
Then \(K = (a^{{X}_{a}} mod(q))^{k} mod(q)\)
Then \(K = a^{(k{X}_{a})} mod(q)\) ---> we substitute \(a^{k} mod(q) = {C}_{1}  ( {C}_{1} = a^{k} mod(q))\)
Then \(K = {C}_{1}^{{X}_{a}} mod(q)\).

Example :

In Elgamal public key scheme suppose prime number q = 19
and primitive root of 19 we choose a=10
User A generate private and public keys as the following :
1- User A choose \({X}_{a} = 5\).
2- \({Y}_{a} = a^{{X}_{a}} mod(q) = 10^{5} mod(19) = 13\)

User A's public key = (19,10,3) and A's private key=5

User B want to send encrypted message M to user A with M value = 17

1- User B choose k=6.
2- \(K = {Y}_{a}^{k} mod(q) = 3^{6} mod(19) = 7\).
Then \({C}_{1} = a^{k} mod(q) = 10^{6} mod(19) = 11\)
\({C}_{2} = KM\ mod(q) = 7*17 mod(19) = 5\)

Then user B send\({C}_{1} = 11 \ and \ {C}_{2} = 5\) to user A.
Then user A decrypt the message
1- User A calculate \(K = {C}_{1}^{{X}_{a}} mod(q) = 11^{5} mod(19) = 7\)
2- The \(K^{-1}\ in \ GF(19) = K^{-1} mod(19) = 7^{-1} mod(19) = 11\)
3- \(M = ({C}_{2}K^{-1})mod(q) = (5*11) mod(19) = 17\) #.



Cryptography 13

Diffie-Hellman Key Exchange

Diffie-Hellman is a key exchange algorithm based on public key cryptography written by Diffie and Hellman

Diffie-Hellman Algorithm :

First we have to know the concept "Primitive root of a prime number" ,A primitive root x of a prime number p means : \(x \ mod(p), x^{2} mod(p), x^{3} mod(p),..., x^{p-1}mod(p)\) --- generates numbers from 1 to p-1.

In Diffie-Hellman algorithm there are two numbers
A- Prime number q.
B- Primitive root of q = a.

We have here a scenario to understand Diffie-Hellman algorithm

Two users A,B want to exchange keys by the following steps:
1- User A select a random number \({X}_{a} < q\).
2- User A compute \({Y}_{a} = a^{{X}_{a}}mod(q)\).
3- User B Select a random number \({X}_{b} < q\).
4- User B compute \({Y}_{b} = a^{{X}_{b}}mod(q)\).

Note:The X values are private and Y values are are public.
5- User A compute the key \(K={Y}_{b})^{{X}_{a}}mod(q)\).
6- User B compute the key \(K={Y}_{a}^{{X}_{b}}mod(q)\).
7- A and B produce the same K value , if true , then the 2 sides have exchanged the secret keys.


Diffie-Hellman key exchange use the following:

Prime number q=353
Primitive root of q=353 , then a=3
A's secret key \({X}_{a}=97\)
B's secret key \({X}_{b}=233\)
Then calculate public values(Y)
\({Y}_{a} = a^{{X}_{a}}mod(q) = 3^{97} mod(353) = 40\)
\({Y}_{b} = a^{{X}_{b}}mod(q) = 3^{233} mod(353) = 248\)
A calculate \(K={Y}_{b})^{{X}_{a}}mod(q) = 248^{97} mod(353) = 160\)
B calculate \(K={Y}_{a}^{{X}_{b}}mod(q) = 40^{233} mod(353) = 160\)
K values are the same , then A and B

Note: Diffie-Hellman is not protected against Man-In-The-Middle attack , look at the following scenario:

User A and B want to exchange keys , if an attacker V want to get in middle
1- Attacker V generate 2 private keys \({X}_{v1}\) and \({X}_{v2}\).
2- Attacker V compute \({Y}_{v1}\) and \({Y}_{v1}\).
3- User A send Ya to user B.
4- Attacker V intercept \({Y}_{a}\) and send \({Y}_{v1}\) to user B , then attacker V calculate \({K}_{2}={Y}_{a})^{{X}_{v2}}mod(q)\).
5- User B receives \({Y}_{v1}\) and calculate \({K}_{1}={Y}_{v1}^{{X}_{b}} mod(q)\).
6- User B send \({Y}_{b}\) to user A.
7- Attacker V intercept \({Y}_{b}\) and send \({Y}_{v2}\) to user A , then attacker V calculate \({K}_{1}={Y}_{b}^{{X}_{v1}}mod(q)\).
8- User A receive \({Y}_{v2}\) and calculate \({K}_{2}={Y}_{v2}^{{X}_{a}} mod(q)\).

User A and B not sharing a secret key, but User A and attacker V share a secret key \({K}_{2}\) and user B and attacker V share a secret key \({K}_{1}\)
so when user A send encrypted message to user B , attacker V intercept and decrypt this message by using \({K}_{2}\) and then encrypt it by using \({K}_{1}\) and send it to user B.