Questions tagged [rsa]
An asymmetric (e.g. public-key) cryptosystem, based on modular exponentiation with big exponents and modulus. RSA can be used both for signature and encryption with proper paddings.
2,860 questions
1
vote
0
answers
49
views
Impact of Known Arithmetic Progressions on Semiprime Factorization via Differences of Squares
Suppose we have known small parameters $a$, $b$, and $k$ defining two arithmetic progressions: $p = a + k i$ and $q = b + k j$, where $N = pq$ is a semiprime generated from these (with $p > q$ for $...
- 21
1
vote
1
answer
85
views
In RSA, m is greater than n
If n is a 240-bit integer and is the product of two prime numbers p and q, given m % n, p, and q, and if the string corresponding to m is composed of ASCII characters, is there a way to recover m?
By ...
0
votes
0
answers
59
views
Is the large parameter k computationally significant in linear parametrizations of semiprimes with small fixed displacements?
Suppose we have a semiprime $N = p \cdot q$, where $p$ and $q$ are large primes of similar magnitude. Hypothetically, assume $N$ can be written as $N = (m \cdot k + a)(m \cdot k' + b)$, where $m$ is a ...
- 21
3
votes
1
answer
120
views
Why does a textbook RSA multiplicative attack fail with small (64-bit) moduli?
I just finished this challenge: https://cryptopals.com/sets/6/challenges/41
, which is about abusing a flaw in textbook RSA. The challenge is fairly simple: you have a server that stores ciphertexts ...
- 31
11
votes
1
answer
1k
views
Why aren't RSA public keys and signatures compressed in practice?
According to Bernstein[1], it is possible to compress RSA/Rabin public keys by a factor of 2 and 3. And compress signatures by a factor of 2. Apparently, by using Coppersmith's lattice methods.
I wasn'...
- 113
1
vote
0
answers
74
views
Hypothetical semiprime as (ax+b)*(ay+c) - RSA implications? [closed]
If a semiprime N could be written as (ax+b)*(ay+c) with fixed residues b, c, scalable small a = m, and unknown large x, y, would this compromise RSA? Any real examples or purely theoretical?
- 21
4
votes
0
answers
151
views
Is my recreation of the RSA-129 challenge (n, e=9007, numeric encoding) faithful to the original?
Note: A live, public implementation of this reconstructed RSA challenge
(with a solver leaderboard) is available here:
https://rsa-challenge.rf.gd
I am attempting to faithfully recreate the historical ...
2
votes
3
answers
622
views
Benefits and drawbacks of SSH RSA long key
I'd like to know benefits of RSA long keys (16386 and more bit length).
I know the answer for server keys, but I'd like to understand what's happening if I use such long key for a user authentication.
...
- 129
-1
votes
1
answer
304
views
RSA: Factorize $N$ with Cornacchia 's Algorithm . What is the computational cost of the Cornacchia's algorithm?
If we need to factor a number $N$
Given the Pythagorean quadruple (with $n$ and $m$ in $Z$)
$d=36m^2+18m+4n^2+2n+3$
$a=24mn+6m+6n+1$
$b=2(3m+n+1)(6m-2n+1)$
$c=2(3m+n+1)$
$a^2+b^2+c^2=d^2$
then if:
$N=...
6
votes
2
answers
1k
views
Are most RSA integers unbalanced?
RSA integers are integers of form $N=pq$ where $p$ and $q$ are primes. It appears some of the RSA challenge numbers have unequal number of bits.
Eg: RSA-190 = ...
- 1,215
3
votes
1
answer
371
views
Factor multi-prime RSA
I have a multi prime 2043 bit modulus with 8 prime factors, each 256 bit.
...
- 31
2
votes
1
answer
130
views
Modulus blinding in RSA?
To prevent some side-channel attacks in RSA, I've seen people use multiplicative blinding
$$
a^d\bmod N=(r^{-1})^d(ra)^d\bmod N
$$
or additive exponent blinding
$$
a^d=a^{d+r\phi(N)}\bmod N.
$$
...
- 607
1
vote
1
answer
161
views
RSA variant with cyclotomic polynomial
Please I want to ask if some one have any idea about a cryptosystem RSA variant when we replace $\phi(N)$ in the key equation $ed-k\phi(N)=1$ by a product of to Cyclotomic polynomial like $\Phi_8(p)*\...
0
votes
1
answer
174
views
How long would it take a 1GW GPU cluster to brute force RSA1024
Similar to How long does it take to crack RSA 1024 with a PC?
I'm wondering if someone can estimate how long it would take a large ~1GW gpu cluster (such as being built by XAI/Anthropic/Meta) to brute ...
- 101
3
votes
2
answers
205
views
What happens in RSA when $e=23$ is a factor of $p-1$?
I want to understand how to relate that
$e = 23$
$e$ divides $(p-1)$
I have the value $(p+q)\gg 100$ (where $\gg$ stands for right-shift)
I have the value $g = d^{-1}\bmod \varphi$ where $d$ is a ...
- 63