Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

3
votes
1answer
106 views

Algorithm to factorize $N$ given $N$, $e$, $d$

I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key. How can I compute $p$ and $q$, the primes factor of $N$ ?
1
vote
1answer
32 views

Counting the number of binary solutions of quadratic system

I have a quadratic system of equations related to a balanced RSA modulus $n=pq$ (i.e. $\log p\approx\log q$), and I want to give an upper bound on the number of solutions. Indeed, let $p_i,q_i$ be ...
4
votes
0answers
40 views

RSALib prime generation - derive number of primes

I'm working on factorizing a ~450 bit key that I know has been generated with RSALib and thus is vulnerable to ROCA. Now reading the original paper, I can see that the primes are generated in the ...
-5
votes
0answers
29 views

Breaking RSA and Prime Factorization [duplicate]

Most of the tutorials and books mention that if ever someone comes to finding an algorithm for factorizing large semi-prime numbers (i.e. numbers that are the product of two prime numbers) that would ...
-3
votes
1answer
127 views

Why would an efficient integer factorization algorithm render RSA insecure?

I know that RSA relies on the integer factorization problem: given two primes p and q, their product p . q is easy to compute. But not feasible (i.e., polynomial-time) an algorithm is known that could ...
3
votes
3answers
2k views

Can multiplication of two primes be seen as a strong cipher?

If we were define such a cipher: A reversible function that would accept a message $M$ and an initialization vector $\text{IV}_1$ $\operatorname{map}(\text{IV}_1, M)$ which can map an input $M$ to a ...
2
votes
0answers
23 views

What are SNFS-safe limits for an RSA moduli optimized for simple modular reduction?

I consider $n$-bit RSA moduli $N$ having high-order bits starting by with $k$ bits at 1, then $k$ bits at 0, then $m-2k$ bits at ...
0
votes
1answer
56 views

How to find p,q in this problem?

Suppose \begin{align*} g^r &\equiv h \pmod N, \\ h^s &\equiv g \pmod N, \end{align*} for known $g$, $h$, $r$, $s$, and $N$, but not $\phi(N)$. Then $$g^{r\cdot s - 1} \equiv 1 \pmod N,$$...
14
votes
2answers
455 views

RSA factorization for special primes $p$ and $q$

I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given): $$p = a^2 + b^2, \...
1
vote
1answer
86 views

ROCA Implementation, Coppersmith Algorithm does not return roots

We are currently trying to reproduce the implementation of the ROCA-Paper https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf. Therefore we calculated M' from M and Order_M' ...
0
votes
1answer
58 views

Williams' $p+1$ in tandem with Pollard's $p-1$?

Since the success of the $p - 1$ algorithm depends on $p - 1$ having "small" prime factors, or at least smaller than a reasonable smoothness bound, and Williams' $p + 1$ method has the same constraint ...
4
votes
2answers
152 views

How ROCA get the polynomial used with coppersmith

I'm trying to understand the ROCA attack on RSA from Matus Nemec et al. but I'm stuck on how they goes from the constraint they have expressed has: $$f(x) = x ∗ M' + (65537^{a'} \mod M') \pmod p$$ To ...
4
votes
0answers
206 views

Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
0
votes
0answers
24 views

Why do we need 2X input bits in the circuit of Shor's quantum Algorithm? [duplicate]

The text that I am following to understand the factoring algorithm states that we need $m = 2\cdot\log(N)$ input qubits because we need to evaluate the oracle function for at least $N^2$ times. Please ...
0
votes
0answers
90 views

Rsa factoring best method and time

I am going to participate in a local challenge where you have to guess the two prime numbers(p and q), they give you a 8 bits number, 16 bits number..., 128 bits number... , 512,1024,2048... and wins ...
2
votes
2answers
68 views

Number of bits specified in standards implementation?

Currently deployed RSA and discrete logarithm implementation uses $1024$ to $2048$ bits. Hypothetically speaking if a crypto team produces a faster algorithm that moves current factoring and discrete ...
2
votes
2answers
158 views

RSA: Is possible get p and q from this d and n?

I have this algorithm and Im searching p and q: $n=p^2 * q $ $l=(p-1)*(q-1) / \gcd (p-1,q-1)$ $d\equiv l^{-1} \pmod n$ And the values are: For $n$: ...
2
votes
2answers
382 views

