Questions tagged [factoring]

The decomposition of an integer number to the product of other integers. Algorithms such as RSA are based on the premise that no practical way has been found was to factorize large integers when they have been produced by multiplying two large primes.

Filter by
Sorted by
Tagged with
0
votes
0answers
23 views

Is there any relation between Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption?

We have DCRA and ECSQRT assumptions. ECSQRT: Square roots in elliptic curve groups over Z/nZ Definition: Let E(Z/nZ) be the elliptic curve group over Z/nZ. Given a point Q ∈ E(Z/nZ). Compute all ...
1
vote
1answer
70 views

Why is factorial used in Pollard's $p - 1$ algorithm?

Why exactly do we use factorial for finding an $L$ which is divisible by $p - 1$? Pollard's algorithm is about B-powersmooth numbers & not B-smooth numbers. So where exactly does the factorial ...
1
vote
1answer
92 views

Cost of factoring $u^2-v^2$ when $v\ll u$?

What's the approximate computational cost of factoring $N=u^2-v^2$ when $v\ll u$? Assume $u$ and $v$ are unknown integers, with $u$ large enough that $n$ has the size of an RSA modulus. I suspect ...
31
votes
1answer
5k views

How was this 2048 bit number factored so fast?

I'm working on a CTF. The challenge is to get the contents of an encrypted message given the ciphertext and the 2048-bit RSA public key. I did finally get the flag after a few hours, but I'm still not ...
1
vote
0answers
36 views

Security game for factoring

this is probably a fairly simple request, but I have'nt been able to find it anywhere. A lot of cryptography schemes have security games associated with them. In the Book by Katz, a bunch of schemes ...
7
votes
2answers
3k views

Is it proven that breaking RSA is equivalent to factoring as of 2021?

I can't find any publication that proves this.
9
votes
1answer
1k views

Does the security of RSA come from just the carries in multiplication?

Although it's hard for me to find a reference, it's my understanding that if you calculate $N = pq$ using $GF(2)$ polynomial multiplication rather than ordinary multiplication, it is easy to factor $N$...
0
votes
1answer
38 views

summation problem?

Let there are two given numbers $x,y$ which is $A=x+y$ and we know just $A$. How we can find this just $x$ and $y$? If you suppose $a$ a random number, then we know $x_1=a$ and $y_1=A-a$ satisfies in $...
7
votes
2answers
2k views

Prime factorization (102 digits)

I have a number that consists of 102 digits and I need to factor it. I ran it in alpertrom.com.ar, but it'll take up to 40 hours if I counted all right. Is there any way to make it by hand (stupid ...
5
votes
1answer
90 views

Why doesn't this factoring to order-finding reduction work?

Scott Aaronson likes to motivate the factoring-to-period-finding algorithm used inside Shor's algorithm as follows. Now, I want you to step back and think about what this means. It means that, if we ...
5
votes
1answer
120 views

Factorization for special primes $P$, $Q$, and $R$

Suppose that $p$, $q$, and $r$ are distinct $n$-bit primes, we define $$ \begin{array}{rcl} P & = & p \mathbin\Vert q \\ Q & = & q \mathbin\Vert r \\ R & = & r \mathbin\Vert p \...
-2
votes
1answer
237 views

How can I find d knowing c, n, e in RSA?

If I know $n,e,c$ can I find $d$ in RSA? ($n = 3174654383$ and $e = 65537$ $c=2487688703$) I saw this $d=(1/e)\bmod\varphi$ but if the numbers are getting bigger it can be hard to get $d$ in that way ...
2
votes
1answer
102 views

Can you break an RSA modulus if you know $k \cdot \phi(n)$ where $k$ is a large prime?

