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.

274 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
34
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 ...
15
votes
0answers
295 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 ...
15
votes
0answers
302 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 ...
13
votes
0answers
239 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 ...
11
votes
0answers
714 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
709 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
427 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 ...
6
votes
0answers
265 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 ...
5
votes
0answers
361 views

RSA like trapdoor permutations in Discrete logarithm

In RSA, given only $(n,e)$, where $n =pq$ and $e$ is the public exponent, it is hard to find $p$ and $q$. It also seems hard to find $d$. So we came up the RSA conjecture that is RSA defines a ...
5
votes
0answers
243 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
86 views

Can RSA re-encrypt a message without decrypting it?

The goal of this question is to allow a server/proxy to forward an encrypted message without being able to read it with this procedure being transparent to the original sender and receiver. Assume we ...
4
votes
0answers
112 views

Source of very large prime numbers

The RSA cryptosystem makes use of $n=pq$ where $p, q$ are large prime numbers. With quantum computing, factorization might become easier, so it will probably be useful to use much much bigger $p$, $q$ ...
4
votes
0answers
246 views

Where is RSA-KEM used as of 2020?

RSA-KEM is introduced by Yuliang Zheng and Jennifer Seberry 1992, Practical Approaches to Attaining Security against Adaptively Chosen Ciphertext Attacks and compared the security against OAEP ...
4
votes
0answers
95 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 ...
4
votes
0answers
125 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
127 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
87 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
102 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
210 views

How much plainext could be known without reducting security of RSA?

It is known, for example, that exposing 50% of the most significant bits of RSA private exponent does not provide security risk (when a small public exponent is used). So how to qualify security ...
3
votes
0answers
55 views

Is it possible to have a shared secret without any party knowing all the parts?

I believe with Shamir’s Secret Sharing Scheme, I can create an n-part secret and distribute each of those parts to n parties. ...
3
votes
0answers
83 views

No Final subtraction in Word-level Montgomery Multiplication

I am trying to make an RSA module in VHDL, which in turn will be deployed to an FPGA. I am trying to implement a full Montgomery algorithm which means that I am working with the Montgomery ...
3
votes
0answers
345 views

Is "Fast Factoring Integers by SVP Algorithms, corrected" correct?

Schnorr comes again. Will he really break RSA this time? But he still didn't give any concrete examples that can enable us to quickly verify his claim.
3
votes
0answers
149 views

Criteria for public modulus of RSA accumulator

What are criteria for generation of an RSA public modulus used in an RSA accumulator, and their rationale? Are there special requirements in some sub-cases, like for «one-way» accumulators? Josh ...
3
votes
0answers
33 views

Security of receiving RSA-PSS computed mask in verification step

I'm trying to verify an RSA-PSS padding in an Ethereum smart contract The code to compute the MGF step (i.e. calculating many SHA1 hashes) is very expensive in terms of computation costs (gas) on ...
3
votes
0answers
87 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) states the following offer corresponding security strenghts (...
3
votes
1answer
130 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
70 views

How to extract message in Bleichenbacher 1998 attack

I'm 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 $c =...
3
votes
0answers
270 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
258 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
0answers
872 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 ...
3
votes
0answers
181 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....
3
votes
0answers
111 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
651 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
227 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
460 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
331 views

Encrypting/Decrypting using RSA and AES; standards?

I'm looking for a standard way of encrypting and signing a message using RSA and AES. I understand that in pseudo-code the actions taking place are like this: Alice's actions for sending a secret ...
3
votes
0answers
481 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 ...
3
votes
0answers
189 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 the ...
2
votes
1answer
69 views

Need help to understand RSA common modulus attack to get private key

I'm learning about common modulus attack and learned that public modulus attacks can find out the private key. Assume there are 2 users with public and private keys $(e_1, d_1)$ and $(e_2, d_2)$. ...
2
votes
0answers
56 views

Coursera Course or book(s) That covers the following subjects: OPENSSL, SSH, PKI, MD5, RSA, Certificates, keys, signatures

I started working as a developper in a cryptography company 3 months ago where the applications are for mostly windows applications. I found that I don't have enough knowledge concerning the topics ...
2
votes
0answers
179 views

Schnorr RSA factoring (round 2)

Introduction Earlier this year Claus Peter Schnorr claimed to have "broken RSA". The original paper was discussed in Does Schnorr's 2021 factoring method show that the RSA cryptosystem is ...
2
votes
0answers
50 views

Large e in RSA but not Wiener attacks

How to find $d$ with large $e$ ? If $(3\cdot d)^4 \le n$ : Wiener attacks, so what if $(3\cdot d)^4 > n$ ?
2
votes
0answers
71 views

Security of Full Domain Hash (or not quite full)

Full Domain Hash is the simplest signature scheme based on a trapdoor permutation (such as textbook RSA) that enjoys a strict security reduction. It was introduced by Mihir Bellare and Phillip Rogaway:...
2
votes
0answers
61 views

How to associate a post-quantum public key with a pre-quantum one in blockchains?

As a layperson, I'm curious if a cryptocurrency could fork to a quantum-resistant algorithm without people losing access to their wallets. Is it possible to generate a quantum-resistant public key ...
2
votes
0answers
48 views

What grade of protection does a private key's passphrase provide at best?

Does a passphrase with high entropy provide the same level of security as the private key itself? General scenario: An attacker has access to a private key file that is protected with a passphrase ...
2
votes
0answers
89 views

RSA: Find message (m) given that you know p,q, cp and cq where cp=m^dp mod p and cq = m^dq mod q

I have come across an RSA problem that goes like this: You have $p,q,cp,$ and $cq$. You know that $cp = (m^{dp}) \bmod p$ and $cq = (m^{dq}) \bmod q$ where $dp = d \bmod(p-1)$ and $dq = d \bmod(q-1)...
2
votes
0answers
227 views

Can I use RSA as hash function?

My end goal is to have an encryption function $e$ and a hash function $H$ such that for all m we have: $$H(e(m)) = e(H(m))$$ This would work if we use RSA encryption along with RSA "hash", ...
2
votes
0answers
78 views

Content Key Encryption for Multi-User data access

I recently worked out a concept for a use-case, but I'm not sure if my approach is good enough. So I would appreciate feedback and things to look out for, as I'm fairly new to this field. A User can ...
2
votes
0answers
507 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
64 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² ...

1
2 3 4 5 6