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.
25
votes
0answers
1k 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 ...
13
votes
0answers
195 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 ...
12
votes
0answers
153 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 ...
10
votes
0answers
552 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
139 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
173 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 ...
4
votes
0answers
319 views
Use RSA keys to derive AES key
I have 2 end points where I would like to derive the same AES key.
Every end point has its own RSA key pair and RSA public key from the other end point, and I would like to combine them somehow on ...
4
votes
0answers
65 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
77 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
157 views
Finding algorithm: desire RSA's uniqueness and ECDSA's space efficiency
I am asking for help in finding a signature algorithm with the following property:
Given a message m and a private key prikey, ...
4
votes
0answers
153 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
57 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 ...
3
votes
0answers
58 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
62 views
X.509 strong authentication protocols
Is there also a protocol definition in X.509? In "Handbook of Applied Cryptography" by A. Menezes there is a reference to X.509 strong authentication protocol, nevertheless, I could not find the ...
3
votes
0answers
53 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?
3
votes
0answers
291 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
150 views
Montgomery modular multiplication – confusion with subtraction of modulus
I'm reading the paper “COMPARISON OF SCALABLE MONTGOMERY MODULAR MULTIPLICATION IMPLEMENTATIONS EMBEDDED IN RECONFIGURABLE HARDWARE” (PDF) on hardware algorithms for montgomery multiplication for ...
3
votes
0answers
230 views
Attacks on RSA with partially known plaintext
I know modulus $N$, public exponent $e$ and have some crypted messages $c_i$, $c_i = m_i^e mod N$. I know something about each $m_i$: they have a sequence of bytes BAADF00D at offset $t$.
Is there ...
3
votes
0answers
495 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
264 views
Asymmetric vs symmetric encryption
I am a beginner learning about encryption and I would like to ask a few questions, hoping this is the right place to ask, so please bear with me.
We have Alice and multiple clones of Bob. Only Alice ...
3
votes
0answers
44 views
Decisional Small $e$-Residue Assumption
In 2001, Catalano et. al defined Decisional Small $e$-Residue Assumption as follows:
Let $N$ be a random chosen $\ell$-bit long RSA modulus and $e>2$ a random integer such that $\text{gcd}(e, \...
3
votes
0answers
278 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
2k views
How to generate an RSASSA-PSS signature with MGF1-SHA256?
As part of rooting a device, I need to generate a 256-byte RSASSA-PSS signature using SHA256 as the hash and MGF1-SHA256 as the mask function, for an update file I created. I can choose any 32-byte ...
3
votes
0answers
87 views
Authenticate encrypted seed for KEM + AEAD hybrid cryptosystem
Say I want to encrypt something using RSA / KEM and an authenticated cipher. I encrypt using the following scheme:
generate random seed z using ...
3
votes
0answers
147 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
375 views
Relations between RSA and DLOG, factoring and DLOG
Definition: (The generalized Diffie-Hellman problem)
Let $n=pq$ for two large primes $p,q$. Given $x, x^a, x^b,n$, find $x^{ab}\pmod{n}$.
(1) Is there a known reduction from the GDH problem to ...
3
votes
0answers
150 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
57 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
0answers
88 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
80 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
159 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
106 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
25 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
49 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
122 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
292 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
133 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
106 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 ...
2
votes
0answers
114 views
Estonian e-voting, vote verification system
I believe I do understand basics of how Estonian e-voting system work, but I'm stuck at their vote verification system. In order to get the vote verified, client needs to encrypt all of the possible ...
2
votes
0answers
155 views
HBCI Encryption/Decryption
I need help during implementation of C# interface (.NET framework) for encryption of messages which are sent to/from HBCI (Homebanking Computer Interface) server according to RDH-10 standard.
...
2
votes
0answers
151 views
Security of right-zero padded signatures with $e=3$
I am facing this question about RSA signatures and I understand that a hash encode is secure, but I was asked this:
Given the scheme based on RSA assumption.
Consider the RSA function f with some ...
2
votes
0answers
98 views
Is public-key cryptography the correct choice?
I'm working on a project which requires encryption of sensitive data, with communication of said data between a mobile app and a website (via an API).
I'm new to encryption and security, but my ...
2
votes
0answers
391 views
Feasible attacks on ECRSA cryptosystem
In ECRSA cryptosystem, I want to know the feasible attacks. For illustrations we have two prime $p$ and $q$ such that $p \equiv 2 \pmod 3$, $q \equiv 2 \pmod 3$ and generate key pair as follows:
$$n = ...
2
votes
0answers
376 views
Bitwise method of generating r for RSA-KEM
It seems that RSA-KEM has a very troublesome method of generating the secret $r$. It seems that the random value needs to be in the range $0 \le r \le {n - 1}$.
Now most cryptographic environments ...
2
votes
0answers
424 views
MITM Attack on Key Exchange Protocols
I was doing research on this attack and I am wondering, why is Diffie-Hellman always
associated with such an attack? Aren't other public key cryptography schemes vulnerable
to the same kind of ...
2
votes
0answers
363 views
Limit the number of private key uses for RSASSA-PKCS1-v1_5 with SHA-256 signature?
Assuming all messages and their signatures are available to the attacker, is it secure to use the same RSA private key to sign many messages (roughly $10^{6}$) via PKCS#11 ...
2
votes
0answers
35 views
Are there UFDs where the factorization problem is difficult but finding irreducibles is cheap?
Factorization of integers is hard, but finding irreducibles is expensive. Is there a ring where factorization is assumed hard but finding irreducibles is much cheaper than over $\Bbb Z$?
It could ...
2
votes
0answers
317 views
RSA_DH vs ECDH implementation
In ECDH protocol is possible, naturally, to use the same algorithm for calculate a secret key for both communication parties (Alice and Bob for example). It is possible to design also a same algorithm ...
2
votes
0answers
396 views
RSA encryption and signature padding flaw
This is Oxford's computer security exam question:
Suppose that Bob has published an RSA encryption key $ke$ (retaining in secret the corresponding
decryption key $kd$), and Alice has published a ...
2
votes
0answers
217 views
RSA Key Blinding
I was looking the answer to the following question (Timing attack on modular exponentiation), discussing the Private Key Blinding as a countermeasure for timing attacks.
Therefore I'm asking if ...