Recovering 3 private keys if Eve knows that the keys are shared prime numbers and knows their public keys, How would this be done?

okay so here is the original question: Alice Bob and Carl are generating public keys for RSA, but they are lazy and decide to share some of the work of generating prime numbers. They find 3 large ...
5
votes
1answer
190 views

RSA factorization knowing N, e=65537 and g=d*(p-17)

Having known the values for $N$ a large number, $e = 65537$ and another large number $g = d \cdot (p-17)$, how can I use that info to find out $p$ and $q$? I guess that have something to do with ...
2
votes
1answer
51 views

Can we efficiently factor if we are given a Pocklington certificate of one of the prime factors?

I recently read Squeamish Ossifrage's answer on generating RSA keys from (short) randomness where they make the following comment: (You might want to keep the certificate secret too.) As the ...
4
votes
2answers
165 views

Why does TWINKLE use light instead of current?

TWINKLE is a device devised by Adi Shamir to optimize the sieving step of GNFS. It consists of a cylinder, at the bottom of which are LEDs corresponding to factor base primes which blink with ...
0
votes
0answers
77 views

Can Pollard's Rho factor 167-bit RSA within a day on a single-core of a personal computer?

I am working on an assignment for school, for which I have to implement a factoring heuristic. The program must be able to factor a 167-bit modulus within a week. However, I have set my personal goal ...
2
votes
1answer
153 views

Factoring RSA-129 with a personal computer today

I have read the history of the RSA-129 challenge, and now I would like to know if it would be possible to factor RSA-129 with a single "average" personal computer, today. Has someone tried to do this ...
1
vote
1answer
346 views

Finding the first few digits of p and q

Is there a way to find out the first few digits of the factors of the RSA numbers (RSA-1024 or RSA-2048)? I do not want to get all the digits but only first 4-5 digits. My question is thus more ...
0
votes
0answers
21 views

Alternative Hard Problem to Prime Factorization? [duplicate]

Suppose in the future someone conjures a technique to (arbitrarily) quickly find the prime factors of arbitrarily large numbers, thus undermining the computational security of (as far as I am aware) ...
2
votes
1answer
65 views

Malicious DH parameters without using composite numbers

I know that it's possible to generate DH parameters that lead to it being easy to attack (e.g. trivial composite numbers), but is it possible to create a malicious parameter that is not a composite ...
-1
votes
1answer
279 views

Factoring a 512-bit number?

I want to know how to factor this number only given $n$ and $e$, I have tried to factorize $n$ using Fermat's little theorem and also tried primefac module in python (running for the past 4 days) but ...
-1
votes
1answer
93 views

Integer Factorisation

If I have a set of numbers of the form $\{ {kp+r}:k\geq0\}$ with p a prime or product of primes k large in $\in Z^+$ and r fixed, is it computationally feasible to find a factorisation for any one ...
11
votes
0answers
123 views

Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
-1
votes
1answer
104 views

Factorisation for Coprimes of Large Numbers - RSA

What is the current conventional algorithm used to calculate factors of large numbers in order to determine if they are coprimes, or if there is a way to do it without calculating factors, what would ...
5
votes
1answer
174 views

Factor RSA modulus given many valid encryption decryption exponent pairs?

I have read Is sharing the modulus for multiple RSA key pairs secure?, which explains an algorithm for factoring an RSA modulus n given only one encryption and decryption exponent tuple. Given ...
0
votes
0answers
32 views

Why for a secure RSA the difference of | p - q | should not be too small? [duplicate]

I am pretty new in this cryptography world and I have some doubts. Please help! So, for a secure RSA modulus $n=pq$ , this difference $( |p-q| )$ should not be small, then if we choose an integer, ...
1
vote
1answer
140 views

Is RSA vulnerable to possible PRNG + Miller Rabin test weaknesses?

Factoring a 2048 bit number is a difficult topic with a well known complexity. But it seems that p, q, the prime numbers used in RSA (order of magnitude: 10^308) are generated thanks to the ...
1
vote
0answers
72 views

Probability of a prime factor [closed]

