What is the background story of calculating the value of d in the RSA algorithm of Cryptography and Network Security?
The value of d is required for decryption. I want to know the derivation of finding d. The equation of finding d is d = e-1mod Φ(n).
Consider an example: P = 17, q = 7, n = 119, φ (n) = 96, e = 5. From here I want to find the value of d in my hand. How can I do this?
search about....
1-eGCD Algorithm
2-Mltiplicative Inverse
3-Relative Prime
The notation a≡b(modr)a≡b(modr) is defined to mean that rr divides the difference a−ba−b. Therefore, the equation d⋅e≡1(modϕ(n))d⋅e≡1(modϕ(n)) is interpreted to mean that ϕ(n)ϕ(n) divides the difference d⋅e−1d⋅e−1. This means that the difference, being a multiple of ϕ(n)ϕ(n), is of the form k⋅ϕ(n)k⋅ϕ(n) for some integer kk. (This is where the kk comes in.) Rearranging d⋅e−1=k⋅ϕ(n)d⋅e−1=k⋅ϕ(n) yields d⋅e=1+kϕ(n)d⋅e=1+kϕ(n), as desired.
You should think of 1(modϕ(n))1(modϕ(n)) as an equivalence class of all numbers of the form {1+kϕ(n)}{1+kϕ(n)}. You don't really want to use your intuition about 'size' when thinking about modular arithmetic, which I view conceptually as due to the fact that you're using a number wheel (such as a clock, for mod 1212), as opposed to a number line.
From the idea of the RSA algorithm, d = e-1mod Φ(n)
=> de = 1 mod Φ(n). What does it mean? It means “de mod Φ(n) = 1”(Basic theorem of inverse modular arithmetic).
So, we can write: Φ(n)) de ( X
---------------------
1
Now from the basic mathematical formula, we know that,
Dividend = Divisor x Quotient + Remainder.
That means, Φ(n) * X + 1 = de;
=> d = {Φ(n) * X + 1} / e;
d must be an integer number.
From here you have the set any value of x (Integer Value), so that d will be an integer value.
Example:
If, Φ(n) = 96, e = 5, then d = 77.
Φ(n) = 60, e = 7, then d = 43.
I hope the description will be helpful for all.
The idea! The idea of RSA is based on the fact that it is difficult to factorize a large integer. The public key consists of two numbers where one number is multiplication of two large prime numbers. And private key is also derived from the same two prime numbers. So if somebody can factorize the large number, the private key is compromised. Therefore encryption strength totally lies on the key size and if we double or triple the key size, the strength of encryption increases exponentially. RSA keys can be typically 1024 or 2048 bits long, but experts believe that 1024 bit keys could be broken in the near future. But till now it seems to be an infeasible task.
- Badges
- Science topic