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
0 answers
7 views

Find factors of N given RSA public key (e, N) and private key (d)

I am having some problems solving the following problem: find factors of N given RSA public key (e, N) = (11, 459703599527) and private key d = 125373708962. I calculated k = ed - 1/ N = 3, and Φ(n) = ...
user avatar
9 votes
1 answer
214 views

Does a 2047-bit factoring oracle affect 2048-bit RSA security?

I started wondering. RSA relies on prime factorisation being hard. So if a 2047-bit oracle machine existed that could instantly factor any 2047-bit number (and you can't look inside at how it works), ...
user avatar
  • 191
2 votes
1 answer
85 views

Is there a discrete log challenge?

RSA challenge is well-known and it has a wiki page. Is there a discrete log for $\mathbb F_p$ where $p$ is Sophie-Germain prime?
user avatar
2 votes
0 answers
62 views

Historical key sizes for RSA and discrete log [closed]

What is the historical pattern for key size increases for rsa vs discrete log? What are the current and future projected sizes for these?
user avatar
  • 882
1 vote
2 answers
74 views

Factorization of the product of two specific primes

Help me please. Consider specific primes $p = x^{d} + 1$ and $q = x^{e} + 1$ for some $x, d, e \in \mathbb{N}$. Can their product $n = pq$ be factorized faster than the product of general primes ? In ...
user avatar
1 vote
0 answers
87 views

Question about sequence length/count/security of $x\mapsto x^\alpha \mod (N=Q\cdot R)$, with $Q=2q_1q_2+1$ and $R=2r_1r_2+1$ and $\alpha = 2q_2r_2$

Given a number $N$ with $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ with different primes $P,Q,q_1,q_2,r_1,r_2$. If we now choose an exponent $\alpha$ containing prime ...
user avatar
  • 475
1 vote
1 answer
84 views

Which impact on security (factorization) has a common prime factor among prime factors? $N=P\cdot Q$ with $P=2\cdot F\cdot p+1$, $Q=2\cdot F\cdot q+1$

Which impact on security (factorization) has a common prime factor among the prime factors $P$,$Q$ of a number $N$ $$N=P\cdot Q$$ $$P=2\cdot F\cdot p+1$$ $$Q=2\cdot F\cdot q+1$$ with $F,q,p$ different ...
user avatar
  • 475
0 votes
1 answer
68 views

Given $N$ with $d$ prime factors. Can the number of unique values $x^d \mod N$ calculated for $d>2$? Does the total amount decrease at some point?

Given a number $N$ with $d$ unique prime factors. Can the number of unique values $v$ with $$v \equiv x^d \mod N$$ $$x\in[0,N-1]$$ $$N = \prod_{i=1}^{d} p_i$$ be calculated for $d>2$? (Q1) Does ...
user avatar
  • 475
2 votes
2 answers
407 views

A novel method for hiding data using prime numbers?

Has the following method of hiding data been proposed or studied? What is the efficiency or security of this method? What applications could use this method? Data is to be hidden in a number that is ...
user avatar
2 votes
1 answer
74 views

Are there applications which cannot be done with only factoring trapdoor?

Suppose we only have to use factoring as trapdoor function and we are disallowed to use other trapdoors, are there applications currently deployed which cannot be done?
user avatar
  • 882
1 vote
1 answer
44 views

How secure is a projection to a subspace with much lower member size for $x\mapsto x^a$ mod $N = PQ$, $P=2p+1$, $Q=2qr+1$, to target space $r=2abc+1$?

A cyclic sequence can be produced with $$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q\cdot r+1$ and $r = 2\cdot u \cdot v \cdot w +1$ with $P,Q,p,q,r,u,v,w$ ...
user avatar
  • 475
1 vote
1 answer
59 views

Can Shor's algorithm factor over finite fields/rings/groups?

Shor's algorithm can (efficiently) solve equations of the form: $$n = pq$$ and $$n = x^{2} + y^{2}$$ This question is simple: Can Shor's algorithm solve these equations in polynomial time when they ...
user avatar
  • 45
3 votes
1 answer
85 views

Can Shor's algorithm factor over the gaussian integers?

This is related to this question about solving the following expression: $$x^{2} + y^{2}$$ This can be factored over the gaussian integers as $$(x + iy)(x - iy)$$ If one could factor a sum of two ...
user avatar
  • 45
1 vote
1 answer
54 views

Is $\mathbb{Z}_2[x]$-irreducibility in ${\bf P}$?

A fast alternative to conventional multiplication is the carry-less product. It works exactly in the same way as the multiplication on the countable set of binary polynomials $\mathbb{Z}_2[x]$. We can ...
user avatar
3 votes
1 answer
161 views

Probability of choosing a base successfully in Pollard p-1 factorization method

In a problem about pollard p-1 factorization method, where $n=pq$. We choose some random base $a$ , and an exponent $B$, where hopefully $p-1$ has small prime factors, and if so we hope to estimate $p ...
user avatar
2 votes
2 answers
174 views

How much work to find such $n$?

Let $W$ be a random $200$ bit number. How much work would it take to find a semiprime $n=p_1\cdot p_2$ such that $p_1,p_2 > 2^{50} $ and $|W-n|<2^{12}$? More generally, let $W_b$ be a random ...
user avatar
  • 21
1 vote
2 answers
152 views

Using Shor's algorithm to access RSA messages without factoring

Most of the time people forgot that the real aim of the adversary against encryption is accessing the message. For example, in the RSA case, we talk about the factoring of the modulus to reach the ...
user avatar
  • 43.4k
0 votes
1 answer
126 views

Rabin Cryptosystem: Chosen-Ciphertext Attack

I read in literature that Rabin Cryptosystem can be broken using chosen-ciphertext attack. It is described that after chosen ciphertext is decrypted attacker can factorize public key $n$ by using ...
user avatar
1 vote
1 answer
111 views

What are those RSA Challenges, DES Challenges and RSA Factoring Challenges

Can someone explain the differences between the DES challenge, the RSA challenges, and the RSA factoring challenge? What were the aims? I think the factoring challenge was to encourage research, the ...
user avatar
2 votes
1 answer
165 views

Factoring a RSA modulus given parts of a Factor

e,N,c and around 2/3 of p are given and I need to get the whole p to decrypt c. ...
user avatar
1 vote
1 answer
78 views

The significance of the field of the factor in Lenstra’s ECM

I am going through Lenstra's Elliptic Curve Factorisation from Silverman's Mathematical Cryptography book. I have understood the algorithm itself, but unable to understand a specific point the book ...
user avatar
  • 1,637
1 vote
1 answer
112 views

RSA factorization knowing the form of p and q

I'm wondering if knowing the form of both factors (p and q) of a RSA modulus N is a significant help for factoring or not. For instance: p of the form 4k+3, so (p-3)%4 = 0 and q of the form 4k+7, so (...
user avatar
  • 11
2 votes
0 answers
76 views

What would be the safety requirements for the primes in $n=p \cdot q$ regarding the factorization?

Let it be $p, q \in \mathbb{P}$ with $p,q \in [2^{b-1}, 2^b]$ for some $b \in \mathbb{N}$ and $p \cdot q = n \in \mathbb{N}$. What would be the distance between $p$ and $q$ (as a function of b) so ...
user avatar
  • 53
0 votes
1 answer
140 views

RSA use prime p as public exponent

I've got two 1024 bits prime $p$,$q$,and $n$ = $p$ * $q$. now I know the result of $ c^{p} \quad mod \quad n = x$,also the value of c is given, I wonder if it is possible to factorize $n$.
user avatar
  • 29
2 votes
1 answer
166 views

Quadratic Sieve: Is there a thumb rule for deciding how many numbers to sieve?

In the Quadratic Sieve algorithm, we first decide on a B & then look for B-smooth prime factors by sieving using a quadratic polynomial. I can find a few formulas which help figure out how to ...
user avatar
  • 1,637
6 votes
4 answers
1k views

RSA given n % (q-1)

I am trying to work out an RSA challenge where I am given n, e, c and the result of n mod (q-1) However, I can't wrap my head around the maths. Could anyone help?
user avatar
3 votes
1 answer
103 views

Quadratic Sieve: Sieving with prime powers

I am trying to understand the Quadratic Sieve algorithm. Currently I am stuck at the sieving part. Let's say the number to be factored is 9788111. I decide to look for 50-smooth factors. My initial ...
user avatar
  • 1,637
11 votes
8 answers
13k views

Cracking RSA (or other algorithms) manually by a savant

RSA cryptography strength comes from the hardness (or so we believe) of factoring big numbers. For key lengths over 2048 bits, it is infeasible for current or near-future computers to factor those ...
user avatar
  • 171
1 vote
1 answer
90 views

Factors calculation in RSA

You are given $d\bmod(p-1)$ , $d\bmod(q-1)$ , $\operatorname{invert}(p,q)$ and $p\bmod2^{200}$, the public exponent is $e=65537$. $\operatorname{invert}(p,q)$ is the answer of $ p*x \equiv 1 (mod\quad ...
user avatar
  • 29
0 votes
4 answers
434 views

When is a large semiprime possible to factor?

Under which conditions is a large semiprime possible to factor? In particular, is the following 400-digit semiprime actually trivial to factor into primes? ...
user avatar
  • 119
1 vote
1 answer
137 views

Pollard's p - 1 - how do you set the bound & how do you set the base numbers

In Pollard's p-1 algorithm for factoring N, you try to find a L such that p - 1 divides L. Then you check $gcd(pow(a,L,N)- 1, N)$. If 1 < gcd < N, then you have found one of the factors. I have ...
user avatar
  • 1,637
1 vote
0 answers
83 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 ...
user avatar
  • 11
1 vote
1 answer
142 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 ...
user avatar
  • 1,637
1 vote
1 answer
98 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 ...
user avatar
  • 124k
30 votes
1 answer
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 ...
user avatar
1 vote
0 answers
45 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 ...
user avatar
8 votes
2 answers
4k views

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

I can't find any publication that proves this.
user avatar
  • 125
9 votes
1 answer
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$...
user avatar
  • 2,214
0 votes
1 answer
41 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 $...
user avatar
8 votes
2 answers
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 ...
user avatar
5 votes
1 answer
113 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 ...
user avatar
  • 53
5 votes
1 answer
144 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 \...
user avatar
  • 457
-2 votes
1 answer
522 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 ...
user avatar
2 votes
1 answer
150 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 ...
user avatar
0 votes
2 answers
238 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 ...
user avatar
  • 3
2 votes
3 answers
262 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 ...
user avatar
  • 121
91 votes
4 answers
42k 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 ...
user avatar
  • 1,532
3 votes
0 answers
160 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 ...
user avatar
  • 43.4k
1 vote
1 answer
92 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 ...
user avatar
3 votes
2 answers
147 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. ...
user avatar
  • 117

1
2 3 4 5 6