Public Key Cryptography and RSA
1. Public Key Cryptography :
Public key cryptography is also known as Asymmetric cryptography which uses the concept of two keys i.e. Public key and Private key. Generation of such key pairs depends on the cryptographic algorithm which are based on Mathematical problem termed as one-way function.
2. Principles of Public Key Cryptography :
key distribution under symmetric encryption requires either
A. That two communicants already share a key, which somehow has been distributed to them or
B. The use of Key distribution center.
3. Public Key Cryptosystem :
Asymmetric algorithm relay on one key for encryption and a different but related key for decryption. These algorithm have the following important characteristic.
A. It is computationally infeasible to determine the decryption key given only knowledge of the cryptographic algorithm and the encryption key.
B. In addition, some algorithm, such as RSA, also exhibit the following characteristic-
B.1. Either of the two related keys can be used for encryption, with the other used for decryption.
B.2. A public key encryption scheme has six ingredients i.e. Plaintext, Encryption Algorithm, Public Key, Private key, Ciphertext, and Decryption Algorithm (as shown in Fig. 1).
Fig. 1: Public Key Cryptography
'A' prepares a message to 'B' and encrypt it using 'A's private key before transmitting it. 'B' can decrypt the message using 'A's public key (because the message was encrypted using A's private key) only A could have prepared the message. Therefore, the entire process is called digital signature.
5. Public Key Cryptosystem : Secrecy :
It provides confidentially.
Since A produces a message in Plaintext, X = [X1,X2,X3,....,Xm]. The M elements of X are letters in some finite alphabets.
PUb ---> Public key
PRb ---> Private key, it is known only to B.
So Encryption Y = [Y1,Y2,Y3,.....,Yn] :
Y = E(PUb,X)
and Decryption:
X = D(PRb,Y)
Fig. 2: Public-Key Cryptosystem: Secrecy
6. Public Key Cryptosystem : Authentication :
It don't provide Confidentiality because any observer which having the sender public key can easily read the message.
For Encryption :
Y = E(PRa, X)
For Decryption :
X = D(PUa, Y)
Fig. 3: Public-Key Cryptosystem: Authentication
7. Public Key Cryptosystem : Authentication and Secrecy :
Authentication function and confidentiality can be provided by using a double use of Public key scheme (as shown in Fig. 4).
Fig. 4: Public-Key Cryptosystem: Authentication and Secrecy
Above Scheme validating both author and contents, requires a great deal of storage.
Z = E(PUb,E(PRa,X))
X = D(PUa, D(PRb,Z))
NOTE1: This technique provides confidentiality but this approach is complex means exercised four times rather than two in each communication.
8. Application For Public Key Cryptosystem :
1. Encryption/Decryption
2. Digital Signature
3. Key Exchange
8.1 Requirements For Public-Key Cryptosystem :
Now we can till conclude that -
1. It is computationally easy for Party B to generate a pair (PUb, PRb)
2. It is easy for a sender A, knowing the public key and the messagr to be encrypted, M, to generate the corresponding ciphertext.
3. It is computationally easy for receiver B to decrypt the resulting ciphertext using the private key to recover the original message:
M = D(PRb,C) = D(PRb, E(PUb,M))
4. It is computationally infeasible for an adversary, knowing the public key, PUb, to determine the private key, PRb.
5. It is computationally infeasible for an adversary, knowing the public key, PUb and a Ciphertext C to recover the original message, M.
6. The two key can be applied in either order (non necessary condition)
M = D[PUb, E(PRb,M)] = D[PRb, E(PUb, M)]
Now these are formidable requirements, as evidence by the fact that only a few algorithm (RSA, Elliptic curve Cryptography, Diffie-Hellman, DSS) has received widespread acceptance in the several decades since the concept of public key cryptography was proposed.
Now before elaborating on why the requirements are so forbidden, let us first recast them.
Now let us understand one way function. A one way function is one that maps a domain into a range such that every function value has a unique inverse, with the condition that the calculation of the function is easy, whereas the calculation of inverse is infeasible.
Y = F(x), easy
X = inverse(Y), infeasible
This trap door one way function is easy to calculate in one direction but infeasible to calculate in other direction unless certain additional information is known.
A trap door one way function is a family of invertible function Fk such that
9. The (Rivest Shamir Adleman) RSA Algorithm :
The first successful responses to the challenge was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978.
The RSA scheme is a Block cipher in which the plaintext and ciphertext are integers between 0 and n-1 for some n. A typical size for n is 1024 bits, or 309 decimal digits. That is, n is less than 2^(1024).
In RSA Algorithm suppose 'M' and 'C' be the plaintext and ciphertext block.
C = M^(e) mod n -------(1)
M = C^(d) mode n -------(2)
Now equation 2 can be written as-
M = ((M^(e) mod n)^(d)) mod n -------(??)
NOTE 2: Both sender and receiver must know the value o n. The sender knows the value of e, and only the receiver knows the value of d. Thus, this is a public key encryption algorithm with a public key of PU = {e,n} and a private key of PR = {d,n}.
Proof :
When A and n are coprime positive integers, phi(n) is Euler's totient function, and 'x' is a private positive integer then:
A^(phi(n).x) mod n = 1 ------(3)
Since as we compute above,
M = ((M^(e) mod n)^(d)) mod n -----(4)
Now according to exponential Arithmetic Law.(When A, K and n are positive integers, and A<n, then:
A^(K) mode n = (A mod n)^(K) mod n
and,
A mod n = A)
So equation (4) can be rewrite as -
M^(ed) mod n =M ------(5)
Now we know that ed=1 mod phi(n) or ed = phi(n).x + 1
So equation (5) can be written as-
-- M^(phi(n).x+1) mod n
-- M^(phi(n).x).M mod n
or,
M.M^(phi(n).x) mod n -----(6)
using equation (3)
-- M
NOTE 3 : The above relation M^(ed) mod n =M only holds if e and d are multiplicative inverse modulo phi(n). Where phi(n) be the Euler totient function.
ed mod phi(n) = 1
Since gcd(e,phi(n)) = 1, 1<e<phi(n)
So => there exists d such that
ed = 1+k.phi(n)
or ed mod phi(n) =1
9.1 Procedure :
1. chose two prime numbers say P and Q.
2. Calculate the value of n and Phi.
n = PxQ and Phi = (P-1)(Q-1)
3. Find the value of e.
(chose e such that e should be coprime to phi(n), means gcd(e,phi(n))=1)
4. Compute value of d (private Key)
ed = 1+k.phi(n) (with hit-trial method)
5. Do Encryption, and Decryption
C = M^(e) mod n again C and M are given ciphertext and plaintext message.
M = C^(d) mod n
9.2 Computational Aspects :
We know turn to the issue of the complexity of the computation required to use RSA. There are actually two issues to consider : encryption and decryption and key generation.
Both encryption and decryption in RSA involve raising an integer to the power integer mod n. The intermediate value may be gargantum.
so we know
[(a mod n) x (b mod n)] mod n = (a x b) mod n
above law somehow try to minimize the computation and suppose we have to compute x^(11) mod n then,
== (x.x^(2).x^(8)) mod n
== ((x mod n) . (x^(2) mod n) . (x^(8) mod n)) mod n
More generally, suppose we wish to find the value a^(b) mod n with a, b and m positive integers. If we express b as a binary number then,
Efficient operation using the public key to speed up RSA algorithm using the public key, a specific choice of e is usually made. The most common choice is 65537 (2^(16) +1) and two other popular choices are 3 and 17.
For small public key values such as e=3, RSA become vulnerable to a small attack.
Suppose we have three different RSA users who all use the value e=3 but have unique values of n, namely (n1,n2,n3). if user send the same encrypted message M to all three user then,
C1 = M^(3) mod n1
C2 = M^(3) mod n2
C3 = M^(3) mod n3
n1, n2, n3 are pairwise relatively prime.
Therefore, Chinese Remainder theorem to compute M^(3) mod (n1,n2, n3).
By the rule of RSA Algorithm , M<ni
Therefore, M^(3) < n1n2n3
So attacker only have to compute M^(3). ----(easy to break)
So we know that According to RSA
gcd(e,phi(n)) = 1
So if we first chose e and then two prime numbers P and Q then may be possible gcd(e,phi(n)) != 1
9.4 Efficient operation using the Private Key :
We can not similarly chose a small constant value of d for efficient operation. A small value of d is vulnerable to a brute force attack and to other form of cryptanalysis.
Since M = C^(d) mod n
Let us define the following intermediate results
Vp = C^(d) mod P, Vq = C^(d) mod Q
Following the CRT defines the quantities
Xp = Q x (inverse(Q) mod P), Xq = P x (inverse(P) mod Q)
The CRT then shows that
M = (VpXp + VqQ) mod n
Furthermore, we can simplify the calculation of Vp and Vq using Fermat's theorem which states that a^(P-1) congruent to 1 mod P. If P and a are relatively prime.
Some thought should convince you that the following are valid.
Vp = C^(d) mod P = C^(d mod (P-1)) mod P = C^(d mod (Q-1)) mod Q.
The quantities d mod (P-1) and d mod (Q-1) can be pre-calculated. The end result is that the calculation is approximately four times as fast as evaluating M = C^(d) mod n directly.
Comments
Post a Comment