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.
234
questions with no upvoted or accepted answers
32
votes
0answers
2k views
Who first published the interest of more than two prime factors in RSA?
Multi-prime RSA is now a well known technique (described here): it uses $k>2$ distinct secret prime factors in the public RSA modulus, with the advantage that, using the CRT, we can gain a speed ...
14
votes
0answers
231 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 ...
13
votes
0answers
244 views
Name of an archaic type of RSA padding (0BBBBBBB…)
In some legacy code, I encountered RSA signature padding in the following format (hexadecimal):
0B BB BB BB BB BB BB ... BB BB <hash>
Is there a name for ...
11
votes
0answers
175 views
RSA key such that pi deciphers to your name per RSA-OAEP
Can you efficiently construct an RSA public/private key pair with $8k$-bit public modulus such that $C=\left\lfloor\pi\,2^{8k-2}\right\rfloor$ deciphers per RSA-OAEP to your name as a bytestring in ...
9
votes
0answers
535 views
RSA factorization with special primes
Suppose that primes for RSA modulus are generated using formula:
$P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$
where $x,y$ are unknown random numbers with size 128 ...
9
votes
0answers
652 views
Are there attacks against broken RSA signature pad checking with $e = 65537$?
Let's say that an RSA implementation of PKCS #1 signatures fails to validate that the 00 01 FF FF FF ... FF 00 portion of the decrypted signature is exactly as long ...
8
votes
0answers
304 views
Bleichenbacher RSA1024 signature forgery, closed-form solution
Hal Finney's writeup (Bleichenbacher's RSA signature forgery based on implementation error) shows a formula for RSA3072. I tried to replicate the attack for RSA1024 and failed, since the first term of ...
5
votes
0answers
52 views
Finding the period of a function with a single output qubit - impact on RSA
In this paper,May and Schlieper claim that one can find the period of a function $f()$ by embedding $h \circ f = h(f(x))$ for input $x$. This would have the immediate consequence of reducing the ...
5
votes
0answers
220 views
Is there an efficient way to verify the union of two RSA accumulators?
More specifically, say we have one RSA accumulator $A_{S_1}$ accumulating set $S_1$ and another RSA accumulator $A_{S_2}$ accumulating set $S_2$. Does there exist a sublinear method to securely verify ...
5
votes
3answers
233 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 ...
4
votes
0answers
91 views
The security of blind RSA signatures with modular exponentiation as padding
It is known that (blind) RSA signature implementations should apply some sort of padding to messages before signing or blinding them. Does blind RSA signature with modular exponentiation as a padding ...
4
votes
0answers
100 views
Why do one-way accumulators use rigid integers as the modulus?
In the paper that introduced one-way accumulators, the author's justify their use of rigid integers as the modulus with the following:
The advantage of using a rigid integer $n = pq$ is that the ...
4
votes
0answers
78 views
Computing cost for a trillionaire to compute GNFS in RFC 3766
RFC 3766, Section 4.1 discusses picking $n$ to achieve some target cost for employing the GNFS, i.e., $T$ is known and $N$ is unknown in the below equation:
$$T = \kappa \cdot \exp{\left(c \cdot (\ln{...
4
votes
0answers
96 views
What followed findings of A. Lenstra et al. concerning shared factors of practical RSA moduli?
A. Lenstra et al. had a paper in 2012 "Ron was wrong, Whit is right", in which one reads: "What surprised us most is that many thousands of 1024-bit RSA moduli, including thousands that are contained ...
4
votes
0answers
161 views
Is MITM possible after key exchange phase done successfully in RSA?
Is MITM attack theoretically possible after public/private key pair exchange is done successfully. Say Alice and Bob have genuine public keys of each other. Is MITM possible further during ...
3
votes
0answers
51 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
39 views
Update non-member witness in RSA accumulator
According to study of "Universal Accumulators with Efficient Nonmembership Proofs", I don't understand exactly how to update non-member witness in construction 4.2.
In the addition step, I understood ...
3
votes
0answers
97 views
How do I recover RSA primes from the modulus and the coefficient?
The RSA private key contains 2 primes (of about 4096 bits each), and I only know their product (called modulus) and the modular inverse (called coefficient).
How do I recover the RSA primes from the ...
3
votes
0answers
73 views
RSA calculate $d$ using Chinese Remainder Theorem with $d_p$, $d_q$ and $e$
Suppose for a RSA system I have the following variables given:
modulus $n$, expononent $e$, $d_p$ and $d_q$Where, $d_p = d\bmod(p-1)$ and $d_q = d\bmod(q-1)$,
Is it possible to find the private ...
3
votes
1answer
141 views
RSA Accumulators with auxiliary information or known trapdoor information
In "Universal Accumulators with Efficient Nonmembership Proofs" by
Jiangtao Li1, Ninghui Li2, and Rui Xue3 section "How to compute witness with the auxiliary information" the authors write:
"The ...
3
votes
0answers
97 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 ...
3
votes
0answers
531 views
How to determine the correct padding to use for rsa signing?
Before today I didn't know the difference between RSA padding for encryption and for signing, I think this answer describes it pretty succinctly, however, I don't know if there is an optimal padding ...
3
votes
0answers
666 views
RSASSA-PSS p1v2.1 (rfc 4056) signing
I'm signing mails with the RSASSA-PSS (p1v2.1) certificate. When I click Details, it shows "Signature Algorithm: RSASSA-PSS".
openssl x509 -text shows
...
3
votes
0answers
412 views
RSA - factorizing $N$ to get $p$ and $q$
I need to decrypt a message encrypted using RSA. I only know the public keys $n$ and $e$.
I need to get the private key $p$ and $q$ in order to get the decryption exponent $d$. Now to do so, I know ...
3
votes
0answers
172 views
IND-CCA1 RSA padding?
I've found a way to complete a task which I'd solve with passwords or by sending keys over the wire (otherwise) by using RSA's homomorphic property.
I'm restricted to RSA (any padding; for hardware ...
3
votes
0answers
179 views
How much plainext could be known without reducting security of RSA?
It is known, for example, that exposing 50% of most significant bits of RSA private exponent does not provide security risk (when a small public exponent it used). So how to qualify security ...
2
votes
0answers
33 views
Key strength comparison: symmetric key vs RSA/DH key
I came across different reputable sources quoting different equivalent symmetric key strengths for RSA/DH keys. This NIST paper (page 67/161) states the following offer corresponding security ...
2
votes
1answer
75 views
Hard-core bits from RSA assumption
I am trying to understand better the hard-core bit property from the RSA assumption. The paper by Hastad and Naslund shows that every single bit is hard-core. By the result itself, two or more bits ...
2
votes
0answers
95 views
Fixed point in RSA encryption
Some papers count the number of the fixed points in the RSA encryption algorithm. They're a minimum of 9 and the real number depends on the smoothness of primes $p$ and $q$.
It very unlikely that a ...
2
votes
0answers
52 views
One-Way Trapdoor Permutation more secure than RSA at same width?
The classical One-Way Trapdoor Permutation is RSA. The permutation that it implements on a set of $n$ elements¹ is invertible by an adversary knowing only the public key with work $w$ conjecturally² ...
2
votes
0answers
41 views
How to extract message in Bleichenbacher 1998 attack
Im trying to understand the Bleichenbacher 1998 attack, but i am having trouble wrapping my head around the bounds-part.
So as far as i understand, the idea is the following:
We have a ciphertext $...
2
votes
1answer
86 views
Short padding + known prefix RSA attack
Suppose I have a message in the form of:
$m = \text{prefix} \mathbin\| \text{secret} \mathbin\| \text{padding}$
We have:
$e=3$
$n$
$n_\text{padding}$ (length of the random padding, <$1/4$ of $m$)...
2
votes
0answers
251 views
WebCrypto SubtleCrypto RSA sign/verify AND encrypt/decrypt?
I have a project where I'd like to use public-key cryptography in both typical sign/verify situations and encrypt/decrypt situations. For example, I'd like to create a self-signed X.509 certificate ...
2
votes
0answers
25 views
What are some examples of out of bound channels that work over the Internet in practice?
If I want to verify a public key (be it RSA, PGP, etc.) with another client over the Internet only, what are some viable out-of-bound channels for verification? Which channels have been used in ...
2
votes
0answers
72 views
Recursive RSA encryption
I have a ciphertext $C$ encrypted with public key $pub_C$, which contains ciphertext $B$ and $pub_B$, $$C= E_{pub_C}(B\mathbin\|pub_B)$$
Ciphertext $B$ is encrypted with $pub_B$ and contains $pub_A$ ...
2
votes
0answers
44 views
RSA: Blinding versus fixed-time computation
For RSA, what is the standard solution against timing attacks? I know about RSA blinding as one solution.
Another solution is to always compute both the squared value and square-and-multiply values, ...
2
votes
0answers
65 views
Concept for a RSA “repeater”. Is it sensible?
I have been using RSA signed/encrypted mailing a lot recently. Naturally, I wanted to use RSA mailing also on my phone, not only on my computer. However, I feel uneasy having my private key on my ...
2
votes
1answer
142 views
Using YubiKey to store a PIN-protected secret for disk encryption
I want to store a secret on YubiKey and use it for disk encryption. It's crucial that it be PIN protected. There are a limited number of PIN tries, and after three attempts the YubiKey would be ...
2
votes
0answers
132 views
What are the known attacks on $\phi$-hiding assumption? How to chose its parameters?
$\phi$-hiding assumption states the following.
Sample 2 random primes $e_0$ and $e_1$ in the range $[5, 2^{\lambda/4}]$. Sample $N = pq$ of length $\lambda$ ($p$ and $q$ are large primes of length $0....
2
votes
0answers
193 views
Sharing RSA private key between SSH and SSL services. How bad is it?
An appliance uses a curious way of obtaining ssh-rsa host keys: There is a single configuration option "management certificate" that sets RSA private keys both for HTTPS and SSH management.
...
2
votes
0answers
537 views
RSA most significant bit oracle attack
I have been reading up on RSA attacks and came across a problem that could be called a most-significant-bit (MSB) oracle attack.
For the sake of clarity, let's define RSA primes $(p, q)$, private key ...
2
votes
0answers
223 views
Chinese Remainder Theorem and Elgamal
I am studying an encryption scheme which is Elgamal-like where I think CRT can help optimise the encryption and decryption but I am not sure if I am applying CRT the correct way.
I have a cyclic ...
2
votes
0answers
28 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 ...
2
votes
0answers
279 views
Where shoul I store private/public keys and how should I share it?
I'm new in terms of encryption and I have to encrypt the data between two Java Spring applications, one have serves as MVC framework and other as Web Service, I'm implementing an asymmetric encryption ...
2
votes
0answers
66 views
Asymmetric encryption property required in an authentication protocol
We want to choose an asymmetric encryption scheme for use as follows:
A device holds its private key, with the corresponding public key known and trusted by all.
The device also holds a small $b$-bit ...
2
votes
0answers
174 views
What kind of RSA padding mode is it?
1: I have a HTTPS server and I added hooks in RSA decryption procedure to dump error RSA input(client key exchange).
2: I get some RSA input that I couldn't check padding successfully(It's usual) and ...
2
votes
0answers
333 views
RSA signatures that allow hash to move around in block
I'm looking at a broken RSA signature padding implementation in a real device. It's a very-badly implemented version of PKCS #1-like encoding, but before PKCS added the DER-encoded hash identifier.
...
2
votes
0answers
59 views
Does secure LWE implementation leak bit information?
We know RSA leaks one bit about the factors and improper yet secure implementations of Discrete Logarithm leak one bit about the discrete logarithm. Does LWE leak any information?
2
votes
0answers
186 views
Textbook RSA: Public key used to decrypt ciphertext and checked against known plaintext
In textbook RSA with no padding schemes, is it possible to forge a ciphertext that decrypts to a known plaintext when the ciphertext is encrypted using the private key and decrypted with the public ...
2
votes
0answers
118 views
RSA - find d,e with restrictions
For academic purposes, assuming $n, p, q$ with $n\approx 2^{4096}$ and $p,q\approx 2^{2048}$.
I need to find ($e,d$) such that:
$e$ is smaller than $2^{64}$
$d\approx 2^{4096}$ and will have as ...
