What is cryptography?
What is a one-way function?
A one-way function is a mathematical function in which conversion from input to output is very easy but for a given output, identification of input is quite impossible unless you know the trap door.
The trap door can be open only with the help of secret key and this secret key is shared by sender and
receiver.
An example, a function that simply multiplies two primes to produce output is an example of a one-way function.
Given p and q, it is very easy to calculate product, but if we know product it is very difficult to identify the correct prime numbers(factorization problem is NP-hard) unless we know one prime(trap door).
Why we use a one-way function?
We use a one-way function to make cryptanalysis very difficult.Earlier we have discussed that hackers can sense channel and can capture some output values but due to the use of a one-way function it is quite impossible to identify the input.A cryptosystem is a system that implements this secure communication.This cryptosystem is designed with the help of mathematical functions and programming.
Is a cryptosystem breakable?
Every cryptosystem can be broken by using brute force analysis but the following two properties make a cryptosystem secure. If the cost of a braking system is greater than the cost of information.
Or
If the time taken to break the system is greater than the validity of information.
What is the encryption algorithm?
An algorithm that is used to provide confidentiality is called encryption algorithm. It does two thins. It converts encryption Intelligent message or plaintext unintelligent message(ciphertext)
decryption
There are two types of encryption algorithms
1.Symmetric key-based algorithms: The same key is used for encryption and decryption
2.Public key based algorithm: one key is used for encryption and other for decryption
Example of symmetric key and asymmetric key-based algorithm
Symmetric key Based algorithms: DES(Data Encryption Standard), AES(Advanced Encryption Standard) are two important symmetric key-based algorithms. Symmetric key-based algorithms convert binary data and use substitution and permutation techniques for transformation. They are less expensive.
Asymmetric/public key-based algorithm: RSA(Revist Samir Aldemal), Elgamal, ECC(Elliptical Curve Cryptography) public is a key-based algorithm. Their logic is designed by implementing the
properties of prime numbers. It is expensive.
Public key based algorithm:
Use properties related to prime numbers for designing an algorithm. These properties are related to the modulo multiplicative group over the prime number. A modulo multiplicative group over prime p forms a group over modulo multiplication over a set having (p-1)values from (1 to p-1).
A mathematical system is known as a group if it satisfies four properties closure, associative, identity, and inverse. It is called abelian if it also satisfies commutative law.
For example, a modulo multiplicative group over prime 5 contains (1,2,3,4)
Example
Show (1,2,3,4) is a group over modulo multiplication 5(*5).
*5 1 2 3 4
1 1 2 3 4 (multiply 1 with all other values)
2 2 4 1 3 (multiply 2 with all other values and take remainder if the value is greater than 5)
3 3 1 4 2 (multiply 3 with all other values and take remainder if the value is greater than 5)
4 4 3 2 1 (multiply 4 with all other values and take remainder if the value is greater than 5)
See for the second number when 4 is multiplied by 2 it gives 8 and when we take modulo 5 it gives 3.
Show (1,2,3,4) is a group over modulo multiplication 5(*5).
Why this is a group over modulo multiplication.
It satisfies closure property as all numbers generate numbers from the group when operated. The matrix is symmetric hence operation will be commutative. (property fo abelian group) Modulo multiplication satisfies the associative property. Identity is modulo multiplication over prime is 1(in most of the cases). Inverse exist for each number.for each value, check which multiplication is producing identity that other number will be inverse.
For 1 it is 1, for 2 it is 3, for 3 it is 2 and for 4 it is 4.
Some properties of a modulo multiplicative group over prime p.There is one very important theorem that is related to this group. The name of the theorem is Fermat. Fermat theorem says that any number a from modulo multiplicative group over p satisfy this property.
(a)(p-1)mod p= 1(mod p)
Example of Fermat theorem:
Calculate (7)13 mod 11.
See by fermat theorem (7)10mod 11=1
(7)10+3 mod 11= ((7)10mod 11)*((7)3mod 11)=1*(49mod11*7mod11)=(5*7)mod11=2
Similarly we can use fermat theorem for calculating other values
(3)201mod 11=(3)20*10+1mod 11= ((3)10mod 11)20 * (3 mod 11)=(1)20 *3 mod 11=3
Calculate (13)10mod 11=(13 mod 11)10mod 11=(2)10mod 11=1
Euler theorem:
The generalized version of the Fermat theorem is known as the Euler theorem.
It is related to modulo multiplication operation over a composite number n.
Euler theorem says that any number a from modulo multiplicative group over p
satisfy this property.
(a)Φ(n) mod n= 1(mod n) this rule is applicable only if
a and p should be relatively prime to each other .Φ(n) is the totient function.
How can we calculate the value of the totient function:
The calculation of totient function Φ(n) is very easy.to calculate totient value write n as product
of prime numbers and use this formula.
If for example n= (p1)n1 (p2)n2 (p3)n3 (p4)n4........... (pi)ni
Then Φ(n) = (p1-1)(p1)(n1-1)(p2-1) (p2)(n2-1)(p3-1) (p3)(n3 -1)(p4-1)(p4)n4-1.......(pi-1)(pi)ni
Example Euler Theorem
Calculate
(7)12 mod 10= see only Euler can be applied as 10 is a composite number. See Euler can be applied as 7 and 10 are relative prime they have no common factor. What will be totient(10) so 10 can be written as 2(1)* 5(1) so
Totient (10) will be = (2-1)*2(0) *(5-1) *5(0)=4 so according to euler theorem (7)4 mod 10=1
So (7)12 mod 10 will be ((7)4 mod 10)3 mod 10 =1
More example:
Calculate (7)122mod 100= see the only Euler can be applied as 100 is a composite number.
See Euler can be applied as 7 and 100 are relative prime they have no common factor.
What will be totient(100) so 100 can be written as 2(2)* 5(2) so
Totient (100) will be = (2-1)*2(1)*(5-1) *5(1)=40 so according to Euler theorem (7)40mod 100=1
So (7)122 mod 10 will be (((7)40mod 100)3 mod 100 * (7)2mod100=49 mod 100)mod100 =49 mod