We are given an arbitrary number $n$ and a sequence of primes $p_1=2$, $p_2=3$, ..., $p_k$. I am interested in the following question: Are the events "Prime $p_i$ is a factor of $n$" independent for ...
2
votes
1answer
361 views

Is factorization modulo a product of primes an NP-hard problem?

For example, let, $p$ and $q$ be two large prime numbers. We set $n = p \cdot q$. Now, let $a \cdot b = c \pmod n$. Given $c$ and $n$, is finding the factors $a$ and $b$ computationally difficult? I ...
2
votes
0answers
62 views

Are there special techniques to factor numbers of this form?

Suppose $N=p^2rq$ where $p,r,q$ are primes and $r,q$ have equal bits with roughly $(\frac14-\epsilon)\log_2N$ bits while $p$ has roughly $(\frac14+\epsilon)\log_2N$ bits is there a special technique ...
0
votes
1answer
313 views

What are some of the best prime factorization algorithms and their effecitvity

I was wondering aren't the most used prime factorization algorithms a symbolic mile behind the security of the RSA cryptosystem? The way it looks to me is that every time an algorithm is able to ...
11
votes
1answer
160 views

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$?

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$, where $t$ and $p$ are large primes?
0
votes
1answer
65 views

Factorizing a handiwork number $n$ in two prime factors

I have generated two primes $r_0$ and $s_0$ with same bit size $\le 64$, then make another two primes as follows: choose constant $k$ and define $$r_i = r_0 + \alpha_i, \quad 1 \le i \le k, \quad 0 \...
7
votes
1answer
873 views

Safe primes in RSA

It's my understanding that there's no longer a requisite of safe primes for $q$ and $p$ when choosing a RSA modulus. How is it that this does not change the hardness of factoring $N$?
4
votes
0answers
82 views

LWE status versus modern deployed crypto [closed]

LWE is the one of the most promising post quantum strategy. How does parameters (key sizes, time for encryption etc) for LWE compare with modern deployed standards such as Factoring or discrete log ...
2
votes
1answer
2k views

How to factor an RSA256 public key with YAFU?

(Layman's terms please, I'm just a kid stuck on a puzzle) I'm trying to factor the following RSA256 public key to find the corresponding private key: ...
0
votes
1answer
163 views

Factoring RSA number knowing some B-smooth numbers

Hi I am studying for an exam and having some problems solving one of the questions. It reads as follows: Factor $$N=44370047$$ using Quadratic Sieve by using the information that you get from squaring ...
6
votes
2answers
300 views

Worst case of Integer factorization

From Fundamental theorem of arithmetic, every integer greater than 1 either is prime itself or is the product of prime numbers, and that this product is unique, up to the order of the factors. $$n=...
5
votes
0answers
155 views

What are the theoretical memory requirements for these factoring algotihms?

Given an $n$ bit integer quadratic sieve takes $L(\frac12,1+o(1))$ time and number field sieve takes $L(\frac13,1.922)$ time where $L$ notation is given in https://en.wikipedia.org/wiki/L-notation. ...
0
votes
0answers
25 views

How to factor n in RSA? [duplicate]

Imagine we know n and we know the public key e and the private key d. How can i factor with these informations n ?
1
vote
1answer
208 views

Role of primitive roots in Pollard's P-1 factorization algorithm

I have recently been reading about different factorization algorithms and I came across this paper that discusses the Pollard's P-1 algorithm. In the footnote of the first page, it states... For ...
-2
votes
1answer
315 views

How expensive is the Extended Euclidean Algorithm?

Given a private key $k$ and a modulus $n=pq$, where $p \neq q$ are two very large prime numbers, we find the value of Euler's Totient Function $\varphi(n)=(p-1)(q-1)$. The public key $K$ is given by ...
-3
votes
1answer
225 views

I can divide a very large integer - did I discover anything?

So I was sitting on an algorithm I thought up at school, and just decided to implement it. And it worked for what I wanted - but I don't know what this is worth. I broke apart a 2048 private key for ...
0
votes
2answers
101 views

complexity of iterative squaring in relation to factorization

I've run into a question dealing with the number of modular multiplications of O(n) bit numbers in the following situation: Given two n bit primes p,q define m=pq. ​ ​ ​ Choose some 'a' so that ​ $2&...