8 votes

Why is 65537 always coprime to φ(N) in RSA?

$65537$ is not always coprime to $\varphi(N)$ in RSA1. But it often is, because: It often2 is chosen $e=F_4=2^{(2^4)}+1=65537$ in RSA, and then the requirement3 that $e$ is coprime to $\varphi(N)$ ...
fgrieu's user avatar
  • 141k
3 votes

Why is 65537 always coprime to φ(N) in RSA?

There is no known weakness for any public exponent for RSA, as long as the public exponent $e$ is relatively prime to $\varphi(n)$ and the proper padding scheme is used. Fermat's primes are preferable ...
NB_1907's user avatar
  • 640
3 votes

Confused about use of Euler totient function in RSA

why $x^{ed} \mod n =x$ implies that $ed\mod \phi(n)=1$? Answer: it doesn't. On the other hand, if $\forall x: x^{ed} = x \pmod n$, that does imply that $ed \bmod \text{lcm}(p-1, q-1) = 1$. If $ed \...
poncho's user avatar
  • 147k
1 vote

What is the best possible security for authentication of entity?

No, asymmetric algorithms generally are build upon mathematical problems. These problems are considered mathematically hard, but it is not clear if P = NP. If that's the case then any of these hard ...
Maarten Bodewes's user avatar
  • 92.6k
1 vote

Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?

Yes both QS and NFS (Number Field Sieve) imply that factorization is subexponential. But the exact relationship between SUBEXP and NP is unknown. See the answer to the question here. And as pointed ...
kodlu's user avatar
  • 22.5k
1 vote

Why is 65537 always coprime to φ(N) in RSA?

The choice of 65537 is popular because it is a prime number $2^{16}+1$. There might be more reasons, but ones that come to mind are: It's prime, but not a large number so it's easy on the division ...
b degnan's user avatar
  • 4,820
1 vote

Creating multiple "public" keys from one private key

It sounds like you are talking about key derivation, for example Hmac-based key derivation (HKDF). You can derive a private key from a known (private) seed or from another private key, creating a ...
Rohinton Collins's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible