Name	: Amit Jaiswal
Roll No. 	: 03329011
Assignment : Network Security, Assignment 1, part 1
email : amitj@it.iitb.ac.in




In the original problem definition
m = message
e = 3
c(1), c(2), c(3) are the three encrypted messages
n(1), n(2), n(3) are the three nos. used in encryption which are relatively coprime with
each other.


m^3 is-congruent-to c(1) module n(1)
m^3 is-congruent-to c(2) module n(2)
m^3 is-congruent-to c(3) module n(3)



Lets take m^3=x and use the Chinese Remainder theorem to find the value of x


The Chinese Remainder Theorem states that
let n(1), n(2), ..., n(k) be relatively prime positive integers and let c(1), c(2),...c(k)
be any integers. Then the system of linear equations of linear congruence given in one variable
given by
		x congruent-to c1 mod n(1)
		x congruent-to c2 mod n2(1)
		.
		.
		.
		x congruent-to c(k) mod n(k)

has a unique solution modulo n(1)n(2)...n(k)

To find the original message we take
N = n(1) * n(2) * n(3)
Let N(i) = N / n(i)
so
 N(1) = N/n(1)
 N(2) = N/n(2)
 N(3) = N/n(3)

 Since, the nos. are relatively prime so gcd(N(i), n(i))=1 for i=1, 2, 3

 Thus
 	N(i)*x(i) congruent-to 1 mod n(i) , for all i=1,2,3
	has a unique solution x(i).
	Here x(i) is the modulo inverse of N(i) modulo n(i)
	which can be found using Euclid Algorithm


Let
	x = c(1)*N(1)*x(1) + c(2)*N(2)*x(2) + c(3)*N(3)*x(3)

Since
	n(i) | M(j) for all j not equal to i
therefore
	x = c(1)*N(1)*x(1) + c(2)*N(2)*x(2) + c(3)*N(3)*x(3)
	and its given that
	x is-congruent-to c(i) modulo n(i) for	all i = 1, 2, 3


	so x can be found using the above equation.
Here x = m^e
where m=message
and e = 3
so its
	m*m*m = c(1)*N(1)*x(1) + c(2)*N(2)*x(2) + c(3)*N(3)*x(3)
	so m can be found using module arithmetic (with the help of modulo inverse concepts)
	




