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,853 questions
-1
votes
1
answer
283
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,199
2
votes
1
answer
244
views
Factor multi-prime RSA
I have a multi prime 2043 bit modulus with 8 prime factors, each 256 bit.
...
- 21
2
votes
1
answer
114
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.
$$
...
- 522
1
vote
1
answer
128
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
151
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
196
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
1
vote
2
answers
245
views
RSA: Construct PKCS #1 padding for given data string and cipher prefix
Let $n$, $e$ be an RSA public key. Let $k$ be the byte length of $n$. Hence, we have $2^{8(k-1)} \le n \lt 2^{8k}$.
A data string $DS$, consisting of $|DS|$ bytes, is encrypted as follows. First, a ...
6
votes
1
answer
1k
views
Factoring RSA numbers on a laptop
According to https://en.wikipedia.org/wiki/RSA_Factoring_Challenge $862$ bit $RSA$ numbers have not been factored.
With the current state of the art in sieve techniques is it possible to factor $460$ ...
- 1,199
1
vote
0
answers
124
views
Fermat's difference of squares: Expanding & factoring the subsequent differences to infinity [closed]
If I factor all subsequent differences of Fermat's difference of squares, I conclude that $(a^2-b^2) = 0$ as follows below. Did I do something incorrect in my expansion, or is my attempt at proof ...
- 91
3
votes
2
answers
358
views
In the RSA(SSA)-PSS signature scheme, why does the message need to be hashed twice and why is masking the "salt" needed?
I'm trying to understand the design of RSA(SSA)-PSS, as shown here:
https://upload.wikimedia.org/wikipedia/commons/5/53/RSASSA-PSS_PSS-encode.png
Two things I don't really understand:
Why does the ...
1
vote
1
answer
100
views
Obliviously sampling RSA moduli
Is it possible to efficently sample an RSA modulus (a product of two uniformly random λ-bit primes) obliviously?
Obliviously here means that the random coins used for the sampling should not reveal ...
- 148
1
vote
0
answers
72
views
Can this identity between integer products and digital roots aid in partial RSA key recovery?
I've recently published a paper introducing a new algebraic identity that links integer products and their digital roots in a structured way.
The identity is:
$
\frac{pq - r_p r_q}{9} = 9 \cdot \frac{...
- 11
1
vote
0
answers
105
views
Can products of primes generated by this random walk algorithm be factored efficiently? [closed]
Algorithm Description:
A prime-generation algorithm constructs random primes by appending digits such that:
Start with a small initial digit (e.g., 1).
At each step, append a new digit d to the ...
- 577
0
votes
0
answers
25
views
k- out of N oblivious transfer based on "blindable" one-more assumptions?
I was thinking about one paper I was writing and suddenly it occurred to me that I can build k-out of n oblivious transfer using any of the blindable one-more type problems (One more RSA-inversion, ...
- 671