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.

Filter by
Sorted by
Tagged with
9
votes
4answers
12k views

Why is RSA encryption significantly faster than decryption?

I am designing an implementation of RSA . I recorded computation times in Java by using System.currentTimeMillis(). It returned an encryption time of 0.05 ms and ...
9
votes
1answer
8k views

Can an RSA private key have several public keys?

Ok, so my cryptography lecturer in University posed this question at the end of the RSA key generation lecture as a brain teaser. I have been thinking about this and I think I have come up with a way ...
9
votes
1answer
16k views

RSA cracking: The same message is sent to two different people problem

Suppose we have two people: Smith and Jones. Smith public key is e=9, n=179 and Jones public key is e=13, n=179. Bob sends to ...
9
votes
2answers
1k views

Can RSA be used to encrypt p?

In RSA you choose $n=pq$ where $p$ and $q$ are large primes with similar length. Then you choose $e$ that is coprime with $\phi(n)$ and find $d$ that is modular multiplicative inverse of $e$ modulo $\...
9
votes
1answer
2k views

What signature schemes allow recovering the public key from a signature?

It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone. This seems like an interesting property; as far as I know, RSA doesn't share ...
9
votes
4answers
731 views

Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?

Alice is going to use some existing RSA scheme (employing industry-standard signature or/and encryption with proper padding), which she can't change, or influence beyond her choice of key. In this ...
9
votes
1answer
7k views

How do other, non-RSA algorithms, compare to the PKCS #1 standard?

Arguably the PKCS suite of standards have a profit-oriented bias as they are promoted by RSA and promote their algorithms over others in the form of RFCs and other means. I'm considering the ...
9
votes
2answers
3k views

What's the difference between rsa_pss_pss_* and rsa_pss_rsae_* schemes?

I'm trying to understand the difference between rsa_pss_pss_ and rsa_pss_rsae_. The picture shows the extension of TLS1.3's ...
9
votes
2answers
961 views

Can Shor's algorithm compromise RSA when both the public and private key are secret?

If RSA is to create a public private key pair and encryption is performed on plain test P to create cipher text C, given P and C could Shor's algorithm be used to find either of the public and private ...
9
votes
2answers
1k views

Given a message and signature, find a public key that makes the signature valid

Given a message $M$ and a signature $S$, is it feasible to find a RSA public key $(n,e)$ such that $S$ verifies as a valid signature on $M$ (using this public key)? What if we're given one public key ...
9
votes
3answers
6k views

RSA and prime difference

It is known that the two prime factors $p$ and $q$ of an RSA modulus $n$ should not be too close to each other, otherwise an attacker may factor the modulus. In other words, $\Delta = \left| p - q \...
9
votes
2answers
1k views

Is Bouncycastle RSA+OAEP implementation vulnerable to Manger’s attack?

I have written a code to encrypt a plaintext as below. Here I am using bouncycastle crypto provider and referring to the RSA+OAEP for that. ...
9
votes
3answers
6k views

Anatomy of an RSA private key

I'm learning about OpenSSL and public key infrastructure and am curious about the structure of an RSA key and how it's related to its corresponding public key. I can generate a private RSA key with ...
9
votes
1answer
3k views

RSA enc/decryption with multiple prime modulus using CRT

Every information I found on internet about RSA-CRT encryption/decryption uses only two primes. I'm interested in my project in doing that using multiple (up to 8) primes. The general idea is to ...
9
votes
1answer
1k views

Why isn't Rabin-Williams cryptosystem widely used?

