New answers tagged

14

There is no proof that the integer factorization is computationally difficult and similarly, there is no proof that the RSA problem is similarly difficult. The RSA problem RSA problem is finding the $P$ given the public key $(n,e)$ and a ciphertext $C$ computed with $C \equiv P^e \pmod n$. Factoring $\implies $ the RSA problem This is the easiest part. If ...


12

No, it's not proved that solving the RSA problem [that is, finding $x$ from the value of $x^e\bmod n$ for unknown random integer $x$ in interval $[0,n)$, and $(n,e)$ a proper RSA key ] is equivalent to factoring. It's even widely believed that does not hold, for $e$ of fixed magnitude (as used in practice) in particular. Trivially, ability to factor implies ...


12

might have the terminology wrong when I say "GF(2) polynomial multiplication" You are thinking of multiplication in the ring of binary polynomials, that is polynomials with coefficients in the Galois Field with 2 elements. That set is noted $GF(2)[x]$. It's addition reduces to XOR of the coefficients of equal weight. It's multiplication is called &...


1

In general this is not possible. Assuming a finite group, for any $A$ in the group and for any $x$ in the group, the pair $(x,A-x)$ is a possible solution. You cannot do any better. If you have some side information which enables you test a value $x$ for being valid, you would at worst still need to test every $x$ in the group. This property follows from the ...


0

Addressing kapserd's comment: Likely using more than the two primes we use today would not help immensely, and likely (again) would reduce the difficulty. This is, of course, subject to the point I shall end with (below). The reason is that there is one pair of lengths completing your right triangle for every pair combination of prime factors used. So use {3,...


2

Using for example cado-nfs, you can find the factorization (~5min using 32 cores) as 51700365364366863879483895851106199085813538441759 * 3211696652397139991266469757475273013994441374637143


15

Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit. This can be easily achieved with existing libraries like; CADO-NFS ; http://cado-nfs.gforge.inria.fr/ NFS factoring: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html Factoring as a service https://seclab.upenn.edu/projects/faas/ The Factoring as a ...


5

Aaronson's notes discuss finding $p$ and $q$ if we know $\phi(N)$ by solving the quadratic equation $X^2-(N-\phi(N)+1)X+N=0$ whose roots are $p$ and $q$. This only works if $N$ is the product of two distinct primes (which is the case in most applications of interest) and if we know $\phi(N)$ exactly. What doesn't often get mentioned about RSA and ...


Top 50 recent answers are included