Menu
Apparently an alternative method (to just using the extended Euclidean algorithm) of obtaining the exponent for deciphering is to do d = e**(phi(phi(n))-1) mod(phi(n)). Why does this work?
904
Euler's phi (or totient) function of a positive integer n is the number of integers in {1,2,3,...,n} which are relatively prime to n. This is usually denoted φ(n). Clearly for primes p, φ(p)=p-1.
In number theory, Euler's totient function, also called Euler's phi function, denoted as φ(n) , counts the positive integers up to a given integer n that are relatively prime to n .
Another possible way to break RSA is to find the value p+q . Finding p+q allows us to find p and q if we combine it with the following equation for p−q : (1)p−q=√(p+q)2−4n. p - q = ( p + q ) 2 - 4
I've got a question concerning fields used in RSA. I learnt that an inverse element exists if a is coprime to m. Applied to RSA I would have guessed that e needs to be coprime to n in order to find it's inverse element, because n is used as mod. But according to the rules of RSA it has to be coprime to ϕ (n) (gcd (ϕ (n),e)=1).
Let's start: Those two solutions are the values of the secret primes P and Q. In other words, knowing both N and ϕ ( N) an attacker can trivially recover P and Q and therefore recreate the RSA public and private keys. That is why it's important to keep P, Q and ϕ ( N) secret and never reveal them.
Why is it important that phi (n) is kept a secret, in RSA? Why is it important that ϕ ( n) is kept a secret, in RSA? From the definition of the totient function, we have the relation: Which can be readily solved using the well-known quadratic formula: Because of symmetry, the two solutions for p will in fact be the two prime factors of n.
Given ϕ ( n) and n it's easy to factor n by solving the equations n = p ⋅ q and ϕ ( n) = ( p − 1) ⋅ ( q − 1) for p and q. Remember that with RSA the number N is the product of two large secret primes. Let's call them P and Q. We will treat them as our unknowns: Now N is known, as part of the public key.
The general requirement for the RSA operation to function properly is that e*d = 1 mod X, where X is typically (p-1)*(q-1).
In this case, X is phi(n), e is e, and d is e^[phi(phi(n))-1] = e^[phi(X)-1].
Notice that e*d mod X is e*e^[phi(X)-1] mod X = e^phi(X) mod X.
Euler's Theorem states that a^phi(X) = 1 mod X, for any a which is relatively prime to X, thus the requirement holds.
137
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
