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.

learn more… | top users | synonyms

7
votes
1answer
4k 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 ...
7
votes
1answer
411 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 ...
7
votes
1answer
1k views

CKM_RSA_PKCS vs CKM_RSA_X_509 mechanisms in PKCS#11

What is the exact difference between the CKM_RSA_PKCS and CKM_RSA_X_509 mechanisms in the PKCS#11 v2.20 specification (Please ...
7
votes
2answers
1k 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 ...
7
votes
1answer
332 views

Blinding twice in RSA

I understand that if you have a message $m$, you can blind it by selecting a random $r$ and then multiplying $r^e\times m \pmod{n}$ Someone else then signs it with $d$, raising to the power of $d$: $(...
7
votes
1answer
209 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 ...
7
votes
1answer
194 views

How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?

So in the news this week, IBM have created a universal quantum computer with 5 fully functional qubits. Logic and Moore's law dictates they will be able to scale this up to a lot more qubits within a ...
7
votes
2answers
597 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 ...
7
votes
1answer
470 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 ...
7
votes
1answer
2k views

Is a private RSA key vulnerable to a chosen plaintext encrypted with that private key?

I grasp that having known plaintext encrypted with the public key doesn't provide a means of discovering the private key (that being the whole point...). But if one were in a situation where they ...
7
votes
1answer
635 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 ...
7
votes
1answer
1k views

RSA-OAEP Input Parameters

When creating padding for RSA using OAEP, a message is prepared as follows: Hash(Input Parameter) || Zeros || 1 || Message My question is, what should the Input ...
7
votes
1answer
2k 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 ...
7
votes
1answer
558 views

Is SSH public key authentication weakened by 'none' cipher?

As far as I know, SSH2 first does a key exchange based on the server host key and brings up transport authentication and encryption derived from this kex. The real authentication (password or public ...
6
votes
4answers
568 views

Why can’t the public key exponent in RSA be negative?

I am looking at why certain public keys in RSA can't be used, such as: 2 and all other even numbers (since $\gcd(\phi,e)$ must equal 1) 1 (since the cipher text would equal the message) 0 (since the ...
6
votes
3answers
733 views

Initialize a PRNG with a password

Let's assume that we have a secure PRNG. Is it "safe" to initialize it with password, or seed based on a password like SHA256(password)? If yes, is it "safe" to generate an RSA or DSA key from it? ...
6
votes
3answers
200 views

Is there an upper bound to the private exponent in RSA?

In the RSA algorithm, we choose $p$ and $q$ as prime numbers and we select a value $e$ which is coprime to $\varphi(pq)=(p-1)(q-1)$. Then we calculate $d:=e^{-1}\bmod\varphi(pq)$. My question is: ...
6
votes
3answers
6k 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 ...
6
votes
2answers
468 views

Is encrypting credit card numbers one by one with rsautl secure?

I wish to encrypt credit card numbers one by one using asymmetric encryption on the command line. My current approach is this… Encrypt: ...
6
votes
2answers
4k views

In RSA, why is it important choosing e so that it is coprime to φ(n)?

When choosing the public exponent e, it is stressed that $e$ must be coprime to $\phi(n)$, i.e. $\gcd(\phi(n), e) = 1$. I know that a common choice is to have $e = 3$ (which requires a good padding ...
6
votes
2answers
4k views

Hybrid encryption with RSA and AES versus spliting into multiple RSA messages?

I've done research about this subject, but I can't find the answer I'm looking for. The problem is that the string I want to send doesn't fit into the RSA key that the client have, and during ...
6
votes
2answers
533 views

What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures?

I am attempting to determine the strength of an incorrectly implemented 1024 bit RSA signature scheme. The weakness in the implementation is that the padding data lacks random numbers. As a result, ...
6
votes
2answers
189 views

What is wrong in the following algorithm for computing a hash function using RSA?

I'm studying for a cryto exam and have run across this question which has stumped me. What is wrong in the following algorithm for computing a hash function? Take a message $M$, generate a random ...
6
votes
2answers
121 views

RSA: Proving that $p+q-1 < 3 \sqrt{N}$, where N = pq and p,q are prime?

I'm doing some research into attacks on the RSA cryptosystem and have stumbled across Wiener's attack. Within the proof there exists the statement "$p+q-1 < 3\sqrt{N}$". No proof is given for this,...
6
votes
1answer
290 views

RSA exhibits symmetrical properties — is it possible to form a cryptanalytic attack?

This question is broken into two sections really: Symmetry in RSA I have been analyzing raw RSA and I have noticed some interesting symmetrical properties of the algorithm. Assume that $M$ is a ...
6
votes
1answer
3k views

Can an RSA private key have several public keys?

Ok, so my crpto lecturer in Uni 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 ( I am aware ...
6
votes
1answer
1k views

Why Elliptic curve cryptography are not popular in practice

RSA and ElGamal can be implemented using the technique of Elliptic curves. I am confused on why the it seems that Elliptic curves are not so popular in cryptographic applications since they provide ...
6
votes
1answer
3k views

Is a known plaintext, ciphertext, and public-key a viable attack on RSA?

Assume Alice and Bob are using RSA to create a common session key and Cindy is listening, attempting to obtain the session key. Alice and Bob each have their public- and private-key pairs ($\left[...
6
votes
1answer
1k views

In RSA encryption, does the value of e need to be random?

I am a novice programmer and am just finishing up an RSA encryption program that I am writing for practice. Currently I have the program generate a relatively small random value for the public key e. ...
6
votes
2answers
5k views

Why can’t DSA be used for encryption?

This question at StackOverflow mentions that DSA cannot be used for encrypt. But Both RSA and DSA can be used to generate public and private keys, right? (Or am I wrong?). Then why can't I use the ...
6
votes
1answer
409 views

Anonymous trust/reputation system

Suppose there are 3 persons, Alice, Bob and Peter. They are identified by their pseudonyms (public RSA keys). Alice has a key Alice, Bob has ...
6
votes
1answer
189 views

Including a “purpose” designation in a digital signature

A signature of some data can mean many different things, such as: This is a message I sent, this is a certificate I validated,... So I was surprised that common signing schemes don't include a "...
6
votes
2answers
122 views

Effect of $L_n[1/4,c]$ integer factorization on RSA-2048

Using the L-notation, integer factorization of an integer $n$ has the best known complexity of $L_n[1/3,c]$ using general number field sieve. Would discovery of an algorithm with complexity $L_n[1/4,c]...
6
votes
3answers
11k views

The modulus of RSA public key

I am studying the RSA cryptosystem. The public key consists of $(n, e)$, the modulus (product of two large primes), and the encryption exponent. I want to separate the modulus $n$ and exponent $e$. A ...
6
votes
1answer
2k views

how to use common modulus attack?

I am struck with the following problem: Let Alice, Bob, Chris and Eve communicate over a public network. They encrypt all messages they send using RSA system. Bob and Chris have the RSA modulus $...
6
votes
1answer
8k views

How much stronger is RSA-2048 compared to RSA-1024?

How much stronger is RSA-2048 compared to RSA-1024? It is hard to imagine very big numbers. So what would be your way to explain the difference to someone who doesn't know much about cryptography?
6
votes
1answer
420 views

Difference RSA keypair creation openSSL and openPGP?

Creating a 2048bits RSA keypair I figured that doing this using openssl takes as an input 32bytes of "randomness" from ...
6
votes
2answers
701 views

RSA Signature Weak Padding Attack

Assume that we have a message $m$ of size $n$, and it is padded with two 01 bytes in front. Then the signature $s$ is computed using a private key $ks$. Can we ...
6
votes
1answer
5k views

Why has the RSA factoring challenge been withdrawn?

Wikipedia states that RSA challenge has been withdrawn. Does it mean that an efficient factoring algorithm is "just around the corner"? or are there some other reasons? If the challenge was still ...
6
votes
1answer
521 views

Would RSA-encrypting a private key for itself constitute a vulnerability?

I'm planning to encrypt some individual files for storage, using the GnuPG implementation of RSA. If I happened to encrypt the private key corresponding to the public key used for encrypting -- either ...
6
votes
1answer
231 views

RSA reconstructing private key knowing MSBs

PREMISE: This question is purely theoretical because usually an attacker will not know private exponent d and can't compare it with obtained MSB bytes. Suppose an RSA 1024 bit signature. An attacker ...
6
votes
2answers
1k views

Is perfect-forward secrecy achieved with RSA?

I am new to cryptography and am going through the book Understanding Cryptography by Paar and Pelzl. From what I understand Symmetric key distribution systems like Kerberos do not provide PFS ...
6
votes
1answer
2k views

RSA with modulus product of many primes

I would like to ask what happens if we build an RSA system with modulus a product of more than 2 primes, for example let $n=p_{1}p_{2}...p_{L}$. I know only the classical RSA system with $n=pq$ with $...
6
votes
2answers
2k 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 ...
6
votes
2answers
1k views

RSA least significant bit oracle attack

I have been reading up on RSA attacks and came across one that could be called a least-significant-bit (LSB) oracle attack. For the sake of clarity lets define RSA primes $(p, q)$, private key $d$ ...
6
votes
1answer
769 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 ...
6
votes
1answer
4k views

RSA-PSS salt size

One of the inputs of RSA-PSS signing and verification is the salt size. According to PKCS#1, you must know the salt size before the verfication is carried out. However, this makes interoperability ...
6
votes
4answers
1k views

How do institutions like banks do RSA with big primes?

When encrypting with RSA it is often infeasible to decrypt by just doing c^d mod n, because for example when using the primes $(p,q)=(12553,1233)$, which are small ...
6
votes
3answers
662 views

Security equivalence proofs for breaking RSA

It is my understanding that while a practical solution to the factoring problem will definitely break RSA, it has never been proven that the security of RSA is equivalent to factoring. In otherwords, ...
6
votes
2answers
2k 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 ...