Given some RSA modulus $n$, can you factor $n$ if you are given $k \cdot \phi(n)$ where $k$ is also a large prime? (Of course, you could factor $n$ if you were given $\phi(n)$ as discussed here, but ...
0
votes
2answers
108 views

Do perfect squares count as valid moduli for an RSA semi-prime?

The question is pretty self-explanatory but basically I just want to ask if, when choosing the p and q primes that, when multiplied, become the modulus for an RSA public key, is there a risk that ...
2
votes
3answers
167 views

Factoring Anderson's RSA backdoor

In 1993, Anderson [1] proposed a backdoor to the RSA key generation algorithm. This backdoor requires that a backdoor key (prime) $A$ be implanted within the key generation portion of the RSA ...
88
votes
4answers
40k views

Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?

Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct? It says that the algorithm factors integers $N \approx 2^{400}$ and $N \approx 2^{800}$ by $4.2 \cdot ...
3
votes
0answers
92 views

How can the Number Field Sieve attack the discrete log in $\mathbb Z_p^*$ of DSA?

The Digital Signature Algorithm (DSA) uses $L$-bit prime $p$ and $N$-bit prime $q$ with $q| p-1$, i.e., $p = r\cdot q +1$ ( Schnorr group if $r>2$ and safe prime if $r=2$). In a way, the security ...
1
vote
1answer
77 views

Is RSA-OAEP secure against Shor's factoring algorithm

I've seen in this answer Can Shor's algorithm compromise RSA when both the public and private key are secret? that if textbook RSA is used (deterministic) the Shor's algorithm can reak it. However, if ...
3
votes
2answers
140 views

Does Coron and May's paper for deterministically reducing finding 𝑑 to factoring 𝑛 work with $\lambda(n)$?

Samuel Neves in his reply mentioned a method by Coron and May's 2004 paper for deterministically reduce finding 𝑑 to factoring 𝑛. As you all know, we are using $\lambda(n)$ everywhere now for RSA. ...
1
vote
0answers
99 views

Where is factoring if discrete logarithm is broken?

Assume given $g^X\equiv h\bmod p$ where $g$ is of order $\frac{\lambda(p)}2$ where $\lambda(p)$ is Carmichael Lambda function applied to prime $p$ (so $2$ is invertible in exponent) we can compute $X$ ...
0
votes
0answers
42 views

Generalization of Bezout Identity for Polynomials

Let $i \in \{1,\ldots, n\}$, $f_i(x)$ be a univariate polynomial, and $g(x) = \mathsf{GCD}(f_1(x), \ldots,f_n(x))$. According to Bezout identity, there exists $a_i(x)$ such that: $$\sum_{i \in [n]}a_i(...
1
vote
1answer
81 views

How long to reestablish PKI if Diffie Hellman and Factoring are in classical $P$?

Supposing there is a classical (no need quantum) $O(\log N)$ algorithm to factor integers $N$ and supposing there is a classical (no need quantum) $O(\log p)$ algorithm to find $g^{xy}$ given $g^x$ ...
0
votes
0answers
54 views

How do I retrieve a number which has been multiplied with a random number?

I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$. Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number. I do not have $\phi$ ...
2
votes
0answers
43 views

Possibility of computing a and b values from the ciphertext?

Using paillier encryption, $N$ is the product of two large prime numbers, $s$ is sampled randomly from $Z_{N^2}$ we get $ C \leftarrow g^ms^N \bmod N^2 $ where $g=1+N$, By multiplying the cipher $c$ ...
1
vote
1answer
342 views

How Does Prime Factorization Break ECDSA?

I have heard that ECDSA will be broken in the not-to-distant future (roughly 15-25 years) by Quantum Computers running Shor's Algorithm. However, to my understanding, the only purpose of Shor's ...
7
votes
1answer
130 views

Is phi-hiding assumption as hard as integer factorization?

Phi-hiding assumption can be simply stated as (wrt hardness) It is difficult to find small factors of $\varphi(m)$ where $m$ is a number whose factorization is unknown and $\varphi$ is Euler's ...
2
votes
1answer
58 views

Does knowing modular eth roots help in factoring n?

Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e>2$, with $n$ being a composite integer and unknown $x$. Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to ...
0
votes
1answer
220 views

Why discrete logarithm modulo composite moduli not popular and not defined in standards?

The classical discrete logarithm problem is to find $x$ such that $g^x\equiv h\bmod p$ where $p$ is a prime and $g$ is generator of multiplicative group modulo $p$. The demerit of this approach seems ...
7
votes
2answers
876 views

Calculating RSA Public Modulus from Private Exponent and Public Exponent

If I know the private and public exponents ($d$ and $e$) of an RSA key pair, is it possible to (efficiently) calculate the public modulus $n$?
0
votes
1answer
77 views

On splitting vs factoring

On page 89 Remark 3.5 in the Handbook of Applied Cryptography the following is written: A non-trivial factorization of $n$ is a factorization of the form $n = ab$ where $1 < a < n$ and $1 &...
3
votes
0answers
62 views

Multi-users RSA problem

Rivest and Kalisky's RSA problem considers various notions on security of the RSA One-Way Trapdoor Permutation. They do it only from the perspective of a single user. What's the state of the art in ...
3
votes
1answer
62 views

Computational trapdoor where the problem is tractable for both parties but easier for one

Usually the sort of trapdoors which are talked about are designed such as to make the computation intractable for one party and tractable for the other. But what if one party merely has a big ...
1
vote
1answer
67 views

With composite $n_1$ = $p_1q_1$, and a separate $n_2 = p_1q_2$, can the primes be calculated more efficiently than factorization?

Supposing that the (3 total) primes are kept secret? Does the reuse of $p_1$ allow an attacker to compromise $n_1$ and $n_2$ if the attacker guesses that both were generated with a shared prime ...
2
votes
1answer
140 views

Can Eve break this public key cryptosystem if she can solve DLP or DHP?

The PKC is in this way: Alice and Bob fix a publicly known prime $p$, and all of the other numbers used are private (unless sent). Alice takes her message $m$, chooses a random exponent $a$, and ...
8
votes
0answers
101 views

Hardness of iterated squaring in Pailler group

The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random: Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
6
votes
3answers
299 views

Decrypting small integers under RSA

Let $(n,e)$ be an RSA public key. Suppose $c = m^e \pmod n$, where $c>1$ is a very small integer. For concreteness, say $c=2$ or $c=4$. Is it hard to find $m$ under the RSA assumption (or any of ...
1
vote
1answer
106 views

Algorithm for factoring a 30 decimal digit number

My professor has given me an RSA factoring problem as an assignment. The given modulus is 30 decimal digits long. I have been searching a lot about factoring algorithms. But it has been quite a ...
0
votes
1answer
117 views

Prime Factorization in RSA always leads to the product of two primes?

Lets prime factorize $30$: $$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$ We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two ...
0
votes
1answer
111 views

Factorization problem

Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$? Note that, either $a$ or $b$ can be reused to ...
0
votes
0answers
266 views

Brute force integer factorization - back of the envelope calculation

RSA-240, an integer with 240 decimal digits from the original RSA Factoring Challenge, has recently been factorized. According to the researchers, the factorization took a total of 900 core-years on ...
1
vote
0answers
42 views

How large a product out of 3 close-by factors need to be to avoid factorization?

For encryption a prime $P = 2 \cdot Q \cdot R \cdot S +1$ was used. An adversary want to solve the discrete log problem $m \equiv g^i \bmod P$. For this he want to use the Pholig-Hellmann algorithm. ...
1
vote
0answers
27 views

Help with next step in the Quadratic Sieve

So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here: Say, for N = 90283, I compute bound 𝐡=𝑒(12+π‘œ(1))(ln(𝑛)ln(lnπ‘›βˆš))...
3
votes
1answer
377 views

RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N?

For $N=pq$, if the first $x$ least significant bits of both $p$ and $q$ are leaked. what is the advantage in factoring $N$? Does this give an advantage beyond simply lowering the number of bits we ...
2
votes
1answer
72 views

Modification of RSA using two inverses, one for P mod (Q-1) and one for Q mode (P-1), instead of inverse d mod [(p-1)(q-1)], more or less secure?

Lets say I have the following modified RSA scheme We choose two large primes P, Q, with additional restriction that these are relatively prime to (p-1) and (q-1) We choose N = PQ as public key We ...
2
votes
1answer
455 views

Msieve & Yafu - RSA Exponents and bruteforcing

I am a layman in regards to the math behind RSA (and in general, relatively), and my goal is to bruteforce a large quantity of 512-bit RSA keys. Having searched around, I see that msieve, yafu, and an ...
1
vote
0answers
49 views

If they exist a relation between decisional Diffie-Hellman assumption and composite decisional residuosity assumption

From the cryptographic hardness assumptions, we have DDH and CDR assumptions. It is known that the composite decisional residuosity assumption is related to a factoring problem, while the DDH is ...
1
vote
1answer
195 views

Show that $\text{FACTORING} \le_P \text{SQROOT}$

I tried to prove that $\text{FACTORING} \le_P \text{SQROOT}$ in a general setting, so $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$. THEOREM:Let $n$ be a composite ...
0
votes
1answer
77 views

If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors?

Suppose you are given an algorithm $A$ which takes $y \in \{0, 1, \ldots , N βˆ’ 1\}$ as input, and outputs $x \in \{0,1,\ldots,N βˆ’ 1\}$ such that $x^2 \equiv y \pmod{N}$. Design an efficient, ...
0
votes
0answers
55 views

Given a deterministic oracle that calculates square roots modulo n, factor n

When $n = pq$ where $p$ and $q$ are primes, we can generate random numbers until we get $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$. This implies $n$ has some common factor with $a^2-b^2$, and then ...
-1
votes
1answer
466 views

Factoring 2048 bit number is easy?

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? i used prime 95. and actually i am kinda curious how it found a factor so fast? i can even factor ...

1
2 3 4 5 6