Hot answers tagged

12 votes
Accepted

Validating an RSA public key

Given a pair of integers $(n,e)$, we can quickly decide that it is not a valid RSA key (mathematically, or in the sense of conforming to the de-facto standard PKCS#1, or in the sense of providing ...
  • 126k
5 votes

Validating an RSA public key

Well, for $e$, you can certainly test if $e$ is an odd number greater than 1; any such $e$ is a possible public exponent, and and it is infeasible to determine if $\gcd( e, \phi(n)) > 1$, and so ...
  • 134k
5 votes

Why RSA uses {d,n} as private key instead of {e,n}?

Note: This answer was written for the question "In RSA, are $e$ and $d$ technically equivalent?", that was migrated from security-SE, then merged here. The relevant parts of that other ...
  • 126k
4 votes
Accepted

Solving system of equation based on RSA

Since this is a past CTF we can provide a guide to solve it. Euler's theorem states that if $\gcd(m,n) =1$ with $m,n \in \mathbb{Z}^+$ then $$m^{\varphi (n)} \equiv 1 \pmod{n} \label{5}\tag{1}$$ and $\...
  • 44.3k
4 votes

Are the structures (groups/rings) that RSA operations are performed on actually R-modules?

Or maybe the concept of modules is usually not known by students entering cryptography? I believe this is more likely; modules are a rather arcane subject, and one which even people decently educated ...
  • 134k
3 votes

Are the structures (groups/rings) that RSA operations are performed on actually R-modules?

Most students starting in cryptography either have a computer science background or a mathematics background. In either case, the students are at a fairly basic level. Computer science students ...
  • 4,467
3 votes

Are the structures (groups/rings) that RSA operations are performed on actually R-modules?

Beside what's in these other two answers, a reason not to study RSA in the question's way is that it tends to lead to a definition restricted to plaintext in $\mathbb Z_N^*$, rather than plaintext in ...
  • 126k
1 vote

Finding d of RSA given e and phi using SageMath

This is about the XGCD implementation of Sagemath. XGCD(a, b) Return a triple (g,s,t) such that g=s⋅a+t⋅b=gcd(a,b). g, s, t - such that g=s⋅a+t⋅b Note There is no guarantee that the returned ...
  • 44.3k

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