I think we all know RSA. And of course we also know DJB (a.k.a. Daniel J. Bernstein). Now some already have noticed that he has an opinion towards cryptographic questions. In his 2008 paper ("RSA ...
9
votes
1answer
4k views

ECDSA vs RSA: Performance on Android platform and surprising results

For our privacy-preserving protocol, an encrypted channel is established. In order to protect our system from man-in-the-middle attacks, signature-based approach is used. After we've implemented it ...
9
votes
1answer
1k views

What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?

I was reading that a current open problem is if inverting the RSA function is as hard as factoring. Does this mean that, its an open problem whether, if given a subroutine that computes in ...
9
votes
1answer
808 views

Is it possible to have multiple RSA private keys?

I just did some math: Pick $p$ and $q$ distinct primes; Calculate $N=p\cdot q$; Calculate Euler`s totient => $\phi=(p-1)\cdot(q-1)$; Pick an $e$ (public key), coprime with $\phi$; Calculate $d$ (...
9
votes
2answers
3k views

RSA-based authentication and key-agreement protocol

An authentication and key-agreement protocol between devices shall mutually demonstrate their identity, and establish a shared random secret $R$ suitable for securing later communications. To that ...
9
votes
1answer
686 views

why did oaep change from pkcs1 v2.0 and v2.1?

In PKCS1 v2.1 the OAEP output is prepending with a null byte. Quoting RFC3447, ...
9
votes
2answers
1k views

State of the art RSA key generation

I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis. Beside the key lenght I know there are some weakness in the choice of prime ...
9
votes
1answer
4k views

How can I determine the GPG/PGP key ID from the RSA modulus?

According to http://www.pgp.net/pgpnet/pgp-faq/pgp-faq-keys.html#key-public-key-forgery, key ID is some lower bits sequence from the modulus (i.e. the $n$ variable): A PGP key ID is just the bottom ...
9
votes
1answer
1k views

In textbook RSA with low public exponent, how big does a random message needs to be?

Assume RSA with a public modulus $N$ of $n$ bits, a small odd public exponent $e$, plaintext $M$ a random non-negative integer less than $2^m$ for some integer parameter $m$, with $M\mapsto C=M^e\bmod ...
9
votes
0answers
491 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
641 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
2answers
3k views

RSA: What would happen if you chose n to be a prime? [duplicate]

If Alice were to choose n to be a prime, instead of the product of two primes, what exactly would go wrong in the RSA cryptosystem? How would Bob decrypt her message?
8
votes
2answers
2k views

Can RSA encryption produce collisions?

In RSA, a message is encrypted by $m^e \pmod N$. $N$ is the modulus, $m$ is the message and $e$ is the public exponent. (I know that $m$ should not be greater than $N$.) My question is, can $m^e$ be ...
8
votes
5answers
3k views

RSA4096 vs AES256 for secure Chat application?

Which of these two methods suits better the implementation of a secure chat application? In this context, chat will be limited up to 150 letters for one message. I would prefer RSA because what I ...
8
votes
3answers
4k views

Can an ephemeral RSA key give forward secrecy?

Suppose party A generates an ephemeral RSA key and sends the public key to B. Party B then generates a symmetric key, encrypts it with Party A's public key and sends the Ciphertext to Party A. Party ...
8
votes
2answers
974 views

Would RSA make sense if we used no computers?

I was recently wondering - would RSA be useful if we brought it to, say, medieval times? Could you choose the keys so that you could encrypt/decrypt messages quite easily, but factoring the private ...
8
votes
2answers
17k views

Why are RSA ciphertexts different for the same plaintext?

I am using SpongyCastle for a project in android. I have used RSA to encrypt the data and then decrypt it in another activity, the keys are stored in the shared preferences. I discovered a thing I ...
8
votes
3answers
4k views

Is knowing the private key of RSA equivalent to the factorization of $N$?

Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems ...
8
votes
3answers
16k views

In RSA, do I calculate d from e or e from d?

In the original paper introducing RSA, it is implied that one should first choose $d$ and then calulate $e$ from $p$, $q$, and $d$. However, I have found in other places (such as the wikipedia article ...
8
votes
1answer
827 views

The 9 lives of Bleichenbacher's CAT, it puts another scratch again

Bleichenbacher demonstrated a padding oracle attack against RSA implementations that follow the PKCS #1 v1.5. Through the years, there are various mitigation techniques developed as OAEP and limiting ...
8
votes
1answer
5k views

RSA with 3 primes

I was trying to understand how does RSA with 3 primes work. I have checked Wikipedia but yet I didn’t fully understand their solution. I would like to know how do you encrypt for $n=p*q*r$ How do you ...
8
votes
2answers
5k views

Reverse engineering secret key in RSA encryption with the help of signature

Consider the following: $i$th message, $m_i$, in its original state. $i$th message, $M_i$, encrypted message $m_i$ using public key. Public key, $p$, in a $b$-bit RSA encryption setup. We can ...
8
votes
1answer
12k views

what are DP and DQ in Encryption by RSA in c#

I want to know about these tags in RSA Encryption by private Key. when I use this code: ...
8
votes
1answer
734 views

Why Static RSA and Diffie-Hellman cipher suites have been removed in TLS 1.3?

Why Static RSA and Diffie-Hellman cipher suites have been removed in TLS 1.3? How keys can be exchanged then? https://tools.ietf.org/html/draft-ietf-tls-tls13-28
8
votes
1answer
3k views

What is the difference between “wrapping” a key and encrypting?

I wanted to implement a way to generate an RSA public/private key pair and protect the private key with a password. Looking into the Web crypto api, I thought the ...
8
votes
4answers
945 views

How to argue to a paranoid that RSA is safe?

From today's standpoint, most people would claim RSA to be secure. However, to my knowledge, this is purely based on the speculation that no one knows a computational feasible way to find a $d$ for ...
8
votes
1answer
10k views

Should I be using PKCS1 v1.5 or PSS for RSA signatures?

I am implementing an application where a user needs to sign some data that they have created, store it in an untrusted place, then later retrieve that data and verify it is still authentic before ...
8
votes
2answers
1k views

How does Clifford Cocks 'Non-Secret Encryption' work?

I have read Clifford Cocks "A Note on 'Non-secret Encryption'" and thought I would try to implement this, but I don't seem to be able to get it to work. I'm obviously missing something. From the ...
8
votes
2answers
3k views

RSA blind signatures in practice

Hi I have a problem with moving my blind signature implementation from educational (textbook RSA) to more practical (padded RSA) side. David Chaums paper gives a following figure: $r$ - blinding ...
8
votes
1answer
2k views

What does “a 15360-bit RSA key is the equivalent to a 256-bit symmetric key” mean?

NIST key management guidelines suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys. If a 15360-bit RSA key is the equivalent to a 256-bit symmetric key, does that mean ...
8
votes
2answers
2k views

How to better generate large primes: sieving and then random picking or random picking and then checking?

I'm writing an RSA algorithm, and am wondering what is the best and/or usual way to choose the initial prime numbers (p and q). I know of two methods to achieve this, one based on a prime number ...
8
votes
1answer
953 views

Adi Shamir's secret database of all primes

I was going through these presentation slides (PDF) on Crypto 2013. It summarizes the paper, Factoring RSA keys from certified smart cards: Coppersmith in the wild. In the last slide, it was ...
8
votes
1answer
415 views

In RSA, rationale for prime $p$ with $p-1$ having prime factor $u$ with $u-1$ having large prime factor?

In the 1978 RSA paper, it is recommended, among other things, to choose primes $p$ such that $(p-1)$ has a large prime factor $u$. This was motivated by Pollard's p-1 algorithm. Further, the authors ...
8
votes
1answer
183 views

Can we break RSA with an optical Fourier Transform?

We all known that RSA can be compromised using quantum Shor's algorithm. The horsepower underlying this algorithm is the Fourier transform. However, we can use alternatives to perform this function, ...
8
votes
1answer
1k views

What is the harm if I publish an encrypted RSA private key publicly?

What is the harm if I publish an encrypted RSA private key publicly? Or in this case, what is the harm if I publish many thousands or millions of them? Assuming that the private key is encrypted ...
8
votes
1answer
421 views

Deterministic RSA blinding

I have an implementation of the RSA private key operation in a context where I don't have access to an entropy source. I'd like to add blinding to it (both message and exponent), to make it resist ...

1 2 3
4
5
41